Category: Medicine

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.

The 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.

 

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.

Operations 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”