Category: OR in the Press

Algorithms in the Attic

The February 2007 issue of the Harvard Business Review has an article on “Breakthrough Ideas for 2007” (sorry, pay-only link: HBR isn’t much for making stuff available for free). One of the breakthrough ideas is given by Michael Schrage of the MIT Media Lab under the title “Algorithms in the Attic”, a play on the title Rembrandts in the Attic, a book on unlocking the value of patents (for better or worse). Schrage argues:

For a powerful perspective on future business, take a hard look at mathematics past. As computing gets ever faster and cheaper, yesterday’s abstruse equations are becoming platforms for tomorrow’s breakthroughs. Companies in several industries are now dusting off these formulas and putting them in the service of new products and processes.

Examples Schrage cites are include:

Procter & Gamble has been restructuring its supply chain with complex “expressive bidding” algorithms–based on 1950s linear-programming equations– that allow suppliers to bid online with bundled offerings of products and service levels rather than with standardized lots. Google’s search engine was possible only because the founders adapted a century-old theorem about matrices to software for ranking Web pages according to links from other sites. Networks like the Web can be expressed as matrices, and a relatively simple calculation gives a ranking of how well each site is connected to the rest of the Web. That formula for automatic ranking – which could be understood and appreciated without a PhD – is one of the most lucrative algorithms ever. The math was there for the taking.

Well-known OR researcher Dick Larson gives a nice quote:

“There are huge hidden assets in the operations-research community,” says the MIT professor Richard Larson, a pioneer in probabilistic modeling techniques. “If you gave an army of 20 grad students the mission to rake through the published literature of the past 30
years, they would find stuff that has untapped business potential worth billions
of dollars. There are many clever ideas my students worked on decades
ago that in today’s networked environment would not be an academic exercise
but a real business opportunity.”

Schrage concludes:

Whether looking for breakthroughs or just trying to improve decision making, companies will benefit from greatersophistication around even simple mathematics. A decade ago, big firmsbegan to realize that they were sitting on a treasure trove of underutilized patentsand know-how that could be commercialized for willing buyers. Those “Rembrandts in the attic,” as Kevin G.Rivette and David Kline put it in their 2000 book by that name, needed thekeen eye of an intellectual property curator to appreciate their value. Similarly, we now require quantitative entrepreneurs to seek out existing equations that meet today’s pressingbusiness needs. Technology continues to make that quest faster, easier, and cheaper.

Hmmm…. thinking over my past research doesn’t immediately lead to thoughts of business opportunity, but maybe it is time to pull out those dusty journal articles.

Linda Green on OR in Healthcare

Linda Green of Columbia University was here (Auckland) today and gave a talk on the use of operations research in the health care industry. Most of her presentation was on simple queueing models to gain insight into capacity and scheduling for healthcare. Some of this work has recently been covered in Business Week. One simple “Queueing 101” result that people just don’t understand is that a queueing system with 85% utilization, say, is not 15% inefficient. In fact, this value is the rule of thumb many hospital administrators use to determine optimal intensive care unit (and other hospital unit) sizing. But such a utilization can lead to 10% or more of the patients arriving with no beds for them! The exact number depends on the variability and other statistical measures of the arrival and service processes but aiming for 95% utilization (as some hospitals and districts do) is foolish and dangerous: it will lead inevitably to many turned away (or choosing to leave without being seen, leading to more critical later issues). The world would be a much better place if more people understood some of the basic insights that OR provides.

NCAA Tournament and Operations Research

Final Four LogoIt is time again for the year’s best sports event: the NCAA college basketball tournament. 65 teams in a single elimination tournament held over 3 successive weekends, with the winner taking all. Picking the teams for the tournament is a favorite conversation topic over coffee and beers (not that most of us can distinguish among the 336 eligible teams!). Joel Sokol, Paul Kvam and my research and business partner George Nemhauser have a system entitled the “Linear Regression/Markov Chain” (LRMC) to rank teams. You can get the pre-tournament rankings here. These rankings suggest that the four top teams in the land are North Carolina, Kansas, UCLA, and Texas A&M. The tournament committee picked Ohio State and Florida (number 5 and 6) instead of UCLA and Texas A&M.

If you are filling out your bracket, you can use the rankings to guide you (just pick the highest ranked team at each step). As an article in the Atlanta Journal Constitution writes:

LRMC’s most striking predictions this year: Picking No. 12 seed Arkansas over No. 5 seed Southern Cal and No. 10 seed Georgia Tech to knock off No. 7 seed UNLV.

The tournament committee this year had access to LRMC:

Nemhauser, a former Tech faculty athletics representative, arranged to provide a special version of LRMC to the selection committee for the first time this year. (The committee wouldn’t look at a ratings system that considered victory margin, so it got one with that component factored out.)

“It’s certainly one tool people could look at,” committee chairman Gary Walters said, but he went on to praise the RPI and the Sagarin ratings and to call the RPI “our primary quantitative tool.”

It will be interesting to see how some of the predicted upsets work out: perhaps the tournament committee will need a new primary quantitative tool.

