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.
Citation
Journal of the Operations Research Society of Japan, vol. 54, no.4, December 2011, pp. 191--200.