Geração de Colunas para o Problema de Empacotamento de Árvores de Steiner
Autores
|
2275 |
519,44,539
|
|
|
2276 |
519,44,539
|
|
|
2277 |
519,44,539
|
Informações:
Publicações do PESC
Um algoritmo de solução exata, para uma das variantes do problema de empacotamento de árvores de Steiner, é proposto nesta tese. 0 algoritmo se baseia em uma nova formulação do problema, por nós introduzida, e é do tipo branch-and-price. É iniciado por uma heurística primal que gera, além de soluções viáveis (limites superiores) para o problema, um conjunto viável adicional de árvores de Steiner. Essas árvores são usadas para inicializar a geração dinâmica de colunas. Limites inferiores para o problema são obtidos através de relaxação linear do modelo, que é resolvido via geração de colunas. Limites superiores adicionais para o problema são obtidos através da solução ótima de um problema mestre (bastante) reduzido. Os resultados computacionais obtidos com o algoritmo redefinem o "estado da arte" para algoritmos de soluções exatas para o problema de empacotamento de árvores de Steiner.
An exact solution algorithm, for one of the variants of the Steiner tree packing problem, is introduced in this thesis. The algorithm is based on a new formulation of the problem, introduced by us. The algorithm is of the branch-and-price type and is initiated with a primal heuristic which ge- nerates, in addition to feasible solutions (upper bounds) to the problem, a feasible set of Steiner trees. These trees are used to initialize dynamic column generation. Lower bounds for the problem are obtained through a linear programming relaxation of the model, which is solved via column generation. Additional problem upper bounds are obtained through the optimal solution to a fairly restricted master problem. Computational results, obtained with the algorithm, push forward the state-of-the-art for exact solution algorithms to the Steiner tree packing problem.