The Unreasonable Effectiveness of Operations Research

More

By Sanjay Saigal

On Monday, I had pointed to visibility dilemma bedeviling the profession of operations research (OR) thus:

... mentions of OR in the popular press are few and far between. Worse yet, popular media articles covering OR manage to avoid mentioning OR entirely!

On Tuesday, Steve Lohr's New York Times blog post, titled "Software Progress Beats Moore's Law," appeared. It mentioned "Martin Grotschel, a German scientist and mathematician." Over the 20-odd years that I've known Martin Grotschel, we have not discussed his primary professional affiliation. Nevertheless, even a cursory survey of his research interests will suggest that Martin is at least as much an operations researcher as he is a mathematician or an omnibus "scientist." Martin's OR expertise is entirely missing in Lohr's story. (The bias that "pure" mathematics is better, or harder, or more meaningful, than applied mathematics isn't universal, but it is pervasive. OR is application-focused. Lest I be slotted as a wannabe boiled-frog crusader, this will be my final mention of OR's branding dilemma.)

Lohr argues that improvement in the performance of software such as optimization algorithms has outpaced highly celebrated hardware speedups:

The rapid improvement in chips [...] has its own "law" -- Moore's Law, named after the Intel co-founder Gordon Moore, who in 1965 predicted that the density of transistors on integrated circuits would double every 18 months or so...

... a study of progress over a 15-year span on a benchmark production-planning task. Over that time, the speed of completing the calculations improved by a factor of 43 million. Of the total, a factor of roughly 1,000 was attributable to faster processor speeds, according to the research by Martin Grotschel, a German scientist and mathematician. Yet a factor of 43,000 was due to improvements in the efficiency of software algorithms...

But the ingenuity that computer scientists have put into algorithms have yielded performance improvements that make even the exponential gains of Moore's Law look trivial," said Edward Lazowska, a professor at the University of Washington.

My first reaction was: These don't look like Martin's results.

I have since verified my hunch via e-mail: Martin was reporting the work of his longtime associate Bob Bixby, who has advanced a more calibrated version of Lohr's argument for more than 10 years. Indeed, the performance improvement for linear optimization software has been nothing short of spectacular. Lohr's is the first recognition of this revolution that I have read in the popular press.

