The Bandwidth minimization problem

Mestrado em Métodos Quantitativos para a Decisão Económica e EmpresarialEsta dissertação tem como objetivo comparar o desempenho de duas heurísticas com a resolução de um modelo exato de programação linear inteira na determinação de soluções admissíveis do problema de minimização da largura de banda para matrizes esparsas simétricas. As heurísticas consideradas foram o algoritmo de Cuthill e McKee e o algoritmo Node Centroid com Hill Climbing. As duas heurísticas foram implementadas em VBA e foram avaliadas tendo por base o tempo de execução e a proximidade do valor das soluções admissíveis obtidas ao valor da solução ótima ou minorante. As soluções ótimas e os minorantes para as diversas instâncias consideradas foram obtidos através da execução do código para múltiplas instâncias e através da resolução do problema de Programação Linear Inteira com recurso ao Excel OpenSolver e ao software de otimização CPLEX. Como inputs das heurísticas foram utilizadas matrizes com dimensão entre 4×4 e 5580×5580, diferentes dispersões de elementos não nulos e diferentes pontos de partida.This dissertation intends to compare the performance of two heuristics with the resolution on the exact linear integer program model on the search for admissible solutions of the bandwidth minimization problem for sparse symmetric matrices. The chosen heuristics were the Cuthill and McKee algorithm and the Node Centroid with Hill Climbing algorithm. Both heuristics were implemented in VBA and they were rated taking into consideration the execution time in seconds, the relative proximity of the value obtained to the value of the optimal solution or lower bound. Optimal solutions and lower bounds were obtained through the execution of the code for several instances and trough the resolution of the integer linear problem using the Excel Add-In OpenSolver and the optimization software CPLEX. The inputs for the heuristics were matrices of dimension between 4×4 and 5580×5580, different dispersion of non-null elements and different initialization parameters.