Defesa de Dissertação de Mestrado: André Willik Valenti
Document Actions
Defesa de Dissertação de Mestrado: Andrei de Almeida Sampaio Braga
Relaxações Lagrangeanas e Planos de Corte Faciais na resolução de Problemas de Particionamento de Conjuntos.
| What | Defesa de Mestrado |
|---|---|
| When |
02/09/2011 from 14:00 to 16:00 |
| Where | Auditório do IC - Sala 85 - IC 2 |
| Add event to calendar |
vCal
iCal
|
O problema de particionamento de conjuntos (SPP, do inglês set partitioning problem) é considerado um dos problemas de otimização combinatória com mais vasta gama de aplicações. Para solucioná-lo, utilizam-se comumente métodos tradicionais para a resolução de problemas NP-Difíceis. Nesta dissertação, estuda-se o uso da combinação de relaxação Lagrangeana com planos de corte.
Relaxação Lagrangeana é uma técnica que tem sido usada com bastante sucesso para atacar vários problemas NP-Difíceis. Os algoritmos relax-and-cut, em especial, onde se adicionam dinamicamente planos de corte a relaxações Lagrangeanas, têm ganhado bastante destaque nas últimas décadas. Em [1], Cavalcante et al. aplicam um algoritmo relax-and-cut ao SPP e obtêm ótimos resultados. No entanto, tal algoritmo, bem como implementações em geral da citada combinação, são ainda passíveis de refinamentos e extensões. O estudo proposto aqui é realizado por meio das seguintes extensões do referido algoritmo: a implementação de uma partida quente para o multiplicador de uma inequação adicionada; a incorporação do algoritmo a uma enumeração, gerando, assim, um branch-and-cut baseado em relaxação Lagrangeana para o SPP; a implementação do citado branch-and-cut com o emprego de relaxações alternativas e a implementação de uma versão distribuída do algoritmo.
[1] V. Cavalcante, C. de Souza, and A. Lucena. A Relax-and-Cut algorithm for the set partitioning problem. Computers & Operations Research, 35(6):1963–1981, 2008.
Concurso Público para Professor Doutor - MS-3
