Learning to Cut Generation in Branch-and-Cut Algorithms for Combinatorial Optimization

Branch-and-cut is one of the most successful methods to exactly solve combinatorial optimization problems. A key decision problem in branch-and-cut is cut generation —the problem of deciding whether to generate cuts or to branch at each node of the search tree. This decision significantly impacts performance: generating efficient cuts can remove a substantial portion of the infeasible region and reduce tree size. However, in many cases, generating cuts slows runtime as separation routines could be time-consuming, and the violated cuts found by these routines could be inefficient. Hence, a smart strategy for generating cuts is crucial for the efficiency of branch-and-cut algorithms. There are two main types of cuts: generic cuts derived from the integrality of variables and combinatorial cuts based on the facial structure of the convex hull of feasible solutions. Combinatorial cuts are particularly determinant in branch-and-cut for many NP-hard combinatorial optimization problems, e.g., the Traveling Salesman Problem and the Max-Cut problem. In this article, we propose a framework combining supervised learning and deep reinforcement learning to learn strategies for generating combinatorial cuts in branch-and-cut. Our framework contains two components: a cut detector to predict the cut existence and a cut evaluator to choose between generating cuts and branching. We conduct experiments on two well-known combinatorial cut classes: subtour elimination constraints for the Traveling Salesman problem and cycle inequalities for the Max-Cut problem. Our results show that the proposed framework outperforms the commonly used strategies for cut generation, even on instances larger than those used for training.