Sobre o problema de caminhos tropicais em grafos: formulação, heurística e resultados experimentais

• Ano de defesa: 2023
• Autor(a) principal: Sampaio, Igor de Moraes
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Caminho tropical; Coloração de grafos; Graph coloring; Heurística; Heuristics; Integer linear programming; Programação linear inteira; Tropical path
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/100/100131/tde-19062023-083841/

Neste trabalho, estudamos o problema do caminho tropical máximo em grafos, MTPP. Um caminho em um grafo colorido nos vértices é dito ser tropical se os vértices do caminho possuem as cores usadas pela coloração dos vértices grafo. Para o problema MTPP é dado um grafo e uma coloração de seus vértices, e o objetivo é encontrar um caminho cuja coloração use o maior número possível de cores desta coloração. A motivação para estudar o MTPP surge da constatação de que, até o início desta pesquisa, não havia na literatura abordagens baseadas em modelos de programação linear inteira, nem algoritmos heurísticos para o problema de interesse. Sabe-se que o MTPP é NP-difícil para grafos em geral, grafos direcionados acíclicos, grafos cacto e grafos de intervalo. Nesta pesquisa, foi desenvolvida uma modelagem para o problema MTPP como um problema de programação linear inteira para grafos simples e uma simplificação do modelo proposto para DAGs também é apresentada. Uma formulação similar é apresentada para uma segunda versão de otimização do problema em que o objetivo é encontrar um caminho tropical cuja soma dos pesos das arestas seja o menor possível. A contribuição principal desta pesquisa consiste na construção de uma heurística de tempo polinomial para o MTPP que juntamente com o modelo de PLI foi possível avaliar o desempenho de ambos por meio de experimentos computacionais em instâncias aleatórias e reais.