What is the Worst Case Behavior of the Simplex Algorithm?
Abstract
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 Dantzig's 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1980
- Accession Number
- ADA089486
Entities
People
- Norman Zadeh
Organizations
- Stanford University