My 2019 Mathematics a to Z: Linear Programming
In grad school, I was lucky enough to have some especially well qualified professors of optimization including linear programming.  I&#x27;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:<p>There is no need to explain the meaning of <i>simplex</i> or mention that polytope.  The simplex algorithm just works with a <i>polytope</i> and never makes any use of the fact that there can be simplex polotypes.<p>Or, to be more clear, &quot;simplex algorithm&quot; is the name of the algorithm, but there is no need to mention <i>simplex</i> again.<p>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 <i>feasible</i> 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 <i>handles</i> that, i.e., routinely discovers that fact and reports it.<p>He hints at <i>cycling</i>; 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 <i>work</i>, 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 <i>saddlepoint</i> theorem of two-person game theory, e.g., the game paper, scissors, rock.<p>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&#x27;s TeX)<p>William H.\ Cunningham and
John G.\ Klincewicz,
``On Cycling in the Network Simplex Algorithm&#x27;&#x27;,
{\it Mathematical Programming,\&#x2F;}
Volume 26,
pages 182-189,
North Holland,
1983.\ \<p>Disclosure:  Cunningham was one of my professors.<p>Why so &quot;interesting&quot;?  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.<p>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.<p>The simplex algorithm can be explained nicely as just a slight tweak of standard Gauss elimination for systems of linear equations.<p>Indeed, the algorithm is so simple that when it ends, <i>terminates</i>, 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 <i>shadow prices</i>.  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 <i>post-optimality</i>.<p>He didn&#x27;t give any real examples; the usual first example is the <i>diet problem</i> 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<p><a href="https:&#x2F;&#x2F;themusingsofthebigredcar.com&#x2F;the-technology-we-dont-see&#x2F;#comment-4652467083" rel="nofollow">https:&#x2F;&#x2F;themusingsofthebigredcar.com&#x2F;the-technology-we-dont-...</a><p>He gave no references.  Here are some old but good references, just from my personal library with my markup for D. Knuth&#x27;s TeX:<p>Va\v sek Chv\&#x27;atal,
{\it Linear Programming,\&#x2F;}
ISBN 0-7167-1587-2,
W.\ H.\ Freeman,
New York,
1983.\ \<p>Mokhtar S.\ Bazaraa and
John J.\ Jarvis,
{\it Linear Programming and Network Flows,\&#x2F;}
ISBN 0-471-06015-1,
John Wiley and Sons,
New York,
1977.\ \<p>G.\ Hadley,
{\it Linear Programming,\&#x2F;}
Addison-Wesley,
Reading, MA,
1962.\ \<p>Dimitri P.\ Bertsekas,
{\it Linear Network Optimization:
Algorithms and Codes,\&#x2F;}
ISBN 0-262-02334-2,
MIT Press,
Cambridge, MA,
1991.\ \<p>Saul I.\ Gass,
{\it Linear Programming:
Methods and Applications,
Third Edition,\&#x2F;}
McGraw-Hill,
New York,
1969.\ \<p>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<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Simplex_algorithm" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Simplex_algorithm</a><p>But there are carefully constructed <i>pathological</i> problems where the simplex algorithm is very slow.  The first paper on this was likely from Klee and Minty with more details at<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Klee–Minty_cube" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Klee–Minty_cube</a><p>Disclosure:  Minty was one of my professors.<p>Since I have mentioned integer linear programming, I should include a reference, e.g. (with my TeX markup)<p>George L.\ Nemhauser and
Laurence A.\ Wolsey,
{\it Integer and Combinatorial Optimization,\&#x2F;}
ISBN 0-471-35943-2,
John Wiley \&amp; Sons, Inc.,
New York,
1999.\ \<p>Disclosure:  At one time Nemhauser gave me three words of advice, and that was the main direction for my Ph.D. dissertation.<p>Yes, my references are, like the field, old.<p>What the future in practice is of linear programming and related applied math I don&#x27;t know.