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

• 成果类型: Article
• 署名作者: Glorie, Kristiaan M.; van de Klundert, J. Joris; Wagelmans, Albert P. M.
• 署名单位: Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam; Erasmus University Rotterdam; Erasmus University Rotterdam - Excl Erasmus MC
• 刊物名称: M&SOM-MANUFACTURING & SERVICE OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1523-4614
• DOI: 10.1287/msom.2014.0496
• 发表日期: 2014
• 页码: 498-512
• 关键词: Kidney exchange; multicriteria optimization; math programming; branch-and-price; simulation

摘要

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.