IDEAS home Printed from
   My bibliography  Save this paper

Iterative branch-and-price for hierarchical multi-criteria kidney exchange


  • Glorie, K.M.
  • Wagelmans, A.P.M.
  • van de Klundert, J.J.


Kidney exchange is an increasing modality for transplanting end stage renal disease patients with an incompatible living donor. Typically, the aim is to find an allocation of donors to patients that is optimal with respect to multiple hierarchical criteria. This paper presents an iterative branch-and-price algorithm for clearing such multi-criteria kidney exchanges with large patient-donor pools. Using a polynomial pricing procedure, the algorithm accomodates not only for cycles of incompatible pairs but also for long chains initiated by unspecified donors. Such chains are increasingly common and important in clinical practice, but, as we show, cannot be efficiently dealt with using existing depth-first pricing procedures. Our algorithm also supports individual rationality constraints required for multi-center coordination. Using Dutch kidney exchange data, we show the effect of long term multi-criteria optimization with our algorithm.

Suggested Citation

  • Glorie, K.M. & Wagelmans, A.P.M. & van de Klundert, J.J., 2012. "Iterative branch-and-price for hierarchical multi-criteria kidney exchange," Econometric Institute Research Papers EI 2012-11, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
  • Handle: RePEc:ems:eureir:38649

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. Tayfun Sönmez & Alvin E. Roth & M. Utku Ünver, 2007. "Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences," American Economic Review, American Economic Association, vol. 97(3), pages 828-851, June.
    2. Itai Ashlagi & Alvin E. Roth, 2012. "New Challenges in Multihospital Kidney Exchange," American Economic Review, American Economic Association, vol. 102(3), pages 354-359, May.
    3. Roth, Alvin E. & Sonmez, Tayfun & Unver, Utku & Delmonico, Francis & Saidman, Susan L., 2014. "Utilizing List Exchange and Non-directed Donation through “Chain” Paired Kidney Donations," MPRA Paper 58246, University Library of Munich, Germany.
    4. Saidman, Susan L. & Roth, Alvin E. & Sonmez, Tayfun & Unver, M. Utku & Delmonico, Francis L., 2014. "Increasing the Opportunity of Live Kidney Donation by Matching for Two and Three Way Exchanges," MPRA Paper 58247, University Library of Munich, Germany.
    Full references (including those not matched with items on IDEAS)


    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:ems:eureir:38649. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (RePub). General contact details of provider: .

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

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.