Research map / Learning theory and algorithms / Combinatorial and search optimization
Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Learns neural-network mappings from ILP instances to algorithm parameters, gives pseudo-dimension sample complexity bounds for linear-threshold and ReLU networks, and applies them to CG cut-multiplier selection in branch-and-cut trained with TD3 RL.
Problem
Data-driven algorithm design typically selects a single parameter setting for all instances; the paper instead learns an instance-to-parameter neural mapping and needs sample complexity guarantees, applied to cut selection in branch-and-cut.
Approach
Reduces instance-dependent algorithm selection to learning neural-network parameters, bounds the pseudo-dimension of the resulting hypothesis classes for sgn/Sigmoid and ReLU/CReLU networks, and instantiates this for CG cut multipliers, trained with RL (TD3) to minimize branch-and-cut tree size.
Key results
- The RL-trained ReLU network for CG cut multipliers outperforms the SCIP-style weighted efficacy/parallelism cut selection baseline on tree size over 1,000 test instances.
- Computing cuts with the trained network takes 0.010 s on GPU and 0.055 s on CPU versus 2.031 s for solving the required LPs with Gurobi (100 runs over 1,000 instances).
- Pseudo-dimension bounds are O(W log(U gamma Gamma (lambda+1))) for linear-threshold networks and O(LW log(U+l) + W log(gamma Gamma (lambda+1))) for ReLU networks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use neural-network inference on GPU instead of solving required LPs | CG cut selection · Test set of 1,000 instances, 100 runs | time (seconds): 2.031 -> 0.010 | Helped |
| Use neural-network inference on CPU instead of solving required LPs | CG cut selection · Test set of 1,000 instances, 100 runs | time (seconds): 2.031 -> 0.055 | Helped |
| Select CG cuts using an RL-trained neural network instead of weighted efficacy and parallelism scores | Branch-and-bound tree size · 1,000 novel test instances from the Chvátal distribution | average tree size | Helped |
| Generate CG cut parameters with a linear-threshold neural network instead of the RL approach (ablation) | Branch-and-bound tree size · 1,000 novel test instances from the Chvátal distribution | average tree size | Mixed |
Surprising findings
- The authors note that allowing general mappings from instances to cutting planes can yield infinite sample complexity, so overly rich mapping classes may be unlearnable.
Limitations
- RL training does not guarantee convergence to optimal parameters and relies on exploration; may fail when random Chvátal multipliers rarely help.
- Cuts are added only at the root node of the branch-and-cut tree.
- Experiments use a simple stacking encoder on small synthetic multiple knapsack instances.
Experimental setup
Datasets: Chvátal distribution multiple knapsack instances (synthetic)
Benchmarks: multiple knapsack instances from Chvátal distribution (1,000 test)
Metrics: average branch-and-cut tree size percentage tree size reduction LP solving and inference time
Baselines: SCIP-style efficacy+parallelism weighted cut selection linear threshold network CG cut selection with STE
Builds on: Balcan et al. data-driven algorithm design pseudo-dimension framework Balcan et al. learning CG cut multipliers TD3
Closest papers by meaning
- Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.91)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.91)
- Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.87)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.87)
- Accelerating data-driven algorithm selection for combinatorial partitioning problems (NeurIPS 2025 · similarity 0.87)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.