New insights on integer-programming models for the kidney exchange problem
New insights on integer-programming models for the kidney exchange problem
复制标题
DOI：
10.1016/j.ejor.2013.05.025
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
M. Constantino;Xenia Klimentova;Ana Viana;A. Rais
中科院分区：
文献类型：
--
作者：
M. Constantino;Xenia Klimentova;Ana Viana;A. Rais
近年来，一些国家制定了允许两个或更多不相容的患者-捐赠者对之间交换肾脏的政策。这些政策导致了通常所说的肾脏交换计划。基本的优化问题可以用整数规划模型表示。以前提出的肾脏交换计划模型具有指数数量的约束或变量，这使得它们在问题规模较大时相当难以解决。在这项工作中，我们提出了两个紧凑的配方的问题，解释这些配方如何可以适应解决一些问题的变种，并提供一些模型的优势比其他的结果。最后，我们提出了一个系统的比较，我们的模型和两个以前提出的通过彻底的计算分析。结果表明，当问题规模较大时，紧公式比非紧公式具有优势。
In recent years several countries have set up policies that allow exchange of kidneys between two or more incompatible patient–donor pairs. These policies lead to what is commonly known as kidney exchange programs. The underlying optimization problems can be formulated as integer programming models. Previously proposed models for kidney exchange programs have exponential numbers of constraints or variables, which makes them fairly difficult to solve when the problem size is large. In this work we propose two compact formulations for the problem, explain how these formulations can be adapted to address some problem variants, and provide results on the dominance of some models over others. Finally we present a systematic comparison between our models and two previously proposed ones via thorough computational analysis. Results show that compact formulations have advantages over non-compact ones when the problem size is large.