Dataset for the stable kidney exchange problem

The dataset contains instances of the Kidney Exchange Problem (KEP), when the patient has different preferences over the potential donors. The common practice is to model the KEP on a directed graph G = (V,A), called compatibility graph, where the set of vertices V corresponds to the set of incompatible pairs and an arc from a vertex i to a vertex j indicates compatibility of donor in j with the patient in i. For this dataset graphs are created by use of the generator mentioned in X. Klimentova, A. Viana, J. P. Pedroso, N. Santos. Fairness models for multi-agent kidney exchange programmes. Omega: The International Journal of Management Science (2020) https://doi.org/10.1016/j.omega.2020.102333. The generator creates random graphs based on probabilities for blood type and donor–patient tissue compatibility. The set of vertices in the instances contains both incompatible pairs and non-directed donors (NDDs). Dummy arcs are created from a NDD to each vertex to operate the chains initiated by NDDs in the same way as cycles are operated.

Then, for each arc in the graphs we generate randomly a weight in the interval (0,1). The preferences are provided by ranks of outgoing arcs (r_ij), where r_ij is an integer number between 1 and |V|; the lower the rank the more preferable is the donor in j for patient in i. Those ranks are assigned in accordance with weights: the lower is the weight of an outgoing arc for a given vertex, the more preferred is the corresponding good. For weak preferences, outgoing arcs with weights within each interval of length 1/|V| were considered equally preferable. The dataset contains 4 zip files: two with instances with strict preferences and another two with weak preferences. For each type of preferences there is a file with smaller instances with 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170 and 180 vertices, and another file with bigger instances with 200, 250, 350 and 400 vertices, 50 instances of each size. Files are named in the format n_seed.input, where n = |P| is the number of incompatible pairs in the pool and seed is the seed used by the random function when generating the instance.

The first line of each file contains 5 values:

1) |V| - number of vertices in the graph (the set of vertices V consists of a set of incompatible pairs, P, and a set of NDDs, N, i.e. V = P U N);

2) m - number of arcs in the graph (including dummy arcs from NDDs);

3) |P| – number of incompatible pairs,

4) |N| – number of altruistic donors.

5) number of dummy arcs

In the following m lines of the file the existing arcs (i,j) are presented as follows:

i j w_ij r_ij

where w_ij is the weight and r_ij is the rank of the of the arc (i,j).