5 ms·

> Wait, so this is straight up gradient ascent on the vertices of the feasable set? The simplex method literally crawls the edges of the feasible region, which

> Wait, so this is straight up gradient ascent on the vertices of the feasable set? 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 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 https://en.wikipedia.org/wiki/Branch_and_bound .

brianchu 10y ago
Theoretically. In practice, simplex is competitive with and often beats, interior point methods.
- catnaroek 10y ago
  Depends on the size of your problem. If you have tens of thousands of variables, you definitely don't want to risk dealing with the simplex method's worst-case behavior.
  - luu 10y ago
    > If you have tens of thousands of variables, you definitely don't want to risk dealing with the simplex method's worst-case behavior. 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 http://arxiv.org/pdf/cs/0111050.pdf
Animats 10y ago
Worst case for the simplex algorithm is exponential. Average case is polynomial. It's possible to get out of the pathological exponential case by adding some noise.
repsilat 10y ago
>> 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). 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.
- mathgenius 10y ago
  > 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. 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.
  - arghbleargh 10y ago
    There is a linear programming formulation of the shortest path problem: see https://en.m.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation https://en.m.wikipedia.org/wiki/Shortest_path_problem#Linear.... Indeed the vertices of the simplex method would correspond to paths, but I think running the simplex method on the dual formulation is more akin to Dijkstra's algorithm. Actually, I think the simplex method on the dual and Dijkstra's are equivalent, although I did not work through the details carefully.
wolfgke 10y ago
> 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. 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.

brianchu 10y ago

Theoretically. In practice, simplex is competitive with and often beats, interior point methods.

catnaroek 10y ago
Depends on the size of your problem. If you have tens of thousands of variables, you definitely don't want to risk dealing with the simplex method's worst-case behavior.
- luu 10y ago
  > If you have tens of thousands of variables, you definitely don't want to risk dealing with the simplex method's worst-case behavior. 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 http://arxiv.org/pdf/cs/0111050.pdf

Animats 10y ago

Worst case for the simplex algorithm is exponential. Average case is polynomial. It's possible to get out of the pathological exponential case by adding some noise.

repsilat 10y ago

>> 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). 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.

mathgenius 10y ago
> 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. 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.
- arghbleargh 10y ago
  There is a linear programming formulation of the shortest path problem: see https://en.m.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation https://en.m.wikipedia.org/wiki/Shortest_path_problem#Linear.... Indeed the vertices of the simplex method would correspond to paths, but I think running the simplex method on the dual formulation is more akin to Dijkstra's algorithm. Actually, I think the simplex method on the dual and Dijkstra's are equivalent, although I did not work through the details carefully.

wolfgke 10y ago

> 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. 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.