KidneyAlgo: New Algorithms for UK and International Kidney Exchange

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