Premium
Constructing a minimal‐cost spanning tree subject to resource constraints and flow requirements
Author(s) -
Shogan Andrew W.
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130203
Subject(s) - computer science , mathematical optimization , lagrangian relaxation , flow network , arc (geometry) , constant (computer programming) , spanning tree , minimum cost flow problem , tree (set theory) , node (physics) , mathematics , discrete mathematics , combinatorics , geometry , programming language , structural engineering , engineering
Consider a network in which one node is a source having an infinite supply of a commodity, and every other node is a sink having a known constant demand. Furthermore, associated with each potential arc of the network are the following known constants: the cost of constructing the arc, the amount of each scarce resource consumed during the construction of the arc, and the flow capacity of the arc. Given the above known constants as well as the available supply of each of the scarce resources, the problem is to construct a minimal‐cost spanning tree subject to the limitations on the consumption of the scarce resources and the requirement that there exists a flow from the source satisfying the demands at the sinks without exceeding any arc capacity. This paper discusses the solution of such a problem by a branch and bound algorithm based on Lagrangian relaxation. Also included are applications of the problem, extensions of the problem, and a report on preliminary computational experience with a computer implementation of the algorithm.