Dataset for kidney exchange problems

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 the most commonly used 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. Default values for the generator's parameters were used. For the research where probabilities of failure of arcs and vertices are considered, information is provided in an additional file for each instance. The probabilities of failure p_i of a vertex i, or p_ij of an arc (i,j) were generated randomly with uniform distribution in [0;1]. The dataset is split into two parts, according to the size of the graphs. The folder small contains instances with n = 20,30,40,50,60,70,80,90 and100 vertices. There are 50 instances of each size. for instances with n = 20,30,40,50,60,70,100 vertices and 10 instances of bigger sizes. The folder big has instances with n = 100, 200,300,400,500,600,700,800,900,1000,2000, 3000,5000 vertices, with 10 instances of each size.

Each instance has two files with data. 1) The first one is the compatibility graph of an instance of a given size. Name of those files is formed as n_seed.input.gz where n = |V| is the number of incompatible pairs in the pool and seed is the seed, used for random function when generating the instance. 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 w-ij where w_ij is the weight of the arc, which is always equal to 1.0 for all the instances in this dataset. 2) The second file contains probabilities of failure. Name is formed as n_seed.prob.gz The lines of the file formed as follows. Consecutively for each vertex i in V:

p_i p_ij1… pi_jk

where (i, j1)… (i,jk) is the set of outgoing arcs for vertex i.

Data and Resources

Additional Info

Field Value
Source The instances were generated by use of generator, provided by authors 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. DOI: 10.1097/01.tp.0000195775.77081.25
Author João Pedro Pedroso, Ana Viana, Xenia Klimentova
Last Updated September 30, 2019, 17:53 (Europe/Lisbon)
Created September 27, 2019, 21:24 (Europe/Lisbon)
CiteAs PEDROSO, João Pedro, VIANA, Ana, KLIMENTOVA, Xenia. Dataset for kidney exchange problems [dataset]. 27 September 2019. INESC TEC research data repository. DOI: https://doi.org/10.25747/RG74-5D38
DOI https://doi.org/10.25747/RG74-5D38
dc.Contributor The instances were generated by use of generator, provided by authors 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.
dc.Coverage.Spatial CEGI, INESC TEC, Porto, Portugal
dc.Date 2012
dc.Format *.txt, *.zip
dc.Format.Extent 279 MB
dc.Language EN
dc.Relation 1. Constantino M, Klimentova X, Viana A, Rais A. New insights on integer programming models for the kidney exchange problem. Eur. J. Oper. Res. 2013;231(1):57–68. DOI: https://doi.org/10.1016/j.ejor.2013.05.025 Link: https://www.sciencedirect.com/science/article/pii/S0377221713004244; 2. X. Klimentova, J.P. Pedroso, A. Viana. Maximising expectation of the number of transplants in kidney exchange programmes. Computers and Operations Research, V. 73 (2016), p. 1-11. DOI: https://doi.org/10.1016/j.cor.2016.03.004 Link: https://www.sciencedirect.com/science/article/pii/S0305054816300533; 3. F. Alvelos, X. Klimentova, A. Viana. Maximizing the expected number of transplants in kidney exchange programs with branch-and-price. Annals of Operations Research (2017). DOI: https://doi.org/10.1007/s10479-017-2647-4. Link: https://link.springer.com/article/10.1007/s10479-017-2647-4; 4. Klimentova X, Alvelos F, Viana A. A new branch-and-price approach for the kidney exchange problem. In: Murgante B, Misra S, Rocha A M A, Torre C, Rocha JG, Falcão M I, etal., editors. Computational science and its applications ICCSA 2014, Lecture notes in computer science, vol.8580. Switzerland: Springer International Publishing;2014. p.237–52. DOI: https://doi.org/10.1007/978-3-319-09129-7_18 Link: https://link.springer.com/chapter/10.1007/978-3-319-09129-7_18#citeas; 5. Pedroso J P. Maximizing expectation on vertex-disjoint cycle packing. In: Murgante B, Misra S, Rocha A M A, Torre C, Rocha JG, Falcão M I, etal., editors. Computational science and its applications ICCSA 2014, Lecture notes in computer science, vol.8580. Switzerland: Springer International Publishing; 2014. p. 32–46. DOI: https://doi.org/10.1007/978-3-319-09129-7_3 Link: https://link.springer.com/chapter/10.1007%2F978-3-319-09129-7_3
dc.Type Compatibility graph for the Kidney Exchange Problem
ddi.GrossFileStructure The instances are splitted in two groups. small.zip containt with smaller instances with up to 100 vertices, big.zip containt larger graphs. The file kep_io.py exemplifies reading of a test instance in Python language.
ddi.Software The generator used for generation of the instances is implemented in C++ programming language.