1. Uma revisão comentada das abordagens do problema quadrático de alocação
- Author
-
Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura Netto, and Eliane Maria Loiola
- Subjects
Mathematical optimization ,Optimization problem ,formulations ,otimização combinatória ,Quadratic assignment problem ,lcsh:Mathematics ,Cross-entropy method ,Management Science and Operations Research ,lcsh:QA1-939 ,problema quadrático de alocação ,quadratic assignment problem ,formulações ,Combinatorial optimization ,combinatorial optimization ,Bottleneck traveling salesman problem ,Assignment problem ,Generalized assignment problem ,Combinatorial data analysis ,Mathematics - Abstract
O Problema Quadrático de Alocação, PQA, um dos mais difíceis da classe NP-hard, modela diversas aplicações em diferentes áreas como pesquisa operacional, computação paralela e análise estatística de dados discretos. Além disso, problemas conhecidos como o do caixeiro viajante, o da clique maximal, o de particionamento e o de isomorfismo de grafos podem ser formulados como um PQA. Na tentativa de identificar novas propriedades estruturais para este problema, diversas formulações aparecem na literatura. Reunimos tais formulações, destacando suas principais características para classificá-las segundo as técnicas matemáticas nelas adotadas. Finalizamos o artigo avaliando a extensão das contribuições dadas ao problema, quer na elaboração de algoritmos, quer no cálculo de limites inferiores ou na caracterização de classes de exemplares polinomiais ou não, oriundas das diferentes abordagens aqui estudadas. 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.
- Published
- 2004