nÃo hà / The Min-Degree Constrained Minimum Spannig Tree - MD-MST is to find a minimum spanning tree of a graph where each vertex is a leaf of the tree or satisfies a constraint of minimum degree. The leaf vertices are called terminals and the others are the central vertices. We define and study a variation of this problem, which we denote MDF-MST, where the terminal and central vertices are fixed. We show that the problem is NP-Hard and is in FPT, parameterized by the number of central vertices. We also identify cases where the problem becomes polynomial. We propose several integer programming formulations for the problem and compare the quality of lower bound generated by their linear relaxations. We propose and teste a Lagrangian Relaxation for the problem, which we also use to define Lagrangian heuristics. We define greedy heuristics, a VND Local search and a VNS heuristic. We present a Bendersâs Decomposition. We propose a new general heuristic that combines ingredients from the Bendersâs decomposition with subgradient method, which we call subgradient heuristic. We apply this heuristic to the MDF-MST. All these algorithms have been implemented, tested and compared among them and with the CPLEX solver. The computational efficiency of the proposed algorithms, especially the Lagrangian heuristics, is comparable with that of CPLEX, and even better in several cases. Some of these algorithms were adapted for the MD-MST and DC-MST (inthelatter,thedegreeconstraintisofmaximumdegree). Whencomparingthecomputational results with the literature, we conclude that the algorithms are competitive. / O Problema de Ãrvore Geradora MÃnima com RestriÃÃo de Grau MÃnimo (Min-Degree Constrained Minimum Spannig Tree - MD-MST) consiste em encontrar uma Ãrvore geradora mÃnima de um grafo onde cada vÃrtice ou à folha da Ãrvore ou satisfaz uma restriÃÃo de grau mÃnimo. Os vÃrtices folhas sÃo chamados terminais e os demais sÃo os centrais. Definimos e estudamos uma variaÃÃo desse problema, que denotamos MDF-MST, onde os terminais e centrais sÃo definidos a priori. Mostramos que o problema à NP-DifÃcil e està na Classe FPT, parametrizado pelo nÃmero de centrais. Identificamos tambÃm casos onde o problema torna-se polinomial. Propomos vÃrias formulaÃÃes de programaÃÃo inteira para o problema e comparamos teÃrica e computacionalmente a qualidade do limite inferior gerado por suas relaxaÃÃes lineares. Propomos e testamos uma relaxaÃÃo lagrangeana para o problema, que usamos tambÃm para definir heurÃsticas lagrangenas. Definimos heurÃsticas gulosas, uma busca VND e uma heurÃstica VNS. Apresentamos uma decomposiÃÃo de Benders. Propomos uma nova heurÃstica geral que combina ingredientes da decomposiÃÃo de Benders com mÃtodo de subgradientes, a qual denominamos HeurÃstica de Subgradientes. Aplicamos tal heurÃstica ao MDF-MST. Todos esses algoritmos foram implementados, testados, comparados entre si e com o solver CPLEX. A eficiÃncia computacional dos algoritmos propostos, especialmente a relaxaÃÃo lagrangeana, à competitiva com a do CPLEX, e superior em vÃrios casos. Alguns desses algoritmos foram adaptados para o problema MD-MST e seu correlato DC-MST (este Ãltimo onde a restriÃÃo sobre os centrais à de grau mÃximo). Quando comparamos os resultados computacionais com a literatura
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:8785 |
| Date | 31 July 2014 |
| Creators | FÃbio Carlos Sousa Dias |
| Contributors | Manoel Bezerra Campelo Neto, Luiz Satoru Ochi, Rafael Castro de Andrade, CrÃston Pereira de Souza, Mauricio Cardoso de Souza |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0016 seconds