論文の概要: Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories

• arxiv url: http://arxiv.org/abs/2205.14345v1
• Date: Sat, 28 May 2022 06:08:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-04 21:28:46.048192
• Title: Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories
• Title（参考訳）: 反射軌道を用いた分岐境界最適化のための強化学習
• Authors: Christopher W. F. Parsonson, Alexandre Laterre, Thomas D. Barrett
• Abstract要約: 機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
• 参考スコア（独自算出の注目度）: 72.15369769265398
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimisation problems framed as mixed integer linear programmes (MILPs) are ubiquitous across a range of real-world applications. The canonical branch-and-bound (B&B) algorithm seeks to exactly solve MILPs by constructing a search tree of increasingly constrained sub-problems. In practice, its solving time performance is dependent on heuristics, such as the choice of the next variable to constrain ('branching'). Recently, machine learning (ML) has emerged as a promising paradigm for branching. However, prior works have struggled to apply reinforcement learning (RL), citing sparse rewards, difficult exploration, and partial observability as significant challenges. Instead, leading ML methodologies resort to approximating high quality handcrafted heuristics with imitation learning (IL), which precludes the discovery of novel policies and requires expensive data labelling. In this work, we propose retro branching; a simple yet effective approach to RL for branching. By retrospectively deconstructing the search tree into multiple paths each contained within a sub-tree, we enable the agent to learn from shorter trajectories with more predictable next states. In experiments on four combinatorial tasks, our approach enables learning-to-branch without any expert guidance or pre-training. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables, with ablations verifying that our retrospectively constructed trajectories are essential to achieving these results.
• Abstract（参考訳）: 混合整数線形プログラム(MILP)としてフレーム化された組合せ最適化問題は、現実世界の様々なアプリケーションに広く分布する。 標準分岐バウンド(B&B)アルゴリズムは、ますます制約されたサブプロブレムの探索木を構築することにより、MILPを正確に解く。 実際には、その解法時間パフォーマンスは、次の変数を制約('ブランチ')に選択するといったヒューリスティックに依存している。 最近、機械学習(ML)が分岐のための有望なパラダイムとして登場した。 しかし、事前の成果は強化学習(RL)の適用に苦慮しており、スパース報酬、探究の困難さ、部分的な観測可能性などを重要な課題として挙げている。 代わりに、ML手法の先導者は、新しいポリシーの発見を妨げ、高価なデータラベリングを必要とする模倣学習(IL)による高品質の手作りヒューリスティックを近似する。 本稿では,RLの分岐に対する単純かつ効果的なアプローチであるレトロ分岐を提案する。 探索木をサブツリーに含まれる複数のパスに再構成することにより、エージェントはより予測可能な次の状態の短い軌跡から学習することができる。 4つの組み合わせタスクの実験において,本手法は専門家の指導や事前学習を必要とせず,学習とブランチを可能にする。 我々は現在の最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドのパフォーマンスの20%以内に到達します。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
  大規模言語モデルは、高度なプロンプト技術で顕著な推論能力に優れています。 近年の研究では、LLMがより困難な推論タスクを解くために受動的木探索を行えるように、検索ロジックを定義するために外部プログラムを活用することが提案されている。 我々は,LLMの自律木探索能力という新しい概念を提案し,正しい解を求める探索軌跡を含む応答を自動生成する。
  論文  参考訳（メタデータ） (2023-10-14T14:14:38Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• Improving and Benchmarking Offline Reinforcement Learning Algorithms [87.67996706673674]
  この作業は、低レベルの選択とデータセットによって引き起こされるギャップを埋めることを目的としている。 3つの代表アルゴリズムを用いて20の実装選択を実証的に検討する。 CRR+とCQL+の2つの変種がD4RL上で新たな最先端を実現している。
  論文  参考訳（メタデータ） (2023-06-01T17:58:46Z)
• Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning [45.1011106869493]
  オフライン強化学習(RL)問題として分岐学習を定式化する。 オフラインポリシー学習を通じてブランチランキングと呼ばれるブランチモデルをトレーニングします。 合成MIPベンチマークと実世界のタスクの実験は、ブランチランクがより効率的で堅牢であることを示している。
  論文  参考訳（メタデータ） (2022-07-26T15:34:10Z)
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch [13.024115985194932]
  本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。 我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
  論文  参考訳（メタデータ） (2022-06-14T16:35:58Z)
• Learning to branch with Tree MDPs [6.754135838894833]
  我々は、強化学習(RL)を通して、スクラッチから分岐規則を学習することを提案する。 木マルコフ決定過程 (tree Markov Decision Processes) や木MDP (tree MDPs) を提案する。 我々は,MDPが学習収束を改善するための計算実験を通じて,MILPにおける学習とブランチの問題に対処するための有望な枠組みを提供する。
  論文  参考訳（メタデータ） (2022-05-23T07:57:32Z)
• Branching Reinforcement Learning [16.437993672422955]
  分岐強化学習(ブランチングRL)モデルを提案する。 本稿では,Regret Minimization(RM)とReward-Free Exploration(RFE)の指標について検討する。 このモデルは階層的なレコメンデーションシステムやオンライン広告に重要な応用を見出す。
  論文  参考訳（メタデータ） (2022-02-16T11:19:03Z)
• Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm [0.10499611180329801]
  現実世界のインスタンスのパターンを活用して、与えられた問題に最適化された新しいブランチ戦略をスクラッチから学習します。 本稿では,この課題に特化して設計された新しい強化学習手法であるFMSTSを提案する。
  論文  参考訳（メタデータ） (2020-05-20T13:15:48Z)
• 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)

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

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