Papers › A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem
A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem
Lizeth Carolina Riascos-Álvarez, Merve Bodur, Dionne M. Aleman
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Kidney paired donation programs allow patients registered with an incompatible donor to receive a suitable kidney from another donor, as long as the latter's co-registered patient, if any, also receives a kidney from a different donor. The kidney exchange problem (KEP) aims to find an optimal collection of kidney exchanges taking the form of cycles and chains. Existing exact solution methods for KEP either are designed for the case where only cyclic exchanges are considered, or can handle long chains but are scalable as long as cycles are short. We develop the first decomposition method that is able to deal with long cycles and long chains for large realistic instances. More specifically, we propose a branch-and-price framework, in which the pricing problems are solved (for the first time in packing problems in a digraph) through multi-valued decision diagrams. Also, we present a new upper bound on the optimal value of KEP, stronger than the one proposed in the literature, which is obtained via our master problem. Computational experiments show superior performance of our method over the state of the art by optimally solving almost all instances in the PrefLib library for multiple cycle and chain lengths.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections