# Learning Cut Generating Functions for Integer Programming

arXiv: https://arxiv.org/abs/2405.13992 · HTML: https://mlsanity.com/paper/2405.13992/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 56 references that are in the map.
- First posted on arXiv 22 May 2024.

## Builds on (most cited first, 19 of 19)

- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Generalized Linear Rule Models](https://mlsanity.com/paper/1906.01761/) (2019)
- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts](https://mlsanity.com/paper/2204.07312/) (2022)
- [Integer Programming for Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/2102.03129/) (2021)
- [Improved Sample Complexity Bounds for Branch-and-Cut](https://mlsanity.com/paper/2111.11207/) (2021)
- [The continuous categorical: a novel simplex-valued exponential family](https://mlsanity.com/paper/2002.08563/) (2020)
- [Lifting properties of maximal lattice-free polyhedra](https://mlsanity.com/paper/1404.7421/) (2014)
- [Operations that preserve the covering property of the lifting region](https://mlsanity.com/paper/1410.1571/) (2014)
- [Unique lifting of integer variables in minimal inequalities](https://mlsanity.com/paper/1701.06628/) (2017)
- [Can cut generating functions be good and efficient?](https://mlsanity.com/paper/1803.00667/) (2018)
- [Combination Chemotherapy Optimization with Discrete Dosing](https://mlsanity.com/paper/2111.02000/) (2021)

## Built on by (most cited first, 5 of 5)

- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)
- [Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming](https://mlsanity.com/paper/2505.11636/) (2025)

## Abstract (arXiv)

The branch-and-cut algorithm is the method of choice to solve large scale integer programming problems in practice. A key ingredient of branch-and-cut is the use of cutting planes which are derived constraints that reduce the search space for an optimal solution. Selecting effective cutting planes to produce small branch-and-cut trees is a critical challenge in the branch-and-cut algorithm. Recent advances have employed a data-driven approach to select optimal cutting planes from a parameterized family, aimed at reducing the branch-and-bound tree size (in expectation) for a given distribution of integer programming instances. We extend this idea to the selection of the best cut generating function (CGF), which is a tool in the integer programming literature for generating a wide variety of cutting planes that generalize the well-known Gomory Mixed-Integer (GMI) cutting planes. We provide rigorous sample complexity bounds for the selection of an effective CGF from certain parameterized families that provably performs well for any specified distribution on the problem instances. Our empirical results show that the selected CGF can outperform the GMI cuts for certain distributions. Additionally, we explore the sample complexity of using neural networks for instance-dependent CGF selection.