Maximizing Flow Through a Network with Node and Arc Capacities

A method for maximizing the flow from source to destination along a transportation network whose nodes and arcs have limited capacities. An algorithm is derived that eliminates the need for artificial arcs and nodes used in the flow-augmenting method of Fulkerson and Ford. This simplification should provide a substantial savings in computer time and core storage. The problem is formulated as a linear program. For all nodes other than the source and sink, the node capacity may be expressed as the flow either into or out of the node, since these two quantities are equal. For the source and sink, the node capacity must be expressed in terms of the greater of the two quantities. Thus, the source node capacity limits flow out of the source, while the sink capacity limits flow into the sink. The solution method used, a cut set approach, is a generalization of Ford and Fulkerson's labeling method.