Optimization Online


Klee-Minty's LP and Upper Bounds for Dantzig's 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 (2010) get two upper bounds for the number of different basic feasible solutions generated by Dantzig’s simplex method. The size of the bounds highly depends on the ratio between the maximum and minimum values of all the positive elements of basic feasible solutions. In this paper, we show some relations between the ratio and the number of iterations by using an example of LP, which is a simple variant of Klee-Minty’s LP. We see that the ratio for the variant is equal to the number of iterations of Dantzig’s simplex method for solving it. This implies that it is impossible to get a better upper bound than the ratio. We also give improved results of the upper bounds.

Keywords: Simplex method, Linear programming, Basic feasible solutions, Klee-Minty’s LP.

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

Citation: This article will appear in Operations Research Letters.


Entry Submitted: 01/04/2011
Entry Accepted: 01/04/2011
Entry Last Modified: 02/06/2011

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 Programming Society