Stochastic Cutting Planes for Data-Driven Optimization

2021/03/03 by Dimitris Bertsimas, Bertsimas, Dimitris, Michael Lingzhi Li +1
Engineering · #Advanced Numerical Analysis Techniques #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Manufacturing Process and Optimization #Optimization and Control (math.OC) #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.2103.02506

openalex publication_date 2021/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a stochastic version of the cutting-plane method for a large class of data-driven Mixed-Integer Nonlinear Optimization (MINLO) problems. We show that under very weak assumptions the stochastic algorithm is able to converge to an ε-optimal solution with high probability. Numerical experiments on several problems show that stochastic cutting planes is able to deliver a multiple order-of-magnitude speedup compared to the standard cutting-plane method. We further experimentally explore the lower limits of sampling for stochastic cutting planes and show that for many problems, a sampling size of O(√[3]n) appears to be sufficient for high quality solutions.

Related

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates
• Analysis of Sparse Cutting-planes for Sparse MILPs with Applications to Stochastic MILPs
• A computational study of cutting-plane methods for multi-stage stochastic integer programs
• Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization
• Continuous cutting plane algorithms in integer programming