Online Mixed-Integer Optimization in Milliseconds
<jats:p> 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 soluti...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144109 |
| _version_ | 1826208542046027776 |
|---|---|
| author | Bertsimas, Dimitris Stellato, Bartolomeo |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Bertsimas, Dimitris Stellato, Bartolomeo |
| author_sort | Bertsimas, Dimitris |
| collection | MIT |
| description | <jats:p> 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. </jats:p><jats:p> 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. </jats:p> |
| first_indexed | 2024-09-23T14:07:16Z |
| format | Article |
| id | mit-1721.1/144109 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:07:16Z |
| publishDate | 2022 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1441092023-06-20T17:33:26Z Online Mixed-Integer Optimization in Milliseconds Bertsimas, Dimitris Stellato, Bartolomeo Sloan School of Management <jats:p> 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. </jats:p><jats:p> 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. </jats:p> 2022-07-28T14:16:56Z 2022-07-28T14:16:56Z 2022-04-08 2022-07-28T14:13:15Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/144109 Bertsimas, Dimitris and Stellato, Bartolomeo. 2022. "Online Mixed-Integer Optimization in Milliseconds." INFORMS Journal on Computing. en 10.1287/ijoc.2022.1181 INFORMS Journal on Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) arXiv |
| spellingShingle | Bertsimas, Dimitris Stellato, Bartolomeo Online Mixed-Integer Optimization in Milliseconds |
| title | Online Mixed-Integer Optimization in Milliseconds |
| title_full | Online Mixed-Integer Optimization in Milliseconds |
| title_fullStr | Online Mixed-Integer Optimization in Milliseconds |
| title_full_unstemmed | Online Mixed-Integer Optimization in Milliseconds |
| title_short | Online Mixed-Integer Optimization in Milliseconds |
| title_sort | online mixed integer optimization in milliseconds |
| url | https://hdl.handle.net/1721.1/144109 |
| work_keys_str_mv | AT bertsimasdimitris onlinemixedintegeroptimizationinmilliseconds AT stellatobartolomeo onlinemixedintegeroptimizationinmilliseconds |