A constrained Steiner tree problem

The Steiner tree problem on a graph involves finding a minimum cost tree which connects a designated subset of the nodes in the graph. Variants of the basic Steiner tree model can arise in the design of telecommunication networks where customers must be connected to a switching center. In this paper, we consider the constrained Steiner tree problem which is the Steiner tree problem on a graph with one additional side constraint that imposes a budget on the total amount of a resource (e.g. employee maintenance time) required by the arcs in the solution. We discuss various problem formulations, decomposition based solution approaches, and computational experience with the proposed methods.