Kidney Exchange with Long Chains: An Efficient Pricing Algorithm for Clearing Barter Exchanges with Branch-and-Price

Kristiaan M. Glorie (), J. Joris van de Klundert () and Albert P. M. Wagelmans ()
Additional contact information
Kristiaan M. Glorie: Econometric Institute, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands
J. Joris van de Klundert: Institute of Health Policy and Management, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands
Albert P. M. Wagelmans: Econometric Institute, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands

Manufacturing & Service Operations Management, 2014, vol. 16, issue 4, 498-512

Abstract: Barter exchange markets are markets in which agents seek to directly trade their goods with each other. Exchanges occur in cycles or in chains in which each agent gives a good to the next agent. Kidney exchange is an important type of barter exchange market that allows incompatible patient–donor pairs to exchange kidneys so the involved patients can receive a transplant. The clearing problem is to find an allocation of donors to patients that is optimal with respect to multiple criteria. To achieve the best possible score on all criteria, long cycles and chains are often needed, particularly when there are many hard-to-match patients. In this paper we show why this may pose difficulties for existing approaches to the optimization of kidney exchanges. We then present a generic iterative branch-and-price algorithm that can deal effectively with multiple criteria, and we show how the pricing problem may be solved in polynomial time for a general class of criteria. Our algorithm is effective even for large, realistic patient–donor pools. Our approach and its effects are demonstrated by using simulations with kidney exchange data from the Netherlands and the United States.

Keywords: kidney exchange; multicriteria optimization; math programming; branch-and-price; simulation (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/msom.2014.0496 (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:16:y:2014:i:4:p:498-512

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 ().