A Simple Heuristic Approach to Simplex Efficiency.
Abstract
Consider the standard linear program: Minimize c x--subject to: A x = b, x greater than or equal to 0, where A is an m x n matrix. The simplex algorithm solves this linear program by moving from extreme point of the feasibility region to a better (in terms of the objective function c x) 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 logarithm (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 wi, i = 1, ..., j - 1. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1981
- Accession Number
- ADA107913
Entities
People
- Sheldon M. Ross
Organizations
- University of California, Berkeley