Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912021057896448 |
|---|---|
| author | Deza, Arnaud Khalil, Elias B. Fan, Zhenan Zhou, Zirui Zhang, Yong |
| author_facet | Deza, Arnaud Khalil, Elias B. Fan, Zhenan Zhou, Zirui Zhang, Yong |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06559 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks Deza, Arnaud Khalil, Elias B. Fan, Zhenan Zhou, Zirui Zhang, Yong Machine Learning Optimization and Control 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. |
| title | Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2409.06559 |