A feasibility look to two-stage robust optimization in kidney exchange

Abstract

Kidney paired donation programs (KPDPs) are an alternative for patients whose non-ideal donors are willing to donate a kidney to another patient, under the promise that their intended recipient receives a kidney in return from a different donor. A patient and donor join a KPDP as a pair, known in the literature as patient-donor pairs. Pairs can then become vertices in a compatibility graph, where arcs represent compatible kidneys flowing from a donor in one pair to a patient in another. An important challenge of real-world KPDPs is the possibility that a planned match is cancelled, e.g., due to late detection of organ incompatibility or patient-donor dropout. We therefore develop a two-stage robust optimization approach to the kidney exchange problem wherein (1) the first stage determines a kidney matching solution according to the original compatibility graph, and then (2) the second stage repairs the solution after observing transplant cancellations. Unlike the state of the art, which only considers homogeneous failure, we consider for the first time homogeneous and non-homogeneous failure rate between vertices and arcs, and develop solution algorithms with a feasibility-seeking master problem. Current solution methods are tied to the recourse policy in consideration. Instead, our solution framework can solve in finitely many iterations the two-stage robust problem for recourse policies whose recourse solution set consists of a subset of the feasible cycles and chains of the compatibility graph, that contain at least one pair selected in the first stage. Our approach is tested on publicly available instances and compared to a state-of-the-art algorithm under homogeneous failure. Moreover, we provide insights on the scalability of our solution algorithms under non-homogeneous failure for two recourse policies and analyze their impact on highly-sensitized patients.