A computational comparison of the network simplex method with the dual affine scaling method

The authors compare the performance of an implementation of dual affine scaling method using complete Cholesky factors with the network simplex method on (sparse) minimum cost network flow, transportation and assignment problems. They find that the network simplex method out-performs this implementation of affine scaling method. The ratio of times required by the two methods is bound to grow with the number of nodes and the density of network. However, for very sparse problems the authors find the two methods to be competitive.