Linear Programming: How Does It Work?
Here is a brief summary that gives some context both for the article, and for the discussion here.<p>In linear programming the solution space is a convex[0] polytope[1] - the optimum is always at a vertex.[2]<p>The Simplex Method proceeds by:<p>* Finding a vertex<p>* While there exists a neighbour who is better, move to it.<p>Done.<p>The usual implementation doesn&#x27;t even bother trying to find the best neighbour, just anyone will do.  The math tells us that you never get into a dead end.  In other words, if you are not at the optimum, at least one of your neighbours is guaranteed to be better, and the pivot step of the Simplex Method will find one.<p>You can refine the technique slightly by checking several neighbours and choosing the one that gives the greatest improvement, but in practice it doesn&#x27;t save a lot of work.  There is no search, no back-tracking, and no queue of points to consider.  It&#x27;s not Dijkstra&#x27;s algorithm in disguise - it&#x27;s not any kind of search.<p>In pathological cases it can take exponential time, but there are two ways to avoid that.  One is to add a little noise, the other is to choose, from among those neighbours that are better, one at random.  Other comments in this discussion give some references that go into the detail of ellipsoidal and interior point methods.<p>Simplex method for the win - it&#x27;s simple to implement, robust, efficient in practice, and applicable to a wide range of problems.<p>[0] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Convex" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Convex</a><p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Polytope" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Polytope</a><p>[2] This depends crucially on the fact that this is &quot;linear&quot; programming.  As you sweep a hyper-plane across a polytope, the last point of contact will contain at least one vertex.<p>[3] If you&#x27;ve read this far and found it useful, but want more, contact me, because I&#x27;ve been thinking of writing this up properly for some time.