On the number of solutions generated by the simplex method for LP

Tomonari Kitahara, Shinji Mizuno

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


We obtain upper bounds for the number of distinct solutions generated by the simplex method for linear programming (LP). One of the upper bounds is polynomial in the number of variables, the number of constraints, and the ratio of the maximum to the minimum positive components in all the basic feasible solutions. We show that they are good upper bounds for some special LP problems including those on 0-1 polytopes, those with totally unimodular matrices, and the Markov decision problems. We also show that the upper bounds are almost tight by using an LP instance on a 0-1 polytope and a simple variant of the Klee-Minty example.

Original languageEnglish
Title of host publicationOptimization and Control Techniques and Applications
EditorsYi Zhang, Honglei Xu, Kok Lay Teo, Honglei Xu
PublisherSpringer New York LLC
Number of pages16
ISBN (Electronic)9783662434031
Publication statusPublished - 2014
Externally publishedYes

Publication series

NameSpringer Proceedings in Mathematics and Statistics
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


Dive into the research topics of 'On the number of solutions generated by the simplex method for LP'. Together they form a unique fingerprint.

Cite this