O Problema da Floresta Geradora k-Rotulada
Detalhes
- Tipo de apresentação: Trabalho completo (oral)
- Eixo temático: 14. OC – Otimização Combinatória
- Palavras chaves: Floresta Geradora k-Rotulada; Branch & Cut; Programação Paralela;
- 1 Universidade Federal do Ceará
O Problema da Floresta Geradora k-Rotulada
Pedro Jorge de Abreu Figueredo
UNIVERSIDADE FEDERAL DO CEARÁ
Resumo
Neste trabalho, estudamos o problema da Floresta Geradora k-Rotulada. Dado um grafo com um rótulo atribuído a cada aresta, o objetivo é encontrar um subgrafo gerador que é uma floresta com a menor quantidade de componentes e cujas arestas têm no máximo k rótulos distintos. O problema é NP-Difícil, e a maioria dos métodos propostos na literatura são baseados em metaheurísticas. Analisamos características do problema com o intuito de propor dois modelos matemáticos de programação inteira mista binária e inteira binária. Usamos algoritmos Branch & Cut para resolver os modelos de forma exata, explorando desigualdades válidas como cortes, regras de branching, poda, limites e decomposição de Benders. Além disso, melhoramos o único método exato disponível na literatura, usando paralelismo. Realizamos testes computacionais usando grafos gerados de forma pseudoaleatória, mostrando as melhores configurações para os modelos e Cplex encontradas.
Discussões Científicas de Qualidade
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:
Manoel Bezerra Campelo Neto
Oi, Thiago
Obrigado por seu comentário. Sua tese e resultados têm sido uma grande inspiração para o trabalho do Pedro Jorge. É uma bíblia que ele vem seguindo! Acho que agora já entendemos um pouco melhor o assunto e talvez consigamos dar uns palpites, caso você ainda tenha interesse pelo tema. Sobre o grafo G+, ele não precisa ser efetivamente construído. Mas usamos variáveis "associadas às arestas" dele em ambas as formulações. Vc sugere que não precisaríamos usar essas variáveis? Isso seria legal. Não saberia dizer se é possível.
Um abraço,
Manoel
Pedro Jorge de Abreu Figueredo
Muito obrigado thiago ficamos muito satisfeitos pelo trabalho ter agradado! Sua tese foi um dos grandes motivos que nos inspirou a trabalhar com esse problema! Sobre o Benders temos que levar em consideração que utilizamos uma abordagem automatizada. Por tanto, talvez um algoritmo mais especializado possa mudar esse cenário. A principal dificuldade deste problema é que a relaxação linear fornecer um limite inferior muito fraco, para melhorar seria necessário fortalecer o problema mestre com um conjunto de desigualdades mais fortes. Sim é possível abstrair o G+ a partir do grafo original, porém o G+ para o tamanho de instâncias usadas não causa um impacto tão grande em relação ao DFS. Algo que tentamos foi diminuir a simetrias em relação ao vertice s, porém não tivemos tanto ganho e para as formulações de fluxo tivemos casos onde tivemos uma perca de desempenho absurda. Isso não significa que não seja possível e sim que é preciso testar de forma exaustiva e com testes bem definidos como fazer essa abordagem corretamente.