A Markov Decision Process for Variable Selection in Branch & Bound

2025/10/22 by Paul Strang, Strang, Paul, Zacharie Alès +9
Computer Science · Engineering · #Branch and bound #Branching (polymer chemistry) #Constraint Satisfaction and Optimization #Heuristic #Leverage (statistics) #Linear programming #Markov chain #Markov decision process #Partially observable Markov decision process #Reinforcement Learning in Robotics #Reinforcement learning #Selection (genetic algorithm) #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.2510.19348

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2025/10/22 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28

Abstract

Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and Bound (B&B). A key factor influencing the performance of B&B solvers is the variable selection heuristic governing branching decisions. Recent contributions have sought to adapt reinforcement learning (RL) algorithms to the B&B setting to learn optimal branching policies, through Markov Decision Processes (MDP) inspired formulations, and ad hoc convergence theorems and algorithms. In this work, we introduce BBMDP, a principled vanilla MDP formulation for variable selection in B&B, allowing to leverage a broad range of RL algorithms for the purpose of learning optimal B&B heuristics. Computational experiments validate our model empirically, as our branching agent outperforms prior state-of-the-art RL agents on four standard MILP benchmarks.

Citations

• Stop Regressing: Training Value Functions via Classification for Scalable Deep RL
• Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming
• A Survey of Temporal Credit Assignment in Deep Reinforcement Learning
• Combinatorial Optimization with Policy Adaptation using Latent Space Search
• RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark
• Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model
• Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning
• Learning to branch with Tree MDPs
• Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs
• Solving Mixed Integer Programs Using Neural Networks
• Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers
• Monte-Carlo Tree Search as Regularized Policy Optimization
• Reinforcement Learning for Integer Programming: Learning to Cut
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon
• Machine learning for combinatorial optimization: A methodological tour d’horizon
• Implicit Quantile Networks for Distributional Reinforcement Learning
• Improving Regression Performance with Distributional Losses
• Attention, Learn to Solve Routing Problems!
• Rainbow: Combining Improvements in Deep Reinforcement Learning
• A Distributional Perspective on Reinforcement Learning
• Prioritized Experience Replay
• Deep Reinforcement Learning with Double Q-learning

Related

• Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization
• Learning to branch with Tree MDPs
• TreeDQN: Learning to minimize Branch-and-Bound tree
• Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
• An Improved Reinforcement Learning Algorithm for Learning to Branch