Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/40133
Title in Portuguese: O problema da k-floresta com máximo número de folhas
Title: The maximum leaf k-forest problem
Author: Freitas Filho, Francisco Sérgio de
Advisor(s): Andrade, Rafael Castro de
Keywords: Otimização combinatória
Árvore geradora com máximo número de folhas
k-floresta com máximo número de folhas.
Desigualdades válidas
Programação Inteira
Issue Date: 2019
Citation: FREITAS FILHO, Francisco Sérgio de. O problema da k-floresta com máximo número de folhas. 2019. 58 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2019.
Abstract in Portuguese: Dados um grafo simples conexo e um inteiro positivo k, o problema da k-floresta com máximo número de folhas consiste em encontrar uma floresta geradora com tantas folhas quanto possível e não mais que k componentes. Propomos os primeiros modelos matemáticos para o problema bem como desigualdades válidas. Para k = 1 temos o conhecido problema da árvore geradora com máximo número de folhas (MLSTP). Em particular, para esse problema, as novas desigualdades se mostraram muito eficientes. Dois dos modelos propostos neste documento generalizam formulações encontradas na literatura para o MLSTP e têm como base formulações que descrevem os poliedros de árvores e arborescências geradoras. Apresentamos também caracterizações para o problema, que facilitam expressá-lo de uma maneira alternativa, onde buscamos um conjunto de folhas que gere uma solução ótima e, uma vez que dispomos de tal conjunto, podemos obter uma solução completa para o problema em tempo polinomial. Como consequência, propomos um modelo denominado (MB) o qual resolvemos utilizando um método iterativo de decomposição de Benders para k = 1 e, para o caso geral, uma formulação denominada (MVE) e um modelo (MFA) utilizando fluxo em rede. Realizamos experimentos computacionais e analisamos os desempenhos dos modelos. Em particular, para k = 1, comparamos os resultados obtidos tendo como referência formulações da literatura para o MLSTP. Damos destaque ao modelo (MFA) por sua simplicidade de implementação e por não demandar técnicas sofisticadas de corte ou separação. Além disso, para k = 1, esse modelo foi o único a encontrar soluções ótimas para todo o conjunto de instâncias, mostrando-se superior aos modelos específicos para o MLSTP presentes na literatura. Também vale ressaltar que, ainda para k = 1, o modelo (MB) mostrou-se consideravelmente mais eficiente que os demais quando consideramos um subconjunto de instâncias que apresentam maiores densidades de arestas.
Abstract: Given a simple connected graph and a positive integer k, the maximum leaf k-forest problem consists in finding a spanning forest with as many leaves as possible and no more than k components. We propose the first mathematical models for the problem as well as valid inequalities. For k = 1, we have the known maximum leaf spanning tree problem (MLSTP). In particular, for this problem, the new inequalities have proved to be very efficient. Two of the models we propose in this work generalize formulations found in the literature for the MLSTP and are based on formulations that describe the polytope of spanning trees and arborescences. We also present new characterizations for the problem, which makes easy to express it in an alternative way, where we look for a set of leaves that generate an optimal solution and, once we have such set, we can obtain a solution to the problem in polynomial time. As a consequence, we propose a model called (MB) which we solve by using an iterative method based on Benders decomposition for k = 1 and, for the general case, a formulation called (MVE) and a model (MFA) exploring network flow. We perform computational experiments and analyze the performance of our models. In particular, for k = 1, we compare our results with the ones obtained by existing formulations for MLSTP. We emphasize model (MFA) for its simplicity to implement and for not demanding sophisticated cutting or separation techniques. In addition, for k = 1, this model was the unique to find optimal solutions for the whole set of instances, outperforming MLSTP models from the literature. It is also worth noting that, for k = 1, model (MB) was considerably more efficient than the other ones when considering instances with higher edge densities.
URI: http://www.repositorio.ufc.br/handle/riufc/40133
Appears in Collections:DCOMP - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2019_dis_fsfreitasfilho.pdf522,91 kBAdobe PDFView/Open


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