O problema da arvore de custo minimo com k arestas: reformulações e relaxação lagrangeana

• Ano de defesa: 2008
• Autor(a) principal: Frederico Paiva Quintao
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; UFMG
• Palavras-chave em Português: árvore de custo mínimo; lagrangeana; Programação inteira; Programação heuristica
• Link de acesso: http://hdl.handle.net/1843/RVMR-7L6MET

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.