{'fraction_non_alphanumeric': 0.03854259487135967, 'fraction_numerical': 0.010042290773822153, 'mean_word_length': 4.289294531308446, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Benders-type Approach for Robust Optimization of Kidney Exchanges under Full Recourse

The goal of kidney exchange programs is to match recipients with a willing but incompatible donor with another compatible donor, so as to maximize total (weighted) transplants. There is significant uncertainty in this process, as planned transplants may be cancelled for a variety of reasons. Planning exchanges while considering failures, and options for recourse, is therefore crucial. In this paper, we reconsider a robust optimization model with recourse proposed in Carvalho et al. (2020) that takes into account the event that a number of donors leaves the KEP. After these donors have left the program, a new set of exchanges is identified (the recourse decision). Current algorithmic considerations do not allow to find optimal solutions for the robust optimization model for realistic sized kidney exchanges with a reasonable time frame. Following the iterative framework in Carvalho et al. (2020) for solving a large-scale mixed integer programming model, we propose a new variable and constraint generation method based on Generalized Benders' Decomposition. A characterization of this method is given based on two widely used integer programming models for kidney exchange programs. Furthermore, a lifting technique is proposed to obtain stronger Benders cuts to speed up computation. Computational results show that our algorithm is very competitive, improving on the running time of the state-of-the-art method by one order of magnitude. Furthermore, our methods are able to solve a large number of previously unsolved instances within the same time limit.


Introduction
In the final stage of chronic kidney disease, patients suffer from end-stage renal disease (ESRD). Treatments for this disease consist of dialysis or the more preferred option of a kidney transplant. However, the supply of healthy kidneys from deceased donors does not adequately meet the demand from ESRD patients. An alternative are living donations, e.g., by a relative or friend who is willing to donate one of their two kidneys to a specific patient. This is possible since only one healthy kidney is necessary to ensure sufficient kidney function. Transplants from living donors also offer better long-term outcomes for the recipient compared to deceased donor grafts, with limited risk to the donor, see, e.g., Davis and Delmonico (2005). However, to allow for donations, recipients must be medically compatible with the donor. Incompatibilities can be caused, among other reasons, by conflicting blood or tissue type. Recipients might thus be unable to receive a transplant from their intended donor.
To overcome incompatibilities between a patient and its related donor, Rapaport (1986) introduced Kidney exchange programs (KEPs), which have been further popularized by a series of seminal papers in the field (see Roth et al. (2004), Roth et al. (2005), and Roth et al. (2007)). In a KEP, a set of incompatible patient-donor pairs is given, and every donor is willing to give one of its kidneys to any patient as long as their paired recipient receives a transplant in turn from some other donor. In the simplest case, one is thus looking for tuples (P 1 , P 2 ) of such pairs such that the kidney of P 1 's donor is compatible with the recipient of P 2 and vice versa. Once such a match is identified, the patients from P 1 and P 2 can receive the kidney from the other pair's donor. We call such a swap a 2-cycle as it includes two patient-donor pairs. Of course, this idea can be generalized to k-cycles, where the exchange of donors occurs in a cyclic way between k patient-donor pairs. In many real-life KEPs, an upper bound K is used for the size of a cycle, see Biró et al. (2019). As transplants within a single cycle are usually performed simultaneously to remove the risk of donors reneging once their paired patient has received a kidney, long cycles are logistically challenging and thus avoided.
Extensions to the basic KEP model include non-directed donors, as studied in Morrissey et al. (2005) and Roth et al. (2006). These donors are willing to donate to any recipient, without requiring a return transplant to a paired recipient. Such non-directed donors can start a chain of transplants, in which the donor of the i-th pair in the chain donates a kidney to the recipient of the (i + 1)-th pair. The donor of the last pair in the chain can donate their kidney to a recipient on the deceased donor waiting list, or becomes a bridge donor, functioning as a non-directed donor in a future KEP run. In practice, it is often also assumed that the maximum chain length is bounded by some integer L.
The basic KEP model can be regarded as a directed graph G = (V, A) whose vertices v ∈ V correspond to recipient-donor pairs and non-directed donors, and an arc (i, j) ∈ A corresponds to compatibilities between the donor of i and the recipient of j. One intuitive objective in kidney exchange programs is to maximize the number of transplants that can be realized. Figure 1 illustrates an example of a kidney exchange program. Figure 1: Example of a KEP model. Each vertex corresponds to a recipient-donor pair (P 1 , . . . , P 8 ) or a non-directed donor (N 1 , N 2 ). Possible transplants are depicted by the bold arcs leading to one chain of length one, two 2-cycles and one 3-cycle, i.e., eight transplants in total.
Basic KEP models assume that all identified matches proceed to transplant. In practice however, this is usually not the case. For example,  report that 93% of proposed matches fail in the UNOS program. In the NHS Living Kidney Sharing Scheme, 30% of identified matches did not proceed to transplant between 2013-2017(NHS, 2017. Such failures can occur for a variety of reasons, two examples are the identification of additional medical incompatibilities between matching run and transplant, or recipients and donors may (temporarily) drop out due to health issues. Mathematical models for KEPs incorporating the possibilities of failure of intended transplants have been studied extensively in the literature.  first consider arc failures with equal arc existence probabilities and weight for each cycle and chain based on their expected number of transplants rather than only on the maximum achievable number of transplants. Bidkhori et al. (2020) extends this model to a setting with inhomogeneous arc existence probabilities and gives a compact formulation. Since stochastic models require accurate estimations for arc existence probabilities, an alternative model based on robust optimization is proposed in McElfresh et al. (2019). In addition to handling the possibility of failures a priori, an additional decision can be made once the failures are observed, called the recourse decision. In a recourse decision, the initially proposed solution can be adapted subject to some constraints, which might allow for a significant percentage of additional transplants to be realized, see e.g. Bray et al. (2015). One possible implementation of recourse is to allow an entirely new set of cycles and chains, only involving pairs and NDDs corresponding to donors that are not affected by failure. Carvalho et al. (2020) combines these concepts in a three-stage robust optimization approach, where the final stage is the recourse decision.

Our contribution
This paper builds further on the three-stage robust optimization model proposed by Carvalho et al. (2020). In the first stage, an initial set of cycles and chains is proposed for potential transplants. The second stage incorporates the possibility that a limited number of donors will fail pre-transplant such that a part of the intended transplants cannot proceed. The final stage involves a recourse decision. Throughout this paper, we consider the setting of full recourse, meaning that all cycles and chains can be considered that are not affected by donors that have failed in the second stage, since it is the least restrictive and most natural implementation of recourse. The aim of the model is to maximize the number of recipients that both (i) are included in the initial set of cycles and chains, and (ii) correspond to a proceeding transplant after recourse. To solve their robust model, Carvalho et al. (2020) proposed an algorithm in which a mixed-integer program (MIP) of exponential size needs to be solved. This problem is tackled by an iterative procedure that solves a restricted version of the full MIP that only takes some possible failure patterns into account. If the obtained solution can be confirmed to be already an optimal solution of the original MIP, the method stops. Otherwise, new patterns are generated, which results in adding further variables and constraints to the restricted MIP which needs to be solved again. They report computational results in which the robust optimization model can be solved to optimality within one hour for realistic instances with up to 50 vertices, i.e., the number of recipient-donor pairs and nondirected donors combined, with K = 3 and L = 2 and a maximum number B ∈ {1, 2, 3, 4} of donors leaving the program. Nevertheless, the time limit was frequently reached for instances with 100 vertices, where the main bottleneck is the generation of new failure patterns. Since KEPs of these sizes are already operating, and their sizes are still increasing, algorithms need to be devised that are much more efficient in practice. Furthermore, longer chains are of interest since these are believed to lead to a significant benefit in the number of transplants that can be realized. However, setting L > 2 will lead to even larger MIP models and thus higher computation times.
For these reasons, we propose an alternative algorithm to generate failure patterns, and thus, to solve the robust optimization problem. Specifically, we suggest to use a Benders-type approach, which is used to solve a MIP for generating new patterns. We discuss this method for two MIP models for KEP, the well-known cycle-chain formulation due to Roth et al. (2007) and the position-indexed cycle edge formulation (PICEF) introduced in Dickerson et al. (2016). Since the time needed to solve the robust model heavily depends on the number of patterns that need to be generated, we also discuss means to generate patterns that are more meaningful for the problem. We show through computational experiments on benchmark instances that our algorithms for the robust optimization problem outperform the current state-of-the-art optimization method of Carvalho et al. (2020) by an order of magnitude. These improvements pave the way for solving larger and more difficult instances.
To provide a basis for our new algorithm, we continue in the following subsection with a short review of the relevant literature. Then, we give a precise mathematical description of the robust optimization model of Carvalho et al. (2020) and review integer programming formulations and algorithms for this model in Section 2. In Section 3, we propose new MIP models for a subproblem of the robust optimization model, which is solved through a new iterative algorithm based on a generalized version of Benders' decomposition. Several enhancements are provided in Section 4 that have the purpose of reducing the number of iterations of our algorithms. We conclude the article with an extensive numerical experiments in Section 5.

Literature review
The model in Carvalho et al. (2020) that we study in this paper is a specific example of a general class of optimization models known as the class of defender-attacker-defender (DAD) models. Problems involving network interdiction are often intuitively modeled by a DAD model, many of which are surveyed in Smith and Song (2020). DAD models often follow a general multilevel structure of a sequential game with two players, the defender and the attacker, and three decisions. First, player one can spend a budget to protect or give additional value to parts of a network, e.g., a subset of vertices or arcs in a graph. Afterwards, the second player acts as an adversary and has a separate budget to disrupt parts of network that are not protected by player one. In the third and final decision, player one aims to maximize some graph parameter on the non-disrupted part of the network. We formalize how the model in Carvalho et al. (2020) fits in this class in Section 2.
Research related to kidney exchange programs is not restricted to KEPs with incompatible recipientdonor pairs and non-directed donors and robust models. There exist kidney exchange programs in practice which also allow compatible pairs to participate. Although transplantation within this pair is feasible, the recipient of such a pair might benefit from the existence of donors in the kidney exchange pool forming a better match, see, e.g., Roth et al. (2006) and Gentry et al. (2007). Furthermore, it might happen that also a larger number of recipients from incompatible pairs will now receive a kidney as a result of the presence of compatible pairs. There exist multiple objectives that can indicate the ultimate goal of KEPs. Among those are maximizing the number of transplants, the number of hard-to-match patients, and the number of 2-cycles, but also the quality of transplants. Hierarchical optimization over a variety of objectives is common in fielded exchanges, see Biró et al. (2020) for an overview of established KEPs in Europe and their stated objectives.
In addition, more realistic models for kidney exchange, such as stochastic models and recourse in kidney exchange programs, are extensively studied. Alvelos et al. (2019) propose a stochastic model with internal recourse, meaning that once a cycle or chain fails, another cycle or chain can be chosen on the remaining non-failing vertices. Klimentova et al. (2016) extends this notion to subset recourse, where a number of small disjoint subsets of vertices are tested for failures, and recourse is allowed within these subsets. An alternative recourse model is proposed in Smeulders et al. (2019), that aims to identify which crossmatch tests should be performed, given a limited testing budget, in order to maximize the expected number of transplants.
Most algorithms related to kidney exchange programs are based on integer programming (IP). An intuitive IP formulation is the cycle-chain formulation (CC) due to Roth et al. (2007), which uses a binary variable for each cycle and each chain, and constraints for each pair and each NDD j, stating that only one cycle or chain can be chosen that includes j. One readily verifies that the number of variables in this formulation is in the worst-case exponential in |V | and therefore becomes impractical when the number of participating pairs and NDDs increases. A common technique for solving the cycle-chain model is branch-and-price, see Glorie et al. (2014) and . Another fundamental formulation is the edge formulation due to Abraham et al. (2007). Instead of cycle and chain variables, this formulation uses binary variables y ij for each (i, j) ∈ A, that indicate whether the donor of i donates a kidney to the recipient of j, leading to a polynomial number of variables. However, the number of constraints is exponential in the number of pairs and NDDs. Constantino et al. (2013) introduced the first compact formulations, i.e., models with a polynomial number of variables and constraints. The drawback of this formulation is that the LP relaxation is generally weaker than of the CC formulation.  introduced the position-indexed cycle edge formulation (PICEF), which is a hybrid variant of different models: equivalent to CC, it uses binary variables for each cycle. But instead of using variables for each individual chain, chains are modeled by variables that express the position of an individual transplant within a chain. If no chains are considered, CC and PICEF thus coincide. Otherwise, the LP relaxation of PICEF is shown to be strictly weaker than that of CC.

Problem description
In this article, we consider KEPs consisting of a set P of incompatible recipient-donor pairs and a set N of non-directed donors. Before we formally define the problem we want to solve, we need to introduce some terminology and notation. To represent a KEP, we use a directed graph G = (V, A), the compatibility graph, with vertex set V := P ∪ N and arc set A ⊆ V × P . An arc (i, j) ∈ A encodes that the donor of vertex i ∈ P ∪ N is compatible with the patient of vertex j ∈ P . Moreover, throughout the article, K and L denote upper bounds on the maximum number of arcs that the KEP allows in cycles and chains, respectively. The cycles and chains that can be used according to the policy of the KEP are denoted by C K and D L , respectively. That is, C K denotes the set of directed cycles in G consisting of at most K arcs; D L is the set of directed paths in G that start from some NDD and consist of at most L arcs. Furthermore, we denote by V (c) and A(c) the set of vertices and arcs in c, respectively. For a vertex j ∈ V , we now denote by C j K (D j L ) the sets of cycles (chains) c such that j ∈ V (c). We further denote by F G the set of subsets S ⊆ C K ∪ D L such that the elements of S are pairwise vertex-disjoint, i.e., S forms a cycle and chain packing on G. We will refer to F G as the set of feasible KEP solutions, since each element of F G describes a feasible set of exchanges.
As mentioned earlier, we can describe the model in Carvalho et al. (2020) as a defender-attackerdefender model consisting of three stages. In the first stage, a defender can make a decision x contained in some set X . Then, the attacker makes a decision u contained in some set U(x) that might depend on the defender's decision x. Finally, the defender is allowed to select another decision y contained in some set Y(x, u) which might depend on both the attacker's decision u and the defender's initial decision x. Furthermore, in each of the three levels an objective has to be taken into account. We denote these objectives by f (·, ·, ·), g(·, ·), and h(·), respectively. The goal of a defender-attacker-defender problem is to solve the trilevel optimization problem max f (x, u * , y * ) s.t.
x ∈ X , u * ∈ arg min g(u, y * ) The problem considered by Carvalho et al. (2020), referred to as the full recourse robust kidney exchange problem, follows this general defender-attacker-defender scheme. We detail the choices in each of the three stages here.
1. Given the compatibility graph G = (V, A), the defender selects a feasible set of exchanges x ∈ X , where Here, χ S denotes the characteristic vector of S. In other words, X denotes the set of all feasible KEP solutions on G, or the set of initial KEP solutions, since X corresponds to the domain of initial decisions for the defender. For a solution x ∈ X , we denote by V (x) the set of pairs j ∈ P for which there exists some cycle or chain c with j ∈ V (c) such that x c = 1. These pairs correspond to the set of recipients that will receive a transplant according to the initial KEP solution x.
2. The attacker is given a budget B ∈ N and can decide to attack up to B vertices in the compatibility graph, corresponding to pairs or non-directed donors leaving the program. The attacker's aim is to disturb the initial KEP solution as much as possible, as well as hinder recourse in the next stage.
The attacker's domain is defined as We refer to an attacker's decision u ∈ U(x) as an attack. We encode an attack using a vector of length |V |, where u j = 1 means that vertex j is an attacked vertex with respect to u, and u j = 0 if j is not attacked. Furthermore, for each attack u, we define i.e., the set of vertices that are not attacked by u. Notice that the domain of the attacker does not explicitly depend on the initial KEP solution x ∈ X chosen by the defender.
3. The defender finally is given the opportunity to reconsider its initial KEP solution after observing which donors leave the program according to the chosen attack u ∈ U(x), in order to (partially) restore the damage inflicted by the attacker upon cycles and chains of the chosen initial KEP solution x ∈ X . The defender can decide to choose an alternative KEP solution on the vertex- .We define the domain of this decision, given an initial KEP solution plan x ∈ X and subsequent attack u ∈ U(x), by and we refer to each y ∈ Y(x, u) as a recourse KEP solution. Using the notation introduced above, V (y) denotes the set of pairs j ∈ P such that there exists some cycle or chain c with j ∈ V (c) for which y c = 1. This again corresponds to the set of recipients that will receive a transplant according to the recourse KEP solution y ∈ Y(x, u).
The above model still has some degrees of freedom, because its objectives are not fixed. In practice, whenever an initial KEP solution x ∈ X is proposed, recipients are notified that they might receive a transplant. It is of course a disappointing experience when recipients will not receive a transplant anymore due to some leaving donor breaking the cycle or chain. Taking this into account, Carvalho et al. (2020) considered the objective of maximizing the worst-case guaranteed number of recipients that receive a transplant according to both the initial KEP solution x ∈ X and the recourse solution y ∈ Y(x, u) w.r.t.  all attacks u ∈ U that can be realized by the attacker. The three-stage optimization problem described above is illustrated in Figure 2. Although our definition of Y(x, u) will generally allow for the best robust solution, the drawback is that for large instances it is computationally challenging to solve this problem to optimality with existing techniques from Carvalho et al. (2020). For this reason, we devise new algorithms for the robust kidney exchange problem with full recourse that are competitive and more scalable for practical applications than the state-of-the-art. To be able to accurately compare our methods with the methods by Carvalho et al. (2020), we provide details on the latter in the next subsection.

CC-based mixed-integer programming models
In this section, we discuss a mixed-integer programming model of the trilevel problem introduced above, and we provide a summary of the techniques suggested by Carvalho et al. (2020) to solve it. In the next section, we will then develop an alternative method to solve the problem, which turns out to be more efficient computationally. Formally, these method allow us to find an answer to the following decision problem.
Definition 1. (Full recourse robust kidney exchange problem (FRRKEP)) Given: Compatibility graph G = (V, A), defender domains X and Y, attacker domain U, integer t Question: Does there exist an initial KEP solution x ∈ X such that for all attacks u ∈ U(x) ⊆ U there exists a recourse KEP solution y ∈ Y(x, u) ⊆ Y such that V (x) ∩ V (y) ≥ t?
To be able solve it in practice, Carvalho et al. (2020) exploit that the attacker's domain U is a finite set, which allows them to model FRRKEP as a MIP. Specifically, they suggest the following MIP model z F R (U) that is based on the cycle-chain formulation, see Roth et al. (2007).
In this model, variables y u j are used for each patient-donor pair j ∈ P and each attack u ∈ U, indicating whether or not the recipient of j receives a transplant according to both the initial and the recourse KEP solution under attack u. Furthermore, a binary variable x c for each cycle and chain c ∈ C K ∪ D L indicates whether or not c is used in the initial KEP solution, and analogously x u c for the recourse KEP solution. Constraints (2b) are used to make sure that the value Z accurately represents the largest guaranteed overlap in the initial and recourse KEP solutions over all attacks. Constraints (2c) and (2d) ensure that y u j = 0 if the initial or recourse KEP solution under u do not involve some cycle or chain c with j ∈ V (c). Notice that in each optimal solution to z F R (U), we have y u j = 1 otherwise, since we want to maximize the value of each variable y u j while preserving feasibility. Since in any optimal solution, the value of the variables y u j is either 0 or 1, it is not necessary to impose integrality constraints on these variables. Furthermore, Constraints (2e) and (2f) impose that both the initial and recourse KEP solution induce vertex-disjoint exchanges, where the latter also guarantees that no cycle or chain containing an attacked node is selected in the recourse solution.

Iterative solution approach
Since this MIP formulation requires many variables and constraints per attack u ∈ U, it is computationally intractable to solve the full model (2) by a black-box MIP solver. Instead, Carvalho et al. (2020) proposed an iterative solution approach for this MIP. They start with restricting the attacker's domain to a small rangeŪ ⊆ U of attacks. If they can show that the solution of z F R (Ū) is already optimal w.r.t. the set of all attacks U, their method stops. Otherwise, a new attack in U \Ū is added to U and the previous steps are repeated. The main component of their method is thus the mechanism to generate a new attack, u ∈ U \Ū such that, given an initial solutionx ∈ X , there exists no recourse solution . This mechanism uses a subroutine based on the problem of finding the best recourse solution x u given an initial solutionx ∈ X and an attack u ∈ U(x). It can be modeled as the following IP: where the objective coefficients w c (x) are defined as i.e., the number of recipient-donor pairs j ∈ V (c)∩P that were involved in some cycle or chain c chosen in the initial KEP solution. In Model (3), the objective is equivalent to maximizing the total sum of weights of cycles and chains chosen in a feasible recourse KEP solution on G[V u ], i.e., the number of transplants to patients that were also planned to receive a transplant in the initial solutionx. Constraints (3b) impose that the recourse KEP solution x u is vertex-disjoint. This means that R(x, u) is equivalent to solving a maximum weight kidney exchange program. In other words, R(x, u) computes the optimal recourse decision given an initial KEP solutionx ∈ X and attack u ∈ U(x). A flowchart of this method is given in Figure 3. Initially, a small setŪ ⊆ U of attacks is selected and z F R (Ū) is computed. This restricted robust model yields an optimal initial solutionx ∈ X . In each iteration of the algorithm, we solve the problem One can then decide based on the value of A(x) whether there exists an attack u * ∈ U \Ū such that Although it is suggested that we should find the attack u ∈ U(x) with the smallest objective for R(x, u), it actually suffices to either (i) show there exists no attack satisfying Inequality (6) or (ii) to find an attack satisfying Inequality (6). In the following, we will use that A(x) is the problem of deciding if case (i) or case (ii) holds and refer to it as the attack generation problem. If case (i) holds, we can conclude that z F R (Ū) = z F R (U), so the problem is solved to optimality. Otherwise, an attack u * satisfying Inequality (6) is identified and added toŪ. This means that the corresponding variables and constraints are added to z F R (Ū) and the method iterates. Notice that this method terminates in finite time, since only a finite number of distinct attacks u ∈ U can be generated.

Solving the attack generation problem
We now focus on the subroutine of the iterative method that solves the attack generation problem A(x). Carvalho et al. (2020) propose a branch-and-bound type algorithm to solve A(x). A branch-and-bound tree is created and at every non-leaf node, a vertex j ∈ V is chosen to be attacked or not attacked. This decision is incorporated in the tree by creating two child nodes that fix u j to 1 and 0, respectively. Consequently, at each node t of the tree, a subset of the binary u-variables has already been fixed, which is used to derive bounds on z F R (U). Lower bounds are obtained through extending the u-variables fixed to 1 to an attack u t of B vertices and counting the number of vertices in the cycles/chains not affected by the attack. This is indeed a lower bound on z F R (U), because the attack removes cycles/chains fromx and we do not compute an alternative recourse solution. Upper bounds are computed through solving R(x, u t ), which is valid since u t is a feasible attack, i.e., its objective is always at least as high as the value of A(x). Notice that the model can terminate early whenever we compute an upper bound that is smaller than z F R (U), since the corresponding attack u t then satisfies Inequality (6).

PICEF-based formulations
The solution approach described above can also be adapted to fit the definition for other integer programming formulations for the kidney exchange problem. Carvalho et al. (2020) proposed an alternative formulation based on the position indexed cycle edge formulation (PICEF) introduced by Dickerson et al. (2016). Instead of enumerating all chains d ∈ D L , it considers binary variables ξ ij ∈ {0, 1} for each (i, j) ∈ A and each position index ∈ L(i, j) ⊆ L = {1, . . . , L} that describes the position of the arc in a chain. Note that for each arc (i, j) ∈ A, a position index ∈ L(i, j) exists if and only if there exists a path of length − 1 from an NDD to i that does not traverse j. Since chains d ∈ D L start from a non-directed donor i ∈ N , this means that arcs i.e., the set of arcs that can have position index . PICEF is in fact a hybrid formulation for the basic KEP model in the sense that there still exist binary variables x c for each cycle c ∈ C K , but the chain variables are replaced by position indexed arc variables ξ ij for each arc (i, j) and position ∈ L(i, j). The full recourse robust kidney exchange problem z F R (U) can be formulated with PICEF as The formulation (7) can be explained as follows. Again, Constraints (7b) are used to model the minimum guaranteed number of patients that receive a transplant according to both the initial and recourse KEP solution. Constraints (7c) and (7d) again ensure that y u j = 0 whenever a recipient of pair j ∈ P either does not receive a transplant in the initial or the recourse KEP solution with respect to an attack u ∈ U. The structure of the MIP again allows us to pick the value of y u j as large as possible while preserving feasibility, so y u j = 1 whenever both the initial solution and recourse solution under u involve a transplant for recipient j. The PICE formulation makes a distinction between patient-donor pairs and non-directed donors when it comes to imposing vertex-disjointedness of KEP solutions. For each patient-donor pair j ∈ P , Constraints (7e) and (7g) imply that we can either choose a cycle containing j or a position indexed arc going into j, for the initial and recourse KEP solutions respectively. For each non-directed donor j ∈ N , Constraints (7f) and (7h) ensure that there is at most one position indexed arc going out of j selected. Constraints (7g) and (7h) also ensure that recourse KEP solutions under u do not involve attacked vertices. Finally, Constraints (7i) and (7j) ensure that an arc (i, j) at position ≥ 2 can only be chosen whenever a preceding arc going into i is picked in position − 1.
Furthermore, given an initial KEP solution (x,ξ), the weight of an arc (i, j) ∈ A is given by i.e., w ij (x,ξ) = 1 if patient j receives a transplant according to the initial KEP solution (x,ξ), and 0 otherwise. Similarly, the weight of a cycle is defined as i.e., the number of patients of cycle c ∈ C K involved in the initial KEP solution (x,ξ).
The problem R(x,ξ, u) of finding the best recourse KEP solution given an initial solution (x,ξ) and attack u can then be formulated as It is then straightforward to adapt the iterative approach due to Carvalho et al. (2020) to these PICEFbased models, as can be seen in Figure 4. 3 Benders-type approaches to the full recourse robust kidney exchange problem In this section, we describe a new algorithmic approach to solve the full recourse robust kidney exchange problem. For our new approach, we still make use of the basic framework depicted in Figure 3. Our main contribution is an alternative algorithm for generating new attacks. It is based on a reformulation of the attack generation problem A(x) given an initial KEP solutionx ∈ X . We investigate two variants of these IPs, based on the cycle-chain formulation (CC) and the position-indexed cycle edge formulation (PICEF) respectively.

Generalized Benders decomposition algorithm
We first provide a single-level MIP reformulation of the attack generation problem A(x) using the cyclechain formulation for kidney exchange programs. This new formulation is based on the set of all feasible KEP solutions F G . We define the remainder of a feasible KEP solution S ⊆ F G with respect to attack u ∈ U as ρ(S, u) i.e., the set of cycles and chains in S not affected by the attack u. Note that the problem R(x, u) of finding the best recourse solution x u given an initial KEP solution x ∈ X and attack u ∈ U(x) is equivalent to solving max i.e., to maximize the total weight of the remainder over all feasible KEP solutions S ∈ F G . Using this observation, we can reformulate A(x) as a single MIP z(F G ,x) based on the set of feasible KEP solutions F G : We now show that this is indeed a valid reformulation for A(x).
Theorem 2. The integer program (11) is a formulation for the attack generation problem A(x) given by (5).
Proof. For a given feasible attack u ∈ U, it is imposed through Constraints (11c) that x c ≥ 1 for a cycle or chain c ∈ C K ∪ D L whenever none of the vertices j ∈ V (c) is attacked by u, and x c ≥ 0 otherwise. Hence, there exists an optimal solution that is binary: given an optimal solution x, we can reduce x c to 1 (or 0) if none of c's nodes is attacked (there is an attacked node in c) without affecting the objective value of x since the weights w c (x) are non-negative. Moreover, each constraint from (11b) corresponds to a feasible KEP solution S ∈ F G , and the right-hand side consists of the variables and weights of cycles and chains in S. Therefore, for every attack u ∈ U, the objective value is equal to the maximum of the total weight of the remainders ρ(S, u) over all feasible KEP solutions S ∈ F G , or in other words, the value of R(x, u). Since we consider a minimization problem, we search for the attack u ∈ U such that this maximum weight is as small as possible. This shows the equivalence of this formulation with the attack generation problem A(x).
Note that because of Constraints (11b), the number of constraints in Model (3) might be exponential in |V |. To reduce the number of constraints, observe that Constraint (11b) for a KEP solution S ∈ F G is redundant if there exists another KEP solution S ∈ F G with S ⊂ S . For this reason, it is sufficient to only include (11b) for KEP solutions S ∈ F G that are (inclusionwise) maximal. Since the number of maximal KEP solutions can still be exponential in |V |, we use a row generation technique that allows us to solve (11) iteratively.
The idea of this algorithm is to initially select a restricted set F G ⊆ F G of feasible KEP solutions and to solve z(F G ,x). This restricted model gives us an optimal attack u ∈ U and objective value Z . To check whether an inequality of type (11b) is violated, we solve the problem R(x, u ) of finding a best recourse solution given an initial solutionx and attack u . Suppose that x is such an optimal recourse solution. If R(x, u ) is at most Z , then we have found an optimal solution to (11). Otherwise, we add the constraint associated with x to F G and iterate until no violated constraint can be found anymore. Although R(x, u) is equivalent to solving a weighted kidney exchange problem and thus NPhard in general due to Abraham et al. (2007), it can still be solved efficiently in practice since many MIP formulations for KEPs, such as the cycle-chain formulation and PICEF, have a rather tight LP relaxation.
We call this a Benders-type approach since we can split the problem into a master and subproblem. Here, the problem z(F G ,x) serves as the master problem. Furthermore, given an optimal attack u ∈ U with respect to this master problem, we solve the subproblem R(x, u ) to identify the best recourse solution given initial solutionx and attack u . The optimal solutions of the subproblems in turn each provide a constraint from (11b), which are the Benders cuts based on feasible KEP solutions for the master problem. Algorithm 1 provides the exact description of our method.
In Algorithm 1, we initialize the restricted set of feasible KEP solutions F G = {x}. Next, we solve z(F G ,x) and check two conditions. On the one hand, if z(F G ,x) ≥ z F R (Ū), then for any attack u there exists a recourse KEP solution on G[V u ] with weight at least z F R (Ū). Hence there cannot exist an attack We conclude that z F R (Ū) = z F R (U), i.e., the full recourse robust kidney exchange problem is solved to optimality. This condition is checked in Line 4, and we break out of the loop whenever this occurs.
On the other hand, there might exist an attack u * ∈ U \Ū such that (12) is violated. Then, whenever we solve the KEP on G[V u * ], the if-statement in Line 6 is triggered, as z F R (Ū) = minū ∈Ū R(x,ū). We return this attack as output of the iterative algorithm and add it toŪ. Furthermore, we add both the Algorithm 1: Benders-type algorithm for solving the attack generation problem based on the cyclechain formulation Data: graph G = (V, A), setŪ ⊆ U of attacks, optimal initial KEP solutionx ∈ X for zF R(Ū ) Result: attack u * ∈ U \Ū with R(x, u * ) < R(x,ū) for allū ∈Ū, or show nonexistence sets of Variables (2g)-(2h) and Constraints (2c)-(2e) corresponding to u * to obtain z F R (Ū ∪ {u * }). If both conditions do not hold, we consider a recourse KEP solution x(u * ) that is optimal on G[V u * ], add it to the restricted set of feasible maximal KEP solutions F G , and iterate. We will now show that this algorithm terminates in finite time and gives a correct decision about whether or not an attack exists that violates the optimal solution with respect to the restricted robust problem z F R (Ū).
Proof. We start by observing that the domain of attacks U is finite as it is a subset of finite-dimensional binary vectors. Furthermore, one can check that-whenever we iteratively solve z(F G ,x) and add attacks toŪ-each attack u ∈ U minimizes z(F G ,x) at most twice. To see this, suppose there is an attack u * ∈ U minimizing z(F G ,x) for the second time during the execution of the algorithm. Then, during the first iteration in which this occurs, we get both z(F G ,x) < z F R (Ū) and R(x, u * ) ≥ z F R (Ū). Some optimal recourse KEP solution x(u * ) corresponding to u * is then added to F G . Notice now that if u * becomes the minimizer of z(F G ,x) for a second time, we get that z(F G ,x) ≥ R(x, u * ) ≥ z F R (Ū) as some best recourse KEP solution x(u * ) with respect to u * has already been added to F G . Therefore, the algorithm terminates since we satisfy the condition in Line 4 after a finite number of iterations. Since z(F G ,x) is a valid formulation for the attack generation problem, we will return no attack if and only if there really exists no attack u * ∈ U for which the best recourse solution has smaller weight than for allū ∈Ū, hence the algorithm decides correctly on the attack generation problem.

PICEF-based implementation
We consider also a reformulation for the attack generation problem based on PICEF due to . The advantage of using PICEF compared to the cycle-chain formulation is that instead of an exponential number of chain variables, PICEF considers position indexed arcs, of which there exist polynomially many. PICEF is preferred especially for kidney exchange programs involving many nondirected donors and in which the maximum chain length is large (or even unbounded). In our application, using a PICEF-based formulation introduces some complications. In the cycle-chain formulation of this problem, we require only a single variable for each possible cycle or chain. Indeed, if a vertex in a cycle or chain is attacked, this cycle or chain is unavailable for every KEP solution. In a PICEF based formulation, arcs may not only become unavailable by attacks on their origin or destination, but also by attacks on vertices earlier in the chain. Whether an arc may be used thus depends on the value of some other arc variables, which might vary depending on the KEP solution. Figure 5 demonstrates that choosing the value of a position indexed arc variable is not unambiguous.
Example 4. Consider the compatibility graph depicted in Figure 5 consisting of four vertices: the two NDDs N 1 and N 2 , and the two recipient-donor pairs P 1 and P 2 . Furthermore, two feasible KEP solutions are indicated with red arcs and dashed blue arcs respectively. Notice that both solutions use the arc (P 1 , P 2 ) ∈ A as the second arc of a chain, i.e. at position = 2. Whenever the attacker performs an attack on vertex N 2 , it completely breaks the blue chain, meaning ξ P1,P2,2 should have value 0. However, the red chain completely remains, meaning ξ P1,P2,2 should have value 1. Therefore, there is an ambiguity in how to choose the value for this position indexed arc variable. When we want to derive a PICEF implementation for the attack generation problem A(x,ξ) in a similar fashion as in Model (11), we need to address this issue. We can overcome this problem by adding an extra index to the arc variables indicating the feasible KEP solution S ∈ F G it corresponds to. This way, there cannot exist any confusion on the value of an arc variable given an attack u ∈ U. Let us now denote by A S the set of arcs with position index ∈ L used in a feasible KEP solution S ∈ F G .
The corresponding reformulation z(F G ,x,ξ) of the attack generation problem A(x,ξ) can then be given by where We briefly go over this model to explain the differences. Again, consider some attack u ∈ U. Then, Constraints (13b) consider all feasible KEP solutions and the value on the right-hand side again corresponds to the weight of all cycles and chains that are not attacked by u. Constraints (13c) impose as before that we set x c = 1 if none of the vertices of cycle c ∈ C K is attacked by u. We then make a distinction between arcs going out of a non-directed donor and arcs going out of patient-donor pairs. In the first case, Constraints (13d) ensure that an arc (i, j) at position 1 of a chain remains if neither of i and j is attacked by u, since the first arc in a chain is only affected by attacks on these two vertices. In the latter case, Constraints (13e) impose that an arc (i, j) occurring at position ≥ 2 in a chain of KEP solution S remains in a solution if both its preceding arc (k, i) at position − 1 remains and j is not attacked by u.
Using these adaptations for the MIP formulations of the three levels of our trilevel problem, we can run Algorithm 2 to solve the attack generation problem A(x,ξ). The only difference here compared to Algorithm 1 is the notation for both the initial and recourse KEP solutions.
Remark 5. Whenever we consider a feasible KEP solution S ∈ F G , the inequalities corresponding to feasible KEP solutions are stronger for PICEF in general. In the cycle-chain formulation (11), whenever a chain d ∈ D L has at least one attacked vertex, the entire chain breaks down due to Constraint (11c). In that case, this chain d has zero contribution to the right-hand side of Constraint (11b) associated to S. However, for PICEF, with the same attack, the chain up to the first attacked vertex remains. In that case, chain d has a positive contribution to the right-hand side of Constraint (13b). This means that whenever the same feasible solutions S ∈ F G are added to the model, the PICEF-based model will have a value at least as large as the CC-based model for the attack generation problem. As a result, it will often occur that Line 4 is triggered after a smaller number of iterations of the Benders-type algorithm.

Lifting Benders cuts
In this section, we discuss a method to strengthen the constraints of type (11b) and (13b), which we refer to as the Benders constraints. Let us first consider two KEP solutions S, S ∈ F G with S ⊂ S . Then, the Benders constraint related to S is strictly implied by the Benders constraint for S , i.e., if the constraint corresponding to S is violated, so is the constraint corresponding to S . We say the constraint for S lifts the constraint for S. We consider the term lifting here since the cut for S is obtained from the cut for S through lifting the cycle and chain variables x c for c ∈ S \ S. We refer to the book of Conforti et al. (2014) for an extensive survey of different lifting techniques for general mixed-integer programs. The algorithm laid out in the previous section can produce sets S that can still be lifted. Indeed, in the current implementation of the subproblem, R(x, u ), is a maximum weight kidney exchange problem on a subgraph G[V u ], i.e, the graph after removing attacked vertices with respect to u . An optimal solution S to this subproblem thus cannot contain attacked cycles and chains. The solution may be expanded by adding such cycles, and thus lifting the resulting constraint. We explore for both the cycle-chain formulation and PICEF a method for finding lifted cuts through re-weighting the cycles, chains and arcs. The main idea is to identify KEP solutions that maximize the recourse value, given the attack u. Ties are broken by choosing the largest number of cycles, chains, and arcs in the solution. This means that attacked cycles or chains are included if possible, because even though they do not add recourse value, they do increase the number of cycles and chains. We can achieve this goal solving a single KEP on the entire compatibility graph by appropriate re-weightings of all cycles and chains.

Cycle-chain formulation
Let us be given a subset F G ⊂ F G of feasible KEP solutions. In order to obtain stronger cuts for z(F G ,x), we need to make two modifications to R(x, u) defined in (3). First of all, given an attack u ∈ U, let us consider different weightsŵ c (x, u) for each cycle or chain c ∈ C K ∪ D L given bŷ Furthermore, we relax the right hand sides 1 − u j of Constraints (3b) to 1, meaning that we are not restricting a solution to non-attacked cycles and chains anymore. We denote the resulting problem by R lift (x, u).
We can strengthen Benders cuts through solving R lift (x, u), which is proven in the following lemma.
Lemma 6. Let G = (V, A) be a digraph with F G = ∅. Letx ∈ X be an arbitrary initial KEP solution, and u ∈ U an arbitrary attack. Then, for any S ∈ F G that is an optimal recourse KEP solution to R lift (x, u), we have that S = ρ(S , u) is an optimal recourse KEP solution to R(x, u).
Proof. Let z * lift and z * be the optimal objective values to Problems (15) and (3) respectively. Furthermore, let S ∈ F G be any optimal solution to (15). Notice that by the new weightsŵ c (x, u) defined in (14), we have that z * lift > z * |V |, since any feasible solution to (3) is also feasible to (15). We claim now that the remainder S = ρ(S , u) of S under attack u is optimal to (3). Suppose on the contrary S is not optimal for (3), then the objective value of the feasible solution S to (3) is at most z * − 1. Since a feasible KEP solution consists of at most |V | 2 cycles, we get that which contradicts the fact that S is optimal for (15). Therefore, S ∈ F G must be optimal for (3).
Consequently, Lemma 6 shows that the Benders cuts derived from solving R lift (x, u) are at least as strong as those obtained from R(x, u). The difference, however, is that we now allow to find feasible solutions S ∈ F G including attacked cycles and chains c ∈ C K ∪ D L with respect to u, while the solution S = ρ(S , u) is still an optimal solution to the original best recourse problem R(x, u). Since Problems (5) and (15) are both weighted kidney exchange problems, we expect that both can be solved equally efficient, while the latter will in general derive the strongest cuts. Notice that we identify, among all solutions S with remainder S = ρ(S , u) being optimal to R(x, u), the solution containing the largest number of cycles and chains because of the new weightsŵ c (x, u). Such solutions often consist of relatively small cycles and chains, meaning that the remainder of the solution is often larger after an attack u ∈ U is observed, indicating once again the strength of these lifted cuts.

Position-indexed cycle edge formulation (PICEF)
A similar adjustment can be performed on the maximum weight kidney exchange problem based on PICEF to derive stronger cuts (13b). In order to obtain solutions with cycles that are not contained in G[V u ] given an attack u ∈ U, we again need to relax the right-hand sides of constraints, namely constraints (10b) and (10c). The re-weighting of the cycle weights is also similar to that in the Cycle-Chain formulation, (14), i.e.,ŵ The main additional complication here is to assign proper weights to the arc variables. An arc which is not attacked directly may still not contribute to the recourse value, if an arc earlier in the chain is already attacked. An arc weight based simply on the existence in V u thus does not work. To solve this problem, we use two types of arc-variables, ξ u ijl , the traditional binary PICEF variables indicating whether arc (i, j) is used in position l of a chain, and y ij a binary variable indicating whether that arc indeed contributes to the recourse value, i.e. there has not been an attack earlier in the chain that uses this arc (i, j). For the y ij -variables, we introduce weightŝ with w ij (x,ξ) as defined in (8). Lastly, we also assign weightsŵ ij (x,ξ) = 1 |V | to the arc variables ξ ij . The modified model R lift (x,ξ, u) is then given by This model can be explained as follows. In Constraints (18b) and (18c), we again make sure that the recourse KEP solution (x u , ξ u ) is vertex-disjoint. Constraints (18g) tell us that a position indexed arc variable ξ ij with ≥ 2 can only be set to 1 whenever there exists a preceding arc (k, i) going into i at position − 1 such that ξ ki( −1) = 1, since (i, j) needs to be part of a chain starting from an NDD. The remaining constraints deal with the arc variables y ij for each arc (i, j) ∈ A. Constraints (18d) have a similar meaning as Constraints (18g), to make sure the arcs with y ij = 1 indeed induce vertex-disjoint chains. Furthermore, Constraints (18e) make sure that y ij = 0 if either i or j is attacked by u, since then (i, j) is not an arc in G[V u ]. Constraints (18f) imposes that arc variables y ij can only be set to 1 if one of the corresponding position indexed arc variables ξ ij = 1 for ∈ L(i, j). We can once again prove that stronger Benders cuts can be obtained to solving R lift (x,ξ, u) instead of the model in (10).
Lemma 7. Let G = (V, A) be a digraph with F G = ∅. Let (x,ξ) ∈ X and u ∈ U. Then, for any S ∈ F G that is an optimal recourse KEP solution to R lift (x,ξ, u), S = ρ(S , u) is an optimal recourse KEP solution to R(x,ξ, u).
Proof. Let z * lift and z * be the optimal objective values for (18) and (10) respectively. Furthermore, let (x u , y, ξ u ) be any optimal solution to (18) inducing a feasible KEP solution S ∈ F G . Once again, since any feasible solution to (10) can be mapped to a feasible solution to (18), we get z * lift > z * |V | by considering the new weights. Again, we claim that the subsolution S = ρ(S , u) ⊆ S is optimal. By contradiction, suppose it is not optimal, then the objective value corresponding to (x u , y, ξ u ) in (18) is Once again, we have obtained a contradiction, since we assumed S is optimal to (18) with value z * lift > z * |V |. Therefore, S ∈ F G must be optimal to (10). This proves that also with the PICEF reformulation of the attack generation problem A(x,ξ), we can deploy a new formulation for the Benders submodel to obtain Benders cuts that are at least equally strong. In the following section we provide computational experience where we compare our Benders-type approach, including these lifting schemes, to the reference method due to Carvalho et al. (2020).

Computational experience
The aim of this section is to evaluate and compare the performance of our new Benders-type approaches with the branch-and-bound-based approach by Carvalho et al. (2020) on practical instances. To this end, we investigate the following two questions: Q1 Is our new Benders-type approach computationally more efficient than the branch-and-bound-based approach?
Q2 Does the PICEF-based Benders approach dominate the approach based on the cycle-chain formulation or vice versa?
For the sake of brevity, we refer to our approaches using the cycle-chain formulation and the PICE formulation as Benders and Benders PICEF method, respectively. The reference method by Carvalho et al. (2020) is referred to as branch-and-bound method. In the following, we first discuss our computational setup and used test sets in Section 5.1. Afterwards, we present our numerical results in Section 5.2 and discuss the impact of lifting in Section 5.3.

Test sets and computational setup
In our experiments, we have used the same test set as Carvalho et al. (2020), which is publicly available 1 . This test set consists of ninety graphs of which thirty contain 20, 50, and 100 vertices, respectively. More characteristics of these instances can be found in Carvalho et al. (2020). From these graphs, we generate different instances of the full recourse robust kidney exchange problem by bounding the length K and L of the considered cycles and chains, respectively.
To allow for a fair comparison, we have implemented both our new methods and the reference method in C/C++ using the mixed-integer programming framework SCIP 7.0.2 with SoPlex 5.0.2 as LP solver 2 , see Gamrath et al. (2020). All computations were run on a Linux cluster with Intel Xeon E5 3.5 GHz quad core processors and 32 GB memory. The code was executed using a single thread. The time limit of all computations is 1 h per instance.
For both the Benders and branch-and-bound method, we compute all cycles of length at most K and chains of length at most L present in the compatibility graph of an instance, whereas for the Benders PICEF method we just compute all cycles. In all methods, all cycle variables (and, if applicable, all chain or all position indexed arc variables) are added to the initial model. Column generation techniques exist for these models (see Glorie et al. (2014) and  among others), but these are not efficient for the smaller chain and cycle sizes we study ). In the Benders methods, we use the lifting methods as described in Section 4 to separate stronger Benders cuts. We also conducted experiments without lifting, which we will discuss briefly in Section 5.3. Since the Benders approaches with lifting dominate the ones without, we only present numbers for the approaches with lifting in our comparison with the branch-and-bound method for the ease of presentation.
In the branch-and-bound method, there are some degrees of freedom in selecting the branching strategy. To be able to produce results as consistent as possible with the ones described in Carvalho et al. (2020), we have implemented the same strategies as discussed there. A summary of these strategies is given in Appendix A.

Numerical results
To empirically find answers to Questions Q1 and Q2, we have conducted experiments with varying maximum cycle and chain lengths K and L for the compatibility graphs described in Section 5.1. The maximum cycle length in our experiments takes value K ∈ {3, 4}; the maximum chain length is L ∈ {2, 3, 4}. We allow to attack between 1 and 4 vertices per instance in our experiments; attacks of edges are not taken into account, which is consistent with the experiments by Carvalho et al. (2020). In comparison to the experiments described in Carvalho et al. (2020), we consider the impact of varying cycle lengths, while they only considered length K = 3, since multiple European countries allow longer cycles, e.g. Czech Republic and The Netherlands, see Biró et al. (2020). The different chain lengths in our experiments are the same as in Carvalho et al. (2020) (note, however, that they measure the length of a chain by its number of vertices instead of arcs, i.e., the numerical values are shifted by 1 compared to their article). Before we proceed with a discussion of our experiments, we describe the common structure of the presented tables. Column "#vertices" reports on the number of vertices in the tested graphs, whereas column "#opt" provides the number of instances solved within the time limit. The average solution time per instance is given in "time total", whereas "stage 2" and "stage 3" present the average proportion of running time spent in stage 2 and 3, respectively. For the branch-and-bound method, "stage 2" represents the problem of solving the attack generation problem with the branch-and-bound algorithm. For the Benders and Benders PICEF method, "stage 2" and "stage 3" correspond to solving the Benders master problems and the Benders subproblems, respectively. Note that all reported times are in seconds. Column "#att." reports on the average number of generated attacks per solved instance; if no instance from a test set could be solved within the time limit, the corresponding entry is "-". Finally, column "#B&B-nodes" gives the average number of branch-and-bound nodes per optimally solved instance for the branch-and-bound method, and "#sub" shows the average number of subproblems in stage 3 that needed to be solved by the Benders methods for instances that could be solved within the time limit.
All average values are given in arithmetic mean with the only exception being the average solving time, which is measured in shifted geometric mean where we use a shift of s = 10. The reason for the latter is to reduce the impact of outliers and instances with a very small running time.
In our experiments for maximum cycle length K = 3, we observe that all methods can solve all instances based on graphs with 20 vertices within seconds. For graphs with 50 vertices, however, the branch-and-bound method fails to solve all instances for L = 2 and B = 4; for L = 3 and L = 4, it starts encountering problems in solving all instances already if the attack budget B is 3 or 2, respectively. In contrast to this, the Benders approach can solve all instances with up to 50 vertices within the time limit of one hour except for one instance with L = 4 and attack budget B ≥ 3. Benders PICEF is able to solve all instances within the time limit. This is also reflected in the running time of the different methods: the Benders approaches are on average one order of magnitude faster than the branch-and-bound method.
For instances with 100 vertices in the compatibility graph, the branch-and-bound method is hardly able to solve any instance if the attack budget B is at least 3 for L = 2; for increasing chain length, even instances with B ∈ {1, 2} become challenging for the branch-and-bound approach. The Benders approach is much more competitive on these instances as it allows to solve all instances with L = 2 within the time limit, and also for L = 3 it can solve at least half of the instances. If the maximum chain length exceeds 3, however, also the Benders approach fails to solve more than 3 instances per test set. Using the Benders PICEF method, we can solve almost all instances and there is only a small degradation of the number of solved instances if the maximum chain length L is increased.
Based on these experiments, we can answer Question Q1 affirmatively as the Benders approaches are able to consistently solve more instances than the branch-and-bound method within the time limit of one hour, which results in a running time improvement of one order of magnitude for most instance sets. Regarding the comparison of the Benders and the Benders PICEF method, we can observe that for instances with L = 2, the Benders method is superior to the Benders PICEF approach: for 100 vertices and all different attack budgets B ∈ {1, 2, 3, 4}, the Benders method is at least 31.5 % faster than the Benders PICEF approach; for B = 1, it is even 46.9 % faster. For L ≥ 3, however, the picture changes and Benders PICEF is the more competitive method. As already explained above, it is able to solve almost all instances independent from the number of attacks, whereas Benders can hardly solve any instance with 100 vertices. But even if we consider test sets in which both Benders and Benders PICEF can solve almost all instances, Benders PICEF is slightly faster if L = 3. For L = 4 and graphs with 50 vertices, Benders PICEF is between 71.5 % and 84.0 % faster than the Benders method.
Two explanations for this behavior are, first that the number of variables in the cycle-chain formulation depends exponentially on the maximum chain and cycle length, leading to already millions of chains for the graphs in our test set with 100 vertices and L = 4. The impact of the maximum chain length L on the number of variables in PICEF, however, is only linear, which leads to a much more compact model than the cycle-chain formulation. Our experiments show that we can benefit from the smaller formulation already if the chain length L ≥ 2, because the corresponding integer programs can be solved more efficiently. A second reason is the slightly stronger formulation of the attack generation problem using PICEF. In Remark 5, we note that theoretically, the cycle-chain formulation may require more  KEP solutions and thus more iterations of the Benders algorithm to obtain the same result, and this is reflected in our computational results. For almost every setting, more KEP solutions are generated using the cycle-chain formulation. Regarding Question Q2, we thus conclude that for short chains the Benders method dominates the Benders PICEF approach, whereas for L ≥ 3, Benders PICEF is more efficient. These conclusions are also supported by our experiments with maximum cycle length K = 4. For the sake of brevity, we do not report on these numbers in detail and refer the reader to Appendix B for detailed figures.
Since the use of a PICEF-based formulation has a positive impact on the running time of the Benders method for long chains, one might wonder whether the same holds true for the branch-and-bound method. Due to our experiments, this seems to be reasonable, but we expect a branch-and-bound method to still be significantly slower than the PICEF Benders method, even when its implementation uses PICEF. First, we note that the branch-and-bound method needs more time to generate a single attack using the same underlying formulation. This effect is the most apparent for the instances with 100 vertices. For example, for L = 3 and B = 2 on graphs with 50 vertices, the average time per attack is 10.7 s for the branch-and-bound method and 4.7 s for the Benders method. Moreover, the branch-and-bound approach generates more attacks than the Benders-type approach for the cycle-chain formulation. While, as we have shown, the PICEF reduced the numbers of attacks required for the Benders-type approach, there is no reason to expect this in the branch-and-bound framework.
Remark 8. When comparing the number of generated attacks for the branch-and-bound method with the numbers reported by Carvalho et al. (2020), we observe that our numbers are higher in general. Although we tried to implement the method as close as possible to the implementation of Carvalho et al. (2020), cf. Appendix A, there are still factors that might negatively impact the number of generated attacks in our implementation. Among others, the order of cycles/chains might be different in the two implementations, which might cause to find different optimal solutions in each iteration, and the MIP solver used in our experiments is different to the one used by Carvalho et al. (2020). Thus, since these factors impact both the branch-and-bound and Benders models equally, our implementation does not give an advantage to either of these methods.

Evaluation of the impact of lifting
As mentioned above, we have also conducted experiments to measure the impact on the Benders approaches of the lifting schemes proposed in Section 4. Table 2 and Table 3 show aggregated information for graphs of different sizes using the Benders and Benders PICEF approach, respectively. Again, the attack budgets B from 1 to 4 are used. The aggregated numbers are average values of the numbers provided in the detailed tables of these experiments, which can be found in Appendix C.
For both approaches, we can see that lifting has a positive impact on the performances of the Benders approaches. While the number of generated attacks per optimally solved instance is roughly the same, the number of subproblems that need to be solved is significantly smaller in the approaches making use of the lifting technique. This is reflected in the running time, which is much smaller if lifting is enabled. Thus, also more instances can be solved. Since a fair comparison of these numbers is only possible if the number of solved instanced is almost the same for the methods to be compared, we report in the following only on more detailed numbers for graphs with at most 50 vertices. Before presenting these For instances with 20 vertices, there is almost no difference for the running time if lifting is enabled or not. For graphs with 50 vertices, however, the number of solved subproblems for the Benders method using lifting is roughly 50 % smaller than without lifting. This leads to a running time reduction of about 25 % for L ∈ {3, 4} and 43.2 % for L = 2. For the Benders PICEF method, we can observe a similar trend, which is even slightly stronger. Here, lifting leads to a running time improvement between 50.4 % and 59.9 % for graphs with 50 vertices, and the number of generated attacks reduces by 62.6 %-67.5 %.
We conclude that lifting is an important component for obtaining a performant Benders method.

Conclusion
In this paper, we investigate a robust optimization variant of the kidney exchange problem, based on the fact that donors might decide to opt out of the program after exchanges are proposed but before transplants take place. This is a practical issue, since donors and pairs leaving a kidney exchange program leads to broken cycles and chains of initially proposed transplants. We propose a Benders decomposition algorithm for solving the attack generation problem based on the cycle-chain formulation and the position-indexed chain-edge formulation. The algorithms are based on a reformulation of the attack generation algorithm with constraints for any feasible KEP solution. Initially, the Benders master problem takes into account a small number of feasible KEP solutions, and new KEP solutions are added by the Benders submodel through solving a weighted kidney exchange problem on an induced subgraph after observing which donors have left the program. The idea of using Benders decomposition is intuitive, since the variables used in the reformulation are decoupled whenever a set of leaving donors is fixed. Furthermore, a lifting technique is deployed to obtain solutions on the entire compatibility graph that still have maximum recourse value on the non-attacked cycles and chains.
Our computational results show that the Benders decomposition algorithm outperforms the state-ofthe-art, which is a branch-and-bound type algorithm proposed in Carvalho et al. (2020), when we consider benchmark instances with |V | ≥ 50. We observe a transition phase between the Benders methods based on CC and PICEF. Whenever we allow only small chains, i.e., L = 2, the CC-based implementation outperforms the PICEF-based implementation, since the number of chain variables is then often smaller than the number of position-indexed arc variables. However, when larger chains are allowed, i.e., L ≥ 3, the PICEF-based implementation becomes the significantly more competitive method and the benefit of having a polynomial-size formulation in terms of chains becomes really apparent. Enabling the lifting technique leads, under all chosen sets of parameters, to a significant reduction in the running time since fewer cuts need to be generated in the last iteration of the iterative algorithm for solving the large-scale mixed integer programming model of the robust optimization problem. Since the stronger Benders cuts give better feedback on the recourse value that can be realized given an attack, we need fewer attacks to solve the robust optimization model to optimality. This also reflects in an increased number of instances that can be solved within the time limit.
Extending this work to a setting with a less restricted uncertainty set will give more insight in how to incorporate the possibility of donor or transplant failure in a more realistic setting, since one cannot predict in advance the number of donors that leave the KEP. A more sophisticated data analysis of the physiological properties of donors and recipients may be necessary to find an uncertainty set that more accurately approximates the real set of attacks that may occur.
Line 9: Fill for maximal attack When choosing the maximal attack, we add vertices to be attacked sequentially. For each new node, we first identify the highest weight cycle or chain for which no vertices are attacked yet, and for which there is a vertex that is still unfixed. Ties between cycles and chains are broken arbitrarily. For this cycle or chain, we add the lowest index vertex to the attack. If no such cycles or chains exist, i.e., at least one vertex is already attacked, or all vertices are fixed to be attacked or not attacked, we add the lowest index vertex that is not yet fixed to the attack.
Line 25: Branching We choose the first vertex we added to the attack to branch on.

B Numerical results for cycle length 4
In the main part of this article, we have discussed the results of our experiments for instances with cycles of length at most 3. This appendix provides a summary of our experiments for the same compatibility graphs and maximum cycle length 4 in Table 4.

C Detailed results for comparing the effect of lifting
In Section 5.3, we have provided aggregated numbers to compare the impact of lifting on the Bendersbased approaches. Tables 5 and 6 provide detailed statistics for the Benders and Benders PICEF, respectively.