Busca avançada
Ano de início
Entree

Problemas de florestas geradoras ótimas restritas em grafos

Processo: 08/01497-8
Linha de fomento:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de junho de 2008
Vigência (Término): 31 de maio de 2010
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação
Pesquisador responsável:Cid Carvalho de Souza
Beneficiário:Luidi Gelabert Simonetti
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Otimização combinatória   Programação linear inteira   Combinatória poliédrica

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)