Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/RVMR-7L6MET
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Alexandre Salles da Cunha | pt_BR |
dc.contributor.referee1 | Abilio Pereira de Lucena Filho | pt_BR |
dc.contributor.referee2 | Carlos Roberto V de Carvalho | pt_BR |
dc.contributor.referee3 | Rodney Rezende Saldanha | pt_BR |
dc.contributor.referee4 | Geraldo Robson Mateus | pt_BR |
dc.creator | Frederico Paiva Quintao | pt_BR |
dc.date.accessioned | 2019-08-12T10:03:53Z | - |
dc.date.available | 2019-08-12T10:03:53Z | - |
dc.date.issued | 2008-07-09 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/1843/RVMR-7L6MET | - |
dc.description.abstract | Given a graph G = (V,E) with costs associated to the vertices of V and to the edges of E, the k-Cardinality Tree Problem (KCT) seeks a minimal cost sub-tree T of G with exactly kedges. This problem has applications in, among others, oil field leasing, telecommunications and routing.In this dissertation, we propose Integer Programming reformulations for the KCT, based upon a tranformation accomplished over the input graph. After an empirical analysis of our formulations, we implemented a Lagrangian Relaxation approach for the strongest of them. The aim of this approach is to yield lower bounds for the problem. A Lagrangian Heuristic, that was embedded in the method, was able to generate upper bounds that compare favourably to the best in the literature. | pt_BR |
dc.description.resumo | Dado um grafo G = (V,E), com custos nos vértices de V e nas arestas de E, o Problema da Árvore de Custo Mínimo com k Arestas (k-ACM) consiste em encontrar uma sub-árvore T em G com exatas k arestas, com o objetivo de que o custo de T seja mínimo. Este problema possui aplicacoções nas áreas de arrendamento de campos de petróleo, telecomunicações e roteamento, dentre outras.Neste trabalho, são propostas reformulações de Programação Inteira que se baseiam em uma transformação realizada sobre o grafo de entrada do problema. Após uma análise empírica do comportamento de algoritmos Branch-and-Bound que empregam as reformulações, foi proposta uma Relaxação Lagrangeana para uma delas. Esta Relaxação, que visa obter limites inferiores para o problema, foi integrada a uma heurística que se mostrou capaz de gerar limites superiores de qualidade para o mesmo. | pt_BR |
dc.language | Português | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | árvore de custo mínimo | pt_BR |
dc.subject | lagrangeana | pt_BR |
dc.subject.other | Programação inteira | pt_BR |
dc.subject.other | Programação heuristica | pt_BR |
dc.title | O problema da arvore de custo minimo com k arestas: reformulações e relaxação lagrangeana | pt_BR |
dc.type | Dissertação de Mestrado | pt_BR |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
fredericopaivaquintao.pdf | 621.18 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.