Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization

• URL: http://arxiv.org/abs/2511.09219v2
• Date: Wed, 19 Nov 2025 12:58:56 GMT
• Title: Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization
• Authors: Paul Strang, Zacharie Alès, Côme Bissuel, Safia Kedad-Sidhoum, Emmanuel Rachelson,
• Abstract summary: Mixed-Integer Linear Programming (MILP) lies at the core of many real-world optimization (CO) problems, traditionally solved by branch-and-bound (B&B)<n>We introduce Plan-and-Branch-and-Bound (PlanB&B), a model-based reinforcement learning (MBRL) agent that leverages a learned internal model of the B&B dynamics to discover improved branching strategies.
• Score: 5.089078998562186
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed-Integer Linear Programming (MILP) lies at the core of many real-world combinatorial optimization (CO) problems, traditionally solved by branch-and-bound (B&B). A key driver influencing B&B solvers efficiency is the variable selection heuristic that guides branching decisions. Looking to move beyond static, hand-crafted heuristics, recent work has explored adapting traditional reinforcement learning (RL) algorithms to the B&B setting, aiming to learn branching strategies tailored to specific MILP distributions. In parallel, RL agents have achieved remarkable success in board games, a very specific type of combinatorial problems, by leveraging environment simulators to plan via Monte Carlo Tree Search (MCTS). Building on these developments, we introduce Plan-and-Branch-and-Bound (PlanB&B), a model-based reinforcement learning (MBRL) agent that leverages a learned internal model of the B&B dynamics to discover improved branching strategies. Computational experiments empirically validate our approach, with our MBRL branching agent outperforming previous state-of-the-art RL methods across four standard MILP benchmarks.

Related papers

• A Markov Decision Process for Variable Selection in Branch & Bound [4.802758600019421]
  A key factor influencing the performance of Branch and Bound solvers is the variable selection governing branching decisions.<n>Recent contributions have sought to adapt reinforcement learning algorithms to the B&B setting to learn optimal branching policies.<n>We introduce BBMDP, a principled vanilla MDP formulation for variable selection in B&B, allowing to leverage a broad range of RL algorithms.
  arXiv  Detail & Related papers  (2025-10-22T08:15:32Z)
• AgentGym-RL: Training LLM Agents for Long-Horizon Decision Making through Multi-Turn Reinforcement Learning [129.44038804430542]
  We introduce AgentGym-RL, a new framework to train LLM agents for multi-turn interactive decision-making through RL.<n>We propose ScalingInter-RL, a training approach designed for exploration-exploitation balance and stable RL optimization.<n>Our agents match or surpass commercial models on 27 tasks across diverse environments.
  arXiv  Detail & Related papers  (2025-09-10T16:46:11Z)
• Revisiting LLM Reasoning via Information Bottleneck [57.519119962528166]
  Large language models (LLMs) have recently demonstrated remarkable progress in reasoning capabilities through reinforcement learning with verifiable rewards (RLVR)<n>We present a theoretical characterization of LLM reasoning grounded in information bottleneck (IB) principle.<n>We propose IB-aware reasoning optimization (IBRO), a framework that encourages reasoning trajectories to be both informative about the final correct answer and generalizable.
  arXiv  Detail & Related papers  (2025-07-24T13:14:25Z)
• Enhancing Offline Model-Based RL via Active Model Selection: A Bayesian Optimization Perspective [11.20804263996665]
  offline model-based reinforcement learning (MBRL) serves as a competitive framework that can learn well-performing policies solely from pre-collected data.<n>We propose BOMS, an active model selection framework that enhances model selection in offline MBRL with only a small online interaction budget.<n>We show that BOMS improves over the baseline methods with a small amount of online interaction comparable to only $1%$-$2.5%$ of offline training data.
  arXiv  Detail & Related papers  (2025-02-17T06:34:58Z)
• Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
  Off-CMAB is the first offline learning framework for CMAB.<n>Off-CMAB combines pessimistic reward estimations with solvers.<n>Experiments on synthetic and real-world datasets highlight the superior performance of CLCB.
  arXiv  Detail & Related papers  (2025-01-31T16:56:18Z)
• MALT: Improving Reasoning with Multi-Agent LLM Training [67.76186488361685]
  MALT (Multi-Agent LLM Training) is a novel post-training strategy that divides the reasoning process into generation, verification, and refinement steps.<n>On MATH, GSM8K, and CSQA, MALT surpasses the same baseline LLM with a relative improvement of 15.66%, 7.42%, and 9.40% respectively.
  arXiv  Detail & Related papers  (2024-12-02T19:30:36Z)
• BiERL: A Meta Evolutionary Reinforcement Learning Framework via Bilevel Optimization [34.24884427152513]
  We propose a general meta ERL framework via bilevel optimization (BiERL) We design an elegant meta-level architecture that embeds the inner-level's evolving experience into an informative population representation. We perform extensive experiments in MuJoCo and Box2D tasks to verify that as a general framework, BiERL outperforms various baselines and consistently improves the learning performance for a diversity of ERL algorithms.
  arXiv  Detail & Related papers  (2023-08-01T09:31:51Z)
• When to Update Your Model: Constrained Model-based Reinforcement Learning [50.74369835934703]
  We propose a novel and general theoretical scheme for a non-decreasing performance guarantee of model-based RL (MBRL) Our follow-up derived bounds reveal the relationship between model shifts and performance improvement. A further example demonstrates that learning models from a dynamically-varying number of explorations benefit the eventual returns.
  arXiv  Detail & Related papers  (2022-10-15T17:57:43Z)
• A Unified Framework for Alternating Offline Model Training and Policy Learning [62.19209005400561]
  In offline model-based reinforcement learning, we learn a dynamic model from historically collected data, and utilize the learned model and fixed datasets for policy learning. We develop an iterative offline MBRL framework, where we maximize a lower bound of the true expected return. With the proposed unified model-policy learning framework, we achieve competitive performance on a wide range of continuous-control offline reinforcement learning datasets.
  arXiv  Detail & Related papers  (2022-10-12T04:58:51Z)
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch [13.024115985194932]
  We propose a new approach for solving the data labeling and inference issues in optimization based on the use of the reinforcement learning (RL) paradigm. We use imitation learning to bootstrap an RL agent and then use Proximal Policy (PPO) to further explore global optimal actions.
  arXiv  Detail & Related papers  (2022-06-14T16:35:58Z)
• 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)
• On Multi-objective Policy Optimization as a Tool for Reinforcement Learning: Case Studies in Offline RL and Finetuning [24.264618706734012]
  We show how to develop novel and more effective deep reinforcement learning algorithms. We focus on offline RL and finetuning as case studies. We introduce Distillation of a Mixture of Experts (DiME) We demonstrate that for offline RL, DiME leads to a simple new algorithm that outperforms state-of-the-art.
  arXiv  Detail & Related papers  (2021-06-15T14:59:14Z)

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.