{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:13:03Z","timestamp":1760033583182,"version":"build-2065373602"},"reference-count":46,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T00:00:00Z","timestamp":1746489600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003141","name":"Mexican Council for Science and Technology (CONACyT)","doi-asserted-by":"publisher","award":["CF-2023-I-880","CE876-19","CE1416-20","CE1837-21","241-CE-2022"],"award-info":[{"award-number":["CF-2023-I-880","CE876-19","CE1416-20","CE1837-21","241-CE-2022"]}],"id":[{"id":"10.13039\/501100003141","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004685","name":"Universidad Aut\u00f3noma de Nuevo Le\u00f3n through its Scientific and Technological Research Support Program","doi-asserted-by":"publisher","award":["CF-2023-I-880","CE876-19","CE1416-20","CE1837-21","241-CE-2022"],"award-info":[{"award-number":["CF-2023-I-880","CE876-19","CE1416-20","CE1837-21","241-CE-2022"]}],"id":[{"id":"10.13039\/501100004685","id-type":"DOI","asserted-by":"publisher"}]},{"name":"MDPI","award":["CF-2023-I-880","CE876-19","CE1416-20","CE1837-21","241-CE-2022"],"award-info":[{"award-number":["CF-2023-I-880","CE876-19","CE1416-20","CE1837-21","241-CE-2022"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>Kidney-paired donation programs assist patients in need of a kidney to swap their incompatible donor with another incompatible patient\u2013donor pair for a suitable kidney in return. The kidney exchange problem (KEP) is a mathematical optimization problem that consists of finding the maximum set of matches in a directed graph representing the pool of incompatible pairs. Depending on the specific framework, these matches can come in the form of (bounded) directed cycles or directed paths. This gives rise to a family of KEP models that have been studied over the past few years. Several of these models require an exponential number of constraints to eliminate cycles and chains that exceed a given length. In this paper, we present enhancements to a subset of existing models that exploit the connectivity properties of the underlying graphs, thereby rendering more compact and tractable models in both cycle-only and cycle-and-chain versions. In addition, an efficient algorithm is developed for detecting violated constraints and solving the problem. To assess the value of our enhanced models and algorithm, an extensive computational study was carried out comparing with existing formulations. The results demonstrated the effectiveness of the proposed approach. For example, among the main findings for edge-based cycle-only models, the proposed (*PRE(i)) model uses a new set of constraints and a small subset of the full set of length-k paths that are included in the edge formulation. The proposed model was observed to achieve a more than 98% reduction in the number of such paths among all tested instances. With respect to cycle-and-chain formulations, the proposed (*ReSPLIT) model outperformed Anderson\u2019s arc-based (AA) formulation and the path constrained-TSP formulation on all instances that we tested. In particular, when tested on a difficult sets of instances from the literature, the proposed (*ReSPLIT) model provided the best results compared to the AA and PC-based models.<\/jats:p>","DOI":"10.3390\/computation13050110","type":"journal-article","created":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T11:38:06Z","timestamp":1746531486000},"page":"110","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Algorithm Based on Connectivity Properties for Finding Cycles and Paths on Kidney Exchange Compatibility Graphs"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1053-5183","authenticated-orcid":false,"given":"Roger Z.","family":"R\u00edos-Mercado","sequence":"first","affiliation":[{"name":"Graduate Program in Electrical Engineering, Universidad Aut\u00f3noma de Nuevo Le\u00f3n (UANL), Av. Universidad s\/n, Cd. Universitaria, San Nicol\u00e1s de los Garza 66455, NL, Mexico"}]},{"given":"L. Carolina","family":"Riascos-\u00c1lvarez","sequence":"additional","affiliation":[{"name":"Graduate Program in Mechanical and Industrial Engineering, The University of Toronto, 5 King\u2019s College Road, Toronto, ON M5S 3G8, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8569-0909","authenticated-orcid":false,"given":"Jonathan F.","family":"Bard","sequence":"additional","affiliation":[{"name":"Graduate Program in Operations Research and Industrial Engineering, The University of Texas at Austin, 204 E. Dean Keeton St. C2200, Austin, TX 78712, USA"}]}],"member":"1968","published-online":{"date-parts":[[2025,5,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1752","DOI":"10.1056\/NEJM199706123362412","article-title":"Ethics of a paired-kidney exchange program","volume":"336","author":"Ross","year":"1997","journal-title":"N. Engl. J. Med."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1812","DOI":"10.1056\/NEJMp038228","article-title":"Exchanging kidneys\u2014Advances in living-donor transplantation","volume":"350","author":"Delmonico","year":"2004","journal-title":"N. Engl. J. Med."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1162\/0033553041382157","article-title":"Kidney exchange","volume":"119","author":"Roth","year":"2004","journal-title":"Q. J. Econ."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.jet.2005.04.004","article-title":"Pairwise kidney exchange","volume":"125","author":"Roth","year":"2005","journal-title":"J. Econ. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1257\/000282805774669989","article-title":"A kidney exchange clearinghouse in New England","volume":"95","author":"Roth","year":"2005","journal-title":"Am. Econ. Rev."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1287\/inte.2014.0766","article-title":"Kidney exchange and the alliance for paired donation: Operations research changes the way kidneys are transplanted","volume":"45","author":"Anderson","year":"2015","journal-title":"Interfaces"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1330","DOI":"10.1111\/j.1600-6143.2009.02622.x","article-title":"The roles of dominos and nonsimultaneous chains in kidney paired donation","volume":"9","author":"Gentry","year":"2009","journal-title":"Am. J. Transplant."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1073\/pnas.1421853112","article-title":"Finding long chains in kidney exchange using the traveling salesman problem","volume":"112","author":"Anderson","year":"2015","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"984","DOI":"10.1111\/j.1600-6143.2011.03481.x","article-title":"Nonsimultaneous chains and dominos in kidney-paired donation\u2014Revisited","volume":"11","author":"Ashlagi","year":"2011","journal-title":"Am. J. Transplant."},{"key":"ref_10","unstructured":"Dickerson, J.P., Procaccia, A.D., and Sandholm, T. (2012, January 4\u20138). Optimizing kidney exchange with transplant chains: Theory and reality. Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201912), Volume 2, Valencia, Spain."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Abraham, D.J., Blum, A., and Sandholm, T. (2007, January 11\u201315). Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. Proceedings of the 8th ACM Conference on Electronic Commerce, San Diego, CA, USA.","DOI":"10.1145\/1250910.1250954"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees, and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Can. J. Math."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1142\/S1793830909000373","article-title":"Maximum weight cycle packing in directed graphs, with application to kidney exchange programs","volume":"1","author":"Manlove","year":"2009","journal-title":"Discret. Math. Algorithms Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1257\/aer.97.3.828","article-title":"Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences","volume":"97","author":"Roth","year":"2007","journal-title":"Am. Econ. Rev."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ejor.2013.05.025","article-title":"New insights on integer-programming models for the kidney exchange problem","volume":"231","author":"Constantino","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s10878-015-9932-4","article-title":"On the kidney exchange problem: Cardinality constrained cycle and chain problems on directed graphs: A survey of integer programming approaches","volume":"33","year":"2017","journal-title":"J. Comb. Optim."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.cor.2018.06.008","article-title":"A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs","volume":"99","year":"2018","journal-title":"Comput. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"104852","DOI":"10.1016\/j.cor.2019.104852","article-title":"Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange","volume":"115","author":"Lam","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"ref_19","first-page":"5","article-title":"The case for a living emotionally related international kidney donor exchange registry","volume":"18","author":"Rapaport","year":"1986","journal-title":"Transplant. Proc."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1539","DOI":"10.1097\/00007890-200004270-00001","article-title":"Ethical issues in increasing living kidney donations by expanding kidney paired exchange programs","volume":"69","author":"Ross","year":"2000","journal-title":"Transplantation"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2694","DOI":"10.1111\/j.1600-6143.2006.01515.x","article-title":"Utilizing list exchange and nondirected donation through \u2018chain\u2019 paired kidney donations","volume":"6","author":"Roth","year":"2006","journal-title":"Am. J. Transplant."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1097\/01.tp.0000195775.77081.25","article-title":"Increasing the opportunity of live kidney donation by matching for two- and three-way exchanges","volume":"81","author":"Saidman","year":"2006","journal-title":"Transplantation"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Dickerson, J.P., Manlove, D.F., Plaut, B., Sandholm, T., and Trimble, J. (2016, January 24\u201328). Position-indexed formulations for kidney exchange. Proceedings of the 2016 ACM Conference on Economics and Computation (EC\u201916), Maastricht, The Netherlands.","DOI":"10.1145\/2940716.2940759"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/s10479-017-2647-4","article-title":"Maximizing the expected number of transplants in kidney exchange programs with branch-and-price","volume":"272","author":"Alvelos","year":"2019","journal-title":"Ann. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Plaut, B., Dickerson, J.P., and Sandholm, T. (2016, January 12\u201317). Fast optimal clearing of capped-chain barter exchanges. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA.","DOI":"10.1609\/aaai.v30i1.10053"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/msom.2014.0496","article-title":"Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price","volume":"16","author":"Glorie","year":"2014","journal-title":"Manuf. Serv. Oper. Manag."},{"key":"ref_27","first-page":"485","article-title":"A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem","volume":"26","author":"Bodur","year":"2023","journal-title":"Manuf. Serv. Oper. Manag."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/s12532-023-00251-7","article-title":"KidneyExchange.jl: A Julia package for solving the kidney exchange problem with branch-and-price","volume":"16","author":"Arslan","year":"2024","journal-title":"Math. Program. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1768","DOI":"10.1287\/mnsc.2018.3026","article-title":"Failure-aware kidney exchange","volume":"65","author":"Dickerson","year":"2019","journal-title":"Manag. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Murgante, B., Misra, S., Rocha, A.M.A.C., Torre, C., Rocha, J.G., Falc\u00e3o, M.I., Taniar, D., Apduhan, B.O., and Gervasi, O. (2014). Maximizing expectation on vertex-disjoint cycle packing. Computational Science and Its Applications\u2014ICCSA 2014, Part II, Springer. Volume 8580 of Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-319-09144-0"},{"key":"ref_31","first-page":"2.6:1","article-title":"Paired and altruistic kidney donation in the UK: Algorithms and experimentation","volume":"19","author":"Manlove","year":"2014","journal-title":"Acm J. Exp. Algorithmics"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1391","DOI":"10.1016\/j.ejor.2022.09.031","article-title":"Novel integer programming models for the stable kidney exchange problem","volume":"307","author":"Klimentova","year":"2023","journal-title":"Eur. J. Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"2361","DOI":"10.1111\/j.1600-6143.2007.01935.x","article-title":"Expanding kidney paired donation through participation by compatible pairs","volume":"7","author":"Gentry","year":"2007","journal-title":"Am. J. Transplant."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Dickerson, J.P., Kazachkov, A.M., Procaccia, A., and Sandholm, T. (2017, January 4\u20139). Small representations of big kidney exchange graphs. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.10593"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/j.ejor.2019.09.006","article-title":"Modelling and optimisation in European Kidney Exchange Programmes","volume":"291","author":"Manlove","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_36","unstructured":"Conitzer, V., Hadfield, G., and Vallor, S. (2019, January 27\u201328). Using deceased-donor kidneys to initiate chains of living donor kidney paired donations: Algorithms and experimentation. Proceedings of the 2019 AAAI\/ACM Conference on Artificial Intelligence, Ethics, and Society, Honolulu, HI, USA."},{"key":"ref_37","first-page":"372","article-title":"Dynamic kidney exchange","volume":"77","year":"2010","journal-title":"Rev. Econ. Stud."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Chisca, D., Lombardi, M., Milano, M., and O\u2019Sullivan, B. (2018, January 5\u20137). From offline to online kidney exchange optimization. Proceedings of the 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI), Volos, Greece.","DOI":"10.1109\/ICTAI.2018.00095"},{"key":"ref_39","unstructured":"Boutilier, C. (2009, January 11\u201317). Online stochastic optimization in the large: Application to kidney exchange. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), Pasadena, CA, USA."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1080\/24725579.2019.1640318","article-title":"Kidney-related operations research: A review","volume":"9","author":"Fathi","year":"2019","journal-title":"Iise Trans. Healthc. Syst. Eng."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0898-1221(81)90008-0","article-title":"A strong-connectivity algorithm and its applications in data flow analysis","volume":"7","author":"Sharir","year":"1981","journal-title":"Comput. Math. Appl."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/1097-0037(200009)36:2<69::AID-NET1>3.0.CO;2-Q","article-title":"A polyhedral study of the asymmetric traveling salesman problem with time windows","volume":"36","author":"Ascheuer","year":"2000","journal-title":"Networks"},{"key":"ref_44","unstructured":"Riascos Alvarez, L.C. (2017). Formulations and Algorithms for the Kidney Exchange Problem. [Master Thesis, Universidad Aut\u00f3noma de Nuevo Le\u00f3n]."},{"key":"ref_45","unstructured":"Anderson, R.M. (2014). Stochastic Models and Data Driven Simulations for Healthcare Operations. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0204007","article-title":"Finding all the elementary circuits of a directed graph","volume":"4","author":"Johnson","year":"1975","journal-title":"Siam J. Comput."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/5\/110\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:28:09Z","timestamp":1760030889000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/5\/110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,6]]},"references-count":46,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2025,5]]}},"alternative-id":["computation13050110"],"URL":"https:\/\/doi.org\/10.3390\/computation13050110","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2025,5,6]]}}}