Journal article
Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming
Journal of global optimization, Vol.43(2-3), pp.471-484
03/01/2009
DOI: 10.1007/s10898-008-9372-0
Abstract
We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that the use of SDP and RLT constraints together can produce bounds that are substantially better than either technique used alone. For highly symmetric problems we also consider the effect of symmetry-breaking based on tightened bounds on variables and/or order constraints.
Details
- Title: Subtitle
- Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming
- Creators
- Kurt M. Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Journal of global optimization, Vol.43(2-3), pp.471-484
- Publisher
- Springer Nature
- DOI
- 10.1007/s10898-008-9372-0
- ISSN
- 0925-5001
- eISSN
- 1573-2916
- Number of pages
- 14
- Language
- English
- Date published
- 03/01/2009
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380410702771
Metrics
9 Record Views