Chapter notes

This chapter only begins to study the wide field of linear programming. A number of books are devoted exclusively to linear programming, including those by Chv´tal [62], Gass [111], Karloff [171], Schrijver [266], and Vanderbei [304]. Many other books give a good coverage of linear programming, including those by Papadimitriou and Steiglitz [237] and Ahuja, Magnanti, and Orlin [7]. The coverage in this chapter draws on the approach taken by Chvátal.

The simplex algorithm for linear programming was invented by G. Dantzig in 1947. Shortly after, it was discovered that a number of problems in a variety of fields could be formulated as linear programs and solved with the simplex algorithm. This realization led to a flourishing of uses of linear programming, along with several algorithms. Variants of the simplex algorithm remain the most popular methods for solving linear-programming problems. This history is described in a number of places, including the notes in [62] and [171].

The ellipsoid algorithm was the first polynomial-time algorithm for linear programming, and is due to L. G. Khachian in 1979; it was based on earlier work by N. Z. Shor, D. B. Judin, and A. S. Nemirovskii. The use of the ellipsoid algorithm to solve a variety of problems in combinatorial optimization is described in the work of Grötschel, Lov´sz, and Schrijver [134]. To date, the ellipsoid algorithm does not appear to be competitive with the simplex algorithm in practice.

Karmarkar's paper [172] includes a description of his interior-point algorithm. Many subsequent researchers designed interior-point algorithms. Good surveys can be found in the article of Goldfarb and Todd [122] and the book by Ye [319].

Analysis of the simplex algorithm is an active area of research. Klee and Minty constructed an example on which the simplex algorithm runs through 2ⁿ - 1 iterations. The simplex algorithm usually performs very well in practice and many researchers have tried to give theoretical justification for this empirical observation. A line of research begun by Borgwardt, and carried on by many others, shows that under certain probabilistic assumptions on the input, the simplex algorithm converges in expected polynomial time. Recent progress in this area has been made by Spielman and Teng [284], who introduce the "smoothed analysis of algorithms" and apply it to the simplex algorithm.

The simplex algorithm is known to run more efficiently in certain special cases. Particularly noteworthy is the network-simplex algorithm, which is the simplex algorithm, specialized to network-flow problems. For certain network problems, including the shortest-paths, maximum-flow, and minimum-cost-flow problems, variants of the network-simplex algorithm run in polynomial time. See, for example, the article by Orlin [234] and the citations therein.