Disjunctive Cuts for Non-Convex Mixed Integer Quadratically Constrained Programs
Anureet Saxena (anureetsandrew.cmu.edu)
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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|