運(yùn)籌學(xué)整數(shù)分析案例

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

2、成為一種標(biāo)準(zhǔn)模式。配對捐贈(zèng)聯(lián)盟（APD）就是這樣一個(gè)運(yùn)用優(yōu)化算法和市場設(shè)計(jì)等運(yùn)籌學(xué)理論去提高配型效率的組織。,CONTANTS,背景,運(yùn)籌學(xué)運(yùn)用,算法與優(yōu)化,效果與結(jié)論,腎移植背景問題困境,,,短鏈和同時(shí)鏈長鏈和異時(shí)鏈,首位循環(huán)交易算法遞歸算法,在APD的表現(xiàn)在美國其他移植網(wǎng)絡(luò)的影響,,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.,,,可供移植腎源短缺,可供移植腎臟主要有兩個(gè)來源：已故捐贈(zèng)人病患親屬朋友捐贈(zèng),腎臟嚴(yán)重排異,腎臟配型是一個(gè)復(fù)雜而審慎的過程，主要需要血型和組織兩部分的兼容。即使

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

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

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

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

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

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

10、者供體對數(shù)據(jù)。這些標(biāo)注為藍(lán)色的病人大多是高致敏。因此，他們無法參與循環(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算法是單邊匹配理論的基石。以腎交換為例，具體步驟如下：每組捐贈(zèng)配對捐獻(xiàn)組包括2人，即患者和定向?yàn)槠渚枘I的捐獻(xiàn)者，表示為（ki，ti），其中ki是捐贈(zèng)者的腎臟，ti是作為病人的接受者。由腎臟與病人排序列單必定組成一個(gè)循環(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)的所有被指向的病人得到腎臟，重復(fù)以上步驟，直到每個(gè)病人得到腎臟為止。TTC算法產(chǎn)生的匹配結(jié)果滿足帕累托有效性、穩(wěn)定性及激勵(lì)相容性。TTC機(jī)制等價(jià)于嚴(yán)格“核”機(jī)制，當(dāng)偏好是嚴(yán)格，它是唯一滿足個(gè)體理性、帕累托有效、抗策略性的一種機(jī)制。,遞歸算法,用這個(gè)算法解決使用約束生成的

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

15、邊是沒有方向性的）。假設(shè)將一些紐扣散落在地上，并且不斷隨機(jī)地將兩個(gè)紐扣之間系上一條線，這樣就得到一個(gè)隨機(jī)圖的例子。 顯而易見，本文中的腎移植案例的腎源匹配就是一個(gè)天然的隨機(jī)圖模型，同時(shí)也是一個(gè)整數(shù)規(guī)劃模型。所以，將移植數(shù)據(jù)庫視作原始圖G(V,E)，使用遞歸算法在計(jì)算機(jī)上進(jìn)行運(yùn)算。,遞歸算法,遞歸：最大化加權(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在每個(gè)邊以二進(jìn)制輸入,,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),,肝臟配對捐贈(zèng)聯(lián)盟（APD）,為了擴(kuò)大活體供者池，A

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