Article ID: | iaor20084738 |
Country: | Brazil |
Volume: | 24 |
Issue: | 1 |
Start Page Number: | 73 |
End Page Number: | 109 |
Publication Date: | Jan 2004 |
Journal: | Pesquisa Operacional |
Authors: | Netto Paulo Oswaldo Boaventura, Loiola Eliane Maria, Abreu Nair Maria Maia de |
Keywords: | optimization |
The Quadratic Assignment Problem, QAP, one of the most difficult problems in NP-hard class, models many applications in several areas such as operational research, parallel and distributed computing, and combinatorial data analysis. Besides, other optimization combinatorial problems such as the traveling salesman problem, maximal clique, isomorphism and graph partitioning can be formulated as a QAP. In this paper, we survey some of the most important formulations available, in order to classify them according to their mathematical resources. Finally, we analyze the extension of the contributions brought by the studies of different approaches.