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 __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 __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: .tsv - is Simple, BackArcs or Full and corresponds to recourse policy applied, as presented in the paper; - 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.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_.tsv containt the results of these experiments for different values of L; hs_noprior_.tsv contains the results for the same failure of arcs, but the highly sensitized patients are not prioritised.

Data and Resources

Additional Info

Field Value
Source The instances were generated by implementation of the generator, proposed 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.Transplantation 2006;81:773–82. DOI: 10.1097/01.tp.0000195775.77081.25
Author Kristiaan Glorie, Xenia Klimentova, Margarida Carvalho, Ana Viana, Miguel Constantino
Last Updated March 9, 2020, 21:02 (Europe/Lisbon)
Created March 9, 2020, 17:01 (Europe/Lisbon)
CiteAs GLORIE, Kristiaan, KLIMENTOVA, Xenia, CARVALHO, Margarida, VIANA, Ana, CONSTANTINO, Miguel. Dataset and results for Robust Kidney Exchange Problem [dataset]. 09 March 2020. INESC TEC research data repository. DOI: https://doi.org/10.25747/4y7p-a577
DOI https://doi.org/10.25747/4y7p-a577
dc.Contributor The instances were generated by generator, proposed 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.Transplantation 2006;81:773–82, that was implemented by Kristiaan Glorie.
dc.Coverage.Spatial CEGI, INESC TEC, Porto, Portugal
dc.Date 2019
dc.Format *.txt, *.zip
dc.Format.Extent 392KB
dc.Language EN
dc.Publisher INESC TEC
dc.Relation 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).
dc.Type Compatibility graph characteristics of vertices for the Kidney Exchange Problem.
ddi.GrossFileStructure The instances are splitted in three groups. 20.zip, 50.zip, 100.zip by number of vertices in graphs of instances
ddi.Software The generator used for generation of the instances is implemented in C# programming language.