Problema da árvore t-spanner de custo mínimo

Abstract

In the Minimum Weight t-Spanner Tree Problem, whose input is a triplet (G,w,t), where G = (V,E) is a simple graph, w : E → R+ is an edge weighting function and t ≥ 1 is a parameter, called the dilatation factor, the objective consists in determining a spanning tree T in G of minimum weight, such that the distance between any pair of vertices i and j in tree T is at most t times the distance between i and j in G. Starting from the formal definition of the problem, we present an application context, the problem complexity and related works in the literature. We focus on mathematical programming methods for its resolution. We propose an enumerative algorithm based on a branch-and-bound procedure. We present and study an exponential and three compact integer linear programming formulations for the problem. Two of the compact formulations are the only ones present in the problem literature. We propose valid inequalities with the potential to strengthen the linear relaxation of the models. We implement and computatuionally evaluate the formulations, the valid inequalities, and the enumerative algorithm using C++ Language and CPLEX solver. We report on the computational results obtained by each method, and we identify the one that presents the best performance for each group of instances.