論文の概要: Learning Pseudo-Backdoors for Mixed Integer Programs
- arxiv url: http://arxiv.org/abs/2106.05080v1
- Date: Wed, 9 Jun 2021 13:59:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 14:55:32.013038
- Title: Learning Pseudo-Backdoors for Mixed Integer Programs
- Title（参考訳）: 混合整数プログラムのための擬似バックドアの学習
- Authors: Aaron Ferber, Jialin Song, Bistra Dilkina, Yisong Yue
- Abstract要約: そこで我々は,Mixed Programs (MIP) の解法として,擬似バックドア(擬似バックドア)と呼ばれる一連の決定変数の優先順位付けを学習し,解時間を短縮する機械学習手法を提案する。
我々のアプローチは、これらの変数の分岐のみが最適積分解と最適性の証明となるような、小さな変数の集合に対応する強いバックドアの概念から着想を得ている。
強力なバックドアに対する擬似バックドアの重要な利点は、データ駆動の識別や予測に非常に適している点である。
- 参考スコア（独自算出の注目度）: 48.36587539004464
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a machine learning approach for quickly solving Mixed Integer
Programs (MIP) by learning to prioritize a set of decision variables, which we
call pseudo-backdoors, for branching that results in faster solution times.
Learning-based approaches have seen success in the area of solving
combinatorial optimization problems by being able to flexibly leverage common
structures in a given distribution of problems. Our approach takes inspiration
from the concept of strong backdoors, which corresponds to a small set of
variables such that only branching on these variables yields an optimal
integral solution and a proof of optimality. Our notion of pseudo-backdoors
corresponds to a small set of variables such that only branching on them leads
to faster solve time (which can be solver dependent). A key advantage of
pseudo-backdoors over strong backdoors is that they are much amenable to
data-driven identification or prediction. Our proposed method learns to
estimate the solver performance of a proposed pseudo-backdoor, using a labeled
dataset collected on a set of training MIP instances. This model can then be
used to identify high-quality pseudo-backdoors on new MIP instances from the
same distribution. We evaluate our method on the generalized independent set
problems and find that our approach can efficiently identify high-quality
pseudo-backdoors. In addition, we compare our learned approach against Gurobi,
a state-of-the-art MIP solver, demonstrating that our method can be used to
improve solver performance.
- Abstract（参考訳）: 本研究では,混合整数プログラム(mip)を高速に解くための機械学習手法を提案する。
学習に基づくアプローチは、与えられた問題の分布において共通構造を柔軟に活用することで、組合せ最適化問題を解決する領域で成功している。
我々のアプローチは、これらの変数の分岐のみが最適な積分解と最適性の証明をもたらすような小さな変数の集合に対応する強いバックドアの概念から着想を得ている。
我々の疑似バックドアの概念は、変数の小さなセットに対応するので、それらの上で分岐するだけで(ソルバに依存することができる)より早く解くことができる。
強力なバックドアに対する擬似バックドアの重要な利点は、データ駆動の識別や予測に非常に適していることである。
提案手法は,学習用MIPインスタンスの集合から収集したラベル付きデータセットを用いて,提案した擬似バックドアの解法性能を推定する。
このモデルを使用して、同じ分布から新しいMIPインスタンス上の高品質な擬似バックドアを識別することができる。
一般化された独立集合問題に対する本手法の評価を行い,高品質な擬似バックドアを効率的に同定できることを見出した。
さらに,最先端のMIP解法であるGurobiに対する学習手法を比較し,その手法が解法の性能向上に有効であることを実証した。
関連論文リスト
- LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。
このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
論文 参考訳（メタデータ） (2024-10-03T18:12:29Z) - UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning [13.106799330951842]
多くの実世界の問題は、MILP(Mixed Linear Programs)として効率的にモデル化でき、ブランチ・アンド・バウンド法で解決できる。
以前の研究はMILPバックドアの存在を示しており、可能であれば分岐の優先順位付けが実行時間の短縮につながるような変数の小さなセットである。
過去の研究は、ランダムにサンプリングされたバックドアの相対的な解法速度をランク付けして推定し、最高ランクのバックドア候補を使うかどうかを決定する。
本稿では,モンテカルロ木探索法を用いて,ランダムサンプリングに頼るのではなく,学習用バックドアを収集し,コントラストに適応する。
論文 参考訳（メタデータ） (2024-01-19T03:39:43Z) - TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。
解法の効率は、分割する変数を選択するのに使用される分岐に依存する。
分岐を効率的に学習できる強化学習法を提案する。
論文 参考訳（メタデータ） (2023-06-09T14:01:26Z) - Solving Recurrent MIPs with Semi-supervised Graph Neural Networks [15.54959083707859]
本稿では,変数の値を予測することで,MIPの解を自動化・高速化するMLモデルを提案する。
私たちのアプローチは、多くの問題インスタンスが健全な特徴とソリューション構造を共有しているという観察によって動機付けられています。
例えば、輸送やルーティングの問題では、商品の量やリンクコストが変わるたびに、決定を再最適化する必要がある。
論文 参考訳（メタデータ） (2023-02-20T15:57:56Z) - Finding Backdoors to Integer Programs: A Monte Carlo Tree Search
Framework [22.824450460839245]
バックドアは、以下のプロパティを持つインスタンスの整数変数の小さなサブセットである。
MIPのバックドアを見つけるためのモンテカルロ木探索フレームワークBaMCTSを提案する。
論文 参考訳（メタデータ） (2021-10-16T00:36:53Z) - Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。
本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。
可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
論文 参考訳（メタデータ） (2021-07-02T06:46:23Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - A General Large Neighborhood Search Framework for Solving Integer Linear
Programs [46.62993477453986]
我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。
我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
論文 参考訳（メタデータ） (2020-03-29T23:08:14Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳（メタデータ） (2020-02-20T11:11:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。