Back to Search
Start Over
On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0-1 quadratic problems leading to quasi-Newton methods.
- Source :
-
Mathematical Programming . Aug2013, Vol. 140 Issue 1, p99-124. 26p. 1 Black and White Photograph, 6 Charts, 2 Graphs. - Publication Year :
- 2013
-
Abstract
- This article presents a family of semidefinite programming bounds, obtained by Lagrangian duality, for 0-1 quadratic optimization problems with linear or quadratic constraints. These bounds have useful computational properties: they have a good ratio of tightness to computing time, they can be optimized by a quasi-Newton method, and their final tightness level is controlled by a real parameter. These properties are illustrated on three standard combinatorial optimization problems: unconstrained 0-1 quadratic optimization, heaviest $$k$$-subgraph, and graph bisection. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 140
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 88428572
- Full Text :
- https://doi.org/10.1007/s10107-012-0628-6