kidney_solver is a program for the kidney-exchange problem, using Python 3 and the Gurobi IP solver.
nosetests from the base directory.The program reads an instance from standard input, and writes the result to standard output. If no non-directed donors (NDDs) are used, the input format is the .input format. The example in the example_data directory has 64 donor-patient pairs numbered 0, ..., 63, and has 1025 edges. The rows representing edges are in source target weight format. The final row of the input contains -1 three times.
If NDDs are used, the input described above is followed by additional data in a very similar format. The .ndds file in the example_data directory, for example, has 6 NDDs and 188 edges from NDDs. NDDs are numbered from zero. The edges are in source-NDD target-pair weight format.
The program utils/convert.py can be used to convert from .wmd format. (Generated instances in this format can be found on PrefLib.)
The kidney_solver program has three required command-line arguments: cycle cap, chain cap, and formulation. Note that the chain cap is the maximum permitted number of edges in a chain, excluding the dummy arc to the NDD. The formulation can be:
uef: Edge formulation with unrestricted cycle and chain sizeshpief_prime: A hybrid PIEF with an additional refinement that avoids the need for variables in first positionhpief_prime_full_red: hpief_prime, with further reduction by generating cycleshpief_2prime: hpief_prime, with an additional refinement that avoids the need for variables in position equal to the cycle cap. Note that if the cycle cap is less than 3, hpief_prime is used instead.hpief_2prime_full_red: hpief_2prime, with further reduction by generating cycleseef: Reduced extended edge formulation (with a slight modification to the symmetry-breaking constraints)eef_full_red: eef with further reduction by generating cyclespicef: Position-indexed chain-edge formulationcf: Cycle formulation, with one variable per cycle or chainThe optional flag -r can be used to solve on a copy of the graph with vertices relabelled in descending order of out-degree plus in-degree, which may result in a smaller IP model. To set a time limit of LIMIT seconds, use -t LIMIT.
If the cycle formulation or PICEF is used, failure-aware matching with uniform edge failure probability can be performed with -p EDGE-SUCCESS-PROB.
Example 1: .wmd format input
python3 -m utils.convert < example_data/MD-00001-00000100.wmd | python3 -m kidney_solver.kidney_solver 3 3 picefExample 2: input in .input and .ndds format
cat example_data/MD-00001-00000100.input example_data/MD-00001-00000100.ndds | python3 -m kidney_solver.kidney_solver 3 3 picefThe output should be mostly self-explanatory. Each row for the cycles listing is a list of donor-patient pair indices. Each row of the chains listing is the NDD index, followed by a list of donor-patient pair indices.
A Python utility for counting cycles and chains in an instance is also included. This reads from standard input and takes the cycle and chain caps as command-line arguments. Example usage:
cat example_data/MD-00001-00000100.input example_data/MD-00001-00000100.ndds | python3 -m kidney_solver.count_cycles_and_chains 3 3Note that this will probably run quite a bit quicker if you use Pypy rather than CPython.
The sparsify.py instance can be used to delete each edge from an instance with some given probability. The program reads from standard input in the .input + .ndds format, and writes to standard output in the same format. The probability that each edge will be kept is a command-line argument.
cat example_data/MD-00001-00000100.input example_data/MD-00001-00000100.ndds | python3 -m kidney_solver.sparsify .05The utils/add_random_real_weights.awk tool sets the weights on edges to random numbers in the range [0,1). Set the random-number seed on the command line using the seed variable:
cat example_data/MD-00001-00000100.input | awk -f utils/add_random_real_weights.awk -v seed=$RANDOMThe utils/add_random_integer_weights.awk tool sets the weights on edges to random integers in the range [lower, upper), where the variables lower and upper are set on the command line. Set the random-number seed on the command line using the seed variable:
cat example_data/MD-00001-00000100.input | awk -f utils/add_random_integer_weights.awk -v seed=$RANDOM -v lower=5 -v upper=10This is a (probably very incomplete) list of other software for kidney exchange.
I'd be more than happy to try to answer any questions: james.trimble at yahoo.co.uk