Industry Insider: Optimization Software
Making Decisions with Precision
Saul Gass talks about how "optimization" is spreading fast
For companies and individuals, decisions come in all shades of complexity. At one end of the spectrum, a business traveler may simply need to identify the fastest way to get from New York to Boston. At the opposite extreme, an airline faces mind-boggling scheduling challenges each time it shuffles crews on its international fleet.
Optimizing such tasks is the mission of a small group of mathematicians in a discipline called Operations Research. Their goal, says Saul I. Gass, a professor at the Robert H. Smith School of Business at the University of Maryland 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 has the right credentials for this mission. He holds degrees in mathematics and engineering and has worked in both the military and industry. He is the author of numerous technical articles and several texts on linear programming, which is the computing method employed in optimization. He is co-editor of the Encyclopedia of Operations Research & Management Sciences and has served as vice-president at the Institute of Operations Research & Management Sciences (INFORMS).
Alan Hall, contributing science and technology correspondent for Business Week Online, recently spoke with Gass about optimization. Below are excerpts from their conversation.Q: Your work goes under the broad name of operations research. What is that?A: Operations research is the application of the methods of science, mostly mathematics and statistics, to complex problems arising in the direction and management of large systems of people, machines, materials, and money in industry, business, government, and defense. Basically, it is a scientific method for providing a basis for making a decision.Q: We hear the term "optimization" a lot lately. Would you explain it?A: We have a "decision problem" when we have to make choices. We are at the proverbial fork in the road. Which route should I take to work to minimize my travel time? A decision problem requires you to choose the "best solution"--the optimal one--from among the competing alternatives.Q: Can you give me an example of a modern "decision problem"?A: The military has to decide how to organize its divisions to meet future threats. This is usually accomplished by describing the problem mathematically and asking: "From among all possible solutions, which one maximizes profit or minimizes cost or minimizes time?"Q: Is there one figure who stands out in developing the present theories and methods of optimization?A: Yes, my PhD adviser at [U.C.] Berkeley in the early 1960s, George B. Dantzig, who is now a professor emeritus at Stanford University. While working as a mathematician in the Pentagon for the Army during World War II, and afterwards for the newly created Air Force, Dantzig recognized that a wide class of problems can 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. These conditions could be stated mathematically in a linear way: a line in two dimensions or a plane in three dimensions. But even though he could write the mathematics of such problems, a computational method did not exist. So Dantzig developed the so-called simplex algorithm that has proven to be the workhorse for solving optimization problems. Dantzig's group got the second UNIVAC I computer in June, 1952, with the first one going to the Census Bureau.Q: What were the first civilian uses?A: What really brought optimization out in the open was its application to oil refinery operations. Today, all refineries in the West utilize optimization methods to determine what products to make, such as gasoline or heating oil, and when. The objective is to find how to manage refinery outputs to make final products that will maximize profits.Q: Have other industries adopted it as well?A: 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 the Energy Dept. The consulting houses have groups that specialize in solving optimization problems. IBM has an optimization research group.
Crop growers and lumber companies like Weyerhaeuser plan what to plant and harvest using optimization models; Perdue Farms mixes its [chicken] 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: Scheduling plantings and booking airline seats or hotel rooms are tasks we've been facing for ages. What's new?A: Optimization has been used to schedule deliveries for over 40 years, especially truck delivery and pickup. The latest rage is supply chain management (SCM). It's an attempt to integrate all aspects of an organization's buying, storing, manufacturing, and delivery of goods. A typical user might be a national beer company or an automobile manufacturer.Q: Have more powerful computers and packaged software contributed to the popularity of optimization?A: Certainly. SCM software now exists that integrates many applications, such as vehicle routing. The optimization is sort of hidden here but key to it all. Commercial software has enabled us to solve larger and more complex problems. And it's working in a lot of places most people don't suspect. For example, the simplex algorithm is now an add-on in all the major spreadsheets, such as Lotus 1-2-3 and Excel. This makes the algorithm available to the novice linear programmer.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?A: Mathematical optimization is the best. Engineers love it. "Good enough" is what applying techniques of artificial intelligence gets you. It is captured in the term "satisficing," made popular by Nobel laureate economist Herbert Simon. Simon says that people cannot really optimize, so set threshold values for your goals and objectives; the first solution found that satisfies them all is the winner.
Certainly, there are some optimization problems that really have no single answer that everyone can agree on. For example, what movie should we see tonight? Or, what is the best automobile to buy? 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 ahead?A: I think integrated optimization procedures like SCM will become standard, and just about all businesses will stress the need to perform in an optimal manner. In the future, we will see real-time SCM systems. For example, a real-time production system will take in customers' orders as they arrive and reschedule production to meet past and current demands, so the producer's profits are maximized.
The payoff could be enormous. Just take air travel. Airlines will be able to reroute and reorganize flights in real time after a weather disruption. The Federal Aviation Administration will be able to route individual flights in real time to take advantage of changing traffic and weather and available gates at individual airports. Optimization is here to stay!Return to top