This paper was published through Galoá and has a deposited DOI. To cite this paper, use one of the standards below:
In case you are one of the co-authors and want to register this paper in your Lattes, use the following code: doi > 10.59254/sbpo-2020-122888
If you've NEVER registered a DOI in your Lattes, check our tutorial!Algoritmos para a versão Prize-Collecting do Problema da Árvore de Steiner
Roger Junior
Universidade Federal de São Carlos
Now you could share with me your questions, observations and congratulations
Create a topicNo 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.
Thiago Gouveia da Silva
Antes de mais nada, gostaria de parabenizar os autores. Gostei bastante do trabalho.
Acredito que, como falado no final da apresentação, é bem importante testar com um número bem maior de instâncias, assim como fazer testes com benchmarks já utilizados na literatura.
With nearly 200,000 papers published, Galoá empowers scholars to share and discover cutting-edge research through our streamlined and accessible academic publishing platform.
Learn more about our products:
This proceedings is identified by a DOI , for use in citations or bibliographic references. Attention: this is not a DOI for the paper and as such cannot be used in Lattes to identify a particular work.
Check the link "How to cite" in the paper's page, to see how to properly cite the paper
Mário César San Felice
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.