Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
Published Online:1 Aug 1982https://doi.org/10.1287/moor.7.3.441
Abstract
This paper is concerned with the average number of pivot steps of the Simplex Method which are required to solve linear programming problems of the following kind:
$$\mbox{max} v^{T}x,\quad \mbox{subject to} a^{T}_{i}x \leq 1 \quad \mbox{for } i=1,\ldots, m \mbox{ where } a_{i},v,x \in \mathbb{R}^{n}$$
We investigate a certain variant of the Simplex Method, which is particularly suited for theoretical considerations. For every pair (m, n) (m ≥ n) we introduce probability spaces whose random samples are the linear programming problems of the above mentioned type. The vectors ai, v are supposed to be distributed independently, identically and symmetrically under rotations on a bounded subset of ℝn. We deduce upper and lower bounds for the expectation values of the number of steps required in phase II of the Simplex Method. The evaluation of these bounds yields the following result for m → ∞ and for fixed n:(1) The expectation values become O(m1/(n−1)).
(2) There exists a distribution whose expectation values increase like m1/(n−1).
(3) For any distribution which satisfies our conditions the expectation values tend to infinity.
(4) For every ϵ > 0 there are distributions whose expectation values become O(mϵ).
