Uma Heurística Lagrangeana para o Problema da Árvore Geradora Capacitada de Custo Mínimo

 Esta tese introduz uma heurística Lagrangeana para o problema da Árvore Geradora Capacitada de Custo Mínimo. A heurística é inicializada por um algoritmo guloso construtivo e é complementada por uma estratégia de busca local. A heurística opera dentro de um ambiente Lagrangeano onde limites duais (inferiores) são gerados por um algoritmo do tipo Relax and Gut. Nesse procedimento, limites duais são utilizados para modificar os custos de entrada da heurística gulosa. Testes para fixação de variáveis, utilizando limites primais e duais, foram desenvolvidos e se mostraram bastante efetivos quando a distância entre os limitantes não era muito grande. Através desse procedimento conseguimos provar a otimalidade de uma instância a muito em aberta. Testes computacionais foram realizados e indicaram que os nossos resultados melhoraram, sensivelmente, os limites inferiores para uma determinada classe de instâncias da literatura. Os limites superiores obtidos parecem depender fortemente da qualidade dos limites inferiores que lhes servem de entrada, e são dominados apenas por uma meta-heurística recentemente proposta.