論文の概要: Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2511.09219v2
• Date: Wed, 19 Nov 2025 12:58:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-20 13:41:21.064418
• Title: Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization
• Title（参考訳）: ブランチ・アンド・バウンドにおけるプランニング:エクササイズ・コンビネーション最適化のためのモデルベース強化学習
• Authors: Paul Strang, Zacharie Alès, Côme Bissuel, Safia Kedad-Sidhoum, Emmanuel Rachelson,
• Abstract要約: Mixed-Integer Linear Programming (MILP)は、多くの実世界の最適化(CO)問題の中核にあり、伝統的にブランチ・アンド・バウンド(B&B)によって解決されている。 モデルベース強化学習(MBRL)エージェントであるPlan-and-Branch-and-Bound(PlanB&B)を導入する。
• 参考スコア（独自算出の注目度）: 5.089078998562186
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed-Integer Linear Programming (MILP) lies at the core of many real-world combinatorial optimization (CO) problems, traditionally solved by branch-and-bound (B&B). A key driver influencing B&B solvers efficiency is the variable selection heuristic that guides branching decisions. Looking to move beyond static, hand-crafted heuristics, recent work has explored adapting traditional reinforcement learning (RL) algorithms to the B&B setting, aiming to learn branching strategies tailored to specific MILP distributions. In parallel, RL agents have achieved remarkable success in board games, a very specific type of combinatorial problems, by leveraging environment simulators to plan via Monte Carlo Tree Search (MCTS). Building on these developments, we introduce Plan-and-Branch-and-Bound (PlanB&B), a model-based reinforcement learning (MBRL) agent that leverages a learned internal model of the B&B dynamics to discover improved branching strategies. Computational experiments empirically validate our approach, with our MBRL branching agent outperforming previous state-of-the-art RL methods across four standard MILP benchmarks.
• Abstract（参考訳）: Mixed-Integer Linear Programming (MILP) は、多くの実世界の組合せ最適化(CO)問題の中核にあり、伝統的にブランチ・アンド・バウンド(B&B)によって解決されている。 B&Bソルバの効率に影響を与える重要なドライバは、分岐決定を導く変数選択ヒューリスティックである。 静的な手作りヒューリスティックスを超えて、最近の研究は、従来の強化学習(RL)アルゴリズムをB&B設定に適用し、特定のMILP分布に適した分岐戦略を学習することを目的としている。 並行して、RLエージェントは、モンテカルロ木探索(MCTS)を介して計画する環境シミュレータを活用することで、非常に特殊な組合せ問題であるボードゲームにおいて顕著な成功を収めた。 モデルベース強化学習(MBRL)エージェントであるPlan-and-Branch-and-Bound(PlanB&B)を導入する。 MBRL分岐剤は4つの標準MILPベンチマークで従来の最先端RL法よりも優れていた。

関連論文リスト

• A Markov Decision Process for Variable Selection in Branch & Bound [4.802758600019421]
  ブランチとバウンドソルバのパフォーマンスに影響を与える重要な要因は、分岐決定を管理する変数の選択である。 最近のコントリビューションでは、B&B設定に強化学習アルゴリズムを適用して最適な分岐ポリシーを学習しようと試みている。 我々は,B&Bにおける変数選択のための基本的バニラMDP式であるBBMDPを導入し,広い範囲のRLアルゴリズムを活用する。
  論文  参考訳（メタデータ） (2025-10-22T08:15:32Z)
• AgentGym-RL: Training LLM Agents for Long-Horizon Decision Making through Multi-Turn Reinforcement Learning [129.44038804430542]
  本稿では,マルチターン対話型意思決定のためのLLMエージェントをRLで学習する新しいフレームワークであるAgentGym-RLを紹介する。 本研究では,探索-探索バランスと安定したRL最適化のためのトレーニング手法であるScalingInter-RLを提案する。 当社のエージェントは、さまざまな環境にまたがる27のタスクで、商用モデルにマッチするか、超えています。
  論文  参考訳（メタデータ） (2025-09-10T16:46:11Z)
• Revisiting LLM Reasoning via Information Bottleneck [57.519119962528166]
  大規模言語モデル(LLM)は、最近、検証可能な報酬付き強化学習(RLVR)を通じて推論能力の顕著な進歩を示した。 本稿では,情報ボトルネック(IB)の原理に基づくLLM推論の理論的特徴について述べる。 IB対応推論最適化(IBRO)を提案する。
  論文  参考訳（メタデータ） (2025-07-24T13:14:25Z)
• Enhancing Offline Model-Based RL via Active Model Selection: A Bayesian Optimization Perspective [11.20804263996665]
  オフラインモデルベース強化学習(MBRL)は、事前収集データのみから、適切なパフォーマンスのポリシを学習するための競争フレームワークとして機能する。 我々は,オンラインインタラクション予算の少ないオフラインMBRLにおけるモデル選択を強化する,アクティブモデル選択フレームワークBOMSを提案する。 BOMSは、オフライントレーニングデータのわずか1%-2.5%に匹敵する少額のオンラインインタラクションによって、ベースラインメソッドよりも改善されていることを示す。
  論文  参考訳（メタデータ） (2025-02-17T06:34:58Z)
• MALT: Improving Reasoning with Multi-Agent LLM Training [67.76186488361685]
  MALT(Multi-Agent LLM Training)は、推論プロセスを生成、検証、改善ステップに分割する、新しいポストトレーニング戦略である。 MATH、GSM8K、CSQAでは、MALTは、それぞれ15.66%、7.42%、9.40%の相対的な改善で同じベースラインLLMを上回っている。
  論文  参考訳（メタデータ） (2024-12-02T19:30:36Z)
• When to Update Your Model: Constrained Model-based Reinforcement Learning [50.74369835934703]
  モデルベースRL(MBRL)の非遅延性能保証のための新規で一般的な理論スキームを提案する。 続いて導いた境界は、モデルシフトとパフォーマンス改善の関係を明らかにします。 さらなる例では、動的に変化する探索からの学習モデルが、最終的なリターンの恩恵をもたらすことが示されている。
  論文  参考訳（メタデータ） (2022-10-15T17:57:43Z)
• A Unified Framework for Alternating Offline Model Training and Policy Learning [62.19209005400561]
  オフラインモデルに基づく強化学習では、歴史的収集データから動的モデルを学び、学習モデルと固定データセットを用いてポリシー学習を行う。 提案手法は,本手法が期待するリターンを最小限に抑えるための,反復的なオフラインMBRLフレームワークを開発する。 提案する統一型モデル政治学習フレームワークにより、我々は、広範囲の連続制御オフライン強化学習データセット上での競合性能を実現する。
  論文  参考訳（メタデータ） (2022-10-12T04:58:51Z)
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch [13.024115985194932]
  本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。 我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
  論文  参考訳（メタデータ） (2022-06-14T16:35:58Z)
• 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)
• On Multi-objective Policy Optimization as a Tool for Reinforcement Learning: Case Studies in Offline RL and Finetuning [24.264618706734012]
  より効率的な深層強化学習アルゴリズムの開発方法について述べる。 ケーススタディとして,オフラインRLとファインタニングに注目した。 専門家の混合蒸留(DiME)について紹介する オフラインのRLでは、DMEが最先端のアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-15T14:59:14Z)

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

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