Lower bounds for the maximum number of solutions generated by the simplex method
Tomonari Kitahara (kitahara.t.abm.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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|