Details

Autor(en) / Beteiligte

• Xia, Wei
• Vera, Juan C.
• Zuluaga, Luis F.

Titel

Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques

Ist Teil von

• INFORMS journal on computing, 2020-01, Vol.32 (1), p.40-56

Ort / Verlag

Linthicum: INFORMS

Erscheinungsjahr

2020

Quelle

Informs PubsOnline

Beschreibungen/Notizen

• 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 https://github.com/xiawei918/quadprogIP .