A Primal Algorithm For Finding Mimimum-Cost Flows in Capacitated NetworksWith Applications

This paper describes an implementation of the network simplex method for solving the transshipment problem. The problem consists of finding a minimum-cost, single-commodity flow in a capacitated network satisfying supply-and-demand constraints. The familiar transportation, assignment, and shortest route problems are all related to the transshipment problem. The area of network-flow theory has been well studied and has proven useful in many areas of applications. (See Refs. 1 to 7.) 949 A number of different methods have been proposed over the years to solve network-flow problems. These include primal, dual, primaldual, out-of-kilter, negative-cycle, and scaling methods. A survey of computer codes is presented by Charnes et al.8 Until recently, primaldual approaches were believed to be superior to the others. However, much work has been done involving data structures to reduce the computation time and space requirements for primal-network flow codes. The primal approach is a specialization of the bounded-variable, primal-simplex algorithm of linear programming which takes advantage of the special structure of network problems. We describe an implementation of a primal algorithm that is fast and can solve large problems. The major ideas used are as follows: (i) The sparsity of the network is used to reduce the time and space requirements for solving network-flow problems. (ii) Basic solutions are stored compactly as spanning trees of the network. (iii) A candidate stack is used to allow flexible strategies in choosing an arc to enter the tree.