# Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 118 references that are in the map.
- First posted on arXiv 5 Nov 2021.

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

- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/1911.09539/) (2019)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies](https://mlsanity.com/paper/2002.05120/) (2020)
- [Learning to Search Better Than Your Teacher](https://mlsanity.com/paper/1502.02206/) (2015)
- [Learning to Select Cuts for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2105.13645/) (2021)
- [Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems](https://mlsanity.com/paper/1902.01697/) (2019)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)
- [Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem](https://mlsanity.com/paper/1709.09972/) (2017)
- [Theoretical challenges towards cutting-plane selection](https://mlsanity.com/paper/1805.02782/) (2018)
- [A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP](https://mlsanity.com/paper/2007.03948/) (2020)
- [DASH: Dynamic Approach for Switching Heuristics](https://mlsanity.com/paper/1307.4689/) (2013)
- [Cuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman Problem](https://mlsanity.com/paper/1805.01415/) (2018)

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

- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [A Survey of Optimization-based Task and Motion Planning: From Classical To Learning Approaches](https://mlsanity.com/paper/2404.02817/) (2024)
- [Machine Learning for Large-Scale Optimization in 6G Wireless Networks](https://mlsanity.com/paper/2301.03377/) (2023)
- [An Improved Reinforcement Learning Algorithm for Learning to Branch](https://mlsanity.com/paper/2201.06213/) (2022)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [Yordle: An Efficient Imitation Learning for Branch and Bound](https://mlsanity.com/paper/2202.01896/) (2022)
- [Lifelong Learning for Neural powered Mixed Integer Programming](https://mlsanity.com/paper/2208.12226/) (2022)
- [Soft Tuy-Completeness for Robust Projection Selection in Cone-Beam CT](https://mlsanity.com/paper/2605.24023/) (2026)
- [Influence branching for learning to solve mixed-integer programs online](https://mlsanity.com/paper/2510.04273/) (2025)

## Abstract (arXiv)

In this paper, we surveyed the existing literature studying different approaches and algorithms for the four critical components in the general branch and bound (B&B) algorithm, namely, branching variable selection, node selection, node pruning, and cutting-plane selection. However, the complexity of the B&B algorithm always grows exponentially with respect to the increase of the decision variable dimensions. In order to improve the speed of B&B algorithms, learning techniques have been introduced in this algorithm recently. We further surveyed how machine learning can be used to improve the four critical components in B&B algorithms. In general, a supervised learning method helps to generate a policy that mimics an expert but significantly improves the speed. An unsupervised learning method helps choose different methods based on the features. In addition, models trained with reinforcement learning can beat the expert policy, given enough training and a supervised initialization. Detailed comparisons between different algorithms have been summarized in our survey. Finally, we discussed some future research directions to accelerate and improve the algorithms further in the literature.