Оптимальный обмен почек

Оптимальный обмен почек (ОКЕ) — это проблема оптимизации, с которой сталкиваются программы парного донорства почек (также называемые программами обмена почек). Такие программы имеют большие базы данных пар пациент-донор, где донор готов пожертвовать почку, чтобы помочь пациенту, но не может сделать это из-за медицинской несовместимости. Центры стараются наладить обмены между такими парами. Например, донор в паре A делает пожертвование пациенту в паре B, донор в паре B делает пожертвование пациенту в паре C, а донор в паре C делает пожертвование пациенту в паре A.

Цель задачи OKE — найти оптимальную схему таких обменов. «Оптимальный» обычно означает, что количество трансплантаций как можно больше, но могут быть и другие цели. Важнейшим ограничением в этой задаче оптимизации является то, что донор передает почку только в том случае, если его пациент получает совместимую почку, так что ни одна пара не потеряет почку из-за участия. Это требование иногда называют индивидуальной рациональностью .

Задача OKE имеет множество вариантов, которые различаются допустимым размером каждого обмена, целевой функцией и другими факторами. ^{[ 1 ]}

Определения

Вход

Экземпляр OKE обычно описывается как ориентированный граф . Каждый узел представляет собой пару пациент-донор. Направленная дуга от пары А к паре Б означает, что донор в паре А совместим с медицинской точки зрения с пациентом в паре Б (совместимость определяется на основе групп крови донора и пациента, а также других факторов, таких как определенные антигены в паре Б). их кровь). в Направленный цикл графе совместимости представляет собой возможный обмен. Направленный цикл размера 2 (например, A -> B -> A) представляет собой возможный попарный обмен — обмен между парой пар.

Более общий вариант ОКЭ рассматривает также узлы второго типа, которые представляют собой альтруистических доноров - доноров, которые не связаны с пациентом и готовы пожертвовать почку любому совместимому пациенту. Альтруистические донорские узлы имеют только исходящие дуги. С донорами-альтруистами можно устраивать обмены не только циклами, но и цепочками , начиная с донора-альтруиста.

Дуги на графике могут иметь веса, представляющие, например, вероятность успеха задействованных трансплантатов. У них также могут быть приоритеты, определяемые, например, срочностью оказания медицинской помощи или временем ожидания пациента в очереди на трансплантацию.

Выход

Выходом OKE является набор попарно непересекающихся направленных циклов (и, возможно, направленных цепочек, если доступны альтруистические доноры). Самая простая цель OKE — максимально увеличить число пациентов, которым пересадят почку. Другими общими целями являются:

Максимизация взвешенной суммы почечного обмена: ^{[ 2 ]} Каждое ребро в графе имеет вес, и цель состоит в том, чтобы найти обмен, который максимизирует сумму весов на всех ребрах, используемых в обмене.
Максимизация ожидаемой продолжительности жизни кандидатов на трансплантацию или их ожидаемой продолжительности жизни с поправкой на качество . ^{[ 3 ]}

Неограниченная длина цикла

Первоначально проблема изучалась без каких-либо ограничений на длину циклов обмена. Рот, Сонмез и Унвер ^{[ 4 ]} представил механизм, основанный на расширении механизма верхних торговых циклов , для поиска валютных циклов оптимальным по Парето и совместимым со стимулами способом.

Авраам, Блюм и Сандхольм ^{[ 5 ]} покажите, что при неограниченной длине цикла обмен максимальной мощности и максимального веса может быть найден за полиномиальное время. Например, чтобы найти обмен максимальной мощности, учитывая исходный ориентированный граф G , постройте неориентированный двудольный граф H( X + Y , E ), в котором:

Каждая пара j в G имеет два узла: x _j (представляющий донора) и y _j (представляющий пациента). Они соединены ребром веса 1.
Для каждого ребра i -> j в G добавьте в H ребро x _i -- y _j веса 1+1/n.
Найдите паросочетание максимального веса в H .

Каждый обмен максимальной мощности в G соответствует сопоставлению максимального веса в H. Обратите внимание, что веса гарантируют, что каждое сопоставление максимального веса в H является идеальным, так что каждый пациент сопоставляется либо с совместимым донором, либо со своим собственным. донор. Таким образом, ни один донор не передает почку, пока его пациент не получит почку, что удовлетворяет требованию индивидуальной рациональности.

