Dual-Donor Organ Exchange problem#
Description: Most transplants from living donors require only one donor for each procedure. There are, however, exceptions, including dual-graft liver transplantation, bilateral living-donor lobar lung transplantation, and simultaneous liver-kidney transplantation. For each of these procedures, grafts from two compatible living donors are transplanted. As such, these procedures are more involved from an organizational perspective than those with only one donor. Unfortunately, one or both of the donors can often be biologically incompatible with the intended recipient, precluding the transplantation. One way to overcome this potential barrier to transplantation is by an exchange of donors between patients. The mathematical optimization model presented here identifies and maximizes the number of cross-compatibilities between patients and donors, thereby maximizing the number of possible transplants and their variations within the available set of patients and donors.
Learn more about this issue: https://eml.berkeley.edu/~hie/research/dual-donor-organ-exchange.pdf
Tags: Medicine, Organ Exchange, MIP, ampl-only
Model author: Mikhail Riabtsev
Notebook author: Mikhail Riabtsev <mail@solverytic.com>
References: https://sites.bc.edu/utku-unver/wp-content/uploads/sites/67/2019/11/slides-dual-donor-exchange-2016.pdf | https://eml.berkeley.edu/~hie/research/dual-donor-organ-exchange.pdf
# Install dependencies
%pip install -q amplpy
# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["highs"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
Problem formulation in AMPL#
%%ampl_eval
# Donor Exchange
reset;
### SETS
param N;
set Blood; # set of blood types (b)
set PATIENTS := {1..N} ordered; # set of patients (i)
set DONORS; # set of donors (j)
set ALL:= PATIENTS union DONORS; # set of patients union donors (ij)
set Transpl; # type of transplant {tr}
set BLOOD within {Blood, Blood}; # possible transplant options by blood type compatibility
set PAT_DON within {PATIENTS, DONORS}; # donor-patient relationship
set TRANSPL_HUM within {ALL,Transpl}; # type of transplant assigned to a PATIENTS and DONORS
set BLOOD_HUM within {ALL, Blood}; # PATIENTS and DONORS blood type
# patients data: patient(i),type of transplant(tr), blood type(b)
set PATIENTS_:= setof {(i,tr) in TRANSPL_HUM, (i,b) in BLOOD_HUM: i in PATIENTS} (i,tr,b);
# donors data: relationship between patient(i) & donor(j), possible type of transplant(tr), blood type(b)
set DONORS_:= setof {(j,tr) in TRANSPL_HUM, (j,b) in BLOOD_HUM, (i,j) in PAT_DON:j in DONORS}(i,j,tr,b);
### a set of options for possible assignments:
# donor(j) of the patient(ii) who can be assigned to the patient(i) as it is compatible in type of transplantation(tr) and terms of blood type(b1 and b2)
set LINKS_:= setof {(ii,tr,b1) in PATIENTS_, (i,j,tr,b2) in DONORS_:(b1,b2) in BLOOD}(i,j,ii,tr,b1);
### a set of options for possible assignments:
# donor(j) of the patient(ii) who can be assigned to the patient(i) as it is compatible in type of transplantation(tr) and terms of blood type(b1 and b2)
set LINKS:= setof {(ii,tr,b1) in PATIENTS_, (i,j,tr,b2) in DONORS_:(b1,b2) in BLOOD}(i,j,ii,tr,b1,b2);
### a set of options for possible assignments TWO donors for ONE patient:
# a patient (i) with a blood type (b1) can receive 2 parts of the transplant (tr) from donors (j1 and j2) with a compatible blood type (b2, b3)
set PAT_2DON:= setof {(i,j1,ii,tr,b1,b2) in LINKS, (i,j2,tr,b3) in DONORS_:(b1,b3) in BLOOD and (b2,b3) in BLOOD and j1 != j2} (i,j1,j2,tr,b1,b2,b3);
### To simplify the model, the compatibility of donors and patients is checked only by blood type. If necessary, you can add a check of additional criteria for the compatibility of donors and patients. ###
### PARAMETERS
param Clusters:= last(PATIENTS); # create a transplantation cluster for each patient. The introduction of the cluster guarantees simultaneous operation for the donor and his patient.
param demand {(i,tr,b) in PATIENTS_} >= 0; # required number of surgeries for a patient
### VARIABLES
var X {PATIENTS, 1..Clusters} binary; # assigning a patient to an ceparate organ(s) transplant cluster. Clusters are introduced to ensure simultaneous operation for the donor and his client.
var Y {LINKS_, 1..Clusters} binary; # assignment of donors and transplant patients
### OBJECTIVE
# Maximize the number of transplants
maximize Total: sum {i in PATIENTS, c in 1..Clusters} X [i,c];
### REQUIREMENTS
subject to
# for each cluster, supply - demand >= 0;
A {c in 1..Clusters,tr in Transpl, b in Blood}: sum{(i,j,ii,tr,b) in LINKS_} Y[i,j,ii,tr,b,c] - sum {(i,tr,b) in PATIENTS_} demand[i,tr,b] * X[i,c] >= 0; # you can put =
# a patient can only be part of one cluster
A_1 {i in PATIENTS}: sum {c in 1..Clusters} X[i,c] <= 1;
# for each type of operation of the patient in all clusters, only one donor is assigned.
A_2 {ii in PATIENTS, tr in Transpl}:sum{c in 1..Clusters, (i,j,ii,tr,b) in LINKS_} Y[i,j,ii,tr,b,c] <= 1;
# Limiting the number of patients in 1 cluster.
A_3 {c in 1..Clusters}: sum {i in PATIENTS} X[i,c] <= 3;
# A donor can participate in an organ transplant operation only 1 time
A_4 {j in DONORS, tr in Transpl}: sum{c in 1..Clusters, (i,j,ii,tr,b) in LINKS_} Y[i,j,ii,tr,b,c] <= 1;
# Limiting the number of operations in the cluster (it is assumed that after assigning a donor for transplantation, another operation is performed with the patient)
A_5 {c in 1..Clusters}: sum{(i,j,ii,tr,b) in LINKS_} Y[i,j,ii,tr,b,c]*2 <= 6;
Data of model#
%%ampl_eval
### DATA
data;
param N:=5; # number of patients
set Blood := O, A, B, AB; # types of blood
set DONORS := d01 d02 d03 d04 d05 d06 d07 d08 d09 d10 ;# number of donors
set Transpl := Liver, Kidney, Lung; # Type of transplants
set BLOOD: O A B AB := # Data on compatibility of blood types
O + - - -
A + + - -
B + - + -
AB + + + + ;
set PAT_DON(tr): # Donor affiliation with patients
1 2 3 4 5 :=
d01 - + - - -
d02 - + - - -
d03 + - - - -
d04 + - - - -
d05 - - + - -
d06 - - - - +
d07 - - - + -
d08 - - - - +
d09 - - + - -
d10 + - - - - ;
set TRANSPL_HUM: Liver Kidney Lung:=
d01 + - + # This table assumes that each patient is operated
d02 - - + # on in one approach, i.e. all the necessary
d03 + - - # operations are performed at 1 time.
d04 + - +
d05 - + -
d06 + - -
d07 + + +
d08 - + -
d09 + - -
d10 + - +
1 - - +
2 + + +
3 + - -
4 + + -
5 + - - ; # This condition means and. You could change to or.
set BLOOD_HUM: O A B AB:= # PATIENTS and DONORS blood type
d01 + - - -
d02 - + - -
d03 - - + -
d04 - + - -
d05 - - - +
d06 - - - +
d07 - + - -
d08 + - - -
d09 + - - -
d10 - - - +
1 + - - -
2 - + - -
3 - - - +
4 - + - -
5 + - - - ;
param demand default 1 ; # required number of surgeries for a patient
Solve the problem#
%%ampl_eval
### OPTIONS OF AMPL
option omit_zero_cols 1; # omit columns that are all zeros
### The choice of solver
option solver highs;
### SOLVE
solve;
Show Results#
%%ampl_eval
### RESULTS
display BLOOD, # possible transplant options by blood type compatibility
PAT_2DON, # (i,j1,j2,tr,b1,b2,b3) a list of patient (i) with a blood type (b1) can receive 2 parts of the transplant (tr) from donors (j1 and j2) with a compatible blood type (b2, b3)
X, # assigning a patient to an organ(s) transplant cluster
Y; # assignment of donors and transplant patients