Learn2Aggregate: Supervised Generation of Chv\'atal-Gomory Cuts Using Graph Neural Networks
<|reference_start|>Learn2Aggregate: Supervised Generation of Chv\'atal-Gomory Cuts Using Graph Neural Networks: We present $\textit{Learn2Aggregate}$, a machine learning (ML) framework for optimizing the generation of Chv\'atal-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.<|reference_end|>
@article{deza2024learn2aggregate:,
    title={Learn2Aggregate: Supervised Generation of Chv\'atal-Gomory Cuts Using
  Graph Neural Networks},
    author={Arnaud Deza, Elias B. Khalil, Zhenan Fan, Zirui Zhou, Yong Zhang},
    journal={arXiv preprint arXiv:2409.06559},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.06559},
    primaryClass={cs.LG math.OC}
}