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

• Ano de defesa: 2019
• Autor(a) principal: Tostas, Rogério Gomes de Lima
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Rio de Janeiro; Brasil; Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia; Programa de Pós-Graduação em Engenharia Civil; UFRJ
• Palavras-chave em Português: VNS; Largura de banda; Matrizes esparsas; CNPQ::ENGENHARIAS::ENGENHARIA CIVIL
• Link de acesso: http://hdl.handle.net/11422/13683

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.