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.


OR Forum Paper on Influenza released

As one of my hats, I am the Area Editor for Operations Research responsible for the OR Forum. This area tries to attract contentious or provocative papers on topics in OR of broad interest. We have just published our second paper in the Area: a work by Dick Larson of MIT on influenza modeling. You can read the paper and join the discussion at the OR Forum.

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.

President Clinton, AIDS and Operations Research

Clinton FoundationIt is heartening to see former President Clinton talk about “Operations Research” and even better to see outside groups see the promise of our field. At an address at the 16th Annual International AIDS Conference, President Clinton announced a new Consortium for Strategic HIV Operations Research. From the transcript (page 13/14):

Second point I want to make is while more money is necessary, it is nowhere near sufficient. It is our moral obligation to ensure that the enormous contributions already made and those that will be made are used most efficiently. Every single wasted dollar puts a life at risk.
A few days ago, my foundation unveiled our consortium for strategic operation research here in Toronto. It’s an initiative designed to help ensure that this huge investment of resources results in the highest quality care, most efficiently delivered for as many HIV infected people as possible. We want to apply the same planning methods that Fortune 500 companies use to manage their operations, so that we can make the most effective use of what will always be scarce resources until the number of people who are HIV positive begins to drop dramatically. Using simple open-source computer models, we’ll be able to help governments save more lives with the same human and financial resources.

Wow! An obvious reference to operations research and open source in the same paragraph!

A few months ago, I talked to some researchers at the Clinton Foundation. Often “Operations Research” in AIDS/HIV research is what we would call “Statistical Experimental Design”: how to best measure the effect of certain treatments. For instance, there is a book available online entitled: “Designing HIV/AIDS Intervention Studies: An Operations Research Handbook” that will not be recognizable as operations research as our field defines it.

While important, this approach ignores 99% of operations research. Issues like optimal resource allocation, stochastic models of disease spread, simulation and so on are equally or more important, but are under-studied in this area.The Clinton Foundation people seem to understand this, and want to bring the full power of OR to this field. The CSHOR has in place a simulation model of clinics that can be modified to fit local costs/resource availability to determine, for instance, the effect of having another nurse. The Q&A directly addresses the role of OR:

Why was CSHOR created?

The emerging field of operations research offers a practical and strategic approach to future planning for developing countries. Operations research can be performed on the ground, in real-time, to guide decision making at a single clinic or a regional or national HIV treatment program. Local data and best practices from programs around the world can be combined to help ensure consistency and quality of care.

Operations research is increasingly critical; as ever-vaster resources are poured into national HIV treatment programs, it is crucial to be sure they are used as efficiently to provide high-quality treatment and care for as many people as possible.

CSHOR was launched in response to direct appeals from CHAI’s partner countries for assistance with resource planning and allocation.

I am not sure “emerging field” is appropriate for a 60 year old field, but the rest is very encouraging.

OR has a huge amount to offer this area, and I am absolutely thrilled that the Clinton Foundation is using the skills of our field

Bird flu Logistics

J. Michael SteeleJ. Michael Steele has a blog on “Bird Flu Economics”, looking at economic aspects of an avian inluenza pandemic. His blog provides a welcome dose of reality in the arguments about effect and appropriate response to the avian flu. A recent post of his points out how little logistics (read OR) planning has been done in this area.

Logistical nightmares are at the heart of every H5N1 pandemic senario anyone has ever concocted, yet it is hard to tell if anyone in the OR community is currently looking hard at this.

Isn’t it clear that pandemic logistics is a research area that deserves encouragement at every level?

Let’s at least catalog what is being done — or not being done!

Steele has done lots of interesting work. In the early 1980s, he did a lot of fundamental work in the use of probabilistic analysis in combinatorial optimization, including writing a great chapter in the Traveling Salesman book (as an aside: it is a travesty that the book costs more than $250; while dated on the TSP, it still provides a great overview of the various themes associated with combinatorial optimization and remain one of my favorite books of all time). His current work is primarily in mathematical finance and statistical modeling. He has a recent book on the Cauchy-Schwarz inequality (a much more reasonable $30!).

Emergency care at breaking point

The Institute of Medicine, one of the National Academies, has a series of reports out about the state of emergency medical care in the United States. The report is scathing in its assessment:

Despite the lifesaving feats performed every day by emergency departments and ambulance services, the nation’s emergency medical system as a whole is overburdened, underfunded, and highly fragmented, says this series of three reports from the Institute of Medicine.

As a result, ambulances are turned away from emergency departments once every minute on average and patients in many areas may wait hours or even days for a hospital bed. Moreover, the system is ill-prepared to handle surges from disasters such as hurricanes, terrorist attacks, or disease outbreaks.

The full reports are available for purchase, but there is a report brief that summarizes the main conclusions. The number one recommendation for fixing these problems? Use operations research, of course:

Tools developed from engineering and operations research have been successfully applied to a variety of businesses, from banking and airlines to manufacturing companies. These same tools have been shown to improve the flow of patients through hospitals, increasing the number of patients that can be treated while minimizing delays in their treatment and improving the quality of their care. One such tool is queuing theory, which by smoothing the peaks and valleys of patient admissions has the potential to eliminate bottlenecks, reduce crowding, improve patient care, and reduce cost. Another promising tool is the clinical decision unit, or 23-hour observation unit, which helps ED [Emergency Department] staff determine whether certain ED patients require admission. Hospitals should use these tools as a way of improving hospital efficiency and, in particular, reducing ED crowding.

This is exactly the sort of problem where a bit of OR can go a long way.

More Operations Research in Business Week

Business Week coverOperations research is on a roll. The May 29th issue of Business Week has a cover story on the use of simulation and other methods to take the guesswork out of medical care. The key person for this article is Dr. David Eddy, described as a “heart surgeon turned mathemetician and health-care economist”, who was the 1980 recipient of the INFORMS-awarded Lanchester Prize. This prize is given for the “awarded for the best contribution to operations research and the management sciences published in English”. The award citation to Dr. Eddy included the following:

The rapidly growing cost of health care is of great concern to many citizens. Our health care system and policies in the U.S. might be described as the product of many good intentions but only modest analysis. This year’s Lanchester Prize goes to a book: Screening for Cancer: Theory, Analysis and Design by Dr. David M. Eddy, published by Prentice-Hall, Inc., Englewood Cliffs, 1980, which is a significant and welcome contribution to the quality of analysis in the health care field.

In its general form, the problem studied by Dr. Eddy is an old one in the operations research literature, namely, the monitoring and repair of a probabilistic deteriorating system. This dry sounding phrase takes on special meaning when the system is the human body and the deterioration is cancer.

The principal concerns of Dr. Eddy’s work are: which screening tests should be used and with what frequency for various classes of people. The notable feature of Dr. Eddy’s analysis is the thoroughness with which account is taken of such things as the cost of administering a test, the cost of processing false positives from a test, the fact that a test may cause the disease it is attempting to detect, the fact that more frequent testing detects disease earlier and gives the illusion of prolonged life expectancy even in the absence of a cure, and the fact that if the disease may sometimes go into remission naturally, then more frequent testing gives the illusion of a higher cure rate. Also, Dr. Eddy’s analysis was one of the first to make the useful distinction between modeling the state of a patient as his cancer screening history to date, which is observable, as opposed to the state of the disease, which is only partially observable.

The style of Dr. Eddy’s work is in the best operations research tradition of interdisciplinary analysis. The remarkable feature is that in this case the varied disciplines are all embodied in one person.

From the Business Week article, it seems that 26 years later, Dr. Eddy continues this path:

Continue reading “More Operations Research in Business Week”