Solving unconstrained binary quadratic programming problem by global equilibrium search

被引：4

作者：

Shylo V.P. ^{[1
]}

Shylo O.V. ^{[2
]}

机构：

[1] V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv

[2] University of Pittsburgh, Pittsburgh

来源：

Cybernetics and Systems Analysis | 2011年 / 47卷 / 6期

关键词：

Approximate methods; Binary quadratic programming; Comparative analysis of algorithms; Computational experiment; Global equilibrium search;

D O I：

10.1007/s10559-011-9368-5

中图分类号：

学科分类号：

摘要：

A new algorithm based on global equilibrium search (GES) is developed to solve an unconstrained binary quadratic programming (UBQP) problem. It is compared with the best methods of solving this problem. The GES algorithm is shown to be better both in speed and solution quality. © 2011 Springer Science+Business Media, Inc.

引用

页码：889 / 897

页数：8

共 23 条

[1]

Alidaee B., Kochenberger G., Ahmadian A., 0-1 quadratic programming approach for the optimal solution of two scheduling problems, Intern. J. Syst. Sci., 25, pp. 401-408, (1994)

[2]

Gallo G., Hammer P.L., Simeone B., Quadratic knapsack problems, Math. Program., 12, pp. 132-149, (1980)

[3]

Pardalos P.M., Xue J., The maximum clique problem, J. Global Optimiz., 4, pp. 301-328, (1994)

[4]

Lu Z., Glover F., Jin-Kao H., A hybrid metaheuristic approach to solving the UBQP problem, Eur. J. Oper. Res., 207, 3, pp. 1254-1262, (2010)

[5]

Kochenberger G.A., Glover F., Alidaee B., Rego C., A unified modeling and solution framework for combinatorial optimization problems, OR Spectrum, 26, 2, pp. 237-250, (2004)

[6]

Allemand K., Fukuda K., Liebling T.M., Steiner E., A polynomial case of unconstrained zero-one quadratic optimization, Mathematical Programming, Series B, 91, 1, pp. 49-52, (2001)

[7]

Pardalos P.M., Jha S., Complexity of uniqueness and local search in quadratic 0-1 programming, Oper. Res. Letters, 11, pp. 119-123, (1992)

[8]

Helmberg C., Rendl F., Solving quadratic (0, 1)-problems by semidefinite programs and cutting planes, Mathematical Programming, Series B, 82, 3, pp. 291-315, (1998)

[9]

Palubeckis G.A., Heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming, Computing, 54, pp. 283-301, (1995)

[10]

Beasley J.E., "heuristic Algorithms for the Unconstrained Binary Quadratic Programming Problem, (1998)

← 1 2 3 →