論文の概要: 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木の両方の観点から分岐決定を変調する利点を明らかに示している。 結果として得られたポリシーは、"ブランチを学ぶ"という現在の最先端の手法よりもはるかに優れている。

関連論文リスト

• BPP-Search: Enhancing Tree of Thought Reasoning for Mathematical Modeling Problem Solving [11.596474985695679]
  我々は、完全な数学的モデリングプロセスをキャプチャする包括的ラベルを付したStructuredORデータセットをリリースする。 本稿では,強化学習をツリー・オブ・シント構造に統合するアルゴリズムであるBPP-Searchを提案する。 BPP-Searchは、Chain-of-Thought、Self-Consistency、Tree-of-Thoughtなど、最先端の手法を大幅に上回っている。
  論文  参考訳（メタデータ） (2024-11-26T13:05:53Z)
• Technical Report: Enhancing LLM Reasoning with Reward-guided Tree Search [95.06503095273395]
  o1のような推論アプローチは困難で、研究者はこのオープンな研究領域を前進させようとさまざまな試みを行ってきた。 本稿では,報酬誘導木探索アルゴリズムを用いて,LLMの推論能力を高めるための予備的な検討を行う。
  論文  参考訳（メタデータ） (2024-11-18T16:15:17Z)
• An efficient solution to Hidden Markov Models on trees with coupled branches [0.0]
  木上の隠れモデル(HMM)のフレームワークを拡張して、データのツリーのような構造が結合されたブランチを含むシナリオに対処する。 本研究では,木系HMMと分岐した分岐木に対する確率,復号化,パラメータ学習問題を効率的に解くプログラミングアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-06-03T18:00:00Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、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)
• 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)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)

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

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