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 mixedinteger linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and bigM 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 stateoftheart MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILPbased 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:  nonconvex 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 07284452 Xia, Wei; Vera, Juan C.; Zuluaga, Luis F. 
2020

all
top 5
Cited by 26 Authors
all
top 5
Cited in 8 Serials
Cited in 3 Fields
11  Operations research, mathematical programming (90XX) 
1  Linear and multilinear algebra; matrix theory (15XX) 
1  Game theory, economics, finance, and other social and behavioral sciences (91XX) 