Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Cut Generating Functions for Integer 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 the best cut generating function (1-row and k-row families extending GMI) for branch-and-cut via data-driven selection with pseudo-dimension sample complexity bounds, plus instance-dependent neural selection.
Problem
Selecting cutting planes from a parameterized family of cut generating functions that minimize branch-and-cut tree size in expectation over an instance distribution, with sample complexity guarantees.
Approach
Extends data-driven cut selection from CG/GMI cuts to general cut generating functions: a 1-row family (GMI-based, parameterized by two slopes) and a k-row extreme-function family, proves pseudo-dimension bounds via piecewise-structure arguments, and extends the bounds to neural networks mapping instances to CGF parameters.
Key results
- On Knapsack(20,1), the 1-row cut reduces average tree size from 158.88 (GMI) to 87.0.
- On Knapsack(16,2), the 2-row cut reaches 178.68 vs 399.86 for GMI.
- On Knapsack(30,3), the 5-row cut achieves 2817.55 vs 4963.91 for GMI, and all multi-row cuts beat the best 1-row cut.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace GMI with the learned 1-row cut | branch-and-cut · Knapsack(20,1) | average tree size: 158.88 -> 87.0 | Helped |
| replace GMI with the learned 1-row cut | branch-and-cut · Knapsack(30,1) | average tree size: 832.16 -> 58.84 | Helped |
| replace GMI with the learned 1-row cut | branch-and-cut · Knapsack(50,1) | average tree size: 3543.91 -> 277.01 | Helped |
| replace GMI with the 2-row cut | branch-and-cut · Knapsack(16,2) | average tree size: 399.86 -> 178.68 | Helped |
| replace GMI with the 5-row cut | branch-and-cut · Knapsack(30,3) | average tree size: 4963.91 -> 2817.55 | Helped |
| replace GMI with the 1-row cut | branch-and-cut · Packing(15,30) | average tree size: 389.67 -> 367.48 | Helped |
| replace GMI with the 5-row cut | branch-and-cut · Packing(20,40) | average tree size: 1200.55 -> 1113.82 | Helped |
| use the 5-row cut instead of the 1-row cut | branch-and-cut · Knapsack(30,3) | average tree size: 4311.04 -> 2817.55 | Helped |
| use the 2-row cut instead of the 1-row cut | branch-and-cut · Knapsack(30,3) | average tree size: 4311.04 -> 3430.37 | Helped |
| use the 10-row cut instead of the 1-row cut | branch-and-cut · Knapsack(30,3) | average tree size: 4311.04 -> 2822.37 | Helped |
| use the 2-row cut instead of the 1-row cut | branch-and-cut · Knapsack(16,2) | average tree size: 316.8 -> 178.68 | Helped |
| use the 5-row cut instead of the 1-row cut | branch-and-cut · Packing(15,30) | average tree size: 367.48 -> 401.87 | Hurt |
Surprising findings
- Per-instance best 1-row cut yields much smaller trees than any single fixed parameter, but on Packing(15,30) the test-set 1-row cut is worse than GMI (367.48 vs 389.67 is better, but 2-row, 5-row are worse than GMI in some cases).
Limitations
- Experiments only on synthetic Knapsack and Packing distributions
- Parameters chosen by grid search over a coarse grid; neural instance-dependent selection is theoretical only
- Row selection not studied; first non-integer rows used
Experimental setup
Datasets: Chvatal knapsack distribution packing distribution
Benchmarks: Knapsack(N,K) instances Packing(m,n) instances
Metrics: average branch-and-cut tree size
Baselines: GMI cut best 1-row cut
Builds on: Gomory mixed-integer cuts Balcan et al. data-driven cut selection Balcan et al. learning to branch/cut sample complexity Dey et al. cut generating functions
Closest papers by meaning
- Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut (NeurIPS 2024 · similarity 0.91)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.90)
- Learn2Aggregate: Supervised Generation of Chvatal-Gomory Cuts Using Graph Neural Networks (AAAI 2025 · similarity 0.90)
- Learning to Remove Cuts in Integer Linear Programming (ICML 2024 · similarity 0.89)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.88)
- Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming (AAAI 2024 · similarity 0.87)
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.