Kidney Exchange

with integer programming and Gurobi

In this example we'll solve the Kidney Exchange Problem: how to exchange kidneys between donors and patients in need of a transplant.

We'll construct a mathematical model of the problem, implement this model in Gurobi's Python interface, and compute and visualize an optimal solution.

Click the screenshot to skip directly to the Live Demo!

Live Demo

Problem Description

According to the New York Times, in the United States there are more than 100,000 people, on the transplant list, waiting for a kidney. Patients typically wait four to five years before a transplant. In 2014, more than 4,000 people died while waiting on the transplant list.

New software and algorithms, many of them based on integer programming, have recently been developed to better match patients with donors. In this example, we will see how an integer programming model based on exchanging kidneys can help more transplants happen.

Often a patient in need of a transplant has a friend or family member who is willing to donate their kidney. However, because of differences in blood types and proteins in the blood, the potential donor may be incompatiable with the patient. Thus a transplant cannot be made, or if the transplant were to occur, the recipient would have a high chance of rejecting the donor's kidney.

In this example we consider four types of patients (donors and recipients) categorized by blood type and proteins. Each patient type is represented by a color: blue, orange, green, or red. The different compatibility factors between the different types are shown in the table below:

R R R R
D 100% 50% 20% 0%
D 50% 100% 0% 70%
D 20% 0% 100% 60%
D 0% 70% 60% 100%

For example, an orange donor cannot give a kidney to a green recipient, and a blue donor and a green recipient are only 20% compatiable.

The key to conducting a transplant in the presence of these incompatibilites, is doing a pair-exchange, or a kidney swap.

Suppose there are four patients: two potential recipients and two potential donors. Recipient 1 is orange and her potential donor is green, while recipient 2 is green and his potential donor is blue. From the table above, we see that recipient 1 and donor 1 are incompatibale, and recipient 2 and donor 2 are only 20% compatible. However, if recipient 1 were to receive a kidney from donor 2, they would be 50% compatiable. And if recipient 2 were to receive a kidney from donor 1 they would be 100% compatiable.

According to the New York Times, last year in the United States more than 500 kidneys were transplanted through these paired exchange programs.

Furthermore, kidney exchanges need not be between two patient-donor pairs. We could form longer cycles. For example, with donor 1 giving to patient 2, donor 2 giving to patient 3, and donor 3 giving to patient 1. Longer cycles with even more patients are also possible.

However, there are issues with longer cycles. In a longer cycle more people are affected if an exchange fails. In addition, if all transplants are done simultaneously (to avoid donors backing out once their partner has received a kidney), more medical staff and operating rooms are required with longer cycles. Therefore, in this example, we restrict the number of donor/recipient pairs in a cycle to be at most 3.

The kidney exchange problem is then: given a set of donor/recipient pairs with differing compatibility, find a set of cycles, of length at most 3, that maximizes the number of patients receiving a compatiable kidney.

Mathematical Model

Kidney exchange is an example of the more general barter exchange market problem. In this problem, agents seek to swap their items, creating cycles of agents where each agent receives the item from the previous agent in the cycle. The goal is to find a set of cycles which maximize the utility over all agents. In contrast to usual exchanges, in a barter exchange, items are swapped directly without the use of money.

There are several ways to formulate the kidney exchange problem as an integer program. In this example, we will use a cycle cover formulation.

Let $G(V, E)$ be a directed graph with weighted edges. Each vertex in $V$ corresponds to a donor/recipient pair. The directed weighted edges represent the compatiblity factors between donors and recipients. For example, if recipient 1 and donor 2 are perfectly compatible, we give the edge (1,2) a weight of 1. If they are less compatible, and the risk of failure of a transplant is higher, we would give the edge a smaller weight.

