Optimization Online


Disjunctive Cuts for Non-Convex Mixed Integer Quadratically Constrained Programs

Anureet Saxena (anureets***at***andrew.cmu.edu)
Pierre Bonami (pierre.bonami***at***lif.univ-mrs.fr)
Jon Lee (jonlee***at***us.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: 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.


Entry Submitted: 03/07/2008
Entry Accepted: 03/07/2008
Entry Last Modified: 08/15/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society