Problemas de Árvores Geradoras em Grafos com Ênfase no Número de Folhas
Autores
|
5643 |
Pedro Henrique Pereira Vargas Lighori
|
2598,519
|
|
5646 |
2598,519
|
Informações:
Publicações do PESC
Dado um grafo não orientado G = (V,E) e um inteiro l, o problema da árvore geradora com restrição no número de folhas consiste em encontrar uma árvore geradora T = (V,E'), com pelo menos l folhas. A versão de otimização desse problema busca encontrar uma árvore geradora de custo mínimo para G, que contenha pelo menos l folhas. Um outro problema muito próximo ao que acabamos de descrever é aquele de encontrar uma árvore geradora de G com um número máximo de folhas. Formulações, desigualdades válidas e algoritmos de solução para esses dois problemas são os temas principais investigados nesse trabalho.
Entre as principais contribuições alcançadas, destacamos a introdução de uma nova família de desigualdades válidas para a formulação clássica baseada em grafos não orientados.
Ainda, como contribuições do trabalho, chamamos a atenção para o desenvolvimento de um algoritmo exato do tipo branch-and-cut baseado em uma nova formulação proposta para os problemas apresentados acima. Esse algoritmo se mostrou capaz de resolver à otimalidade as maiores instâncias propostas até o problema,
apresentado performance comparável à de outras formulações existentes na literatura. Adicionalmente, sugerimos um conjunto de instâncias difíceis para o problema da árvore geradora de custo mínimo com limite inferior do número de folhas. Finalmente, desenvolvemos um algoritmo do tipo relax-and-cut, que contém, como parte integrante, uma heurística Lagrangeana que se mostrou eficaz na construção de soluções viáveis de boa qualidade para o problema.
Given a non-directed graph G = (V,E) and a number l, the leaf constrained minimum spanning tree problem (LCMSTP) can be formulated as the search of a spanning tree T = (V,E'), with at least l leaves. In its optimization version, one should look for a minimum cost spanning tree of G with at least l leaves. A close related problem is that of finding a spanning tree of G with as many leaves as possible (known in literature as the maximum leaf spanning tree problem - MLSTP). Formulations, valid inequalities and solution algorithms are the main focus of this work.
Among the most importants contribuitions achieved we point out the introduction of a new family of valid inequalities to characterize the leaves in a tree.
Other contribuition of this work is the development of a branch-and-cut algorithm based on the formulation introduced earlier. This algorithm was able to solve optimally the biggest instances known. We also develop a Lagrangean based algorithm, relax-and-cut, for wich we use a Lagrangean heuristic to build good primal solutions to the problem. Finally, we introduce a set of dificult instances for LCMSTP.