Stochastic Cutting Planes for Data-Driven Optimization

Dimitris Bertsimas () and Michael Lingzhi Li ()
Additional contact information
Dimitris Bertsimas: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Michael Lingzhi Li: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

INFORMS Journal on Computing, 2022, vol. 34, issue 5, 2400-2409

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 can 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 with 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 ( n 3 ) appears to be sufficient for high-quality solutions.

Keywords: stochastic optimization; mixed-integer optimization; machine learning; cutting planes; outer approximation; scaling (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1205 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:5:p:2400-2409

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().