PREMIUM SEARCH Search by job title, geography and build a list of executive contacts
Traveling salesmen know the conundrum all too well: Finding the shortest route to visit the most cities on a single trip. Even with just a few stops, enough possibilities are in that little puzzle to befuddle even the most powerful computers. There's no single answer -- the trick is to pick the one that is "best."
Decision-making problems like this abound in everyday life. They run from the simple, like finding the fastest route from New York to Boston, to the complex, like scheduling the crews for a fleet of globe-girdling airplanes. In the world of commerce, they range from routing deliveries to running factories, picking the best design for a car, or choosing which stocks to put in a mutual fund.
The task of figuring out how to make the right decision is the challenge being tackled by a small group of mathematicians delving into what is known as "operations research." Operations researchers develop computer programs that guide decision-makers toward the optimum choice. Their goal, says Saul I. Gass, a professor at the University of Maryland's Robert H. Smith School of Business in College Park, is to apply the scientific method to finding "the most efficient use and allocation of limited resources to meet desired objectives." Gass worked with early developers of modern, computer-based optimization programs that have since become important tools for business and industry to minimize costs and maximize time.
Alan Hall, contributing science and technology correspondent for Business Week Online, recently spoke with Gass and another leading operations researcher, John R. Birge, dean of the Robert R. McCormick School of Engineering & Applied Science at Northwestern University in Evanston, Ill. Birge's work focuses on methods for making decisions that must be implemented sequentially over time. He has developed methods for optimal asset-and-liability allocations, efficient scheduling of workers and machines, and power and energy distribution. Here are edited excerpts from Hall's conversations with them:
Q: What are the mathematical origins of optimization?
Birge: Calculus was really the beginning since it gives us a method for finding an optimum solution, whether maximum or minimum. The roots go back to Newton and Leibniz, the independent inventors of mathematical calculus. In fact, Leibniz's presentation of calculus was titled Nova Methodus Pro Maximus et Minimus or A New Method for Maximum and Minimum.
Q: Where were optimization techniques first used?
Birge: We find pre-20th century examples in determining best designs of fields to allow the most possible grazing land with a given amount of fence. More modern industrial examples include Frederick Taylor's analysis of early manufacturing process (described in Robert Kincaid's book, The One Best Way). Mathematical applications that coincided with the invention of the computer include initial work in the defense industries for coordinating production in World War II and subsequent adoption in the steel, oil, and chemical-processing industries.
Q: Is there one figure who stands out in developing the present theories and methods of optimization?
Gass: Yes, my PhD adviser at Berkeley in the 1960s, George B. Dantzig, who is now a professor emeritus at Stanford University. While working as a mathematician in the Pentagon for the U.S. Army during WWII, and afterwards for the newly created U. S. Air Force, Dantzig recognized that a wide class of problems could be stated in a mathematical form that he named linear programming.
A typical problem considered by Dantzig was the allocation of aircraft and pilots to combat and for training. Such problems involved many hundreds and even thousands of conditions and decision variables. These conditions could be stated mathematically in a linear way -- a line in two dimensions or a plane in three dimensions, for example. But, even though he could write the mathematics of such problems, a computational method did not exist. So, Dantzig didn't stop there. He developed the so-called "Simplex Algorithm" that has proven to be the workhorse for solving linear optimization problems.
Q: What were the first civilian uses?
Gass: What really brought optimization out in the open was its application to oil-refinery operations. Today all refineries in the West utilize linear-programming and other optimization methods to determine what products to make, such as gasoline or heating oil, and when. The decision problem is how to blend the refinery's outputs into final products that will maximize profits.
Q: Have other industries adopted it as well?
Gass: I can hardly think of a major company that does not use optimization techniques. It's a key tool at all network companies like AT&T, all shipping companies like FedEx, all the airlines, all the military services, and other government groups like the EPA and Department of the Energy. The consulting houses have groups that specialize in solving optimization problems. IBM has an optimization center in its research division.
Crop-growers and lumber companies like Weyerhaeuser plan what to plant and harvest using optimization models. Perdue Farms mixes its feed using linear programming. Companies that have used operations-research techniques range from Procter & Gamble, National Car Rental, Hewlett-Packard, and Taco Bell to American Airlines, and on and on.
Q: Some of these applications sound a bit "old hat." What's new?
Gass: The latest rage is supply-chain management (SCM). It's an attempt to integrate all aspects of an organization's buying, manufacturing, storing, and delivery of its goods. A typical user might be a national beer brewer or an automobile manufacturer.
Q: Does "artificial intelligence" play a role in optimization?
Birge: Artificial intelligence (AI) and optimization have many common origins, uses, and applications. In many software applications today, these concepts are being joined. AI generally attempts to identify principles in different contexts and put them together to find new inferences. Optimization does the same thing but uses a more general mathematical framework that allows connections that extend beyond what general-purpose AI can find.
AI can help the most in problems where there are too many options for a traditional computer program to consider. The combination of AI and optimization often can produce exceptional results by restricting the options to a manageable size with AI and then using linear programming to find the best of the remaining alternatives.
Q: Have more powerful computers and "packaged" software contributed to the popularity of optimization?
Birge: Yes, it has made optimization methods available to everyone. The "Solver" in Microsoft Excel is probably the most widespread example. This has led to a broad range of applications and uses in all industries. Earlier usage required a user to write computer code, which definitely required a higher level of skill.
Q: Does that make everyone an expert in optimization?
Gass: No, it doesn't! And there is a danger here: In formulating a linear-programming problem for a real-world problem, you have to be concerned about whether the model is a proper representation of the real-world situation. Is the model valid? It is often difficult to answer.
If the novice modeler is also the analyst is also the decision-maker is also the validator, there is a danger that the model's results will be accepted without the proper vetting. Linear programming is so easy to understand that many of those who try believe they are experts! They fail to recognize that training and expertise are necessary to make one a proper analyst. Would you let your dental hygienist drill a tooth?
Q: You seem to be saying that optimization will provide the "best" answer. We hear people talking about answers that are "good enough." What's the difference?
Gass: Mathematical optimization provides you with the best answer, the optimum. Good enough is what applying techniques of artificial intelligence can get you. It is captured in the term "satisficing" made popular by Nobel laureate economist Herbert Simon. Simon says that people cannot optimize, so set threshold values for your goals and objectives -- the solution found that satisfies them all is the winner.
Certainly, there are optimization problems that really have no single answer that everyone can agree on. They have multiple criteria. For example, what movie should we see tonight? Or, what is the best automobile to buy? Or what site should we pick for the nuclear dump? Optimization is usually not possible here because one alternative is almost never the best for all criteria. So you come up with a compromise.
Q: What's the most exciting thing you see in the future of this field?
Birge: The most exciting developments might be in the incorporation of optimization methods into real-time. An optimized automobile, for example, might coordinate traffic, atmospheric, mechanical, and surface conditions to determine optimal routes, engine performance, and guidance to bring you to your destination as efficiently, safely, and reliably as possible.
Similarly, aircraft control might be optimized to allow faster and more reliable connections with fractions of the fuel use today. Medical procedures might also be optimized in this way to enable real-time control and optimal feedback based on discovery in surgery or via radiology.
Copyright 2000, by The McGraw-Hill Companies Inc. All rights reserved.
Printer-Friendly Version
