Heurísticas Lagrangeanas para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau nos Vértices

Autores

1795
Rafael Castro de Andrade
762,44,519
1796
Nelson Maculan Filho
(Orientador)
762,44,519
1797
Abilio Pereira de Lucena Filho
(Co-orientador)
762,44,519

Informações:

Publicações do PESC

Título
Heurísticas Lagrangeanas para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau nos Vértices
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
20/9/1999
Resumo
PESC: Resumo de Dissertação de Mestrado Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)

Heurísticas Lagrangeanas para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau nos Vértices

Rafael Castro de Andrade

Setembro/1999
Orientador: Nelson Maculan Filho
Abílio Pereira de Lucena Filho 		 

 
Programa: Engenharia de Sistemas e Computação

      Este trabalho introduz diversas heurísticas Lagrangeanas para o problema da árvore geradora com restrição de grau nos vértices. Os algoritmos são compostos por uma heurística gulosa básica que é complementada por um processo de busca local. As heurísticas se diferenciam entre si pelos custos de entrada enviados, em cada caso, à heurística gulosa. Algumas desigualdades válidas para o problema foram consideradas aqui e se mostraram de grande valia quando utilizadas, implicitamente, na heurística gulosa. Testes computacionais foram realizados e indicaram que nossas heurísticas dominam amplamente as melhores heurísticas da literatura; isso, em termos de qualidade das soluções obtidas. Fomos também capazes de trabalhar com instâncias de dimensão muito superiores àquelas tratadas na literatura.

Abstract
PESC: Master Degree Abstract Abstract of Thesis presented at COPPE/UFRJ as a partial fulfillment of the requirements for the degree of Master of Science (M.Sc.)

Lagragean Heuristics to the Degree Constrained Minimum Spanning Tree Problem

Rafael Castro de Andrade

September/1999
Advisors:Nelson Maculan Filho
Abílio Pereira de Lucena Filho 		 
Department: Systems Engineering and Computer Science

      Some Lagragean heuristics for the degree constrained minimum spanning tree problem are introduced in this Thesis. The algorithms involve a basic greedy heuristic, which is followed by a local search procedure. Each Lagrangean heuristic distinguishes itself from the others by the costs used as input to the greedy heuristic. Some valid inequalities to the problem are considered here and have shown to be very usefull when used implicity by the greedy heuristic. Computational tests were performed and indicate that our heuristics dominate the best ones from the literature. Furthermore much large instances than those in the literature have been successfully tackled in this work.

Arquivo
Topo