Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry

In this paper we study the average number of pivot steps required by the simplex algorithm for solving linear programs. For this purpose we perform numerical and empirical tests. The problems are generated randomly according to several rotation symmetric distribution models. We observe the influence of the distributions and the dimension. This evaluation is done for seven different, well known variants of the simplex algorithm. In addition, we test the shadow vertex algorithm. It should be remarked that only the shadow vertex variant and equivalent parametric methods could be analyzed theoretically so far under this or other stochastic models. Here we compare the empirical values with the theoretical bounds.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.