Solving Box-Constrained Nonconvex Quadratic Programs

We present effective computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvatal-Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with an integrality-based branching technique and a strengthened convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Most of our computational techniques have been implemented in the recent version of CPLEX and lead to significant performance improvements on nonconvex quadratic programs with linear constraints.