An algorithm for the generalized quadratic assignment problem

被引：0
作者：
Peter M. Hahn
Bum-Jin Kim
Monique Guignard
J. MacGregor Smith
Yi-Rong Zhu
机构：
[1] University of Pennsylvania,Electrical and Systems Engineering
[2] University of Pennsylvania,Operations and Information Management, The Wharton School
[3] University of Massachusetts Amherst,Mechanical and Industrial Engineering
来源：
Computational Optimization and Applications | 2008年 / 40卷
关键词：
Combinatorial optimization; Branch-and-bound; Quadratic assignment problem; Reformulation linearization technique; Lagrangean dual; Dual ascent procedure;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
相关论文
共 84 条
[1]  
Adams W.P.(1986)A tight linearization and an algorithm for zero-one quadratic programming problems Manag. Sci. 32 1274-1290
[2]  
Sherali H.D.(1990)Linearization strategies for a class of zero-one mixed integer programming problems Oper. Res. 38 217-226
[3]  
Adams W.P.(2007)A level-2 reformulation-linearization technique bound for the quadratic assignment problem Eur. J. Oper. Res. 180 983-996
[4]  
Sherali H.D.(2001)A new bound for the quadratic assignment problem based on convex quadratic programming Math. Program. 89 341-357
[5]  
Adams W.P.(1983)A property of assignment type mixed integer linear programming problems Oper. Res. Lett. 2 47-52
[6]  
Guignard M.(1995)An algorithm for finding the k-best allocations of a tree structured program J. Parallel Distrib. Comput. 26 225-232
[7]  
Hahn P.M.(2001)Best reduction of the quadratic semi-assignment problem Discrete Appl. Math. (DAM) 109 197-213
[8]  
Hightower W.L.(2006)Solving lift-and-project relaxations of binary integer programs SIAM J. Optim. 16 726-750
[9]  
Anstreicher K.M.(2006)A memetic heuristic for the generalized quadratic assignment problem INFORMS J. Comput. 19 433-443
[10]  
Brixius N.W.(2001)A tabu search heuristic for the generalized assignment problem Eur. J. Oper. Res. 132 22-38
123456789