In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The clearing problem involves finding a social welfare maximizing set of non-overlapping short cycles. We proved this NP-hard. It was one of the main obstacles to a national kidney exchange. We presented the first algorithm capable of clearing these exchanges optimally on a nationwide scale. The key was incremental problem formulation. We adapted two paradigms for this: constraint generation and column generation. For each, we developed techniques that dramatically improve runtime and memory usage.
Furthermore, clearing is an online problem where patient-donor pairs and altruistic donors appear and expire over time. We developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. I will discuss design parameters and tradeoffs. Our best online algorithms outperform the current practice of solving each batch separately.
I will share my experiences from using these algorithms in real kidney exchanges, and the generalizations we introduced. For one, we used them to launch the first never-ending altruistic donor chains. I am also helping UNOS design the nationwide kidney exchange; I will discuss current design considerations.
The talk will cover the following papers:
- A Nonsimultaneous, Extended, Altruistic-Donor Chain. New England Journal of Medicine 360(11), March 2009. (With Rees, M., Kopke, J., Pelletier, R., Segev, D., Rutter, M., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Ünver, U., and Montgomery, R.)
- Online Stochastic Optimization in the Large: Application to Kidney Exchange. Draft, 2009. (With Awasthi, P.)
- Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. Proc. ACM Conference on Electronic Commerce, 2007. (With Blum, A. and Abraham, D.)
I thank for funding NSF, and Microsoft Research that funds the Computational Thinking Center at Carnegie Mellon.
