Solving large-scale sparse semidefinite programs for combinatorial optimization

Authors
Benson, SJ Ye, YY Zhang, X
Citation
Sj. Benson et al., Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM J OPTI, 10(2), 2000, pp. 443-461
Citations number
36
Categorie Soggetti
Mathematics
Journal title
SIAM JOURNAL ON OPTIMIZATION
ISSN journal
10526234 → ACNP
Volume
10
Issue
2
Year of publication
2000
Pages
443 - 461
Database
ISI
SICI code
1052-6234(20000223)10:2<443:SLSSPF>2.0.ZU;2-0
Abstract
We present a dual-scaling interior-point algorithm and show how it exploits the structure and sparsity of some large-scale problems. We solve the posi tive semidefinite relaxation of combinatorial and quadratic optimization pr oblems subject to boolean constraints. We report the first computational re sults of interior-point algorithms for approximating maximum cut semidefini te programs with dimension up to 3,000.