Learning to Remove Cuts in Integer Linear Programming
This addresses the computational efficiency problem for practitioners solving integer linear programs, representing an incremental but practically important advance in optimization algorithms.
The paper tackles the problem of improving cutting plane methods for integer linear programming by introducing a novel approach that learns to remove previously added cuts, rather than only adding new ones. The result shows this cut removal policy leads to significant improvements over both human-designed and machine learning-guided cut addition methods in fundamental combinatorial optimization settings.
Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional optimal solution while not affecting the optimal integer solution. In this work, we explore a novel approach within cutting plane methods: instead of only adding new cuts, we also consider the removal of previous cuts introduced at any of the preceding iterations of the method under a learnable parametric criteria. We demonstrate that in fundamental combinatorial optimization settings such cut removal policies can lead to significant improvements over both human-based and machine learning-guided cut addition policies even when implemented with simple models.