A Feasibility-Seeking Approach to Two-stage Robust Optimization in Kidney Exchange

Kidney paired donation programs (KPDPs) match patients with willing but incompatible donors to compatible donors with an assurance that when they donate, their intended recipient receives a kidney in return from a different donor. A patient and donor join a KPDP as a pair, represented as a vertex in a compatibility graph, where arcs represent compatible kidneys flowing from a donor in one pair to a patient in another. A challenge faced in real-world KPDPs is the possibility of a planned match being 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. In addition to considering homogeneous failure, we present the first approach that considers non-homogeneous failure between vertices and arcs. To this end, we develop solution algorithms with a feasibility-seeking master problem and evaluate two types of recourse policies. Our framework outperforms the state-of-the-art kidney exchange algorithm under homogeneous failure on publicly available instances. 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, patients for whom few kidney donors are available and whose associated exchanges tend to fail at a higher rate than non-sensitized patients.