GitHub

KidneyExchange.jl

This a Julia package to solve the deterministic kidney exchange problem. It provides five different solution methods, two of which are based on a branch-and-price algorithm. The other three methods consist in solving compact integer programming formulations. These methods are described in Omer et al. (Oct 2022).

The package also comes with three instance generators that allow to reproduce a benchmark similar to that used in the aforementionned report.

Input data

The package provides a parser (function read_kep_file) for the instances of the PrefLib library publicly shared by John P. Dickerson and described in Dickerson et al. (2012). Those instances must be downloaded from the PrefLib website and stored in the data/preflib folder before solving them with the algorithms of the package.

Otherwise, three generators functions are provided with the package :

Note

The generate_saidman_instance function will generate instances similar to those of the PrefLib library.

Users who wish to run our code on other existing instances may input them as .wmd file and read them with read_wmd_file.

Integer programming solvers

The package was fully tested with the two commercial MIP solvers CPLEX and Gurobi. Those can both be downloaded and used under an Academic licence at https://www.ibm.com/academic/home and https://www.gurobi.com.

If you prefer running a fully open version of the package, it is possible to do so by using a chosen mixture of HiGHS, Clp, Cbc, and GLPK. Be aware that the execution of the algorithms may take longer than communicated in our article if you do so. In particular, for large instances, this is even true for the branch-and-price algorithms which rely on the capacity of the solver to solve the relaxed master problem with integer variables. The corresponding packages are documented at HiGHS.jl, Cbc.jl, Clp.jl and Glpk.jl.

To choose the solver, you need to set the field optimizer of the BP_params or MIP_params structure with one of the following options:

  • HiGHS: use exclusively HiGHS, i.e., both for integer programs (IPs) and linear programs (LPs)
  • GLPK: use exclusively GLPK
  • Clp: use Cbc for every integer program and solve the linear relaxations with Clp
  • Cbc: exactly the same as Clp (***default for MIP approaches***)
  • GLPK-Cbc: use Cbc for every integer program and solve the linear relaxations with GLPK (***default for branch-and-price***)
  • CPLEX: use exclusively CPLEX (requires a licensed installation of CPLEX)
  • Gurobi: use exclusively Gurobi (requires a licensed installation of Gurobi)

Some parameters of the solvers (e.g. the number of threads used by the solver) can be set when calling the constructors of the parameters used by the desired algorithm. Additional details are given in the documentation of MIP_params and BP_params.

Packages Clp, Cbc, Gurobi and CPLEX are not included among the dependencies so they must be added and loaded (with using) if you wish to use one of them. This was necessary due to some compatibility issues with Clp and Cbc, and because CPLEX and Gurobi require a licensed installation.

Quickstart

using KidneyExchange

Generate an instance with 500 pairs of incompatible donors and receivers and 25 non-directed donors. The corresponding input files will be created in the "data/sparse/" folder of the package.

generate_sparse_unos_instance(500, 25, 1)
Write sparse/sparse_500_25_1
- write vertices
- write edges
sparse/sparse_500_25_1 is written

Solve the instance with branch-and-price. The basic usage of this function requires as input, the instance (below "sparse/sparse50025_1"), and the parameters K and L (below 3 and 4, respectively).

solve_with_BP("sparse/sparse_500_25_1", 3, 4)
(KidneyExchange.BP_status(KidneyExchange.BP_info(298.0, 298.0, 1828), "OPTIMAL", 298.0, 0.0, [[495, 70], [463, 56, 446], [302, 489, 496], [264, 69], [199, 22, 208], [414, 183, 250], [287, 209, 319], [448, 434, 201], [238, 420], [263, 47]  …  [78, 136, 409], [205, 478, 422], [433, 397, 34], [401, 458, 138], [309, 210, 16], [83, 459, 382], [279, 307, 1], [435, 272, 365], [419, 153, 245], [44, 148, 461]], [[516, 427, 356, 442], [504, 348, 180, 10, 3], [523, 231, 323, 472], [507, 327, 72, 280, 130], [506, 74, 73, 143, 52], [502, 174, 115, 146, 273], [521, 182, 310, 5, 23], [510, 107, 276, 444, 21], [515, 63, 400, 338, 212], [513, 140, 266, 248, 71]  …  [520, 357, 68, 386, 269], [508, 436, 82, 111, 477], [519, 195, 369, 308, 188], [509, 267, 12, 116, 119], [514, 215, 384, 191, 112], [517, 15, 247, 25, 222], [512, 26, 343, 99, 236], [518, 252, 394, 325, 96], [524, 332, 268, 103, 337], [501, 253, 451, 255, 75]], 1, 5.861055064, 1828, 1, MathOptInterface.OPTIMAL), KidneyExchange.Graph_info(525, 500, 25, 14011, 0.050930570701563066), KidneyExchange.Subgraph_info(201, 73.87562189054727, 0.0, 0.0))

As always with Julia, the first time the solve function is called, it takes extra time.

In a more advanced use case additional parameters can be changed through the object BP_params. For instance, specify another branch-and-price formulation (the second true is to keep verbosity)

