The Simplex Method

From IFORS Education Resources
Jump to: navigation, search

By: Jeff Erickson


Linear Programming Algorithms

In this lecture, we’ll see a few algorithms for actually solving linear programming problems. The most famous of these, the simplex method, was proposed by George Dantzig in 1947. Although most variants of the simplex algorithm performs well in practice, no deterministic simplex variant is known to run in sub-exponential time in the worst case.1 However, if the dimension of the problem is considered a constant, there are several linear programming algorithms that run in linear time. I’ll describe a particularly simple randomized algorithm due to Raimund Seidel. My approach to describing these algorithms will rely much more heavily on geometric intuition than the usual linear-algebraic formalism. This works better for me, but your mileage may vary. For a more traditional description of the simplex algorithm, see Robert Vanderbei’s excellent textbook Linear Programming: Foundations and Extensions [Springer, 2001], which can be freely downloaded (but not legally printed) from the author’s website.


Link to material: http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/26-simplex.pdf


Personal tools