論文の概要: Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model

• arxiv url: http://arxiv.org/abs/2302.00244v1
• Date: Wed, 1 Feb 2023 04:59:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-02 17:51:07.451636
• Title: Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model
• Title（参考訳）: 階層列モデルによる混合整数線形計画のための学習カット選択
• Authors: Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, Feng Wu
• Abstract要約: 本稿では,強化学習によるカット選択ポリシーを学習するための新しい階層型シーケンスモデル(HEM)を提案する。 HEMはデータ駆動の観点から(P1)-(P3)のカット選択に対処できる最初の方法である。 実験の結果,HEMは人間設計および学習ベースラインと比較してMILPの解法効率を著しく向上させることがわかった。
• 参考スコア（独自算出の注目度）: 81.56473654324328
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting planes (cuts) are important for solving mixed-integer linear programs (MILPs), which formulate a wide range of important real-world applications. Cut selection -- which aims to select a proper subset of the candidate cuts to improve the efficiency of solving MILPs -- heavily depends on (P1) which cuts should be preferred, and (P2) how many cuts should be selected. Although many modern MILP solvers tackle (P1)-(P2) by manually designed heuristics, machine learning offers a promising approach to learn more effective heuristics from MILPs collected from specific applications. However, many existing learning-based methods focus on learning which cuts should be preferred, neglecting the importance of learning the number of cuts that should be selected. Moreover, we observe from extensive empirical results that (P3) what order of selected cuts should be preferred has a significant impact on the efficiency of solving MILPs as well. To address this challenge, we propose a novel hierarchical sequence model (HEM) to learn cut selection policies via reinforcement learning. Specifically, HEM consists of a two-level model: (1) a higher-level model to learn the number of cuts that should be selected, (2) and a lower-level model -- that formulates the cut selection task as a sequence to sequence learning problem -- to learn policies selecting an ordered subset with the size determined by the higher-level model. To the best of our knowledge, HEM is the first method that can tackle (P1)-(P3) in cut selection simultaneously from a data-driven perspective. Experiments show that HEM significantly improves the efficiency of solving MILPs compared to human-designed and learning-based baselines on both synthetic and large-scale real-world MILPs, including MIPLIB 2017. Moreover, experiments demonstrate that HEM well generalizes to MILPs that are significantly larger than those seen during training.
• Abstract（参考訳）: カットプレーン(カット)は、様々な重要な実世界の応用を定式化する混合整数線形プログラム(MILP)の解決に重要である。 カット選択 -- 候補カットの適切なサブセットを選択してMILPを解く効率を改善する - は、(P1)、(P2)、(P2)、選択すべきカット数に大きく依存する。 多くの現代のMILPソルバは、手動で設計したヒューリスティックスによって(P1)-(P2)に取り組むが、機械学習は特定のアプリケーションから収集されたMILPからより効果的なヒューリスティックスを学ぶための有望なアプローチを提供する。 しかしながら、既存の学習ベースの手法の多くは、選択すべきカット数を学ぶことの重要性を無視して、どのカットが望ましいかを学ぶことに焦点を当てている。 さらに, 広範囲にわたる実験結果から, (p3) 選択されたカットの順序が, ミルプの解く効率にも大きな影響を与えていることを確認した。 この課題に対処するために,強化学習を通じてカット選択方針を学ぶための新しい階層的シーケンスモデル(hem)を提案する。 具体的には,(1)選択すべきカット数を学習する上位モデル,(2)シーケンス学習問題に対するシーケンスとしてカット選択タスクを定式化する下位モデル,(2)上位モデルによって決定されるサイズで順序付けられたサブセットを選択するポリシを学習する2レベルモデルで構成されている。 我々の知る限りでは、HEMはデータ駆動の観点から(P1)-(P3)のカット選択に対処できる最初の方法である。 実験により、HEMはMIPLIB 2017を含む、人工および大規模現実世界MILPの人間設計および学習ベースラインと比較して、MILPの解法効率を著しく改善することが示された。 さらに、実験により、HEMはトレーニング中に見られるものよりもかなり大きいMILPによく一般化することが示された。

関連論文リスト

• 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 to Stop Cut Generation for Efficient Mixed-Integer Linear Programming [4.85018419433297]
  混合整数線形プログラム(MILP)の解法における切削平面(カット)の役割 カットの鍵となる問題は、MILPの解法において重要なカット生成を停止するタイミングである。 効率的な停止戦略を学習するためのハイブリッドグラフ表現モデル(HYGRO)を提案する。
  論文  参考訳（メタデータ） (2024-01-31T01:09:40Z)
• Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning [92.31528918811007]
  本稿では,P1)-(P3) を同時に扱うための簡易かつ効率的な強化学習フレームワーク,すなわち,事前解決のための強化学習(RL4Presolve)を提案する。 2つの解法と8つのベンチマーク(実世界と合成)の実験により、RL4Presolveは大規模LPの解法効率を大幅に改善することを示した。
  論文  参考訳（メタデータ） (2023-10-18T09:51:59Z)
• Machine Learning for Cutting Planes in Integer Programming: A Survey [21.567191691588643]
  混合整数線形プログラミング(MILP)における切断平面(または切断)の選択のための機械学習(ML)技術に関する最近の研究について述べる。 MLは、データを使用してMILPインスタンスのソリューションを加速する有望なカットを特定することによって、カット選択プロセスを改善するための有望なアプローチを提供する。 本研究では,研究の成果を定量的に分析し,今後の研究への道筋を提案する。
  論文  参考訳（メタデータ） (2023-02-17T22:26:49Z)
• MILO: Model-Agnostic Subset Selection Framework for Efficient Model Training and Tuning [68.12870241637636]
  モデル学習からサブセット選択を分離するモデルに依存しないサブセット選択フレームワークMILOを提案する。 実験結果から、MILOはモデルを3ドル(約3,300円)でトレーニングし、ハイパーパラメータを20ドル(約2,300円)でチューニングできます。
  論文  参考訳（メタデータ） (2023-01-30T20:59:30Z)
• Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning [80.45697245527019]
  我々は、最良限の改善をもたらすカットを明示的に目指している欲求選択規則が、カット選択に対して強い決定を下すことを示す。 本研究では,頭頂部の専門家を対象とした模擬学習のための新しいニューラルアーキテクチャ(NeuralCut)を提案する。
  論文  参考訳（メタデータ） (2022-06-27T16:07:27Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。 カットランキングは、大規模MIPのための産業用解決器に展開されている。 解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
  論文  参考訳（メタデータ） (2021-05-28T07:48:34Z)

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

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