NOVA FORMULAÇÃO E DESIGUALDADES VÁLIDAS PARA O PROBLEMA DA ÁRVORE t-SPANNER DE CUSTO MÍNIMO

No Problema da Árvore $t$-Spanner de Custo Mínimo, cuja entrada é uma tripla $(G,w,t)$, onde $G=(V,E)$ é um grafo simples, $w:E\rightarrow\mathbb{R}^{+}$ é uma função de ponderação das arestas e $t\geq 1$ é um parâmetro, denominado de fator de dilatação, o objetivo consiste em determinar uma árvore geradora $T$ em $G$ de menor custo, tal que a distância entre qualquer par de vértices $i$ e $j$ na árvore $T$ é no máximo $t$ vezes a distância entre $i$ e $j$ em $G$. Determinar uma árvore $t$-spanner de custo mínimo é um problema NP-Difícil mesmo no caso de pesos unitários. Neste trabalho, propomos uma formulação matemática e um conjunto de desigualdades válidas. Implementamos a formulação e comparamos seu desempenho com a formulação mais eficiente da literatura. Analisamos também o efeito da adição das desigualdades válidas na performance do melhor modelo.