Optimizing Airline routes

Thanks to Chad, a Tepper MBA student, who pointed out the the Wall Street Journal of March 6, 2007 has an article on optimizing international airline routes. It turns out that countries have complicated costs for airplanes flying in their space, and rerouting the planes can lead to pretty significant savings (on the order of $1,400/flight, which multiplies out to millions per year). From the article:

The formulas countries use to compute their overflight fees vary widely. Cameroon, in Africa, bases its charges on the maximum takeoff weight, with an international flight passing over the country paying from €102 to €204 ($134 to $267). Canada assesses 3.6 Canadian cents (3 U.S. cents) times the distance flown times the weight of the aircraft, plus C$97 per flight for air-traffic control coverage over the North Atlantic. United Kingdom overfly rates are three times as high as Ireland’s rates, and German rates are at least twice as high as Canada’s, according to international aviation specialists.
The U.S. funds its air-traffic-control system differently. Instead of flyover fees, passengers pay multiple taxes to the airlines, which pass the money on to a trust fund. On domestic flights fliers pay 7.5% of the cost of the ticket, plus $3.40 for each flight segment. Passengers on international flights pay $15.10 in fees for coming into and leaving the U.S. Minimizing overflight fees must be balanced against additional fuel costs if an alternative route is less direct. The software systems track a slew of additional data: weather; airport locations and runways; weight and performance of each airplane in the carrier’s fleet; temporarily blocked airspace and the locations of fixed air routes, which change daily due to winds.
The computers churn through multiple scenarios, including minimum time, minimum fuel and minimum cost, and determine which is the best solution for the maximum payload, given up-tothe-minute wind and weather information.

It is surprising the savings possible:

British Airways in 2003 finished installing such software on its route network, replacing a homemade system that one pilot describes as “a blunt instrument.” As a result, it has drastically changed the routing of its Sao Paulo-London flight. Instead of flying in a straight line and crossing over Portugal, Spain and France before entering U.K. airspace, the airline now takes a northerly track over the Atlantic and enters the U.K. over Cornwall. Capt. Tim de la Fosse, BA’s general manager of flight technical, says the new path saves £3,000 ($5,767) per one-way flight in European overfly fees, uses one fewer ton of fuel and is 18 minutes shorter in duration.

The BBC and queues

