Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/8697
Type: Dissertação
Title: Algoritmos exatos e heurísticos para o problema da diversidade máxima
Author(s)/Inventor(s): Oliveira, Lucas Vinicius Amaral de
Advisor: Lucena Filho, Abílio Pereira de
Abstract: Neste trabalho, propomos algoritmos Branch-and-Cut e heurísticas Lagrangeanas para o Problema da Máxima Diversidade. Utilizamos uma formulação linear padrão fortalecida por desigualdades válidas para o problema. Estas são dualizadas dinamicamente nas heurísticas e utilizadas como cortes nos algoritmos exatos. Para tanto, propomos alguns procedimentos heurísticos para separá-las de maneira eficiente. Adicionalmente, realizamos testes computacionais e comparamos nossos algoritmos exatos e heurísticos com aqueles existentes na literatura para o problema.
Abstract: In this work, we suggest Branch-and-Cut algorithms and Lagrangian heuristics for the Maximum Diversity Problem. We use a standard formulation reinforced by some valid inequalities for the problem. These are dynamically dualized in the heuristics and used as cuts in the exact methods. To separate them efficiently, we propose some heuristic procedures. In addition, we perform computational tests and compare our exact and heuristics methods with those found in the literature for the problem.
Keywords: Engenharia de Sistemas e Computação
Algoritmos exatos
Algoritmos heurísticos
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Program: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Department : Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Publisher: Universidade Federal do Rio de Janeiro
Issue Date: Aug-2017
Publisher country: Brasil
Language: por
Right access: Acesso Aberto
Appears in Collections:Engenharia de Sistemas e Computação

Files in This Item:
File Description SizeFormat 
879590.pdf323,67 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.