論文の概要: Learning to Select Cuts for Efficient Mixed-Integer Programming

• arxiv url: http://arxiv.org/abs/2105.13645v1
• Date: Fri, 28 May 2021 07:48:34 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-31 13:32:28.192878
• Title: Learning to Select Cuts for Efficient Mixed-Integer Programming
• Title（参考訳）: 効率的な混合整数プログラミングのためのカット選択学習
• Authors: Zeren Huang, Kerong Wang, Furui Liu, Hui-ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, Jun Wang
• Abstract要約: 複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。 カットランキングは、大規模MIPのための産業用解決器に展開されている。 解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
• 参考スコア（独自算出の注目度）: 46.60355046375608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting plane methods play a significant role in modern solvers for tackling mixed-integer programming (MIP) problems. Proper selection of cuts would remove infeasible solutions in the early stage, thus largely reducing the computational burden without hurting the solution accuracy. However, the major cut selection approaches heavily rely on heuristics, which strongly depend on the specific problem at hand and thus limit their generalization capability. In this paper, we propose a data-driven and generalizable cut selection approach, named Cut Ranking, in the settings of multiple instance learning. To measure the quality of the candidate cuts, a scoring function, which takes the instance-specific cut features as inputs, is trained and applied in cut ranking and selection. In order to evaluate our method, we conduct extensive experiments on both synthetic datasets and real-world datasets. Compared with commonly used heuristics for cut selection, the learning-based policy has shown to be more effective, and is capable of generalizing over multiple problems with different properties. Cut Ranking has been deployed in an industrial solver for large-scale MIPs. In the online A/B testing of the product planning problems with more than $10^7$ variables and constraints daily, Cut Ranking has achieved the average speedup ratio of 12.42% over the production solver without any accuracy loss of solution.
• Abstract（参考訳）: 混合整数プログラミング (MIP) 問題に対処する上で, 平面法は現代の解法において重要な役割を果たす。 カットの適切な選択は、初期の段階では実現不可能な解を除去し、解の精度を損なうことなく計算負担を大幅に削減する。 しかし、主要なカット選択アプローチは、特定の問題に強く依存するヒューリスティックスに大きく依存しており、それによって一般化能力が制限される。 本稿では,データ駆動型で一般化可能なカット選択手法であるカットランキングを,複数インスタンス学習の設定において提案する。 候補カットの品質を測定するために、インスタンス固有のカット特徴を入力として取り込んだスコア関数をトレーニングし、カットランキングと選択に応用する。 本手法を評価するために,合成データセットと実世界のデータセットの両方について広範な実験を行った。 カット選択のための一般的なヒューリスティックと比較すると、学習に基づくポリシーはより効果的であり、異なる特性を持つ複数の問題を一般化することができる。 カットランキングは大規模mips用の産業用ソルバに展開されている。 オンラインのA/Bテストでは、1日あたり10^7ドル以上の変数と制約のある製品プランニング問題があり、Cut Rankingは、ソリューションの精度を損なうことなく、製品解決器の平均スピードアップ比を12.42%達成している。

関連論文リスト

• Learning to Remove Cuts in Integer Linear Programming [57.15699051569638]
  本研究では, 学習可能なパラメトリック基準の下で, 手法の前回の繰り返しで導入された前回のカットの除去について検討する。 基本的な最適化設定では、カット削除ポリシーは、ヒューマンベースおよび機械学習誘導のカット追加ポリシーよりも大幅に改善される可能性があることを実証する。
  論文  参考訳（メタデータ） (2024-06-26T22:50:43Z)
• 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 Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning [80.45697245527019]
  我々は、最良限の改善をもたらすカットを明示的に目指している欲求選択規則が、カット選択に対して強い決定を下すことを示す。 本研究では,頭頂部の専門家を対象とした模擬学習のための新しいニューラルアーキテクチャ(NeuralCut)を提案する。
  論文  参考訳（メタデータ） (2022-06-27T16:07:27Z)
• Adaptive Cut Selection in Mixed-Integer Linear Programming [0.294944680995069]
  カットセレクション(英: cut selection)は、現代の全ての混合整数線形計画解法で用いられるサブルーチンである。 混合整数線形プログラムのファミリーを、無限に多くのファミリーワイド有効なカットと共に提示する。 特定のカット選択規則について、パラメータ空間の有限グリッド探索は常に全てのパラメータ値を見逃すことを示す。
  論文  参考訳（メタデータ） (2022-02-22T15:07:33Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• ABM: an automatic supervised feature engineering method for loss based models based on group and fused lasso [0.0]
  分類や回帰問題の解決における重要な問題は、モデルに入力される前のデータに特徴工学と変数選択を適用することである。 本稿では,グループとラッソを融合したエンドツーエンドのカットポイント選択手法を提案する。
  論文  参考訳（メタデータ） (2020-09-22T12:42:22Z)

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

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