Dual-Donor Organ Exchange problem

Dual-Donor_Organ_Exchange.ipynb Open In Colab Kaggle Gradient Open In SageMaker Studio Lab Hits

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 <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];    

### REQUAREMENTS
	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
	# omit columns that are all zeros
	option omit_zero_cols 1;
	
### 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