An algorithm for the generalized quadratic assignment problem

被引：38

作者：

Hahn, Peter M. ^{[1
]}

Kim, Bum-Jin ^{[1
]}

Guignard, Monique ^{[2
]}

Smith, J. MacGregor ^{[3
]}

Zhu, Yi-Rong ^{[1
]}

机构：

[1] Univ Penn, Philadelphia, PA 19104 USA

[2] Univ Penn, Wharton Sch, Philadelphia, PA 19104 USA

[3] Univ Massachusetts, Amherst, MA 01003 USA

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2008年 / 40卷 / 03期

基金：

美国国家科学基金会;

关键词：

combinatorial optimization; branch-and-bound; quadratic assignment problem; reformulation linearization technique; Lagrangean dual; dual ascent procedure;

D O I：

10.1007/s10589-007-9093-1

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pair-wise related entities are assigned to N destinations constrained by the destinations' ability to accommodate them. This new algorithm is based on a Reformulation Linearization Technique (RLT) dual ascent procedure. Experimental results show that the runtime of this algorithm is as good or better than other known exact solution methods for problems as large as M=20 and N=15.

引用

页码：351 / 372

页数：22

共 47 条

[1] A level-2 reformulation-linearization technique bound for the quadratic assignment problem [J].