authors/mikhail/Medicine/Dual-Donor_Organ_Exchange.ipynb

{
  "cells": [
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {
        "id": "7RjB1ipC7KbS"
      },
      "source": [
        "# Dual-Donor Organ Exchange problem\n",
        "[![Dual-Donor_Organ_Exchange.ipynb](https://img.shields.io/badge/github-%23121011.svg?logo=github)](https://github.com/ampl/colab.ampl.com/blob/master/authors/mikhail/Medicine/Dual-Donor_Organ_Exchange.ipynb) [![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/ampl/colab.ampl.com/blob/master/authors/mikhail/Medicine/Dual-Donor_Organ_Exchange.ipynb) [![Kaggle](https://kaggle.com/static/images/open-in-kaggle.svg)](https://kaggle.com/kernels/welcome?src=https://github.com/ampl/colab.ampl.com/blob/master/authors/mikhail/Medicine/Dual-Donor_Organ_Exchange.ipynb) [![Gradient](https://assets.paperspace.io/img/gradient-badge.svg)](https://console.paperspace.com/github/ampl/colab.ampl.com/blob/master/authors/mikhail/Medicine/Dual-Donor_Organ_Exchange.ipynb) [![Open In SageMaker Studio Lab](https://studiolab.sagemaker.aws/studiolab.svg)](https://studiolab.sagemaker.aws/import/github/ampl/colab.ampl.com/blob/master/authors/mikhail/Medicine/Dual-Donor_Organ_Exchange.ipynb) [![Hits](https://h.ampl.com/https://github.com/ampl/colab.ampl.com/blob/master/authors/mikhail/Medicine/Dual-Donor_Organ_Exchange.ipynb)](https://colab.ampl.com)\n",
        "\n",
        "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.\n",
        "One way to overcome this potential barrier to transplantation is by an exchange of donors between patients. \n",
        "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.\n",
        "\n",
        "Learn more about this issue: https://eml.berkeley.edu/~hie/research/dual-donor-organ-exchange.pdf\n",
        "\n",
        "[*Partner with the AMPL team to transform complex problems into optimized solutions. AMPL consulting services combine deep technical knowledge with industry-leading insights, helping you unlock the full potential of optimization within your organization.*](https://ampl.com/services/)\n",
        "\n",
        "Tags: Medicine, Organ Exchange, MIP, ampl-only\n",
        "\n",
        "Model author: Mikhail Riabtsev\n",
        "\n",
        "Notebook author: Mikhail Riabtsev <<mail@solverytic.com>>\n",
        "\n",
        "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"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "rQ50dBwL7KbX"
      },
      "outputs": [],
      "source": [
        "# Install dependencies\n",
        "%pip install -q amplpy"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "s7DEaRp87KbY",
        "outputId": "6ece6d53-a3db-443c-c623-5cc409115fdf"
      },
      "outputs": [],
      "source": [
        "# Google Colab & Kaggle integration\n",
        "from amplpy import AMPL, ampl_notebook\n",
        "\n",
        "ampl = ampl_notebook(\n",
        "    modules=[\"highs\"],  # modules to install\n",
        "    license_uuid=\"default\",  # license to use\n",
        ")  # instantiate AMPL object and register magics"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {
        "id": "twrd0pLo7KbZ"
      },
      "source": [
        "## Problem formulation in AMPL"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "aEtyesqs7KbZ"
      },
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "# Donor Exchange\n",
        "reset;\n",
        "### SETS \n",
        "  param N;\n",
        "  set Blood;                             # set of blood types (b)\n",
        "  set PATIENTS := {1..N} ordered;        # set of patients (i)\n",
        "  set DONORS;                            # set of donors (j)\n",
        "  set ALL:= PATIENTS union DONORS;       # set of patients union donors (ij)\n",
        "  set Transpl;                           # type of transplant {tr}\n",
        "  set BLOOD within {Blood, Blood};       # possible transplant options by blood type compatibility\n",
        "  set PAT_DON within {PATIENTS, DONORS}; # donor-patient relationship\n",
        "  set TRANSPL_HUM within {ALL,Transpl};  # type of transplant assigned to a PATIENTS and DONORS\n",
        "  set BLOOD_HUM within {ALL, Blood};     # PATIENTS and DONORS blood type\n",
        "\n",
        "  # patients data:  patient(i),type of transplant(tr), blood type(b) \n",
        "    set PATIENTS_:= setof {(i,tr) in TRANSPL_HUM, (i,b) in BLOOD_HUM: i in PATIENTS} (i,tr,b);\n",
        "\n",
        "  # donors data: relationship between patient(i) & donor(j), possible type of transplant(tr), blood type(b) \t\n",
        "    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);\n",
        "\n",
        "  ### a set of options for possible assignments: \n",
        "  # 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) \n",
        "    set LINKS_:= setof {(ii,tr,b1) in PATIENTS_, (i,j,tr,b2) in DONORS_:(b1,b2) in BLOOD}(i,j,ii,tr,b1);\n",
        "\n",
        "  ### a set of options for possible assignments:\n",
        "  # 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) \n",
        "    set LINKS:= setof {(ii,tr,b1) in PATIENTS_, (i,j,tr,b2) in DONORS_:(b1,b2) in BLOOD}(i,j,ii,tr,b1,b2);\n",
        "\n",
        "  ### a set of options for possible assignments TWO donors for ONE patient:\n",
        "  # 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)\n",
        "    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);\t\t\t\t\t\t\t\t\t\n",
        "\t### 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. ###\n",
        "\n",
        "### PARAMETERS\n",
        "  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.\n",
        "  param demand {(i,tr,b) in PATIENTS_} >= 0;   # required number of surgeries for a patient\n",
        "\n",
        "### VARIABLES\n",
        " 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.\n",
        " var Y {LINKS_, 1..Clusters} binary;           # assignment of donors and transplant patients\n",
        "\n",
        "### OBJECTIVE\n",
        "  # Maximize the number of transplants\n",
        "  maximize Total: sum {i in PATIENTS, c in 1..Clusters} X [i,c];    \n",
        "\n",
        "### REQUIREMENTS\n",
        "subject to\n",
        " # for each cluster, supply - demand >= 0;\n",
        "  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 =\n",
        "\n",
        " # a patient can only be part of one cluster\n",
        "  A_1 {i in PATIENTS}: sum {c in 1..Clusters} X[i,c] <= 1;\n",
        "\n",
        " # for each type of operation of the patient in all clusters, only one donor is assigned.\n",
        "  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;\n",
        "\n",
        " # Limiting the number of patients in 1 cluster.\n",
        "  A_3 {c in 1..Clusters}: sum {i in PATIENTS} X[i,c] <= 3; \n",
        "\n",
        " # A donor can participate in an organ transplant operation only 1 time \n",
        "  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;\n",
        "    \n",
        " # 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)\n",
        "  A_5 {c in 1..Clusters}: sum{(i,j,ii,tr,b) in LINKS_} Y[i,j,ii,tr,b,c]*2 <= 6;\n"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {
        "id": "jCyp8qRS7Kba"
      },
      "source": [
        "## Data of model"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "jYDiBDD_7Kba"
      },
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "### DATA\n",
        "data;\n",
        "  param N:=5;                               # number of patients\n",
        "\n",
        "  set Blood := O, A, B, AB;                 # types of blood\n",
        "\n",
        "  set DONORS := d01 d02 d03 d04 d05 d06 d07 d08 d09 d10 ;# number of donors\n",
        "\n",
        "  set Transpl := Liver, Kidney, Lung;       # Type of transplants\n",
        "\n",
        "  set BLOOD: O   A   B  AB :=               # Data on compatibility of blood types\n",
        "\tO        +   -   -  -\n",
        "\tA        +   +   -  -\n",
        "\tB        +   -   +  -\n",
        "\tAB       +   +   +  + ;\n",
        "\n",
        "  set PAT_DON(tr):                          # Donor affiliation with patients\n",
        "\t\t1   2   3   4   5 :=\n",
        "\td01 -   +   -   -   -\n",
        "\td02 -   +   -   -   -   \n",
        "\td03 +   -   -   -   -\n",
        "\td04 +   -   -   -   -\n",
        "\td05 -   -   +   -   -\n",
        "\td06 -   -   -   -   +\n",
        "\td07 -   -   -   +   -\n",
        "\td08 -   -   -   -   +\n",
        "\td09 -   -   +   -   -\n",
        "\td10 +   -   -   -   -  ;\n",
        "\n",
        "  set TRANSPL_HUM: Liver  Kidney  Lung:=\n",
        "\td01              +      -       +       # This table assumes that each patient is operated \n",
        "\td02              -      -       +       # on in one approach, i.e. all the necessary \n",
        "\td03              +      -       -       # operations are performed at 1 time.\n",
        "\td04              +      -       +      \n",
        "\td05              -      +       -      \n",
        "\td06              +      -       -      \n",
        "\td07              +      +       +      \n",
        "\td08              -      +       -      \n",
        "\td09              +      -       -      \n",
        "\td10              +      -       +      \n",
        "\t1                -      -       +      \n",
        "\t2                +      +       +      \n",
        "\t3                +      -       -      \n",
        "\t4                +      +       -      \n",
        "\t5                +      -       -     ; # This condition means and. You could change to or.\n",
        "  \n",
        "  set BLOOD_HUM:   O   A   B   AB:=         # PATIENTS and DONORS blood type\n",
        "\td01            +   -   -   -    \n",
        "\td02            -   +   -   -      \n",
        "\td03            -   -   +   -      \n",
        "\td04            -   +   -   -      \n",
        "\td05            -   -   -   +      \n",
        "\td06            -   -   -   +      \n",
        "\td07            -   +   -   -      \n",
        "\td08            +   -   -   -     \n",
        "\td09            +   -   -   -      \n",
        "\td10            -   -   -   +      \n",
        "\t1              +   -   -   -    \n",
        "\t2              -   +   -   -      \n",
        "\t3              -   -   -   +     \n",
        "\t4              -   +   -   -      \n",
        "\t5              +   -   -   -     ; \n",
        "\n",
        "param demand default 1                     # required number of surgeries for a patient"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {
        "id": "uftSUdTh9eZY"
      },
      "source": [
        "## Solve the problem"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "\n",
        "### OPTIONS OF AMPL\n",
        " option omit_zero_cols 1;  # omit columns that are all zeros\n",
        " \n",
        "### The choice of solver \n",
        " option solver highs;\n",
        "\n",
        "### SOLVE \n",
        " solve;"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Show Results"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "j6pPuSOi8nPH",
        "outputId": "0f6ad246-3351-4187-b373-216ec7b36c98"
      },
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "\n",
        "### RESULTS\t\n",
        " display BLOOD,            # possible transplant options by blood type compatibility\n",
        " 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)\n",
        " X,                        # assigning a patient to an organ(s) transplant cluster\n",
        " Y;                        # assignment of donors and transplant patients"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3 (ipykernel)",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.10.12"
    },
    "vscode": {
      "interpreter": {
        "hash": "ee4198aac13dae9b6fccd443041680d99c2643c4956ef7c80ff6dcc0057cb523"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}