Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
This is an incremental survey that synthesizes existing research on optimizing branch and bound methods for practitioners in optimization and operations research.
This survey examines techniques for improving branch and bound algorithms in mixed integer linear programming, focusing on four critical components and the integration of machine learning to enhance speed, such as supervised learning mimicking experts and reinforcement learning outperforming them.
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.