ENUMERATIVE ALGORITHMS FOR SOLVING A CLASS OF NETWORK SYNTHESIS PROBLEMS.

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