Reformulations and branch-and-price algorithm for the Minimum Cost Hop-and-root Constrained Forest Problem

Abstract

The Minimum Cost Hop-and-root Constrained Forest Problem (MCHCFP) is a combinatorial optimization problem that arises in the design of energy efficient wireless sensor networks with mobile sinks. It aims at providing a communication topology that minimizes energy consumption while controlling network latency and message loss due to communication failure. The problem is defined in terms of a mixed graph with set of vertices V (representing the sensor nodes), edges E, arcs A, and parameters and . Each edge has an associated length, and each arc has an associated cost. The MCHCFP aims at finding a rooted spanning forest of (V, A) with minimum total cost. The solution must be hop constrained, in the sense that the path from any leaf to its root in the forest does not have more than H arcs, as well as distance constrained, so that one must be able to find K routes of length at most D, visiting exactly once the chosen roots of the forest. We study four integer programming formulations, two of them are new, the other two come from the literature. The first formulation coming from the literature is a multicommodity flow based model. The second is a Dantzig–Wolfe reformulation of the first. The two new formulations, which are equivalent with respect to their linear programming bounds, arise when the problem is formulated over a layered graph. To evaluate the bounds implied by the formulations other than the network flow model, we develop algorithms based on delayed column and/or row generation. We provide computational experiments showing that the best lower bounds are given by the formulations based on the layered graph. The reformulation coming from the literature provides lower bounds that are very close to those provided by the layered graph formulations, but in significantly less computational time. As it provides the best trade-off between lower bound quality and computational effort, that reformulation is thus chosen as the basis for a branch-and-price algorithm introduced here. Such an algorithm managed to solve instances with up to 60 vertices, a significant improvement over the previous approach in the literature, which systematically solves instances with up to 20 vertices.