Оптимальный обмен почками (OKE) — это проблема оптимизации, с которой сталкиваются программы парного донорства почек (также называемые программами обмена почками). Такие программы имеют большие базы данных пар пациент-донор, где донор готов пожертвовать почку, чтобы помочь пациенту, но не может сделать этого из-за медицинской несовместимости. Центры пытаются организовать обмены между такими парами. Например, донор в паре A жертвует пациенту в паре B, донор в паре B жертвует пациенту в паре C, а донор в паре C жертвует пациенту в паре A.
Целью задачи OKE является поиск оптимального расположения таких обменов. «Оптимальный» обычно означает, что число трансплантатов максимально, но могут быть и другие цели. Решающим ограничением в этой задаче оптимизации является то, что донор отдает почку только в том случае, если его пациент получает совместимую почку, так что ни одна пара не теряет почку из-за участия. Это требование иногда называют индивидуальной рациональностью .
Задача OKE имеет много вариантов, которые различаются допустимым размером каждого обмена, целевой функцией и другими факторами. [1]
Экземпляр OKE обычно описывается как направленный граф . Каждый узел представляет пару пациент-донор. Направленная дуга от пары A к паре B означает, что донор в паре A совместим с пациентом в паре B с медицинской точки зрения (совместимость определяется на основе групп крови донора и пациента, а также других факторов, таких как конкретные антигены в их крови). Направленный цикл в графе совместимости представляет собой возможный обмен. Направленный цикл размера 2 (например, A -> B -> A) представляет собой возможный попарный обмен — обмен между парой пар.
Более общий вариант OKE рассматривает также узлы второго типа, которые представляют собой альтруистических доноров — доноров, которые не парны с пациентом и готовы пожертвовать почку любому совместимому пациенту. Узлы альтруистических доноров имеют только исходящие дуги. С альтруистическими донорами можно организовывать обмены не только циклами, но и цепочками , начиная с альтруистического донора.
Дуги в графике могут иметь вес, представляющий, например, вероятность успеха вовлеченных трансплантаций. Они также могут иметь приоритеты, определяемые, например, медицинской срочностью или временем ожидания пациента в очереди на трансплантацию.
Выход OKE — это набор попарно-непересекающихся направленных циклов (и, возможно, направленных цепей, если доступны альтруистические доноры). Самая простая цель в OKE — максимизировать количество пациентов, которые получат почку. Другие общие цели:
Первоначально проблема изучалась без каких-либо ограничений на длину циклов обмена. Рот, Сонмез и Унвер [4] представили механизм, основанный на расширении механизма верхних торговых циклов , для нахождения циклов обмена оптимальным по Парето и совместимым со стимулами способом.
Абрахам, Блюм и Сандхолм [5] показывают, что при неограниченной длине цикла обмен максимальной мощностью и максимальным весом может быть найден за полиномиальное время. Например, чтобы найти обмен максимальной мощностью, учитывая исходный ориентированный граф G , постройте неориентированный двудольный граф H( X + Y , E ), в котором:
Каждый обмен максимальной мощности в G соответствует сопоставлению максимального веса в H. Обратите внимание, что веса гарантируют, что каждое сопоставление максимального веса в H является идеальным, так что каждый пациент сопоставлен либо с совместимым донором, либо со своим собственным донором. Таким образом, ни один донор не отдает почку, если его пациент не получает почку, что удовлетворяет требованию индивидуальной рациональности.
Этот алгоритм легко расширить до обменов с максимальным весом и включить альтруистичных доноров.
В ходе обсуждений по внедрению программы обмена почками в Новой Англии в 2004 году было установлено, что с точки зрения логистики возможны только парные обмены. Это связано с тем, что все операции в обмене должны выполняться одновременно. Это требование направлено на обеспечение ограничения индивидуальной рациональности — чтобы избежать риска того, что донор откажется от донорства после того, как его пациент получит почку. Цикл обмена размером k требует 2 k одновременных операций. В то время было непрактично организовывать более 4 одновременных операций, поэтому размер циклов был ограничен 2. [6]
В этом случае можно свести направленный граф совместимости к неориентированному графу, где пары A и B связаны тогда и только тогда, когда A->B и B->A. Нахождение попарного обмена с максимальной мощностью эквивалентно нахождению соответствия с максимальной мощностью в этом неориентированном графе. Более того, когда разрешены только попарные обмены, соответствие является Парето-эффективным тогда и только тогда, когда оно имеет максимальную мощность. [6] : Лем.1 Следовательно, такой обмен может быть найден за полиномиальное время.
Рот, Сонмез и Унвер [6] изучают два расширения простого обмена максимальной мощностью:
В последующие годы логистические усовершенствования позволили выполнять большее количество одновременных операций. Соответственно, стали возможны циклы обмена, включающие три или более пар. Нахождение обмена с максимальной мощностью называется в терминах теории графов максимальной упаковкой циклов . Максимальная упаковка циклов с циклами длины не более k для любого фиксированного k ≥ 3 является NP-трудной вычислительной задачей [5] (это можно доказать путем сведения из задачи трехмерного сопоставления в гиперграфе).
Абрахам, Блюм и Сандхолм [5] представляют два метода для максимальной упаковки цикла: генерация столбцов и генерация ограничений. Они сообщают, что генерация столбцов масштабируется гораздо лучше. Их алгоритм был реализован в Альянсе за парные донорства почек.
Биро, Мэнлав и Рицци [7] предлагают два подхода к решению этой проблемы, даже когда ребра имеют вес (в этом случае это называется упаковкой циклов максимального веса ):
Альтруистические доноры могут быть использованы для инициирования цепочки обменов, которая не является циклом. В такой цепочке операции не обязательно должны проводиться одновременно: можно гарантировать каждому пациенту, что он получит почку до того, как ее отдаст его донор. Если донор дает сбой, это нарушает цепочку, но не наносит вреда пациентам, чей донор уже отдал почку, поэтому это не нарушает индивидуальную рациональность.
Андерсон, Ашлаги, Гамарник и Рот [8] представляют два алгоритма для нахождения упаковки максимальной мощности в циклы длины не более k и цепи неограниченной длины:
Ранние теоретические работы в OKE предполагали, что как только набор обменов определен, все они будут выполнены. Однако на практике трансплантации могут быть отменены. Например, медицинское обследование, проведенное непосредственно перед трансплантацией, может выявить, что донор несовместим с пациентом, даже если в базе данных они зарегистрированы как совместимые. Поэтому более новые работы направлены на максимизацию ожидаемого количества трансплантаций. Например, Альвелос, Климентова и Виана [9] представляют алгоритм ветвей и цен для этой задачи.
