Intercambio renal óptimo

El intercambio óptimo de riñón (OKE, por sus siglas en inglés) es un problema de optimización al que se enfrentan los programas de donación de riñón en pares (también llamados Programas de Intercambio de Riñón). Dichos programas cuentan con grandes bases de datos de pares de pacientes y donantes, en los que el donante está dispuesto a donar un riñón para ayudar al paciente, pero no puede hacerlo debido a una incompatibilidad médica. Los centros intentan organizar intercambios entre dichos pares. Por ejemplo, el donante del par A dona al paciente del par B, el donante del par B dona al paciente del par C y el donante del par C dona al paciente del par A.

El objetivo del problema OKE es encontrar una disposición óptima de dichos intercambios. "Óptimo" suele significar que el número de trasplantes sea el mayor posible, pero puede haber otros objetivos. Una restricción crucial en este problema de optimización es que un donante dona un riñón solo si su paciente recibe un riñón compatible, de modo que ninguna pareja pierda un riñón por participar. Este requisito a veces se denomina racionalidad individual .

El problema OKE tiene muchas variantes, que difieren en el tamaño permitido de cada intercambio, la función objetivo y otros factores. ^[1]

Una instancia de OKE se describe generalmente como un gráfico dirigido . Cada nodo representa un par de pacientes y donantes. Un arco dirigido del par A al par B significa que el donante del par A es médicamente compatible con el paciente del par B (la compatibilidad se determina en función de los tipos de sangre del donante y del paciente, así como de otros factores, como antígenos particulares en su sangre). Un ciclo dirigido en el gráfico de compatibilidad representa un posible intercambio. Un ciclo dirigido de tamaño 2 (por ejemplo, A -> B -> A) representa un posible intercambio por pares , es decir, un intercambio entre un par de pares.

Una variante más general de OKE también considera nodos de un segundo tipo, que representan donantes altruistas , es decir, donantes que no están emparejados con ningún paciente y que están dispuestos a donar un riñón a cualquier paciente compatible. Los nodos de donantes altruistas solo tienen arcos salientes. Con los donantes altruistas, es posible organizar intercambios no solo con ciclos sino también con cadenas , comenzando con un donante altruista.

Los arcos del gráfico pueden tener pesos que representan, por ejemplo, la probabilidad de éxito de los trasplantes en cuestión. También pueden tener prioridades, determinadas, por ejemplo, por la urgencia médica o por el tiempo que el paciente ha esperado en la cola de trasplantes.

El resultado de un OKE es un conjunto de ciclos dirigidos disjuntos por pares (y posiblemente cadenas dirigidas, si hay donantes altruistas disponibles). El objetivo más simple en un OKE es maximizar la cantidad de pacientes que reciben un riñón. Otros objetivos comunes son:

• Maximizar la suma ponderada de los intercambios de riñones: ^[2] Cada borde del gráfico tiene un peso y el objetivo es encontrar un intercambio que maximice la suma de pesos en todos los bordes utilizados en el intercambio.
• Maximizar la expectativa de vida de los candidatos a trasplante, o su expectativa de vida ajustada por calidad . ^[3]

Inicialmente, el problema se estudió sin ningún límite en la duración de los ciclos de intercambio. Roth, Sonmez y Unver ^[4] presentaron un mecanismo, basado en una extensión del mecanismo de los ciclos comerciales superiores , para encontrar ciclos de intercambio de una manera Pareto-óptima y compatible con los incentivos .

Abraham, Blum y Sandholm ^[5] demuestran que, con una longitud de ciclo ilimitada, se puede encontrar un intercambio de máxima cardinalidad y máximo peso en tiempo polinomial. Por ejemplo, para encontrar un intercambio de máxima cardinalidad, dado el grafo dirigido original G , construya un grafo bipartito no dirigido H( X + Y , E ) en el que:

• Cada par j en G tiene dos nodos: x _j (que representa al donante) e y _j (que representa al paciente). Están conectados por una arista de peso 1.
• Para cada arista i -> j en G , agregue en H una arista x _i -- y _j de peso 1+1/n.
• Encuentra una correspondencia de peso máximo en H.

Cada intercambio de máxima cardinalidad en G corresponde a una correspondencia de máximo peso en H. Nótese que los pesos garantizan que cada correspondencia de máximo peso en H sea perfecta, de modo que cada paciente sea compatible, ya sea con un donante compatible o con su propio donante. Por lo tanto, ningún donante dona un riñón a menos que su paciente reciba un riñón, lo que satisface el requisito de racionalidad individual.

Es fácil extender este algoritmo a intercambios de peso máximo e incorporar donantes altruistas.