Этот алгоритм легко распространить на обмены с максимальным весом и включить в него альтруистических доноров.

Попарный обмен почками

В ходе обсуждений реализации программы обмена почками в Новой Англии в 2004 году выяснилось, что с точки зрения логистики возможен только парный обмен. Это связано с тем, что все операции при обмене должны выполняться одновременно. Это требование направлено на обеспечение ограничения индивидуальной рациональности – во избежание риска того, что донор откажется от донорства после того, как его пациент получил почку. Цикл обмена размером k требует 2k одновременных операций. В то время организовывать более 4-х одновременных операций было непрактично, поэтому размер циклов был ограничен 2-мя. ^{[ 6 ]}

В этой настройке можно свести направленный граф совместимости к неориентированному графу, где пары A и B связаны тогда и только тогда, когда A->B и B->A. Поиск парного обмена максимальной мощности эквивалентен поиску соответствия максимальной мощности в этом неориентированном графе. Более того, когда разрешены только попарные обмены, сопоставление является эффективным по Парето тогда и только тогда, когда оно имеет максимальную мощность. ^{[ 6 ]}^{: Лем.1} Следовательно, такой обмен можно найти за полиномиальное время.

Рот, Сонмез и Унвер ^{[ 6 ]} изучите два расширения простого обмена максимальной мощности:

Учитывая приоритетность пациентов или трансплантатов, можно за полиномиальное время найти приоритетное сопоставление - сопоставление, которое среди всех сопоставлений максимальной мощности максимизирует количество пациентов с более высоким приоритетом. Более того, эти алгоритмы можно сделать совместимыми по стимулам в том смысле, что каждый пациент максимизирует свои шансы на совпадение, привлекая в систему как можно больше доноров и соглашаясь принять как можно больше почек. В доказательствах используются понятия теории графов, такие как разложение Галлаи–Эдмондса .
Можно найти стохастический обмен, в котором паросочетание выбирается случайным образом среди всех паросочетаний максимальной мощности. Эгалитарный механизм направлен на максимизацию наименьшей вероятности того , что пациент получит почку. Эгалитарный механизм совместим со стимулами в том же смысле, что и механизм приоритета.

Циклы длины k

В последующие годы улучшения в логистике позволили выполнять большее количество одновременных операций. Соответственно, стали возможны циклы обмена с участием трех и более пар. Нахождение обмена максимальной мощности называется, в терминах теории графов, максимальной упаковкой цикла . Максимальная упаковка циклов с циклами длины не более k для любого фиксированного k ≥ 3 является NP-трудной вычислительной задачей . ^{[ 5 ]} (это можно доказать редукцией к задаче о трехмерном паросочетании в гиперграфе).

Авраам, Блюм и Сандхольм ^{[ 5 ]} представить два метода упаковки максимального цикла: генерацию столбцов и генерацию ограничений. Они сообщают, что генерация столбцов масштабируется намного лучше. Их алгоритм был реализован в Альянсе парного донорства почек .

Биро, Манлав и Рицци ^{[ 7 ]} предложить два подхода к решению этой проблемы, даже если ребра имеют веса (в этом случае это называется упаковкой цикла максимального веса ):

Алгоритм аппроксимации, основанный на известных алгоритмах аппроксимации независимого множества максимального веса ;
Точный алгоритм , систематически проверяющий все способы преобразования гиперграфа циклов в граф. Алгоритм работает во времени $O(3^{s})$ , где s — размер множества, содержащего по одной дуге из каждого 3-цикла.

Циклы длины k и цепи неограниченной длины

Альтруистические доноры могут быть использованы для инициирования цепочки обменов, которая не является циклом. В такой цепочке операции не обязательно делать одновременно: можно гарантировать каждому пациенту, что он получит почку раньше, чем его донор отдаст почку. Если донор отказывается от почки, это разрывает цепь, но это не причиняет вреда пациентам, которым донор уже отдал почку, а значит, не нарушает индивидуальную рациональность.

