A survey for the quadratic assignment problem

作者：Loiola Eliane Maria; de Abreu Nair Maria Maia; Boaventura Netto Paulo Oswaldo; Hahn Peter^*; Querido Tania

来源：European Journal of Operational Research, 2007, 176(2): 657-690.

DOI：10.1016/j.ejor.2005.09.032

• assignment
• integer programming
• combinatorial optimization
• facilities planning and design
• metaheuristics
• branch and bound

The quadratic assignment problem (QAP), one of the most difficult 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 define 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 different approaches.

• 出版日期2007-1-16