Defesa de Dissertação: Gabriel Hellen de Sousa

Ter, 27 de Abril de 2021 00:00 | Escrito por Secretaria MDCC | Imprimir

Título: Problema da Árvore t-Spanner de Custo Mínimo
Data: 29/04/2021
Horário: 09:30
Local: Videoconferência
Resumo:

No Problema da Árvore t-Spanner de Custo Mínimo, cuja entrada é uma tripla (G,w,t), onde G=(V,E) é um grafo simples, w:E→R+ é uma função de ponderação das arestas e t≥1 é um parâmetro, denominado de fator de dilatação, o objetivo consiste em determinar uma árvore geradora T em G de menor custo, tal que a distância entre qualquer par de vértices i e j na árvore T é no máximo t vezes a distância entre i e j em G. Apresentamos a definição formal do problema, um contexto de aplicação, complexidade e trabalhos relacionados na literatura. Concentramo-nos em métodos de programação matemática para sua resolução. Propomos um algoritmo enumerativo baseado em um procedimento de Branch-and-Bound. Além disso, apresentamos quatro formulações matemáticas para o problema, uma exponencial e três compactas. Vale ressaltar que dentre as formulações compactas, duas são as únicas presentes na literatura do problema. As demais formulações estamos propondo neste trabalho. Ainda com relação às formulações, propomos desigualdades válidas com potencial de fortalecer a
relaxação linear dos modelos. As implementações das formulações e do algoritmo enumerativo foram realizadas em C++, com o uso do solver CPLEX, para resolução das formulações. Descrevemos como geramos os grafos (instâncias) que serão utilizados para os testes computacionais e ao final apresentamos as conclusões do trabalho.

Banca examinadora:
  • Prof. Dr. Manoel Bezerra Campêlo Neto (Orientador - MDCC/UFC)
  • Prof. Dr. Rafael Castro de Andrade (MDCC/UFC)
  • Prof. Dr. Phablo Fernando Soares Moura (UFMG)

Última atualização (Ter, 27 de Abril de 2021 12:13)