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

• DOI: 10.48550/arxiv.2111.06257
• Publication Date: 2021-01-01
• Authors: Lingying Huang; Xiaomeng Chen; Wei Huo; Jiazheng Wang; Fan Zhang; Bo Bai; Ling Shi
• Keywords: Initialization; Branch and bound; Pruning

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