Título: Contribuições para o problema do caminho mínimo k-colorido

Data: 31/05/2023

Horário: 13h00

Local: Online

Resumo:

Dado um digrafo D = (V, A), onde todos os arcos (i, j) em A possuem um custo d_{ij} real positivo e uma cor c(i, j), um inteiro positivo k, e vértices s e t em V, o Problema do Caminho Mínimo k-Rotulado consiste em encontrar um caminho de s para t em D de custo mínimo usando no máximo k cores de arcos distintas. Propomos desigualdades válidas para o problema que provaram fortalecer a relaxação linear de uma formulação existente na literatura de Programação Linear Inteira. Um conjunto exponencial de desigualdades válidas definem uma nova formulação para o problema, os quais são resolvidas utilizando um algoritmo de branch-and-cut. Introduzimos instâncias mais desafiadoras para o problema e apresentamos experimentos numéricos para as benchmark e as novas instâncias. Finalmente, nós avaliamos o uso individual e coletivo das desigualdades válidas. Resultados computacionais para as ideias propostas e para as abordagens existentes para o problema mostram a eficiência das novas desigualdades em lidar com as novas instâncias ambos em termos de tempo de execução e em proporcionar melhoria nas soluções relaxadas.

Banca examinadora:

• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC - Orientador)
• Prof. Dr. Rommel Dias Saraiva (UNIFOR - Coorientador)
• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)