En las discusiones para implementar un programa de intercambio de riñones en Nueva Inglaterra en 2004, se descubrió que, logísticamente, solo son posibles los intercambios por pares. Esto se debe a que todas las operaciones en un intercambio deben realizarse simultáneamente. Este requisito tiene como objetivo garantizar la restricción de racionalidad individual : evitar el riesgo de que un donante se niegue a donar después de que su paciente haya recibido un riñón. Un ciclo de intercambio de tamaño k requiere 2 k operaciones simultáneas. En ese momento, no era práctico organizar más de 4 operaciones simultáneas, por lo que el tamaño de los ciclos se limitó a 2. ^[6]

En este contexto, es posible reducir el grafo de compatibilidad dirigido a un grafo no dirigido, donde los pares A y B están conectados si y solo si A->B y B->A. Encontrar un intercambio por pares de cardinalidad máxima es equivalente a encontrar una coincidencia de cardinalidad máxima en ese grafo no dirigido. Además, cuando solo se permiten intercambios por pares, una coincidencia es Pareto-eficiente si y solo si tiene cardinalidad máxima. ^{[6] : Lem.1} Por lo tanto, dicho intercambio se puede encontrar en tiempo polinomial.

Roth, Sonmez y Unver ^[6] estudian dos extensiones del simple intercambio de máxima cardinalidad:

• Dado un orden de prioridad sobre los pacientes o los trasplantes, es posible encontrar en tiempo polinomial una coincidencia prioritaria , es decir, una coincidencia que, entre todas las coincidencias de máxima cardinalidad, maximice el número de pacientes con mayor prioridad. Además, estos algoritmos pueden hacerse compatibles con los incentivos en el sentido de que cada paciente maximiza su posibilidad de ser compatible al traer al sistema tantos donantes como sea posible y al aceptar tantos riñones como sea posible. Las pruebas utilizan conceptos de la teoría de grafos, como la descomposición de Gallai-Edmonds .
• Es posible encontrar un intercambio estocástico , en el que se selecciona una pareja al azar entre todas las parejas de máxima cardinalidad. El mecanismo igualitario tiene como objetivo maximizar la menor probabilidad de que un paciente reciba un riñón. El mecanismo igualitario es compatible con los incentivos en el mismo sentido que el mecanismo de prioridad.

En años posteriores, las mejoras logísticas permitieron la ejecución de un mayor número de operaciones simultáneas. En consecuencia, se hicieron posibles los ciclos de intercambio que involucraban tres o más pares. Encontrar un intercambio de máxima cardinalidad se denomina, en términos de teoría de grafos, empaquetamiento de ciclo máximo . El empaquetamiento de ciclo máximo con ciclos de longitud como máximo k , para cualquier k fijo ≥ 3 , es un problema computacional NP-hard ^[5] (esto se puede demostrar por reducción a partir del problema de emparejamiento tridimensional en un hipergrafo).

Abraham, Blum y Sandholm ^[5] presentan dos técnicas para el empaquetamiento máximo de ciclos: generación de columnas y generación de restricciones. Informan que la generación de columnas escala mucho mejor. Su algoritmo se ha implementado en la Alianza para Donaciones Renales en Par.

Biro, Manlove y Rizzi ^[7] sugieren dos enfoques para resolver este problema incluso cuando los bordes tienen pesos (en cuyo caso se denomina empaquetamiento cíclico de peso máximo ):

• Un algoritmo de aproximación basado en algoritmos de aproximación conocidos para conjuntos independientes de peso máximo ;
• Un algoritmo exacto que comprueba sistemáticamente todas las formas de convertir el hipergrafo de ciclos en un grafo. El algoritmo se ejecuta en tiempo , donde s es el tamaño de un conjunto que contiene un arco de cada 3 ciclos.${\displaystyle O(3^{s})}$

Los donantes altruistas pueden utilizarse para iniciar una cadena de intercambios, que no es un ciclo. En una cadena de este tipo, las operaciones no tienen por qué realizarse simultáneamente: es posible garantizar a cada paciente que recibirá un riñón antes de que su donante lo haga. Si un donante se expulsa, se rompe la cadena, pero no se perjudica a los pacientes cuyo donante ya ha donado un riñón, por lo que no se rompe la racionalidad individual.

Anderson, Ashlagi, Gamarnik y Roth ^[8] presentan dos algoritmos para encontrar un empaquetamiento de cardinalidad máxima en ciclos de longitud como máximo k y cadenas de longitud ilimitada:

• Uno se basa en programación lineal entera y generación de restricciones;
• La otra se basa en una solución al problema del viajante de comercio .

Los primeros trabajos teóricos en OKE asumían que, una vez determinado un conjunto de intercambios, todos ellos se ejecutarían. Sin embargo, en la práctica, los trasplantes podrían cancelarse. Por ejemplo, el examen médico realizado justo antes del trasplante podría revelar que el donante es incompatible con el paciente, aunque en la base de datos estén registrados como compatibles. Por lo tanto, los trabajos más recientes apuntan a maximizar el número esperado de trasplantes. Por ejemplo, Alvelos, Klimentova y Viana ^[9] presentan un algoritmo de rama y precio para este problema.

• Modelos de programación entera para el intercambio de riñones. ^[10]