Introdução. No problema da Árvore de Steiner (ST) desejamos encontrar uma árvore de custo mínimo, em um grafo não direcionado, que conecta um subconjunto dos vértices, denominados terminais. A versão Prize-Collecting do problema da Árvore de Steiner (PST) é uma generalização do problema clássico, em que ao invés de existirem terminais, cada vértice possui uma penalidade que deve ser paga caso ele não esteja conectado à árvore. Assim, o objetivo é construir uma árvore que minimize o custo das arestas utilizadas somado com as penalidades dos vértices não atendidos. O PST é relevante por modelar diversos cenários reais com mais precisão que o ST, como aqueles em projeto de redes de fibra óptica, telecomunicações, redes de gás e aquecimento. O PST é um problema NP-Difícil, portanto, não há esperança que algoritmos exatos e eficientes sejam encontrados, a menos que P=NP. Para contornar essa dificuldade, podemos usar algoritmos de aproximação.

Objetivo. O objetivo desse projeto é estudar, implementar e comparar diferentes algoritmos de aproximação para o problema da árvore de Steiner e suas variantes, principalmente para a versão Prize-Collecting do problema de Steiner.

Metodologia. Neste trabalho implementamos algoritmos que utilizam arredondamento de programação linear para transformar uma instância do PST em uma instância do ST. Feito isso, é possível aplicar algoritmos clássicos para o ST, como o baseado em Árvore Geradora Mínima (MST) e o algoritmo Primal Dual. Destacamos que, para resolver o programa linear do PST utilizamos algoritmos de corte mínimo, que permitem encontrar restrições de conectividade em tempo de execução. Para realizar o arredondamento diversas abordagens foram implementadas: uma determinística, uma probabilística com limiar fixo e uma probabilística com múltiplos limiares.

Resultados. No total, 12 combinações de algoritmos foram testados para 20 instâncias. A comparação dos algoritmos de corte levou a um resultado inesperado, onde o resolvedor de programação linear se saiu melhor do que algoritmos especializados. No arredondamento de programação linear, o método que propusemos, com múltiplos limiares, obteve resultados melhores em algumas instâncias. Já para resolver a última etapa, o algoritmo Primal Dual superou o algoritmo baseado em MST.

Conclusão. O problema da árvore de Steiner e suas variantes são problemas fundamentais na área de otimização combinatória. Durante o projeto foi possível obter uma boa noção sobre as dificuldades de se resolver problemas NP-Difíceis e como técnicas de aproximação podem contornar essas dificuldades. Além disso, foi possível entender e estudar melhor algumas técnicas de projeto de algoritmos. A despeito de algumas dificuldades de implementação, a análise empírica permitiu obter alguns resultados interessantes.