Algoritmos Exatos e Heurísticos para o Problema da Diversidade Máxima
Autores
|
6467 |
2925,519
|
|
|
6468 |
2925,519
|
Informações:
Publicações do PESC
Neste trabalho, propomos algoritmos Branch-and-Cut e heurísticas Lagrangeanas para o Problema da Máxima Diversidade. Utilizamos uma formulação linear padrão fortalecida por desigualdades válidas para o problema. Estas são dualizadas dinamicamente nas heurísticas e utilizadas como cortes nos algoritmos exatos. Para tanto, propomos alguns procedimentos heurísticos para separá-las de maneira eficiente. Adicionalmente, realizamos testes computacionais e comparamos nossos algoritmos exatos e heurísticos com aqueles existentes na literatura para o problema.
In this work, we suggest Branch-and-Cut algorithms and Lagrangian heuristics for the Maximum Diversity Problem. We use a standard formulation reinforced by some valid inequalities for the problem. These are dynamically dualized in the heuristics and used as cuts in the exact methods. To separate them eficiently, we propose some heuristic procedures. In addition, we perform computational tests and compare our exact and heuristics methods with those found in the literature for the problem.