Back to Search
Start Over
Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and Equipartition.
- Source :
-
Mathematical Programming . Feb2006, Vol. 105 Issue 2/3, p451-469. 19p. 7 Charts, 2 Graphs. - Publication Year :
- 2006
-
Abstract
- We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a relatively simple semidefinite program. Our approach provides accurate solutions to semidefinite relaxations of the Max-Cut and the Equipartition problem, which are not achievable by direct approaches based only on interior-point methods. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 105
- Issue :
- 2/3
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 19076656
- Full Text :
- https://doi.org/10.1007/s10107-005-0661-9