Online Mixed-Integer Optimization in Milliseconds
Authors:
- Dimitris BertsimasDBDimitris Bertsimas
- Bartolomeo StellatoBSBartolomeo Stellato
Preprint
Abstract
We propose a method to solve online mixed-integer optimization (MIO) problems at very high speed using machine learning. By exploiting the repetitive nature of online optimization, we are able to greatly speedup the solution time. Our approach encodes the optimal solution into a small amount of information denoted as strategy using the Voice of Optimization framework proposed in [BS20]. In this way the core part of the optimization algorithm becomes a multiclass classification problem which 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 (MIQO). We propose an extremely fast online optimization algorithm consisting of a feedforward neural network (NN) evaluation and a linear system solution where the matrix has already been factorized. Therefore, this online approach does not require any solver nor 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 (flops) required to completely recover the optimal solution as a function of the problem dimensions. Compared to 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 from two to three orders of magnitude speedups on examples from fuel cell energy management, sparse portfolio optimization and motion planning with obstacle avoidance.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Machine learning for combinatorial optimization: A methodological tour d’horizonEuropean Journal of Operational Research, 2021
- Machine learning-based warm starting of active set methods in embedded model predictive controlEngineering Applications of Artificial Intelligence, 2019
- A survey of direct methods for sparse linear systemsActa Numerica, 2016
- Embedded optimization for mixed logical dynamical systemsComputers & Chemical Engineering, 2015
- qpOASES: a parametric active-set algorithm for quadratic programmingMathematical Programming Computation, 2014
- CVXGEN: a code generator for embedded convex optimizationOptimization and Engineering, 2011
- Scheduling of head-dependent cascaded hydro systems: Mixed-integer quadratic programming approachEnergy Conversion and Management, 2010
- Robust multiperiod portfolio management in the presence of transaction costsComputers & Operations Research, 2008
- The explicit linear quadratic regulator for constrained systemsAutomatica, 2002
- Control of systems integrating logic, dynamics, and constraintsAutomatica, 1999