A Bound for the Number of Different Basic Solutions Generated by the Simplex Method

Details A Bound for the Number of Different Basic Solutions Generated by the Simplex Method A Bound for the Number of Different Basic Solutions Generated by the Simplex Method

2011-01-20

arxiv.org/abs/1101.3820v1

Mathematics

Optimization and Control

Keywords: Simplex method, Linear programming, Iteration bound, Strong polynomiality, Basic feasible solutions

Scientific paper

In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the positive elements of primal basic feasible solutions. When the primal problem is nondegenerate, it becomes a bound for the number of iterations. We show some basic results when it is applied to special linear programming problems. The results include strongly polynomiality of the simplex method for Markov Decision Problem by Ye and utilize its analysis.

Affiliated with

Also associated with

No associations

Rating

A Bound for the Number of Different Basic Solutions Generated by the 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 A Bound for the Number of Different Basic Solutions Generated by the Simplex Method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Bound for the Number of Different Basic Solutions Generated by the Simplex Method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-333076