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, linear programs with more than one million variables and thousands of constraints can now be solved. Preprocessing and polyhedral theory have yielded at least an order of magnitude improvement in branch-and-bound algorthms 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 modern 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.