Simplex algorithm

Summary

The simplex algorithm, introduced by George Dantzig, solves linear programs. It walks from vertex to adjacent vertex of the feasible polyhedron along edges, never decreasing the objective, until no neighbouring vertex is better. In practice it is fast. But for the usual pivot rules there are inputs, such as the Klee–Minty cubes, on which it takes exponentially many steps. The question of how few steps suffice in the worst case is linked to the diameter of polytope graphs and to the Hirsch conjecture.