Um modelo reforçado e heurísticas relax-and-fix e VNS para o Problema da Árvore Geradora Mínima Capacitada em Níveis.
Nenhuma Miniatura disponível
Data
2018
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
Este trabalho tem seu foco no Problema da Árvore Geradora Mínima Capacitada em Níveis (PAGMCN). Ele consiste em encontrar uma árvore geradora de custo mínimo, tal
que o fluxo a ser transferido de um nó central aos demais nós seja limitado pela capacidade
das arestas. Para resolvê-lo, propomos neste trabalho uma formulação reforçada de
programação matemática e um algoritmo híbrido, combinando as heurísticas relax-and-fix e Variable Neighborhood Search (VNS), juntamente com um modelo matemático. A
formulação matemática proposta, chamada \Modelo Baseado na Capacidade das Facilidades
2" (MBC2), consiste em adicionar dois novos conjuntos de restrições à formulação
considerada a mais e
ciente da literatura. A motivação para a utilização do modelo
MBC2 está em ele fornecer um limite inferior de qualidade, esperando assim convergir
mais rapidamente à solução ótima. Experimentos computacionais mostraram que a
formulação reforçada proposta, quando comparada ao modelo da literatura, melhora a
qualidade da relaxação linear, fornecendo um limite inferior melhor e justificando a sua
utilização. Para o desenvolvimento do algoritmo híbrido, foi utilizado o modelo MBC2
proposto neste trabalho, em razão de ele ser capaz de proporcionar um limite inferior
de qualidade. Essa formulação reforçada é usada com a heurística relax-and-fix para
fornecer uma solução inicial para o VNS. Resultados mostram que o VNS melhora a
solução inicial e gera soluções com gaps relativamente pequenos nas instâncias usadas
para teste.
Descrição
Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
Palavras-chave
Algoritmos de computador, Otimização combinatória, Design de redes
Citação
CAMPOS, Jean Carlos Tibúrcio. Um modelo reforçado e heurísticas relax-and-fix e VNS para o Problema da Árvore Geradora Mínima Capacitada em Níveis. 2018. 112 f. Dissertação (Mestrado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2018.