Klee-Minty's LP and Upper Bounds for Dantzig's Simplex Method

Details Klee-Minty's LP and Upper Bounds for Dantzig's Simplex Method Klee-Minty's LP and Upper Bounds for Dantzig's Simplex Method

2011-01-20

arxiv.org/abs/1101.3821v2

Mathematics

Optimization and Control

This paper has been withdrawn by the authors. This article will appear in Operations Research Letters

Scientific paper

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 by 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.

Affiliated with

Also associated with

No associations

Rating

Klee-Minty's LP and Upper Bounds for Dantzig's Simplex Method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Klee-Minty's LP and Upper Bounds for Dantzig's Simplex Method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Klee-Minty's LP and Upper Bounds for Dantzig's Simplex Method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-333081