Article,
A survey for the quadratic assignment problem
European Journal of Operational Research, (2007)
Abstract
The quadratic assignment problem (QAP), one of the most di?cult problems
in the NP-hard class, models many real-life problems in several areas
such as facilities location, parallel and distributed computing,
and combinatorial data analysis. Combinatorial optimization problems,
such as the traveling salesman problem, maximal clique and graph
partitioning can be formulated as a QAP. In this paper, we present
some of the most important QAP formulations and classify them according
to their mathematical sources. We also present a discussion on the
theoretical resources used to de?ne lower bounds for exact and heuristic
algorithms. We then give a detailed discussion of the progress made
in both exact and heuristic solution methods, including those formulated
according to metaheuristic strategies. Finally, we analyze the contributions
brought about by the study of di?erent approaches.
