Título: O problema da k-floresta com máximo número de folhas

Data: 23/11/2018

Horário: 13:00h

Local: Sala de Seminários - Bloco 952

Resumo:

Dado um grafo simples conexo e um inteiro positivo k, o problema da k-floresta com máximo número de folhas consiste em encontrar uma floresta geradora com tantas folhas quanto possível e não mais que k componentes. Propomos os primeiros modelos matemáticos para o problema bem como desigualdades válidas. Para k = 1 temos o conhecido problema da árvore geradora com máximo número de folhas (MLSTP). Em particular, para esse problema, as novas desigualdades se mostraram muito eficientes. Dois dos modelos propostos neste documento generalizam formulações encontradas na literatura para o MLSTP e têm como base formulações que descrevem os poliedros de árvores e arborescências geradoras. Apresentamos também caracterizações para o problema, que facilitam expressá-lo de uma maneira alternativa, onde buscamos um conjunto de folhas que gere uma solução ótima e, uma vez que dispomos de tal conjunto, podemos obter uma solução completa para o problema em tempo polinomial. Como consequência, propomos um modelo denominado (MB) o qual resolvemos utilizando um método iterativo de decomposição de Benders para k = 1 e um modelo (MFA) utilizando fluxo em rede para o caso geral. Realizamos experimentos computacionais e analisamos os desempenhos dos modelos. Em particular, para k = 1, comparamos os resultados obtidos tendo como referência formulações da literatura para o MLSTP. Damos destaque ao modelo (MFA) por sua simplicidade de implementação e por não demandar técnicas sofisticadas de corte ou separação. Além disso, para k = 1, esse modelo foi o único a encontrar soluções ótimas para todo o conjunto de instâncias, mostrando-se superior aos modelos específicos para o MLSTP presentes na literatura. Também vale ressaltar que, ainda para k = 1, o modelo (MB) mostrou-se consideravelmente mais eficiente que os demais quando consideramos um subconjunto de instâncias que apresentam maiores densidades de arestas.

Banca:

• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC - Orientador)
• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)
• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC)