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, Albert P.M. Wagelmans

Research output: Contribution to journalArticlepeer-review

53 Scopus citations


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.

Original languageEnglish
Pages (from-to)498-512
Number of pages15
JournalManufacturing and Service Operations Management
Issue number4
StatePublished - 1 Sep 2014
Externally publishedYes


  • Branch-and-price
  • Kidney exchange
  • Math programming
  • Multicriteria optimization
  • Simulation


Dive into the research topics of 'Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price'. Together they form a unique fingerprint.

Cite this