Uso da metaheurística de busca em vizinhança variável para redução de largura de banda em matrizes esparsas

Abstract

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.