論文の概要: RL-MILP Solver: A Reinforcement Learning Approach for Solving Mixed-Integer Linear Programs with Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2411.19517v4
• Date: Tue, 11 Mar 2025 08:21:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:40:22.312781
• Title: RL-MILP Solver: A Reinforcement Learning Approach for Solving Mixed-Integer Linear Programs with Graph Neural Networks
• Title（参考訳）: RL-MILPソルバー:グラフニューラルネットワークを用いた混合整数線形プログラムの強化学習手法
• Authors: Tae-Hoon Lee, Min-Soo Kim,
• Abstract要約: 混合整数線形プログラミング (MILP) は様々な分野にまたがる最適化手法である。 本稿では,最初の実現可能な解を見つけるだけでなく,より有効な解を段階的に発見する新しい強化学習(RL)に基づく解法を提案する。
• 参考スコア（独自算出の注目度）: 3.3894236476098185
• License:
• Abstract: Mixed-integer linear programming (MILP) is a widely used optimization technique across various fields. Existing $\textit{end-to-end learning}$ methods for MILP generate values for a subset of decision variables and delegate the remaining problem to traditional MILP solvers. However, this approach often fails to guarantee solution feasibility (i.e., satisfying all constraints) due to inaccurate predictions and primarily focuses on binary decision variables. Satisfying all constraints is a prerequisite for obtaining the optimal solution, and the feasibility issue becomes even more critical with non-binary integer (integer, for short) variables. Thus, addressing the feasibility of MILP involving integer variables is crucial. To address these challenges, we propose a novel reinforcement learning (RL)-based solver that not only finds the first feasible solution but also incrementally discovers better feasible solutions without delegating the remainder to off-the-shelf solvers. Our experimental results demonstrate that the proposed method achieves (near-)optimal solutions.
• Abstract（参考訳）: 混合整数線形プログラミング (MILP) は様々な分野にまたがる最適化手法である。 既存の$\textit{end-to-end learning}$メソッドは、決定変数のサブセットの値を生成し、残りの問題を従来のMILPソルバに委譲する。 しかしながら、このアプローチは不正確な予測のために解の実現可能性(すなわち全ての制約を満たすこと)を保証することができず、主に二項決定変数に焦点を当てる。 すべての制約を満たすことは最適解を得るための前提条件であり、実現可能性問題は非バイナリ整数(整数、短値)変数に対してさらに重要となる。 したがって、整数変数を含むMILPの実現可能性に対処することが重要である。 これらの課題に対処するため、我々は、最初の実現可能な解を見つけるだけでなく、残りの解を既成の解に委譲することなく、より良い実現可能な解を段階的に発見する、新しい強化学習(RL)ベースの解法を提案する。 実験により,提案手法が最適(近距離)な解を実現することを示す。

関連論文リスト

• Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs [6.1860817947800655]
  教師なし学習方式でバイナリ変数の自動エンコーダを訓練する。 オフライン学習AEのデコーダパラメータから平面制約を切断するクラスを構築する戦略を提案する。 原始的なMIP問題への統合は、実現可能な領域を縮小したMIPの強化につながる。
  論文  参考訳（メタデータ） (2024-12-23T14:48:32Z)
• Learning to Optimize for Mixed-Integer Non-linear Programming [20.469394148261838]
  混合整数非線形プログラム(MINLP)は、エネルギーシステムや輸送といった様々な領域で発生する。 MINLPは特に大規模な解決が難しいことで知られている。 本稿では,解の積分性を保証するための2つの学習可能な補正層と,解の実現性を改善するための後処理ステップを備えた新しいディープラーニング手法を提案する。
  論文  参考訳（メタデータ） (2024-10-14T20:14:39Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。 本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。 これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
  論文  参考訳（メタデータ） (2024-03-06T04:43:22Z)
• Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems [0.6906005491572401]
  本研究では、教師なし学習(UL)に基づくCOソルバのための連続的アン緩和(CTRA)を提案する。 CTRAは、単一のトレーニング実行で多様なソリューションを見つけるための計算効率のよいフレームワークである。 数値実験により、CTRAにより、ULベースの解法は、既存の解法を繰り返すよりもはるかに高速にこれらの多様な解を見つけることができることが示された。
  論文  参考訳（メタデータ） (2024-02-03T15:31:05Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers [13.790116387956703]
  混合整数プログラミング(MIP)技術は最適化問題の定式化と解法を提供する。 MIP-GNNは、データ駆動の洞察でそのような問題を解決するための一般的なフレームワークである。 MIP-GNNを最先端のMIP解決器に統合し,ノード選択やウォームスタートといったタスクに適用する。
  論文  参考訳（メタデータ） (2022-05-27T19:34:14Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
  本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。 本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。 可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
  論文  参考訳（メタデータ） (2021-07-02T06:46:23Z)
• A Mutual Information Maximization Approach for the Spurious Solution Problem in Weakly Supervised Question Answering [60.768146126094955]
  弱々しい教師付き質問応答は通常、最終的な答えのみを監督信号として持つ。 偶然に正解を導出する刺激的な解が多数存在するかもしれないが、そのような解の訓練はモデルの性能を損なう可能性がある。 本稿では,質問応答対と予測解間の相互情報の最大化により,このような意味的相関を明示的に活用することを提案する。
  論文  参考訳（メタデータ） (2021-06-14T05:47:41Z)
• Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
  数学用語問題(mwps)の従来のニューラルネットワークソルバは、完全な監視によって学習され、多様なソリューションを生み出すことができない。 MWPを学習するためのテキスト弱教師付きパラダイムを提案する。 この手法は最終回答のアノテーションのみを必要とし、単一の問題に対して様々な解決策を生成できる。
  論文  参考訳（メタデータ） (2020-12-19T03:10:21Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。