論文の概要: Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework

• arxiv url: http://arxiv.org/abs/2110.08423v1
• Date: Sat, 16 Oct 2021 00:36:53 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-21 19:46:22.641468
• Title: Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework
• Title（参考訳）: 整数プログラムのバックドアを見つける:Monte Carlo Tree Searchフレームワーク
• Authors: Elias B. Khalil, Pashootan Vaezipoor, Bistra Dilkina
• Abstract要約: バックドアは、以下のプロパティを持つインスタンスの整数変数の小さなサブセットである。 MIPのバックドアを見つけるためのモンテカルロ木探索フレームワークBaMCTSを提案する。
• 参考スコア（独自算出の注目度）: 22.824450460839245
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In Mixed Integer Linear Programming (MIP), a (strong) backdoor is a "small" subset of an instance's integer variables with the following property: in a branch-and-bound procedure, the instance can be solved to global optimality by branching only on the variables in the backdoor. Constructing datasets of pre-computed backdoors for widely used MIP benchmark sets or particular problem families can enable new questions around novel structural properties of a MIP, or explain why a problem that is hard in theory can be solved efficiently in practice. Existing algorithms for finding backdoors rely on sampling candidate variable subsets in various ways, an approach which has demonstrated the existence of backdoors for some instances from MIPLIB2003 and MIPLIB2010. However, these algorithms fall short of consistently succeeding at the task due to an imbalance between exploration and exploitation. We propose BaMCTS, a Monte Carlo Tree Search framework for finding backdoors to MIPs. Extensive algorithmic engineering, hybridization with traditional MIP concepts, and close integration with the CPLEX solver have enabled our method to outperform baselines on MIPLIB2017 instances, finding backdoors more frequently and more efficiently.
• Abstract（参考訳）: Mixed Integer Linear Programming (MIP) では、(強い)バックドアは、インスタンスの整数変数の小さなサブセットで、以下の性質を持つ: 分岐とバウンドの手順では、バックドアの変数のみに分岐することで、インスタンスをグローバルな最適性に解決することができる。 広く使われているmipベンチマークセットや特定の問題ファミリーのための事前計算されたバックドアのデータセットを構築することで、mipの新規な構造的性質に関する新たな質問が可能になる。 既存のバックドア発見アルゴリズムは様々な方法で候補変数のサブセットをサンプリングすることに依存しており、MIPLIB2003 や MIPLIB2010 のバックドアの存在を実証している。 しかし、これらのアルゴリズムは探索と搾取の不均衡のために、そのタスクで一貫して成功するには不足している。 MIPのバックドアを見つけるためのモンテカルロ木探索フレームワークBaMCTSを提案する。 広範なアルゴリズム工学、従来のmip概念とのハイブリダイゼーション、cplexソルバとの密接な統合により、この手法はmiplib2017インスタンスのベースラインよりも優れており、より頻繁により効率的にバックドアを見つけることができる。

関連論文リスト

• 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)
• Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning [13.106799330951842]
  多くの実世界の問題は、MILP(Mixed Linear Programs)として効率的にモデル化でき、ブランチ・アンド・バウンド法で解決できる。 以前の研究はMILPバックドアの存在を示しており、可能であれば分岐の優先順位付けが実行時間の短縮につながるような変数の小さなセットである。 過去の研究は、ランダムにサンプリングされたバックドアの相対的な解法速度をランク付けして推定し、最高ランクのバックドア候補を使うかどうかを決定する。 本稿では,モンテカルロ木探索法を用いて,ランダムサンプリングに頼るのではなく,学習用バックドアを収集し,コントラストに適応する。
  論文  参考訳（メタデータ） (2024-01-19T03:39:43Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Computational Short Cuts in Infinite Domain Constraint Satisfaction [34.522661052004324]
  有限ドメインのCSPインスタンスのバックドアは変数の集合であり、各インスタンス化がインスタンスを解決可能な時間クラスに移動させる。 このような無限領域のバックドアは、有限領域のバックドアが持つ多くの正の計算特性を持つことを示す。 バックドアの代替としてサイドドアを導入します。
  論文  参考訳（メタデータ） (2022-11-18T10:37:51Z)
• 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)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Learning Pseudo-Backdoors for Mixed Integer Programs [48.36587539004464]
  そこで我々は,Mixed Programs (MIP) の解法として,擬似バックドア(擬似バックドア)と呼ばれる一連の決定変数の優先順位付けを学習し,解時間を短縮する機械学習手法を提案する。 我々のアプローチは、これらの変数の分岐のみが最適積分解と最適性の証明となるような、小さな変数の集合に対応する強いバックドアの概念から着想を得ている。 強力なバックドアに対する擬似バックドアの重要な利点は、データ駆動の識別や予測に非常に適している点である。
  論文  参考訳（メタデータ） (2021-06-09T13:59:53Z)
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
  Branch and Bound (B&B) は、Mixed-Integer Linear Programming Problem (MILP) の解法として一般的に用いられる木探索法である。 本稿では,新しい模倣学習フレームワークを提案し,分岐を表現するための新しい入力機能とアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2020-02-12T17:43:23Z)

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

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