Research map / Graph learning / Graph algorithms and clustering

Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks

AAAI 2025 · Graph learning › Graph algorithms and clustering · approach: Neural combinatorial optimization on graphs · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Learn2Aggregate trains a GNN over the variable-constraint graph to classify which constraints to aggregate for Chvátal-Gomory cut generation, shrinking the CG-MIP separator while keeping integrality gap closure.

Problem

Exact Chvátal-Gomory cut separation requires solving an auxiliary MILP (CG-MIP) whose size grows with the number of constraints, making it too slow for large MILPs.

Approach

Use a supervised GNN on the variable-constraint graph to classify constraints that appear in non-dominated (tight) CG cuts, then run CG-MIP only on the reduced constraint set, with labels from tight cuts and a hybrid of engineered features and GNN embeddings.

Key results

• On average, the reduced separator removes about 75% of constraints and yields mean IGC ratios of 1.02, 1.23, and 1.93 for small, medium, and large instances, with time ratios of 0.43, 0.36, and 0.59.
• Set cover large and stable set large reach IGC ratios of 2.99 and 2.59 relative to full CG-MIP.
• A GNN trained on small instances generalizes to medium and large instances, e.g. facility location large IGC ratio 1.92 at time ratio 0.51.

Measured effects reported in the paper

Surprising findings

• Learning from only tight (non-dominated) cuts gives slightly better performance than learning from all cuts.

Limitations

• Evaluated in a pure cutting plane method, not integrated within a MILP solver, where time constraints are stricter.
• Classification approach may be outperformed by regression of aggregation upper bounds, which the authors found harder to train.
• Some instance families show lower accuracy or recall (e.g., set cover large recall 40.79%).

Experimental setup

Datasets: stable set instances (MIPLearn) p-median instances (MIPLearn) set cover instances (Ecole) binary packing instances capacitated facility location instances (Ecole)

Benchmarks: stable set p-median set cover binary packing capacitated facility location

Metrics: integrality gap closure (IGC) cut generation time size reduction win/loss counts shifted geometric mean

Baselines: full CG-MIP separator GMI cuts

Builds on: CG-MIP GMI cuts graph convolutional neural network for MILP (Gasse et al.) projected Chvátal-Gomory cuts

Closest papers by meaning

• Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.90)
• ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.88)
• Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.87)
• Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming (AAAI 2024 · similarity 0.86)
• Predicting Lagrangian Multipliers for Mixed Integer Linear Programs (ICML 2024 · similarity 0.86)
• Learning to Remove Cuts in Integer Linear Programming (ICML 2024 · similarity 0.86)