Título: Problema da Floresta Geradora k-Rotulada

Horário: 15:00h

Data: 10/02/2020

Local: Bloco 952 - Sala de Seminários

Resumo:

Neste trabalho, estudamos o problema da Floresta Geradora k-Rotulada. Dentre os problema em grafos coloridos em arestas, neste temos como objetivo encontrar um subgrafo gerador que seja uma floresta com a menor quantidade de componentes e com um fator limitante inteiro positivo k para o número de rótulos distintos usados. O problema é NP-Dificil, por ser generalização do problema da Árvore Geradora Minimamente Rotulada, e a maioria dos métodos propostos pela literatura são metaheurísticas. Estudamos características do problema e relacionamos com a literatura pertinente em grafos coloridos para propor três modelos matemáticos de programação inteira mista binária e inteira binária. Propomos métodos Branch & Cut para resolver o problema de forma exata, usando algoritmos para separação de Cortes Coloridos. Além disso, propomos uma paralelização para único método exato disponível na literatura, que aplica um procedimento backtracking. Apresentamos experimentos computacionais preliminares com os modelos e o método backtracking, usando instâncias de teste sugeridas na literatura. Aplicamos melhorias nos métodos de resolução, explorando desigualdades válidas como cortes, regras de branching, poda e limites. Além disso, aplicamos a decomposição de Benders a um dos modelos propostos. Para avaliar tais abordagens, testes adicionais são então realizados em instâncias com maior variação de densidade de arestas. A partir daí, são discutidas as melhores configurações encontradas para os modelos e Cplex.

Banca:

• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC)
• Prof. Dr. Lucídio dos Anjos Formiga Cabral (UFPB)
• Prof. Dr. Marcos José Negreiros Gomes (UECE)