TITLE: Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs

SPEAKER: Dr. Anureet Saxena (Research division, Axioma, Inc.)

ABSTRACT:

Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Extended Formulations
http://www.optimization-online.org/DB_HTML/2008/08/2068.html

This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, we propose new methods for generating valid inequalities by using the equation Y = xx^T. We use the concave constraint 0 succcurlyeq Y - xx^T to derive disjunctions of two types. The first ones are directly derived from the eigenvectors of the matrix Y - xx^T with positive eigenvalues, the second type of disjunctions are obtained by combining several eigenvectors in order to minimize the "width" of the disjunction. We also use the convex SDP constraint Y - xx^T succcurlyeq 0 to derive convex quadratic cuts, and we combine both approaches in a cutting plane algorithm. We present computational results to illustrate our findings.

Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs
http://www.optimization-online.org/DB_HTML/2008/11/2145.html

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 x_i x_j 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 - x x^T succeq 0 and disjunctive programming. On the other hand, their main drawback is their huge size, even for problems of moderate size. 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 the 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 sec even for larger instances with 100 variables; the SDP+RLT relaxations of the same set of instances can take up to a couple of hours to solve using a state-of-the-art SDP solver.

This is joint work with Pierre Bonami and Jon Lee