Using variable neighborhood search metaheuristic to reduce bandwidth on sparse matrices

In this thesis, we present two proposals to solve the problem of bandwidth reduction on sparse matrices (PRB). Due to its wide applicability in engineering, computing and optimization, PRB is the subject of extensive research via both exact and heuristic models. We present an exact method for PRB via mathematical programming that has as great advantage the guarantee of optimality of the obtained solutions. PRB belongs to the class of NP-hard problems, so in general the computational time to get exact solutions grows exponentially with the size of the input. As an alternative to the high computational cost of obtaining exact solutions, we propose the use of a variant of the Variable Neighborhood Search (VNS) metaheuristic.Neste trabalho, apresentamos duas propostas para a resolução do problema de redução de banda em matrizes esparsas (PRB). Devido à sua grande aplicabilidade em engenharia, computação e otimização, o PRB é objeto de extensa pesquisa via tanto modelos exatos quanto heurísticas. Apresentamos um método exato para o PRB via modelagem matemática que apresenta como grande vantagem a garantia da otimalidade das soluções obtidas. O PRB pertence à classe de problemas NPdifíceis, sendo assim, em geral, o tempo computacional para a obtenção de soluções exatas cresce exponencialmente com o tamanho da entrada. Como alternativa ao alto custo computacional de obtenção de soluções exatas, propomos o uso de uma variante da metaheurística de Busca em Vizinhança Variável (VNS)