Here is a brief summary that gives some context both for the article, and for the discussion here.
In linear programming the solution space is a convex[0] polytope[1] - the optimum is always at a vertex.[2]
The Simplex Method proceeds by:
* Finding a vertex
* While there exists a neighbour who is better, move to it.
Done.
The usual implementation doesn't even bother trying to find the best neighbour, just anyone will do. The math tells us that you never get into a dead end. In other words, if you are not at the optimum, at least one of your neighbours is guaranteed to be better, and the pivot step of the Simplex Method will find one.
You can refine the technique slightly by checking several neighbours and choosing the one that gives the greatest improvement, but in practice it doesn't save a lot of work. There is no search, no back-tracking, and no queue of points to consider. It's not Dijkstra's algorithm in disguise - it's not any kind of search.
In pathological cases it can take exponential time, but there are two ways to avoid that. One is to add a little noise, the other is to choose, from among those neighbours that are better, one at random. Other comments in this discussion give some references that go into the detail of ellipsoidal and interior point methods.
Simplex method for the win - it's simple to implement, robust, efficient in practice, and applicable to a wide range of problems.
[2] This depends crucially on the fact that this is "linear" programming. As you sweep a hyper-plane across a polytope, the last point of contact will contain at least one vertex.
[3] If you've read this far and found it useful, but want more, contact me, because I've been thinking of writing this up properly for some time.
As you point out in [2], it would be more correct to say that among the optimal solutions there is always one at a vertex of the polyhedron</nitpicking>
Also, simplex methods are very versatile when combined with other methods (see branch-and-bound for mixed integer linear optimization), but are sometimes easily beaten by barrier methods.
Excellent textbooks for LP: Chvátal [4] and Bertsimas and Tsitsiklis [5]. For mixed integer linear optimization: Wolsey [6], Nemhauser and Wolsey [7], and Conforti et al. [8].
[4] V. Chvátal, Linear Programming. MacMillan 1983.
[5] D. Bertsimas, J.N. Tsitsiklis. Introduction to linear optimization. Vol. 6. Belmont, MA: Athena Scientific, 1997.
Actually, choosing an improving neighbor at random (the random edge pivot rule) also has expected exponential worst-case behavior, see Friedman, Hansen, Zwick, Subexponential lower bounds for randomized pivoting rules for solving linear programs.
More generally, it is not known whether a pivot rule exists whose (expected) worse case running time is polynomial.
For the shadow vertex rule, it has been shown that the smoothed complexity (i.e. after perturbation of the input) is polynomial. However, the shadow vertex rule is totally impractical.
> It's not Dijkstra's algorithm in disguise - it's not any kind of search.
It's a kind of superficial statement to make: "this is not that". Obviously these things are different on the surface, but probing a bit deeper can sometimes bring similarities out. This is more interesting to me, although perhaps I am just getting old and too many neurons are interconnected and this is what makes me seek the similarities between things, instead of just saying "this is not that".
As has been noted by arghbleargh [0], the simplex method can be used to implement Dijkstra. How sure are you that the converse is not also true? Will you at least admit this is an interesting question? Or even the question of how to ask this question in such a way that it is provable/disprovable. I think this is worthwile.
Continuing to probe: Dijkstra (and dynamic programming, etc.) hinges crucially on the idea of a semiring, or generalized distributivity [1], [2]. In the case of a minimum weight path this boils down to noticing that a+max(b, c) = max(a+b, a+c). The plus distributes over the max (think of the usual distributivity: a(b+c)=ab+a*c).
Convexity also has a kind of distributivity, which can be most easily seen by taking averages: a+(b+c)/2 = (a+b)/2 + (a+c)/2. So addition distributes additively over "averages". And this formula extends to arbitrary convex combinations. My spider sense is telling me that something interesting is going on here, and there may be some more ways to link linear programming up with dynamic programming.
"How sure are you that the converse is not also true? Will you at least admit this is an interesting question? Or even the question of how to ask this question in such a way that it is provable/disprovable. I think this is worthwile."
It's an interesting question, but one which has a sad answer:
integer linear programming (and other restricted forms, such as 0-1 programming) are NP-Hard.
If you could use dijkstra's algorithm to solve them, in less than exponential time, you will have proved P=NP.
So i would go with "pretty sure".
(now, could you do it in exponential number of dijkstra invocations? Maybe? But that is, to me, not an interesting question :P
Same with could you expand the linear programming problem into an exponential size graph that was then solvable by dijkstra's algorithm - we already know that expspace is a superset of p, etc)
>> It's not Dijkstra's algorithm in disguise
>> - it's not any kind of search.
> It's a kind of superficial statement to make:
> "this is not that". Obviously these things
> are different on the surface, but probing a
> bit deeper can sometimes bring similarities
> out.
Agreed, although I was trying to answer the question as asked, and not start writing an entire essay on how instances of one type can be encoded as instances of another. MineSweeper is NP-Complete, so we can encode Hamilton Cycle (for example) in it. MineSweeper is not an instance of Hamilton Cycle, they can each be encoded in the other, this is deeply interesting, but it doesn't help someone trying to get to grips with what the Simplex Method "is". Coming to understand what it "is" is the gateway to seeing how it might, or might not, then be used to encode, and solve, other problems.
> This is more interesting to me, although
> perhaps I am just getting old and too many
> neurons are interconnected and this is what
> makes me seek the similarities between things,
> instead of just saying "this is not that".
I'm 55, and finding deep connections is (part of) what I do. Understanding that some things are genuinely different is, to me, an important place to start.
> ... the simplex method can be used to
> implement Dijkstra. How sure are you
> that the converse is not also true?
I'm pretty sure Dijkstra can be used to solve instances of Linear Programming, although the encoding is likely to be exponential. It might then be simplified by using the specific characteristics of linearity, etc, but that's not the same as saying that it is an instance of LP.
> Will you at least admit this is an
> interesting question?
Absolutely - I'm not even forced to "admit" this sort of thing. It's what I spend much of my time trying to convince other people about.
But Dijkstra is not the Simplex Method in disguise, not vice versa. Perfectly happy to say that each could (perhaps) be encoded in the other, and that doing so might turn out to be interesting. But just as finding a Hamilton Cycle is not the same as 3-Colouring a Graph, they are not the same.
> My spider sense is telling me that
> something interesting is going on
> here, and there may be some more
> ways to link linear programming up
> with dynamic programming.
I'd love to see more detailed speculations and investigations.
In summary, I suspect we are in agreement, and that you're objecting to something I didn't actually say. I don't deny that there might be, or even probably are, deep connections. But for someone trying to understand what the Simplex Method is and does, I don't think that's particularly helpful. Maybe I'm wrong - I'm pleased to wrote what you did.
In linear programming the solution space is a convex[0] polytope[1] - the optimum is always at a vertex.[2]
The Simplex Method proceeds by:
* Finding a vertex
* While there exists a neighbour who is better, move to it.
Done.
The usual implementation doesn't even bother trying to find the best neighbour, just anyone will do. The math tells us that you never get into a dead end. In other words, if you are not at the optimum, at least one of your neighbours is guaranteed to be better, and the pivot step of the Simplex Method will find one.
You can refine the technique slightly by checking several neighbours and choosing the one that gives the greatest improvement, but in practice it doesn't save a lot of work. There is no search, no back-tracking, and no queue of points to consider. It's not Dijkstra's algorithm in disguise - it's not any kind of search.
In pathological cases it can take exponential time, but there are two ways to avoid that. One is to add a little noise, the other is to choose, from among those neighbours that are better, one at random. Other comments in this discussion give some references that go into the detail of ellipsoidal and interior point methods.
Simplex method for the win - it's simple to implement, robust, efficient in practice, and applicable to a wide range of problems.
[0] https://en.wikipedia.org/wiki/Convex
[1] https://en.wikipedia.org/wiki/Polytope
[2] This depends crucially on the fact that this is "linear" programming. As you sweep a hyper-plane across a polytope, the last point of contact will contain at least one vertex.
[3] If you've read this far and found it useful, but want more, contact me, because I've been thinking of writing this up properly for some time.