Affiliations: Computer Science Department, The Pennsylvania State University, University Park, PA 16802, USA | 303 Weil Hall, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA
Abstract: In this paper, we present a new local search algorithm for solving the Quadratic Assignment Problem based on the Kernighan-Lin heuristic for the Graph Partitioning Problem. We also prove that finding a local optimum for the Quadratic Assignment Problem, with the neighborhood structure defined in the algorithm, is PLS-complete. The greatest advantages of the algorithm are its simplicity and speed in generating high quality solutions. The algorithm has been implemented and tested on an IBM 3090 computer with a variety of test problems of dimensions up to 100, including many test problems available in the literature and a new set of test problems with known optimal permutations.
Keywords: analysis of algorithms: computational complexity, suboptimal algorithms, facilities/equipment planning: discrete location, combinatorial optimization, graph partitioning, polynomial-time local search
DOI: 10.3233/INF-1992-3405
Journal: Informatica, vol. 3, no. 4, pp. 524-538, 1992
