Constructing a Minimal Cost Spanning Tree Subject to Resource Constraints and Flow Requirements.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1981
- Accession Number
- ADA115354
Entities
People
- Andrew W. Shogan
Organizations
- Stanford University