
Accession Number : ADA115354
Title : Constructing a Minimal Cost Spanning Tree Subject to Resource Constraints and Flow Requirements.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CA
Personal Author(s) : Shogan,Andrew W
PDF Url : ADA115354
Report Date : Nov 1981
Pagination or Media Count : 56
Abstract : 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 branchandbound algorithm base on Lagrangean relaxation. Also included are applications of the problem, extensions to the problem, and a report on preliminary computational experience with a computer implementation of the algorithm. (Author)
Descriptors : *Algorithms, *Operations research, *Cost models, Nodes, Lagrangian functions, Computations, Integer programming, Trees, Flow charting, Computer logic
Subject Categories : Theoretical Mathematics
Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE