# Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 70 references that are in the map.
- First posted on arXiv 15 Apr 2022.

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

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [ParamILS: An Automatic Algorithm Configuration Framework](https://mlsanity.com/paper/1401.3492/) (2014)
- [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)
- [Learning to Select Cuts for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2105.13645/) (2021)
- [Interpretable Classification Models for Recidivism Prediction](https://mlsanity.com/paper/1503.07810/) (2015)
- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)
- [Adaptive Cut Selection in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2202.10962/) (2022)
- [Data-Driven Clustering via Parameterized Lloyd's Families](https://mlsanity.com/paper/1809.06987/) (2018)
- [DASH: Dynamic Approach for Switching Heuristics](https://mlsanity.com/paper/1307.4689/) (2013)
- [Question Answering via Integer Programming over Semi-Structured Knowledge](https://mlsanity.com/paper/1604.06076/) (2016)
- [LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration](https://mlsanity.com/paper/1807.00755/) (2018)
- [Improved Sample Complexity Bounds for Branch-and-Cut](https://mlsanity.com/paper/2111.11207/) (2021)
- [Learning Complexity of Simulated Annealing](https://mlsanity.com/paper/2003.02981/) (2020)
- [Refined bounds for algorithm configuration: The knife-edge of dual class approximability](https://mlsanity.com/paper/2006.11827/) (2020)
- [Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration](https://mlsanity.com/paper/1902.05454/) (2019)
- [Supervising Unsupervised Learning](https://mlsanity.com/paper/1709.05262/) (2017)
- [Learning Robust Search Strategies Using a Bandit-Based Approach](https://mlsanity.com/paper/1805.03876/) (2018)

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

- [Machine Learning for Cutting Planes in Integer Programming: A Survey](https://mlsanity.com/paper/2302.09166/) (2023)
- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2404.12638/) (2024)
- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [LLMs for Cold-Start Cutting Plane Separator Configuration](https://mlsanity.com/paper/2412.12038/) (2024)
- [Machine Learning Insides OptVerse AI Solver: Design Principles and Applications](https://mlsanity.com/paper/2401.05960/) (2024)
- [Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut](https://mlsanity.com/paper/2402.02328/) (2024)
- [Learning Cut Generating Functions for Integer Programming](https://mlsanity.com/paper/2405.13992/) (2024)
- [Learning to Remove Cuts in Integer Linear Programming](https://mlsanity.com/paper/2406.18781/) (2024)
- [Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming](https://mlsanity.com/paper/2503.15847/) (2025)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming](https://mlsanity.com/paper/2605.19052/) (2026)
- [Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branching](https://mlsanity.com/paper/2305.12352/) (2023)
- [AlphaZeroES: Direct score maximization outperforms planning loss minimization](https://mlsanity.com/paper/2406.08687/) (2024)
- [Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming](https://mlsanity.com/paper/2505.11636/) (2025)
- [Minimum-Cost Network Flow with Dual Predictions](https://mlsanity.com/paper/2601.20203/) (2026)
- [Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming](https://mlsanity.com/paper/2606.08638/) (2026)
- [Tight Bounds for Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2608.17343/) (2026)

## Abstract (arXiv)

The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. These solvers are the foremost method for solving discrete optimization problems and thus have a vast array of applications in machine learning, operations research, and many other fields. Choosing cutting planes effectively is a major research topic in the theory and practice of integer programming. We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to the input integer program. Our main application of this analysis is to derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during branch-and-cut. These guarantees apply to infinite families of cutting planes, such as the family of Gomory mixed integer cuts, which are responsible for the main breakthrough speedups of integer programming solvers. We exploit geometric and combinatorial structure of branch-and-cut in our analysis, which provides a key missing piece for the recent generalization theory of branch-and-cut.