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!

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

1 Answer 1

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.

$\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
    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$ Mar 14, 2019 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.