On the computational behavior of a polynomial-time network flow algorithm

A variation on the Edmonds-Karp scaling approach to the minimum cost network flow problem is examined. This algorithm, which scales costs rather than right-hand sides, also runs in polynomial time. Large-scale computational experiments indicate that the computational behavior of such scaling algorithms may be much better than had been presumed. Within several distributions of square, dense, capacitated transportation problems, a cost scaling code, SCALE, exhibits linear growth in average execution time with the number of edges, while two network simplex codes, RNET and GNET, exhibit greater than linear growth.Our experiments reveal that median and mean execution times are predictable with surprising accuracy for all of the three codes and all three distributions from which test problems were generated. Moreover, for fixed problem size, individual execution times appear to behave as though they are approximately lognormally distributed with constant variance. The experiments also reveal sensitivity of the parameters in the models, and in the models themselves, to variations in the distribution of problems. This argues for caution in the interpretation of such computational studies beyond the realm in which the computations were performed.This work has been supported in part by NSF grants ENG-7910807, ECS-8313853, DMS-8706133, and DDM-8813054, and by AFOSR, NSF, and ONR under NSF grant DMS-8920550 to Cornell University, and by a Sloan Foundation research fellowship held by the first author.