Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks

• URL: http://arxiv.org/abs/2409.06559v1
• Date: Tue, 10 Sep 2024 14:41:46 GMT
• Title: Learn2Aggregate: Supervised Generation of Chvátal-Gomory Cuts Using Graph Neural Networks
• Authors: Arnaud Deza, Elias B. Khalil, Zhenan Fan, Zirui Zhou, Yong Zhang,
• Abstract summary: We present a machine learning 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. Our method closes roughly $textittwice$ as much of the integrality gap as the standard CG method while running 40$% faster.
• Score: 24.126826148945586
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  We introduce Mixture-of-Graphs (MoG) to dynamically select tailored pruning solutions for each node. MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node. Experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNNs, demonstrate that MoG identifies subgraphs at higher sparsity levels.
  arXiv  Detail & Related papers  (2024-05-23T07:40:21Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [56.26113670151363]
  Graph condensation is a data-centric solution to replace the large graph with a small yet informative condensed graph. Existing GC methods suffer from intricate optimization processes, necessitating excessive computing resources. We propose a training-free GC framework termed Class-partitioned Graph Condensation (CGC) CGC achieves state-of-the-art performance with a more efficient condensation process.
  arXiv  Detail & Related papers  (2024-05-22T14:57:09Z)
• Solving a Class of Cut-Generating Linear Programs via Machine Learning [0.0]
  Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of mixed-integer programs. Running the dualPs at the nodes of the branch-and-bound tree is computationally cumbersome due to the number of node candidates and the lack of a priori knowledge on which nodes admit useful cutting planes. We propose a novel framework based on learning to approximate the optimal value of a machineP class that determines whether a cutting plane can be generated at a node of the branch-bound tree.
  arXiv  Detail & Related papers  (2023-10-30T18:31:52Z)
• CARL-G: Clustering-Accelerated Representation Learning on Graphs [18.763104937800215]
  We propose a novel clustering-based framework for graph representation learning that uses a loss inspired by Cluster Validation Indices (CVIs) CARL-G is adaptable to different clustering methods and CVIs, and we show that with the right choice of clustering method and CVI, CARL-G outperforms node classification baselines on 4/5 datasets with up to a 79x training speedup compared to the best-performing baseline.
  arXiv  Detail & Related papers  (2023-06-12T08:14:42Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  We generalize the bound propagation procedure to allow the addition of arbitrary cutting plane constraints. We find that MIP solvers can generate high-quality cutting planes for strengthening bound-propagation-based verifiers. Our method is the first verifier that can completely solve the oval20 benchmark and verify twice as many instances on the oval21 benchmark.
  arXiv  Detail & Related papers  (2022-08-11T10:31:28Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• A Deep Reinforcement Learning Framework For Column Generation [13.767526395378638]
  Column Generation (CG) is an iterative algorithm for solving linear programs with an extremely large number of variables (columns) We propose RLCG, the first Reinforcement Learning (RL) approach for CG. Unlike typical column selection rules which myopically select a column based on local information at each iteration, we treat CG as a sequential decision-making problem.
  arXiv  Detail & Related papers  (2022-06-03T03:58:54Z)
• MGAE: Masked Autoencoders for Self-Supervised Learning on Graphs [55.66953093401889]
  Masked graph autoencoder (MGAE) framework to perform effective learning on graph structure data. Taking insights from self-supervised learning, we randomly mask a large proportion of edges and try to reconstruct these missing edges during training.
  arXiv  Detail & Related papers  (2022-01-07T16:48:07Z)
• Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring [5.278929511653199]
  Column Generation (CG) is an effective method for solving large-scale optimization problems. We propose a Machine-Learning Pricing Heuristic that can generate many high-quality columns efficiently.
  arXiv  Detail & Related papers  (2021-12-08T03:58:25Z)
• Meta Clustering Learning for Large-scale Unsupervised Person Re-identification [124.54749810371986]
  We propose a "small data for big task" paradigm dubbed Meta Clustering Learning (MCL) MCL only pseudo-labels a subset of the entire unlabeled data via clustering to save computing for the first-phase training. Our method significantly saves computational cost while achieving a comparable or even better performance compared to prior works.
  arXiv  Detail & Related papers  (2021-11-19T04:10:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.