My 2019 Mathematics a to Z: Linear Programming

I find the lack of pictures and/or equations in this article disappointing. There are much better explanations out there.

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

He overuses the "this is obviously true; actually that is wrong" device, but it's a pretty good explanation of LP for the layman.

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.

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 easy just to read off a lot of additional, possibly valuable, information about the problem. E.g., if are mixing feed for chickens, then can learn what one more pound of corn would be worth; here we can have what some economists call shadow prices. For one more, it can be easy to change some of the original data, add some constraints, etc. and for surprisingly little additional work solve the problem again. Such work after the algorithm terminates is called post-optimality.

He didn't give any real examples; the usual first example is the diet problem for mixing feed, e.g., chicken feed, to give the chickens the nutrition they need at least total cost. I happened to have written up that problem earlier this week and posted it at

https://themusingsofthebigredcar.com/the-technology-we-dont-...

He gave no references. Here are some old but good references, just from my personal library with my markup for D. Knuth's TeX:

Va\v sek Chv\'atal, {\it Linear Programming,\/} ISBN 0-7167-1587-2, W.\ H.\ Freeman, New York, 1983.\ \

Mokhtar S.\ Bazaraa and John J.\ Jarvis, {\it Linear Programming and Network Flows,\/} ISBN 0-471-06015-1, John Wiley and Sons, New York, 1977.\ \

G.\ Hadley, {\it Linear Programming,\/} Addison-Wesley, Reading, MA, 1962.\ \

Dimitri P.\ Bertsekas, {\it Linear Network Optimization: Algorithms and Codes,\/} ISBN 0-262-02334-2, MIT Press, Cambridge, MA, 1991.\ \

Saul I.\ Gass, {\it Linear Programming: Methods and Applications, Third Edition,\/} McGraw-Hill, New York, 1969.\ \

In practice the simplex algorithm is astoundingly fast. An explanation for just why was by Karl-Heinz Borgwardt with more details and the reference at

https://en.wikipedia.org/wiki/Simplex_algorithm

But there are carefully constructed pathological problems where the simplex algorithm is very slow. The first paper on this was likely from Klee and Minty with more details at

https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube

Disclosure: Minty was one of my professors.

Since I have mentioned integer linear programming, I should include a reference, e.g. (with my TeX markup)

George L.\ Nemhauser and Laurence A.\ Wolsey, {\it Integer and Combinatorial Optimization,\/} ISBN 0-471-35943-2, John Wiley \& Sons, Inc., New York, 1999.\ \

Disclosure: At one time Nemhauser gave me three words of advice, and that was the main direction for my Ph.D. dissertation.

Yes, my references are, like the field, old.

What the future in practice is of linear programming and related applied math I don't know.

Linear programming is overlooked in most programmes but it is incredibly applicable

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.