Solving large-scale sparse semidefinite programs for combinatorial optimization

被引：180

作者：

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 [J].

Vandenberghe, L ;

Boyd, S .

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 [J].

Ye, YY .

MATHEMATICAL PROGRAMMING, 1999, 84 (02) :219-226

[35] Semidefinite programming relaxations for the quadratic assignment problem [J].

Zhao, Q ;

Karisch, SE ;

Rendl, F ;

Wolkowicz, H .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 1998, 2 (01) :71-109

[36]

ZHAO Q, 1996, THESIS U WATERLOO

← 1 2 3 4 →