From the Director

Doing it Better

Doug Arnold,

IMA Director

The 2002-3 IMA thematic program has a deceptively simple title: Optimization. In fact, even with seven workshops, four tutorials, a short course, two public lectures, and the constant activities of our postdocs and visitor community, the year can only concentrate on a few of the most mathematically interesting, and challenging, areas in this vast arena.

Optimization is everywhere. In almost every facet of human economic activity (and many other activities as well) there is something that you would like to do faster, cheaper, more efficiently, or otherwise better in some quantifiable sense. The question of how to do so can often be modeled as finding extreme points and values of functions of many variables over constrained domains. Such modeling often requires great ingenuity, and solving the mathematical model--finding the extreme value or something close to it in a reasonable amount of time--can be immensely challenging. It requires, and has given birth to, a great variety of wonderful mathematics.

The IMA optimization year started with a small optimization problem of its own. The opening tutorial week brought ten distinguished speakers to survey the state of the art in mathematical techniques applied to optimization problems arising in supply chain management and logistics. Arranging the schedule was itself a small scale exercise in contrained combinatorial optimization. The schedule we first devised had to be rearranged due to a speaker's outside commitment, but each time we tried to rearrange, a new difficulty would arise--two talks had to be coordinated, for example. Finally Gregory Glockner, a speaker at the tutorial and one of the developers of the ILOG Optimization Suite, solved the problem by writing a short ILOG program describing all the constraints and having it pick out the feasible schedule closest to the one originally desired.

Later in the fall, huge combinatorial optimization problems dominated. For example, Barry Smith of Sabre described the present role and future possibilities for optimization in the airline industry. The typical major US carrier offers over 4,000,000 fares a day, changing 100,000 of these daily in an effort to maximize profits, so it is easy to imagine that very sophisticated methods are needed to manage pricing, not even taking into account the many other coupled optimization problems such as fleet and crew assignment, scheduling, and routing. Another striking example was given by Cynthia Barnhart of MIT in describing her group's work on optimizing fleet assignment and routing for overnight package delivery for UPS. This led to a mixed integer programming problem with over 1,000,000,000 unknowns and 200,000 constraints! The solution of Barnhart's group, which resulted in a 25% cost saving, had some features which puzzled the experienced schedulers at UPS, such as the presence of routes in which a plane flew first west and then, after dropping off packages, turned around and flew east. The explanation of this unintuitive routing comes from the 10 AM package delivery deadline and the possibility of crossing a timezone and picking up an extra hour. This was an insight born of the optimization software that had eluded the human experts for decades.

While the fall emphasized optimization problems with discrete variables, continuous optimization was more dominant in the winter quarter. The quarter began with a very popular two-day short course on "Industrial Strength Optimization" organized by John Dennis of Rice University, who is spending the quarter at the IMA. The closing workshop of the quarter, on semidefinite programming and robust optimization, related areas where new mathematics is making major headways, is proving to be extremely popular as well. It begins with a tutorial on March 11, and continues until March 19.

Coming up in the spring are two workshops, each preceded by an introductory one-day tutorial, on applications of optimization to information technology: the design and management of efficient and robust communication networks (e.g., optimizing the Internet or a cellular phone network), and optimization techniques in data analysis and mining.