# Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond arXiv: https://arxiv.org/abs/2106.04033 ยท HTML: https://mlsanity.com/paper/2106.04033/ ## Key facts - Cited by 33 papers in the map (data through 14 Oct 2026). - Builds on 15 of its 49 references that are in the map. - First posted on arXiv 8 Jun 2021. ## Builds on (most cited first, 15 of 15) - [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) - [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (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) - [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019) - [DASH: Dynamic Approach for Switching Heuristics](https://mlsanity.com/paper/1307.4689/) (2013) - [LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration](https://mlsanity.com/paper/1807.00755/) (2018) - [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) - [Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees](https://mlsanity.com/paper/1905.10819/) (2019) - [Data-driven Algorithm Design](https://mlsanity.com/paper/2011.07177/) (2020) - [Learning Robust Search Strategies Using a Bandit-Based Approach](https://mlsanity.com/paper/1805.03876/) (2018) ## Built on by (most cited first, 30 of 33) - [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022) - [Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model](https://mlsanity.com/paper/2302.00244/) (2023) - [Adaptive Cut Selection in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2202.10962/) (2022) - [Generalization Bounds for Data-Driven Numerical Linear Algebra](https://mlsanity.com/paper/2206.07886/) (2022) - [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024) - [Machine Learning for Cutting Planes in Integer Programming: A Survey](https://mlsanity.com/paper/2302.09166/) (2023) - [Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts](https://mlsanity.com/paper/2204.07312/) (2022) - [Provably tuning the ElasticNet across instances](https://mlsanity.com/paper/2207.10199/) (2022) - [Improved Sample Complexity Bounds for Branch-and-Cut](https://mlsanity.com/paper/2111.11207/) (2021) - [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) - [Accelerating ERM for data-driven algorithm design using output-sensitive techniques](https://mlsanity.com/paper/2204.03569/) (2022) - [Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming](https://mlsanity.com/paper/2401.17527/) (2024) - [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) - [Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search](https://mlsanity.com/paper/2205.09963/) (2022) - [Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation](https://mlsanity.com/paper/2209.08281/) (2022) - [Learning Cut Generating Functions for Integer Programming](https://mlsanity.com/paper/2405.13992/) (2024) - [Cutting Plane Selection with Analytic Centers and Multiregression](https://mlsanity.com/paper/2212.07231/) (2022) - [Learning to Remove Cuts in Integer Linear Programming](https://mlsanity.com/paper/2406.18781/) (2024) - [Learning accurate and interpretable tree-based models](https://mlsanity.com/paper/2405.15911/) (2024) - [Solving a Class of Cut-Generating Linear Programs via Machine Learning](https://mlsanity.com/paper/2310.19920/) (2023) - [Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming](https://mlsanity.com/paper/2503.15847/) (2025) - [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025) - [Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2602.02406/) (2026) - [Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming](https://mlsanity.com/paper/2605.19052/) (2026) - [How hard is learning to cut? Trade-offs and sample complexity](https://mlsanity.com/paper/2506.00252/) (2025) - [Learning-augmented smooth integer programs with PAC-learnable oracles](https://mlsanity.com/paper/2602.02505/) (2026) - [Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs](https://mlsanity.com/paper/2310.14659/) (2023) ## Abstract (arXiv) Cutting-plane methods have enabled remarkable successes in integer programming over the last few decades. State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm used to find optimal solutions. In this paper we prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution at hand using samples. We first bound the sample complexity of learning cutting planes from the canonical family of Chv'atal-Gomory cuts. Our bounds handle any number of waves of any number of cuts and are fine tuned to the magnitudes of the constraint coefficients. Next, we prove sample complexity bounds for more sophisticated cut selection policies that use a combination of scoring rules to choose from a family of cuts. Finally, beyond the realm of cutting planes for integer programming, we develop a general abstraction of tree search that captures key components such as node selection and variable selection. For this abstraction, we bound the sample complexity of learning a good policy for building the search tree.