On the length of simplex paths: The assignment case

This paper reports on an experimental study of the distribution of the length of simplex paths for the Optimal Assignment Problem. We study the distribution of the pivot counts for a version of the simplex method that with essentially equal probabilities introduces any variable with negative reduced cost into the basis. In this situation the distribution of the pivot counts turns out to be normally distributed and independent of the actual cost coefficients, provided these are sufficiently spread out. Further, the mean and standard deviation grow only moderately with the size of the problem, namely as d^1.8, and d^1.5 respectively for a d×d problem, implying in particular that the pivot counts concentrate around the mean with growing d. The usual simplex method on the other hand gives a growth of d^1.6. Hence a large part of the favourable polynomial growth experienced on practical problems may be attributed to the fact that the simplex paths are rather short on the average, at least for assignment problems.