Algoritmos para a versão Prize-Collecting do Problema da Árvore de Steiner

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Pôster
  • Eixo temático: 14. OC – Otimização Combinatória
  • Palavras chaves: Prize-Collecting; Problema da Árvore de Steiner; Arredondamento de Programação Linear;
  • 1 Universidade Federal de São Carlos
  • 2 Universidade Federal de Itajubá

Algoritmos para a versão Prize-Collecting do Problema da Árvore de Steiner

Roger Junior

Universidade Federal de São Carlos

Resumo

No problema da árvore de Steiner 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 minimiza o custo das arestas somado com as penalidades dos vértices não atendidos.

O PST é relevante na medida que é capaz de modelar, com mais precisão que a versão clássica do problema de Steiner, diversos problemas reais, como aqueles em projeto de redes de fibra ótica, 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 não ser que P = NP. Para contornar essa dificuldade, podemos usar algoritmos de aproximação.

Nesse trabalho implementamos algoritmos que utilizam arredondamento de programação linear para transformar uma instância do PST em uma instância do problema de Steiner tradicional. Feito isso, é possível aplicar algoritmos clássicos para o problema de Steiner, como o baseado em Árvore Geradora Mínima e o algoritmo Primal Dual, e então converter essa solução para uma solução do PST.

Para realizar o arredondamento diversas abordagens foram implementadas, uma determinística, uma probabilística com limitante fixo e uma probabilística com múltiplos limitantes. Dessas as duas primeiras levam a soluções com garantia de aproximação, enquanto a última é uma proposta nova que apesar de não apresentar garantia de qualidade no pior caso possui bons resultados empíricos.

Os algoritmos foram implementados em linguagem Python usando como resolvedor de programação linear o Gurobi v9.0.2. Todas as combinações de estratégias de arredondamento e algoritmos para o problema de Steiner foram testados em instâncias adaptadas da literatura, dessa forma foi possível comparar o desempenho de cada uma dessas combinações.

Questões (1 tópico)

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Mário César San Felice

Autor
Obrigado pelo feedback :). Concordamos com a necessidade de mais testes. Essa ausência se deveu a restrições de tempo agravadas por algumas dificuldades no desenvolvimento.