論文の概要: Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts

• arxiv url: http://arxiv.org/abs/2204.07312v1
• Date: Fri, 15 Apr 2022 03:32:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-18 22:13:45.508964
• Title: Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
• Title（参考訳）: 枝・枝の構造解析とゴモリー混合整数切断の学習性
• Authors: Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, Ellen Vitercik
• Abstract要約: ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
• 参考スコア（独自算出の注目度）: 88.94020638263467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. These solvers are the foremost method for solving discrete optimization problems and thus have a vast array of applications in machine learning, operations research, and many other fields. Choosing cutting planes effectively is a major research topic in the theory and practice of integer programming. We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to the input integer program. Our main application of this analysis is to derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during branch-and-cut. These guarantees apply to infinite families of cutting planes, such as the family of Gomory mixed integer cuts, which are responsible for the main breakthrough speedups of integer programming solvers. We exploit geometric and combinatorial structure of branch-and-cut in our analysis, which provides a key missing piece for the recent generalization theory of branch-and-cut.
• Abstract（参考訳）: ブランチ・アンド・カット (branch-and-cut) と呼ばれる分岐・バウンドアルゴリズムにおける切断平面の組込みは、現代的な整数プログラミングソルバのバックボーンを形成する。 これらの解法は離散最適化問題を解くための最前線の手法であり、機械学習、オペレーション研究、その他多くの分野に幅広い応用がある。 切断平面を効果的に選択することは整数プログラミングの理論と実践における主要な研究テーマである。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いて分岐切断時に適用すべき切断面を決定するためのサンプル複雑性の保証を導出することである。 これらの保証は、ゴモリー混合整数切断(英語版)(gomory mixed integer cut)のような、整数プログラミングソルバの主要なブレークスルースピードアップの原因となる切断平面の無限族に適用できる。 我々は,分岐・切断の幾何学的および組合せ的構造を解析で活用し,分岐・切断の最近の一般化理論の重要な欠片となっている。

関連論文リスト

• Learning Cut Generating Functions for Integer Programming [1.1510009152620668]
  分岐とカットのアルゴリズムは、大規模な整数計画問題の解法である。 近年の進歩は、パラメータ化された族から最適な切断平面を選択するためのデータ駆動アプローチを採用している。 選択したCGFは,特定の分布に対するGMIカットよりも優れることを示す。
  論文  参考訳（メタデータ） (2024-05-22T20:56:34Z)
• Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming [11.293025183996832]
  Mixed Linear Programming (MILP)は、幅広いアプリケーションに対して強力なモデリング言語を提供する。 近年,ブランチ・アンド・バウンドアルゴリズムに関わる主要なタスクをすべて強化するための機械学習アルゴリズムの利用が爆発的な発展を遂げている。 特に、分岐とバウンドの効率の指標を自動的に最適化する機械学習アルゴリズムに注意を払っている。
  論文  参考訳（メタデータ） (2024-02-08T09:19:26Z)
• Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization [1.7398512809572197]
  本稿では,パラメータ混合整数線形最適化問題の一群を,入力データにいくつかの項目が存在する場合に解く問題について考察する。 我々は分割カットを生成するためのCPLの実装を提案し、いくつかのCPLを組み合わせることでパラメトリックインスタンスの繰り返しの性質を生かした微分可能なカットプレーンアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2023-11-06T18:57:07Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  任意の切削平面制約を加えることができるような境界伝搬手順を一般化する。 MIPソルバは、境界プロパゲーションベースの検証器を強化するために高品質な切削面を生成することができる。 本手法は,oval20ベンチマークを完全解き,oval21ベンチマークの2倍のインスタンスを検証できる最初の検証器である。
  論文  参考訳（メタデータ） (2022-08-11T10:31:28Z)
• Improved Learning Bounds for Branch-and-Cut [98.92725321081994]
  分岐とカットは整数プログラムの解法として最も広く使われているアルゴリズムである。 ますます人気のあるアプローチは、機械学習を使ってパラメータをチューニングすることだ。 本稿では,本手法のサンプル保証について述べる。
  論文  参考訳（メタデータ） (2021-11-18T04:07:29Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)

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

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