運籌學整數(shù)分析案例

1、,運籌學改變腎移植方法,捐獻系統(tǒng)中的腎臟交換和配對,黎漢英 惠原君 劉思睿 李錦楠 李椰,,關(guān)鍵詞：匹配；移植；市場設計；優(yōu)化；設計；整數(shù)規(guī)劃,摘要,無論從短期效果或長期存活而言，活體腎移植都已經(jīng)被認為是終末期腎病(ESRD) 的最佳治療方法。但是對于終末期腎病患者而言，即使有親戚朋友的自愿捐贈，也仍然要面對供受者之間無法匹配的問題。事實上，這種不相容性可以通過與另一個不相容的患者交換腎臟供體來克服，這樣的腎臟交換在美國的腎移植中已經(jīng)

2、成為一種標準模式。配對捐贈聯(lián)盟（APD）就是這樣一個運用優(yōu)化算法和市場設計等運籌學理論去提高配型效率的組織。,CONTANTS,背景,運籌學運用,算法與優(yōu)化,效果與結(jié)論,腎移植背景問題困境,,,短鏈和同時鏈長鏈和異時鏈,首位循環(huán)交易算法遞歸算法,在APD的表現(xiàn)在美國其他移植網(wǎng)絡的影響,,01,背景,In the United States, about 100,000 sufferers of ESRD are currentl

3、y on the waiting list for a kidney transplant from a deceased donor. Transplantation is the preferred treatment for this severe disease.,,,可供移植腎源短缺,可供移植腎臟主要有兩個來源：已故捐贈人病患親屬朋友捐贈,腎臟嚴重排異,腎臟配型是一個復雜而審慎的過程，主要需要血型和組織兩部分的兼容。即使

4、想要捐獻腎臟的病患家屬通過了嚴苛的身體檢查，也有出現(xiàn)嚴重排異可能。,腎移植的必要性,,,,對于終末期腎病患者（ESRD）而言，腎移植是世界公認的最優(yōu)治療方案。不幸的是,在美國，大約有4000名病人在等待接受移植前就死亡了,還有病人在等待時病情加重以至于無法移植。隨著時間的推移，腎源短缺越來越嚴重。,,,背景總結(jié),.,要解決移植的困局，就要為腎臟移植尋找一個最大的相容匹配。這是一個經(jīng)典的組合優(yōu)化問題，涉及到整數(shù)規(guī)劃和優(yōu)化算法。

5、,由于腎臟的交換是分散的，所以組織腎臟交換既是一個優(yōu)化問題，也是一個嚴肅的市場設計和協(xié)調(diào)問題,,02,運籌學運用,The APD initially adopted design and optimization techniques for identifying short cycles and chains.,,短鏈和同時鏈,,雙人簡單交叉交換,最初，大多數(shù)腎臟交換都以簡單的雙人循環(huán)交換的形式完成，如右圖所示。因為要承擔失敗的

6、風險，這樣的交叉交換必須同時進行，而這也成為交換過程中的一個重要的挑戰(zhàn)——兩個最簡單的患者腎臟移植需要四個手術(shù)室和四個手術(shù)團隊同時進行腎臟切除和移植。因為這個原因，超過三名病人的腎臟循環(huán)交換很少進行。,,短鏈和同時鏈,,簡單鏈條交換,另一種形式的交換形式是一個鏈，這條捐贈短鏈的實現(xiàn)首先依靠于一位利他捐助者（NDD）(即腎臟捐贈者的捐贈不要求或指定特定接受者)，見右圖。這樣的短鏈所涉及的腎臟循環(huán)交換最多不會超過三人，手術(shù)時間也不會

7、相隔很遠。,,長鏈和異時鏈,,相關(guān)優(yōu)勢,有 兩個因素始終在促使腎臟配對捐獻（KPD） 的模式不斷完善，救治更多的終末期腎?。‥SRD）患者: ( 1) 如何最大程度的將不匹配供受者人群納入 KPD中; ( 2) 如何在已納入 KPD的不匹配供受者之間實現(xiàn)匹配最佳化。而長鏈和異時鏈在實際運用中更好地解決了這兩個問題,,長鏈和異時鏈,,首先，長鏈的編排可以盡可能減少破壞鏈的成本。一個利他捐助者（NDD）是非常珍貴和難得的，盡可能延

