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

• URL: http://arxiv.org/abs/2508.17452v1
• Date: Sun, 24 Aug 2025 17:13:41 GMT
• Title: ReviBranch: Deep Reinforcement Learning for Branch-and-Bound with Revived Trajectories
• Authors: Dou Jiabao, Nie Jiayi, Yihang Cheng, Jinwei Liu, Yingrui Ji, Canran Xiao, Feixiang Du, Jiaping Xiao,
• Abstract summary: ReviBranch is a novel deep RL framework that constructs revived trajectories by reviving explicit historical correspondences between branching decisions and their corresponding graph states.<n>During training, ReviBranch enables agents to learn from complete structural evolution and temporal dependencies within the branching process.<n>ReviBranch outperforms state-of-the-art RL methods, reducing B&B nodes by 4.0% and LP by 2.2% on large-scale instances.
• Score: 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.

Related papers

• TopoCurate:Modeling Interaction Topology for Tool-Use Agent Training [53.93696896939915]
  Training tool-use agents typically rely on Supervised Fine-Tuning (SFT) on successful trajectories and Reinforcement Learning (RL) on pass-rate-selected tasks.<n>We propose TopoCurate, an interaction-aware framework that projects multi-trial rollouts from the same task into a unified semantic quotient topology.<n>TopoCurate achieves consistent gains of 4.2% (SFT) and 6.9% (RL) over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-03-02T10:38:54Z)
• Training Multi-Turn Search Agent via Contrastive Dynamic Branch Sampling [29.182538022605627]
  Branching Relative Policy Optimization (BranPO) is a value-free method that provides step-level contrastive supervision without dense rewards.<n>BranPO truncates trajectories near the tail and resamples alternative continuations to construct contrastive suffixes over shared prefixes.<n>To further boost efficiency and stabilize training, we introduce difficulty-aware branch sampling to adapt branching frequency across tasks, and redundant step masking to suppress uninformative actions.
  arXiv  Detail & Related papers  (2026-02-03T16:43:09Z)
• Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration [49.9937230730202]
  We propose Search-R2, a novel Actor-Refiner collaboration framework that enhances reasoning through targeted intervention.<n>Our approach decomposes the generation process into an Actor, which produces initial reasoning trajectories.<n>We show that Search-R2 consistently outperforms strong RAG and RL-based baselines across model scales.
  arXiv  Detail & Related papers  (2026-02-03T15:32:09Z)
• Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching [28.92346104523666]
  Branch-and-Bound (B&B) is the dominant approach for solving Mixed Linear Programming (MILP)<n>We propose ours, a underlinetextbfStratified underlinetextbfContrastive Training Framework for underlinetextbfMILP Branching.<n>It groups branch-and-bound nodes based on their feature distributions and trains a GCNN-based discriminative model to progressively separate nodes.
  arXiv  Detail & Related papers  (2025-11-26T06:47:11Z)
• Mixture of Ranks with Degradation-Aware Routing for One-Step Real-World Image Super-Resolution [76.66229730098759]
  In real-world image super-resolution (Real-ISR), existing approaches mainly rely on fine-tuning pre-trained diffusion models.<n>We propose a Mixture-of-Ranks (MoR) architecture for single-step image super-resolution.<n>We introduce a fine-grained expert partitioning strategy that treats each rank in LoRA as an independent expert.
  arXiv  Detail & Related papers  (2025-11-20T04:11:44Z)
• RL for Reasoning by Adaptively Revealing Rationales [36.50924054394857]
  Supervised fine-tuning (SFT) relies on dense ground-truth labels, which become increasingly costly as sequence length grows.<n>We address this by adaptive backtracking (AdaBack), a per-sample curriculum learning algorithm that reveals only a partial prefix of the target output during training.<n>We show that our adaptive curriculum over partial answers reliably solves problems that are otherwise intractable.
  arXiv  Detail & Related papers  (2025-06-22T17:46:14Z)
• Solving Offline Reinforcement Learning with Decision Tree Regression [0.0]
  This study presents a novel approach to addressing offline reinforcement learning problems by reframing them as regression tasks. We introduce two distinct frameworks: return-conditioned and return-weighted decision tree policies. Despite the simplification inherent in this reformulated approach to offline RL, our agents demonstrate performance that is at least on par with the established methods.
  arXiv  Detail & Related papers  (2024-01-21T23:50:46Z)
• Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation [62.738582127114704]
  Adar is a framework for understanding and improving the generalization of both imitation-learning-based (IL-based) and reinforcement-learning-based solvers (RL-based)
  arXiv  Detail & Related papers  (2023-10-22T03:15:36Z)
• Learning Prompt-Enhanced Context Features for Weakly-Supervised Video Anomaly Detection [37.99031842449251]
  Video anomaly detection under weak supervision presents significant challenges. We present a weakly supervised anomaly detection framework that focuses on efficient context modeling and enhanced semantic discriminability. Our approach significantly improves the detection accuracy of certain anomaly sub-classes, underscoring its practical value and efficacy.
  arXiv  Detail & Related papers  (2023-06-26T06:45:16Z)
• Semantically Aligned Task Decomposition in Multi-Agent Reinforcement Learning [56.26889258704261]
  We propose a novel "disentangled" decision-making method, Semantically Aligned task decomposition in MARL (SAMA) SAMA prompts pretrained language models with chain-of-thought that can suggest potential goals, provide suitable goal decomposition and subgoal allocation as well as self-reflection-based replanning. SAMA demonstrates considerable advantages in sample efficiency compared to state-of-the-art ASG methods.
  arXiv  Detail & Related papers  (2023-05-18T10:37:54Z)
• Lookback for Learning to Branch [77.32867454769936]
  Bipartite Graph Neural Networks (GNNs) have been shown to be an important component of deep learning based Mixed-Integer Linear Program (MILP) solvers. Recent works have demonstrated the effectiveness of such GNNs in replacing the branching (variable selection) in branch-and-bound (B&B) solvers.
  arXiv  Detail & Related papers  (2022-06-30T02:33:32Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• Branching Reinforcement Learning [16.437993672422955]
  We propose a novel Branching Reinforcement Learning (Branching RL) model. We investigate Regret Minimization (RM) and Reward-Free Exploration (RFE) metrics for this model. This model finds important applications in hierarchical recommendation systems and online advertising.
  arXiv  Detail & Related papers  (2022-02-16T11:19:03Z)
• Return-Based Contrastive Representation Learning for Reinforcement Learning [126.7440353288838]
  We propose a novel auxiliary task that forces the learnt representations to discriminate state-action pairs with different returns. Our algorithm outperforms strong baselines on complex tasks in Atari games and DeepMind Control suite.
  arXiv  Detail & Related papers  (2021-02-22T13:04:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.