运筹学整数分析案例

,运筹学改变肾移植方法,捐献系统中的肾脏交换和配对,黎汉英 惠原君 刘思睿 李锦楠 李椰,关键词：匹配；移植；市场设计；优化；设计；整数规划,摘要,无论从短期效果或长期存活而言，活体肾移植都已经被认为是终末期肾病(ESRD) 的最佳治疗方法。但是对于终末期肾病患者而言，即使有亲戚朋友的自愿捐赠，也仍然要面对供受者之间无法匹配的问题。事实上，这种不相容性可以通过与另一个不相容的患者交换肾脏供体来克服，这样的肾脏交换在美国的肾移植中已经成为一种标准模式。配对捐赠联盟（APD）就是这样一个运用优化算法和市场设计等运筹学理论去提高配型效率的组织。,CONTANTS,背景,运筹学运用,算法与优化,效果与结论,肾移植背景问题困境,短链和同时链长链和异时链,首位循环交易算法递归算法,在APD的表现在美国其他移植网络的影响,01,背景,In the United States, about 100,000 sufferers of ESRD are currently on the waiting list for a kidney transplant from a deceased donor. Transplantation is the preferred treatment for this severe disease.,可供移植肾源短缺,可供移植肾脏主要有两个来源：已故捐赠人病患亲属朋友捐赠,肾脏严重排异,肾脏配型是一个复杂而审慎的过程，主要需要血型和组织两部分的兼容。即使想要捐献肾脏的病患家属通过了严苛的身体检查，也有出现严重排异可能。,肾移植的必要性,对于终末期肾病患者（ESRD）而言，肾移植是世界公认的最优治疗方案。不幸的是,在美国，大约有4000名病人在等待接受移植前就死亡了,还有病人在等待时病情加重以至于无法移植。随着时间的推移，肾源短缺越来越严重。,背景总结,.,要解决移植的困局，就要为肾脏移植寻找一个最大的相容匹配。这是一个经典的组合优化问题，涉及到整数规划和优化算法。,由于肾脏的交换是分散的，所以组织肾脏交换既是一个优化问题，也是一个严肃的市场设计和协调问题,02,运筹学运用,The APD initially adopted design and optimization techniques for identifying short cycles and chains.,短链和同时链,双人简单交叉交换,最初，大多数肾脏交换都以简单的双人循环交换的形式完成，如右图所示。因为要承担失败的风险，这样的交叉交换必须同时进行，而这也成为交换过程中的一个重要的挑战两个最简单的患者肾脏移植需要四个手术室和四个手术团队同时进行肾脏切除和移植。因为这个原因，超过三名病人的肾脏循环交换很少进行。,短链和同时链,简单链条交换,另一种形式的交换形式是一个链，这条捐赠短链的实现首先依靠于一位利他捐助者（NDD）(即肾脏捐赠者的捐赠不要求或指定特定接受者)，见右图。这样的短链所涉及的肾脏循环交换最多不会超过三人，手术时间也不会相隔很远。,长链和异时链,相关优势,有 两个因素始终在促使肾脏配对捐献（KPD） 的模式不断完善，救治更多的终末期肾病（ESRD）患者: ( 1) 如何最大程度的将不匹配供受者人群纳入 KPD中; ( 2) 如何在已纳入 KPD的不匹配供受者之间实现匹配最佳化。而长链和异时链在实际运用中更好地解决了这两个问题,长链和异时链,首先，长链的编排可以尽可能减少破坏链的成本。一个利他捐助者（NDD）是非常珍贵和难得的，尽可能延长捐赠链条就可以帮助更多的ESRD患者。同时，这样的异时链突破了时间限制，更灵活的手术时间和操作成本可以为医院提供更大的操作空间。其次，长链的运用可以更好地帮助高致敏ESRD患者。高度敏感的病人通常需要等待异常长的时间才能从捐赠者处找到一个可用的配型肾脏。许多这样的病人，很难进行两人或三人的短链移植。长链移植，为他们提供了除了等待之外的另一条选择。,长链和异时链,NEAD计划,基于这样的考虑，APD执行了第一个异时拓展利他捐赠(NEAD)长链计划，并且在2007年7月完成了第一例非同时传输的长链式肾移植手术。APD指定在供体接受者完成了移植手术之后，长链中的最后一个捐献者将为链条中下一个部分起到搭建桥梁的作用，这样就能将每一个捐赠者的爱传递下去。有时移植过程会被分解到长达几个月里完成。截止到2008年3月，第一条NEAD链包含了十场移植和十一位捐赠者，他们把自己的肾无偿捐赠给了陌生人。,长链和异时链,长链和异时链,这种兼容性图是从APD得到的患者供体对数据。这些标注为蓝色的病人大多是高致敏。因此，他们无法参与循环交换，但可以作为链条终端。,03,算法与优化,The APD and other kidney exchange programs organize transplants by regularly searching the compatibility graph generated by the current pool of patientsand donors for the maximum weighted number of transplants that can be achieved through cycles and chains. It is convenient to think of the pool as acompatibility network described by a directed graph G（V,E）.,TTC算法,首位交易循环（TTC）,TTC算法是单边匹配理论的基石。以肾交换为例，具体步骤如下：每组捐赠配对捐献组包括2人，即患者和定向为其捐肾的捐献者，表示为（ki，ti），其中ki是捐赠者的肾脏，ti是作为病人的接受者。由肾脏与病人排序列单必定组成一个循环为 （k1，t1，k2，t2，km，tm，k1），即肾脏k1指向病人t1、病人t1指向肾脏k2肾脏km指向病人tm、病人tm又指向肾脏k1形成的循环。,TTC算法,首位交易循环（TTC）,TTC算法是单边匹配理论的基石。然后将肾脏k2安排给病人t1，肾脏k3安排给病人t2肾脏k1安排给病人tm。这些配对的肾脏与病人从市场中移除，然后继续排序，形成循环，循环内的所有被指向的病人得到肾脏，重复以上步骤，直到每个病人得到肾脏为止。TTC算法产生的匹配结果满足帕累托有效性、稳定性及激励相容性。TTC机制等价于严格“核”机制，当偏好是严格，它是唯一满足个体理性、帕累托有效、抗策略性的一种机制。,递归算法,用这个算法解决使用约束生成的优化问题，无需为每一个链条的变量赋值，只需引入流守恒约束。要了解这个算法首先要解释一下随机图的概念：随机图(random graph)，它是伴随有不确定性的图，是按某种随机方式删去一个图G的某些节点或边而保留下来的图，又称为随机子图.G称为随机图的原始图。随机图的性质与原始图，以及随机删除原始图点或边的方式有关.随机删除方式包括只删点、只删边和既删点又删边三种.,递归算法,所以一个随机图实际上就是将给定的顶点之间随机地连上边（边是没有方向性的）。假设将一些纽扣散落在地上，并且不断随机地将两个纽扣之间系上一条线，这样就得到一个随机图的例子。显而易见，本文中的肾移植案例的肾源匹配就是一个天然的随机图模型，同时也是一个整数规划模型。所以，将移植数据库视作原始图G(V,E)，使用递归算法在计算机上进行运算。,递归算法,递归：最大化加权流S.T. Total flow out of a pair is at most the total flow that goes into a pair总输出量不能大于总输入量Total flow out of an altruistic donor is at most 1一例利他捐助最大输出为1Total flow that goes into a pair is at most 1每次输入量最大为1Flow on each edge is binary在每个边以二进制输入,04,效果与结论,Kidney exchange has become a standard part of transplantation in the United States, and the innovative ideas of many researchers and practitioners have played an important role in this success.,在APD的表现,肝脏配对捐赠联盟（APD）,为了扩大活体供者池，APD联合了83家移植中心参与，众多中心将供受者资源整合至 APD 中，使得供受者群体大大增加.在异时链被引入以来，超过220例的ESRD患者通过NEAD长链进行了肾移植，不仅自己重获健康，而且累积为美国医疗保健系统节约了450万美元的透析费用。,对于美国其他移植网络,全美有超过200家移植中心，而