Optimization Online


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

Anureet Saxena (anureet***at***yahoo.com)
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 = 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

  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