Optimization Online


Lower bounds for the maximum number of solutions generated by the simplex method

Tomonari Kitahara (kitahara.t.ab***at***m.titech.ac.jp)
Shinji Mizuno (mizuno.s.ab***at***m.titech.ac.jp)

Abstract: Kitahara and Mizuno get upper bounds for the maximum number of different basic feasible solutions generated by Dantzig�s simplex method. In this paper, we obtain lower bounds of the maximum number. Part of the results in this paper are shown in a paper by the authors as a quick report without proof. They present a simple variant of Klee-Minty�s LP and get a lower bound. In this paper, we explain and prove the properties of the variant more precisely. We also show a new lower bound by using a simple example of LP.

Keywords: Simplex method, basic feasible solutions, Klee-Minty's LP

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Journal of the Operations Research Society of Japan, vol. 54, no.4, December 2011, pp. 191--200.


Entry Submitted: 07/31/2011
Entry Accepted: 07/31/2011
Entry Last Modified: 05/09/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society