Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming
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.
Learns a hybrid graph neural network (HYGRO) with evolutionary strategies that outputs a per-node threshold on consecutive stagnation cut rounds, controlling when SCIP stops cut generation.
Problem
When to stop cut generation and addition rounds in the branch-and-cut process of MILP solvers; hard-coded heuristic stopping rules ignore instance-specific patterns and hurt solving efficiency.
Approach
Reformulates per-iteration stop/continue decisions as learning a single node-level threshold on consecutive stagnation rounds (a small action space), and encodes the MILP with a hybrid model combining a bipartite graph convolution over dynamic constraint/variable/coefficient features with static instance features, trained by evolutionary strategies inside SCIP.
Key results
- On classical datasets HYGRO improves average solving time by about 22% over SCIP's default stopping strategy, with up to 31% on a specific dataset (Knapsack).
- On harder datasets HYGRO improves about 8-10% on average over default, peaking at 17% (Corlat).
- The indirect threshold formulation reduces model call count from about 116 to 1 on MIK versus direct per-iteration decisions, and improves solving time by 49% on MIK (21.5s to 10.9s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use HYGRO instead of SCIP's default stopping strategy | SCIP · Set Covering | solving time: 5.15(3.5) -> 3.91(3.0) | Helped |
| use HYGRO instead of SCIP's default stopping strategy | SCIP · Max Independent Set | solving time: 6.46(4.1) -> 5.78(3.8) | Helped |
| use HYGRO instead of SCIP's default stopping strategy | SCIP · Knapsack | solving time: 13.34(15.6) -> 9.12(12.6) | Mixed |
| use HYGRO instead of SCIP's default stopping strategy | SCIP · Corlat | solving time: 45.6(85.8) -> 37.7(77.5) | Mixed |
| use HYGRO instead of SCIP's default stopping strategy | SCIP · MIK | solving time: 10.2(14.3) -> 9.5(14.0) | Helped |
| use HYGRO instead of SCIP's default stopping strategy | SCIP · Anonymous | solving time: 245(96) -> 241(102) | Hurt |
| replace direct stop/continue decisions with an indirect learned stagnation threshold (ablation) | HYGRO on MIK · MIK | solving time: 21.5(15.3) -> 10.9(5.4) | Helped |
| replace direct stop/continue decisions with an indirect learned stagnation threshold (ablation) | HYGRO on MIK · MIK | Extra Time: 7.0(5.8) -> 1.9(2.6) | Helped |
| replace direct stop/continue decisions with an indirect learned stagnation threshold (ablation) | HYGRO on MIK · MIK | PDI: 403.0(458.4) -> 239.2(262.7) | Helped |
| replace direct stop/continue decisions with an indirect learned stagnation threshold (ablation) | HYGRO on MIS · MIS | solving time: 9.2(4.6) -> 7.1(4.7) | Helped |
| replace direct stop/continue decisions with an indirect learned stagnation threshold (ablation) | HYGRO on MIS · MIS | Extra Time: 2.9(2.4) -> 1.1(2.2) | Helped |
| replace direct stop/continue decisions with an indirect learned stagnation threshold (ablation) | HYGRO on MIS · MIS | PDI: 55.4(36.2) -> 45.0(34.0) | Helped |
Surprising findings
- Always-on cut generation and fixed cut-number/round limits often perform worse than SCIP's default, and in some datasets even worse than No Cuts.
- On the Anonymous dataset, HYGRO's improvement is marginal (1.6% to 3.1%), and the No Cuts baseline slightly beats HYGRO on time.
Limitations
- Improvements on the Anonymous dataset are small, and HYGRO is slightly beaten by some baselines on a few tests.
- Training uses evolutionary strategies with many solver runs, and the training cost is not reported.
- Decisions are made mainly at the root node; multi-node decisions (HYGRO I) are only tested up to depth 2.
Experimental setup
Datasets: Multiple Knapsack Maximum Independent Set Set Covering Corlat MIK Anonymous
Benchmarks: Multiple Knapsack Maximum Independent Set Set Covering Corlat MIK Anonymous larger Set Covering and MIS instances (generalization)
Metrics: solving time primal-dual integral (PDI) average improvement over SCIP default
Baselines: SCIP default (stagnation round detection) No Cuts Always Fixed Cut Number Fixed Cut Rounds Immediate Random I Random II
Builds on: SCIP stagnation round detection graph convolution for MILP Principal Neighbourhood Aggregation
Closest papers by meaning
- Learning to Remove Cuts in Integer Linear Programming (ICML 2024 · similarity 0.90)
- Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.87)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.87)
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates (AAAI 2024 · similarity 0.87)
- Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks (AAAI 2025 · similarity 0.86)
- MILP-StuDio: MILP Instance Generation via Block Structure Decomposition (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.