Embedded Mixed-Integer Quadratic Optimization Using the OSQP Solver

B. Stellato, V. V. Naik, A. Bemporad, P. J. Goulart and S. Boyd

@inproceedings{SNBetal:2018,
  author = {B. Stellato and V. V. Naik and A. Bemporad and P. J. Goulart and S. Boyd},
  title = {Embedded Mixed-Integer Quadratic Optimization Using the OSQP Solver},
  booktitle = {European Control Conference},
  year = {2018},
  pages = {1536-1541}
}

We present a novel branch-and-bound solver for mixed-integer quadratic programs (MIQPs) that efficiently exploits the first-order OSQP solver for the quadratic program (QP) sub-problems. Our algorithm is very robust, requires no dynamic memory allocation and is division-free once an initial factorization is computed. Thus, it suitable for embedded applications with low computing power. Moreover, it does not require any assumption on the problem data such as strict convexity of the objective function. We exploit factorization caching and warm-starting to reduce the computational cost of QP relaxations during branch-and-bound and over repeated solutions of parametric MIQPs such as those arising in embedded control, portfolio optimization, and machine learning. Numerical examples show that our method, using a simple high-level Python implementation interfaced with the OSQP solver, is competitive with established commercial solvers.