論文の概要: A Deep Instance Generative Framework for MILP Solvers Under Limited Data
Availability
- arxiv url: http://arxiv.org/abs/2310.02807v3
- Date: Mon, 11 Mar 2024 10:51:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 15:59:05.025417
- Title: A Deep Instance Generative Framework for MILP Solvers Under Limited Data
Availability
- Title（参考訳）: データ可用性に制限のあるMILPソリューションのためのディープインスタンス生成フレームワーク
- Authors: Zijie Geng, Xijun Li, Jie Wang, Xiao Li, Yongdong Zhang, Feng Wu
- Abstract要約: 我々は、MILPインスタンスのための最初の深層生成フレームワークであるG2MILPを提案する。
G2MILPはMILPインスタンスを二部グラフとして表現し、マスク付き変分オートエンコーダを元のグラフの一部を反復的に破損させ、置き換えて新しいグラフを生成する。
生成されたMILPインスタンスの品質を評価するためのベンチマークスイートを設計する。
- 参考スコア（独自算出の注目度）: 66.37474135424637
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the past few years, there has been an explosive surge in the use of
machine learning (ML) techniques to address combinatorial optimization (CO)
problems, especially mixed-integer linear programs (MILPs). Despite the
achievements, the limited availability of real-world instances often leads to
sub-optimal decisions and biased solver assessments, which motivates a suite of
synthetic MILP instance generation techniques. However, existing methods either
rely heavily on expert-designed formulations or struggle to capture the rich
features of real-world instances. To tackle this problem, we propose G2MILP,
the first deep generative framework for MILP instances. Specifically, G2MILP
represents MILP instances as bipartite graphs, and applies a masked variational
autoencoder to iteratively corrupt and replace parts of the original graphs to
generate new ones. The appealing feature of G2MILP is that it can learn to
generate novel and realistic MILP instances without prior expert-designed
formulations, while preserving the structures and computational hardness of
real-world datasets, simultaneously. Thus the generated instances can
facilitate downstream tasks for enhancing MILP solvers under limited data
availability. We design a suite of benchmarks to evaluate the quality of the
generated MILP instances. Experiments demonstrate that our method can produce
instances that closely resemble real-world datasets in terms of both structures
and computational hardness. The deliverables are released at
https://miralab-ustc.github.io/L2O-G2MILP.
- Abstract（参考訳）: 過去数年間、組合せ最適化(CO)問題、特に混合整数線形プログラム(MILP)に対処するために機械学習(ML)技術の使用が爆発的に増加した。
成果にもかかわらず、実世界のインスタンスの可用性が限られていることは、しばしば最適化された決定とバイアスド・ソルバ・アセスメントにつながり、一連の合成milpインスタンス生成技術が動機となる。
しかし、既存のメソッドは専門家が設計した定式化に大きく依存するか、現実のインスタンスのリッチな特徴を捉えるのに苦労する。
そこで本研究では,MILPインスタンスの深層生成フレームワークであるG2MILPを提案する。
特に、G2MILPはMILPインスタンスを二部グラフとして表現し、マスク付き変分オートエンコーダを用いて元のグラフの一部を反復的に破壊し、置き換えて新しいグラフを生成する。
G2MILPの魅力は、現実のデータセットの構造と計算硬度を同時に保ちながら、事前のエキスパート設計による定式化なしに、斬新で現実的なMILPインスタンスを生成することができることである。
したがって、生成されたインスタンスは、限られたデータ可用性の下でMILPソルバを強化するための下流タスクを容易にすることができる。
生成されたMILPインスタンスの品質を評価するためのベンチマークスイートを設計する。
実験により,本手法は実世界のデータセットによく似た構造と計算硬度の両方を生成できることを示した。
製品はhttps://miralab-ustc.github.io/L2O-G2MILPで公開される。
関連論文リスト
- MILP-StuDio: MILP Instance Generation via Block Structure Decomposition [55.79888361191114]
Mixed-integer linear programming (MILP) は、多くの応用において最も一般的な数学的定式化の1つである。
我々は,ブロック構造を保存して高品質なインスタンスを生成するために,ブロック構造分解(MILP-StuDio)と呼ばれる新しいMILP生成フレームワークを提案する。
論文 参考訳（メタデータ） (2024-10-30T08:33:27Z) - DIG-MILP: a Deep Instance Generator for Mixed-Integer Linear Programming
with Feasibility Guarantee [47.11455377400096]
混合整数線形プログラミング(MILP)は、多くの重要な産業アプリケーションにとって重要なNPハード問題である。
可変オートエンコーダ(VAE)に基づく深層生成フレームワークであるDIG-MILPを提案する。
論文 参考訳（メタデータ） (2023-10-20T03:45:29Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。
textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。
様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
論文 参考訳（メタデータ） (2023-05-29T17:25:26Z) - TSGM: A Flexible Framework for Generative Modeling of Synthetic Time Series [61.436361263605114]
時系列データは、研究者と産業組織間のデータの共有を妨げるため、しばしば不足または非常に敏感である。
本稿では,合成時系列の生成モデリングのためのオープンソースフレームワークである時系列生成モデリング(TSGM)を紹介する。
論文 参考訳（メタデータ） (2023-05-19T10:11:21Z) - MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers [13.790116387956703]
混合整数プログラミング(MIP)技術は最適化問題の定式化と解法を提供する。
MIP-GNNは、データ駆動の洞察でそのような問題を解決するための一般的なフレームワークである。
MIP-GNNを最先端のMIP解決器に統合し,ノード選択やウォームスタートといったタスクに適用する。
論文 参考訳（メタデータ） (2022-05-27T19:34:14Z) - Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer
Programs [0.0]
混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。
近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。
本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
論文 参考訳（メタデータ） (2022-02-07T18:52:56Z) - Learning Mixed-Integer Linear Programs from Contextual Examples [37.56298025474654]
混合整数線形プログラム(MILP)は人工知能や運用研究で広く使われている。
本稿では,文脈的事例からMILPを取得することの問題点について考察する。
また、コンテキストサンプルからMILPを学習するアルゴリズムであるMISLEをコントリビュートする。
論文 参考訳（メタデータ） (2021-07-15T05:45:52Z) - A Survey on Large-scale Machine Learning [67.6997613600942]
機械学習はデータに対する深い洞察を与え、マシンが高品質な予測を行うことを可能にする。
ほとんどの高度な機械学習アプローチは、大規模なデータを扱う場合の膨大な時間コストに悩まされる。
大規模機械学習は、ビッグデータからパターンを、同等のパフォーマンスで効率的に学習することを目的としている。
論文 参考訳（メタデータ） (2020-08-10T06:07:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。