If we squint a bit do we get Dijkstra's algorithm?
The simplex method literally crawls the edges of the feasible region, which is always a convex polytope. Sadly, the simplex method runs in exponential time in the number of variables. A more efficient alternative for large LP problems is interior point methods: https://en.wikipedia.org/wiki/Interior_point_method . As the name suggests, interior point methods traverse the interior of the feasible region.
To see why interior point methods are more efficient, suppose your feasible region is a convex n-gon in XY plane, for some very large n. Your initial point is the lowest vertex (least Y coordinate), and the objective function to maximize is Y, so you want to reach the highest vertex. The simplex method will literally crawl the vertices one by one until you reach the top. Interior point methods will take a more straightforward path through the interior of the polygon.
> If we squint a bit do we get Dijkstra's algorithm?
No. Dijkstra's algorithm operates on fundamentally discrete structures (finite graphs), whereas the simplex method solves linear programming problems with continuous variables (conceptually ranging over the reals, although of course on a computer one uses floating-points or some other approximate representation).
Integer linear programming, where all or some of the variables range over the integers, is also possible, but it requires extending some base LP-solving algorithm with a means to “discretize” the feasible region, such as branch and bound methods: https://en.wikipedia.org/wiki/Branch_and_bound .
> No. Dijkstra's algorithm operates on fundamentally discrete structures (finite graphs), whereas the simplex method solves linear programming problems with continuous variables (conceptually ranging over the reals, although of course on a computer one uses floating-points or some other approximate representation).
I think you've misunderestood the grandparent. Try to think of the vertices of the simplex as vertices in a graph, and edges on the simplex as edges on the graph. The (primal) simplex method chooses an entering variable by saying, "which edge from this vertex improves the objective most quickly?"
The reason the graph search doesn't turn into Dijkstra's algorithm is that we would never have any reason to backtrack. The next basis is always at least as good as the last, so we don't "get stuck" and we don't ask whether we would rather have gone another way earlier on.
EDIT:
> To see why interior point methods are more efficient...
I know they exist, but I've never seen a problem for which interior point methods are actually faster in practice. My experience isn't too deep with very large LPs, mind -- mine tend to have tens or hundreds of thousands of variables, not millions.
I wonder if there is a sharper way of putting this.
Dijkstra's algorithm doesn't backtrack either, it is always merely propagating a "wave-front" of current best vertices (and perhaps how we got there). And the simplex method will also do this when presented with a connected component of vertices all of which have the same objective value.
I feel there are some deeper connections to "dynamic programming", of which Dijkstra's algorithm is a good example. Having trouble putting my finger on it.
One obvious difference is that the Simplex method doesn't know the target vertex, whereas we do know this in Dijkstra. So perhaps the (possibly non-existent) analogy I am searching for links vertices of the Simplex method with paths in Dijkstra.
Reminds me also of using linear programming to do belief propagation and decode sparse codes.
It has been a while since I did implemented the simplex method, but I don't think this is accurate. There is only ever one basis stored. You don't need a collection of them to fix stalling/cycling.
> Dijkstra's algorithm doesn't backtrack either
I suppose this was a poor choice of language. The algorithm doesn't backtrack, but the whole point of the wavefront is to allow you to be noncommittal about which way you're going -- you explore many paths at once, something that would be very expensive to do on a simplex (where the big cost is the number of edges explored, not the number of edges on the shortest path.)
Edit: I guess you could see the simplex method as Astar with the heap key being just the heuristic (no "cost to this point" term.) Because of the structure of the graph, there's no need to keep the heap at all.
The convex n-gon is a really bad counterexample since the encoding length for inequalities describing it is Omega(n) - thus the required number of simplex iterations is linear in the input length.
Better consider the Goldfarb cube (Nina Amenta and Günter M. Ziegler: Deformed products and maximal shadows of polytopes, Contemporary Math. 233 (1999), 57-90.).
> No. Dijkstra's algorithm operates on fundamentally discrete structures (finite graphs), whereas the simplex method solves linear programming problems with continuous variables (conceptually ranging over the reals, although of course on a computer one uses floating-points or some other approximate representation).
It is equivalent to optimize over a finite set of points in Z^m or over its convex hull. The convex hull of the integer points in a rational polyhedron is a rational polyhedron again. So we just have to know its facet-defining inequalities. Sometimes these are known - for example for the problem of finding the shortest path with nonnegative edge weights (here the Total Unimodular (TU) property holds). Any step of the Dijkstra algorithms corresponds to some specific simplex iteration (or dual simplex iteration? - at least one of them). Yes, as an implementation it is faster to implement it on discrete data structures, but fundamentally it is a simplex algorithm in strong disguise.
Source: I currently do my PhD in discrete optimization.
In practice, simplex is competitive with and often beats, interior point methods.
The risk is extremely low. In fact, the risk is so low that, for deacdes, it was an open question why the simplex algorithm was so good in practice on a wide variety of workloads despite having poor worst-case complexity (unlike, for example, pure quicksort, which is often problematic in practice).
Spielman solved that problem in 2001 and showed that even very small perturbations from a contrived worst-case input have good performance: http://arxiv.org/pdf/cs/0111050.pdf
Basically you visit all vertex in sequence moving along the boundary of the solution space. As soon the result start decreasing you are done.
'But there’s an obvious risk of winding up in a “cycle” where you get back to a vertex that you already hit earlier–in which case the program will never terminate.'
Turns out that its actually the other way around! If you squint a bit you can solve the shortest-path problem with linear programming
https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_p...
https://www.utdallas.edu/~scniu/OPRE-6201/documents/LP06-Sim...
I'm not sure how the Djikstra algorithm and Simplex tableaux marry.