Computational results for Constrained Minimum Spanning Trees in Flow Networks
Dalila B. M. M. Fontes
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.
Dynamic programming, network flows, constrained trees, general nonlinear costs
In order to set up a list of libraries that you have access to,
you must first login
or sign up.
Then set up a personal list of libraries from your profile page by
clicking on your user name at the top right of any screen.