Árvores Capacitadas
Autores
|
6674 |
2992,519,539
|
|
|
6675 |
2992,519,539
|
|
|
6676 |
2992,519,539
|
Informações:
Publicações do PESC
Nesta tese de doutorado investigamos diversos problemas relacionados a reformulações Dantzig-Wolfe sugeridas para o Problema da Árvore Geradora Mínima Capacitada (CMSTP). Para esses problemas, propomos formulações e algoritmos de soluções exatas e heurísticas para os problemas investigados.
Inicialmente, nós estudamos o problema da Arborescência Mínima (MAP). Esse problema é uma relaxação do problema de pricing associado as reformulações Dantzig-Wolfe para o CMSTP. Como primeira contribuição, é apresentada uma formulação matemática e um algoritmo Branch-and-cut para resolver o MAP. Em seguida, é proposta uma formulação para a versão do problema que é restrita a grafos direcionados acíclicos (DAGs - Directed Acyclic Graphs). Os limites encontrados pela relaxação linear dessa formulação são, em média, 77% melhores. Ainda, apresentamos um novo conjunto de instâncias DAGs, sendo essas mais difíceis que as já existentes para o problema.
O segundo problema relacionado às reformulações Dantzig-Wolfe sugeridas para o CMSTP é denominado problema da Arborescência Mínima Capacitada (CMAP). Neste trabalho, definimos formalmente esse problema e apresentamos uma formulação matemática. Adicionalmente, generalizamos as desigualdades multistar, originalmente propostas para o CMSTP, e elaboramos um algoritmo de separação para essas desigualdades. Os resultados computacionais mostram que o algoritmo de plano de cortes sob essa formulação, quando fortalecida pelas multistars generalizadas, levam à limites inferiores 50% melhores, em média. Por fim, nós apresentamos uma heurística baseada em programação dinâmica e um conjunto de instâncias para o CMAP. Essas são criadas a partir de um algoritmo de geração de colunas para o CMSTP.
In this thesis we investigate some problems related to Dantzig-Wolfe reformulation suggested to the CMSTP. Indeed, we study same variants of the column generation problems relative to such reformulations. In this process, we propose formulations and algorithms for exact and heuristic solutions to the problems.
We start by studing the Minimum Arborescence Problem (MAP), which is a relaxation of the pricing problem associated to the CMSTP Dantzig-Wolfe reformulations. We propose a better formulation for the problem and, for the version restricted to Directed Acyclic Graphs (DAGs), we prove that this formulation leads to a better representation of the cover hull. Additionally, we present a set of new DAGs instances, which turns to be more dicult to solve than the existing ones.
Later, we formally define the pricing problem related to Dantzig-Wolfe reformulation suggested to the CMSTP, named Capacitated Minimum Arborescence Problem (CMAP). Except for the capacity constraint, the formulation we propose for this problem is equal to the one proposed for the MAP. Moreover, we generalize the multistar inequalities, originaly proposed for the CMSTP, and present a separation algorithm. Computational results show that the cutting plane algorithm under the formulation enforced by the generalized multistars leads to dual bounds 50% tighter, on average. Finally, we propose a dynamic programming based heuristic and benchmark instances originated from a column generation algorithm.