Abstract
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 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 taboo search are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Angel, E. and V. Zissimopoulos. (1998). “Autocorrelation Coefficient for the Graph Bipartitioning Problem.” Theoretical Computer Science 191, 229–243.
Angel, E. and V. Zissimopoulos. (1998). “On the Quality of Local Search for the Quadratic Assignment Problem.” Discrete Applied Mathematics 82, 15–25.
Angel, E. and V. Zissimopoulos. (2000). “On the Classification of NP-Complete Problems in Terms of their Correlation Coefficient.” Discrete Applied Mathematics 99, 261–277.
Angel, E. and V. Zissimopoulos. (2001). “On the Landscape Ruggedness of the Quadratic Assignment Problem.” Theoretical Computer Science 263(1/2), 159–172.
Bachelet, V., P. Preux, and E-G. Talbi. (1996). “Parallel Hybrid Meta-Heuristics: Application to the Quadratic Assignment Problem.” Technical Report LIL-96-2, LIFL, Université des Sciences et Technologies de Lille.
Bachelet, V., P. Preux, and E-G. Talbi. (1997). “The Landscape of the Quadratic Assignment Problem and Local Search Methods.” In Tenth Meeting of the European Chapter on Combinatorial Optimization. Teneriffe, Canary Islands.
Block, T.E. (1979). “On the Complexity of Facilities Layout Problems.” Management Science 25, 280.
Burkard, R.E. and U. Fincke. (1985). “Probabilistic Asymptotic Properties of Some Combinatorial Optimization Problems.” Discrete Applied Mathematics 12, 21–29.
Burkard, R.E., S.E. Karisch, and F. Rendl. (1997). “QAPLIB—AQuadratic Assignment Problem Library.” Journal of Global Optimization 10, 391–403. See also at http://www.imm.dtu.dk/∼sk/qaplib/.
Connolly, D.T. (1990). “An Improved Annealing Scheme for the QAP.” European Journal of Operational Research 46, 93–100.
Dorigo, M., V. Maniezzo, and A. Colorni. (1995). Algodesk: An Experimental Comparison of Eight Evolutionary Heuristics for the Quadratic Assignment Problem.” European Journal of Operational Research 81, 188–204.
Fonlupt, C., D. Robilliard, P. Preux, and E-G. Talbi. (1997). “Fitness Landscapes and Performance of Meta-Heuristics.” In 2nd International Conference on Metaheuristics. Sophia-Antipolis, France.
Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability—A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.
Herroelen, W. and A. Van Gils. (1985). “On the Use of Flow Dominance in Complexity Measures for Facility Layout Problems.” International Journal of Production Research 23(1), 97–108.
Johnson, D.S., C.R. Aragon, L.A. McGeoch, and C. Schevon. (1989). “Optimization by Simulated Annealing: An Experimental Evaluation; part I, Graph Partitioning.” Operations Research 37(6), 865–892.
Li, Y. and P.M. Pardalos. (1992). “Generating Quadratic Assignment Test Problems with Known Optimal Permutations.” Computational Optimization and Applications 1, 163–184.
Martin O. (1998). “Propriétés des solutions engendrées par des algorithmes heuristiques: la limite de grande taille.” In Premier Congrès de la Société Française de Recherche Opérationnelle et Aide `a la Décision. Paris, Janvier.
Mautor, T. and C. Roucairol. (1993). “Difficulties of Exact Methods for Solving the Quadratic Assignment Problem.” In DIMACS (Series in Discrete Mathematics and Theoretical Computer Science) Workshop, Vol. 16, pp. 263–274.
Merz, P. and B. Freisleben. (1997). “A Genetic Local Search Approach to the Quadratic Assignment Problem.” In Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA'97). East Lansing, USA.
Reidys, C.M. and P.F. Stadler. “Combinatorial Landscapes.” SIAM Review, to appear.
Sahni, S. and T. Gonzalez. (1976). “P-Complete Approximation Problems.” Journal of the ACM 23, 555–565.
Schreiber, G.R. and O. Martin. (1999). “Cut Size Statistics of Graph Bisection Heuristics.” SIAM Journal on Optimization 20(1), 231–251.
Stadler, P.F. (1995). “Landscapes and their Correlations Functions.” Technical Report 95-07-067, Santa Fe Institute, Santa Fe, NM.
Taillard, E.D. (1991). “Robust Taboo Search for the QAP.” Parallel Computing 17, 443–455.
Taillard, E.D. (1995). “Comparison of Iterative Searches for the Quadratic Assignment Problem.” Location Science 3, 87–105.
Taillard, E.D. www.idsia.ch/∼eric.
Vollmann, T.E. and E.S. Buffa. (1966). “The Facilities Layout Problem in Perspective.” Management Science 12(10), 450–468.
Weinberger, E.D. (1990). “Correlated and Uncorrelated Fitness Landscapes and How to Tell the Difference.” Biological Cybernetics 63, 325–336.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Angel, E., Zissimopoulos, V. On the Hardness of the Quadratic Assignment Problem with Metaheuristics. Journal of Heuristics 8, 399–414 (2002). https://doi.org/10.1023/A:1015454612213
Issue Date:
DOI: https://doi.org/10.1023/A:1015454612213