An Efficient Procedure for Implementing a Dual Simplex Network Flow Algorithm

This paper shows that for linear programming formulations of network flow problems, the nonzero components of rows of the basis inverse are identical. A simple algorithm for identifying these nonzero components is given along with a suggested data structure for implementation. The algorithm requires only one bit of storage for each node plus one additional bit. Finally we indicate how these ideas may be used in the development of a dual simplex code for network flow problems.