A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem.
Yong Li, Pãnos M. Pardalos, Maurício G. C. Resende · 1993
. A greedy randomized adaptive search procedure (GRASP) is a randomized heuristic that has been shown to quickly produce good quality solutions for a wide variety of combinatorial optimization problems. In this paper, we describe a GRASP for the quadratic assignment problem. We review basic concepts of GRASP: construction and local search algorithms. The implementation of GRASP for the quadratic assignment problem is described in detail. Computational experience on a large set of standard test problems (QAPLIB) is presented. Key words. Combinatorial optimization, quadratic assignment problem, local search, PLScomplete, GRASP, computer implementation, graph partitioning AMS(MOS) subject classifications. 90B80, 90C20, 90C35, 90C27, 65H20, 65K05 1. Introduction. Given a set N = f1; 2; : : :; ng and n \\Theta n matrices F = (f ij ) and D = (d kl ), the quadratic assignment problem (QAP) can be stated as follows: min p2\\Pi N n X i=1 n X j=1 f ij d p(i)p(j); where \\Pi N is the set o...