The BBC has an economics editor named Evan Davis who has a blog on understanding the real world using the tool kit of economics. There are two recent entries (here and here) on queueing results. Now the English are famous for their queueing discipline, but Davis is concerned with two examples of “non-obvious” queues: road congestion and waits for health services. In both cases, there are significant costs to queueing and the economic effect is that since people enter the queue only when the benefit of the service outways the cost of queueing, many people end up with very little value (the queue increases to wipe away the consumer surplus). This is a nice example of combining economics with operations research (many OR models have very simple queue entry rules, like “will enter always” or “will enter only if queue size <=12"), but using economics to guide the consumer behavior leads to better insights. Davis shows his economist (not OR!) training in stating the following:

There are three very simple rules about queues.

• 1. They grow longer when the number of people joining at the back of the queue exceeds the rate at which people are being dealt with at the front.

• 2. They grow shorter when the rate at which people are dealt with at the front exceeds the rate at which people join at the back.

• 3. They stay constant when the flow of new arrivals is equal to the flow of people being seen.

It is the last point that is incorrect, assuming there is any variation at all in either service or queue entry. If flow of arrivals equals flow of people being seen, the queue will continue to increase (on average). This point is actually very important. Managers are constantly being told to look for inefficiencies, and having more service than customers looks like an inefficiency, so they work at getting service = customers. The result is long queues (unless there is no variation in service or queue entry). Unless there is slack in the system, the system doesn’t work.

Davis does mention Operations Research (surprisingly: Operational Research would be more “british”):

Queuing theory is in fact, quite a science. It comes up in the discipline of Operations Research, which studies processes, production and organisations using maths, statistics, economics and management science. It’s a fascinating subject.

The “It’s” in the last sentance is unclear. I’ll take it to mean that “Operations Research is a fascinating subject”, which is certainly the case.

Brenda Dietrich in Fast Company

Brenda Dietrich,  President of INFORMS and head of Math Sciences at IBM Watson Research is profiled in Fast Company this month.  Some wonderful stories:

If you’re not a mathematician, the deep math that Dietrich and her team perform sounds utterly foreign–combinatorial auctions, integer programming, conditional logic, and so on. Their whiteboard scribbles at Watson look incomprehensible, like Farsi or Greek (then again, many of the symbols are Greek). But these mysterious equations represent the real world and how it works. When mathematicians “model” a problem, they’re creating a numerical snapshot of a dynamic system and its variables.

Take the forest-fire project Dietrich and the researchers are working on. Extinguishing fast-spreading flames over tens of thousands of acres is an expensive and complicated undertaking. In 2000, a particularly devastating year, the federal government spent more than $1 billion and still lost more then 8 million acres. Its fire planners want to reduce the cost and the damage through better coordination among the five agencies involved.

Armed with seven years of data, IBM’s mathematicians are creating an enormous model that shows how the resources–every firefighter, truck, plane, etc.–have been used in the past, how much each effort cost, and how many acres burned. The algorithms describe the likely costs and results for any number of strategies to combat a given fire. “How many bulldozers and buckets do you keep in Yellowstone Park?” Dietrich asks. “And if you need to move them elsewhere, how much will it cost and how long will it take?” She’s talking fast, describing the unruly variables that math makes sense of. “It’s a nice project. Complicated, huh?”

It is too bad that Brenda is described as a mathematician (which she is) rather than the more specific and accurate “Operations Researcher”.

Do Operations Research, win $1 million

Art Geoffrion wrote me, pointing out that the Netflix Prize is a great opportunity for OR people to show their stuff. Netflix is offering up to $1 million for a system that predicts whether a customer will like a movie or not. They have made available a wonderful database of 100,000 ratings. Lots of people have used data mining methods on this database For me, the line between data mining and OR is very thin indeed, so it would be interesting to see what an OR approach can do with this.

The Wall Street Journal has an article on these types of prizes. There are a lot of good reasons for companies to provide these competitions:

Prizes prompt a lot of effort, far more than any sponsor could devote itself, but they generally pay only for success. That’s “an important piece of shifting risk from inside the walls of the company and moving it out to the solver community,” says Jill Panetta, InnoCentive’s chief scientific officer. Competitors for the $10 million prize for the space vehicle spent 10 times that amount trying to win it.

Contests also are a mechanism to tap scientific knowledge that’s widely dispersed geographically, and not always in obvious places. Since posting its algorithm bounty in October, Netflix has drawn 15,000 entrants from 126 countries. The leading team is from Budapest University of Technology and Economics.

Given the generality of OR, it is clear that our field can be competitive in many of these. Any takers?

Quant at Barclay’s Global Investors

Business Week has an article on how Barclay’s Global Investors has hireed more than 100 Ph.D.s in quantitative areas to define its investment strategies. The article discusses the advantages of quantitative investing:

In traditional circles, quant has been derided as “black box” investing for its reliance on computer models comprehensible only to the double-domes who created them. The black box survives today in the more mystifying form of investing techniques derived from fuzzy logic, neural networks, Markov chains, and other nonlinear probability models.

As epitomized by BGI, though, modern quant investing is grounded in the same economic fundamentals that preoccupy mainstream analysts, though quants amass much more data and massage it more systematically than anyone else does. Another key difference is that quants ignore the story behind the numbers. The whole sprawling human drama of business is of no interest to Barclays researchers, who never venture out to call on a company or tour a store or a factory. If a thing cannot be measured and factored into an investment hypothesis for testing against historical data, BGI has no use for it.

Quants also are far more mindful of risk, as measured mainly by price volatility. Traditional portfolio managers tend to heighten risk by concentrating their investments in a relative handful of companies that they believe will beat the market averages over the long run. Instead of angling to get in early on the next Wal-Mart (WMT )or Microsoft (MSFT ), BGI spreads its bets across a broad market swath, frequently trading in and out to exploit small pricing anomalies. The firm’s $19.9 billion in alpha represents just 1.64% above the market return, on average.

It is in a discussion of a presentation by one of the researchers, Xiaowi Li, that it is clear the breadth of skills that can go into this sort of work:

Gathered around a table in a small conference room on the 28th floor of BGI headquarters were a half-dozen of Li’s peers, plus her manager and the co-heads of the overall Asian research effort, Ernie Chow and Jonathan Howe, both of whom joined BGI in 1999 and were the fortysomething graybeards of the group. Everyone in the room had either a PhD or a master’s degree in financial engineering. The disciplines represented included physics, applied mathematics, and operations research, as well as finance and economics.

Nice to see operations research mentioned without need for further definition.

OR and Air Security

Operations research has been getting a lot of press recently due to a study about the effectiveness of “no-fly” lists in preventing terrorism. Long-time researcher of airline safety, Arnie Barnett along with Harvey Mudd professor Susan Martonosi found, using OR models of course, that it is best to screen all passengers, rather than try to pre-screen so-called safe passengers. Here are some excerpts from the LA Times:

Operations research is a little-known but valuable tool for such things as scheduling airline flight crews, planning National Football League seasons and even designing waiting lines at Walt Disney World. And in a report released on Monday, it was used to assess the effectiveness of the nation’s security screening of airline passengers.

Using a mathematical model, Susan E. Martonosi, an assistant professor of mathematics at Harvey Mudd College in Claremont, and Arnold Barnett, a professor of management science at MIT, sought to explore the effectiveness of the “no-fly” lists in preventing terrorism. The conclusions they reached were less remarkable perhaps than the way they evaluated the program.

They found that improving the screening required of all passengers at security checkpoints would do more to enhance security than further refinements to the pre-screening of passengers by no-fly lists.

Here is a presentation on the topic.  Check out your December issue of Interfaces for the full paper, along with a number of other papers on homeland security.