Research map / Optimization / Optimizers
Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates
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.
Uses RL-trained PPO policies as surrogates for the NP-hard master MIP in Benders decomposition and L0-regularized regression cutting-plane methods, with periodic exact MIP solves to keep optimality certificates, reporting up to 45% faster convergence.
Problem
Cutting-plane algorithms (Benders decomposition, L0-regularized regression) require repeatedly solving NP-hard mixed-integer master problems, which scales poorly on large discrete optimization instances.
Approach
Periodically replace the mixed-integer master problem with a fast RL policy surrogate (sampled over a batch of trajectories and selected by greedy, weighted, or cut-informed rules), while still running the exact MIMP at a Bernoulli-controlled rate to retain optimality certificates.
Key results
- Informed selection with Gamma=0.75 converged 30.45% faster than the Benders baseline on the inventory problem, faster on 88.24% of instances.
- Greedy selection achieved 45.31% acceleration on regularized regression, with Surrogate-MP faster on 85.60% of instances.
- RL surrogate solutions on the inventory problem were on average 14.73% higher cost than Benders optima at convergence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an RL surrogate with informed selection at Γ=0.75 instead of the no-surrogate baseline | Benders decomposition for inventory management · Inventory Management Problem | average convergence speed: 30.45% faster | Helped |
| Use greedy selection at Γ=0.75 instead of the no-surrogate baseline (ablation) | Benders decomposition for inventory management · Inventory Management Problem | average convergence speed: 19.43% faster | Helped |
| Use weighted selection at Γ=0.75 instead of the no-surrogate baseline (ablation) | Benders decomposition for inventory management · Inventory Management Problem | average convergence speed: 14.96% faster | Helped |
| Increase Γ from 0.25 to 0.5 with informed selection (ablation) | Benders decomposition for inventory management · Inventory Management Problem | average convergence speed: 11.84% -> 21.24% faster | Helped |
| Increase Γ from 0.5 to 0.75 with informed selection (ablation) | Benders decomposition for inventory management · Inventory Management Problem | average convergence speed: 21.24% -> 30.45% faster | Helped |
| Use an RL surrogate with greedy selection at Γ=0.75 instead of the no-surrogate baseline | L₀ regularized regression cutting-plane algorithm · Regularized Regression | average convergence speed: 45.31% acceleration | Helped |
| Use weighted selection at Γ=0.75 instead of greedy selection (ablation) | L₀ regularized regression cutting-plane algorithm · Regularized Regression | average convergence speed: 45.31% -> 44.41% acceleration | Hurt |
| Use informed selection at Γ=0.75 instead of greedy selection (ablation) | L₀ regularized regression cutting-plane algorithm · Regularized Regression | average convergence speed: 45.31% -> 37.97% acceleration | Hurt |
| Set Γ=0.5 instead of Γ=0.75 with informed selection (ablation) | L₀ regularized regression cutting-plane algorithm · Regularized Regression | average convergence speed: 42.94% acceleration | Helped |
| Use L₀ regularization at λ=0.1 instead of L₁ regularization at λ=0.1 (ablation) | Sparse regression · Regularized Regression, 250 synthetic problems | β Recovery: 0.317 -> 0.056 | Helped |
| Use L₀ regularization at λ=0.1 instead of L₁ regularization at λ=0.1 (ablation) | Sparse regression · Regularized Regression, 250 synthetic problems | β MSE: 0.014 -> 0.009 | Helped |
| Use L₀ regularization at λ=0.1 instead of L₁ regularization at λ=0.1 (ablation) | Sparse regression · Regularized Regression, 250 synthetic problems | Prediction MSE: 2.644 -> 2.692 | Hurt |
Surprising findings
- Best surrogate selection method differed by domain: informed selection was best for inventory management, while greedy selection was best for regularized regression.
- Surrogate-MP was less beneficial in regularized regression for informed selection (37.97%) than greedy or weighted selection.
Limitations
- Surrogate solutions are only pseudo-optimal (about 14.7% higher cost than Benders optima on inventory), so the exact MIMP is still needed for certification.
- Evaluated only on two cutting-plane applications with specific problem structures.
- Informed selection benefits depend on the observability of the MDP and were weaker for regularized regression.
Experimental setup
Datasets: real-world inventory demand data (153 cases) synthetic linear regression data (250 problems)
Benchmarks: inventory management problem instances (153 cases) L0 regularized regression instances (250 synthetic problems)
Metrics: average convergence time / percent faster fraction of instances faster cost gap to optimal beta recovery beta MSE prediction MSE
Baselines: accelerated Benders decomposition (scenario group cuts and partial decomposition cutting-plane algorithm for L0 regression without surrogate L1 regularization (lasso)
Builds on: Benders decomposition proximal policy optimization generalized advantage estimation L0 regularized regression cutting planes
Closest papers by meaning
- Learning to Remove Cuts in Integer Linear Programming (ICML 2024 · similarity 0.88)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.87)
- Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming (AAAI 2024 · similarity 0.87)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.85)
- Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.85)
- Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.85)
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.