# Reinforcement Learning for Node Selection in Branch-and-Bound

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 29 Sep 2023.

## Builds on (most cited first, 16 of 16)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Empirical Evaluation of Rectified Activations in Convolutional Network](https://mlsanity.com/paper/1505.00853/) (2015)
- [ReZero is All You Need: Fast Convergence at Large Depth](https://mlsanity.com/paper/2003.04887/) (2020)
- [What Matters In On-Policy Reinforcement Learning? A Large-Scale Empirical Study](https://mlsanity.com/paper/2006.05990/) (2020)
- [The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights](https://mlsanity.com/paper/2203.02433/) (2022)
- [Learning to Compare Nodes in Branch and Bound with Graph Neural Networks](https://mlsanity.com/paper/2210.16934/) (2022)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)
- [Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories](https://mlsanity.com/paper/2205.14345/) (2022)
- [A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP](https://mlsanity.com/paper/2007.03948/) (2020)
- [Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8](https://mlsanity.com/paper/2301.00587/) (2023)
- [On the generation of Metric TSP instances with a large integrality gap by branch-and-cut](https://mlsanity.com/paper/2109.02454/) (2021)

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

- [Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods](https://mlsanity.com/paper/2406.06954/) (2024)
- [Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guarantees](https://mlsanity.com/paper/2410.11061/) (2024)
- [Optimizing Quantum Circuits via ZX Diagrams using Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2504.03429/) (2025)
- [Designing faster mixed integer linear programming algorithm via learning the optimal path](https://mlsanity.com/paper/2601.16056/) (2026)

## Abstract (arXiv)

A big challenge in branch and bound lies in identifying the optimal node within the search tree from which to proceed. Current state-of-the-art selectors utilize either hand-crafted ensembles that automatically switch between naive sub-node selectors, or learned node selectors that rely on individual node data. We propose a novel simulation technique that uses reinforcement learning (RL) while considering the entire tree state, rather than just isolated nodes. To achieve this, we train a graph neural network that produces a probability distribution based on the path from the model's root to its "to-be-selected" leaves. Modelling node-selection as a probability distribution allows us to train the model using state-of-the-art RL techniques that capture both intrinsic node-quality and node-evaluation costs. Our method induces a high quality node selection policy on a set of varied and complex problem sets, despite only being trained on specially designed, synthetic travelling salesmen problem (TSP) instances. Using such a fixed pretrained policy shows significant improvements on several benchmarks in optimality gap reductions and per-node efficiency under strict time constraints.