Андерсон, Ашлаги, Гамарник и Рот ^{[ 8 ]} представим два алгоритма нахождения упаковки максимальной мощности в циклы длины не более k и цепи неограниченной длины:

Один основан на целочисленном линейном программировании и генерации ограничений;
Другой основан на решении задачи коммивояжера .

Неопределенные трансплантаты

Ранние теоретические работы в OKE предполагали, что после определения набора обменов все они будут выполнены. Однако на практике трансплантация может быть отменена. Например, медицинское обследование, проведенное непосредственно перед трансплантацией, может выявить несовместимость донора с пациентом, хотя в базе данных они зарегистрированы как совместимые. Поэтому новые работы направлены на максимизацию ожидаемого количества трансплантаций. Например, Альвелос, Климентова и Виана. ^{[ 9 ]} представить алгоритм ветвей и цен для этой задачи.

Дальнейшие ссылки

Модели целочисленного программирования для обмена почек. ^{[ 10 ]}

Ссылки

^ Ашлаги, Итай; Рот, Элвин Э. (01 сентября 2021 г.). «Обмен почек: операционная перспектива» . Наука управления . 67 (9): 5455–5478. дои : 10.1287/mnsc.2020.3954 . ISSN 0025-1909 .
^ Мэнлав, Дэвид Ф.; О'Мэлли, Грегг (7 января 2015 г.). «Парное и альтруистическое донорство почек в Великобритании: алгоритмы и эксперименты» . Журнал экспериментальной алгоритмики ACM . 19 : 2,6:1–2,6:21. дои : 10.1145/2670129 . ISSN 1084-6654 . S2CID 8744186 .
^ Зениос, Стефанос А.; Чертоу, Гленн М.; Вейн, Лоуренс М. (1 августа 2000 г.). «Динамическое распределение почек среди кандидатов в списке ожидания трансплантации» . Исследование операций . 48 (4): 549–569. дои : 10.1287/opre.48.4.549.12418 . ISSN 0030-364X .
^ Рот, А.Е.; Сонмез, Т.; Унвер, МЮ (01 мая 2004 г.). «Обмен почек» . Ежеквартальный экономический журнал . 119 (2): 457–488. дои : 10.1162/0033553041382157 . ISSN 0033-5533 .
^ Перейти обратно: ^а ^б ^с Авраам, Дэвид Дж.; Блюм, Аврим; Сандхольм, Туомас (11 июня 2007 г.). «Алгоритмы клиринга на бартерных биржевых рынках» . Материалы 8-й конференции ACM по электронной коммерции . ЕС '07. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 295–304. дои : 10.1145/1250910.1250954 . ISBN 978-1-59593-653-0 . S2CID 8909161 .
^ Перейти обратно: ^а ^б ^с Рот, Элвин Э.; Сёнмез, Тайфун; Утку Юнвер, М. (1 декабря 2005 г.). «Парный обмен почек» (PDF) . Журнал экономической теории . 125 (2): 151–188. дои : 10.1016/j.jet.2005.04.004 . ISSN 0022-0531 . S2CID 583399 .
^ Биро, Петер; Мэнлав, Дэвид Ф.; Рицци, Ромео (01 декабря 2009 г.). «Упаковка цикла максимального веса в ориентированных графиках с применением к программам обмена почек» . Дискретная математика, алгоритмы и приложения . 01 (4): 499–517. дои : 10.1142/S1793830909000373 . ISSN 1793-8309 . S2CID 11337530 .
^ Андерсон, Росс; Ашлаги, Итай; Гамарник, Дэвид; Рот, Элвин Э. (20 января 2015 г.). «Нахождение длинных цепочек при обмене почек с помощью задачи коммивояжера» . Труды Национальной академии наук . 112 (3): 663–668. Бибкод : 2015PNAS..112..663A . дои : 10.1073/pnas.1421853112 . ISSN 0027-8424 . ПМК 4311855 . ПМИД 25561535 .
^ Альвелос, Филипе; Климентова, Ксения; Виана, Ана (01 января 2019 г.). «Максимизация ожидаемого количества трансплантаций в программах обмена почками с учетом соотношения филиалов и цен» . Анналы исследования операций . 272 (1): 429–444. дои : 10.1007/s10479-017-2647-4 . ISSN 1572-9338 . S2CID 254235768 .
^ Константино, Мигель; Климентова, Ксения; Виана, Ана; Раис, Абдур (16 ноября 2013 г.). «Новый взгляд на модели целочисленного программирования для проблемы обмена почек». Европейский журнал операционных исследований . 231 (1): 57–68. дои : 10.1016/j.ejor.2013.05.025 . hdl : 10400.22/3315 . ISSN 0377-2217 .

