From the Director
Doing it Better
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,
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