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:
I thank for funding NSF, and Microsoft Research that funds the Computational Thinking Center at Carnegie Mellon.