論文の概要: Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
- arxiv url: http://arxiv.org/abs/2002.05120v4
- Date: Wed, 2 Jun 2021 20:11:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 18:43:46.777798
- Title: Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
- Title(参考訳): 分岐ポリシー学習のための分岐境界探索木パラメータ化
- Authors: Giulia Zarpellon, Jason Jo, Andrea Lodi and Yoshua Bengio
- Abstract要約: Branch and Bound (B&B) は、Mixed-Integer Linear Programming Problem (MILP) の解法として一般的に用いられる木探索法である。
本稿では,新しい模倣学習フレームワークを提案し,分岐を表現するための新しい入力機能とアーキテクチャを提案する。
- 参考スコア(独自算出の注目度): 76.83991682238666
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Branch and Bound (B&B) is the exact tree search method typically used to
solve Mixed-Integer Linear Programming problems (MILPs). Learning branching
policies for MILP has become an active research area, with most works proposing
to imitate the strong branching rule and specialize it to distinct classes of
problems. We aim instead at learning a policy that generalizes across
heterogeneous MILPs: our main hypothesis is that parameterizing the state of
the B&B search tree can aid this type of generalization. We propose a novel
imitation learning framework, and introduce new input features and
architectures to represent branching. Experiments on MILP benchmark instances
clearly show the advantages of incorporating an explicit parameterization of
the state of the search tree to modulate the branching decisions, in terms of
both higher accuracy and smaller B&B trees. The resulting policies
significantly outperform the current state-of-the-art method for "learning to
branch" by effectively allowing generalization to generic unseen instances.
- Abstract(参考訳): ブランチ・アンド・バウンド (B&B) は、Mixed-Integer Linear Programming Problem (MILP) の解法として一般的に用いられる木探索法である。
MILPの分岐ポリシーの学習は活発な研究領域となり、ほとんどの研究は、強い分岐規則を模倣し、異なる問題のクラスに特化することを提案している。
我々は、異種MILPをまたいで一般化するポリシーを学ぶことを目指しており、B&B探索木の状態のパラメータ化がこの種の一般化に役立つという仮説を立てている。
本稿では,新しい模倣学習フレームワークを提案し,分岐を表現するための新しい入力機能とアーキテクチャを紹介する。
MILPベンチマークインスタンス上での実験では,探索木の状態の明示的なパラメータ化を,高い精度とより小さなB&B木の両方の観点から分岐決定を変調する利点を明らかに示している。
結果として得られたポリシーは、"ブランチを学ぶ"という現在の最先端の手法よりもはるかに優れている。
関連論文リスト
- Learning a Decision Tree Algorithm with Transformers [80.49817544396379]
本稿では,従来のアルゴリズムから出力されたフィルタを用いてトランスフォーマーモデルを用いて,分類のための強力な決定木を生成するメタトレーについて紹介する。
次にMetaTreeをトレーニングして、強力な一般化パフォーマンスを実現するツリーを生成します。
論文 参考訳(メタデータ) (2024-02-06T07:40:53Z) - TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。
解法の効率は、分割する変数を選択するのに使用される分岐に依存する。
分岐を効率的に学習できる強化学習法を提案する。
論文 参考訳(メタデータ) (2023-06-09T14:01:26Z) - A General Framework for Sample-Efficient Function Approximation in
Reinforcement Learning [132.45959478064736]
モデルベースとモデルフリー強化学習を統合した汎用フレームワークを提案する。
最適化に基づく探索のための分解可能な構造特性を持つ新しい推定関数を提案する。
本フレームワークでは,OPERA (Optimization-based Exploration with Approximation) という新しいサンプル効率アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-09-30T17:59:16Z) - 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) - Learning to branch with Tree MDPs [6.754135838894833]
我々は、強化学習(RL)を通して、スクラッチから分岐規則を学習することを提案する。
木マルコフ決定過程 (tree Markov Decision Processes) や木MDP (tree MDPs) を提案する。
我々は,MDPが学習収束を改善するための計算実験を通じて,MILPにおける学習とブランチの問題に対処するための有望な枠組みを提供する。
論文 参考訳(メタデータ) (2022-05-23T07:57:32Z) - Probabilistic DAG Search [29.47649645431227]
探索空間の潜伏構造を利用して探索木間で情報を共有するための確率的フレームワークを開発する。
我々は、Tic-Tac-Toeの既存の非確率的代替品と特徴選択アプリケーションとを比較検討するアルゴリズムを実証的に見出した。
論文 参考訳(メタデータ) (2021-06-16T11:35:19Z) - Dive into Decision Trees and Forests: A Theoretical Demonstration [0.0]
決定木は"divide-and-conquer"の戦略を使用して、入力機能とラベル間の依存性に関する複雑な問題を小さなものに分割します。
近年, 計算広告, 推薦システム, 情報検索などの性能が大幅に向上している。
論文 参考訳(メタデータ) (2021-01-20T16:47:59Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳(メタデータ) (2020-07-24T17:06:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。