Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Extended Formulations

Anureet Saxena (anureetyahoo.com)
Pierre Bonami (pierre.bonamilif.univ-mrs.fr)
Jon Lee (jonleeus.ibm.com)

Abstract: 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.

Keywords: MINLP, Mixed integer nonlinear programming, MIQCP, global optimization

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Global Optimization

Citation: IBM Research Report RC24621, August 2008

Download: [PDF]

Entry Submitted: 08/15/2008
Entry Accepted: 08/15/2008
Entry Last Modified: 08/27/2008

Modify/Update this entry