Solving large-scale sparse semidefinite programs for combinatorial optimization

被引：178

作者：

Benson, SJ ^{[3
]}

Ye, YY

Zhang, X

机构：

[1] Univ Iowa, Dept Management Sci, Iowa City, IA 52242 USA

[2] Huazhong Univ Sci & Technol, Sch Mech Engn, Wuhan 430074, Hubei, Peoples R China

[3] Univ Iowa, Computat Optimizat Lab, Iowa City, IA 52242 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 2000年 / 10卷 / 02期

关键词：

semidefinite programming; dual potential reduction algorithm; maximum cut problem;

D O I：

10.1137/S1052623497328008

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 positive semidefinite relaxation of combinatorial and quadratic optimization problems subject to boolean constraints. We report the first computational results of interior-point algorithms for approximating maximum cut semidefinite programs with dimension up to 3,000.

引用

页码：443 / 461

页数：19

共 36 条

[31] Semidefinite programming
Vandenberghe, L
Boyd, S
[J]. SIAM REVIEW, 1996, 38 (01) : 49 - 95
[32] WOLKOWICZ H, IN PRESS DISCRETE AP
[33] YE Y, 1997, WILEY INTERSCI SER D
[34] Approximating quadratic programming with bound and quadratic constraints
Ye, YY
[J]. MATHEMATICAL PROGRAMMING, 1999, 84 (02) : 219 - 226
[35] Semidefinite programming relaxations for the quadratic assignment problem
Zhao, Q
Karisch, SE
Rendl, F
Wolkowicz, H
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 1998, 2 (01) : 71 - 109
[36] ZHAO Q, 1996, THESIS U WATERLOO

← 1 2 3 4 →