0
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You might find it interesting to do a google search on Klee-Minty cube. $\endgroup$
    – Patricia Hersh
    Commented Oct 9, 2012 at 22:26

1 Answer 1

Reset to default
2
$\begingroup$

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 "interior-point" algorithms, because they traverse the interior of the simplex.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I looked into it more - you're completely right, and now I'm trying to remember why I was so sure Simplex was strongly polynomial in the first place. I may have found one of the cases on which it's exponential. I found a source that says there are no known strongly-polynomial linear programming algorithms, and the existence of such an algorithm is a major open question. Thanks for your help! $\endgroup$
    – user21816
    Commented Apr 24, 2012 at 21:45
  • $\begingroup$ I have doubts if smoothed analysis helps here. If you perturb the constraints as it is done in smoothed analysis, then none of them will go through the origin. $\endgroup$
    – Bodo Manthey
    Commented Mar 14, 2019 at 11:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .