Technical Note—Bench Marks Comparing Transportation Codes based on Primal Simplex and Primal-Dual Algorithms

OVER the past several years, investigators at the Center for Cybernetic Studies (CCS), University of Texas, have published a number of articles purporting to demonstrate the superiority of the primal simplex approach over other approaches to the solution of transportation and assignment problems. "3'4 7] The design employed by these investigators entails explicit storage of all admissible arcs and the use of the Augmented Threaded Index (ATI) method."' Klingman, Napier, and Stutzt8] have published a problem generator (NETGEN) so that researchers can compare solutions to identical problems. These investigators also published solution times, problem parameters, and NETGEN random number seeds for problems of their selection using their primal simplex code, PNET-1. Using these identical problems, computer, and FORTRAN compiler, we were able to obtain bench marks directly comparable to those of their primal simplex code. We analyzed the solution times derived from the special purpose primal simplex codes developed by the Center for Cybernetic Studies as well as the primal simplex code developed by Srinivasan and Thompson[l?0 and compared them with DSAI's modified Ford-Fulkerson primal-dual codes (see Note 1). From these analyses we concluded that the primal simplex methodology is more sensitive to both problem size and problem density than the primal-dual methodology. The primal simplex approach also encounters considerable difficulty with primal degeneracy in solving two types of problem: (1) the classic assignment problem and (2) those trans-