02 mai 2024
14:00 Defesa de Mestrado Sala 53 do IC2
Tema
Métodos Exatos e Heurísticos para o Problema do Subgrafo de Diâmetro Mínimo
Aluno
Arthur Pratti Dadalto
Orientador / Docente
Fábio Luiz Usberti - Coorientador: Mário César San Felice
Breve resumo
Esta dissertação aborda o Problema do Subgrafo de Diâmetro Mínimo (MSDP), um problema de otimização combinatória NP-difícil com aplicações em design de redes. Dado um grafo não direcionado com comprimentos e custos nas arestas, o objetivo do MSDP é encontrar um subgrafo gerador com custo total limitado por um orçamento especificado, de forma que o diâmetro do subgrafo seja mínimo. São propostas metodologias exatas e heurísticas para o MSDP, e um benchmark de instâncias foi projetado para avaliar as metodologias em um extenso estudo computacional.
Na abordagem exata, é proposta uma formulação de Programação Linear Inteira Mista (MILP) para o MSDP, com duas famílias de desigualdades válidas generalizando desigualdades de cobertura e corte, que formam a base das primeiras abordagens exatas para o MSDP. Estas são complementadas por uma abordagem para aplicar “lazy constraints” no MILP e uma heurística para gerar limitantes superiores a partir de soluções fracionárias. Os resultados do benchmark mostram a eficácia de cada contribuição para reduzir os gaps de otimalidade e os tempos de computação.
Na abordagem heurística, é apresentada uma abordagem metaheurística para o MSDP usando um Algoritmo Genético de Chaves Aleatórias Enviesadas (BRKGA), com três decodificadores, cache de computações de diâmetro e soluções de partida. Os resultados do benchmark mostram que os métodos propostos contribuem para reduzir os gaps de otimalidade conhecidos e são melhores que os métodos exatos para instâncias grandes na qualidade das soluções obtidas.
Banca examinadora
Titulares:
| Fábio Luiz Usberti | IC/UNICAMP |
| Pedro Augusto Munari Junior | CCET/UFSCar |
| Maycon Sambinelli | CMCC/UFABC |
Suplentes:
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Petra Maria Bartmeyer | FEEC/UNICAMP |