solve_with_BP("sparse/sparse_500_25_1", 3, 4, BP_params(true, true))
(KidneyExchange.BP_status(KidneyExchange.BP_info(298.0, 298.0, 529), "OPTIMAL", 298.0, 0.0, [[127, 134], [120, 143], [24, 158], [128, 208], [156, 228], [47, 263], [69, 264], [132, 293], [93, 315], [204, 382]  …  [309, 210, 16], [401, 458, 39], [214, 64, 49], [467, 89, 320], [383, 159, 473], [243, 449, 424], [455, 278, 474], [287, 209, 319], [66, 206, 18], [279, 307, 1]], [[501, 123, 131, 388, 48], [502, 174, 115, 146, 273], [503, 281, 427, 356, 442], [504, 348, 180, 335, 37], [505, 492, 84, 483, 229], [506, 74, 73, 138, 19], [507, 327, 72, 280, 13], [508, 343, 99, 236, 130], [509, 357, 68, 386, 338], [510, 107, 276, 444, 364]  …  [516, 20, 391, 28, 324], [517, 15, 247, 25, 222], [518, 252, 394, 325, 197], [519, 195, 369, 308, 188], [520, 267, 12, 116, 119], [521, 182, 310, 5, 23], [522, 289, 430, 98, 337], [523, 231, 323, 472, 83], [524, 332, 268, 38, 52], [525, 8, 240, 30, 484]], 1, 25.908608467, 529, 1, MathOptInterface.OPTIMAL), KidneyExchange.Graph_info(525, 500, 25, 14011, 0.050930570701563066), KidneyExchange.Subgraph_info(201, 73.87562189054727, 0.0, 0.0))

Solve the instance using one of its compact MIP formulations (HPIEF by default). The basic usage of this function requires as input, the instance (below "sparse/sparse50025_1"), and the parameters K and L (below 3 and 4, respectively).

solve_with_mip("sparse/sparse_500_25_1", 3, 4)
(KidneyExchange.Solution_status("OPTIMAL", 298.0, Inf, [[279, 307, 1], [342, 186, 7], [92, 413, 9], [40, 283, 11], [66, 206, 18], [391, 165, 20], [298, 199, 22], [158, 24], [330, 91, 32], [58, 423, 33]  …  [416, 344, 261], [447, 407, 271], [365, 435, 272], [474, 455, 278], [489, 496, 302], [389, 312], [411, 341], [381, 418, 360], [452, 421], [439, 437]], [[501, 267, 12, 116, 119], [502, 174, 115, 146, 273], [503, 123, 131, 388, 48], [504, 348, 180, 10, 234], [505, 492, 84, 483, 274], [506, 74, 73, 349, 269], [507, 327, 72, 280, 13], [508, 343, 99, 236, 130], [509, 357, 68, 386, 338], [510, 107, 276, 444, 364]  …  [516, 427, 356, 442], [517, 15, 247, 25, 222], [518, 252, 394, 325, 197], [519, 195, 369, 138, 19], [520, 441, 218, 453, 62], [521, 182, 310, 5, 23], [522, 214, 64, 485, 16], [523, 231, 323, 472], [524, 332, 268, 38, 52], [525, 8, 240, 30, 426]], 0, 22.683531761169434), KidneyExchange.Graph_info(525, 500, 25, 14011, 0.050930570701563066), KidneyExchange.Subgraph_info(201, 73.87562189054727, 1340.8557213930349, NaN))

In a more advanced use case additional parameters can be changed through the object MIP_params. For instance, specify another MIP formulation (true is to keep verbosity)

solve_with_mip("sparse/sparse_500_25_1", 3, 4, MIP_params(KidneyExchange.EXTENDED_EDGE, true))
(KidneyExchange.Solution_status("OPTIMAL", 298.0, Inf, [[279, 307, 1], [342, 186, 7], [92, 413, 9], [40, 283, 11], [309, 485, 16], [66, 206, 18], [391, 329, 20], [298, 199, 22], [158, 24], [127, 28]  …  [416, 344, 261], [447, 407, 271], [365, 435, 272], [474, 455, 278], [489, 496, 302], [389, 312], [411, 341], [381, 418, 360], [452, 421], [439, 437]], [[501, 441, 218, 453, 147], [502, 174, 115, 146, 273], [503, 123, 131, 388, 48], [504, 348, 180, 10, 80], [505, 492, 84, 483, 259], [506, 74, 73, 349, 269], [507, 327, 72, 280, 13], [508, 343, 99, 236, 130], [509, 357, 68, 386, 338], [510, 107, 276, 444, 76]  …  [516, 427, 356, 442], [517, 15, 247, 25, 222], [518, 252, 394, 325, 197], [519, 195, 369, 254, 251], [520, 267, 12, 116, 119], [521, 182, 310, 5, 23], [522, 214, 64, 49, 188], [523, 231, 323, 472], [524, 332, 268, 38, 52], [525, 8, 240, 30, 36]], 0, 20.614107370376587), KidneyExchange.Graph_info(525, 500, 25, 14011, 0.050930570701563066), KidneyExchange.Subgraph_info(201, 73.87562189054727, 1340.8557213930349, NaN))

Index