[en] The problem to decide which patient-donor pairs in a kidney exchange program should undergo a crossmatch test is modelled as a two-stage stochastic optimization problem. We give an integer programming formulation of this so-called selection problem, and describe a solution method based on Benders decomposition. We extensively test various solution methods, and observe that the solutions, when compared to solutions found by recourse models, lead to an improvement in the expected number of transplants. We also investigate the computational efficiency of our approach as a function of different parameters, such as maximum cycle length and the presence of altruistic donors.
Research Center/Unit :
QuantOM - HEC Management School
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Smeulders, Bart; Eindhoven University of Technology, The Netherlands
Bartier, Valentin; Grenoble INP, France
Crama, Yves ; Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production
Spieksma, Frits C.R.; Eindhoven University of Technology, The Netherlands
Language :
English
Title :
Recourse in Kidney Exchange Programs
Publication date :
2022
Journal title :
INFORMS Journal on Computing
ISSN :
1091-9856
eISSN :
1526-5528
Publisher :
INFORMS, Linthicum, United States - Maryland
Volume :
34
Issue :
2
Pages :
1191-1206
Peer reviewed :
Peer Reviewed verified by ORBi
Tags :
CÉCI : Consortium des Équipements de Calcul Intensif
Abraham DJ, Blum A, Sandholm T (2007) Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. Proc. 8th ACM Conf. Econom. Commerce (ACM, New York), 295-304.
Alvelos F, Klimentova X, Rais A, Viana A (2015) A compact formulation for maximizing the expected number of transplants in kidney exchange programs. Journal of Physics: Conference Series, vol. 616 (IOP Publishing), 012011.
Anderson R, Ashlagi I, Gamarnik D, Rees M, Roth AE, Sönmez T, Ünver MU (2015) Kidney exchange and the alliance for paired donation: Operations research changes the way kidneys are transplanted. Interfaces 45(1):26-42.
Assadi S, Khanna S, Li Y (2016) The stochastic matching problem with (very) few queries. Proc. 2016 ACM Conf. Econom. Comput. (ACM, New York), 43-60.
Behnezhad S, Farhadi A, Hajiaghayi M, Reyhani N (2019) Stochastic matching with few queries: New algorithms and tools. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2855-2874.
Biró P, Haase-Kromwijk B, Andersson T, Ásgeirsson EI, Baltesová T, Boletis I, Bolotinha C, et al (2019) Building kidney exchange programmes in Europe: An overview of exchange practice and activities. Transplantation 103:1514-1522.
Blum A, Gupta A, Procaccia A, Sharma A (2013) Harnessing the power of two crossmatches. Proc. 14th ACM Conf. Electronic Commerce (ACM, New York), 123-140.
Blum A, Dickerson JP, Haghtalab N, Procaccia AD, Sandholm T, Sharma A (2015) Ignorance is almost bliss: Near-optimal stochastic matching with few queries. Proc. 16th ACM Conf. on Econom. Comput. (ACM, New York), 325-342.
Dickerson JP, Procaccia AD, Sandholm T (2013) Failure-aware kidney exchange. Proc. 14th ACM Conf. Electronic Commerce (ACM, New York), 323-340.
Dickerson JP, Manlove DF, Plaut B, Sandholm T, Trimble J (2016) Position-indexed formulations for kidney exchange. Proc. 2016 ACM Conf. Econom. Comput. (ACM, New York), 25-42.
Gentry SE, Mongomery RA, Segev DL (2011) Kidney paired donation: Fundamentals, limitations, and expansions. Amer. J. Kidney Disease 57(1):144-151.
Glorie K (2012) Estimating the probability of positive crossmatch after negative virtual crossmatch. Technical report, Econometric Institute, Erasmus University, Rotterdam, Netherlands.
Glorie K (2014) Clearing barter exchange markets: Kidney exchange and beyond. PhD thesis, Erasmus University, Rotterdam, Netherlands.
Homem-de-Mello T, Bayraksan G (2014) Monte Carlo samplingbased methods for stochastic optimization. Survey Oper. Res. Management Sci. 19:56-85.
Kleywegt A, Shapiro A, Homem-de-Mello T (2001) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479-502.
Klimentova X, Pedroso JP, Viana A (2016) Maximising expectation of the number of transplants in kidney exchange programmes. Comput. Oper. Res. 73:1-11.
Mak-Hau V (2017) On the kidney exchange problem: Cardinality constrained cycle and chain problems on directed graphs: A survey of integer programming approaches. J. Combinational Optim. 33(1):35-59.
Manlove DL, O'malley G (2015) Paired and altruistic kidney donation in the UK: Algorithms and experimentation. J. Experiment. Algorithmics 19:2-6.
Montgomery RA, Gentry SE, Marks WH, Warren DS, Hiller J, Houp J, Zachary AA, et al. (2006) Domino paired kidney donation: A strategy to make best use of live non-directed donation. Lancet 368(9533):419-421.
NHS (2017a) Annual report on living donor kidney transplantation. Technical report, NHS, London.
NHS (2017b) Living donor kidney matching run process. Technical report. Retrieved April 26, 2018, https://nhsbtdbe.blob.core.windows.net/umbraco-assets-corp/2287/ldkmr-matchingprocess.pdf.
Pedroso JP (2014) Maximizing expectation on vertex-disjoint cycle packing. Proc. Internat. Conf. Comput. Sci. Appl. (Springer, Berlin), 32-46.
Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801-817.
Roth AE, Sönmez T, Ünver MU (2004) Kidney exchange. Quart. J. Econom. 119(2):457-488.
Roth AE, Sönmez T, Ünver MU, Delmonico FL, Saidman SL (2006) Utilizing list exchange and nondirected donation through 'chain' paired kidney donations. Amer. J. Transplantation 6(11): 2694-2705.
Saidman SL, Roth AL, Sönmez T, Ünver MU, Delmonico FL (2006) Increasing the opportunity of live kidney donation by matching for two-and three-way exchanges. Transplantation 81(5):773-782.
