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 branch-and-bound 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