Designing reliable tree networks with two cable technologies

In this paper we introduce a minimal spanning tree problem with generalized hop constraints and primary connectivity constraints. The problem is concerned with reliability requirements in a centralized network design problem where two different cable technologies are available. The problem is shown to be NP-hard and as a consequence we derive lower bounding and upper bounding schemes for the problem. We formulate the problem as a directed multicommodity flow model. Due to the size of the corresponding linear programming (LP) model we use Lagrangean relaxation together with subgradient optimization to derive lower bounds. A Lagrangean heuristic is developed to construct feasible solutions. The theoretically best lower bound associated with the Lagrangean scheme quite often improves on the value of the corresponding LP bound since the relaxed problem does not satisfy the integrality property. In fact, using the heuristic, these bounds can be proved to be even optimal for many of the cases tested. These results are taken from a set of complete graphs with up to 40 nodes. We also examine a few variations of the main model. In particular we shall discuss several different ways of modeling the primary connectivity constraints. One outcome of our discussion is that we shall derive an extended and compact representation of the convex hull of directed rooted subtrees when the underlying graph is series-parallel.