Machine Learning for Cutting Planes in Integer Programming: A Survey

Abstract

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.

arXiv commentAccepted in IJCAI 2023 Survey Track

References in corpus (7)

• Attention-based Deep Multiple Instance Learning
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Reinforcement Learning for Integer Programming: Learning to Cut
• Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning
• Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts