Árvores capacitadas

Abstract

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 difficult 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.