[1] Ашлаги, Итай; Рот, Элвин Э. (01 сентября 2021 г.). «Обмен почек: операционная перспектива» . Наука управления . 67 (9): 5455–5478. дои : 10.1287/mnsc.2020.3954 . ISSN 0025-1909 .

[2] Мэнлав, Дэвид Ф.; О'Мэлли, Грегг (7 января 2015 г.). «Парное и альтруистическое донорство почек в Великобритании: алгоритмы и эксперименты» . Журнал экспериментальной алгоритмики ACM . 19 : 2,6:1–2,6:21. дои : 10.1145/2670129 . ISSN 1084-6654 . S2CID 8744186 .

[3] Зениос, Стефанос А.; Чертоу, Гленн М.; Вейн, Лоуренс М. (1 августа 2000 г.). «Динамическое распределение почек среди кандидатов в списке ожидания трансплантации» . Исследование операций . 48 (4): 549–569. дои : 10.1287/opre.48.4.549.12418 . ISSN 0030-364X .

[4] Рот, А.Е.; Сонмез, Т.; Унвер, МЮ (01 мая 2004 г.). «Обмен почек» . Ежеквартальный экономический журнал . 119 (2): 457–488. дои : 10.1162/0033553041382157 . ISSN 0033-5533 .

[:1-5] Перейти обратно: ^а ^б ^с Авраам, Дэвид Дж.; Блюм, Аврим; Сандхольм, Туомас (11 июня 2007 г.). «Алгоритмы клиринга на бартерных биржевых рынках» . Материалы 8-й конференции ACM по электронной коммерции . ЕС '07. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 295–304. дои : 10.1145/1250910.1250954 . ISBN 978-1-59593-653-0 . S2CID 8909161 .

[:0-6] Перейти обратно: ^а ^б ^с Рот, Элвин Э.; Сёнмез, Тайфун; Утку Юнвер, М. (1 декабря 2005 г.). «Парный обмен почек» (PDF) . Журнал экономической теории . 125 (2): 151–188. дои : 10.1016/j.jet.2005.04.004 . ISSN 0022-0531 . S2CID 583399 .

[7] Биро, Петер; Мэнлав, Дэвид Ф.; Рицци, Ромео (01 декабря 2009 г.). «Упаковка цикла максимального веса в ориентированных графиках с применением к программам обмена почек» . Дискретная математика, алгоритмы и приложения . 01 (4): 499–517. дои : 10.1142/S1793830909000373 . ISSN 1793-8309 . S2CID 11337530 .

[8] Андерсон, Росс; Ашлаги, Итай; Гамарник, Дэвид; Рот, Элвин Э. (20 января 2015 г.). «Нахождение длинных цепочек при обмене почек с помощью задачи коммивояжера» . Труды Национальной академии наук . 112 (3): 663–668. Бибкод : 2015PNAS..112..663A . дои : 10.1073/pnas.1421853112 . ISSN 0027-8424 . ПМК 4311855 . ПМИД 25561535 .

[9] Альвелос, Филипе; Климентова, Ксения; Виана, Ана (01 января 2019 г.). «Максимизация ожидаемого количества трансплантаций в программах обмена почками с учетом соотношения филиалов и цен» . Анналы исследования операций . 272 (1): 429–444. дои : 10.1007/s10479-017-2647-4 . ISSN 1572-9338 . S2CID 254235768 .

[10] Константино, Мигель; Климентова, Ксения; Виана, Ана; Раис, Абдур (16 ноября 2013 г.). «Новый взгляд на модели целочисленного программирования для проблемы обмена почек». Европейский журнал операционных исследований . 231 (1): 57–68. дои : 10.1016/j.ejor.2013.05.025 . hdl : 10400.22/3315 . ISSN 0377-2217 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]