Algoritmos para o problema da árvore geradora mínima probabilística

Abstract

The Probabilistic Minimum Spanning Tree Problem is a generalization of the classical Minimum Spanning Tree problem, addressing the assumption that arise when not all nodes are deterministically present but, rather, nodes are active with known probabilities. Given a graph, G = (V,E), where there is a cost associated with every edge in E and a probability of each node in V to be active, the objective is to build a sub-tree T in G a priori, where the expected cost of T is minimum. This problem is proved to be NP-Hard in the general case. In this dissertation, the homogeneous case of the problem, when all nodes havethe same probability of being active, is described, analyzed and solved through local search algorithms. A constructive heuristic is proposed in order to find feasible solutions for the problem. Starting through a technique that efficiently evaluates the costs of neighboring solutions, it is proposed the embedding of local search algorithms into a Tabu Search metaheuristic, capable of yielding better quality solutions for the problem.It is also proposed a model that can be solved through Integer Programming. The analysis of the results shows that the algorithms, when compared to the resolution of the exact model, proved to be an efficient tool to deal with a computationally difficult problem.