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.
Citation
IBM Research Report RC24621, August 2008