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 条
[31]  
Jaikumar R.(1990)A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems SIAM J. Discrete Math. 3 411-430
[32]  
Van Wassenhove L.N.(1994)A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems Discrete Appl. Math. 52 83-106
[33]  
Guignard M.(1992)Simulated annealing applied to the process allocation problem Eur. J. Oper. Res. 60 327-334
[34]  
Rosenwein M.(1992)The process allocation problem: a survey of the application of graph-theoretic and integer programming approaches J. Oper. Res. Soc. 43 407-413
[35]  
Hahn P.M.(1998)A variable depth search algorithm with branching search for the generalized assignment problem Optim. Methods Softw. 10 419-441
[36]  
Grant T.L.(undefined)undefined undefined undefined undefined-undefined
[37]  
Hahn P.M.(undefined)undefined undefined undefined undefined-undefined
[38]  
Krarup J.(undefined)undefined undefined undefined undefined-undefined
[39]  
Hahn P.M.(undefined)undefined undefined undefined undefined-undefined
[40]  
Grant T.L.(undefined)undefined undefined undefined undefined-undefined
123456789