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

Online Mixed-Integer Optimization in Milliseconds

Author

Listed:
  • Dimitris Bertsimas

    (Operations Research Center and Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Bartolomeo Stellato

    (Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544)

Abstract

We propose a method to approximate the solution of online mixed-integer optimization (MIO) problems at very high speed using machine learning. By exploiting the repetitive nature of online optimization, we can greatly speed up the solution time. Our approach encodes the optimal solution into a small amount of information denoted as strategy using the voice of optimization framework. In this way, the core part of the optimization routine becomes a multiclass classification problem that can be solved very quickly. In this work, we extend that framework to real-time and high-speed applications focusing on parametric mixed-integer quadratic optimization. We propose an extremely fast online optimization method consisting of a feedforward neural network evaluation and a linear system solution where the matrix has already been factorized. Therefore, this online approach does not require any solver or iterative algorithm. We show the speed of the proposed method both in terms of total computations required and measured execution time. We estimate the number of floating point operations required to completely recover the optimal solution as a function of the problem dimensions. Compared with state-of-the-art MIO routines, the online running time of our method is very predictable and can be lower than a single matrix factorization time. We benchmark our method against the state-of-the-art solver Gurobi obtaining up to two to three orders of magnitude speedups on examples from fuel cell energy management, sparse portfolio optimization, and motion planning with obstacle avoidance. Summary of Contribution: We propose a technique to approximate the solution of online optimization problems at high speed using machine learning. By exploiting the repetitive nature of online optimization, we learn the mapping between the key problem parameters and an encoding of the optimal solution to greatly speed up the solution time. This allows us to significantly improve the computation time and resources needed to solve online mixed-integer optimization problems. We obtain a simple method with a very low computing time variance, which is crucial in online settings.

Suggested Citation

  • Dimitris Bertsimas & Bartolomeo Stellato, 2022. "Online Mixed-Integer Optimization in Milliseconds," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2229-2248, July.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:4:p:2229-2248
    DOI: 10.1287/ijoc.2022.1181
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1181
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2022.1181?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. Dimitris Bertsimas & Patrick Jaillet, & Sébastien Martin, 2019. "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," Operations Research, INFORMS, vol. 67(1), pages 143-162, January.
    2. Florian Herzog & Gabriel Dondi & Hans P. Geering, 2007. "Stochastic Model Predictive Control And Portfolio Optimization," International Journal of Theoretical and Applied Finance (IJTAF), World Scientific Publishing Co. Pte. Ltd., vol. 10(02), pages 203-233.
    3. Onur Tavaslıoğlu & Oleg A. Prokopyev & Andrew J. Schaefer, 2019. "Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function," Operations Research, INFORMS, vol. 67(6), pages 1659-1677, November.
    4. David Silver & Julian Schrittwieser & Karen Simonyan & Ioannis Antonoglou & Aja Huang & Arthur Guez & Thomas Hubert & Lucas Baker & Matthew Lai & Adrian Bolton & Yutian Chen & Timothy Lillicrap & Fan , 2017. "Mastering the game of Go without human knowledge," Nature, Nature, vol. 550(7676), pages 354-359, October.
    5. Stephen Boyd & Enzo Busseti & Steven Diamond & Ronald N. Kahn & Kwangmoo Koh & Peter Nystrup & Jan Speth, 2017. "Multi-Period Trading via Convex Optimization," Papers 1705.00109, arXiv.org.
    6. Alejandro Marcos Alvarez & Quentin Louveaux & Louis Wehenkel, 2017. "A Machine Learning-Based Approximation of Strong Branching," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 185-195, February.
    7. Andrea Lodi & Giulia Zarpellon, 2017. "Rejoinder on: On learning and branching: a survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(2), pages 247-248, July.
    8. Andrea Lodi & Giulia Zarpellon, 2017. "On learning and branching: a survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(2), pages 207-236, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dimitris Bertsimas & Cheol Woo Kim, 2023. "A Prescriptive Machine Learning Approach to Mixed-Integer Convex Optimization," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1225-1241, November.
    2. Yilmaz, Dogacan & Büyüktahtakın, İ. Esra, 2024. "An expandable machine learning-optimization framework to sequential decision-making," European Journal of Operational Research, Elsevier, vol. 314(1), pages 280-296.

    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. Bissan Ghaddar & Ignacio Gómez-Casares & Julio González-Díaz & Brais González-Rodríguez & Beatriz Pateiro-López & Sofía Rodríguez-Ballesteros, 2023. "Learning for Spatial Branching: An Algorithm Selection Approach," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1024-1043, September.
    2. Dimitris Bertsimas & Cheol Woo Kim, 2023. "A Prescriptive Machine Learning Approach to Mixed-Integer Convex Optimization," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1225-1241, November.
    3. Yu Yang & Natashia Boland & Martin Savelsbergh, 2021. "Multivariable Branching: A 0-1 Knapsack Problem Case Study," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1354-1367, October.
    4. Francisco Jara-Moroni & John E. Mitchell & Jong-Shi Pang & Andreas Wächter, 2020. "An enhanced logical benders approach for linear programs with complementarity constraints," Journal of Global Optimization, Springer, vol. 77(4), pages 687-714, August.
    5. Nikolaus Furian & Michael O’Sullivan & Cameron Walker & Eranda Çela, 2021. "A machine learning-based branch and price algorithm for a sampled vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 693-732, September.
    6. Bengio, Yoshua & Lodi, Andrea & Prouvost, Antoine, 2021. "Machine learning for combinatorial optimization: A methodological tour d’horizon," European Journal of Operational Research, Elsevier, vol. 290(2), pages 405-421.
    7. Álinson S. Xavier & Feng Qiu & Shabbir Ahmed, 2021. "Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 739-756, May.
    8. Yang, Yu & Boland, Natashia & Dilkina, Bistra & Savelsbergh, Martin, 2022. "Learning generalized strong branching for set covering, set packing, and 0–1 knapsack problems," European Journal of Operational Research, Elsevier, vol. 301(3), pages 828-840.
    9. Bongiovanni, Claudia & Kaspi, Mor & Cordeau, Jean-François & Geroliminis, Nikolas, 2022. "A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    10. Brais González-Rodríguez & Joaquín Ossorio-Castillo & Julio González-Díaz & Ángel M. González-Rueda & David R. Penas & Diego Rodríguez-Martínez, 2023. "Computational advances in polynomial optimization: RAPOSa, a freely available global solver," Journal of Global Optimization, Springer, vol. 85(3), pages 541-568, March.
    11. Shen, Yunzhuang & Sun, Yuan & Li, Xiaodong & Eberhard, Andrew & Ernst, Andreas, 2023. "Adaptive solution prediction for combinatorial optimization," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1392-1408.
    12. Gambella, Claudio & Ghaddar, Bissan & Naoum-Sawaya, Joe, 2021. "Optimization problems for machine learning: A survey," European Journal of Operational Research, Elsevier, vol. 290(3), pages 807-828.
    13. Eric Larsen & Sébastien Lachapelle & Yoshua Bengio & Emma Frejinger & Simon Lacoste-Julien & Andrea Lodi, 2022. "Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 227-242, January.
    14. Juho Lauri & Sourav Dutta & Marco Grassia & Deepak Ajwani, 2023. "Learning fine-grained search space pruning and heuristics for combinatorial optimization," Journal of Heuristics, Springer, vol. 29(2), pages 313-347, June.
    15. Razvan Oprisor & Roy Kwon, 2020. "Multi-Period Portfolio Optimization with Investor Views under Regime Switching," JRFM, MDPI, vol. 14(1), pages 1-31, December.
    16. Ayman Chaouki & Stephen Hardiman & Christian Schmidt & Emmanuel S'eri'e & Joachim de Lataillade, 2020. "Deep Deterministic Portfolio Optimization," Papers 2003.06497, arXiv.org, revised Apr 2020.
    17. Charly Robinson La Rocca & Jean-François Cordeau & Emma Frejinger, 2024. "One-Shot Learning for MIPs with SOS1 Constraints," SN Operations Research Forum, Springer, vol. 5(3), pages 1-28, September.
    18. Christoph Hertrich & Martin Skutella, 2023. "Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1079-1097, September.
    19. Emilio Carrizosa & Cristina Molero-Río & Dolores Romero Morales, 2021. "Mathematical optimization in classification and regression trees," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 5-33, April.
    20. Renke Kuhlmann, 2019. "Learning to steer nonlinear interior-point methods," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(4), pages 381-419, December.

    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:4:p:2229-2248. 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.