IDEAS home Printed from https://ideas.repec.org/a/inm/ormsom/v26y2024i2p485-499.html

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Lizeth C. Riascos-Álvarez & Merve Bodur & Dionne M. Aleman, 2024. "A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem," Manufacturing & Service Operations Management, INFORMS, vol. 26(2), pages 485-499, March.
    • Handle: RePEc:inm:ormsom:v:26:y:2024:i:2:p:485-499
    DOI: 10.1287/msom.2022.0192
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/msom.2022.0192
    Download Restriction: no
    File URL: https://libkey.io/10.1287/msom.2022.0192?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. David R. Morrison & Edward C. Sewell & Sheldon H. Jacobson, 2016. "Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 67-82, February.
    2. Kristiaan M. Glorie & J. Joris van de Klundert & Albert P. M. Wagelmans, 2014. "Kidney Exchange with Long Chains: An Efficient Pricing Algorithm for Clearing Barter Exchanges with Branch-and-Price," Manufacturing & Service Operations Management, INFORMS, vol. 16(4), pages 498-512, October.
    3. Margarita P. Castro & Andre A. Cire & J. Christopher Beck, 2020. "An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 263-278, April.
    4. Anderson, Ross & Ashlagi, Itai & Gamarnik, David & Roth, Alvin E., 2015. "Finding long chains in kidney exchange using the traveling salesman problem," Scholarly Articles 30830063, Harvard University Department of Economics.
    5. Itai Ashlagi & David Gamarnik & Michael A. Rees & Alvin E. Roth, 2012. "The Need for (long) Chains in Kidney Exchange," NBER Working Papers 18202, National Bureau of Economic Research, Inc.
    6. Klimentova, Xenia & Viana, Ana & Pedroso, João Pedro & Santos, Nicolau, 2021. "Fairness models for multi-agent kidney exchange programmes," Omega, Elsevier, vol. 102(C).
    7. Kinable, Joris & Cire, Andre A. & van Hoeve, Willem-Jan, 2017. "Hybrid optimization methods for time-dependent sequencing problems," European Journal of Operational Research, Elsevier, vol. 259(3), pages 887-897.
    8. Itai Ashlagi & Alvin E. Roth, 2021. "Kidney Exchange: An Operations Perspective," Management Science, INFORMS, vol. 67(9), pages 5455-5478, September.
    9. Andre A. Cire & Willem-Jan van Hoeve, 2013. "Multivalued Decision Diagrams for Sequencing Problems," Operations Research, INFORMS, vol. 61(6), pages 1411-1428, December.
    10. John P. Dickerson & Ariel D. Procaccia & Tuomas Sandholm, 2019. "Failure-Aware Kidney Exchange," Management Science, INFORMS, vol. 65(4), pages 1768-1791, April.
    11. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    12. Biró, Péter & van de Klundert, Joris & Manlove, David & Pettersson, William & Andersson, Tommy & Burnapp, Lisa & Chromy, Pavel & Delgado, Pablo & Dworczak, Piotr & Haase, Bernadette & Hemke, Aline & J, 2021. "Modelling and optimisation in European Kidney Exchange Programmes," European Journal of Operational Research, Elsevier, vol. 291(2), pages 447-456.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mehdi Zeynivand & Mehdi Najafi & Mohammad Modarres Yazdi, 2023. "A Recourse Policy to Improve Number of Successful Transplants in Uncertain Kidney Exchange Programs," Journal of Optimization Theory and Applications, Springer, vol. 197(2), pages 476-507, May.
    2. Tuan Le & Jon M. Stauffer & Bala Shetty & Chelliah Sriskandarajah, 2023. "An optimization framework for analyzing dual‐donor organ exchange," Production and Operations Management, Production and Operations Management Society, vol. 32(3), pages 740-761, March.
    3. Margarita P. Castro & Andre A. Cire & J. Christopher Beck, 2022. "Decision Diagrams for Discrete Optimization: A Survey of Recent Advances," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2271-2295, July.
    4. Klimentova, Xenia & Biró, Péter & Viana, Ana & Costa, Virginia & Pedroso, João Pedro, 2023. "Novel integer programming models for the stable kidney exchange problem," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1391-1407.
    5. John P. Dickerson & Ariel D. Procaccia & Tuomas Sandholm, 2019. "Failure-Aware Kidney Exchange," Management Science, INFORMS, vol. 65(4), pages 1768-1791, April.
    6. Kristóf Druzsin & Péter Biró & Xenia Klimentova & Rita Fleiner, 2024. "Performance evaluation of national and international kidney exchange programmes with the ENCKEP simulator," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 32(4), pages 923-943, December.
    7. Arvind U. Raghunathan & David Bergman & John N. Hooker & Thiago Serra & Shingo Kobori, 2024. "Seamless Multimodal Transportation Scheduling," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 336-358, March.
    8. Amin Hosseininasab & Willem-Jan van Hoeve, 2021. "Exact Multiple Sequence Alignment by Synchronized Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 721-738, May.
    9. Sundara Natarajan Panchanatham & Michael Freeman & Harry Groenevelt & Sameer Hasija, 2022. "Be the Match: Optimizing Capacity Allocation for Allogeneic Stem Cell Transplantation," Manufacturing & Service Operations Management, INFORMS, vol. 24(6), pages 3019-3038, November.
    10. Itai Ashlagi & Maximilien Burq & Patrick Jaillet & Vahideh Manshadi, 2019. "On Matching and Thickness in Heterogeneous Dynamic Markets," Operations Research, INFORMS, vol. 67(4), pages 927-949, July.
    11. Kratz, Jörgen, 2024. "Conflicting objectives in kidney exchange," Journal of Economic Theory, Elsevier, vol. 217(C).
    12. Johannes Maschler & Günther R. Raidl, 2021. "Multivalued decision diagrams for prize-collecting job sequencing with one common and multiple secondary resources," Annals of Operations Research, Springer, vol. 302(2), pages 507-531, July.
    13. Domenico Serra & Carmine Sorgente & Monica Gentili & Raffaele Cerulli, 2026. "Kidney Exchanges with Desensitization and Orphans: A Matheuristic Approach," SN Operations Research Forum, Springer, vol. 7(1), pages 1-46, March.
    14. Biró, Péter & van de Klundert, Joris & Manlove, David & Pettersson, William & Andersson, Tommy & Burnapp, Lisa & Chromy, Pavel & Delgado, Pablo & Dworczak, Piotr & Haase, Bernadette & Hemke, Aline & J, 2021. "Modelling and optimisation in European Kidney Exchange Programmes," European Journal of Operational Research, Elsevier, vol. 291(2), pages 447-456.
    15. Margarida Carvalho & Xenia Klimentova & Kristiaan Glorie & Ana Viana & Miguel Constantino, 2021. "Robust Models for the Kidney Exchange Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 861-881, July.
    16. Margarita P. Castro & Andre A. Cire & J. Christopher Beck, 2020. "An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 263-278, April.
    17. St-Arnaud, William & Carvalho, Margarida & Farnadi, Golnoosh, 2025. "Adaptation, comparison and practical implementation of fairness schemes in Kidney Exchange Programs," European Journal of Operational Research, Elsevier, vol. 325(1), pages 38-52.
    18. Rachael Colley & David Manlove & Daniel Paulusma & Mengxiao Zhang, 2025. "Complexity and Manipulation of International Kidney Exchange Programmes with Country-Specific Parameters," Papers 2506.04092, arXiv.org, revised Jun 2025.
    19. Filipe Alvelos & Xenia Klimentova & Ana Viana, 2019. "Maximizing the expected number of transplants in kidney exchange programs with branch-and-price," Annals of Operations Research, Springer, vol. 272(1), pages 429-444, January.
    20. de Weerdt, Mathijs & Baart, Robert & He, Lei, 2021. "Single-machine scheduling with release times, deadlines, setup times, and rejection," European Journal of Operational Research, Elsevier, vol. 291(2), pages 629-639.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormsom:v:26:y:2024:i:2:p:485-499. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.