論文の概要: Machine Learning for Cutting Planes in Integer Programming: A Survey

• arxiv url: http://arxiv.org/abs/2302.09166v1
• Date: Fri, 17 Feb 2023 22:26:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-21 20:07:55.921434
• Title: Machine Learning for Cutting Planes in Integer Programming: A Survey
• Title（参考訳）: 整数プログラミングにおけるカットプレーンのための機械学習: 調査
• Authors: Arnaud Deza and Elias B. Khalil
• Abstract要約: 混合整数線形プログラミング(MILP)における切断平面(または切断)の選択のための機械学習(ML)技術に関する最近の研究について述べる。 MLは、データを使用してMILPインスタンスのソリューションを加速する有望なカットを特定することによって、カット選択プロセスを改善するための有望なアプローチを提供する。 本研究では,研究の成果を定量的に分析し,今後の研究への道筋を提案する。
• 参考スコア（独自算出の注目度）: 4.702456193042534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We survey recent work on machine learning (ML) techniques for selecting cutting planes (or cuts) in mixed-integer linear programming (MILP). Despite the availability of various classes of cuts, the task of choosing a set of cuts to add to the linear programming (LP) relaxation at a given node of the branch-and-bound (B&B) tree has defied both formal and heuristic solutions to date. ML offers a promising approach for improving the cut selection process by using data to identify promising cuts that accelerate the solution of MILP instances. This paper presents an overview of the topic, highlighting recent advances in the literature, common approaches to data collection, evaluation, and ML model architectures. We analyze the empirical results in the literature in an attempt to quantify the progress that has been made and conclude by suggesting avenues for future research.
• Abstract（参考訳）: 混合整数線形プログラミング(MILP)における切断平面(または切断)を選択する機械学習(ML)技術に関する最近の研究について調査する。 カットの様々なクラスが利用可能であるにもかかわらず、分岐とバウンド(B&B)ツリーの特定のノードにおける線形プログラミング(LP)緩和に追加するためのカットセットを選択するタスクは、これまで公式およびヒューリスティックなソリューションの両方に反した。 MLは、データを使用してMILPインスタンスのソリューションを加速する有望なカットを特定することによって、カット選択プロセスを改善するための有望なアプローチを提供する。 本稿では,最近の文献の進歩,データ収集への共通アプローチ,評価,MLモデルアーキテクチャについて概説する。 文献における経験的結果を分析し,今後の研究への道筋を示唆し,その成果を定量化し,結論づける。

関連論文リスト

• Learning Cut Generating Functions for Integer Programming [1.1510009152620668]
  分岐とカットのアルゴリズムは、大規模な整数計画問題の解法である。 近年の進歩は、パラメータ化された族から最適な切断平面を選択するためのデータ駆動アプローチを採用している。 選択したCGFは,特定の分布に対するGMIカットよりも優れることを示す。
  論文  参考訳（メタデータ） (2024-05-22T20:56:34Z)
• 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)
• Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning [45.1011106869493]
  オフライン強化学習(RL)問題として分岐学習を定式化する。 オフラインポリシー学習を通じてブランチランキングと呼ばれるブランチモデルをトレーニングします。 合成MIPベンチマークと実世界のタスクの実験は、ブランチランクがより効率的で堅牢であることを示している。
  論文  参考訳（メタデータ） (2022-07-26T15:34:10Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
  論文  参考訳（メタデータ） (2022-04-15T03:32:40Z)
• Learning to Reformulate for Linear Programming [11.628932152805724]
  本稿では,リニアプログラミング(LP)の強化学習に基づく再構成手法を提案する。 本研究では,2つの公共研究用LPデータセットと,実運用シナリオから収集した大規模LPデータセットに対して提案手法を実装した。
  論文  参考訳（メタデータ） (2022-01-17T04:58:46Z)
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning [56.17603785248675]
  モデルに依存しないメタラーニング (MAML) が人気のある研究分野となっている。 既存のMAMLアルゴリズムは、イテレーション毎にメタモデルを更新するためにいくつかのタスクとデータポイントをサンプリングすることで、エピソードのアイデアに依存している。 本稿では,MAMLのメモリベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-09T08:47:58Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。 カットランキングは、大規模MIPのための産業用解決器に展開されている。 解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
  論文  参考訳（メタデータ） (2021-05-28T07:48:34Z)
• A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees [17.152864798265455]
  1ノルムサポートベクトルマシンモデルに基づく新しいMIP定式化を提案し、分類問題に対する多変量 ODT の訓練を行う。 我々は, MIP定式化の線形緩和を緩和する切削面技術を提供し, 実行時間の改善と最適性を実現する。 我々の定式化は、平均的なサンプル外テストの精度で、文献において、平均で約10%上回っていることを実証する。
  論文  参考訳（メタデータ） (2020-11-06T14:17:41Z)
• A Survey on Large-scale Machine Learning [67.6997613600942]
  機械学習はデータに対する深い洞察を与え、マシンが高品質な予測を行うことを可能にする。 ほとんどの高度な機械学習アプローチは、大規模なデータを扱う場合の膨大な時間コストに悩まされる。 大規模機械学習は、ビッグデータからパターンを、同等のパフォーマンスで効率的に学習することを目的としている。
  論文  参考訳（メタデータ） (2020-08-10T06:07:52Z)

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

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