quadprogIP swMATH ID: 36327 Software Authors: Xia, Wei; Vera, Juan C.; Zuluaga, Luis F. Description: Globally solving nonconvex quadratic programs via linear integer programming techniques . We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at url{https://github.com/xiawei918/quadprogIP}. Homepage: https://github.com/xiawei918/quadprogIP Source Code: https://github.com/xiawei918/quadprogIP Dependencies: Matlab Keywords: non-convex quadratic programming; global optimization; mixed integer linear programming; KKT conditions; branch and bound; Hoffman bound Related Software: QuadProgBB; CPLEX; GitHub; Gurobi; BARON; Eigen; QPLIB; GLOBALLib; CUTEr; GloMIQO; CopositiveAnalyticCenter.jl; BiqMac; Biq Mac; SDPLR; Mosek; NewtonKKTqp; LPCCbnc; dodgr; OpenStreetMap; Julia Cited in: 11 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Globally solving nonconvex quadratic programs via linear integer programming techniques. Zbl 07284452Xia, Wei; Vera, Juan C.; Zuluaga, Luis F. 2020 all top 5 Cited by 26 Authors 2 Liuzzi, Giampaolo 2 Locatelli, Marco 2 Muñoz, Gonzalo 2 Piccialli, Veronica 1 Anstreicher, Kurt M. 1 Badenbroek, Riley 1 Bentobache, Mohand 1 Bienstock, Daniel 1 Chen, Chen 1 de Klerk, Etienne 1 Dey, Santanu Subhas 1 Fampa, Marcia Helena C. 1 Gondzio, Jacek 1 Gourtani, Arash 1 Kazachkov, Aleksandr M. 1 Lee, Jon 1 Lodi, Andrea 1 Mokhtari, Abdelkader 1 Nguyen, Tri-Dung 1 Rass, Stefan 1 Telli, Mohamed 1 Vera, Juan-Carlos 1 Xia, Wei 1 Xu, Huifu 1 Yildirim, Emre Alper 1 Zuluaga, Luis Fernando all top 5 Cited in 8 Serials 3 Journal of Global Optimization 2 INFORMS Journal on Computing 1 Linear Algebra and its Applications 1 Mathematical Programming. Series A. Series B 1 SIAM Journal on Optimization 1 Computational Optimization and Applications 1 Optimization Letters 1 EURO Journal on Computational Optimization Cited in 3 Fields 11 Operations research, mathematical programming (90-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year