The minimum cost generalized network flow problem with upper and lower bounds on the node requirements

Typescript (photocopy).Successful applications of generalized flow programming have been reported in physical flow problems with losses (such as water distribution networks, electrical power systems and transportation systems), financial investment problems, many types of assignment problems, inventory-production systems, and system planning/scheduling problems. It appears that many other applications are possible as the theory and tools based on this relatively new subject become more and more available. This dissertation presents a new modeling and optimization technique using generalized network flows, the use of which will enable large models to be formulated and solved quickly and efficiently. The problem is stated as follows: Given a directed network G = (N, E) where N is the set of nodes, with upper and lower bounds in the node flow requirements, and E is the set of arcs, with a lower bound, an upper bound, a cost and a transformation coefficient (gain or loss) associated with each arc, find a minimum cost flow distribution in the network in such a way that generalized flow conservation constraints are satisfied. The problem of finding a feasible flow in a generalized network with nonzero lower bounds on one or more arcs, and the problem of balancing flow at a node for which there is an excess of supply that must be shipped away, or an excess of demand that must be satisfied, are solved as subproblems. Both primal and dual algorithms are studied. An extension of the threaded index data structure to generalized networks is presented and an implementation of the primal algorithm using this new data structure is given. The central innovation of the technique presented is its capability to formulate and solve many generalized network flow problems that would otherwise require transformations or more restrictive assumptions before the available techniques can be applied. ..