ReviBranch: Deep Reinforcement Learning for Branch-and-Bound with Revived Trajectories

2025-08-24 · Dou Jiabao, Nie Jiayi, Yihang Cheng, Jinwei Liu, Yingrui Ji, Canran Xiao, Feixiang Du, Jiaping Xiao arxiv

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.

📄 PDF Abstract BibTeX arXiv:2508.17452

Code (0)

등록된 구현이 없습니다.

Tasks

Computational Efficiency Reinforcement Learning

Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories

2022-05-28 · Christopher W. F. Parsonson, Alexandre Laterre, Thomas D. Barrett

Combinatorial optimisation problems framed as mixed integer linear programmes (MILPs) are ubiquitous across a range of real-world applications. The canonical branch-and-bound algorithm seeks to exactly solve MILPs by con…

Imitation Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Branching Reinforcement Learning

2022-02-16 · Yihan Du, Wei Chen

In this paper, we propose a novel Branching Reinforcement Learning (Branching RL) model, and investigate both Regret Minimization (RM) and Reward-Free Exploration (RFE) metrics for this model. Unlike standard RL where th…

LEMMA Recommendation Systems reinforcement-learning Reinforcement Learning+1

Neural Networks for Lorenz Map Prediction: A Trip Through Time

2019-03-18 · Denisa Roberts

In this article the Lorenz dynamical system is revived and revisited and the current state of the art results for one step ahead forecasting for the Lorenz trajectories are published. Multitask learning is shown to help …

Enhancing Decision Transformer with Diffusion-Based Trajectory Branch Generation

2024-11-18 · Zhihong Liu, Long Qian, Zeyang Liu, Lipeng Wan 외

Decision Transformer (DT) can learn effective policy from offline datasets by converting the offline reinforcement learning (RL) into a supervised sequence modeling task, where the trajectory elements are generated auto-…

D4RL Reinforcement Learning (RL)

Tree Training: Accelerating Agentic LLMs Training via Shared Prefix Reuse

2025-11-01 · Jinghui Wang, Shaojie Wang, Yinghan Cui, Xuxing Chen 외 arxiv

Agentic large language model (LLM) training often involves multi-turn interaction trajectories that branch into multiple execution paths due to concurrent tool use, think-mode, sub-agent, context management and other run…

Reinforcement Learning