  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.
