5 ms·
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] poly
by ColinWright 10y ago
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.
[0] https://en.wikipedia.org/wiki/Convex https://en.wikipedia.org/wiki/Convex
[1] https://en.wikipedia.org/wiki/Polytope 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.
- merraksh 10y agothe optimum is always at a vertex 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. [6] L.A. Wolsey (1998). Integer programming (Vol. 42). New York: Wiley. [7] L.A. Wolsey, G.L. Nemhauser. Integer and combinatorial optimization. John Wiley & Sons; 2014 Aug 28. [8] M. Conforti, G. Cornuéjols, G. Zambelli (2014). Integer programming (Vol. 271). Berlin: Springer.
- nhaehnle 10y agoActually, 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.
- mathgenius 10y ago> 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. [0] https://news.ycombinator.com/item?id=11845375 https://news.ycombinator.com/item?id=11845375 [1] Aji, Srinivas M., and Robert J. McEliece. "The generalized distributive law." Information Theory, IEEE Transactions on 46, no. 2 (2000): 325-343. [2] Gondran, Michel, and Michel Minoux. Graphs, dioids and semirings: new models and algorithms. Vol. 41. Springer Science & Business Media, 2008.
- DannyBee 10y ago"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)