Paper Info
Title
Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations
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 from the equation Y =  x x T . We use the non-convex constraint $${ Y - x x^T \preccurlyeq 0}$$ 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 we combine both approaches in a cutting plane algorithm. We present computational results to illustrate our findings.
Year
DOI
Venue
2010
10.1007/s10107-010-0371-9
Math. Program.
Keywords
Field
DocType
strong convex relaxation,extended formulation,non-convex quadratic constraint,non-convex mixed integer quadratically,equation y,convex quadratic cut,miqcp problem,convex sdp constraint,non-convex constraint,matrix y,strong relaxation,constrained programming,eigenvectors,global optimization,eigenvalues
Integer,Constraint satisfaction,Discrete mathematics,Quadratic growth,Cutting-plane method,Mathematical optimization,Combinatorics,Global optimization,Integer programming,Quadratic programming,Convex optimization,Mathematics
Journal
Volume
Issue
ISSN
124
1-2
1436-4646
Citations 
PageRank 
References 
29
1.07
27
Authors
3
Name
Order
Citations
PageRank
Anureet Saxena11677.42
Pierre Bonami254728.71
Jon Lee385658.60