  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.
