論文の概要: Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2401.17527v2
• Date: Fri, 2 Feb 2024 05:54:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-05 12:01:07.653002
• Title: Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming
• Title（参考訳）: 効率的な混合整数線形プログラミングのためのカット生成の停止学習
• Authors: Haotian Ling, Zhihai Wang, Jie Wang
• Abstract要約: 混合整数線形プログラム(MILP)の解法における切削平面(カット)の役割 カットの鍵となる問題は、MILPの解法において重要なカット生成を停止するタイミングである。 効率的な停止戦略を学習するためのハイブリッドグラフ表現モデル(HYGRO)を提案する。
• 参考スコア（独自算出の注目度）: 4.85018419433297
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs), as they significantly tighten the dual bounds and improve the solving performance. A key problem for cuts is when to stop cuts generation, which is important for the efficiency of solving MILPs. However, many modern MILP solvers employ hard-coded heuristics to tackle this problem, which tends to neglect underlying patterns among MILPs from certain applications. To address this challenge, we formulate the cuts generation stopping problem as a reinforcement learning problem and propose a novel hybrid graph representation model (HYGRO) to learn effective stopping strategies. An appealing feature of HYGRO is that it can effectively capture both the dynamic and static features of MILPs, enabling dynamic decision-making for the stopping strategies. To the best of our knowledge, HYGRO is the first data-driven method to tackle the cuts generation stopping problem. By integrating our approach with modern solvers, experiments demonstrate that HYGRO significantly improves the efficiency of solving MILPs compared to competitive baselines, achieving up to 31% improvement.
• Abstract（参考訳）: 混合整数線形プログラム (MILP) の解法において, 切断面 (カット) が重要な役割を担っている。 カットの鍵となる問題は、MILPの解法において重要なカット生成を停止するタイミングである。 しかし、現代のMILP解法の多くは、この問題に対処するためにハードコードなヒューリスティックを用いており、特定のアプリケーションからMILPのパターンを無視する傾向にある。 この課題に対処するために,カット生成停止問題を強化学習問題として定式化し,効果的な停止戦略を学ぶための新しいハイブリッドグラフ表現モデル(hygro)を提案する。 HYGROの魅力的な特徴は、MILPの動的特徴と静的特徴の両方を効果的に捉え、停止戦略の動的決定を可能にすることである。 我々の知る限りでは、HYGROはカット生成停止問題に対処する最初のデータ駆動手法である。 提案手法を現代の解法と統合することにより, HYGROはMILPの解法効率を競争ベースラインと比較して有意に向上し, 最大31%の改善が達成された。

関連論文リスト

• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
  本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。 重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。 フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
  論文  参考訳（メタデータ） (2024-08-16T02:07:34Z)
• CHARME: A chain-based reinforcement learning approach for the minor embedding problem [16.24890195949869]
  本稿では,CHARME という名前の小さな埋め込み問題に対処するために,強化学習(RL)技術を利用した新しい手法を提案する。 CHARMEには、ポリシーモデリングのためのグラフニューラルネットワーク(GNN)アーキテクチャ、ソリューションの有効性を保証する状態遷移アルゴリズム、効果的なトレーニングのための順序探索戦略の3つの重要なコンポーネントが含まれている。 詳細では、CHARME は Minorminer や ATOM のような高速な埋め込み法に比べて優れた解が得られる。
  論文  参考訳（メタデータ） (2024-06-11T10:12:10Z)
• Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming [61.59888010725235]
  混合整数線形プログラム(MILP)の解法における切削平面(カット)の役割 カット選択ポリシーを学習するための新しい階層型シーケンス/セットモデル(HEM)を提案する。 HEMは、(P1)-(P3)を同時に扱う最初のデータ駆動手法である。
  論文  参考訳（メタデータ） (2024-04-19T05:40:25Z)
• Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model [81.56473654324328]
  本稿では,強化学習によるカット選択ポリシーを学習するための新しい階層型シーケンスモデル(HEM)を提案する。 HEMはデータ駆動の観点から(P1)-(P3)のカット選択に対処できる最初の方法である。 実験の結果,HEMは人間設計および学習ベースラインと比較してMILPの解法効率を著しく向上させることがわかった。
  論文  参考訳（メタデータ） (2023-02-01T04:59:55Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning [80.45697245527019]
  我々は、最良限の改善をもたらすカットを明示的に目指している欲求選択規則が、カット選択に対して強い決定を下すことを示す。 本研究では,頭頂部の専門家を対象とした模擬学習のための新しいニューラルアーキテクチャ(NeuralCut)を提案する。
  論文  参考訳（メタデータ） (2022-06-27T16:07:27Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。 本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
  論文  参考訳（メタデータ） (2020-06-17T20:19:25Z)

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

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