(To put my views in context, I did my graduate work with Bob. Years later, we also worked for the same company. However, I don't write numerical software, and I played no direct role in the results being discussed.)

Lohr mentions production planning. Such problems, technically known as mixed-integer programs, are complex variants of the steak grilling example I previously described. To get a flavor of this complexity, instead of a backyard grill, imagine an airline food-service operation that needs to turn out thousands of steak and vegetable entrees. Naturally, for such a large-scale commercial operation, lots of different grills with different capabilities are used. One grill may cook up to five steaks or 20 servings of vegetables, or any smaller combination that fits, at a time. Another may allow 12 steaks or 42 servings of vegetables, or any smaller combination. And so on. Multiple cooks staff the kitchen. Our challenge is to find a best possible sequence of grilling operations.

LucyChocolate.pngRecall that for our example we sequenced six operations -- three steaks with two sides per steak. For instance, our best possible sequence was [Steak1.side1, Steak2.side1, Steak1.side2, Steak3.side1, Steak2.side2, Steak3.side]. That yields -- you can work it out manually -- 11 meaningful cooking sequences from which to pick the fastest.

Now, depending on the specifics, the number of possible cooking sequences in a commercial kitchen -- the mathematician Paul Halmos once said at a similar point in his exposition, "we are now waving our hands" -- number in the billions. We cannot count our way out of combinatorial explosion. Such problems are often modeled as mixed-integer programs.

For Bob's representative test-set, the overall speedup was roughly 30 million-fold (not the 43 million in the extract above.) Think about that for a minute. A computation process that -- on 15-year-old technology -- would have taken a year to complete now takes one second. Bob's analysis showed that hardware improvements only accounted for a 1,000-fold speedup. Algorithmic improvements were responsible for the remaining 30,000-fold speedup.

How did it happen? How could algorithms improve so dramatically? The short answer: Bob and his colleagues combed through nearly 50 years of research in operations research and computer science. The mathematics was painstakingly tested; what looks clever on paper doesn't always pan out in practice. The techniques that tested best for speed and robustness (it is not uncommon for numerical codes to crash) made it into software.

Much of the research used came from U.S. universities. Contributions also arrived from academics such as Martin Groschel and his associates all over Europe, and yet others in Canada, Japan and elsewhere. Finally, commercial competition -- IBM Research was an early competitor but companies based in the UK and Scandinavia also figure in the story -- kept up the pressure.

Linear optimization codes usually work their magic hidden under many layers of enabling software -- databases, process workflows and business rules, a user interface, etc. Booking a family vacation online is a perfect example. Clicking on "Search" sets in motion a comparison of hundreds of thousands of itineraries involving air transportation, hotel reservations, car rentals, and tickets to child-friendly attractions. Optimization is critical, but it's only one step in a multi-step process. Even if the optimization module speeds up tenfold, the user experience improves only on the margin. Impressive as they are, the improvements should not be extrapolated, either to all optimization problems, or to all software. To that extent, Lohr's insight is less sensational than his title suggests.

Let me conclude with three observations:

  1. Without taking anything away from computational savants like Bob, this success rests on a foundation of publicly funded research going back to the fifties and sixties. Basic research remains the key to progress in technology and business.
  2. At least at the level of a sub-field, innovation is difficult to plan for or predict. In 1991, linear programming was thought to be a mature field. From 1991 through 1998, linear programming performance improved dramatically. But mixed-integer programming (its variant) remained difficult. Following a tectonic performance jump in 1998, mixed-integer programming also began to be considered practically tractable. No external pivotal event occurred in 1998; success came "overnight" due to sustained long-term effort.
  3. Branding often provides limited stickiness in niche software markets. For optimization software in particular, switching costs can be low. It's easy to benchmark performance, so businesses quickly switch to whatever gives them the edge. Tall marketing claims are rarely left unchallenged. Vendor-promised benchmarks are routinely tested and validated (or thrown out). The scientific temper of operations research creates a near-ideal competitive landscape. The progress should be attributed to a combination of openness and scientific skepticism.

Sanjay Saigal is founder and CEO of Mudrika Education, Inc., with offices in Silicon Valley, CA and Delhi, India.

Presented by

James Fallows is a national correspondent for The Atlantic and has written for the magazine since the late 1970s. He has reported extensively from outside the United States and once worked as President Carter's chief speechwriter. His latest book is China Airborne. More

James Fallows is based in Washington as a national correspondent for The Atlantic. He has worked for the magazine for nearly 30 years and in that time has also lived in Seattle, Berkeley, Austin, Tokyo, Kuala Lumpur, Shanghai, and Beijing. He was raised in Redlands, California, received his undergraduate degree in American history and literature from Harvard, and received a graduate degree in economics from Oxford as a Rhodes scholar. In addition to working for The Atlantic, he has spent two years as chief White House speechwriter for Jimmy Carter, two years as the editor of US News & World Report, and six months as a program designer at Microsoft. He is an instrument-rated private pilot. He is also now the chair in U.S. media at the U.S. Studies Centre at the University of Sydney, in Australia.

Fallows has been a finalist for the National Magazine Award five times and has won once; he has also won the American Book Award for nonfiction and a N.Y. Emmy award for the documentary series Doing Business in China. He was the founding chairman of the New America Foundation. His recent books Blind Into Baghdad (2006) and Postcards From Tomorrow Square (2009) are based on his writings for The Atlantic. His latest book is China Airborne. He is married to Deborah Fallows, author of the recent book Dreaming in Chinese. They have two married sons.

Fallows welcomes and frequently quotes from reader mail sent via the "Email" button below. Unless you specify otherwise, we consider any incoming mail available for possible quotation -- but not with the sender's real name unless you explicitly state that it may be used. If you are wondering why Fallows does not use a "Comments" field below his posts, please see previous explanations here and here.
Get Today's Top Stories in Your Inbox (preview)

What Is the Greatest Story Ever Told?

A panel of storytellers share their favorite tales, from the Bible to Charlotte's Web.


Elsewhere on the web

Video

The Death of Film

You'll never hear the whirring sound of a projector again.

Video

How to Hunt With Poison Darts

A Borneo hunter explains one of his tribe's oldest customs: the art of the blowpipe

Video

A Delightful, Pixar-Inspired Cartoon

An action figure and his reluctant sidekick trek across a kitchen in search of treasure.

Video

I Am an Undocumented Immigrant

"I look like a typical young American."

Video

Why Did I Study Physics?

Using hand-drawn cartoons to explain an academic passion

Writers

Up
Down

More in Technology

From This Author

Just In