Optimization Online


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

Anureet Saxena (asaxena***at***axiomainc.com)
Pierre Bonami (pierre.bonami***at***lif.univ-mrs.fr)
Jon Lee (jonlee***at***us.ibm.com)

Abstract: A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem into a higher dimensional space by introducing variables $Y_{ij}$ to represent each of the products $x_i x_j$ of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can be efficiently strengthened by using the (convex) SDP constraint $Y - x x^T \succeq 0$ and disjunctive programming. On the other hand, their main drawback is their huge size, even for problems of moderate size. In this paper, we study methods to build low-dimensional relaxations of MIQCP that capture the strength of the extended formulations. To do so, we use projection techniques pioneered in the context of the lift-and-project methodology. We show how the extended formulation can be algorithmically projected to the original space by solving linear programs. Furthermore, we extend the technique to project the SDP relaxation by solving SDPs. In the case of an MIQCP with a single quadratic constraint, we propose a subgradient-based heuristic to efficiently solve these SDPs. We also propose a new "eigen reformulation" for MIQCP, and a cut generation technique to strengthen this reformulation using polarity. We present extensive computational results to illustrate the efficiency of the proposed techniques. Our computational results have two highlights. First, on the GLOBALLib instances, we are able to generate relaxations that are almost as strong as those proposed in our companion paper even though our computing times are about 100 times smaller, on average. Second, on the box QP instances, the strengthened relaxations generated by our code are almost as strong as the well-studied SDP+RLT relaxations and can be solved in less than 2 sec even for larger instances with 100 variables; the SDP+RLT relaxations of the same set of instances can take up to a couple of hours to solve using a state-of-the-art SDP solver.

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 RC24695, 11/2008

Download: [PDF]

Entry Submitted: 11/14/2008
Entry Accepted: 11/14/2008
Entry Last Modified: 11/19/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