A CONSTRAINED STEINER TREE PROBLEM

The Steiner tree problem on a graph involves finding a minimum cost tr ee which connects a designated subset of the nodes in the graph. Varia nts of the basic Steiner tree model can arise in the design of telecom munication networks where customers must be connected to a switching c enter. 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.