Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem

被引:161
作者
Maniezzo, V [1 ]
机构
[1] Univ Bologna, I-47023 Casena, Italy
关键词
D O I
10.1287/ijoc.11.4.358
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This article introduces two new techniques far solving the Quadratic Assignment Problem. The first is a heuristic technique, defined in accordance with the Ant System metaphor, and includes as a distinctive feature the use of a new lower bound at: each constructive step. The second is a branch-and-hound exact: approach, containing some elements introduced in the Ant algorithm. Computational results prove the effectiveness of both approaches.
引用
收藏
页码:358 / 369
页数:12
相关论文
共 33 条
[1]  
[Anonymous], 1994, DIMACS SERIES DISCRE
[2]  
[Anonymous], DIMACS SERIES DISCRE
[3]   ON LOWER BOUNDS FOR A CLASS OF QUADRATIC-0, 1 PROGRAMS [J].
ASSAD, AA ;
XU, WX .
OPERATIONS RESEARCH LETTERS, 1985, 4 (04) :175-180
[4]  
Battiti R., 1994, ORSA Journal on Computing, V6, P126, DOI 10.1287/ijoc.6.2.126
[5]  
BRUNGGER A, 1996, TR9623 DIKU U COP
[6]   QUADRATIC ASSIGNMENT PROBLEMS [J].
BURKARD, RE .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 15 (03) :283-289
[7]  
BURKARD RE, 1994, QAPLIB QUADRATIC ASS
[8]  
BURKARD RE, 1980, LECT NOTES EC MATH S, V184
[9]   A NEW LOWER BOUND FOR THE QUADRATIC ASSIGNMENT PROBLEM [J].
CARRARESI, P ;
MALUCELLI, F .
OPERATIONS RESEARCH, 1992, 40 :S22-S27
[10]  
Cela E., 1998, The Quadratic Assignment Problem: Theory and Algorithms