Implementation of a steepest-edge primal–dual simplex method for network linear programs

A primal–dual simplex variant is presented that incrementally builds up the optimal LP basis matrix. For network LPs, the incremental primal–dual algorithm can adopt steepest-edge direction of movement utilizing standard graph data structures without additional computational overhead. Computational results indicate the resulting implementation is uniformly superior to other direction movement schemes, and achieve order of magnitude speedups versus a primal network simplex code on medium size NETGEN problems. These speedups carry over to the generalized network problem domain as well. Some comparisons are also made against the relaxation method on NETGEN uncapacitated transportation and transshipment problems.