Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/50722
Title in Portuguese: O problema da floresta geradora k-rotulada
Title: The k-labeled spanning forest problem
Author: Figueredo, Pedro Jorge de Abreu
Advisor(s): Campêlo Neto, Manoel Bezerra
Keywords: Floresta geradora k-rotulada.
Branch&Cut
Backtracking
Programação inteira
Programação paralela
Issue Date: 2020
Citation: FIGUEREDO, Pedro Jorge de Abreu. O problema da floresta geradora k-rotulada. 2020. 99 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2020.
Abstract in Portuguese: Neste trabalho, estudamos o problema da Floresta Geradora k-Rotulada. Dentre os problema em grafos coloridos em arestas, esse tem como objetivo encontrar um subgrafo gerador que é uma floresta com a menor quantidade de componentes e com um fator limitante inteiro positivo k para o número de rótulos distintos usados. O problema é NP-Difícil, por ser generalização do problema da Árvore Geradora Minimamente Rotulada, e a maioria dos métodos propostos pela literatura são baseados em metaheurísticas. Estudamos características do problema e relacionamos com a literatura pertinente em grafos coloridos. A partir das propriedades estudadas, estabelecemos uma classe na qual o problema é resolvido em tempo polinomial. Também exploramos caracterizações do problema para propor três modelos matemáticos de programação inteira mista binária e inteira binária. Propomos métodos Branch&Cut para resolver o problema de forma exata, usando um algoritmo para separação de Cortes Coloridos. Além disso, propomos uma paralelização para o único método exato disponível na literatura, que aplica um procedimento backtracking. Apresentamos experimentos computacionais preliminares com os modelos e o método backtracking, usando instâncias de teste sugeridas pela literatura. Aplicamos melhorias para os métodos de resolução, explorando desigualdades válidas como cortes, regras de branching, poda e limites. Além disso, aplicamos decomposição de Benders ao modelo via fluxo proposto. Em seguida, testamos os modelos para grafos com parâmetro de densidade de arestas diferenciados, porém pertinentes ao problema. Desses testes, mostramos as melhores configurações para os modelos e Cplex encontradas.
Abstract: In this work, we study the k-Labeled Spanning Forest Problem. Among the problems in edge labeled graphs, this one aims at finding a spanning subgraph that is a forest with the least amount of components and with a positive integer limiting factor k for the number of different labels used. The problem is NP-Hard, as it is a generalization of the Minimal Labeled Spanning Tree Problem, and most of the methods proposed in the literature are based on metaheuristics. We study the characteristics of the problem and relate it to the relevant literature in labeled graphs. Through the studied properties, we establish a class on which the problem is solved in polynomial time. We also explore the characterizations of the problem to propose three mathematical models in 0-1 integer and mixed-integer programming. We propose Branch&Cut methods to solve the problem exactly, using an algorithm to separate Colorful Cuts. Moreover, we propose a parallelization for the only exact method available in the literature, which applies a backtracking procedure. We present preliminary computational experiments with the models and the backtracking method, using test instances suggested by the literature. We apply improvements to the resolution methods by exploring valid inequalities as cuts, branching rules, pruning, and bounds. Besides, we apply Benders decomposition to the proposed flow model. Then, we test the models on graphs with different edge density parameters, still pertinent to the problem. Among these tests, we show the best-found configurations for the models and Cplex.
URI: http://www.repositorio.ufc.br/handle/riufc/50722
metadata.dc.type: Dissertação
Appears in Collections:DCOMP - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2020_dis_pjafigueredo.pdf1,04 MBAdobe PDFView/Open


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