A survey for solving mixed integer programming via machine learning

Machine learning (ML) has been recently introduced to solving optimization problems, especially for combinatorial optimization (CO) tasks. In this paper, we survey the trend of leveraging ML to solve the mixed-integer programming problem (MIP). Theoretically, MIP is an NP-hard problem, and most CO problems can be formulated as MIP. Like other CO problems, the human-designed heuristic algorithms for MIP rely on good initial solutions and cost a lot of computational resources. Therefore, researchers consider applying machine learning methods to solve MIP since ML-enhanced approaches can provide the solution based on the typical patterns from the training data. Specifically, we first introduce the for-mulation and preliminaries of MIP and representative traditional solvers. Then, we show the integration of machine learning and MIP with detailed discussions on related learning-based methods, which can be further classified into exact and heuristic algorithms. Finally, we propose the outlook for learning-based MIP solvers, the direction toward more combinatorial optimization problems beyond MIP, and the mutual embrace of traditional solvers and ML components. We maintain a list of papers that utilize machine learning technologies to solve combinatorial optimization problems, which is available at https://github.com/Thinklab-SJTU/awesome-ml4co. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This paper surveys the trend of using machine learning to solve mixed-integer programming problems. Machine learning methods can provide solutions based on patterns from training data. The integration of machine learning and mixed-integer programming is discussed, including both exact and heuristic algorithms. The outlook for learning-based solvers, the expansion to other combinatorial optimization problems, and the embrace of traditional solvers and machine learning components are proposed. A list of papers utilizing machine learning technologies for combinatorial optimization problems is maintained.