Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks
This work addresses optimization challenges in MILP for operations research and computational mathematics, representing a strong specific gain with a novel method for a known bottleneck.
The paper tackled the problem of generating Chvátal-Gomory cuts in mixed integer linear programming by developing a machine learning framework that trains a graph neural network to classify useful constraints, resulting in closing roughly twice as much of the integrality gap as the standard method while running 40% faster on large test sets.
We present $\textit{Learn2Aggregate}$, a machine learning (ML) framework for optimizing the generation of Chvátal-Gomory (CG) cuts in mixed integer linear programming (MILP). The framework trains a graph neural network to classify useful constraints for aggregation in CG cut generation. The ML-driven CG separator selectively focuses on a small set of impactful constraints, improving runtimes without compromising the strength of the generated cuts. Key to our approach is the formulation of a constraint classification task which favours sparse aggregation of constraints, consistent with empirical findings. This, in conjunction with a careful constraint labeling scheme and a hybrid of deep learning and feature engineering, results in enhanced CG cut generation across five diverse MILP benchmarks. On the largest test sets, our method closes roughly $\textit{twice}$ as much of the integrality gap as the standard CG method while running 40$% faster. This performance improvement is due to our method eliminating 75% of the constraints prior to aggregation.