論文の概要: Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming

• arxiv url: http://arxiv.org/abs/2404.12638v1
• Date: Fri, 19 Apr 2024 05:40:25 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-22 16:05:28.729517
• Title: Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming
• Title（参考訳）: 効率的な混合整数計画のための階層シーケンス/セットモデルによるカットの学習
• Authors: Jie Wang, Zhihai Wang, Xijun Li, Yufei Kuang, Zhihao Shi, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, Feng Wu,
• Abstract要約: 混合整数線形プログラム(MILP)の解法における切削平面(カット)の役割 カット選択ポリシーを学習するための新しい階層型シーケンス/セットモデル(HEM)を提案する。 HEMは、(P1)-(P3)を同時に扱う最初のデータ駆動手法である。
• 参考スコア（独自算出の注目度）: 61.59888010725235
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs), which formulate many important real-world applications. Cut selection heavily depends on (P1) which cuts to prefer and (P2) how many cuts to select. Although modern MILP solvers tackle (P1)-(P2) by human-designed heuristics, machine learning carries the potential to learn more effective heuristics. However, many existing learning-based methods learn which cuts to prefer, neglecting the importance of learning how many cuts to select. Moreover, we observe that (P3) what order of selected cuts to prefer significantly impacts the efficiency of MILP solvers as well. To address these challenges, we propose a novel hierarchical sequence/set model (HEM) to learn cut selection policies. Specifically, HEM is a bi-level model: (1) a higher-level module that learns how many cuts to select, (2) and a lower-level module -- that formulates the cut selection as a sequence/set to sequence learning problem -- to learn policies selecting an ordered subset with the cardinality determined by the higher-level module. To the best of our knowledge, HEM is the first data-driven methodology that well tackles (P1)-(P3) simultaneously. Experiments demonstrate that HEM significantly improves the efficiency of solving MILPs on eleven challenging MILP benchmarks, including two Huawei's real problems.
• Abstract（参考訳）: カット平面(カット)は、多くの重要な実世界の応用を定式化する混合整数線形プログラム(MILP)の解法において重要な役割を果たす。 カット選択は、選択するカット数(P1)と選択するカット数(P2)に大きく依存する。 現代のMILPソルバは人間設計のヒューリスティックスによって(P1)-(P2)に取り組むが、機械学習はより効果的なヒューリスティックスを学ぶ可能性を秘めている。 しかし、既存の学習ベースの方法の多くは、どのカットを好むかを学び、どのカットを選ぶかを学ぶことの重要性を無視している。 さらに, (P3) 選択したカットの順序がMILPソルバの効率にも大きく影響することが確認された。 これらの課題に対処するために、カット選択ポリシーを学習するための新しい階層的シーケンス/セットモデル(HEM)を提案する。 HEMは、(1)選択するカット数を学習する高レベルモジュール、(2)、および、カット選択をシーケンス/セットからシーケンス学習問題として定式化する低レベルモジュールの2レベルモデルであり、高レベルモジュールによって決定される濃度で順序付けられたサブセットを選択するポリシーを学習する。 私たちの知る限りでは、HEMは(P1)-(P3)を同時に取り組んだ最初のデータ駆動方法論です。 HEMは、Huaweiの2つの本当の問題を含む11の挑戦的なMILPベンチマークで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)
• 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 Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning [80.45697245527019]
  我々は、最良限の改善をもたらすカットを明示的に目指している欲求選択規則が、カット選択に対して強い決定を下すことを示す。 本研究では,頭頂部の専門家を対象とした模擬学習のための新しいニューラルアーキテクチャ(NeuralCut)を提案する。
  論文  参考訳（メタデータ） (2022-06-27T16:07:27Z)
• The Paradox of Choice: Using Attention in Hierarchical Reinforcement Learning [59.777127897688594]
  サブゴールオプションのさらなる学習に使用できる、オンラインでモデルフリーなアルゴリズムを提案する。 訓練データ収集におけるハード・ソフト・アテンションの役割,長期的タスクにおける抽象的価値学習,および多数の選択肢に対する対処について検討する。
  論文  参考訳（メタデータ） (2022-01-24T13:18:02Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。 カットランキングは、大規模MIPのための産業用解決器に展開されている。 解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
  論文  参考訳（メタデータ） (2021-05-28T07:48:34Z)

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

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