A simple heuristic approach to simplex efficiency

Consider the standard linear program:

$\text{Minimize}\text{cx}\text{subject to}\text{Ax=b, x?0}$

where A is an m × n matrix. The simplex algorithm solves this linear program by moving from an extreme point of the feasibility region to a better (in terms of the objective function cx) extreme point (via the pivot operation) until the optimal is reached. In order to obtain a feel for the number of necessary iterations, we consider a simple probabilistic (Markov chain) model as to how the algorithm moves along the extreme points. At first we suppose that if at any time the algorithm is at the jth best extreme point then after the next pivot the resulting extreme point is equally likely to be any of the j?1 best. Under this assumption, we show that the time to get from the Nth best to the best extreme point has approximately, for large N, a Poisson distribution with mean equal to the algorithm (base e) of N. We also consider a more general probabilistic model in which we drop the uniformity assumption and suppose that when at the jth best the next one is chosen probabilistically according to weights w_i, i = 1, …, j?1.