Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/RVMR-7L6MET| Tipo: | Dissertação de Mestrado |
| Título: | O problema da arvore de custo minimo com k arestas: reformulações e relaxação lagrangeana |
| Autor(es): | Frederico Paiva Quintao |
| primer Tutor: | Alexandre Salles da Cunha |
| primer miembro del tribunal : | Abilio Pereira de Lucena Filho |
| Segundo miembro del tribunal: | Carlos Roberto V de Carvalho |
| Tercer miembro del tribunal: | Rodney Rezende Saldanha |
| Cuarto miembro del tribunal: | Geraldo Robson Mateus |
| Resumen: | 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. |
| 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. |
| Asunto: | Programação inteira Programação heuristica |
| Idioma: | Português |
| Editor: | Universidade Federal de Minas Gerais |
| Sigla da Institución: | UFMG |
| Tipo de acceso: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/RVMR-7L6MET |
| Fecha del documento: | 9-jul-2008 |
| Aparece en las colecciones: | Dissertações de Mestrado |
archivos asociados a este elemento:
| archivo | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| fredericopaivaquintao.pdf | 621.18 kB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.