New Algorithms for Hierarchical Optimization in Kidney Exchange Programs

References

• Abraham D, Blum A, Sandholm T (2007) Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. Proc. Eighth ACM Conf. Electronic Commerce (ACM, New York), 295–304.Google Scholar
• Alvelos F, Klimentova X, Viana A (2019) Maximizing the expected number of transplants in kidney exchange programs with branch-and-price. Ann. Oper. Res. 272:429–444.Crossref, Google Scholar
• Anderson R, Ashlagi I, Gamarnik D, Roth A (2015) Finding long chains in kidney exchange using the traveling salesman problem. Proc. Natl. Acad. Sci. USA 112:663–668.Crossref, Google Scholar
• Axelrod DA, Schnitzler MA, Xiao H, Irish W, Tuttle-Newhall E, Chang SH, Kasiske BL, Alhamad T, Lentine KL (2018) An economic assessment of contemporary kidney transplant practice. Amer. J. Transplantation 18:1168–1176.Crossref, Google Scholar
• Balas E, Christofides N (1981) A restricted Lagrangean approach to the traveling salesman problem. Math. Programming 21:19–46.Crossref, Google Scholar
• Bikbov B, Purcell CA, Levey AS, Smith M, Abdoli A, Abebe M, Adebay OM, et al. (2020) Global, regional, and national burden of chronic kidney disease, 1990–2017: A systematic analysis for the Global Burden of Disease Study 2017. Lancet 395:709–733.Google Scholar
• 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.Crossref, Google Scholar
• Biró P, van de Klundert J, Manlove D, Pettersson W, Andersson T, Burnapp L, Chromy P, et al. (2020) Modelling and optimisation in European kidney exchange programmes. Eur. J. Oper. Res. 291:447–456.Crossref, Google Scholar
• Blum A, Dickerson J, Haghtalab N, Procaccia A, Sandholm T, Sharma A (2020) Ignorance is almost bliss: Near-optimal stochastic matching with few queries. Oper. Res. 68:16–34.Link, Google Scholar
• Caragiannis I, Filos-Ratsikas A, Procaccia AD (2015) An improved 2-agent kidney exchange mechanism. Theoret. Comput. Sci. 589:53–60.Crossref, Google Scholar
• Carpaneto G, Dell’Amico M, Toth P (1995) Exact solution of large-scale, asymmetric traveling salesman problems. ACM Trans. Math. Software 21:394–409.Crossref, Google Scholar
• Chisca D, Lombardi M, Milano M, O’Sullivan B (2019a) Logic-based Benders decomposition for super solutions: An application to the kidney exchange problem. Schiex T, de Givry S, eds. Principles and Practice of Constraint Programming (Springer, Cham, Switzerland), 108–125.Crossref, Google Scholar
• Chisca DS, Lombardi M, Milano M, O’Sullivan B (2019b) A sampling-free anticipatory algorithm for the kidney exchange problem. Rousseau LM, Stergiou K, eds. Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer, Cham, Switzerland), 146–162.Crossref, Google Scholar
• Constantino M, Klimentova X, Viana A, Rais A (2013) New insights on integer-programming models for the kidney exchange problem. Eur. J. Oper. Res. 231:57–68.Crossref, Google Scholar
• Dantzig GB (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Das S, Dickerson JP, Li Z, Sandholm T (2015) Competing dynamic matching markets. Proc. Conf. Auctions Market Mechanisms Appl. (AMMA), vol. 112 (ACM, New York), 245.Google Scholar
• Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J. Comput. 32:101–119.Link, Google Scholar
• Delorme M, García S, Gondzio J, Kalcsics J, Manlove D, Pettersson W, Trimble J (2022) Improved instance generation for kidney exchange programmes. Comput. Oper. Res. 141:105707.Crossref, Google Scholar
• Dickerson JP, Procaccia AD, Sandholm T (2012) Dynamic matching via weighted myopia with application to kidney exchange. Proc. 26th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1340–1346.Google Scholar
• Dickerson J, Manlove D, Plaut B, Sandholm T, Trimble J (2016) Position-indexed formulations for kidney exchange. Proc. 2016 ACM Conf. Econom. Comput. (ACM, New York), 25–42.Google Scholar
• European Network for Collaboration on Kidney Exchange Programmes (2020) ENCKEP. Retrieved June 25 from http://www.enckep-cost.eu.Google Scholar
• Gao I (2019) Fair matching in dynamic kidney exchange. Preprint, submitted December 23, https://doi.org/10.48550/arXiv.1912.10563.Google Scholar
• Garfinkel R, Nemhauser G (1972) Integer Programming (Wiley, New York).Google Scholar
• Global Burden of Disease Collaborative Network and Institute for Health Metrics and Evaluation (2019) Global Burden of Disease Study. Retrieved March 25, 2021, from http://ghdx.healthdata.org/gbd-results-tool?params=gbd-api-2019-permalink/bb32e062360440c605520145ecd096b2.Google Scholar
• Hart A, Smith JM, Skeans MA, Gustafson SK, Stewart DE, Cherikh WS, Wainright JL, et al. (2017) OPTN/SRTR 2015 annual data report: Kidney. Amer. J. Transplantation 17:21–116.Crossref, Google Scholar
• Irnich S, Desaulniers G, Desrosiers J, Hadjar A (2010) Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS J. Comput. 22:297–313.Link, Google Scholar
• Klimentova X, Pedroso JP, Viana A (2016) Maximising expectation of the number of transplants in kidney exchange programmes. Comput. Oper. Res. 73:1–11.Crossref, Google Scholar
• Lam E, Mak-Hau V (2020) Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange. Comput. Oper. Res. 115:104852.Crossref, Google Scholar
• Lin M, Wang J, Feng Q, Fu B (2019) Randomized parameterized algorithms for the kidney exchange problem. Algorithms 12(2):50.Crossref, Google Scholar
• Mak-Hau VH (2017) On the kidney exchange problem: Cardinality constrained cycle and chain problems on directed graphs: A survey of integer programming approaches. J. Combin. Optim. 33(1):35–59.Crossref, Google Scholar
• Manlove D, O’Malley G (2015) Paired and altruistic kidney donation in the UK: Algorithms and experimentation. ACM J. Experiment. Algorithmics 19:1–21.Crossref, Google Scholar
• McElfresh DC, Bidkhori H, Dickerson JP (2019) Scalable robust kidney exchange. Proc. 33rd AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1077–1084.Google Scholar
• National Kidney Foundation (2020) Dialysis. Retrieved June 25 from https://www.kidney.org/atoz/content/dialysisinfo.Google Scholar
• Nemhauser G, Wolsey L (1988) Integer and Combinatorial Optimization (Wiley, New York).Crossref, Google Scholar
• Organ Procurement and Transplantation Network (2020) Organ Procurement and Transplantation Network policies. Retrieved June 25 from https://optn.transplant.hrsa.gov/media/1200/optn_policies.pdf.Google Scholar
• Rapaport F (1986) The case for a living emotionally related international kidney donor exchange registry. Transplantation Proc. 18(3, Suppl. 2)5–9.Google Scholar
• Roth A, Sönmez T, Ünver M (2004) Kidney exchange. Quart. J. Econom. 119(2):457–488.Crossref, Google Scholar
• Roth A, Sönmez T, Ünver M (2005) Pairwise kidney exchange. J. Econom. Theory 125(2):151–188.Crossref, Google Scholar
• Roth A, Sönmez T, Ünver M (2007) Efficient kidney exchange: Coincidence of wants in a market with compatibility-based preferences. Amer. Econom. Rev. 97(3):828–851.Crossref, Google Scholar
• Saidman S, Roth A, Sönmez T, Unver M, Delmonico F (2006) Increasing the opportunity of live kidney donation by matching for two- and three-way exchanges. Transplantation 81:773–782.Crossref, Google Scholar
• Trimble J (2020) Data set generator. Retrieved June 25 from https://jamestrimble.github.io/kidney-webapp/#/generator.Google Scholar
• Wang W, Bray M, Song PX, Kalbfleisch JD (2019) An efficient algorithm to enumerate sets with fallbacks in a kidney paired donation program. Oper. Res. Health Care 20:45–55.Crossref, Google Scholar
• Wolfe RA, Roys EC, Merion RM (2010) Trends in organ donation and transplantation in the United States, 1999–2008. Amer. J. Transplantation 10:961–972.Crossref, Google Scholar
• Wolsey L (1998) Integer Programming (Wiley, New York).Google Scholar