Dataset and results for Robust Kidney Exchange Problem

The dataset contains the instances and results files for the paper M.Carvalho, X. Klimentova, K. Glorie, A. Viana, M. Constantino. Robust Models for the Kidney Exchange Problem. To appear in INFORMS Journal on Computing (2020). There are 7 zip-archives within this dataset: 3 for instances, and 4 for files with results.

I. Instances

The common practice is to model the Kidney Exchange Problem (KEP) on directed graph G = (V,A), called compatibility graph, where set of vertices V corresponds to the set of incompatible pairs and an arc from a vertex i to a vertex j indicates a compatibility of donor in i with the patient in j.

The instances have been created by implementation of the generator, described in Saidman S, Roth A, Sönmez T, Ünver M, Delmonico F. Increasing the opportunity of live kidney donation by matching for two-and three-way exchanges. Transplantation2006;81:773–82.

The generator creates random graphs based on probabilities of blood type and of donor–patient tissue compatibility. As an output, there are two files generated. One provides characteristics of involved pairs, another represents a compatibility matrix. The files apper in the following format.

1. The first one is the characheristics of pairs. Name of those files is formed as n_seed_pairs.txt

2. n = |V| is the number of pairs in the pool (the set of vertices V consist of a set of incompatible pairs, P, and a set of altruistic donor, N, i.e. V = P U N )

3. seed is the seed used for random function when generating the instance.

In the first line the file contains values |P| – number of incompatible pairs, and |N| – number of altruistic donors. The following lines are presented as follows: index Donor ABO Patient ABO Patient PRA

• index is the index of the vertex;

• Donor ABO is the bloodtype of the donor;

• Patient ABO is the bloodtype of the patient;

• Patient PRA is the level of PRA of the patient.

In case the vertex corresponds to the altruistic donor, the last to values are omitted, and represented by ""-"".

1. The second file is the compatibility graph of an instance of a given size. Name of those files is formed as n_seed_compat.txt

In the first line the file contains values n – number of vertices in the graph and m – number of arcs in the graph. In the following m lines of the file, the existing arcs (i,j) are presented as follows: i j

The instances are joint in three zip archives: 20.zip, 50.zip, 100.zip for instances with 20, 50 and 100 vertices, respectively, 30 instances of each size.

II. Results

The results are joined into 4 zip archives: The first three archives (K=3 L=3.zip, K=3 L=4.zip, K=3 L=5.zip) contain the results for respective values of parameters K for maximum leght of cycles, and L maximum length of alturistic donor chains, refered in the name of archive. In each of these folders there are several files with the names: recourse_method.tsv

 - recourse is Simple, BackArcs or Full and corresponds to recourse policy applied, as presented in the paper;

 - method is MIP or DSG which correspods, respectively, to the results for the Mixed Integer formulation (when they exist; see the paper) or the results for the Delayed Scenario Generation method.

Files cf_L.tsv correspond to the results of the deterministic problem, where the number of transplants is maximized, for a given value of L.

The forth archive HS.zip contains the results for the experiment where arcs fail, and the highly sensitised patients are prioritised. Files hs_L.tsv containt the results of these experiments for different values of L; hs_noprior_L.tsv contains the results for the same failure of arcs, but the highly sensitized patients are not prioritised.