Category: OR in the Press

Canadian Algorithms, eh?

The Globe and Mail, Canada’s answer to the New York Times, has an article on “algorithms” in their technology section (thanks Dad for the pointer!).  They give a number of very good examples of work being done by Ontario researchers that illustrates the range of application:

For example, Dr. Terlaky [director of McMaster University’s School of Computational Engineering and Science in Hamilton, Ont] says his school and a team from the University of Waterloo are working with oncologists from Toronto’s Princess Margaret Hospital to find the optimal level of radiation that can be used in treating liver cancer.

“We are working with Dr. Laura Dawson, a PMH oncologist, to find out how much radiation is most effective,” he says.

“Laura Dawson doesn’t understand the math but she doesn’t need to. She knows the treatment – we know the math.”

The drivers behind all this are faster computers and more data:

What has propelled the giant leaps forward in creating mathematical formulas to increase accuracy is a happy combination of data and computing power.

The data becomes the basis for analysis; the more of it available to sift through, the greater the accuracy.

The power and speed of today’s computers means computational tasks that would have taken decades in the 1990s can be done in a matter of minutes today.

“Today, thanks to computational science we can produce huge savings for industry, more effective diagnosis and treatment for medicine, better design for products and better management of resources,” Dr. Terlaky says.

“These great advances come at a time when almost all organizations have accumulated masses of data,” says Rotman’s Dr. Baron, associate professor of operations management. “It becomes historical data which can be analyzed to predict the future.

“Mathematical models are bound to play a greater role in business and even personal decision making,” Dr. Baron predicts.

I suppose I could go off complaining that the words “operations research” are never used, but instead I will be happy that a few million Canadians know a bit more about our field today.

Playing “Pass the Kidney”

Kidneys are unusual organs. We are given two, though we can get by with one. So, unlike the heart, say, we each have a “spare” that we can donate to others. There are some altruistic sorts who will donate a kidney to a stranger, but, for most of us, we need a really good reason before we undergo the surgery to remove a kidney. That reason is typically the need of a loved one for a replacement kidney. But what to do if the transplant won’t work due to blood type or other medical incompatibilities? Well, if my kidney won’t work for my brother, then perhaps it will work for stranger A, who has a sister whose kidney does work for my brother. We can then swap: I give a kidney to A, whose sister gives a kidney to my brother. Such is the logic behind kidney swapping. The Wall Street Journal of October 15, 2007 has an article on these swaps (thanks to Tallys at the University of Miami for pointing this out to me!). Clearly they are important aspect of kidney transplants:

Some experts estimate that eventually there could be as many as 4,000 kidney exchanges a year. That would be a big addition to the 6,400 kidney transplants performed last year involving living donors. An additional 10,600 transplants involved kidneys from deceased donors. Waits for organs from deceased donors can run to five years or more.

But there is an operations research question:

As interest in kidney swaps grows, logistical, medical and ethical questions are emerging. One of the fundamental issues: Who should get first dibs on a match? A donor with blood type O, for instance, can give to patients of any blood type and might match with hundreds of pairs. One combination might allow for two transplants; another, for 10, because it allows other matches to occur, in a kind of domino effect.

This is an interesting problem, though even more interesting when one considers the objective. Do you aim for cycles of length 10, since it allows for lots of transplants? Or do you go with shorter cycles, since they are less likely to be complicated by individual issues? In fact, the rest of the article is about a particular kidney patient and her experiences in trying to arrange for a swap. There were all sorts of issues related to the quality of the kidney she was to receive, the geographic location of the donors, the health of other recipients and so on. The group she ended up with had 3 donors and 3 recipients: a longer cycle would have increased these issues.

A key issue in this area is the population used to find the paths. The network’s currently are ad-hoc, based, it appears, on individual surgeons and hospitals.

Complicating the picture: transplant surgeons, some of whom are highly competitive and focused on their own programs rather than joining networks with other hospitals. “When big egos come together, sparks fly,” says Bill Bry, surgical director of kidney transplantation at California Pacific Medical Center in San Francisco. An Ohio paired-donation network recently split into two when surgeons quarreled.

