Uma Reavaliação Experimental de uma Heurística Multinível para o Problema do Arranjo Linear Mínimo

O Problema do Arranjo Linear Mínimo (MinLA) é um importante problema de otimização combinatória e conta com diversas aplicações práticas. De forma simples, o problema consiste em minimizar a soma da distância das arestas entre vértices dispostos em uma linha. Devido à sua relevância, diversas heurísticas foram propostas para o MinLA nas últimas décadas. Uma revisão recente indicou o Algebraic Multigrid (AMG) como o algoritmo mais promissor no problema para grafos de pequeno porte, mas que apresentou problemas em grafos de grande porte. Neste artigo, avalia-se se o AMG é o algoritmo mais promissor para obter bons resultados com baixo custo computacional em instâncias de grande porte. Neste estudo, mostra-se que o consumo elevado de memória, a dificuldade de parametrização e o custo de execução tornam o AMG impraticável em instâncias de grande porte.