Métodos Exatos para o Problema da Árvore de Cobertura com Representação Mínima

Neste trabalho abordamos o Problema da Árvore de Cobertura com Representação Mínima (PACRM), um problema relativamente recente na literatura acadêmica. Neste, dado um grafo com arestas rotuladas G=(V, E, L) sendo V o conjunto de vértices, E o conjunto de arestas, L o conjunto de rótulos, e cada aresta e ∈ E possui um rótulo L(e) associado, o objetivo é encontrar uma árvore geradora T=(V, E', L'), tal que E' ⊆ E, L' ⊆ L, e a soma dos rótulos representados em cada vértice seja minimizada. Propomos dois métodos exatos para o problema, um algoritmo de refinamento do grafo de entrada, algoritmos de branch-and-cut e novas desigualdades válidas. Os experimentos computacionais realizados demonstraram que os novos modelos matemáticos encontraram mais soluções ótimas e em menor tempo comparadas ao estado da arte.