I suspect that surgeons don’t truly understand that cutting a population in half doesn’t merely cut the probability of a cycle in half. The probability of pairwise exchanges (two donor/recipient pairs) goes down to one-quarter: I am sure some combinatorialist knows the effect on the probability of longer cycles, but I suspect it decreases further.

The term operations research is not mentioned, but the techniques clearly are OR methods. In fact, I get a shout-out, though not by name

In the early kidney swaps, surgeons matched pairs using a pencil and paper or by moving magnetic pieces around on a board. Today, computer experts, working with economists, are developing programs to “optimize” matching, to enable the greatest number of transplants. They’re employing mathematical techniques used for major-league baseball schedules, airline departures and online driving directions.

Perhaps we should rename the field of operations research (OR) to be “the techniques that create baseball schedules” (TCBS). But I think helping facilitate kidney transplants is a little more important than making sure the Yankees get enough summer weekends at home.

UPDATE (Oct 17). Pascal van Hentenryck has alerted me to a CMU connection to this story:

PITTSBURGH—Computer scientists at Carnegie Mellon University have developed a new computerized method for matching living kidney donors with kidney disease patients that can increase the number of kidney transplants—and save lives.

This step-by-step method, or algorithm, could significantly boost the efficiency of kidney exchanges, a mechanism for matching live donors with unrelated recipients. Kidney exchanges are now considered the best chance for boosting the number of kidney transplants in the United States. More than 70,000 Americans are on the waiting list for kidney transplants and about 4,000 die waiting each year.

Tuomas SandholmThe matching algorithm makes it possible to create matches for three- and four-way exchanges—that is, three or four donors matched to three or four recipients—as well as two-way exchanges. It is the first that is scalable so it can be used for a national pool of donors and recipients, said Tuomas Sandholm, professor of computer science.

A paper detailing the algorithm, developed by Sandholm, Computer Science Professor Avrim Blum and graduate assistant David J. Abraham, will be presented Friday at the Association for Computing Machinery’s Conference on Electronic Commerce in San Diego.

 

Operations Research in the Caymans?

Through the magic of “Google Alerts“, I get email every time “operations research” (and a bunch of other terms, some of which are none of your business) appears in the press. I was delighted to see an article in the Cayman Net News about operations research. While we love New Zealand, I will say our first choice was a sabbatical year in the Caymans. But that sounded a little too “recreational”. This was clearly just a failure of imagination. So, Tracy Hargrave, thanks for the OR plug, and if you need a lecturer to explain OR down there, just drop me a note!

Algorithms and the Economist

Economist logoThe Economist, in its September 13th issue, has a nice article on how businesses use algorithms to work better. From the introduction:

ALGORITHMS sound scary, of interest only to dome-headed mathematicians. In fact they have become the instruction manuals for a host of routine consumer transactions. Browse for a book on Amazon.com and algorithms generate recommendations for other titles to buy. Buy a copy and they help a logistics firm to decide on the best delivery route. Ring to check your order’s progress and more algorithms spring into action to determine the quickest connection to and through a call-centre. From analysing credit-card transactions to deciding how to stack supermarket shelves, algorithms now underpin a large amount of everyday life.

They have a number of very nice examples, including UPS:

For its fleet of aircraft in America, the company uses an algorithm called VOLCANO (which stands for Volume, Location and Aircraft Network Optimiser). Developed jointly with the Massachusetts Institute of Technology (MIT), it is used by three different planning groups within UPS—one to plan schedules for the following four to six months, one to work out what kind of facilities and aircraft might be needed over the next two to ten years, and one to plan for the peak season between Thanksgiving and Christmas. Getting the scheduling wrong imposes a heavy cost: flying half-empty planes or leasing extra aircraft is an expensive business. UPSVOLCANO has saved the company tens of millions of dollars since its introduction in 2000.

This UPS example is one of my favorite classroom examples of how algorithmic advances can be a key driver in success for a firm.

Of course, the phrase “operations research” never appears. I guess if people find algorithms scary, operations research will drive them away screaming. The magazine unwittingly shows why operations research never seems to get its due. In a sidebar, “ant algorithms” are given as an example of a powerful algorithm “with great potential”. The great strength of “ant algorithms” is a great name and a wonderful analogy. As for potential, perhaps… I would love to see an ant algorithm that can come close to the integer programming techniques that underly VOLCANO and other UPS systems.

