A Branch-Price-and-Cut Algorithm 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. Electronic Commerce (Association for Computing Machinery, New York), 295–304.Google Scholar
• Arslan AN, Omer J, Yan F (2024) KidneyExchange.jl: A Julia package for solving the kidney exchange problem with branch-and-price. Math. Programming Comput. 16:151–184.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, 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, et al. (2019) Building kidney exchange programmes in Europe—An overview of exchange practice and activities. Transplantation 103(7):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. Eur. J. Oper. Res. 291(2):447–456.Crossref, Google Scholar
• Delorme M, Manlove D, Smeets T (2023) Half-cycle: A new formulation for modelling kidney exchange problems. Oper. Res. Lett. 51(3):234–241.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
• Di Puglia Pugliese L, Guerriero F (2013) A survey of resource constrained shortest path problems: Exact solution approaches. Networks 62(3):183–200.Crossref, 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. (Association for Computing Machinery, New York), 25–42.Google Scholar
• Dror M (1994) Note on the complexity of the shortest path models for column generation in VRPTW. Oper. Res. 42(5):977–978.Link, Google Scholar
• Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44(3):216–229.Crossref, Google Scholar
• Glorie KM, van de Klundert JJ, Wagelmans AP (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
• Glorie KM, Wagelmans APM, van de Klundert JJ (2012) Iterative branch-and-price for hierarchical multi-criteria kidney exchange. Econometric Institute Research Papers EI 2012-11, Erasmus University Rotterdam, Rotterdam, Netherlands.Google Scholar
• Hoffman KL, Padberg M (1993) Solving airline crew scheduling problems by branch-and-cut. Management Sci. 39(6):657–682.Link, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2007) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Kälble T, Lucan M, Nicita G, Sells R, Revilla FB, Wiesel M (2005) Eau guidelines on renal transplantation. Eur. Urology 47(2):156–166.Crossref, Google Scholar
• Klimentova X, Alvelos F, Viana A (2014) A new branch-and-price approach for the kidney exchange problem. Murgante B, Misra S, Rocha AMAC, Torre C, Rocha JG, Falcão MI, Taniar D, Apduhan BO, Gervasi O, eds. Comput. Sci. Its Appl. ICCSA 2014 (Springer, Cham, Switzerland), 237–252.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. Combin. Optim. 33:35–59.Crossref, Google Scholar
• Marzi F, Rossi F, Smriglio S (2019) Computational study of separation algorithms for clique inequalities. Soft Comput. 23:3013–3027.Crossref, Google Scholar
• Mattei N, Walsh T (2013) Preflib: A library for preferences http://www.preflib.org. Perny P, Pirlot M, Tsoukiàs A, eds. Algorithmic Decision Theory ADT 2013 (Springer, Berlin), 259–270.Google Scholar
• Pansart L, Cambazard H, Catusse N (2022) Dealing with elementary paths in the kidney exchange problem. Preprint, submitted January 20, https://arxiv.org/abs/2201.08446.Google Scholar
• PassMark Software (2024) CPU benchmarks. Accessed December 29, 2024, https://www.cpubenchmark.net/singleCompare.php.Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9:61–100.Crossref, Google Scholar
• Petris M, Archetti C, Cattaruzza D, Ogier M, Semet F (2025) A branch-price-and-cut algorithm for the kidney exchange problem. https://doi.org/10.1287/ijoc.2024.0664.cd, https://github.com/INFORMSJoC/2024.0664.Google Scholar
• Plaut B, Dickerson J, Sandholm T (2016) Fast optimal clearing of capped-chain barter exchanges. Proc. AAAI Conf. Artificial Intelligence, vol. 30, no. 1 (AAAI Press, Palo Alto, CA).Google Scholar
• Riascos-Álvarez LC, Bodur M, Aleman DM (2023) A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem. Manufacturing Service Oper. Management 26(2):485–499.Link, Google Scholar
• Roodnat J, Zuidema W, van de Wetering J, de Klerk M, Erdman R, Massey E, Hilhorst M, IJzermans J, Weimar W (2010) Altruistic donor triggered domino-paired kidney donation for unsuccessful couples from the kidney-exchange program. Amer. J. Transplantation 10(4):821–827.Crossref, Google Scholar
• Roth AE, Sönmez T, Ünver MU (2004) Kidney exchange. Quart. J. Econom. 119(2):457–488.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, Ü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.Crossref, Google Scholar
• Yoo KD, Kim CT, Kim MH, Noh J, Kim G, Kim H, An JN, et al. (2016) Superior outcomes of kidney transplantation compared with dialysis: An optimal matched analysis of a national population-based cohort study between 2005 and 2008 in Korea. Medicine 95(33):e4352.Crossref, Google Scholar