Papers › Cutting Plane Approaches for the Robust Kidney Exchange Problem
Cutting Plane Approaches for the Robust Kidney Exchange Problem
Danny Blom, Christopher Hojny, Bart Smeulders
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.
Renal patients which have a willing but incompatible donor can decide to participate in a kidney exchange program (KEP). The goal of a KEP is to identify sets of such incompatible pairs that can exchange donors, leading to compatible transplants for each recipient. There is significant uncertainty involved in this process, as planned transplants may be canceled for a plethora of reasons. It is therefore crucial to take into account failures while planning exchanges. In this paper, we consider a robust variant of this problem with recourse studied in the literature that takes into account vertex failures, i.e., withdrawing donors and/or recipients. This problem belongs to the class of defender-attacker-defender (DAD) models. We propose a cutting plane method for solving the attacker-defender subproblem based on two commonly used mixed-integer programming formulations for kidney exchange. Our results imply a running time improvement of one order of magnitude compared to the state-of-the-art. Moreover, our cutting plane methods can solve a large number of previously unsolved instances. Furthermore, we propose a new practical policy for recourse in KEPs and show that the robust optimization problem concerning this policy is tractable for small to mid-size KEPs in practice.
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