Thanks to the four or five people who wrote me about this article. Even without mentioning operations research, articles like this are good for our field: they teach people the importance of our sorts of approaches to problem solving.

Queue or Queues

I am spending this year visiting the University of Auckland. New Zealand is a wonderful, beautiful country filled with very friendly people (see our personal blog for pictures and stories). It is not, however, a particularly efficient country. Service standards are not quite up to US standards. This is made worse by our living on an island. We love living on Waiheke, but any outing often results in “island efficiency”, which tests our relaxed, island mentality to its fullest. For instance, last night we went to a costume ball (medieval style). Beautiful converted barn, wonderful food, perfect music. And exactly one porta-potty for 200 guests at this four hour affair. Island efficiency.

Of course, operations research is about making things work better. And to an OR person, there is nothing more frustrating than seeing things work inefficiently. Grocery stores really stress me. I will not go to a busy store, since the lines and hassles will eventually give me a stroke. Instead, I shop at the off-off times whenever possible.

Some of this annoyance is completely avoidable, however, using just a bit of OR. In queueing, there are a few basic ideas. Here are a couple that even a two hour introduction to queueing should get to:

  • Assuming variance in either service or arrivals, if the service rate equals the arrival rate, the queue will explode.
  • All else being equal, one line leading to a bunch of servers is better for the customer than a bunch of lines each leading to one server.

So why is it that (almost) every grocery store has individual lines? Grocery stores are some of the most sophisticated users of techniques like data mining and logistics optimization, so they aren’t or-phobic. Why can’t they get this right?

One company does get this right, and that is Whole Foods, which gets a whole lot of things right in its operation (why else would we enthusiastically pay their prices?). The New York Times has an article entitled “A Long Line for a Shorter Wait” (thanks to Brian Borchers for pointing this out to me):

For its first stores here [New York City], Whole Foods, the gourmet supermarket, directs customers to form serpentine single lines that feed into a passel of cash registers. Banks have used a similar system for decades. But supermarkets, fearing a long line will scare off shoppers, have generally favored the one-line-per-register system. By 7 p.m. on a weeknight, the lines at each of the four Whole Foods stores in Manhattan can be 50 deep, but they zip along faster than most lines with 10 shoppers. Because people stand in the same line, waiting for a register to become available, there are no “slow” lines, delayed by a coupon-counting customer or languid cashier.

Now there is the psychological effect to avoid: the lines look long! So Whole Foods added some bells and whistles:

Perhaps the most important role players in the Whole Foods system are the “line managers,” who monitor the flow of people, direct them to a cash register and, when needed, hold up signs saying how long it will take to check out. In another innovation, color-coded digital screens are now replacing those humans.

To give an idea of how effective the single line is, suppose you have a single queue with 20 customers arriving per hour. If the cashier can handle (on average) 22 customers per hour (close to saturation, but probably roughly what “efficient” managers would aim for), then the queue will grow so long that the average wait will be 27 minutes! Five such queues would end up with about 50 people waiting in line on average. If you go over to one line (with 100 arrivals/hour) being served by five cashiers, the average wait goes down to under 5 minutes, and the number of people waiting in line is only 12 on average. Thanks to Armann Ingolfsson for putting together the Queueing Toolpack that makes these calculations easy.

There are a lot of assumptions in this analysis, and you can play around with input and service distributions, reneging, balking, queue hoping, and so on, but the result is robust to any of this: a single line to multiple queues is better than a bunch of single lines (about the only interesting aspect of multiple queues is the ability to have an express line for customers with just a few items). Every OR person knows this, and Whole Foods uses it. Every grocery store should.

I think it goes without saying that on Waiheke island, every line is a bunch of lines each being served (or not) by a single server. Even in banks.

Google’s search algorithm

There is an article in the New York Times on Google’s algorithm for returning pages after a search. It is remarkable how complex it has become. At its base is a concept called Page Rank (named after Larry Page, one of the founders of Google), a very simple concept that every operations research student can understand (Wikipedia has a short outline of it). You can see Page Rank as the ergodic state of a markov chain, or as an eigenvector of a particular matrix (as described by Kurt Bryan and Tanya Leise).  But the system has gone far beyond that:

