Extensions of a tabu search adaptation to the Quadratic Assignment Problem

The adaptation of tabu search to the Quadratic Assignment Problem (QAP) is refined by incorporating knowledge about permutations yielding good objective function values into the solution process. This knowledge serves two purposes. First, it is used to guide the nonimproving moves toward targeted ‘good’ permutations. Second, it allows the possibility to restrict search in the solution space by fixing those parts of permutations that are common in good quality solutions. Fixing and freeing parts of permutations provides an interplay between intensification and diversification of search. Restricting the search neighborhood becomes essential in solution attempts for QAPs of larger dimensions due to the increase in computational time. Computational results for QAPs of dimension 100 are very promising. An implementation of the approach to dynamic tabu list sizes that creates ‘moving gaps’ in the tabu list is also described. Combining these ingredients, the method obtains very good results for all Skorin-Kapov’s problems of dimensions 42-90.