In grad school, I was lucky enough to have some especially well qualified professors of optimization including linear programming. I've applied it in business and taught it, both graduate and ugrad, in a business school. So, here I add a little to the original post:
There is no need to explain the meaning of simplex or mention that polytope. The simplex algorithm just works with a polytope and never makes any use of the fact that there can be simplex polotypes.
Or, to be more clear, "simplex algorithm" is the name of the algorithm, but there is no need to mention simplex again.
He mentioned that the feasible region might go off the paper and seemed to suggest that that could cause a difficulty. Actually, no. Instead, a linear programming problem is feasible or not. If it is feasible, then the objective function is bounded or unbounded. The simplex algorithm handles all three cases. That the feasible region is unbounded does not mean that the objective function is, and, again, even if the objective function is unbounded the simplex algorithm handles that, i.e., routinely discovers that fact and reports it.
He hints at cycling; can solve that nicely with the R. Bland anti-cycling rule. That rule is easy to program and can be used in practice but is also an especially elegant way to prove that the simplex algorithm can always work, that is, ends with the problem is feasible or infeasible and if feasible with an objective function bounded or unbounded and if bounded finds an optimal solution. That this situation is true means that we have just one baby step to showing the core saddlepoint theorem of two-person game theory, e.g., the game paper, scissors, rock.
Some of the most interesting linear programming problems are to find the least cost way to move flow through a network where each arc has a maximum flow capacity. Here the simplex algorithm specializes in an astoundingly nice way (end up working with spanning trees). But cycling is still possible. There is an elegant, easy to program anti-cycling rule in (my TeX markup for D. Knuth's TeX)
William H.\ Cunningham and
John G.\ Klincewicz,
``On Cycling in the Network Simplex Algorithm'',
{\it Mathematical Programming,\/}
Volume 26,
pages 182-189,
North Holland,
1983.\ \
Disclosure: Cunningham was one of my professors.
Why so "interesting"? Now a huge question is how to attack linear programming problems where we ask that some or all of the variable values be integers. Some well informed people regard this problem as the most important in pure and applied math and computer science. Integer linear programming was one of the examples for the importance of the computational complexity question P versus NP; to be more clear, in principle integer linear programming is in NP-complete. There are more details on this question at Clay Mathematics where P versus NP is one of their million dollar prize problems.
Well, for that network flow problem (i) if the arc flow capacities are all integers, (ii) if the problem is feasible with a bounded objective function, (iii) if we start with a feasible integer solution, then the simplex algorithm, including modified for network flows (with the spanning trees), and with an anti-cycling rule will in the simplex algorithm iterations automatically maintain a feasible integer solution and end with an optimal integer solution. In practice, this fact about integers makes a nice dent in the struggle of integer linear programming; that is, surprisingly often in practice integer linear programming problems (in principle in NP-complete) are merely just such network flow problems. Once I had that situation for a marketing resource allocation problem and another time for a NASA signal allocation problem.
The simplex algorithm can be explained nicely as just a slight tweak of standard Gauss elimination for systems of linear equations.
Indeed, the algorithm is so simple that when it ends, terminates, it is...
It would be great if the article could recommend some convenient packages for solving such problems. I’ve had some luck with the GNU linear programming kit, GLPK, myself.
It’s so amazing that I can always look to HN for interesting material for learning. Just today, I made a conscious choice to “get into” Linear Programming. Coming to find this article is simply magic.
11 comments
[ 4.8 ms ] story [ 31.4 ms ] threadMost of modern ML just extends convex optimization techniques anyway.
Linear programming didn't really "click" for me until I read Tim Roughgarden's notes:
* L7 (Intro): http://timroughgarden.org/w16/l/l7.pdf
* L8 (Duality I): http://timroughgarden.org/w16/l/l8.pdf
* L9 (Duality II: http://timroughgarden.org/w16/l/l9.pdf
http://timroughgarden.org/w16/w16.html
https://www.coursera.org/learn/discrete-optimization
There is no need to explain the meaning of simplex or mention that polytope. The simplex algorithm just works with a polytope and never makes any use of the fact that there can be simplex polotypes.
Or, to be more clear, "simplex algorithm" is the name of the algorithm, but there is no need to mention simplex again.
He mentioned that the feasible region might go off the paper and seemed to suggest that that could cause a difficulty. Actually, no. Instead, a linear programming problem is feasible or not. If it is feasible, then the objective function is bounded or unbounded. The simplex algorithm handles all three cases. That the feasible region is unbounded does not mean that the objective function is, and, again, even if the objective function is unbounded the simplex algorithm handles that, i.e., routinely discovers that fact and reports it.
He hints at cycling; can solve that nicely with the R. Bland anti-cycling rule. That rule is easy to program and can be used in practice but is also an especially elegant way to prove that the simplex algorithm can always work, that is, ends with the problem is feasible or infeasible and if feasible with an objective function bounded or unbounded and if bounded finds an optimal solution. That this situation is true means that we have just one baby step to showing the core saddlepoint theorem of two-person game theory, e.g., the game paper, scissors, rock.
Some of the most interesting linear programming problems are to find the least cost way to move flow through a network where each arc has a maximum flow capacity. Here the simplex algorithm specializes in an astoundingly nice way (end up working with spanning trees). But cycling is still possible. There is an elegant, easy to program anti-cycling rule in (my TeX markup for D. Knuth's TeX)
William H.\ Cunningham and John G.\ Klincewicz, ``On Cycling in the Network Simplex Algorithm'', {\it Mathematical Programming,\/} Volume 26, pages 182-189, North Holland, 1983.\ \
Disclosure: Cunningham was one of my professors.
Why so "interesting"? Now a huge question is how to attack linear programming problems where we ask that some or all of the variable values be integers. Some well informed people regard this problem as the most important in pure and applied math and computer science. Integer linear programming was one of the examples for the importance of the computational complexity question P versus NP; to be more clear, in principle integer linear programming is in NP-complete. There are more details on this question at Clay Mathematics where P versus NP is one of their million dollar prize problems.
Well, for that network flow problem (i) if the arc flow capacities are all integers, (ii) if the problem is feasible with a bounded objective function, (iii) if we start with a feasible integer solution, then the simplex algorithm, including modified for network flows (with the spanning trees), and with an anti-cycling rule will in the simplex algorithm iterations automatically maintain a feasible integer solution and end with an optimal integer solution. In practice, this fact about integers makes a nice dent in the struggle of integer linear programming; that is, surprisingly often in practice integer linear programming problems (in principle in NP-complete) are merely just such network flow problems. Once I had that situation for a marketing resource allocation problem and another time for a NASA signal allocation problem.
The simplex algorithm can be explained nicely as just a slight tweak of standard Gauss elimination for systems of linear equations.
Indeed, the algorithm is so simple that when it ends, terminates, it is...
Keep it simple(x)