論文の概要: 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 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) - Improving Large Language Model Fine-tuning for Solving Math Problems [20.417053742869403]
大きな言語モデルのパス・アット・ワン(pass-at-one)とパス・アット・N(pass-at-N)のパフォーマンスの間には大きなギャップがある。
挑戦的なMATHデータセットを用いて3つの微調整戦略を検討する。
我々は、微調整されたPaLM 2-Lモデルを用いて、MATHデータセット上で約58.8%の精度が得られる微調整レシピを設計する。
論文 参考訳(メタデータ) (2023-10-16T04:11:19Z) - 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) - Stepwise Model Selection for Sequence Prediction via Deep Kernel
Learning [100.83444258562263]
本稿では,モデル選択の課題を解決するために,新しいベイズ最適化(BO)アルゴリズムを提案する。
結果として得られる複数のブラックボックス関数の最適化問題を協調的かつ効率的に解くために,ブラックボックス関数間の潜在的な相関を利用する。
我々は、シーケンス予測のための段階的モデル選択(SMS)の問題を初めて定式化し、この目的のために効率的な共同学習アルゴリズムを設計し、実証する。
論文 参考訳(メタデータ) (2020-01-12T09:42:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。