Finding long chains in kidney exchange using the traveling salesman problem

[Clark]

http://www.pnas.org/content/early/2015/01/02/1421853112

Finding long chains in kidney exchange using the traveling salesman problem
Ross Anderson, Itai Ashlagi, David Gamarnik, and Alvin E. Roth

Significance

There are currently more than 100,000 patients on the waiting list in the United States for a kidney transplant from a deceased donor. To address this shortage, kidney exchange programs allow patients with living incompatible donors to exchange donors through cycles and chains initiated by altruistic nondirected donors. To determine which exchanges will take place, kidney exchange programs use algorithms for maximizing the number of transplants under constraints about the size of feasible exchanges. This problem is NP-hard, and algorithms previously used were unable to optimize when chains could be long. We developed two algorithms that use integer programming to solve this problem, one of which is inspired by the traveling salesman, that together can find optimal solutions in practice.

Abstract
As of May 2014 there were more than 100,000 patients on the waiting list for a kidney transplant from a deceased donor. Although the preferred treatment is a kidney transplant, every year there are fewer donors than new patients, so the wait for a transplant continues to grow. To address this shortage, kidney paired donation (KPD) programs allow patients with living but biologically incompatible donors to exchange donors through cycles or chains initiated by altruistic (nondirected) donors, thereby increasing the supply of kidneys in the system. In many KPD programs a centralized algorithm determines which exchanges will take place to maximize the total number of transplants performed. This optimization problem has proven challenging both in theory, because it is NP-hard, and in practice, because the algorithms previously used were unable to optimally search over all long chains. We give two new algorithms that use integer programming to optimally solve this problem, one of which is inspired by the techniques used to solve the traveling salesman problem. These algorithms provide the tools needed to find optimal solutions in practice.

To whom correspondence should be addressed. Email: alroth@stanford.edu.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1421853112/-/DCSupplemental.

http://www.pnas.org/content/suppl/2015/01/02/1421853112.DCSupplemental/pnas.201421853SI.pdf