Convex relaxations of non-convex MIQCP

Tuesday, November 18, 2008 - 11:15am - 12:00pm
EE/CS 3-180
Anureet Saxena (Axioma Inc.)
Joint work with Pierre Bonami and Jon Lee.

This talk 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 xT. We
use the concave constraint $0 \succcurlyeq Y - x xT $ to derive
disjunctions of two types. The first ones are directly derived from
the eigenvectors of the matrix Y - x xT 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
xT \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.
MSC Code: