论文标题
处理肾脏交换问题中的基本道路
Dealing with elementary paths in the Kidney Exchange Problem
论文作者
论文摘要
我们研究了一个基本路径问题，该问题出现在解决肾脏交换问题的列生成方案的定价步骤中。后者的目的是在肾脏移植的患者和捐助者中找到捐赠的交流。在非正式的情况下，问题是要确定一组有限长度的周期和链条在有向图中最大化医疗益处。循环公式是限制在捐赠周期的问题的大规模模型，可以通过分支机构和价格有效地解决。但是，当包括捐赠的链条时，定价子问题将变成NP-HARD。本文提出了一种新的完整的专栏生成计划，该计划考虑了利他捐助者发起的这些链条。针对定价问题，NG-Route松弛和颜色编码启发式的非精力动态方法的开发导致了有效的列生成过程。
We study an elementary path problem which appears in the pricing step of a column generation scheme solving the kidney exchange problem. The latter aims at finding exchanges of donations in a pool of patients and donors of kidney transplantations. Informally, the problem is to determine a set of cycles and chains of limited length maximizing a medical benefit in a directed graph. The cycle formulation, a large-scale model of the problem restricted to cycles of donation, is efficiently solved via branch-and-price. When including chains of donation however, the pricing subproblem becomes NP-hard. This article proposes a new complete column generation scheme that takes into account these chains initiated by altruistic donors. The development of non-exact dynamic approaches for the pricing problem, the NG-route relaxation and the color coding heuristic, leads to an efficient column generation process.
