4 ms·

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 yo

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?

ArkyBeagle 10y ago
Dunno from gradient ascent. Here's an example Simplex tableau: https://www.utdallas.edu/~scniu/OPRE-6201/documents/LP06-Simplex-Tableau.pdf https://www.utdallas.edu/~scniu/OPRE-6201/documents/LP06-Sim... I'm not sure how the Djikstra algorithm and Simplex tableaux marry.
- mathgenius 10y ago
  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.
  - ArkyBeagle 10y ago
    It's automatable. But the old saw is that anything you need Simplex to show is probably pretty obvious anyway.
Pamar 10y ago
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.
- mathgenius 10y ago
  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.
  - adrianN 10y ago
    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.
    - mathgenius 10y ago
      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.'
      - sevensor 10y ago
        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.
        bernardom 10y ago
        And a way to avoid cycles in simplex is known: https://en.wikipedia.org/wiki/Bland%27s_rule https://en.wikipedia.org/wiki/Bland%27s_rule
  - argonaut 10y ago
    You do not need to store vertices with equal value. Simplex is basically a greedy iterative algorithm - you keep moving forwards.
catnaroek 10y ago
> 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
ufo 10y ago
> 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_programming_formulation https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_p...

ArkyBeagle 10y ago

Dunno from gradient ascent. Here's an example Simplex tableau: https://www.utdallas.edu/~scniu/OPRE-6201/documents/LP06-Simplex-Tableau.pdf https://www.utdallas.edu/~scniu/OPRE-6201/documents/LP06-Sim... I'm not sure how the Djikstra algorithm and Simplex tableaux marry.

mathgenius 10y ago
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.
- ArkyBeagle 10y ago
  It's automatable. But the old saw is that anything you need Simplex to show is probably pretty obvious anyway.

Pamar 10y ago

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.

mathgenius 10y ago
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.
- adrianN 10y ago
  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.
  - mathgenius 10y ago
    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.'
    - sevensor 10y ago
      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.
      - bernardom 10y ago
        And a way to avoid cycles in simplex is known: https://en.wikipedia.org/wiki/Bland%27s_rule https://en.wikipedia.org/wiki/Bland%27s_rule
- argonaut 10y ago
  You do not need to store vertices with equal value. Simplex is basically a greedy iterative algorithm - you keep moving forwards.

catnaroek 10y ago

> 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

ufo 10y ago

> 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_programming_formulation https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_p...