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 = x x^T$. We use the concave constraint $0 \succcurlyeq Y - x x^T$ to derive disjunctions of two types. The first ones are directly derived from the eigenvectors of the matrix $Y - x x^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 - x x^T \succcurlyeq 0$ to derive convex quadratic cuts and combine both approaches in a cutting plane algorithm. We present preliminary computational results to illustrate our findings.
Citation
Edited version appeared in IPCO 2008. Anureet Saxena, Pierre Bonami and Jon Lee. Disjunctive cuts for non-convex mixed integer quadratically constrained programs, In: “Integer programming and combinatorial optimization (Bertinoro, 2008)“, A. Lodi, A. Panconesi, and G. Rinaldi, Eds., Lecture Notes in Computer Science volume 5035, pp. 17–33. Springer-Verlag Berlin Heidelberg, 2008.