Disjunctive Cuts for Non-Convex Mixed Integer Quadratically Constrained Programs

Anureet Saxena (anureetsandrew.cmu.edu)
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 = 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.

Keywords: global optimization, mixed integer nonlinear programming, mixed integer quadratically constrained programming, disjunctive programming, lift and project

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

Category 2: Global Optimization

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: IBM Research Report RC24502, 02/2008

Download: [PDF]

Entry Submitted: 03/07/2008
Entry Accepted: 03/07/2008
Entry Last Modified: 03/25/2008

Modify/Update this entry