News for hackers. Stuff that matters.
Re:Linear Programming: How Does It Work? by mathgenius on Monday June 06, 2016 @01:42AM (#11844878)
Wait, so this is straight up gradient ascent on the vertices of the feasable set? I always thought the simplex method was more complicated than that. I guess you do need to maintain some kind of queue of current-best vertices.

If we squint a bit do we get Dijkstra's algorithm?

Re:Linear Programming: How Does It Work? by catnaroek on Monday June 06, 2016 @01:59AM (#11844931)
> 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 . 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 .

Re:Linear Programming: How Does It Work? by repsilat on Monday June 06, 2016 @02:15AM (#11844974)
>> 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.

Re:Linear Programming: How Does It Work? by mathgenius on Monday June 06, 2016 @02:56AM (#11845095)
> 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.

Re:Linear Programming: How Does It Work? by arghbleargh on Monday June 06, 2016 @04:31AM (#11845375)
There is a linear programming formulation of the shortest path problem: see 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.
Re:Linear Programming: How Does It Work? by mathgenius on Monday June 06, 2016 @11:24AM (#11847437)
Aha, yes, this is what I was looking for. Thankyou!

Reminds me also of using linear programming to do belief propagation and decode sparse codes.

Re:Linear Programming: How Does It Work? by repsilat on Monday June 06, 2016 @11:50AM (#11847652)
> 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.

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.

Re:Linear Programming: How Does It Work? by Animats on Monday June 06, 2016 @02:15AM (#11844967)
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.
Re:Linear Programming: How Does It Work? by wolfgke on Monday June 06, 2016 @07:02AM (#11845821)
> 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.

Re:Linear Programming: How Does It Work? by brianchu on Monday June 06, 2016 @02:11AM (#11844956)
Theoretically.

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

Re:Linear Programming: How Does It Work? by catnaroek on Monday June 06, 2016 @02:15AM (#11844973)
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.
Re:Linear Programming: How Does It Work? by luu on Monday June 06, 2016 @02:37AM (#11845041)
> 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

Re:Linear Programming: How Does It Work? by Pamar on Monday June 06, 2016 @01:54AM (#11844914)
It has been decades but I think that no, you don't need a list of best-current vertices. The solutions space is convex, so you move from one solution to a better one (or are on a edge where all solutions are identical) so the moment you get to Solution N which is < of Solution N-1 you know you have just moved over the maximum and N-1 is what you were looking for.

Basically you visit all vertex in sequence moving along the boundary of the solution space. As soon the result start decreasing you are done.

Re:Linear Programming: How Does It Work? by mathgenius on Monday June 06, 2016 @02:40AM (#11845048)
You need a queue of current-best vertices when the objective function is equal best on all those vertices. Obviously you don't need to search less optimal vertices.
Re:Linear Programming: How Does It Work? by adrianN on Monday June 06, 2016 @02:58AM (#11845102)
Either you have a neighboring vertex that is strictly better than your current solution, or you have found an optimal solution. I don't think you need to store vertices with equal value, because you never backtrack.
Re:Linear Programming: How Does It Work? by mathgenius on Monday June 06, 2016 @11:21AM (#11847410)
Ok, I think I'm getting it. This line from the OP confused me:

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

Re:Linear Programming: How Does It Work? by sevensor on Monday June 06, 2016 @12:17PM (#11847882)
You only get a cycle if multiple vertices have the same objective function value. There's a similar problem of degeneracy, where you pivot back and forth between binding constraints on the same vertex and never go anywhere.
Re:Linear Programming: How Does It Work? by bernardom on Monday June 06, 2016 @12:53PM (#11848188)
And a way to avoid cycles in simplex is known: https://en.wikipedia.org/wiki/Bland%27s_rule
Re:Linear Programming: How Does It Work? by argonaut on Monday June 06, 2016 @04:17AM (#11845316)
You do not need to store vertices with equal value. Simplex is basically a greedy iterative algorithm - you keep moving forwards.
Re:Linear Programming: How Does It Work? by ufo on Monday June 06, 2016 @02:23PM (#11848995)
> If we squint a bit do we get Dijkstra's algorithm?

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

Re:Linear Programming: How Does It Work? by ArkyBeagle on Monday June 06, 2016 @01:51AM (#11844902)
Dunno from gradient ascent. Here's an example Simplex tableau:

https://www.utdallas.edu/~scniu/OPRE-6201/documents/LP06-Sim...

I'm not sure how the Djikstra algorithm and Simplex tableaux marry.

Re:Linear Programming: How Does It Work? by mathgenius on Monday June 06, 2016 @11:26AM (#11847458)
Yeah every time I go to learn about the simplex method I end up staring at these monster tables and think "woah this is complicated". But I think maybe that's just not the way to learn about this stuff, and is effectively implementation details.
Re:Linear Programming: How Does It Work? by ArkyBeagle on Monday June 06, 2016 @07:28PM (#11851334)
It's automatable. But the old saw is that anything you need Simplex to show is probably pretty obvious anyway.