Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/50329
Title in Portuguese: Modelagem multigrafo, decomposição e BRKGA para o problema da árvore geradora generalizada mínima
Title: Multigraph, decomposition and BRKGA solution approaches for the generalized minimum spanning tree problem
Author: Sousa, Ernando Gomes de
Advisor(s): Andrade, Rafael Castro
Co-advisor(s): Duhamel, Andréa Cynthia Santos
Keywords: Otimização
Árvore geradora generalizada mínima
Formulações de programação linear inteira mista
Metaheurística BRKGA
Decomposição de Benders
Issue Date: 2019
Citation: SOUSA, Ernando Gomes de. Modelagem multigrafo, decomposição e BRKGA para o problema da árvore geradora generalizada mínima. 2019. 75 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2019.
Abstract in Portuguese: Dado um grafo conexo, não direcionado e m-partido G = (V1 ∪V2 ∪...∪Vm, E), cujo conjunto de vértices é particionado em subconjuntos disjuntos V1,V2,...,Vm e cujas arestas de E conectam somente vértices de clusters distintos, o Problema da Árvore Geradora Generalizada Mínima (denotado por GMSTP, do inglês Generalized Minimum Spanning Tree Problem) consiste em encontrar uma árvore com exatamente m - 1 arestas, as quais conectam V1,V2,...,Vm através da seleção de um único vértice em cada cluster. O GMSTP encontra aplicações em problemas de modelagem de redes, agricultura irrigada, cidades inteligentes, data science, entre outros. Este trabalho apresenta para o GMSTP uma formulação multigrafo original, um procedimento para fixação de vértices que não possam pertencer a uma solução ótima, uma metaheurística Algoritmo Genético Baseado em Chave Aletaória (denotado por BRKGA, do inglês Biased Random Key Genetic Algorithm) e a aplicação do método de decomposição de Benders para uma formulação multifluxo da literatura. Resultados computacionais da formulação multigrafo superam os resultados das melhores formulações da literatura em termos de tempo de CPU para a obtenção de soluções comprovadamente ótimas para instâncias de teste da literatura e a decomposição de Benders aplicada neste trabalho apresenta os melhores resultados dentre todas as estratégias exatas analisadas. Além disso, o BRKGA apresenta melhor performance que metaheurísticas existentes para o problema em termos de qualidade de soluções viáveis obtidas para instâncias benchmark do GMSTP. Por fim, este trabalho abre novas direções de pesquisas para o desenvolvimento de algoritmos para problemas relacionados.
Abstract: Given a connected, undirected, and m-partite graph G = (V1 ∪V2 ∪...∪Vm,E), with set of vertex partitioned into disjoint subsets V1,V2,...,Vm and whose edges of E connect only nodes of distinct clusters, the Generalized Minimum Spanning Tree Problem (GMSTP) looks for a minimum-cost tree with exactly m - 1 edges, connecting V1,V2,...,Vm through the selection of exactly one vertex of each cluster. The GMSTP finds applications in network design, irrigation agriculture, smart cities, data science, among others. This work presents, for the GMSTP, an original multigraph mathematical formulation, a new procedure for eliminating vertices proved to not belong to an optimal solution, a Biased Random Key Genetic Algorithm (BRKGA) metaheuristic, and a Benders decomposition method applied to an existing flow-based formulation. Computational results for the multigraph formulation has better results than for existing formulations for the problem and the Benders decomposition obtains the best results among all the exact strategies analyzed. Moreover, the BRKGA presents better performance than existing metaheuristics with respect to solution quality for benchmark instances of the problem. Finally, this work opens new directions for research and the development of algorithms for related problems.
URI: http://www.repositorio.ufc.br/handle/riufc/50329
metadata.dc.type: Tese
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2019_tese_egsousa.pdf726,77 kBAdobe PDFView/Open


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