On the landscape ruggedness of the Quadratic Assignment Problem

Local search based heuristics have been demonstrated to give very good results for approximately solve the Quadratic Assignment Problem (QAP). In this paper, following the works of Weinberger and Stadler, we introduce a parameter, called the ruggedness coefficient, which measures the ruggedness of the QAP landscape which is the union of a cost function and a neighborhood. We give an exact expression, and a sharp lower bound for this parameter. We are able to derive from it that the landscape of the QAP is rather flat, and so it gives a theoretical justification of the effectiveness of local search based heuristics for this problem. Experimental results with simulated annealing are presented which confirm this conclusion and also the influence of the ruggedness coefficient on the quality of results obtained. Keywords- Quadratic Assignment Problem, local search. 1 Introduction Given two n \Theta n matrices F = (f ij ) and D = (d ij ), the Quadratic Assignment Problem (QAP) asks to find..