# Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm

arXiv: https://arxiv.org/abs/2005.10026 · HTML: https://mlsanity.com/paper/2005.10026/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2020.

## Built on by (most cited first, 29 of 29)

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [Learning to Compare Nodes in Branch and Bound with Graph Neural Networks](https://mlsanity.com/paper/2210.16934/) (2022)
- [Lookback for Learning to Branch](https://mlsanity.com/paper/2206.14987/) (2022)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories](https://mlsanity.com/paper/2205.14345/) (2022)
- [An Improved Reinforcement Learning Algorithm for Learning to Branch](https://mlsanity.com/paper/2201.06213/) (2022)
- [Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation](https://mlsanity.com/paper/2310.14161/) (2023)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends](https://mlsanity.com/paper/2111.06257/) (2021)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [Online Learning for Scheduling MIP Heuristics](https://mlsanity.com/paper/2304.03755/) (2023)
- [Reinforcement Learning for Node Selection in Branch-and-Bound](https://mlsanity.com/paper/2310.00112/) (2023)
- [LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs](https://mlsanity.com/paper/2605.10401/) (2026)
- [UNSAT Solver Synthesis via Monte Carlo Forest Search](https://mlsanity.com/paper/2211.12581/) (2022)
- [Generative deep learning for decision making in gas networks](https://mlsanity.com/paper/2102.02125/) (2021)
- [Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning](https://mlsanity.com/paper/2207.13701/) (2022)
- [TreeDQN: Sample-Efficient Off-Policy Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/2306.05905/) (2023)
- [ReviBranch: Deep Reinforcement Learning for Branch-and-Bound with Revived Trajectories](https://mlsanity.com/paper/2508.17452/) (2025)
- [Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching](https://mlsanity.com/paper/2511.21107/) (2025)
- [Master-slave Deep Architecture for Top-K Multi-armed Bandits with Non-linear Bandit Feedback and Diversity Constraints](https://mlsanity.com/paper/2308.12680/) (2023)
- [Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs](https://mlsanity.com/paper/2310.14659/) (2023)
- [Discounted Pseudocosts in MILP](https://mlsanity.com/paper/2407.06237/) (2024)
- [Towards VM Rescheduling Optimization Through Deep Reinforcement Learning](https://mlsanity.com/paper/2505.17359/) (2025)
- [A Markov Decision Process for Variable Selection in Branch & Bound](https://mlsanity.com/paper/2510.19348/) (2025)
- [Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks](https://mlsanity.com/paper/2602.14772/) (2026)
- [Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching](https://mlsanity.com/paper/2604.00094/) (2026)
- [Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2610.14835/) (2026)

## Abstract (arXiv)

Mixed integer linear programs are commonly solved by Branch and Bound algorithms. A key factor of the efficiency of the most successful commercial solvers is their fine-tuned heuristics. In this paper, we leverage patterns in real-world instances to learn from scratch a new branching strategy optimised for a given problem and compare it with a commercial solver. We propose FMSTS, a novel Reinforcement Learning approach specifically designed for this task. The strength of our method lies in the consistency between a local value function and a global metric of interest. In addition, we provide insights for adapting known RL techniques to the Branch and Bound setting, and present a new neural network architecture inspired from the literature. To our knowledge, it is the first time Reinforcement Learning has been used to fully optimise the branching strategy. Computational experiments show that our method is appropriate and able to generalise well to new instances.