TY - CHAP
T1 - A Sampling-Free Anticipatory Algorithm for the Kidney Exchange Problem
AU - Chisca, Danuta Sorina
AU - Lombardi, Michele
AU - Milano, Michela
AU - O’Sullivan, Barry
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - Kidney exchange programs try to improve accessibility to kidney transplants by allowing incompatible patient-donor pairs to swap donors. Running such a program requires to solve an optimization problem (the Kidney Exchange Problem, or KEP) as new pairs arrive or, unfortunately, drop-off. The KEP is a stochastic online problem, and can greatly benefit from the use of anticipatory algorithms. Unfortunately, most such algorithms suffer from scalability issues due to the reliance on scenario sampling, limiting their practical applicability. Here, we recognize that the KEP allows for a sampling-free probabilistic model of future arrivals and drop-offs, which we capture via a so-called Abstract Exchange Graph (AEG). We show how an AEG-based approach can outperform sampling-based algorithms in terms of quality, while being comparable to a myopic algorithm in terms of scalability. While our current experimentation is preliminary and limited in scale, these qualities make our technique one of the few that can hope to address nation-wide programs with thousands of enrolled pairs.
AB - Kidney exchange programs try to improve accessibility to kidney transplants by allowing incompatible patient-donor pairs to swap donors. Running such a program requires to solve an optimization problem (the Kidney Exchange Problem, or KEP) as new pairs arrive or, unfortunately, drop-off. The KEP is a stochastic online problem, and can greatly benefit from the use of anticipatory algorithms. Unfortunately, most such algorithms suffer from scalability issues due to the reliance on scenario sampling, limiting their practical applicability. Here, we recognize that the KEP allows for a sampling-free probabilistic model of future arrivals and drop-offs, which we capture via a so-called Abstract Exchange Graph (AEG). We show how an AEG-based approach can outperform sampling-based algorithms in terms of quality, while being comparable to a myopic algorithm in terms of scalability. While our current experimentation is preliminary and limited in scale, these qualities make our technique one of the few that can hope to address nation-wide programs with thousands of enrolled pairs.
KW - Kidney Exchange Problem
KW - Probabilistic model
KW - Stochastic online optimization
UR - https://www.scopus.com/pages/publications/85066824496
U2 - 10.1007/978-3-030-19212-9_10
DO - 10.1007/978-3-030-19212-9_10
M3 - Chapter
AN - SCOPUS:85066824496
SN - 9783030192112
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 146
EP - 162
BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 16th International Conference, CPAIOR 2019, Proceedings
A2 - Stergiou, Kostas
A2 - Rousseau, Louis-Martin
PB - Springer Verlag
T2 - 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2019
Y2 - 4 June 2019 through 7 June 2019
ER -