Mr. Singhal [the subject of the article;  the Google engineer responsible for the rankings] has developed a far more elaborate system for ranking pages, which involves more than 200 types of information, or what Google calls “signals.” PageRank is but one signal. Some signals are on Web pages — like words, links, images and so on. Some are drawn from the history of how pages have changed over time. Some signals are data patterns uncovered in the trillions of searches that Google has handled over the years.

“The data we have is pushing the state of the art,” Mr. Singhal says. “We see all the links going to a page, how the content is changing on the page over time.”

Increasingly, Google is using signals that come from its history of what individual users have searched for in the past, in order to offer results that reflect each person’s interests. For example, a search for “dolphins” will return different results for a user who is a Miami football fan than for a user who is a marine biologist. This works only for users who sign into one of Google’s services, like Gmail.

Lots of operations research projects end up looking like that.  A sharp, clean model at the core, augmented over time with more and more additions to better fit reality.

Operations Research in the New York Times and I am annoyed and depressed

The term “Operations Research” appears in the New York Times today (May 20, 2007) in an article entitled “Reaping Results: Data-Mining Goes Mainstream“. Here is the start:

RODNEY MONROE, the police chief in Richmond, Va., describes himself as a lifelong cop whose expertise is in fighting street crime, not in software. His own Web browsing, he says, mostly involves checking golf scores.

But shortly after he became chief in 2005, a crime analyst who had retired from the force convinced him to try some clever software. The programs cull through information that the department already collects, like “911” and police reports, but add new streams of data — about neighborhood demographics and payday schedules, for example, or about weather, traffic patterns and sports events — to try to predict where crimes might occur.

Later comes the “Operations Research” reference:

The desire to exploit computing and mathematical analytics is by no means new. In the 1960s and ’70s, “operations research” combined computing and math mainly to make factory production work more efficient. And in that period, “decision support” software was intended to help managers more intelligently use information in the big computing file cabinets — databases — that were becoming common in corporations.

That really burns my butt. I hate the idea that operations research is shunted into history and it is the new analytics that is the key. It is all Operations Research!

Otherwise, the article is great. Analytics are a key success path for companies. Here is a quote from Wired on why Yahoo! lost out to Google:

At Yahoo, the marketers rule, and at Google the engineers rule. And for that, Yahoo is finally paying the price.

On the personal side, I also cringed when I saw the following in the New York Times article:

“It’s really starting to become mainstream,” says Mr. Davenport, co-author with Jeanne G. Harris of “Competing on Analytics: The New Science of Winning” (Harvard Business School Press, 2007). The entry barrier, he says, “is no longer technology, but whether you have executives who understand this.”

This was really the theme of my Hood Lecture, and I had the inklings of writing something longish on the subject. I will have to see if this book does a good job on this.

Major League Baseball Scheduling

Peter Theis and Jeremy Hastings, MBA students at my home base, the Tepper School of Business at Carnegie Mellon, have independently reminded me that I have been getting some press about the baseball schedule that I should be pointing to. Not all of it has been positive, but most of it talks about how difficult creating satisfying schedules is. For those who don’t know, some colleagues (Doug Bureman, George Nemhauser and Kelly Easton) and I, through our company the Sports Scheduling Group, created the 2005 and 2007 Major League Baseball Schedule. ESPN.com has an article on the 2007 schedule. They talk about some of the rough parts of the schedule:

For baseball players, grousing about the schedule is as routine as chewing sunflower seeds or making rookies wear cocktail dresses and high heels to the airport during the obligatory hazing trip. The average fan might regard it as just another case of millionaires whining, but fans don’t have to step in the box in front of 50,000 people and produce while bleary-eyed and jet-lagged.

Listen closely, and you’ll hear the Pittsburgh Pirates groaning en masse as they look at their schedule and contemplate that geographically challenged Houston-to-San Diego-to-Chicago trip in late September.

Or consider how thrilled the Texas Rangers must be looking forward to a nine-game Detroit-to-Oakland-to-Minnesota jaunt (with no day off) in the final month.

But ESPN.com also talks about the challenges:

