On the landscape ruggedness of the quadratic assignment problem

Local-search-based heuristics have been demonstrated to give very good resu lts to approximately solve the quadratic assignment problem (QAP). In this paper, following the works of Weinberger and Stadler, we introduce a parame ter, called the ruggedness coefficient, which measures the ruggedness of th e 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, a nd so it gives a theoretical justification of the effectiveness of local-se arch-based heuristics for this problem. Experimental results with simulated annealing are presented which confirm this conclusion and also the influen ce of the ruggedness coefficient on the quality of results obtained. (C) 20 01 Published by Elsevier Science B.V.