Computational results for Constrained Minimum Spanning Trees in Flow Networks

In this work, we address the problem of finding a minimum cost spanning tree on a single source flow network. The tree must span all vertices in the given network and satisfy customer demands at a minimum cost. The total cost is given by the summation of the arc setup costs and of the nonlinear flow routing costs over all used arcs. Furthermore, we restrict the trees of interest by imposing a maximum number of arcs on the longest arc emanating from the single source vertex. We propose a dynamic programming model an solution procedure to solve this problem exactly. Intensive computational experiments were performed using randomly generated test problems and the results obtained are reported. From them we can conclude that the method performance is independent of the type of cost functions considered and improves with the tightness of the constrains.