A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem

References

• Abraham DJ, Blum A, Sandholm T (2007) Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. Proc. 8th ACM Conf. Electron. 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 AE (2015) Finding long chains in kidney exchange using the traveling salesman problem. Proc. Natl. Acad. Sci. USA 112(3):663–668.Crossref, Google Scholar
• Ashlagi I, Roth AE (2021) Kidney exchange: An operations perspective. Manage. Sci. 67(9):5455–5478.Link, Google Scholar
• Ashlagi I, Gamarnik D, Rees MA, Roth AE (2012) The need for (long) chains in kidney exchange. NBER Working Paper No. 18202, National Bureau of Economic Research, Cambridge, MA.Google Scholar
• Ashlagi I, Bingaman A, Burq M, Manshadi V, Gamarnik D, Murphey C, Roth AE, Melcher ML, Rees MA (2018) Effect of match-run frequencies on the number of transplants and waiting times in kidney exchange. Am. J. Transplant. 18(5):1177–1186.Crossref, Google Scholar
• Awasthi P, Sandholm T (2009) Online stochastic optimization in the large: Application to kidney exchange. Proc. 21st IJCAI Intern. Joint Conf. Artif. Intell. (ACM, New York), 405–411.Google Scholar
• Bang-Jensen J, Gutin GZ (2000) Digraphs: Theory, Algorithms and Applications, 1st ed. (Springer, London).Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Biró P, Haase-Kromwijk B, Andersson T, Ásgeirsson EI, Baltesová T, Boletis I, Bolotinha C, Bond G, 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. (2021) Modelling and optimisation in European Kidney Exchange Programmes. European J. Oper. Res. 291(2):447–456.Crossref, Google Scholar
• Canadian Blood Services (2019) Interprovincial organ sharing national data report: Kidney Paired Donation Program 2009–2018. Technical report, Canadian Blood Services, Ottawa.Google Scholar
• Cantwell L, Woodroffe C, Holdsworth R, Ferrari P (2015) Four years of experience with the Australian kidney paired donation programme. Nephrology (Carlton). 20(3):124–131.Crossref, Google Scholar
• Carvalho M, Klimentova X, Glorie K, Viana A, Constantino M (2020) Robust models for the kidney exchange problem. INFORMS J. Comput. 33(3):861–881.Link, Google Scholar
• Castro MP, Cire AA, Beck JC (2020) An MDD-based Lagrangian approach to the multicommodity pickup-and-delivery TSP. INFORMS J. Comput. 32(2):263–278.Abstract, Google Scholar
• CIHI (2019) Annual statistics on organ replacement in Canada: Dialysis, Transplantation and Donation, 2009 to 2018. Technical report, Canadian Institute for Health Information, Ottawa.Google Scholar
• Cire AA, van Hoeve WJ (2013) Multivalued decision diagrams for sequencing problems. Oper. Res. 61(6):1411–1428.Link, Google Scholar
• Constantino M, Klimentova X, Viana A, Rais A (2013) New insights on integer-programming models for the kidney exchange problem. European J. Oper. Res. 231(1):57–68.Crossref, 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 (2014) Robust dynamic optimization with application to kidney exchange. Proc. 2014 Internat. Conf. Autom. Agents and Multi-Agent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 1701–1702.Google Scholar
• Dickerson JP, Procaccia AD, Sandholm T (2012) Optimizing kidney exchange with transplant chains: Theory and reality. Proc. 11th Internat. Conf. Autonom. Agents and Multiagent Systems, vol. 2 (ACM, New York), 711–718.Google Scholar
• Dickerson JP, Procaccia AD, Sandholm T (2019) Failure-aware kidney exchange. Manage. Sci. 65(4):1768–1791.Link, Google Scholar
• 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.Google Scholar
• Ding Y, Ge D, He S, Ryan CT (2018) A nonasymptotic approach to analyzing kidney exchange graphs. Oper. Res. 66(4):918–935.Link, Google Scholar
• Farnadi G, St-Arnaud W, Babaki B, Carvalho M (2021) Individual Fairness in Kidney Exchange Programs. Proc. 35th Conf. AAAI Artif. Intell. (AAAI Press, Washington, DC), 11496–11505.Google Scholar
• Flechner SM, Thomas AG, Ronin M, Veale JL, Leeser DB, Kapur S, Peipert JD, et al. (2018) The first 9 years of kidney paired donation through the National Kidney Registry: Characteristics of donors and recipients compared with National Live Donor Transplant Registries. Am. J. Transplant. 18(11):2730–2738.Crossref, Google Scholar
• Gill JS, Tonelli M, Johnson N, Kiberd B, Landsberg D, Pereira BJ (2005) The impact of waiting time and comorbid conditions on the survival benefit of kidney transplantation. Kidney Int. 68(5):2345–2351.Crossref, Google Scholar
• Glorie KM, van de Klundert JJ, Wagelmans APM (2014) Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price. Manufacturing Service Oper. Management 16(4):498–512.Link, Google Scholar
• Hooker JN (2013) Decision diagrams and dynamic programming. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Springer, Heidelberg, Germany), 94–110.Crossref, Google Scholar
• Karp R (1972) Reducibility Among Combinatorial Problems (Springer, Boston), 85–103.Crossref, Google Scholar
• Kinable J, Cire AA, van Hoeve WJ (2017) Hybrid optimization methods for time-dependent sequencing problems. European J. Oper. Res. 259(3):887–897.Crossref, Google Scholar
• Klimentova X, Alvelos F, Viana A (2014) A new branch-and-price approach for the kidney exchange problem. Proc. Computat. Science and Its Applications – ICCSA 2014 (Springer, Cham, Switzerland), 237–252.Crossref, Google Scholar
• Klimentova X, Pedroso Ja P, Viana A (2016) Maximising expectation of the number of transplants in kidney exchange programmes. Comput. Oper. Res. 73:1–11.Crossref, Google Scholar
• Klimentova X, Viana A, Pedroso JP, Santos N (2021) Fairness models for multi-agent kidney exchange programmes. Omega 102:102333.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
• Mak-Hau V (2015) On the kidney exchange problem: Cardinality constrained cycle and chain problems on directed graphs: A survey of integer programming approaches. J. Comb. Optim. 33(1):35–39.Crossref, Google Scholar
• Malik S, Cole E (2014) Foundations and Principles of the Canadian living donor paired exchange program. Can. J. Kidney Health Dis. 1(1):6.Crossref, Google Scholar
• Mattei N, Walsh T (2013) Preflib: A library for preferences. https://www.preflib.org. Perny P, Pirlot M, Tsoukiàs A, eds., Algorithmic Decision Theory (Springer Berlin Heidelberg, Berlin, Heidelberg), 259–270.Crossref, Google Scholar
• McElfresh D, Bidkhori H, Dickerson J (2019) Scalable robust kidney exchange. Proc. Conf. AAAI Artif. Intell., vol. 33 (AAAI Press, Washington, DC), 1077–1084.Google Scholar
• Mittelman HD (2020) Benchmarking optimization software-a (Hi)story. SN Oper. Res. Forum 1(2).Google Scholar
• Monteiro T, Klimentova X, Pedroso JP, Viana A (2021) A comparison of matching algorithms for kidney exchange programs addressing waiting time. CEJOR Cent. Eur. J. Oper. Res. 29(2):539–552.Crossref, Google Scholar
• Morrison DR, Sewell EC, Jacobson SH (2016) Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams. INFORMS J. Comput. 28(1):67–82.Link, Google Scholar
• Omer J, Arslan AN, Yan F (2022) KidneyExchange.jl: A Julia package for solving the kidney exchange problem with branch-and-price. https://hal.inria.fr/hal-03830810/document.Google Scholar
• Plaut B, Dickerson JP, Sandholm T (2016a) Fast optimal clearing of capped-chain barter exchanges. Proc. Thirtieth AAAI Conf. Artificial Intelligence (AAAI Press, Washington, DC), 601–607.Google Scholar
• Plaut B, Dickerson JP, Sandholm T (2016b) Hardness of the pricing problem for chains in barter exchanges. Preprint, submitted June 1, https://arxiv.org/abs/1606.00117.Google Scholar
• Raghunathan AU, Bergman D, Hooker J, Serra T, Kobori S (2018) Seamless multimodal transportation scheduling. Preprint, submitted July 25, https://arxiv.org/abs/1807.09676.Google Scholar
• Rees MA, Dunn TB, Kuhr CS, Marsh CL, Rogers J, Rees SE, Cicero A, et al. (2017) Kidney exchange to overcome financial barriers to kidney transplantation. Am. J. Transplant. 17(3):782–790.Crossref, Google Scholar
• Roth AE, Sönmez T, Ünver MU (2007) Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences. Amer. Econom. Rev. 97(3):828–851.Crossref, Google Scholar
• Saidman SL, Roth AE, Sönmez T, Unver MU, Delmonico FL (2006) Increasing the opportunity of live kidney donation by matching for two- and three-way exchanges. Transplantation 5(81):773–782.Crossref, Google Scholar
• Trapianti CN (2022) Al via programma di trapianti incrociati di rene tra Italia e Usa, firmato l’accordo. Centro Nazionale Trapianti, https://www.trapianti.salute.gov.it/trapianti/dettaglioComunicatiNotizieCnt.jsp?lingua=italiano&area=cnt&menu=media&sottomenu=news&id=784.Google Scholar
• Wall AE, Veale JL, Melcher ML (2018) Advanced donation programs and deceased donor-initiated chains-2 Innovations in kidney paired donation. Transplantation 101(12):2818–2824.Crossref, Google Scholar