What is the Worst Case Behavior of the Simplex Algorithm?
STANFORD UNIV CA DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
The examples published by Klee and Minty in 1972 do not preclude the existence of a pivot rule which will make the simplex method, at worst, polynomial. In fact, the continuing success of Dantzigs method suggests that such a rule does exist. A study of known examples shows that a those which use selective pivot rules require exponentially large coefficients, and b none of the examples pivot rules are typically used in practice, either because of computational requirements or due to a lack of even-handed movement through the column set. In all bad problems, certain improving columns are entered about 2 to the m-2 power times before other improving columns are entered once. This is done by making the unused columns appear to yield small objective function improvement. The purpose of this paper is to explain the Klee-Minty and Jeroslow constructions, show how they can be modified to be pathological with small integral coefficients, and then suggest a least entered pivot rule which forces an improving column to be entered before any other column is entered for the second time. This rule seems immune to the deformed product construction which is the essence of all known exponential counterexamples. Author
- Theoretical Mathematics