Potential reduction algorithms for structured combinatorial optimization problems

被引：3

作者：

Warners, JP ^{[1
]}

Terlaky, T ^{[1
]}

Roos, C ^{[1
]}

Jansen, B ^{[1
]}

机构：

[1] CQM BV,NL-5600 AK EINDHOVEN,NETHERLANDS

来源：

OPERATIONS RESEARCH LETTERS | 1997年 / 21卷 / 02期

关键词：

interior point methods; binary programming; combinatorial optimization; non-linear optimization;

D O I：

10.1016/S0167-6377(97)00031-X

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Recently Karmarkar proposed a potential reduction algorithm for binary feasibility problems. In this paper, a modified potential function that has more attractive properties is introduced. Furthermore, as the main result, for a specific class of binary feasibility problems a concise reformulation as nonconvex quadratic optimization problems is developed. We introduce a potential function to optimize the new model and report on computational experience with the graph coloring problem, comparing the performance of the three potential functions. (C) 1997 Elsevier Science B.V.

引用

页码：55 / 64

页数：10

共 12 条

[1]

Andersen E.D., 1996, Implementation of interior point methods for large scale linear programming, P189

[2]

Duff IS, 1989, DIRECT METHODS SPARS

[3] Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid [J].