Informatica

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.