Este trabalho foi publicado pelo Galoá e tem um DOI depositado. Para citar este trabalho, use um dos padrões abaixo:
Caso você seja um dos co-autores e queira cadastrar esse trabalho no seu Currículo Lattes, use o seguinte código: doi > 10.59254/sbpo-2020-122888
Se você NUNCA registrou um DOI no seu Lattes, veja nosso tutorial!Algoritmos para a versão Prize-Collecting do Problema da Árvore de Steiner
Roger Junior
Universidade Federal de São Carlos
Agora você poderia compartilhar comigo suas dúvidas, observações e parabenizações
Crie um tópicoNo 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.
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Esse proceedings é identificado por um DOI , para usar em citações ou referências bibliográficas. Atenção: este não é um DOI para o jornal e, como tal, não pode ser usado em Lattes para identificar um trabalho específico.
Verifique o link "Como citar" na página do trabalho, para ver como citar corretamente o artigo
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.