Please use this identifier to cite or link to this item: http://www.repositorio.ufop.br/handle/123456789/11687
Title: Um modelo reforçado e heurísticas relax-and-fix e VNS para o Problema da Árvore Geradora Mínima Capacitada em Níveis.
Authors: Campos, Jean Carlos Tibúrcio
metadata.dc.contributor.advisor: Souza, Marcone Jamilson Freitas
Martins, Alexandre Xavier
Keywords: Algoritmos de computador
Otimização combinatória
Design de redes
Issue Date: 2018
metadata.dc.contributor.referee: Souza, Marcone Jamilson Freitas
Martins, Alexandre Xavier
Santos, Haroldo Gambini
Carvalho, Marco Antonio Moreira de
Souza, Maurício Cardoso de
Citation: 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.
Abstract: 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.
metadata.dc.description.abstracten: This work addresses the multi-level capacitated minimum spanning tree (MLCMST) problem. It consists of nding a minimum cost spanning tree such that the ow to be transferred from a central node to the other nodes is bounded by the edge capacities. To solve it, we propose in this work a reinforced mathematical programming formulation and a hybrid algorithm, combining the heuristics Relax-and-Fix and Variable Neighborhood Search (VNS), together with a mathematical model. The proposed mathematical formulation, called \Modelo Baseado na Capacidade das Facilidades 2" (MBC2), consists in adding two new set of constraints in the most e cient formulation in the literature. The motivation for using the MBC2 model is to provide a quality lower limit, hoping to converge more quickly to the optimum solution. Computational experiments showed that the proposed reinforced formulation, when compared to the literature model, improves the quality of linear relaxation, thus providing a better lower bound and justifying its use. For the development of the hybrid algorithm, the MBC2 model proposed in this work was used, because it is able to provide a quality lower limit. The reinforced formulation is used with the relax-and- x heuristic to provide an initial solution for the VNS algorithm. Results show that the VNS improves the initial solutions and obtains solutions with relatively small gaps for all instances used for testing.
Description: 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.
URI: http://www.repositorio.ufop.br/handle/123456789/11687
metadata.dc.rights.license: Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 23/07/2018 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação.
Appears in Collections:PPGCC - Mestrado (Dissertações)

Files in This Item:
File Description SizeFormat 
DISSERTAÇÃO_ModeloReforçadoHeurísticas.pdf3,35 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons