Back to Search
Start Over
Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations.
- Source :
- Mathematical Programming; Jul2010, Vol. 124 Issue 1/2, p383-411, 29p, 1 Diagram, 10 Charts, 3 Graphs
- Publication Year :
- 2010
-
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<superscript> T</superscript>. 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<superscript> T</superscript> 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 124
- Issue :
- 1/2
- Database :
- Complementary Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 52532664
- Full Text :
- https://doi.org/10.1007/s10107-010-0371-9