TY - GEN
T1 - Embedded Mixed-Integer Quadratic optimization Using the OSQP Solver
AU - Stellato, Bartolomeo
AU - Naik, Vihangkumar V.
AU - Bemporad, Alberto
AU - Goulart, Paul
AU - Boyd, Stephen
N1 - Funding Information:
This work was supported by the People Programme (Marie Curie Actions) of the European Unions Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no 607957 (TEMPO). B. Stellato is with the Massachusetts Institute of Technology, 77 Massachusetts Ave, Cambridge MA 02139, USA. stellato@mit.edu P. Goulart is with the University of Oxford, Parks Road, Oxford, OX1 3PJ, UK. {bartolomeo.stellato, paul.goulart}@eng.ox.ac.uk V. V. Naik and A. Bemporad are with IMT Institute for Advanced Studies Lucca, Piazza S. Francesco 19, 55100 Lucca, Italy. {vihangkumar.naik, alberto.bemporad}@imtlucca.it S. Boyd is with the Department of Electrical Engineering, Stanford University, Stanford CA 94305, USA. boyd@stanford.edu
Publisher Copyright:
© 2018 European Control Association (EUCA).
PY - 2018/11/27
Y1 - 2018/11/27
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85059814364&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059814364&partnerID=8YFLogxK
U2 - 10.23919/ECC.2018.8550136
DO - 10.23919/ECC.2018.8550136
M3 - Conference contribution
AN - SCOPUS:85059814364
T3 - 2018 European Control Conference, ECC 2018
SP - 1536
EP - 1541
BT - 2018 European Control Conference, ECC 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 16th European Control Conference, ECC 2018
Y2 - 12 June 2018 through 15 June 2018
ER -