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 |
762,44,519
|
|
1797 |
762,44,519
|
Informações:
Publicações do PESC
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 | |
|
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.
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.