  The current bottleneck of globally solving mixed-integer (non-convex)
quadratically constrained problem (MIQCP) is still to construct strong but
computationally cheap convex relaxations, especially when dense quadratic
functions are present. We propose a cutting surface procedure based on multiple
diagonal perturbations to derive strong convex quadratic relaxations for
nonconvex quadratic problem with separable constraints. Our resulting
relaxation does not use significantly more variables than the original problem,
in contrast to many other relaxations based on lifting. The corresponding
separation problem is a highly structured semidefinite program (SDP) with
convex but non-smooth objective. We propose to solve this separation problem
with a specialized primal-barrier coordinate minimization algorithm.
Computational results show that our approach is very promising. First, our
separation algorithm is at least an order of magnitude faster than interior
point methods for SDPs on problems up to a few hundred variables. Secondly, on
nonconvex quadratic integer problems, our cutting surface procedure provides
lower bounds of almost the same strength with the diagonal SDP bounds used by
(Buchheim and Wiegele, 2013) in their branch-and-bound code Q-MIST, while our
procedure is at least an order of magnitude faster on problems with dimension
greater than 70. Finally, combined with (linear) projected RLT cutting planes
proposed by (Saxena, Bonami and Lee, 2011), our procedure provides slightly
weaker bounds than their projected SDP+RLT cutting surface procedure, but in
several order of magnitude shorter time. Finally we discuss various avenues to
extend our work to design more efficient branch-and-bound algorithms for
MIQCPs.
