  


Disjunctive Cuts for NonConvex 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 nonconvexities: integer variables and nonconvex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the liftandproject 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 nonconvex 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. SpringerVerlag Berlin Heidelberg, 2008. Download: Entry Submitted: 03/07/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  