面向混合整数线性规划问题的智能分支定界算法综述

Mixed integer linear programming problems are spread across various fields in the real world. Solving mixed integer linear programming problems is an NP-hard problem. Current advanced solvers generally use the branch and bound method as the core framework for solving mixed integer linear programming problems. But the inherent exponential nature of branch and bound means that one wrong decision during its execution can double the size of the search tree and fail to improve the search process. Such a complex and data-rich environment, combined with a lack of formal understanding, makes it possible to leverage machine learning techniques to improve branch and bound algorithms. Therefore, combining data-driven machine learning methods with branch and bound algorithms to improve their decision-making processes has received increasing attention. In this article, we first introduce the branch and bound algorithm and analyze the possible decision-making process therein. Afterwards, the research work on integrating machine learning methods into branch and bound algorithms in recent years is mainly analyzed from two aspects: deep learning methods based on behavioral cloning that imitate existing expert strategies and reinforcement learning methods based on the idea of discovering new strategies. Finally, we discuss possible future directions and challenges in combining machine learning with branch and bound algorithms.