D. R. Fulkerson Lectures

Airlines don't schedule without "it", refineries don't produce gasoline without "it", and Wall Street is investing in "it". "It" is optimization. The evolution of powerful operations research algorithms — key among them algorithms for linear and integer programming — together with ever more powerful computers has brought the application of optimization to the desktop. Industry after industry is exploring ways to take advantage of this family of techniques to reduce cost and increase profitability.

We will examine the computational state-of-the-art in linear and integer programming and the ideas that, over the past twenty years, have led to over six orders of magnitude increase in solving power. The result of this increased power is that many problems once considered unsolvable, now are solvable, often in a matter of minutes.

Implementing Simplex Algorithms

Wednesday, April 23, 2008 ● 4:30 p.m. ● B17 Upson Hall

The simplex algorithm for linear programming was introduced by George Dantzig in 1947. It has become one of the most important and most-used algorithms in applied mathematics. For a time, however, it appeared that it would be eclipsed as a computational tool by the methods that emerged after the appearance of Karmarkar's seminal paper on interior point methods in 1989. That has not happened. Further computational developments in implementing simplex algorithms, and most particularly the emergence of the dual-simplex algorithm, have re-established the leading role of these algorithms in the practical application of linear programming. We will describe some of these developments.

From Planning to Operations: The Ever-Shrinking Optimization Time Horizon

Friday, April 25, 2008 ● 3:30 p.m. ● B17 Upson Hall

(Sponsored jointly with the Center for Applied Mathematics)

Operations research techniques such as linear and integer programming have not reached their full business potential. One reason is that they have traditionally been applied to long-term planning models, where the gap between the solutions provided and the actual execution is often quite large. As a result, the impact on the enterprise is sometimes not directly visible to all affected entities. Moreover, these models are often used only once, even where repeated use was intended, again limiting their impact.

That landscape is changing. Startling improvements in our ability to solve linear and integer programs along with improved data access and automated business processes offer the promise of making optimization tools a more central part of the management of the modern enterprise. Increasingly, optimization solutions are being applied at the operational level, solving core business problems, providing real-time solutions to more detailed models. In this talk, we will describe several such success stories.