ENUMERATIVE ALGORITHMS FOR SOLVING A CLASS OF NETWORK SYNTHESIS PROBLEMS.
Abstract
A class of network flow problems having a combinatorial nature is defined. A network is synthesized by including exactly one directed arc from each of several disjoint subsets of possible arcs. All candidate arcs in a particular subset connect the same pair of nodes, and associated with each arc are five parameters: a cost of inclusion, unit cost of flow, lower and upper limits on flow, and direction of positive flow. When a network is synthesized, a least cost feasible flow is computed. The objective of the problem is to synthesize the network for which the total cost--costs of inclusion plus costs of flow--is least. In certain special cases the problem reduces to a linear minimum cost flow problem, but more frequently an enumerative technique is required. Branch-and-bound and implicit enumeration algorithms are formulated and compared. The algorithms are specialized for three applications: plant location problems, cost-time critical path scheduling with nonconvex costs, and critical path scheduling under disjunctive constraints. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1970
- Accession Number
- AD0710417
Entities
People
- Robert D. Sanderson
Organizations
- University of California, Berkeley