Tales of Statisticians: George B. Dantzig

Ah, while we try to keep taste out of math, people differ in their taste of what is really good in applied math! I'll describe some aspects of the simplex algorithm I believe are really good:

Algebraically, the simplex algorithm is just elementary row operations on a system of linear equations but the operations selected to improve the value of the objective function, that is, the quantity to be optimized, that is, made as large (or small) as possible, e.g., cost.

Geometrically the simplex algorithm works on a finite intersection of closed half spaces which, then, is a convex set with flat sides and sharp extreme points (not a convex combination of two other points of the convex set) with the extreme points joined by edges. Well, the simplex algorithm works by moving from one extreme point along an edge to an adjacent extreme point, that is, an extreme point just one edge away.

Or take a solid piece of cheese and whack at it to create a lot of flat sides. Put the cheese on a table and ask an ant to move along edges from one extreme point to another until get to the highest point on the cheese, which of course will be an extreme point.

When the simplex algorithm cycles, that is, goes through a sequence of feasible solutions and returns to an earlier one, geometrically the algorithm is staying at some one extreme point. R, Bland has a nice anti-cycling rule which, then, shows that the simplex algorithm is finite, that is, will end, as we wish, in finitely many iterations.

For min cost flows on networks, also a linear programming problem, the simplex algorithms is super-cute: One of the extreme points and a basic feasible solution correspond to a spanning tree of arcs in the network. Then, a simplex iteration adds an arc to the tree and thus creates a circuit. Then run flow around the circuit in the direction that improves the objective function value until the flow on some arc goes to zero, remove that arc from the basis, and get a new spanning tree. Darned cute. W. Cunningham has a cute modification that works with what he calls strongly feasible bases (trees) that provides an anti-cycling rule.

Cute result: For such a network, if the arc capacities are all integer and if have an initial feasible solution that is all integer, then the simplex algorithm will find only integer solutions and terminate with an optimal integer solution (if an optimal solution exists). So, get an important case of integer linear programming for free. There's money to be made here. We also just showed that there is an optimal solution that is integer.

Yes, a special case of least cost flows on networks is the transportation problem (how to ship widgets at least cost from several factories to several warehouses honoring supply and demand constraints) that won the Nobel prize in economics for Kantorovich.

Yes, for shortest paths in a network, say, from San Francisco to New York City, take the roads, call them a network, give each arc a maximum flow (capacity) of 1 and a cost per unit of flow the length of the arc, and ask for the min cost flow from San Francisco to New York. Start with any initial integer solution and then apply the network simplex algorithm. Okay? Sorry Dantzig!

Knowing that the simplex algorithm is finite yields a nice list of other results such as various theorems of the alternative important in, e.g., the Kuhn-Tucker conditions of nonlinear programming and the saddle point theorem of two person game theory.

And linear programming and the simplex algorithm are also important in some cases of nonlinear programming.

More generally linear programming and some of the properties of the simplex algorithm are nice tools for theorem proving elsewhere in pure and applied math. E.g., in Fleming, Functions of Several Variables, basically a text in advanced calculus, there is an exercise: For the real numbers R and a positive integer n, a linear function on R^n bounded above on a finite intersection of closed half spaces achieves its least upper bound. This result sounds like it would yield to, say, some compactness or completeness argument, but (AFAIK) it doesn't. Instead, deceptively, the result is combinatorial -- e.g., holds over the rationals! For the combinatorial part, use the simplex algorithm with Bland's rule. Bland discovered his rule working in matroid theory.

Work of K. Borgward showed that with meager probabilistic assumptions the simplex algorithm is polynomial or some such (I don't have the details in front of me). So, this result helps explain the good performance in practice, e.g., commonly number of iterations just 3 times the number of rows in the system of linear equations. That is, darned fast.

As I recall, the simplex algorithm was named one of the best innovations in engineering in the 20th century.