IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i5p2400-2409.html
   My bibliography  Save this article

Stochastic Cutting Planes for Data-Driven Optimization

Author

Listed:
  • 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)

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.

Suggested Citation

  • Dimitris Bertsimas & Michael Lingzhi Li, 2022. "Stochastic Cutting Planes for Data-Driven Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2400-2409, September.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:5:p:2400-2409
    DOI: 10.1287/ijoc.2022.1205
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1205
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1205?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Richard W. Blundell & James L. Powell, 2004. "Endogeneity in Semiparametric Binary Response Models," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 71(3), pages 655-679.
    2. Rivers, Douglas & Vuong, Quang H., 1988. "Limited information estimators and exogeneity tests for simultaneous probit models," Journal of Econometrics, Elsevier, vol. 39(3), pages 347-366, November.
    3. Robert Bixby & Edward Rothberg, 2007. "Progress in computational mixed integer programming—A look back from the other side of the tipping point," Annals of Operations Research, Springer, vol. 149(1), pages 37-41, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chesher, Andrew, 2013. "Semiparametric Structural Models Of Binary Response: Shape Restrictions And Partial Identification," Econometric Theory, Cambridge University Press, vol. 29(2), pages 231-266, April.
    2. Richard Bluhm & Martin Gassebner & Sarah Langlotz & Paul Schaudt, 2021. "Fueling conflict? (De)escalation and bilateral aid," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 36(2), pages 244-261, March.
    3. Jarke-Neuert, Johannes & Perino, Grischa & Schwickert, Henrike, 2021. "Free-Riding for Future: Field Experimental Evidence of Strategic Substitutability in Climate Protest," SocArXiv sh6dm, Center for Open Science.
    4. Yingying Dong & Arthur Lewbel, 2015. "A Simple Estimator for Binary Choice Models with Endogenous Regressors," Econometric Reviews, Taylor & Francis Journals, vol. 34(1-2), pages 82-105, February.
    5. Manuel Denzer, 2019. "Estimating Causal Effects in Binary Response Models with Binary Endogenous Explanatory Variables - A Comparison of Possible Estimators," Working Papers 1916, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    6. Brambilla, Irene, 2009. "Multinationals, technology, and the introduction of varieties of goods," Journal of International Economics, Elsevier, vol. 79(1), pages 89-101, September.
    7. Andrea A. Naghi & Máté Váradi & Mikhail Zhelonkin, 2021. "Robust Estimation of Probit Models with Endogeneity," Tinbergen Institute Discussion Papers 21-004/III, Tinbergen Institute.
    8. Joseph G. Altonji & Hidehiko Ichimura & Taisuke Otsu, 2012. "Estimating Derivatives in Nonseparable Models With Limited Dependent Variables," Econometrica, Econometric Society, vol. 80(4), pages 1701-1719, July.
    9. Elia Lapenta, 2022. "A Bootstrap Specification Test for Semiparametric Models with Generated Regressors," Papers 2212.11112, arXiv.org, revised Oct 2023.
    10. Ilhom Abdulloev, 2018. "Job dissatisfaction and migration: evidence from Tajikistan," IZA Journal of Migration and Development, Springer;Forschungsinstitut zur Zukunft der Arbeit GmbH (IZA), vol. 8(1), pages 1-27, December.
    11. Furtado, Delia & Hock, Heinrich, 2008. "Immigrant Labor, Child-Care Services, and the Work-Fertility Trade-Off in the United States," IZA Discussion Papers 3506, Institute of Labor Economics (IZA).
    12. Hoderlein, Stefan & Sherman, Robert, 2015. "Identification and estimation in a correlated random coefficients binary response model," Journal of Econometrics, Elsevier, vol. 188(1), pages 135-149.
    13. Bluhm R & Crombrugghe D.P.I. de & Szirmai A., 2013. "The pace of poverty reduction - A fractional response approach," MERIT Working Papers 2013-051, United Nations University - Maastricht Economic and Social Research Institute on Innovation and Technology (MERIT).
    14. Hongxiu Li, 2017. "Innovation as Adaptation to Natural Disasters," Working Papers 1709, University of Waterloo, Department of Economics, revised Nov 2017.
    15. Fitzenberger, Bernd & Furdas, Marina & Sajons, Christoph, 2016. "End-of-year spending and the long-run employment effects of training programs for the unemployed," Freiburg Discussion Papers on Constitutional Economics 16/08, Walter Eucken Institut e.V..
    16. Amil Petrin & Kenneth Train, 2003. "Omitted Product Attributes in Discrete Choice Models," NBER Working Papers 9452, National Bureau of Economic Research, Inc.
    17. Hahn, Jinyong & Liao, Zhipeng & Ridder, Geert & Shi, Ruoyao, 2023. "The influence function of semiparametric two-step estimators with estimated control variables," Economics Letters, Elsevier, vol. 231(C).
    18. Dong, Yingying, 2010. "Endogenous regressor binary choice models without instruments, with an application to migration," Economics Letters, Elsevier, vol. 107(1), pages 33-35, April.
    19. William Liu, 2023. "A Theory Guide to Using Control Functions to Instrument Hazard Models," Papers 2312.03165, arXiv.org.
    20. Lee C. Adkins, 2009. "An Instrumental Variables Probit Estimator Using Gretl," EHUCHAPS, in: Ignacio Díaz-Emparanza & Petr Mariel & María Victoria Esteban (ed.), Econometrics with gretl. Proceedings of the gretl Conference 2009, edition 1, chapter 4, pages 59-74, Universidad del País Vasco - Facultad de Ciencias Económicas y Empresariales.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:5:p:2400-2409. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.