Booth Id:
SOFT029
Category:
Systems Software
Year:
2017
Finalist Names:
Panuganti, Kireet
Abstract:
The kidney exchange market allows patients with kidney disease to obtain compatible donors by swapping an incompatible friend or family member’s kidney. With over 93,000 people on the kidney waiting list, this market is an ethical way to significantly reduce the 4,000 deaths per year due to kidney disease.
The NP-hard clearing problem involves finding a set of exchanges given a set of patient-donor pairs. In previous studies, an Integer Programming Solver(IPS) solves it as a constrained optimization problem. However, there is an urgent need for more efficient algorithms that scale to large data.
We present a stochastic optimization algorithm based off Metropolis-Hastings, a sampling algorithm. We translate the problem in graph theory by creating a directed graph where a vertex represents a patient-donor pair and a directed edge representing compatibility between a patient and a donor. An exchange is composed of a set of disjoint cycles in the graph. We create a cost function for an exchange that is maximized when it includes the maximum possible vertices. We create a probability distribution in the n-dimensional sample space of exchanges with the same peak as the cost function. Approximating this distribution using Metropolis Hastings allows us to find the optimal solution.
We implement our algorithm on simulated and real data and examine its efficiency compared to that of standard IPS algorithms. We find that our algorithm can find optimal solutions more efficiently than previous tried methods, thereby allowing a kidney exchange with many more patients being served.