Article ID: | iaor20023710 |
Country: | United States |
Volume: | 263 |
Issue: | 1/2 |
Start Page Number: | 159 |
End Page Number: | 172 |
Publication Date: | Jul 2001 |
Journal: | Theoretical Computer Science |
Authors: | Zissimopoulos V., Angel E. |
Keywords: | quadratic assignment |
Local-search-based heuristics have been demonstrated to give very good results to 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.