Uma revisão comentada das abordagens do problema quadrático de alocação

Pesquisa Operacional

Eliane Maria Loiola¹  Nair Maria Maia De Abreu¹  Paulo Oswaldo Boaventura Netto¹ 

[1] ,Universidade Federal do Rio de Janeiro Coordenação dos Programas de Pós-graduação de Engenharia Programa de Engenharia de ProduçãoRio de Janeiro RJ

关键词: problema quadrático de alocação;    formulações;    otimização combinatória;    quadratic assignment problem;    formulations;    combinatorial optimization;   

DOI  :  10.1590/S0101-74382004000100005

来源: SciELO

【 摘 要 】

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.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License