Let $C$ be the set of cycles in the graph of length at most 3. Let $w_c$ denote the weight of cycle $c$, which is equal to the sum of all edge weights in the cycle. Our goal is to find a cycle cover of the graph with maximum weight. Therefore, we define a binary variable $x_c$ for each cycle such that \[ x_c = \left\{\begin{array}{ll} 1 & \text{if cycle $c$ is in the cover}\\ 0 & \mathrm{otherwise.} \end{array}\right. \]

The objective we seek to maximize is the total weight of the cover: \[ \text{total cover weight} = \sum_{c \in C} w_c x_c. \]

Now since a recipient needs to receive one kidney and a donor can give at most one kidney, each vertex of the graph can be in at most one cycle. To impose this constraint, we first find all the cycles in which a given vertex $v$ is included. The sum of the binary variables corresponding to these cycles must then at most be one. So we have the following set of constraints (one for each vertex $v$): \[ \sum_{c : v \in c} x_c \leq 1 \quad \forall v \in V. \]

So finally our optimization model becomes \[ \begin{array}{ll} \text{maximize} & {\displaystyle \sum_{c \in C} w_c x_c} \\ \text{subject to} & {\displaystyle \sum_{c : v \in c} x_c} \leq 1, \quad \forall v \in V, \\ & x_c \in \{ 0, 1 \}, \quad \forall c \in C. \end{array} \]

Implementation

Below is the full implementation of the model (and the associated data) in Gurobi's Python interface:

from gurobipy import * vertices = range(5) edges = { (0,1) : 1, (1,0) : 1, (0,2) : 1, (2,0) : 1, (0,4) : 1, (4,0) : 1, (1,4) : 1, (4,1) : 1, (1,3) : 1, (3,1) : 1, (2,3) : 1, (3,2) : 1, (3,4) : 1, (4,3) : 1 } def twoCycle(vertices, edges): ''' Returns a dictionary of 2 cycles. Keys: (u,v), Value: weight of cycle Note that u < v to not double count cycles. ''' twoCycles = {} for edge in edges: u = edge[0] v = edge[1] if (u < v and (v,u) in edges): twoCycles[(u,v)] = edges[(u,v)] + edges[(v,u)] return twoCycles def threeCycle(vertices, edges): ''' Returns a dictionary of 3 cycles. Keys: (u,w,v), Value: weight of cycle Note that w is always the lowest numbered vertex to not double (or triple) count cycles. ''' threeCycles = {} for edge in edges: u = edge[0] v = edge[1] for w in vertices: if (w >= u or w >= v ): break if ( (u,w) in edges and (w,v) in edges ): threeCycles[(u,w,v)] = edges[(u,v)] + edges[(u,w)] + edges[(w,v)] return threeCycles twoCycles = twoCycle(vertices, edges) threeCycles = threeCycle(vertices, edges) m = Model() c = {} for cycle in twoCycles: c[cycle] = m.addVar(vtype=GRB.BINARY, name="c_%s" % str(cycle)) for cycle in threeCycles: c[cycle] = m.addVar(vtype=GRB.BINARY, name="c_%s" % str(cycle)) m.update() for v in vertices: constraint = [] for cycle in c: if (v in cycle): constraint.append(c[cycle]) if constraint: m.addConstr( quicksum( constraint[i] for i in range(len(constraint)) ) <= 1 , name="v%d" % v) m.setObjective( quicksum( c[cycle] * twoCycles[cycle] for cycle in twoCycles ) + quicksum( c[cycle] * threeCycles[cycle] for cycle in threeCycles ), GRB.MAXIMIZE ) m.optimize()

Live Demo

Below is a visualization of our Kidney Exchange example.

You can add different types of donor/recipient pairs by changing the numbers in the table below.

Donor/recipient pairs are represented by nodes DR where the color of the left side of the circle represents the type of the donor and the color of the right side represents the type of the recipient.

To find the optimal kidney exchange using Gurobi, click "Compute". The colors of the edges represent the type of kidney donated.

You can also drag the nodes around to make the visualization clearer.

R R R R
D
D
D
D

Try Gurobi for Free

We hope this example has taught you a bit about kidney exchange and using Gurobi. We encourage you to try the example out for yourself with Gurobi. To enable this, we provide easy access to a full-featured evaluation version of Gurobi.

We are always happy to discuss your needs and answer your questions. Just contact us at your convenience.