Maximum outflow in generalized flow networks

A generalized flow network (GFN) is characterized by positive arc ‘multipliers’ that differ from one for some or all the arcs. GFNs have proven to be excellent models of many production, investment, and allocation problems. To date, the problem of maximizing the flow at the terminal has been treated via linear programming primal-dual arguments. An algorithm is presented that departs radically from the previous contributions in two respects: It is based on the combinatorial structure of the network, and it reverses the order of iterations by first increasing flow along paths from source to terminal, followed by increasing flow to the terminal from ‘flow generating cycles’. Computer implementation of the procedure is discussed.