論文の概要: ReviBranch: Deep Reinforcement Learning for Branch-and-Bound with Revived Trajectories
- arxiv url: http://arxiv.org/abs/2508.17452v1
- Date: Sun, 24 Aug 2025 17:13:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-26 18:43:45.533103
- Title: ReviBranch: Deep Reinforcement Learning for Branch-and-Bound with Revived Trajectories
- Title（参考訳）: ReviBranch: 再帰軌道を持つブランチ・アンド・バウンドのための深層強化学習
- Authors: Dou Jiabao, Nie Jiayi, Yihang Cheng, Jinwei Liu, Yingrui Ji, Canran Xiao, Feixiang Du, Jiaping Xiao,
- Abstract要約: ReviBranchは、分岐決定と対応するグラフ状態の間の明確な歴史的対応を復活させることにより、再生された軌道を構成する新しい深層RLフレームワークである。
トレーニング中、ReviBranchはエージェントがブランチプロセス内の完全な構造的進化と時間的依存関係から学ぶことができる。
ReviBranchは最先端のRL法よりも優れており、大規模インスタンスではB&Bノードを4.0%、LPを2.2%削減している。
- 参考スコア（独自算出の注目度）: 7.152780225874955
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Branch-and-bound (B&B) algorithm is the main solver for Mixed Integer Linear Programs (MILPs), where the selection of branching variable is essential to computational efficiency. However, traditional heuristics for branching often fail to generalize across heterogeneous problem instances, while existing learning-based methods such as imitation learning (IL) suffers from dependence on expert demonstration quality, and reinforcement learning (RL) struggles with limitations in sparse rewards and dynamic state representation challenges. To address these issues, we propose ReviBranch, a novel deep RL framework that constructs revived trajectories by reviving explicit historical correspondences between branching decisions and their corresponding graph states along search-tree paths. During training, ReviBranch enables agents to learn from complete structural evolution and temporal dependencies within the branching process. Additionally, we introduce an importance-weighted reward redistribution mechanism that transforms sparse terminal rewards into dense stepwise feedback, addressing the sparse reward challenge. Extensive experiments on different MILP benchmarks demonstrate that ReviBranch outperforms state-of-the-art RL methods, reducing B&B nodes by 4.0% and LP iterations by 2.2% on large-scale instances. The results highlight the robustness and generalizability of ReviBranch across heterogeneous MILP problem classes.
- Abstract（参考訳）: 分岐とバウンド(B&B)アルゴリズムは混合整数線形プログラム(MILP)の主要な解法であり、分岐変数の選択は計算効率に不可欠である。
しかしながら、分岐のための従来のヒューリスティックスは、異種問題インスタンスをまたいだ一般化に失敗することが多いが、模倣学習(IL)のような既存の学習ベースの手法は、専門家による実演品質への依存に悩まされ、強化学習(RL)はスパース報酬や動的状態表現の限界に苦しむ。
これらの問題に対処するために,枝分かれ決定と対応するグラフ状態との明示的な歴史的対応を探索木経路に沿って復活させることにより,再生軌道を構成する新しい深部RLフレームワークであるReviBranchを提案する。
トレーニング中、ReviBranchはエージェントがブランチプロセス内の完全な構造的進化と時間的依存関係から学ぶことができる。
さらに,スパース終末報酬をステップワイズフィードバックに変換する重み付け報酬再分配機構を導入し,スパース報奨課題に対処する。
異なるMILPベンチマークによる大規模な実験により、ReviBranchは最先端のRL法よりも優れており、大規模インスタンスではB&Bノードを4.0%、LPイテレーションを2.2%削減している。
その結果、不均一なMILP問題クラス間でのReviBranchの堅牢性と一般化性を強調した。
関連論文リスト
- RL for Reasoning by Adaptively Revealing Rationales [36.50924054394857]
監督された微調整(SFT)は密度の高い地下構造ラベルに依存しており、シーケンスの長さが大きくなるにつれてコストが増大する。
AdaBack(アダプティブ・バックトラック)は,学習中の目標出力の部分的なプレフィックスのみを明らかにする,サンプルごとのカリキュラム学習アルゴリズムである。
部分解に対する適応的なカリキュラムは、そうでなければ難解な問題を確実に解決することを示します。
論文 参考訳（メタデータ） (2025-06-22T17:46:14Z) - Solving Offline Reinforcement Learning with Decision Tree Regression [0.0]
本研究は, オフライン強化学習問題に対して, 回帰タスクとして再検討することで, 新たなアプローチを提案する。
我々は、リターン条件付きとリターン重み付き決定ツリーポリシーの2つの異なるフレームワークを紹介します。
オフラインRLに対するこの改定されたアプローチに固有の単純化にもかかわらず、我々のエージェントは、少なくとも確立された手法と同等の性能を示す。
論文 参考訳（メタデータ） (2024-01-21T23:50:46Z) - Promoting Generalization for Exact Solvers via Adversarial Instance
Augmentation [62.738582127114704]
Adarは、模倣学習ベース(ILベース)と強化学習ベース(RLベース)の両方の一般化を理解し、改善するためのフレームワークである。
論文 参考訳（メタデータ） (2023-10-22T03:15:36Z) - Learning Prompt-Enhanced Context Features for Weakly-Supervised Video
Anomaly Detection [37.99031842449251]
弱い監督下での映像異常検出は重大な課題を呈する。
本稿では,効率的なコンテキストモデリングとセマンティック識別性の向上に焦点をあてた,弱教師付き異常検出フレームワークを提案する。
提案手法は,特定の異常なサブクラスの検出精度を大幅に向上させ,その実用的価値と有効性を裏付けるものである。
論文 参考訳（メタデータ） (2023-06-26T06:45:16Z) - Semantically Aligned Task Decomposition in Multi-Agent Reinforcement
Learning [56.26889258704261]
我々は,MARL(SAMA)における意味的アライズされたタスク分解という,新しい「不整合」意思決定手法を提案する。
SAMAは、潜在的な目標を示唆し、適切な目標分解とサブゴールアロケーションを提供するとともに、自己回帰に基づくリプランニングを提供する、チェーン・オブ・シントによる事前訓練された言語モデルを促進する。
SAMAは, 最先端のASG法と比較して, 試料効率に有意な優位性を示す。
論文 参考訳（メタデータ） (2023-05-18T10:37:54Z) - Lookback for Learning to Branch [77.32867454769936]
Bipartite Graph Neural Networks (GNN) は、ディープラーニングに基づくMixed-Integer Linear Program (MILP) の重要コンポーネントであることが示されている。
近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)を置き換える上で、そのようなGNNの有効性が実証されている。
論文 参考訳（メタデータ） (2022-06-30T02:33:32Z) - 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) - Branching Reinforcement Learning [16.437993672422955]
分岐強化学習(ブランチングRL)モデルを提案する。
本稿では,Regret Minimization(RM)とReward-Free Exploration(RFE)の指標について検討する。
このモデルは階層的なレコメンデーションシステムやオンライン広告に重要な応用を見出す。
論文 参考訳（メタデータ） (2022-02-16T11:19:03Z) - Return-Based Contrastive Representation Learning for Reinforcement
Learning [126.7440353288838]
そこで本研究では,学習表現に異なる戻り値を持つ状態-動作ペアを判別させる新しい補助タスクを提案する。
アルゴリズムはatariゲームやdeepmindコントロールスイートの複雑なタスクのベースラインを上回っています。
論文 参考訳（メタデータ） (2021-02-22T13:04:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。