Problemas de florestas geradoras ótimas restritas em grafos

Resumo

Este documento apresenta o projeto de pesquisa a ser desenvolvido pelo Dr. Luidi Simonetti sob a supervisão do Professor Cid C. de Souza, do Instituto de Computação da UNICAMP. O objetivo é estudar problemas de Otimização Combinatória relacionados a florestas geradoras em grafos e algumas de suas aplicações práticas. Em particular, a investigação se concentrará nos Problemas da Árvore Caterpillar Mínima (PACM) e da Floresta Geradora ótima com restrição de forma (PFG) e na utilização de técnicas de Programação Linear Inteira para resolvê-los. O PACM procura encontrar a árvore caterpillar geradora com custo mínimo, sendo este dado pela soma do custo individual de suas arestas. As árvores caterpillar são formadas por um único caminho ao qual estão penduradas todas as folhas da árvore. O PACM aparece como um subproblema de alguns problemas de roteamento. Já no PFG as soluções viáveis são florestas geradoras, com pelo menos uma restrição de forma, por exemplo, um limite no grau máximo de um vértice na floresta ou no diâmetro das árvores que a compõem. O problema requer que seja encontrada uma solução viável com custo mínimo, o qual é dado pela soma dos custos das arestas presentes na floresta. Aplicações do PFG são encontradas, por exemplo, no projeto de redes de telecomunicações. Portanto, este projeto terá por foco: (i) investigações teóricas sobre modelagem matemática e a estrutura facial dos politopos dos PACM e PFG, e (ii) o desenvolvimento de algoritmos exatos para a resolução de instâncias destes problemas. (AU)