Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning to Remove Cuts in 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.
Proposes cut removal in cutting plane methods for ILPs: add all Gomory cuts each iteration, then keep only k+1 cuts chosen by a learned MLP that imitates the look-ahead LP-bound score.
Problem
Cutting plane methods for integer linear programs add few cuts per iteration because the constraint set grows exponentially if many cuts are added; existing learned cut-addition policies never remove cuts.
Approach
Include the whole cutpool each iteration to get a stronger LP bound, then prune the accumulated cuts back to k+1 using a learned score (MLP over 14 hand-crafted cut features) that approximates the LP-bound drop from removing each cut, keeping the total number of constraints growing by one per iteration.
Key results
- On in-distribution synthetic families, cut removal outperforms all cut addition baselines on packing, bin packing, production planning and set cover; it does not beat expert/Neural Cut on max cut.
- Trained on 50-variable instances and tested on ~100-variable instances, the method matches or outperforms all cut addition methods in all benchmarks, with a larger margin on packing, bin packing and set cover.
- In an appendix SCIP experiment on neural network verification instances, B&C-Cut_Removal finds on average 35% better solutions than B&C-Cut_Addition across 26 instances (better on 88.46%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use learned cut removal instead of cut addition | Cutting plane methods · Packing, Bin Packing, Production Planning, and Set Cover | mean IGC | Helped |
| Use learned cut removal instead of cut addition | Cutting plane methods · Max Cut | mean IGC | Mixed |
| Use a cut-removal policy trained on smaller instances | Cutting plane methods · Larger Packing, Bin Packing, Production Planning, and Set Cover instances | mean IGC | Helped |
| Use a cut-removal policy trained on smaller instances | Cutting plane methods · Larger Max Cut instances | mean IGC | Mixed |
| Use cut removal instead of vanilla cut addition | SCIP branch-and-cut · Neural Network Verification instances | solution quality: 35% | Helped |
| Use cut removal instead of vanilla cut addition | SCIP branch-and-cut · Neural Network Verification instances | LP bound improvement | Helped |
Surprising findings
- On max cut, a random cut-selection policy performs nearly as well as the best policies in the first third of iterations, and cut removal does not beat the expert there.
Limitations
- Cut removal requires keeping the number of cuts growing by one per iteration, a constant-rate restriction the authors flag as a limitation.
- Max cut shows no advantage over expert and Neural Cut baselines; differences are small.
- Evaluation uses IGC per iteration rather than wall-clock time in the main text; the model uses only simple MLP with hand-crafted features and no joint cut structure.
Experimental setup
Datasets: synthetic packing synthetic bin packing synthetic max cut synthetic production planning synthetic set cover
Benchmarks: synthetic packing synthetic bin packing synthetic max cut synthetic production planning synthetic set cover Neural Network Verification instances (SCIP, appendix)
Metrics: mean integrality gap closure (IGC) vs iterations LP bound improvement wall-clock speedup (appendix)
Baselines: look-ahead policy Neural Cut Random Max Violation Max Normalized Violation Lexicographic Min Similar
Builds on: Gomory cuts look-ahead cut selection policy Neural Cut (imitation learning cut selection)
Closest papers by meaning
- Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming (AAAI 2024 · similarity 0.90)
- Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.89)
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates (AAAI 2024 · similarity 0.88)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.88)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.87)
- Faster Global Minimum Cut with Predictions (ICML 2025 · similarity 0.86)
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.