Category: Applications

OR in Popular Mechanics

When I was a kid, I loved the magazine Popular Mechanics.  In addition to articles on futuristic cars and planes, they always had articles on how things worked, and I seem to recall mechanically oriented projects that were always just outside my abilities.  As time went on, I realized that my mechanical abilities were limited indeed, so I moved on to the more cerebral Scientific American and mathematics.  These days, I am always amazed when I see Popular Mechanics in bookstores:  it is like a blast from the 60s.

Blake Nicholson of the University of Michigan wrote me to point out that a recent article in the magazine has a heavy OR focus.  In an article on Improving Air Travel,  one of the ten possible improvements, changing boarding strategies, is explicitly an OR approach.  A few of the other suggestions, including re-pricing landing slots to encourage better spreading of planes and the use of RFID in luggage tracking, are also OR approaches to air travel problems.

Natashia Boland and Open Pit Mining

I am attending the Australian Society for Operational Research meeting in Melbourne.  I had thought Australia always had wonderful weather, but it is a gray, rainy day here.

The conference was opened with a talk by Natashia Boland, currently at the University of Melbourne (but I hear she is moving) who spoke on her experiences in using integer programming in practice.

The first part of the talk was about modeling excavation in open pit mines.  The goal in this problem is to dig out a mine in the best possible way.  The most critical constraint is, of course, that you can’t dig under stuff that is not already dug away.  There are other constraints on how much ore can be processed in a year, and on other operational requirements.  Of course, the amount of money that is at stake is huge:  these mines generate  hundreds  of millions of dollars of income, and require huge investments (see the wikipedia entry on the Bingham Canyon Mine for one example:  the pictured example is from Russia).  So planning the excavation is an important decision, even if most of the savings are just the time-value of money (getting $100 million this year rather than next is quite a difference!).  The integer programs that Natashia and her colleagues get are very large, so they have had to develop specialized branching rules, along with aggregation approaches to the decisions.

Natashia’s second example had to do with shipping planning for a fertilizer company.  The most striking point she made is that her approach still leaves an 8% gap between the upper bound (feasible solution) and lower bound.  This bound may be because the lower bound is poor (no possible solution can reach that value) but even 1 or 2% of an operation that costs a few hundred million dollars to run is a big deal.

Natashia gives very good, clear, inspirational talks.  The thing I like best is her choice of problems.  They are non-standard, but still involve huge amounts of money.  Every percentage point she saves would be enough to support an enormous research effort in integer programming.  If only she were to get a fraction of the savings!

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.

 

Getting cheaper boats and ships

I am in Providence attending this year’s Constraint Programming conference. I’m on the executive and we have developed new bylaws, so instead of listening to all the talks, I am involved in discussions on the minutia of quorums and transition rules. Still, there is some time for the conference itself.

I just saw a terrific talk by Matt Ginsberg of the University of Oregon and On Time Systems, a firm specializing in scheduling optimization. One of the big things they do is shipyard optimization, and he described putting together a system for better scheduling the production of navy submarines (which are boats) and carriers (which are ships). While traditional scheduling involves trying to minimize the amount of time it takes to build something, this sort of scheduling is about minimizing costs (or so he thought). So his firm put together a nice system to minimize the cost of going through the tens of thousands of tasks that go into a boat or ship. If that was the end of the talk, it would have been a fine technical talk on an interesting topic. But he went further.

“Just because a schedule looks good doesn’t mean it is good” is a phrase I wish more people would use. Lots of schedules look good, but when you try to use them they fail for easy-to-see-in-retrospect reasons. One example of this is the highly optimized crew schedules used by airlines. Sure, they look good and they appear to save money, but they are fragile: disruptions can spread throughout the system. Matt brought up two important issues not covered by the “minimize cost” aspects of their schedules. The first is the brittleness seen in airline crew schedules: will delays in one task mess up more? The second is union buy-in. If the goal is to decrease costs, won’t unions naturally be against it?

