Convex relaxations of non-convex mixed integer quadratically constrained programs: Projected formulations

Abstract

A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem into a higher-dimensional space by introducing variables Y ij to represent each of the products xixj of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can be efficiently strengthened by using the (convex) SDP constraint Y - xxT ≥ 0 and disjunctive programming. On the other hand, the main drawback of such an extended formulation is its huge size, even for problems for which the number of xi variables is moderate. In this paper, we study methods to build low-dimensional relaxations of MIQCP that capture the strength of the extended formulations. To do so, we use projection techniques pioneered in the context of the lift-and-project methodology. We show how the extended formulation can be algorithmically projected to the original space by solving linear programs. Furthermore, we extend the technique to project the SDP relaxation by solving SDPs. In the case of an MIQCP with a single quadratic constraint, we propose a subgradient-based heuristic to efficiently solve these SDPs. We also propose a new eigen-reformulation for MIQCP, and a cut generation technique to strengthen this reformulation using polarity. We present extensive computational results to illustrate the efficiency of the proposed techniques. Our computational results have two highlights. First, on the GLOBALLib instances, we are able to generate relaxations that are almost as strong as those proposed in our companion paper even though our computing times are about 100 times smaller, on average. Second, on box-QP instances, the strengthened relaxations generated by our code are almost as strong as the well-studied SDP+RLT relaxations and can be solved in less than 2 s, even for large instances with 100 variables; the SDP+RLT relaxations for the same set of instances can take up to a couple of hours to solve using a state-of-the-art SDP solver. © 2010 Springer and Mathematical Programming Society.