# Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 4 Feb 2024.

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

- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets](https://mlsanity.com/paper/1903.05662/) (2019)
- [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)
- [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)
- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [Adaptive Cut Selection in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2202.10962/) (2022)
- [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)
- [Improved Sample Complexity Bounds for Branch-and-Cut](https://mlsanity.com/paper/2111.11207/) (2021)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)
- [Generalization in portfolio-based algorithm selection](https://mlsanity.com/paper/2012.13315/) (2020)

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

- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025)
- [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025)
- [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)
- [CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees](https://mlsanity.com/paper/2607.14545/) (2026)

## Abstract (arXiv)

Data-driven algorithm design is a paradigm that uses statistical and machine learning techniques to select from a class of algorithms for a computational problem an algorithm that has the best expected performance with respect to some (unknown) distribution on the instances of the problem. We build upon recent work in this line of research by considering the setup where, instead of selecting a single algorithm that has the best performance, we allow the possibility of selecting an algorithm based on the instance to be solved, using neural networks. In particular, given a representative sample of instances, we learn a neural network that maps an instance of the problem to the most appropriate algorithm for that instance. We formalize this idea and derive rigorous sample complexity bounds for this learning problem, in the spirit of recent work in data-driven algorithm design. We then apply this approach to the problem of making good decisions in the branch-and-cut framework for mixed-integer optimization (e.g., which cut to add?). In other words, the neural network will take as input a mixed-integer optimization instance and output a decision that will result in a small branch-and-cut tree for that instance. Our computational results provide evidence that our particular way of using neural networks for cut selection can make a significant impact in reducing branch-and-cut tree sizes, compared to previous data-driven approaches.