The brittleness point is important. Indeed, a minimum cost schedule is brittle (though perhaps no more brittle than the schedule currently in place), though it saves about 10.4% on costs. But the methods Matt used can be adapted to make float (the amount any task can be delayed without affecting other tasks) into account. A task with too little float (perhaps just a few work shifts) is at risk of delaying the whole project. But you can combine these objectives: minimize cost and minimize number of tight tasks. It turns out that you can decrease the number of tight tasks by more than 90% (relative to the current schedule) and still save about 10.3% on costs (numbers approximate: I have to learn to take better notes!). So decreasing brittleness comes almost for free!

As for the unions, one fact about shipyards is that they often layoff and then rehire lots and lots of workers. The schedules Matt provides are much smoother in the way they use workers. Certainly far more workers would have consistent jobs under the schedules, and layoffs would not occur near as often.

Overall, the shipbuilders would save money, the unionized workers would have more consistent jobs, and the building process would be less susceptible to delays. What’s not to like?

Well, the firms building the ships are paid by the Navy on a cost-plus basis. The higher the cost, the higher the plus. So they have essentially no interest in saving our money. They like high costs! Next time you see your congressman or -woman, ask “What happened to the ARGOS project to improve ship-building operations? Wasn’t that supposed to save us a few billion dollars?”

While we wait for the companies to work more efficiently, On Time Systems has a scheduling game you can play.

Scheduling people in the Netherlands

John Poppelaars has started a blog entitled “OR at Work” about OR applications in practice. One of his posts is about employee scheduling, where a Dutch directive includes the following requirements:

In normal English the rule states that when an employee performs one or more resident on call duties, each period of 7 times 24 hours must contain at least 90 hours of compensatory rest. So far this is simple, we can easily add up all the rest periods an see if it matches the requested 90 hours. There are additional restrictions however on how the compensatory rest period is divided up over the 168 hours period. These restrictions state that there should be at least one period of 24 hours compensatory rest, four of at least 11 hours, one of at least 10 hours and finally one of at least 8 hours. 7 rest periods in total.

As John points out, such rules are really good for OR people: it makes things so complicated that only OR models have a chance of doing well. Of course, whether our own approaches work (let’s see, let x[10] be one if it is a ten hour rest, but not eleven, then x[10]= … hmmm… maybe a branch-and-price approach instead…) is a little unclear. But bring on complexity: the more people get frustrated, the more they need us!

INFORMS and YouTube videos

INFORMS has some videos on YouTube from the recent Edelman Awards. This is great for the field. The three videos are

  1. General OR, and the Edelman Award
  2. The 2007 Award (on more efficient ways to attack prostate cancer)
  3. A detailed video on the 2006 award (Warner Robbins on repairing planes)

So far the videos have been accessed a couple of dozen times each. Pass along the pointers, and let’s get that count up!

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.

Interaction of Computers and People

In a few days, I give a “public lecture” as part of the requirements for my Hood Fellowship that the University of Auckland gave me (I would have visited here anyway – New Zealand is wonderful – but the Fellowship was a very nice addition). Rather than trot out a version of my “sports scheduling” talk, I am giving an overview of OR talk. It is really quite a challenge. These overview talks can be quite a snooze for those in the audience who know OR, so I am thinking hard about the role OR has in the world, and the challenges the field faces. The “Science of Better” initiative of INFORMS has been very helpful in this regard.

One aspect I am exploring is the appropriate role of OR in decision making. While optimizers like me tend to be a bit impatient with this (“The best answer is this! Stop arguing with me and do it!!), the real-world is full of stuff that doesn’t appear in our models. In many (most?) applications, OR is an adjunct to decision making, not a replacement. Slate has an interesting article about this in the context of chess-playing programs that I may try to work into my talk.

Apologies in advance: the next few posts may be me trying to work through my thoughts in preparation for the talk.