Título: Modelos e desigualdades válidas para o Problema da Árvore-Estrela.

Data: 26/07/2017 Horário: 11:00h Local: Sala de Seminários - Bloco 952 - Pici

Resumo:

Considere um grafo G=(V,E) com conjunto de vértices V e um conjunto de arestas E. Seja T = (V_T, E_T), com V_T = V e E_T subconjunto de E, uma árvore geradora de G. Para cada aresta e de E, existe um custo de roteamento c^R_{e}, se e conecta dois vértices internos de T; ou um custo de acesso c^A_{e}, caso contrário. O problema da árvore-estrela de custo mínimo consiste em determinar uma árvore geradora de $G$ cuja soma dos custos de acesso e roteamento seja mínima. Apresentamos novas formulações e desigualdades válidas para esse problema, assim como um procedimento de plano de cortes (PC). Realizamos experimentos computacionais para os modelos existentes e os novos propostos. Nosso procedimento de plano de cortes permite resolver instâncias de tamanho médio de até 80 vértices. Já instâncias com 85 vértices ou mais, nosso (PC)  obtém os menores gaps entre todas as abordagens. Resultados preliminares são promissores e indicam que os dois novos modelos apresentam melhor performance que os existentes na literatura para o problema.

Banca:

• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC) - Orientador
• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC)
• Prof. Dr. Christophe Duhamel (UBP)
• Prof. Dr.ª Andréa Cynthia Santos Duhamel (UTT)