Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
arXiv:2111.06257
Abstract
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.
arXiv commentPreprint submitted to Discrete Optimization
References in corpus (9)
- Exact Combinatorial Optimization with Graph Convolutional Neural Networks
- Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem
- Learning to Search Better Than Your Teacher
- Reinforcement Learning for Integer Programming: Learning to Cut
- Learning to Branch
- Hybrid Models for Learning to Branch
- Solving Mixed Integer Programs Using Neural Networks
- A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP
- Cuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman Problem