Embedded Mixed-Integer Quadratic optimization Using the OSQP Solver

Bartolomeo Stellato, Vihangkumar V. Naik, Alberto Bemporad, Paul Goulart, Stephen Boyd

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 European Control Conference, ECC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1536-1541
Number of pages6
ISBN (Electronic)9783952426982
DOIs
StatePublished - Nov 27 2018
Externally publishedYes
Event16th European Control Conference, ECC 2018 - Limassol, Cyprus
Duration: Jun 12 2018Jun 15 2018

Publication series

Name2018 European Control Conference, ECC 2018

Conference

Conference16th European Control Conference, ECC 2018
CountryCyprus
CityLimassol
Period6/12/186/15/18

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Control and Optimization

Fingerprint Dive into the research topics of 'Embedded Mixed-Integer Quadratic optimization Using the OSQP Solver'. Together they form a unique fingerprint.

  • Cite this

    Stellato, B., Naik, V. V., Bemporad, A., Goulart, P., & Boyd, S. (2018). Embedded Mixed-Integer Quadratic optimization Using the OSQP Solver. In 2018 European Control Conference, ECC 2018 (pp. 1536-1541). [8550136] (2018 European Control Conference, ECC 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.23919/ECC.2018.8550136