Journal article
Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique
Production Engineering Department, Universidade Federal Fluminense, Brazil1
Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104-6314, USA2
Operations and Information Management, The Wharton School, University of Pennsylvania, Philadelphia, PA 19104-6340, USA3
Elder Research, Inc., 300 West Main Street, STE 301, Charlottesville, VA 22903-5575, USA4
In this paper, we propose two exact algorithms for the GQAP (generalized quadratic assignment problem). In this problem, given M facilities and N locations, the facility space requirements, the location available space, the facility installation costs, the flows between facilities, and the distance costs between locations, one must assign each facility to exactly one location so that each location has sufficient space for all facilities assigned to it and the sum of the products of the facility flows by the corresponding distance costs plus the sum of the installation costs is minimized.
This problem generalizes the well-known quadratic assignment problem (QAP). Both exact algorithms combine a previously proposed branch-and-bound scheme with a new Lagrangean relaxation procedure over a known RLT (Reformulation-Linearization Technique) formulation. We also apply transformational lower bounding techniques to improve the performance of the new procedure.
We report detailed experimental results where 19 out of 21 instances with up to 35 facilities are solved in up to a few days of running time. Six of these instances were open.
Language: | English |
---|---|
Year: | 2010 |
Pages: | 54-63 |
ISSN: | 18726860 and 03772217 |
Types: | Journal article |
DOI: | 10.1016/j.ejor.2010.02.006 |