論文の概要: Adaptive Cut Selection in Mixed-Integer Linear Programming
- arxiv url: http://arxiv.org/abs/2202.10962v1
- Date: Tue, 22 Feb 2022 15:07:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-23 19:07:15.761166
- Title: Adaptive Cut Selection in Mixed-Integer Linear Programming
- Title（参考訳）: 混合整数線形計画における適応カット選択
- Authors: Mark Turner, Thorsten Koch, Felipe Serrano, Michael Winkler
- Abstract要約: カットセレクション(英: cut selection)は、現代の全ての混合整数線形計画解法で用いられるサブルーチンである。
混合整数線形プログラムのファミリーを、無限に多くのファミリーワイド有効なカットと共に提示する。
特定のカット選択規則について、パラメータ空間の有限グリッド探索は常に全てのパラメータ値を見逃すことを示す。
- 参考スコア（独自算出の注目度）: 0.294944680995069
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Cut selection is a subroutine used in all modern mixed-integer linear
programming solvers with the goal of selecting a subset of generated cuts that
induce optimal solver performance. These solvers have millions of parameter
combinations, and so are excellent candidates for parameter tuning. Cut
selection scoring rules are usually weighted sums of different measurements,
where the weights are parameters. We present a parametric family of
mixed-integer linear programs together with infinitely many family-wide valid
cuts. Some of these cuts can induce integer optimal solutions directly after
being applied, while others fail to do so even if an infinite amount are
applied. We show for a specific cut selection rule, that any finite grid search
of the parameter space will always miss all parameter values, which select
integer optimal inducing cuts in an infinite amount of our problems. We propose
a variation on the design of existing graph convolutional neural networks,
adapting them to learn cut selection rule parameters. We present a
reinforcement learning framework for selecting cuts, and train our design using
said framework over MIPLIB 2017. Our framework and design show that adaptive
cut selection does substantially improve performance over a diverse set of
instances, but that finding a single function describing such a rule is
difficult. Code for reproducing all experiments is available at
https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP.
- Abstract（参考訳）: カットセレクション(cut selection)は、現代のすべての混合整数線形計画解法で用いられるサブルーチンであり、最適な解法性能を誘導する生成されたカットのサブセットを選択することを目的としている。
これらの解法は数百万のパラメータの組み合わせを持ち、パラメータチューニングの優れた候補である。
カット選択スコアリングルールは通常、重みがパラメータである異なる測定値の重み付けされる。
我々は,無限に多数の家族全体の有効切断を伴う混合整数線形プログラムのパラメトリックファミリーを提案する。
これらの切断のいくつかは、適用された後に直接整数最適解を誘導するが、無限の量を適用してもそうしないものもある。
パラメータ空間の有限グリッド探索は、常に全てのパラメータ値を見逃し、任意の整数の最適帰納的カットを無限の量で選択することを、特定のカット選択規則として示している。
本稿では,既存のグラフ畳み込みニューラルネットワークの設計のバリエーションを提案し,カット選択規則パラメータの学習に適応する。
カットを選択するための強化学習フレームワークを提案し、そのフレームワークをMIPLIB 2017上でトレーニングする。
当社のフレームワークと設計では,適応的なカット選択は多様なインスタンス群のパフォーマンスを大幅に向上させるが,そのようなルールを記述した単一関数を見つけることは困難である。
すべての実験を再現するためのコードはhttps://github.com/opt-mucca/adaptive-cutsel-milpで入手できる。
関連論文リスト
- Learning to Remove Cuts in Integer Linear Programming [57.15699051569638]
本研究では, 学習可能なパラメトリック基準の下で, 手法の前回の繰り返しで導入された前回のカットの除去について検討する。
基本的な最適化設定では、カット削除ポリシーは、ヒューマンベースおよび機械学習誘導のカット追加ポリシーよりも大幅に改善される可能性があることを実証する。
論文 参考訳（メタデータ） (2024-06-26T22:50:43Z) - Learning Cut Generating Functions for Integer Programming [1.1510009152620668]
分岐とカットのアルゴリズムは、大規模な整数計画問題の解法である。
近年の進歩は、パラメータ化された族から最適な切断平面を選択するためのデータ駆動アプローチを採用している。
選択したCGFは,特定の分布に対するGMIカットよりも優れることを示す。
論文 参考訳（メタデータ） (2024-05-22T20:56:34Z) - Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation
Learning [80.45697245527019]
我々は、最良限の改善をもたらすカットを明示的に目指している欲求選択規則が、カット選択に対して強い決定を下すことを示す。
本研究では,頭頂部の専門家を対象とした模擬学習のための新しいニューラルアーキテクチャ(NeuralCut)を提案する。
論文 参考訳（メタデータ） (2022-06-27T16:07:27Z) - Structural Analysis of Branch-and-Cut and the Learnability of Gomory
Mixed Integer Cuts [88.94020638263467]
ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。
入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。
この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
論文 参考訳（メタデータ） (2022-04-15T03:32:40Z) - 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) - Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
複数インスタンス学習の設定において,データ駆動型で一般化可能なカット選択手法であるカットランキングを提案する。
カットランキングは、大規模MIPのための産業用解決器に展開されている。
解法の平均スピードアップ比は12.42%に達し、解の精度を損なうことなく製造された。
論文 参考訳（メタデータ） (2021-05-28T07:48:34Z) - Feature Selection Methods for Cost-Constrained Classification in Random
Forests [3.4806267677524896]
コストに敏感な特徴選択は、機能選択の問題であり、モデルに含めるための個々のコストを上昇させる。
ランダムフォレスト(Random Forests)は、機能選択において特に困難な問題を定義している。
小木構造から特徴を選択する新しい高速多変量特徴選択法であるShallow Tree Selectionを提案する。
論文 参考訳（メタデータ） (2020-08-14T11:39:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。