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 - 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 -