Machine Learning for Cutting Planes in Integer Programming: A Survey
It addresses the challenge of cut selection in MILP for optimization practitioners, but is incremental as it reviews existing work rather than proposing new methods.
This survey examines machine learning techniques for selecting cutting planes in mixed-integer linear programming to accelerate solution times, summarizing recent advances and empirical results in the literature.
We survey recent work on machine learning (ML) techniques for selecting cutting planes (or cuts) in mixed-integer linear programming (MILP). Despite the availability of various classes of cuts, the task of choosing a set of cuts to add to the linear programming (LP) relaxation at a given node of the branch-and-bound (B&B) tree has defied both formal and heuristic solutions to date. ML offers a promising approach for improving the cut selection process by using data to identify promising cuts that accelerate the solution of MILP instances. This paper presents an overview of the topic, highlighting recent advances in the literature, common approaches to data collection, evaluation, and ML model architectures. We analyze the empirical results in the literature in an attempt to quantify the progress that has been made and conclude by suggesting avenues for future research.