The Age of Optimization: Solving Large-Scale Real-World Problems

In the last decade, new advances in algorithms have been as important as the impressive advances in computer technology. Using the new interior-point algorithms and advanced implementations of simplex methods, we can now solve linear programs with more than one million variables and thousands of constraints. Preprocessing and polyhedral theory have yielded at least an order of magnitude improvement in branch-and-bound algorithms for solving mixed integer programs. Moreover, these algorithmic advances have been incorporated in commercially inexpensive software that is readily available, easily portable, and supported by a variety of systems that make it possible for unsophisticated users to input and check their models and obtain understandable outputs. This paper, based on the Morse Lecture given in May 1993 at the TIMS/ORSA meeting in Chicago, begins with some of the modem history of optimization, then surveys some recent developments (illustrating them with an application in the airline industry), and closes with some remarks about the future.