Primary simplex method for flow network
This paper describes an efficient network simplex algorithm for solving minimum-cost network flow problems. The algorithm derives from a theoretical characterization of the network topology of the basis embodied in a specially constructed basis tree. Experimentation with large sparse mini- mum-cost network flow problems has shown that in practice good implemen-tation of the network simplex method is more efficient than other implemen-tations based on special network flow methods.