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.

In this work, we studied the problem of maximum tropical path in graphs, MTPP. A path in a vertex-colored graph is said to be tropical if the vertices of the path have the colors used in the vertex coloring of the graph. For the MTPP problem, a graph and a coloring of its vertices are given, and the goal is to find a path whose coloring uses the largest possible number of colors from this coloring. The motivation for studying MTPP arises from the observation that, until the beginning of this research, there were no approaches based on integer linear programming models or heuristic algorithms for the problem of interest in the literature. It is known that MTPP is NP-hard for general graphs, directed acyclic graphs, cactus graphs, and interval graphs. In this research, a modeling for the MTPP problem as an integer linear programming problem for simple graphs was developed, and a simplification of the proposed model for DAGs is also presented. A similar formulation is presented for a second optimization version of the problem, in which the objective is to find a tropical path whose sum of edge weights is as small as possible. The main contribution of this research consists of constructing a polynomial-time heuristic for MTPP, which, together with the ILP model, made it possible to evaluate the performance of both through computational experiments on random and real instances.