KidneyAlgo: New Algorithms for UK and International Kidney Exchange

肾衰竭可能会对患者的生活产生毁灭性的影响。与透析相比，移植提供了更好的长期生存前景，但捐赠者严重短缺。与已故肾脏捐赠相比，活体肾脏捐赠(LKD)在患者和移植患者的长期效果方面甚至更好。然而，例如，医疗配型不相容可能会阻止活着的捐赠者将肾脏捐赠给需要帮助的亲人。肾脏交换计划(KEP)允许需要肾脏移植的受者，以及有自愿但医学上不相容的捐赠者的受者，与另一受者“交换”自己的捐赠者，从而导致移植循环，从而增加LKD。无私的捐赠者可能会触发一连串的移植手术，也会让多个受赠者受益。英国活肾共享计划(UKLKSS)是欧洲最大的肾移植计划，由NHS血液和移植中心(NHSBT)运营。自2008年以来，NHSBT一直使用曼洛夫和他的同事开发的算法来为UKLKSS匹配运行找到最优解决方案。今后有几种方式可以扩大和加强UKLKSS，以促进更好的匹配和更多的移植，如下：1.出于后勤原因，目前周期和链条的长度受到限制。允许比现在更长的周期和链条将导致更多的肾脏移植。英国和其他国家之间的国际合作将带来更多的移植机会，特别是对高度敏感(难以匹配)的接受者。在存在更长的周期和链条以及国际合作的情况下，现有对“最佳”解决办法的解释将不再有效。进行模拟将使NHSBT能够根据对模拟数据的长期影响准确地确定他们希望优化什么。交付这些增强将涉及解决以下复杂的研究挑战：(RC1)：为更大的池和更长的周期/链设计算法。由于寻找最优肾脏交换的基本计算问题是棘手的，需要先进的技术来有效地找到解决方案。(RC2)：设计国际肾脏交换的算法。当多个国家参与一项国际KEP时，公平和稳定的关键考虑因素变得重要。(RC3)：设计算法以应对最优标准的变化。对最优目标的微小更改可能需要对算法进行重大更改以找到最优解。(RC4)：创建动态数据集生成器，生成反映现实世界特征的实例。这将为NHSBT的不同优化标准的影响提供现实的估计。拟议的项目将通过格拉斯哥和达勒姆之间的新合作来应对所有这些挑战。这将提供曼洛夫在配对问题和肾脏交换方面的专业知识与Paulusma在配对问题和国际肾脏交换的博弈论方面的专业知识之间的协同。所需的主要资源是格拉斯哥和达勒姆的博士后研究助理以及格拉斯哥的一名研究软件工程师。项目合作伙伴NHSBT将是项目团队的关键成员。该项目还将受益于下列访问研究人员的专门知识：Maxence Delorme(蒂尔堡大学，运筹学)、Péter Biró和Márton Benedek(KRTK布达佩斯，算法博弈论)。工作方案包括三个相互关联的工作包，如下：WP1：使用先进的整数规划技术为国家KEP设计新算法。WP2：使用合作博弈论的技术为国际KEP设计新算法。WP3：软件实施和实验评估，其中将包括为UKLKSS建立新软件，认识到该项目的影响。

Kidney failure can have a devastating impact on patients' lives. Transplantation offers much better long-term survival prospects compared to dialysis, but there is an acute shortage of donors. Compared to deceased kidney donation, living-donor kidney donation (LKD) has even better long-term patient and transplant outcomes. However, medical incompatibility, for example, may prevent a living donor from donating a kidney to a loved one who is in need.Kidney Exchange Programmes (KEPs) help to increase LKD by allowing recipients who require a kidney transplant, and who have a willing but medically incompatible donor, to "swap" their donor with that of another recipient, leading to a cycle of transplants. Altruistic donors may trigger chains of transplants that can also benefit multiple recipients.The UK Living Kidney Sharing Scheme (UKLKSS), which is operated by NHS Blood and Transplant (NHSBT), is the largest KEP in Europe. Algorithms developed by Manlove and his colleagues have been used by NHSBT to find optimal solutions for UKLKSS matching runs every quarter since 2008. There are several ways in which the UKLKSS can be expanded and strengthened in the future, to facilitate better matches and more transplants, as follows:1. Cycles and chains are currently restricted in length for logistical reasons. Allowing longer cycles and chains than at present will lead to more kidney transplants.2. International collaboration between the UK and other countries will lead to more transplantation opportunities, particularly for highly sensitised (hard to match) recipients.3. In the presence of longer cycles and chains, and international collaboration, the existing interpretation of an "optimal" solution will no longer be valid. Conducting simulations will allow NHSBT to determine exactly what they wish to optimise in the light of long-term effects on simulated data.Delivering these enhancements will involve tackling the following complex research challenges:(RC1): design algorithms for larger pools and longer cycles / chains. As the underlying computational problem of finding an optimal set of kidney exchanges is intractable, advanced techniques are required to find a solution efficiently.(RC2): design algorithms for international kidney exchange. When multiple countries are participating in an international KEP, key considerations of fairness and stability become important.(RC3): design algorithms to cope with changes to optimality criteria. A small change to an optimality objective can necessitate significant changes to the algorithm to find an optimal solution.(RC4): create a dynamic dataset generator, producing instances that reflect real-world characteristics. This will give realistic estimates of the effects of different optimality criteria for NHSBT.The proposed project will meet all these challenges via a new collaboration between Glasgow and Durham. This will provide a synergy between the expertise of Manlove in matching problems and kidney exchange, and that of Paulusma in game-theoretic aspects of matching problems and international kidney exchange.The main resources requested are Postdoctoral Research Associates at Glasgow and Durham, and a Research Software Engineer at Glasgow. The project partner NHSBT will be a key member of the project team. The project will also benefit from the expertise of the following visiting researchers: Maxence Delorme (Tilburg University, operational research), Péter Biró and Márton Benedek (KRTK Budapest, algorithmic game theory).The work programme comprises three interconnected work packages, as follows:WP1: design of new algorithms for national KEPs, using advanced integer programming techniques.WP2: design of new algorithms for international KEPs, using techniques from cooperative game theory.WP3: software implementation and experimental evaluation, which will include building new software for the UKLKSS, realising the impact of this project.