論文の概要: Learning to branch with Tree MDPs

• arxiv url: http://arxiv.org/abs/2205.11107v1
• Date: Mon, 23 May 2022 07:57:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-24 19:44:01.951010
• Title: Learning to branch with Tree MDPs
• Title（参考訳）: 木MDPによる分岐学習
• Authors: Lara Scavuzzo and Feng Yang Chen and Didier Ch\'etelat and Maxime Gasse and Andrea Lodi and Neil Yorke-Smith and Karen Aardal
• Abstract要約: 我々は、強化学習(RL)を通して、スクラッチから分岐規則を学習することを提案する。 木マルコフ決定過程 (tree Markov Decision Processes) や木MDP (tree MDPs) を提案する。 我々は,MDPが学習収束を改善するための計算実験を通じて,MILPにおける学習とブランチの問題に対処するための有望な枠組みを提供する。
• 参考スコア（独自算出の注目度）: 6.754135838894833
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: State-of-the-art Mixed Integer Linear Program (MILP) solvers combine systematic tree search with a plethora of hard-coded heuristics, such as the branching rule. The idea of learning branching rules from data has received increasing attention recently, and promising results have been obtained by learning fast approximations of the strong branching expert. In this work, we instead propose to learn branching rules from scratch via Reinforcement Learning (RL). We revisit the work of Etheve et al. (2020) and propose tree Markov Decision Processes, or tree MDPs, a generalization of temporal MDPs that provides a more suitable framework for learning to branch. We derive a tree policy gradient theorem, which exhibits a better credit assignment compared to its temporal counterpart. We demonstrate through computational experiments that tree MDPs improve the learning convergence, and offer a promising framework for tackling the learning-to-branch problem in MILPs.
• Abstract（参考訳）: State-of-the-the-art Mixed Integer Linear Program (MILP) は、系統木探索と分岐規則のようなハードコードなヒューリスティックスを組み合わせている。 近年,データから分岐規則を学習するアイデアが注目され,強い分岐エキスパートの高速近似を学習することで有望な結果が得られた。 そこで本研究では,Reinforcement Learning (RL) を通じて,スクラッチから分岐ルールを学習することを提案する。 我々は、Etheve et al. (2020) の研究を再考し、分岐学習に適したフレームワークを提供する時間的MDPの一般化であるツリーマルコフ決定過程(tree Markov Decision Processes)を提案する。 木ポリシー勾配定理を導出し、その時相のものと比べ、より優れた信用割当を示す。 我々は,MDPが学習収束を改善するための計算実験を通じて,MILPにおける学習とブランチの問題に対処するための有望な枠組みを提供する。

関連論文リスト

• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• RLET: A Reinforcement Learning Based Approach for Explainable QA with Entailment Trees [47.745218107037786]
  本稿では,強化学習に基づくEntailment Tree生成フレームワークであるRLETを提案する。 RLETは文の選択と推論生成モジュールによる単一ステップ推論を反復的に行う。 EntailmentBankデータセットの3つの設定の実験では、RLフレームワークを使用することの強みが示されている。
  論文  参考訳（メタデータ） (2022-10-31T06:45:05Z)
• 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)
• A Closer Look at Branch Classifiers of Multi-exit Architectures [103.27533521196817]
  一定の複雑さのブランチはすべてのブランチを同じに保ちますが、複雑性の増大と複雑性の低下は、それぞれバックボーンの遅かれ早かれ複雑なブランチを配置します。 知識の整合性を利用して,背骨に枝を追加する効果を探索する。 以上の結果から,複雑性が増大する分岐は,背骨の特徴的抽象的階層を最小限に破壊することが明らかとなった。
  論文  参考訳（メタデータ） (2022-04-28T08:37:25Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)
• 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)

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

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