On the hardness of the quadratic assignment problem with metaheuristics

Meta-heuristics are a powerful way to approximately solve hard combinatorial optimization problems. However, for a problem, the quality of results can vary considerably from one instance to another. Understanding such a behaviour is important from a theoretical point of view, but also has practical applications such as for the generation of instances during the evaluation stage of a heuristic. In this paper we propose a new complexity measure for the Quadratic Assignment Problem in the context of metaheuristics based on local search, e.g. simulated annealing. We show how the ruggedness coefficient previously introduced by the authors, in conjunction with the well known concept of dominance, provides important features of the search space explored during a local search algorithm, and gives a rather precise idea of the complexity of an instance for these heuristics. We comment on previous experimental studies concerning tabu search methods and genetic algorithms with local search in the light of our complexity measure. New computational results with simulated annealing and tabu search are presented.