J. Gondzio and E. Alper Yildirim
Abstract
A standard quadratic program is an optimization problem that consists
of minimizing a (nonconvex) quadratic form over the unit simplex.
We focus on reformulating a standard quadratic program as a mixed
integer linear programming problem. We propose two alternative mixed
integer linear programming formulations. Our first formulation
is based on casting a standard quadratic program as a linear program
with complementarity constraints. We then employ binary variables
to linearize the complementarity constraints. For the second formulation,
we first derive an overestimating function of the objective function
and establish its tightness at any global minimizer. We then linearize
the overestimating function using binary variables and obtain our
second formulation. For both formulations, we propose a set of valid
inequalities. Our extensive computational results illustrate that
the proposed mixed integer linear programming reformulations
significantly outperform other global solution approaches.
On larger instances, we usually observe improvements of orders of magnitude.
Key words: Nonconvex Optimization, Standard Quadratic Programming, Mixed Integer Linear Programming.