Algoritmos para o problema da árvore geradora mínima probabilística
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Simone de Lima Martins
Geraldo Robson Mateus
Mauricio Cardoso de Souza
Geraldo Robson Mateus
Mauricio Cardoso de Souza
Resumo
O Problema da Árvore Geradora Mínima Probabilística é uma generalização do problema clássico da Árvore Geradora Mínima em que se considera a situação na qual nem todos os nós estão deterministicamente presentes, mas estão presentes conforme uma determinada probabilidade. Dado um grafo, G=(V,E), que possui um custo associado a cada aresta em E e uma probabilidade de cada vértice em V estar ativo, pretende-se construir uma árvore geradora T em G a priori, tal que o custo ativo esperado de T seja mínimo. Este problema, provado como NP-Difícil em seu caso geral, possui aplicações em diversas áreas como roteamento, desenho de circuitos integrados, logística e telecomunicações. Nesta dissertação, a versão homogênea do problema, situação em que todos os nós têm a mesma probabilidade de estarem ativos, é descrita, analisada e resolvida através de heurísticas e algoritmos de busca local. Apresentam-se heurísticas construtivas capazes de encontrar soluções viáveis para o problema e, a partir de uma técnica que avalia os custos de soluções vizinhas de maneira eficiente, propõe-se a incorporação de algoritmos de busca local a um algoritmo de Busca Tabu - capaz de gerar soluções de melhor qualidade para o problema. Propõe-se também uma modelagem que permite a resolução do problema por Programação Inteira. A análise dos resultados revela que os algoritmos, quando comparados à resolução do modelo exato, mostraram ser uma ferramenta bastante eficiente para lidar com um problema computacionalmente difícil.
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.
Assunto
Otimização combinatória, Programação linear, Teoria dos grafos
Palavras-chave
Programação Inteira, PMST, Árvore Geradora Mínima, Heurísticas