論文の概要: Learning Branching Policies for MILPs with Proximal Policy Optimization

• arxiv url: http://arxiv.org/abs/2511.12986v1
• Date: Mon, 17 Nov 2025 05:16:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:24.675881
• Title: Learning Branching Policies for MILPs with Proximal Policy Optimization
• Title（参考訳）: 近似ポリシー最適化によるMILPの分岐政策の学習
• Authors: Abdelouahed Ben Mhamed, Assia Kamal-Idrissi, Amal El Fallah Seghrouchni,
• Abstract要約: 混合線形プログラム(MILP)における分岐境界法(B&B) 現在のアプローチはImitation Learning (IL)に依存しており、専門家によるデモンストレーションに過度に適合する傾向にあり、構造的に多様なインスタンスや目に見えないインスタンスに一般化するのに苦労している。 本研究では,RLアルゴリズムであるPPO(Proximal Policy Optimization)を用いて分岐ポリシーの学習を行う新しいフレームワークであるTree-Gate Proximal Policy Optimizationを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Branch-and-Bound (B\&B) is the dominant exact solution method for Mixed Integer Linear Programs (MILP), yet its exponential time complexity poses significant challenges for large-scale instances. The growing capabilities of machine learning have spurred efforts to improve B\&B by learning data-driven branching policies. However, most existing approaches rely on Imitation Learning (IL), which tends to overfit to expert demonstrations and struggles to generalize to structurally diverse or unseen instances. In this work, we propose Tree-Gate Proximal Policy Optimization (TGPPO), a novel framework that employs Proximal Policy Optimization (PPO), a Reinforcement Learning (RL) algorithm, to train a branching policy aimed at improving generalization across heterogeneous MILP instances. Our approach builds on a parameterized state space representation that dynamically captures the evolving context of the search tree. Empirical evaluations show that TGPPO often outperforms existing learning-based policies in terms of reducing the number of nodes explored and improving p-Primal-Dual Integrals (PDI), particularly in out-of-distribution instances. These results highlight the potential of RL to develop robust and adaptable branching strategies for MILP solvers.
• Abstract（参考訳）: ブランチ・アンド・バウンド (B\&B) は混合整数線形プログラム (MILP) の厳密な解法である。 機械学習の能力の増大は、データ駆動の分岐ポリシーを学ぶことによってB\&Bを改善する努力を加速させた。 しかし、既存のほとんどのアプローチはImitation Learning (IL)に依存しており、これは専門家のデモンストレーションに過度に適合し、構造的に多様なインスタンスや目に見えないインスタンスに一般化するのに苦労する。 本研究では,RL(Reinforcement Learning)アルゴリズムであるPPO(Proximal Policy Optimization)を採用した新しいフレームワークであるTree-Gate Proximal Policy Optimization (TGPPO)を提案する。 提案手法は,探索木の進化コンテキストを動的にキャプチャするパラメータ化された状態空間表現に基づいている。 経験的評価から、TGPPOは、特にアウト・オブ・ディストリビューション・インスタンスにおいて、探索されたノード数を減らし、p-Primal-Dual Integrals (PDI)を改善するという点で、既存の学習ベースのポリシーよりも優れていることが示されている。 これらの結果は、MILPソルバの堅牢で適応可能な分岐戦略を開発するRLの可能性を強調している。

関連論文リスト

• REBEL: Reinforcement Learning via Regressing Relative Rewards [59.68420022466047]
  生成モデルの時代における最小限のRLアルゴリズムであるREBELを提案する。 理論的には、自然ポリシーグラディエントのような基本的なRLアルゴリズムはREBELの変種と見なすことができる。 我々はREBELが言語モデリングと画像生成に一貫したアプローチを提供し、PPOやDPOとより強くあるいは類似した性能を実現することを発見した。
  論文  参考訳（メタデータ） (2024-04-25T17:20:45Z)
• Surpassing legacy approaches to PWR core reload optimization with single-objective Reinforcement learning [0.0]
  単目的および多目的の最適化のための深層強化学習(DRL)に基づく手法を開発した。 本稿では、PPO(Proximal Policy Optimization)を用いて、RLに基づくアプローチの利点を実証する。 PPOは学習可能なウェイトを持つポリシーで検索機能を適応し、グローバル検索とローカル検索の両方として機能する。
  論文  参考訳（メタデータ） (2024-02-16T19:35:58Z)
• Mirror Learning: A Unifying Framework of Policy Optimisation [1.6114012813668934]
  総合政策改善(GPI)と信頼領域学習(TRL)は、現代強化学習(RL)における主要な枠組みである。 TRPOやPPOのような多くの最先端(SOTA)アルゴリズムは収束することが証明されていない。 RLのための事実上全てのSOTAアルゴリズムがミラー学習の例であることを示す。
  論文  参考訳（メタデータ） (2022-01-07T09:16:03Z)
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence [60.20076757208645]
  本稿では,正規化RLを解くためのGPMDアルゴリズムを提案する。 我々は,このアルゴリズムが次元自由な方法で,全範囲の学習率に線形に収束することを実証した。
  論文  参考訳（メタデータ） (2021-05-24T02:21:34Z)
• 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)
• Population-Guided Parallel Policy Search for Reinforcement Learning [17.360163137926]
  都市外強化学習(RL)の性能向上を図るために,新たな人口誘導型並列学習手法を提案する。 提案手法では,複数の同一学習者が独自の値関数とポリシーを共用し,共通体験再生バッファを共有し,最良のポリシー情報のガイダンスと協調して適切なポリシーを探索する。
  論文  参考訳（メタデータ） (2020-01-09T10:13:57Z)

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

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