UMA HEURÍSTICA RELAX-AND-FIX PARA O PROBLEMA DA ÁRVORE GERADORA MÍNIMA CAPACITADA EM NÍVEIS
Publicado em: Encontro de Saberes 2015
Evento: XXIII Seminário de Iniciação Científica
Área: ENGENHARIAS
Subárea: Engenharia de Computação
| Palavras-chaves |
| Otimização Combinatória, Pesquisa Operacional, Telecomunicações, Topologia de Redes |
| Resumo |
| Este trabalho refere-se à necessidade de encontrar a topologia de menor custo para uma rede formada pela interconexão de vários terminais ligados a um computador central. Problemas desse tipo são de grande utilidade para a engenharia de telecomunicações e logística, pois a solução é de certa forma abstrata e o método pode ser adaptado para ser aplicado a diversos problemas práticos. O Problema da Árvore Geradora Mínima Capacitada em Níveis (PAGMCN) é clássico na literatura de Otimização Combinatória e não possui procedimento que garanta encontrar sua solução em tempo razoável. No entanto, é possível encontrar soluções boas em um tempo efetivamente baixo. As variáveis de decisão representam o fluxo entre as conexões (links) e são todas inteiras, porém resolver o problema com se fossem fracionárias é muito mais rápido. Neste projeto, primeiramente desenvolvemos um conjunto de restrições para o problema que permitiu que o valor das soluções fracionárias seja muito próximo do valor das soluções inteiras sem prejuízo ao tempo de resolução. A partir de uma solução fracionária escolhemos, de acordo com certos parâmetros um conjunto de variáveis para fixar e resolvemos o problema novamente, até a solução ser inteira. Este método heurístico é conhecido na literatura como Relax–And-Fix. Os testes realizados variam somente quanto à forma de escolher os links, fixamos os links dos terminais em direção ao nó central, do nó central em direção aos terminais e testamos separar a rede com fluxo fracionário em várias sub-redes independentes, em torno do nó central. As variáveis foram escolhidas aleatoriamente. Os resultados obtidos revelaram que seria melhor escolher os links diretamente ligados ao nó central em direção aos terminais, no entanto fixar um enlace por sub-rede é muito eficiente. Portanto, futuramente, serão testadas junções desses dois métodos mais eficazes e novas adaptações, como fixar todos os links diretamente ligados ao nó central no inicio do processo. |