Each team has its own unique circumstances. Cincinnati is always home on Opening Day, while Boston plays at Fenway Park each Patriots Day. The Mets have potential traffic and parking concerns when the U.S. Open tennis tournament is in town, and the Minnesota Twins share the Metrodome with the NFL’s Vikings.

And lest we forget, New York, Chicago, Los Angeles, the San Francisco Bay Area and Baltimore-Washington are all two-team markets. In a perfect world, one team will be at home while the other is on the road.

Throw in six pages of whys and wherefores governing scheduling in the collective bargaining agreement, and you have an extremely complicated jigsaw puzzle.

“You can take any short part of a team’s schedule and say, ‘That’s awful. Why would anybody schedule that?'” Feeney said. “But you can’t look at it that way. It’s not a two-week schedule. It’s a 26-week, 30-team schedule.'”

There have also been articles in the San Jose Mercury News and the Seattle Times. The News has the most depressing line (at least to me):

Starting next season, MLB will create the schedule within its offices. In other words, no more outside consultants.

Not happy news for the Sports Scheduling Group!

American Idol Voting is Flawed

Just to prove that operations research is relevant everywhere, Ed Kaplan of Yale University has pointed out a fundamental flaw in the voting process for American Idol. It appears that lots of people get busy signals when trying to vote for “their” idol. This may appear to be simply a frustration but actually gets to the heart of the fairness of the voting system. As Ed argues in an op-ed at the Hartford Courant, if votes are limited due to phone capacity, and each candidate has a separate line (each with the same capacity), then the votes will by necessity be much more evenly spread than the electorate. So a runaway winner can turn into a coin-toss.

In the best OR tradition, Ed not only identifies the problem but solves it:

There is a simple solution to this problem that does not require “American Idol” to install additional phone capacity. Instead of assigning each contestant a personal phone number, use a single number for all voting, and have voters select their favorite by pushing a button after the call has gone through. This simple fix would equalize the chance of encountering a busy signal for all callers.

Many votes would still be lost. In fact, if the total phone capacity was left unchanged, more calls would be lost due to the increase in processing time per call necessitated by button-pushing. But, since all calls would have the same chance of getting through, the total votes received would be a representative sample of votes cast.

If only OR people ran the world, even American Idol would run better.

Sloan-Kettering wins 2007 Edelman Award

The Franz Edelman award is the most prestigious award for the practice of operations research, and each year’s competition is hotly contested. Nominees need to spend significant time preparing their presentations and almost all of them end up involving CEOs or other top executives in the firm.

This year, the winner of the Edelman Award is Sloan-Kettering for work entitled “Operations Research Answers to Cancer Therapeutics.” From the announcement

Yesterday was the first time that the association awarded the Edelman prize for a medical treatment. The Sloan-Kettering win demonstrates how operations research and mathematics are increasingly bringing improvements to health care, not only in the areas of policy, finance, and public health but in diagnosis and treatment, as well.

Dr. Marco Zaider, Attending Physicist in Medical Physics at Memorial Sloan-Kettering Cancer Center received the award together with Professor Eva K. Lee, Director of the Center for Operations Research in Medicine and HealthCare in the School of Industrial and Systems Engineering at Georgia Institute of Technology.

The 2007 Franz Edelman Award winner was announced at a special awards banquet during The Institute for Operations Research and the Management Sciences (INFORMS®) Conference on O.R. Practice in Vancouver. http://meetings.informs.org/Practice07/ The finalists included Coca-Cola Enterprises, Hewlett-Packard, DaimlerChrysler, and the U.S. Coast Guard.

Dr. Lee and Dr. Zaider devised sophisticated optimization modeling and computational techniques to implement an intra-operative 3D treatment planning system for brachytherapy (the placement of radioactive “seeds” inside a tumor) that offers a safer and more reliable treatment.

The real-time intra-operative planning system eliminates pre-operation simulation and post-implant imaging analysis. Based on the range of costs of these procedures, Prof. Lee estimated conservatively that their elimination nationwide could save $450 million a year for prostate cancer care alone.

I am hoping for some press coverage for this (the winning work is very important, as are the contributions of the other finalists), but not much so far (just a couple pickups from health-oriented web sites). Reporters: great opportunity here!

Papers associated with the Edelman finalists will appear in the January-February issue of Interfaces.