Is the Simplex Method still polynomial when all inequalities are through the origin?

2012-04-24T20:47:16Z

Hello,

I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, or the program is unbounded; I'm only really interested in distinguishing between these two cases).

So here's how I think the algorithm would work: Step one is to pick a pivot variable. Step two - and here's where I think things break down - is to find the equation with the smallest value of the constant to the coefficient of the pivot variable. But since my inequalities all pass through the origin, the constant is 0 every time, so all equations are an equally valid choice for the pivot. This reduces the Simplex Method to a brute-force search of the set of basic variables, which would make it run in above-polynomial time.

Is this correct? Or am I missing some feature of the Simplex Method that handles this case?

Thanks in advance!

Answer by Pascal Maillard for Is the Simplex Method still polynomial when all inequalities are through the origin?

2012-04-24T21:29:51Z

As far as I can recall, the Simplex Algorithm is not running in polynomial time, although when randomly perturbing the input, it runs on average in polynomial time (this is also studied under the name "Smoothed Analysis of Algorithms", see for example the article by Spielman and Teng, Journal of the ACM, Vol. 51, No. 3, May 2004, pp. 385–463 http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CC0QFjAA&url=http%3A%2F%2Fwww.cs.duke.edu%2Fcourses%2Fspring07%2Fcps296.2%2Fpapers%2Fp385-a_spielman.pdf&ei=6BmXT7GONuas0QXig_2yDg&usg=AFQjCNE5PFNqSIUgHjNdVys2dX_drjkUAg&sig2=ItkEJelYbgxu-yO6NOuidA

There are however algorithms for linear programming which run in polynomial time, known as "inner-point" algorithms, because they traverse the interior of the simplex.

Is the Simplex Method still polynomial when all inequalities are through the origin? - MathOverflow

Is the Simplex Method still polynomial when all inequalities are through the origin?

Answer by Pascal Maillard for Is the Simplex Method still polynomial when all inequalities are through the origin?