Problema de Steiner com restrições de hop

• Processo: 11/15839-0
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2012
• Data de Término da vigência: 31 de julho de 2012
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Alysson Machado Costa
• Beneficiário: Murilo Soares Pinheiro
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Programação linear inteira
• Palavra(s)-Chave do Pesquisador: Problema de Steiner | programação linear inteira | Restrições de hop | Teoria poliedral | Programação inteira

Resumo

Este projeto se interessa pelo problema de Steiner em árvores com restrições de hop (HSTP, da sigla em inglês, hop-constrained Steiner tree problem), uma generalização do problema de Steiner que limita o número de arestas entre um nó denominado raiz e qualquer outro nó da árvore solução. O HSTP tem interesses teórico e prático pois, se por um lado, configura-se como um problema de alta complexidade de resolução devido ao seu caráter combinatório, por outro, modela de maneira adequada diversas situações reais. Nos propomos a analisar e propor formulações gerais que modelam as restrições de hop, além de estudar a estrutura poliedral do problema.