Stronger column generation bounds for the Minimum Cost Hop-and-root Constrained Forest Problem

In this paper, we present a Dantzig-Wolfe reformulation for the Minimum Cost Hop-and-root Constrained Forest Problem and discuss a Column Generation (CG) method to evaluate its Linear Programming (LP) bounds. For solving one of two types of pricing problems that arise in CG, we compared two solution strategies: Dynamic Programming and a Branch-and-cut (BC) algorithm. In general, CG performed much better when BC was used. Not only the LP bounds implied by the proposed reformulation are much stronger than the multi-commodity flow bounds from the literature, but also could be evaluated with less computational time. A Column Generation Heuristic was discussed and implemented, providing upper bounds that are, on average, within 2.3% of optimality.