As head of IBM's Optimization Center, Brenda Dietrich spends her days solving some of the hardest problems known to mathematics. Optimization problems -- questions of how best to allocate resources to tasks -- come in many guises, from managing workflow in a factory to setting rates for overnight delivery services. The difficulty of the problem depends on how the tasks consume resources. The "easiest" are so-called linear programming problems. In these, Dietrich explains, "tasks consume resources at a linear rate: to do something once takes one minute; to do it 10 times takes 10 minutes." Even so, large linear optimization problems, such as the allocation of resources for a company the size of IBM, often require tailor-made solutions.
Optimization problems get especially hairy when the answer must be expressed as an integer -- that is, when a fractional answer, such as "half a worker" or "two-thirds of a widget," doesn't make sense. Solving such "integer programming" problems often requires listing all possible arrangements; outwardly similar arrangements can have radically different outcomes -- which may be so numerous that they exceed the number of particles in the universe. Much of the Deep Computing that goes on in the Optimization Center is devoted to obviating the need to list most of the possible solutions.
A classic integer programming problem that Dietrich's group works on is matching airline crews with flights. "Crew pairing," as the exercise is known, can entail a complex tour of cities, taking into account union rules, FAA regulations on how long pilots must sleep and the need to give crew members time to get from one flight to another. Most important, these schedules must cost the airlines as little overtime as possible, since pilots' salaries are the biggest expenditure an airline can control.
Dietrich's group recently solved the largest pairing problem in history. Southwest Airlines is not the biggest carrier in the world, but because its fleet consists entirely of 737s, an unusually large pool of crew members are qualified for duty on a single type of plane. Until the end of 1996, Southwest's solutions to the pairing problem were generated by an experienced worker, who was able to cut through the complexity of the problem much as a grandmaster cuts through the astronomical possibilities presented by a game of chess. The human-generated solutions were good enough, but the scheduler was working at the limits of human ability. As the airline grew, however, the monthly schedule took more than a month to compile. "So Southwest turned to IBM to put it back on schedule, after many failed attempts with other leading vendors," says Ranga Anbil, who, as manager of network logistics in Dietrich's group, specializes in airline optimization problems that involve trillions of variables.
Using standard linear programming techniques on the Southwest problem would have taken hundreds of hours, far too long to make practical decisions. So Anbil and Francisco Barahona, a researcher in Dietrich's group, came up with
an approximate solution they call the volume algorithm. "It doesn't get the exact answer," Anbil explains, "but it gets close enough that you can use it to jump-start the more standard linear programming algorithms. And that speedup was enough to allow us to solve the Southwest problem in reasonable time." When the airline hired IBM it was not looking to save money, only to generate timely schedules. Using the new system it did both, saving millions in crew costs.
Unfortunately, the Southwest solution is not directly transferable to other airlines. "The reason for that lies at the heart of Deep Computing," says Avi Harpaz, a researcher at IBM's Haifa Research Laboratory who has developed a crew-pairing program for Israel's El Al airline. "Because these kinds of problems are so difficult, you must hand-tune each one to get an optimum solution."
By using Haifa's trip-planning and crew-scheduling algorithms, El Al has been able to save 4 to 5 percent of its variable costs, such as overtime, crew transport and hotel expenses. And the benefits flow through the entire organization, Harpaz points out. As the airlines gain a better understanding of the problem, they can experiment with "what if" scenarios. At the same time, the human experts can devote time to fine-tuning the schedules produced by the program and to handling issues that are not reflected in the set of rules used by the algorithms. The scheduling programs also serve an important managerial function, allowing the airlines to calculate costs imposed by changes in work rules, such as the required rest periods between flights. Ultimately, such Deep Computing solutions not only allow a company to operate more effectively but give it the insight to make decisions it might otherwise not have considered.
Another group at Haifa has been working on personnel scheduling for call centers, a major optimization problem that it has tackled for the largest telco in Israel. The goal is to maintain a uniform level of service, but the peaks in call volume are not always predictable; moreover, the workers have to be scheduled by shift rather than by peak call volumes.
The solution, which started with the requirement that 90 percent of the calls be answered within 30 seconds, has several components, says team leader David Bernstein. First, the frequency of calls is calculated from historical data. Based on the length of an average call and factors such as the length of breaks, the number of people needed for each period is computed. Then, taking into account the number of hours a person could work, the solution finds an optimal number of shifts. Finally, people are assigned to shifts, a step that reflects individual constraints such as child care and outside classes. Thanks to the scheduling system, staff utilization is up 5 percent and the weekly planning process -- which formerly took two or three days of an expert's time -- now takes two or three hours and can be done by a nonspecialist.
Unlike weather forecasting, which can be easily divided among the processors of a parallel computer, most optimization problems are inherently serial. Anbil says the Southwest pairing program runs nicely on an RS/6000 workstation.
So what makes optimization a Deep Computing problem? For Dietrich, a problem must pass two tests: "Is it hard? And is it important?
I want to be working on important hard problems. Problems that have the potential to change the way business is done."
More information
Bruce Schechter, who has just completed a Knight Science Journalism Fellowship at MIT, is the author of My Brain Is Open: The Mathematical Journeys of Paul Erdös.
