論文の概要: A Markov Decision Process for Variable Selection in Branch & Bound

• arxiv url: http://arxiv.org/abs/2510.19348v1
• Date: Wed, 22 Oct 2025 08:15:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:15.343676
• Title: A Markov Decision Process for Variable Selection in Branch & Bound
• Title（参考訳）: 分岐境界における可変選択のためのマルコフ決定過程
• Authors: Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, Emmanuel Rachelson,
• Abstract要約: ブランチとバウンドソルバのパフォーマンスに影響を与える重要な要因は、分岐決定を管理する変数の選択である。 最近のコントリビューションでは、B&B設定に強化学習アルゴリズムを適用して最適な分岐ポリシーを学習しようと試みている。 我々は,B&Bにおける変数選択のための基本的バニラMDP式であるBBMDPを導入し,広い範囲のRLアルゴリズムを活用する。
• 参考スコア（独自算出の注目度）: 4.802758600019421
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and Bound (B&B). A key factor influencing the performance of B&B solvers is the variable selection heuristic governing branching decisions. Recent contributions have sought to adapt reinforcement learning (RL) algorithms to the B&B setting to learn optimal branching policies, through Markov Decision Processes (MDP) inspired formulations, and ad hoc convergence theorems and algorithms. In this work, we introduce BBMDP, a principled vanilla MDP formulation for variable selection in B&B, allowing to leverage a broad range of RL algorithms for the purpose of learning optimal B\&B heuristics. Computational experiments validate our model empirically, as our branching agent outperforms prior state-of-the-art RL agents on four standard MILP benchmarks.
• Abstract（参考訳）: Mixed-Integer Linear Programming (MILP) は、NP-hard組合せ最適化の幅広い問題に対処するために使用される強力なフレームワークであり、ブランチ・アンド・バウンド(B&B)によってしばしば解決される。 B&Bソルバの性能に影響を与える重要な要因は、分岐決定の変数選択ヒューリスティックである。 近年の貢献は、マルコフ決定過程(MDP)にインスパイアされた定式化とアドホック収束定理とアルゴリズムを通じて、最適な分岐ポリシーを学ぶために、強化学習(RL)アルゴリズムをB&B設定に適用することを目指している。 本稿では,B&B における変数選択のための基本的バニラ MDP 式である BBMDP を導入し,最適な B\&B ヒューリスティックスを学習するために,広い範囲の RL アルゴリズムを活用する。 分岐エージェントは4つの標準MILPベンチマークにおいて、最先端のRLエージェントよりも優れており、計算実験は我々のモデルを実証的に検証する。

関連論文リスト

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• Contextual Bilevel Reinforcement Learning for Incentive Alignment [42.22085862132403]
  両レベルの意思決定モデルであるCB-RL(Contextual Bilevel Reinforcement Learning)を導入する。 CB-RL は Stackelberg Game と見ることができ、リーダーとリーダーのコントロールを超えたランダムなコンテキストが同時に多くの MDP の設定を決定する。 このフレームワークは、従来の二段階最適化を超えて、報酬形成、契約理論、メカニズム設計といった様々な分野に関連性を見出す。
  論文  参考訳（メタデータ） (2024-06-03T17:54:39Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning [132.45959478064736]
  モデルベースとモデルフリー強化学習を統合した汎用フレームワークを提案する。 最適化に基づく探索のための分解可能な構造特性を持つ新しい推定関数を提案する。 本フレームワークでは,OPERA (Optimization-based Exploration with Approximation) という新しいサンプル効率アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-30T17:59:16Z)
• Model-free Reinforcement Learning for Branching Markov Decision Processes [6.402126624793774]
  分岐マルコフ決定過程の最適制御のための強化学習について検討する。 状態 (discrete-time) BMC は、他のエンティティを生成している間にペイオフを生成するエンティティの集合である。 モデルフリー強化学習手法を一般化し、未知のBMDPの最適制御戦略をその極限で計算する。
  論文  参考訳（メタデータ） (2021-06-12T13:42:15Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  本稿では,平均場近似ポリシ最適化(MF-PPO)アルゴリズムを提案する。 我々は,MF-PPOが収束のサブ線形速度で世界的最適政策を達成することを証明した。 特に、置換不変ニューラルアーキテクチャによって引き起こされる誘導バイアスは、MF-PPOが既存の競合より優れていることを示す。
  論文  参考訳（メタデータ） (2021-05-18T04:35:41Z)
• 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)

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

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