mlsanityData to 7 Oct 2026

Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond

arXiv 2106.04033 ↗First posted 8 Jun 2021cs.AI cs.LGcited by 33

Not on the map. Why?

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.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). Builds on 15 of its 49 references that are in the map. First posted on arXiv 8 Jun 2021.

Builds on

15 of 49 references.

References · 15

  1. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  2. 2019Reinforcement Learning for Integer Programming: Learning to Cutcited by 108
  3. 2019MIPaaL: Mixed Integer Program as a Layercited by 93
  4. 2014ParamILS: An Automatic Algorithm Configuration Frameworkcited by 88
  5. 2018Learning to Branchcited by 78
  6. 2015A PAC Approach to Application-Specific Algorithm Selectioncited by 57
  7. 2021Learning to Select Cuts for Efficient Mixed-Integer Programmingcited by 48
  8. 2019How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm designcited by 27
  9. 2013DASH: Dynamic Approach for Switching Heuristicscited by 13
  10. 2018LeapsAndBounds: A Method for Approximately Optimal Algorithm Configurationcited by 13
  11. 2020Refined bounds for algorithm configuration: The knife-edge of dual class approximabilitycited by 12
  12. 2019Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configurationcited by 9
3 more
  1. 2019Learning to Optimize Computational Resources: Frugal Training with Generalization Guaranteescited by 5
  2. 2020Data-driven Algorithm Designcited by 5
  3. 2018Learning Robust Search Strategies Using a Bandit-Based Approachcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 9; 2023: 4; 2024: 11; 2025: 4; 2026: 4.

33 papers.

Sort:

By area:

  1. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 58
  2. 2023Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Modelcited by 44
  3. 2022Adaptive Cut Selection in Mixed-Integer Linear Programmingcited by 25
  4. 2022Generalization Bounds for Data-Driven Numerical Linear Algebracited by 24
  5. 2024Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programmingcited by 24
  6. 2022Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cutscited by 19
  7. 2023Machine Learning for Cutting Planes in Integer Programming: A Surveycited by 19
  8. 2022Provably tuning the ElasticNet across instancescited by 14
  9. 2021Improved Sample Complexity Bounds for Branch-and-Cutcited by 13
  10. 2024Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programmingcited by 12
  11. 2024Algorithm Configuration for Structured Pfaffian Settingscited by 10
  12. 2022Accelerating ERM for data-driven algorithm design using output-sensitive techniquescited by 8
21 more
  1. 2024Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programmingcited by 8
  2. 2024LLMs for Cold-Start Cutting Plane Separator Configurationcited by 8
  3. 2024Machine Learning Insides OptVerse AI Solver: Design Principles and Applicationscited by 7
  4. 2024Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cutcited by 7
  5. 2022Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Searchcited by 6
  6. 2022Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximationcited by 5
  7. 2024Learning Cut Generating Functions for Integer Programmingcited by 5
  8. 2022Cutting Plane Selection with Analytic Centers and Multiregressioncited by 4
  9. 2024Learning to Remove Cuts in Integer Linear Programmingcited by 4
  10. 2024Learning accurate and interpretable tree-based modelscited by 3
  11. 2023Solving a Class of Cut-Generating Linear Programs via Machine Learningcited by 2
  12. 2025Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programmingcited by 2
  13. 2025Learning Admissible Heuristics for A*: Theory and Practicecited by 2
  14. 2026Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Functioncited by 2
  15. 2026Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programmingcited by 2
  16. 2025How hard is learning to cut? Trade-offs and sample complexitycited by 1
  17. 2026Learning-augmented smooth integer programs with PAC-learnable oraclescited by 1
  18. 2023Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programscited by 0
  19. 2024AlphaZeroES: Direct score maximization outperforms planning loss minimizationcited by 0
  20. 2025Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programmingcited by 0
  21. 2026Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programmingcited by 0