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

Lizeth C. Riascos-Álvarez (), Merve Bodur () and Dionne M. Aleman ()
Additional contact information
Lizeth C. Riascos-Álvarez: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Merve Bodur: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Dionne M. Aleman: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada; Institute of Health Policy, Management and Evaluation, University of Toronto, Toronto, Ontario M5S 3E3, Canada; Techna Institute at University Health Network, Toronto, Ontario M5G 1P5, Canada

Manufacturing & Service Operations Management, 2024, vol. 26, issue 2, 485-499

Abstract: Problem definition: Kidney paired donation programs allow patients registered with an incompatible donor to receive a suitable kidney from another donor, as long as the latter’s co-registered patient, if any, also receives a kidney from a different donor. The kidney exchange problem (KEP) aims to find an optimal collection of kidney exchanges taking the form of cycles and chains. Methodology/results: We develop the first decomposition method that is able to consider long cycles and long chains for projected large realistic instances. Particularly, we propose a branch-and-price framework in which the pricing problems are solved (for the first time in packing problems in a digraph) through multivalued decision diagrams. We present a new upper bound on the optimal value of the KEP, obtained via our master problem. Computational experiments show superior performance of our method over the state of the art by optimally solving almost all instances in the PrefLib library for multiple cycle and chain lengths. Managerial implications: Our algorithm also allows the prioritization of the solution composition, for example, chains over cycles or vice versa, and we conclude, similar to previous findings, that chains benefit the overall matching efficiency and highly sensitized patients.

Keywords: kidney exchange; integer programming; branch and price; multivalued decision diagrams (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/msom.2022.0192 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormsom:v:26:y:2024:i:2:p:485-499

Access Statistics for this article

More articles in Manufacturing & Service Operations Management from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().