8、長捐贈鏈條就可以幫助更多的ESRD患者。同時，這樣的異時鏈突破了時間限制，更靈活的手術(shù)時間和操作成本可以為醫(yī)院提供更大的操作空間。其次，長鏈的運用可以更好地幫助高致敏ESRD患者。高度敏感的病人通常需要等待異常長的時間才能從捐贈者處找到一個可用的配型腎臟。許多這樣的病人，很難進行兩人或三人的短鏈移植。長鏈移植，為他們提供了除了等待之外的另一條選擇。,,長鏈和異時鏈,,NEAD計劃,基于這樣的考慮，APD執(zhí)行了第一個異時拓展利他捐贈(

9、NEAD)長鏈計劃，并且在2007年7月完成了第一例非同時傳輸?shù)拈L鏈式腎移植手術(shù)。APD指定在供體接受者完成了移植手術(shù)之后，長鏈中的最后一個捐獻者將為鏈條中下一個部分起到搭建橋梁的作用，這樣就能將每一個捐贈者的愛傳遞下去。有時移植過程會被分解到長達幾個月里完成。截止到2008年3月，第一條NEAD鏈包含了十場移植和十一位捐贈者，他們把自己的腎無償捐贈給了陌生人。,,長鏈和異時鏈,,,長鏈和異時鏈,,這種兼容性圖是從APD得到的患

10、者供體對數(shù)據(jù)。這些標注為藍色的病人大多是高致敏。因此，他們無法參與循環(huán)交換，但可以作為鏈條終端。,,03,算法與優(yōu)化,The APD and other kidney exchange programs organize transplants by regularly searching the compatibility graph generated by the current pool of patientsand don

11、ors 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算法,首位交易循環(huán)（TTC）,

12、TTC算法是單邊匹配理論的基石。以腎交換為例，具體步驟如下：每組捐贈配對捐獻組包括2人，即患者和定向為其捐腎的捐獻者，表示為（ki，ti），其中ki是捐贈者的腎臟，ti是作為病人的接受者。由腎臟與病人排序列單必定組成一個循環(huán)為 （k1，t1，k2，t2，…km，tm，k1），即腎臟k1指向病人t1、病人t1指向腎臟k2……腎臟km指向病人tm、病人tm又指向腎臟k1形成的循環(huán)。,TTC算法,首位交易循環(huán)（TTC）,TTC算法是單

13、邊匹配理論的基石。然后將腎臟k2安排給病人t1，腎臟k3安排給病人t2……腎臟k1安排給病人tm。這些配對的腎臟與病人從市場中移除，然后繼續(xù)排序，形成循環(huán)，循環(huán)內(nèi)的所有被指向的病人得到腎臟，重復以上步驟，直到每個病人得到腎臟為止。TTC算法產(chǎn)生的匹配結(jié)果滿足帕累托有效性、穩(wěn)定性及激勵相容性。TTC機制等價于嚴格“核”機制，當偏好是嚴格，它是唯一滿足個體理性、帕累托有效、抗策略性的一種機制。,遞歸算法,用這個算法解決使用約束生成的

14、優(yōu)化問題，無需為每一個鏈條的變量賦值，只需引入流守恒約束。要了解這個算法首先要解釋一下隨機圖的概念：隨機圖(random graph)，它是伴隨有不確定性的圖，是按某種隨機方式刪去一個圖G的某些節(jié)點或邊而保留下來的圖，又稱為隨機子圖.G稱為隨機圖的原始圖。隨機圖的性質(zhì)與原始圖，以及隨機刪除原始圖點或邊的方式有關(guān).隨機刪除方式包括只刪點、只刪邊和既刪點又刪邊三種.,遞歸算法,所以一個隨機圖實際上就是將給定的頂點之間隨機地連上邊（

15、邊是沒有方向性的）。假設將一些紐扣散落在地上，并且不斷隨機地將兩個紐扣之間系上一條線，這樣就得到一個隨機圖的例子。 顯而易見，本文中的腎移植案例的腎源匹配就是一個天然的隨機圖模型，同時也是一個整數(shù)規(guī)劃模型。所以，將移植數(shù)據(jù)庫視作原始圖G(V,E)，使用遞歸算法在計算機上進行運算。,遞歸算法,遞歸：最大化加權(quán)流S.T. Total flow out of a pair is at most the total f

16、low 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,效果與結(jié)論,Kidney ex

17、change 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的表現(xiàn),,肝臟配對捐贈聯(lián)盟（APD）,為了擴大活體供者池，A

18、PD聯(lián)合了83家移植中心參與，眾多中心將供受者資源整合至 APD 中，使得供受者群體大大增加.在異時鏈被引入以來，超過220例的ESRD患者通過NEAD長鏈進行了腎移植，不僅自己重獲健康，而且累積為美國醫(yī)療保健系統(tǒng)節(jié)約了450萬美元的透析費用。,,對于美國其他移植網(wǎng)絡,,全美有超過200家移植中心，而自從NEAD鏈條實施以來，2600例腎臟移植中超過75%的ESRD患者都通過這樣的方式更早的實現(xiàn)了腎臟配型和移植。雖然美國的美國的