Interpretable method improves mixed-integer linear programming speed by 6 percent
Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
Machine Learning
Summary
Mixed-integer linear programs are complex math problems used for scheduling, planning, and optimization, and they are solved by cutting out impossible solutions in steps. The authors introduce a new approach that learns to select these cuts more effectively using genetic programming, which creates understandable decision rules instead of black-box neural networks. Their method adapts how many cuts to use at each step and works well even when tested on much harder problems than it was trained on. This leads to faster solving times compared to both traditional methods and recent learning-based methods.
What this means in practice
- •For operations research teams: Speed up solving complex scheduling and logistics problems by using an interpretable cut selection method that adapts to problem hardness.
- •For supply chain planners: Improve optimization runtimes in supply chain design tools by integrating a learning-based cut selection heuristic to reduce computation time.
Authors
Gwen maudet, Mathis Da Cunha, Grégoire Danoy
Abstract
Cutting planes (cuts) remove fractional solutions from mixed-integer linear programs (MILPs) without excluding any feasible integer solutions, making them a key ingredient in modern MILP solvers. Current state-of-the-art solvers rely on fine-tuned handcrafted cut strategies, which, despite their effectiveness, remain inherently static and can be suboptimal. More recently, learning-based approaches have been proposed to design adaptive cut strategies; however, most of these methods are based on neural networks, offering limited interpretability and providing no guarantees of convergence. In this paper, we propose \emph{Genetic Programming and Statistics-based Cut Selection} (GPSCS), the first learning-based framework that explicitly generalizes handcrafted cut selection heuristics into a fully interpretable policy. First, a genetic programming model evolves a symbolic scoring function that ranks candidate cuts using features derived from the cuts and the solving context. Second, a lightweight statistics-based mechanism adaptively determines the number of top-ranked cuts to add at each separation round by detecting significant score dropouts. We evaluate GPSCS within the SCIP solver on seven classes of synthetic and real-world benchmark instances, with a strong emphasis on generalization: evaluation instances are on average 41 times harder than those used for training. Experimental results show that GPSCS improves average solving time by $6\%$ compared to SCIP's default cut selection strategy and achieves a two-fold speedup over both a recent neural-network-based approach and a no-cut baseline, demonstrating strong robustness and generalization across heterogeneous MILP families.