text:
\section{Introduction}
\label{Introduction}

Kidney paired donation programs (KPDPs) across the globe have facilitated living donor kidney transplants for patients experiencing renal failure who have a willing yet incompatible or sub-optimal donor. A patient in need of a kidney transplant registers along with their incompatible donor (paired donor) in a KPDP\ as a pair, and that patient receives a compatible kidney from either the paired donor in another pair---who in turn receives a kidney from another donor, or from a singleton donor who does not expect a kidney in return (a.k.a.\ non-directed donor). The transplants are then made possible through the exchange of paired donors between patient-donor pairs. Since first discussed by \cite{Rapaport1986}, and put in practice for the first time in South Korea \citep{Park1999}, kidney exchanges performed through KPDPs\ have been introduced in several countries around the world, e.g., the United States \citep{Saidman2006}, the United Kingdom \citep{Manlove2015}, Canada \citep{CaKEPFoundations} and Australia \citep{AustraliaKPD}, and the underlying matching of patients to donors has been the subject of study from multiple disciplines (see, e.g., \citet{Roth2005,Dickerson2016, Dickerson2019,Carvalho2020, Riascos2020}).
Despite this attention, kidney exchange still faces challenges from both a practical and a theoretical point of view \citep{Ashlagi2021}.
In this work, motivated by the high rate of exchanges that do not proceed to transplant \citep{Bray2015, Dickerson2016, CBS2019}, we provide a robust optimization methodological framework that proposes a set of exchanges for transplant, observes failures in the transplant plan, and then repairs the affected exchanges provided that a recovering rule (i.e., \textit{recourse policy}) is given by KPDP\ operators.

Kidney exchange, or the kidney exchange problem as it is known in the literature, can be modeled in a compatibility graph, i.e., a digraph whose vertices represent either a pair or a singleton donor and arcs indicate that the donor in the starting vertex is blood type and tissue type compatible with the patient in the ending vertex. Arcs can have an associated weight that represents the importance/priority of that transplant. Exchanges then take the form of simple cycles and simple paths (a.k.a.\ chains).

Cycles consist of patient-donor pairs exchanges only, whereas in a chain, the first donation occurs from a singleton donor to a patient-donor pair and then is followed by a sequence of donations from a paired donor to the patient in the next patient-donor pair. It is standard practice to perform cyclic transplants simultaneously and limit their length due to the logistical implications of arranging operating rooms and surgical teams. Although the size of chains can be unbounded and theoretically infinite \citep{Ashlagi2012, Anderson2015,Ding2018,Dickerson2019} by allowing the donor in the last pair of a chain to become a \textit{bridge donor}, i.e., a paired donor that acts as a singleton donor in a future algorithmic matching, it is also a common practice to limit the size of chains
\citep{Biro2009, CBS2019, Carvalho2020}, in light of potential fallbacks and greater opportunity for late-detected incompatibilities \citep{Biro2009, Carvalho2020}. In that case, the donor in the last pair donates to a patient on the deceased donor's waiting list, ``closing up'' a chain.

Operational and technological limitations bring uncertainty to the existence of vertices and arcs in the compatibility graph when exchanges go through a final checking process before nephrectomies take place. Permanent or temporary withdrawals can also happen at any stage of the kidney exchange process. The availability of a patient or donor, just like the actual compatibility of an exchange, is confirmed only when a set of transplants has already been selected. This phenomenon is explained by changes/lack of accuracy on the ``believed'' information KPDP\ operators rely on when building the compatibility graph. There are multiple reasons a pair/singleton donor selected for transplant may not be available, e.g., match offer rejection, already transplanted out of the KPDP, illness, pregnancy, reneging, etc. Thus, even if some of this information is captured prior to the matching, there is still a chance of a subsequent fallback. Additionally, tissue type compatibility is not known with certainty when the compatibility graph is built, unlike blood type compatibility. Tissue type compatibility is based on the result of a \textit{virtual crossmatch test}, which typically has lower accuracy compared to a \textit{physical crossmatch test}. Both tests try to determine if there are antibodies of importance in a patient that can lead to the rejection of a potential donor's kidney. Physical crossmatch tests are challenging to perform, making them impractical and unlikely to be performed in real life between all patients and donors \citep{Carvalho2020}. Then, at a first stage, a ``believed'' compatibility graph is built according to the results of the virtual crossmatch test and once the set of transplants has been proposed, those exchanges undergo a physical crossmatch test to confirm or rule out the viability of the transplants. After confirming infeasible transplants and depending on KPDPs' regulations, KPDP\ operators may attempt to repair the originally planned cycles and chains impacted by the non-existence of a vertex or an arc. {We refer to these impacted cycles and chains as \textit{failed} cycles and chains. While a cycle fails completely by the failure of any of its elements (vertices or arcs), a chain is cut short at the pair preceding the first failed transplant.}

Failures in the graph, caused by the disappearance of a vertex or arc have a significant impact on the number of exchanges that actually proceed to transplant \citep{Dickerson2019,CBS2019} and can even drive KPDP\ regulations \citep{Carvalho2020}. For instance, \cite{Dickerson2019} reported that for selected transplants from the UNOS program between 2010--2012, 93\% did not proceed to transplant. Of those non-successful transplants, 44\% had a failure reason (e.g., failed physical crossmatch result or patient/donor drop-out), which in turn caused the cancellation of the other 49\% of non-successful transplants. In Canada, between 2009--2018, 62\% of cycles and chains with six transplants failed, among which only 10\% could be repaired. Half the cycles and chains with three or fewer transplants were successful, and approximately 30\% of the total could not proceed to transplant \citep{CBS2019}.

The set of transplants that is repaired by KPDPs\ is planned without accounting for subsequent failures and thus, a sub-optimal outcome on the number of successful transplants is obtained. A large body of work has been concerned with maximizing the expectation of the proposed transplants \citep{Awasti2009, Dickerson2014, Dickerson2019, Klimentova2016, Smeulders2022}. From a practical perspective, maximizing expectation could increase the number of planned exchanges that become actual transplants. However, an underlying concern is that such an objective could benefit patients that are likely to be compatible with multiple donors at the risk of disadvantaging highly-sensitized patients, i.e., patients for whom a few kidney donors are available and whose associated exchanges tend to fail at a higher rate compared to non-sensitized patients. Furthermore, real data is limited and there is not yet enough understanding on how to characterize the dynamics between patients and donors to derive a probability distribution of failures that could be generalized to most KPDPs.
With these considerations in mind, we model failure through an uncertainty set that does not target patient sensitization level nor probabilistic knowledge, and aim to find a set of transplants that allows the biggest recovery under the worst-case failure scenario in the uncertainty set.

We therefore develop a two-stage robust optimization (RO) 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. We extend the current state-of-the-art RO methodologies \citep{Carvalho2020} by considering that the failure rate of vertices and arcs is non-homogeneous---since failure reasons, such as a late-detected incompatibility, seem to be independent from patient/donor fallback and vice versa---and also considering the impact of scarce match possibilities for highly-sensitized patients. The contributions of this work are as follows:
\begin{enumerate}
    \item We study a two-stage RO framework with non-homogeneous failure between vertices and arcs.
    \item We present a novel general solution framework for any recourse policy whose recourse solution set is finite upon selection of a first-stage set of transplants.
    \item We introduce for the first time two feasibility-seeking reformulations of the second stage as opposed to optimality-based formulations \citep{Carvalho2020, Blom2021}. The number of decision variables grows linearly with the size of vertices and arcs. This greater scalability, however, comes at the price of the lack of a lower bound. We derive dominating scenarios and explore several second-stage solution algorithms to overcome the drawbacks and exploit the advantages.
    \item We compare our framework to state-of-the-art algorithms and find significant computational and solution quality improvements.
\end{enumerate}

The remainder of the paper is organized as follows. Section \ref{LitReview} presents a collection of related works. Section \ref{Preliminaries} establishes the problem we address. Sections \ref{RobustModels} and \ref{SecondStage} present the first- and second-stage formulations, respectively. Section \ref{sec:HSAs} presents the full algorithmic framework. Section \ref{Experiments} shows computational results. Lastly, Section \ref{sec:Conclusion} draws some conclusions and states a path for future work.

\section{Related Work}
\label{LitReview}

\cite{Abraham2007} and \cite{Roth2007} introduced the first KPDP\ mixed-integer programming (MIP) formulations to maximize the number/weighted sum of exchanges, namely, the well-known and denominated \textit{edge formulation} and the  \textit{cycle formulation}. The edge formulation uses arcs in the input graph to index decision variables; whereas the cycle formulation, which was initially proposed for cycles only, has a decision variable for every feasible cycle and chain in the input graph. Although both formulations are of exponential size either in the number of constraints (edge formulation) or in the number of decision variables (cycle formulation), the cycle formulation, along with a subsequent formulation proposed by \cite{Dickerson2016}, is the MIP formulation with the strongest linear relaxation. Due to its strength and natural adaptability, multiple works have designed branch-and-price algorithms employing the cycle formulation. The branch-and-price algorithm proposed in \citep{Abraham2007} was effective for cycles of size up to three. \cite{Lam2020} solved the problem for long cycles. \cite{Riascos2020} used decision diagrams to solve the pricing problems and for the first time their branch-and-price addresses both long cycles and long chains, and it is able to scale successfully for even the largest instances in the PrefLib library \citep{Mattei2013}. More recently, \cite{Omer2022} built up on the work in \citep{Riascos2020} by implementing a branch-and-price able to solve remarkably large instances (10000 pairs and 1000 altruists).

Another trend has focused on new arc-based formulations
   (e.g., \cite{Constantino2013,Dickerson2016}) and arc-and-cycle-based formulations (e.g., \cite{Anderson2015, Dickerson2016}). Among these two approaches, arc-and-cycle-based formulations seem to outperform arc-based formulations \citep{Dickerson2016}, especially when allowing up to three exchanges in a cycle.

The previously discussed studies do not consider uncertainty in the proposed exchanges. However, the percentage of planned transplants that end up cancelled suggests a need to plan for uncertainty. There are two sources of uncertainty that have been studied in the literature: weight accuracy (e.g., \cite{Duncan2019}) and vertex/arc existence (e.g., \cite{Dickerson2016, Klimentova2016, Duncan2019, Carvalho2020, Smeulders2022}). Weight accuracy uncertainty considers that the associated social benefit (weight) associated to an exchange can vary, e.g., due to changes in a patient's health condition or from the result of multiple opinions of policy makers on the priority that should be given to a patient with respect to others \citep{Duncan2019}. Uncertainty in the existence of a vertex/arc, e.g., whether or not a patient or donor leaves the KPDP\ or compatibility between a patient and donor changes, has received greater attention. There are three main approaches in the literature when considering vertex or arc existence as the source of uncertainty: (1) a maximum expected value approach; (2) an identification of exchanges for which a physical crossmatch test should be performed to maximize the expected number of realized transplants; and (3) a maximization of the number of transplants under the worst-case disruption of vertices and arcs; which are explained in detail in what follows.

    The maximum expected value approach is the approach most investigated in the literature. It is concerned with finding the set of transplants with maximum expected value, i.e., a set of transplants that is most likely to yield the maximum number or maximum weighted sum of exchanges given some vertex/arc failure probabilities. This approach has been mostly modeled as a deterministic  KEP, where the objective function approximates the expected value of a matching using the given probabilities as objective coefficient multipliers of deterministic decisions.
    \cite{Awasti2009} considered the failure of vertices in an online setting of the cycle-only version for cycles with at most three exchanges. The authors generate sample trajectories on the arrival of patients/donors and patients survival, then use a REGRETS algorithm as a general framework to approximate the collection of cycles with maximum expectation. \cite{Dickerson2012} proposed a heuristic method to learn the ``potential'' of structural elements (e.g. vertex), which quantifies the future expected usefulness of that element in a changing graph with new patient/donor arrivals and departures.  \cite{Dickerson2013} considered arc failure probabilities and found a matching with maximum expected value, but solution repairs are not considered in case of failure. Following the same motivation, an extension of this work is in \citep{Dickerson2019}. \cite{Klimentova2016} studied the problem of computing the expected number of transplants for the cycle-only version while considering \textit{internal} recourse and \textit{subset} recourse to recover a solution in case of vertex or arc failure. Internal recourse, also known as \textit{back-arcs recourse} (e.g., \cite{Carvalho2020}) allows surviving pairs to match among themselves, whereas subset recourse allows a wider subset of vertices to participate in the repaired solution. To compute the expectation, an enumeration tree is used for all possible failure patterns in a cycle and its extended subset, consisting of the additional vertices (for the subset recourse only) with which the pairs in the original cycle can form feasible cycles. To reasonably limit the size of the tree, the subset recourse is limited to a small subset of extra vertices and the internal recourse seemed to scale for short cycles only. \cite{Alvelos2019} proposed to find the expected value for the cycle-only version while considering internal recourse through a branch-and-price algorithm, finding that the overall run time grew rapidly with the size of the cycles.

 To identify exchanges where a physical crossmatch test should be performed, \cite{Blum2013} modeled the KEP in an undirected graph representing pairwise exchanges only. They proposed to perform two physical crossmatch tests per patient-donor pair---one for every arc in a cycle of size two---before exchanges are selected with the goal of maximizing the expected number of transplants. They showed that their algorithm yields near-optimal solutions in polynomial time. Subsequent works \citep{Assadi2019,Blum2020} evaluated adaptive and non-adaptive policies to query edges in the graph. In the same spirit, but now for the general kidney exchange problem (with directed cycles and chains), \cite{Smeulders2022} formulated the maximization of the expected number of transplants as a two-stage stochastic integer programming problem considering a limited budget on the number of arcs that can be tested in the first stage. Despite the different algorithmic approaches that were proposed, scalability is still challenging.

In addressing worst-case vertex/arc disruption, \cite{Duncan2019} found robust solutions with no recourse considering a budget failure on the number of arcs that fail in the graph. \cite{Carvalho2020} proposed a two-stage robust optimization model that allowed recovery of failed solutions through the back-arcs recourse and the full recourse policies. The latter can be seen as a subset recourse policy (e.g., \cite{Klimentova2016}), in which all vertices that were not selected in the matching can be included in the repaired solution. Unlike our work, vertex and arc failure are treated as homogeneous, i.e., both elements can fail with the same probability. Since in homogeneous failure there is a worst-case scenario in which all failures are vertex failures, the recourse policies are evaluated under vertex failure only. The back-arcs recourse policy only scales for instances with 20 vertices, whereas the full-recourse policy scales for instances up to 50 vertices. \citet{Blom2021} examined the general robust model for the full-recourse policy studied in \citet{Carvalho2020} and showed its structure to be a defender-attacker-defender model. Two Benders-type approaches are proposed and tested using the same instances from \citet{Carvalho2020}. The Benders-type approaches showed improved performance over the branch-and-bound proposed by \citet{Carvalho2020}. This approach, however, is limited to homogeneous failure for the full-recourse policy. In this work, we allow for different failure rates between vertices and arcs, and present a solution scheme that can address recourse policies whose recourse solution set corresponds to a subset of the feasible cycles and chains in the compatibility graph, e.g., the full recourse, the back-arcs recourse and a new recourse policy introduced later on. Our solution method does require a robust MIP formulation adapted to a specific policy that can be solved iteratively as new failure scenarios are added. The second-stage problem is decomposed into a master problem and a subproblem. The master problem is formulated as the same feasibility problem regardless of the policy but it is implicit in the constraint set, whereas the subproblem (i.e., recourse problem) corresponds to a deterministic KEP where only non-failed cycles and chains contribute to the robust objective.

\section{Preliminaries}
\label{Preliminaries}

In this section, we describe the two-stage robust model we study. We start by formally describing the first-stage problem. Particularly, we define the compatibility graph and the feasible set for the first-stage decisions. We proceed in a similar way for the second-stage problem and then introduce the two-stage robust problem addressed in this paper. Lastly, we define the uncertainty set and the recourse policies study in this work.

\paragraph{First-stage compatibility graph.} The KEP can be defined on a directed graph $\graph = (\vertexSet, \arcSet)$, whose vertex set $V := P \cup N$ represents the set of patient-donor pairs, $P$, and the set of singleton donors $N$. From this point onward, we will refer to patient-donor pairs simply as \emph{pairs}. The arc set $A \subseteq V \times P$ contains arc $(\vertexa,\vertexb)$ if and only if the donor in vertex $u \in V$ is compatible with patient in vertex $v \in P$.
A matching of donors and patients in the KEP can take the form of simple cycles and simple chains (i.e., paths from the digraph).
A cycle is feasible if it has no more than $K$ arcs, whereas a chain is feasible if it has no more than $L$ arcs ($L + 1$ vertices) and starts with a singleton donor.
The set of feasible cycles and chains is denoted by $\mathcal{C}_{\cycleCap}$ and $\mathcal{C}_{\chainCap}$, respectively. Furthermore, let $V(\cdot)$ and $A(\cdot)$ be the set of vertices and arcs in $(\cdot)$.

\paragraph{Feasible set of first-stage decisions.} A feasible solution to the KEP corresponds to a collection of vertex-disjoint feasible cycles and chains, referred to as a \emph{matching}\footnote{Note that since each vertex in the KEP compatibility graph corresponds to a patient-donor pair or a singleton donor, a KEP matching---which is referred to as a matching in the literature and in this paper---is not actually a matching of the digraph, rather a collection of simple cycles and paths of the digraph which leads to an actual underlying 1-1 matching of selected donors and patients.}, i.e., $M \subseteq \mathcal{C}_{\cycleCap} \cup \mathcal{C}_{\chainCap}$ such that $V(c) \cap V(c^{\prime}) = \emptyset,$ for all $c, c^{\prime} \in M$ with $c \ne c^{\prime}$.
We let $\matchSet_D$ denote the set of all KEP matchings in graph $D$. Also, we define
$$
\mathcal{X} := \{\bm{x_{\matchSet}}: M \in \matchSet_D \},
$$
as the set of all binary vectors representing the selection of a feasible set of transplants, where $\bm{x_{\matchSet}}$ is the characteristic vector of matching $M$ in terms of the cycles/chains sets $\mathcal{C}_{\cycleCap} \cup \mathcal{C}_{\chainCap}$. That is, $\bm{x_{\matchSet}} \in \{0,1\}^{\mid \mathcal{C}_{\cycleCap} \cup \mathcal{C}_{\chainCap} \mid}$
with $x_{M,c} = 1$  if and only if $c \in M$, meaning that a patient in a pair obtains a transplant if it is the start or terminal vertex of an arc $a \in A(c)$ in some cycle/chain $c$ selected in matching  $M$.

\paragraph{Second-stage compatibility graph.}
Once a failure scenario $\bm{\oneCeS} \in \Gamma$ affecting solution $\varFirstPlain \in \mathcal{X}$ is observed, a digraph $D^{\pi}(\varFirstPlain, \bm{\oneCeS})$ for the second-stage problem is such that its  vertices and arcs do not fail under scenario $\bm{\oneCeS}$ and whose set of feasible cycles $\cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \subseteq \mathcal{C}_{\cycleCap}$ and set of feasible chains $\chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \subseteq \mathcal{C}_{\chainCap}$ are (i) \textit{allowed} under recourse policy $\pi \in \Pi$ and (ii) have \textit{at least one pair} in $\varFirstPlain$. We detail on the uncertainty set  $\Gamma$ and the types of recourse policies $\Pi$ in Sections \ref{subsec:uncertaintyset} and \ref{sec:RecoursePolicies}, respectively.

\paragraph{Feasible set of second-stage decisions.}
A solution to the second stage is referred to as a \textit{recourse solution} in $D^{\pi}(\varFirstPlain, \bm{\oneCeS})$ under some scenario $\bm{\oneCeS} \in \Gamma$, leading to an alternative matching where pairs from the first-stage solution $\varFirstPlain \in \mathcal{X}$ are re-arranged into non-failed cycles and chains, among those allowed under policy $\pi \in \Pi$.
We can now define $\matchSet^{\policy}(\varFirst, \oneCe):= \{M \subseteq \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \mid V(c) \cap V(c^{\prime}) = \emptyset \text{ for all } c, c^{\prime} \in M \text{; } c \neq c^{\prime}\}$ as the set of allowed recovering matchings under policy $\pi$ such that every cycle/chain in  $\matchSet^{\policy}(\varFirst, \oneCe)$ contains at least one pair in $\varFirstPlain$.

Thus, let
$$
\setRecoSym^{\policy}(\varFirst, \oneCe):= \{\bm{y_{\matchSet}}:M \in \matchSet^{\policy}(\varFirst, \oneCe) \}
$$
be the set of all binary vectors representing the selection of a feasible set of transplants with non-failed elements (vertices/arcs), under scenario $\bm{\oneCeS} \in \Gamma$ and policy $\pi \in \Pi$ that contain at least one  pair in $\varFirstPlain$.
Likewise, $\bm{y_{\matchSet}}$ is the second-stage counterpart of the characteristic vector $\bm{x_{\matchSet}}$ in terms of the cycle and chain sets $\cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS})$ and $\chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS})$, respectively.

\paragraph{Two-stage RO problem.}

A general two-stage RO problem for the KEP can then be defined as follows:
\begin{align}
	\label{ROmodel0}
	\max_{\varFirstPlain \in \mathcal{X}} \min_{\bm{\oneCeS} \in \Gamma} \max_{\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)} f(\varFirstPlain,\mathbf{y})&
\end{align}

\noindent i.e., a set of transplants given by solution $\varFirstPlain \in \mathcal{X}$ is selected in the first stage. Then, the uncertainty vector $\bm{\oneCeS} \in \Gamma$ is observed and a recourse solution $\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)$ is found to repair $\varFirstPlain$ according to recourse policy $\pi \in \Pi$. The second stage, established by the min-max problem, finds a recourse solution by solving the recourse problem (third optimization problem), whose objective value maximizes $f(\varFirstPlain,\mathbf{y})$ under failure scenario $\bm{\oneCeS} \in \Gamma$ but it is the lowest among all failure scenarios. The scenario optimizing the second-stage problem is then referred to as the worst-case scenario for solution $\varFirstPlain \in \mathcal{X}$.
The recourse objective function, $f(\varFirstPlain,\mathbf{y})$, assigns weights to the cycles and chains of a recovered matching, associated to a recourse solution $\mathbf{y}$, based on its property with respect to $\varFirstPlain$.  Thus, we define $f(\varFirstPlain,\mathbf{y})$ as $\mathbf{w}(\varFirst)^{\top}\mathbf{y} = \sum_{c \in \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS})} \mathbf{w}_{c}(\varFirstPlain) \mathbf{y}_{c}$ in Model \ref{ROmodel0}, where $\mathbf{w}_{c}(\varFirstPlain) = \sum_{u \in  V(c) \cap  V(\varFirstPlain) \cap P} \mathbf{y}_{c}$ is the weight of a cycle/chain $c \in \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS})$ corresponding to the \textit{number of pairs} that having been matched in the first stage by solution $\varFirstPlain \in \mathcal{X}$ can also be matched in the second stage by recourse solution $\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)$, after failures are observed. As a result, the weight of every cycle and chain selected by $\mathbf{y}$ corresponds to the number of  pairs from the first-stage solution $\varFirstPlain$ that are also present in that cycle/chain. An optimal KEP robust solution corresponds to a feasible set of transplants in the first stage, among all solutions $\varFirstPlain \in \mathcal{X}$, whose best recovery plan has the lowest number of pairs that can be matched in the second stage.

Thus, the two-stage RO problem we study for the KEP can be defined as follows:
\begin{align}
	\label{ROmodel}
	\max_{\varFirstPlain \in \mathcal{X}} \min_{\bm{\oneCeS} \in \Gamma} \max_{\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)} \weightRO\varReco&
\end{align}

\subsection{Uncertainty set}
\label{subsec:uncertaintyset}
Failures in a planned matching are observed after a final checking process. Failure reasons can include illness, late-detected incompatibilities, match offer rejection by a recipient, patient/donor dropout, etc. Theses failure reasons can then lead to the removal of the affected vertices and arcs from the first-stage compatibility graph. The failure of a vertex/arc causes the failure of the entire cycle that element belongs to and the shortening of a chain right at the last vertex before the first failure.
In the literature, the uncertainty set has been defined as a polyhedron where vertices and arcs in the compatibility graph can fail at the same rate (homogeneously), and the total failures for both vertices and arcs are bounded by a predefined integer value  \citep{Blom2021, Carvalho2020}. In \textit{homogeneous failure}, there is no need to consider arc failures since there exists a worst-case scenario where all failures are vertex failures \citep{Carvalho2020}. We consider \textit{non-homogeneous failure} by allowing vertices and arcs fail at different rates, as such, we define two failure budgets, one for vertices and another for arcs. In other words, we are assuming that there exists two unknown probability distributions causing vertices and arcs to fail independently from one another, rather than assuming that both vertices and arcs follow the same failure probability distribution. This approach, however, can still model homogeneous failure since it suffices to consider only vertex failures.

After having selected a set of transplants but before the uncertainty is revealed, there exists a transitory compatibility graph $D^{\pi}(\varFirstPlain) = (V^{\pi}_{\varFirstPlain}, A^{\pi}_{\varFirstPlain})$ with the same properties as the second-stage compatibiblity graph $D^{\pi}(\varFirstPlain, \bm{\oneCeS}) = (V^{\pi}_{\varFirstPlain, \bm{\oneCeS}}, A^{\pi}_{\varFirstPlain, \bm{\oneCeS}})$, except that no failures are yet observed and thus $\lvert V^{\pi}_{\varFirstPlain} \rvert \ge \lvert V^{\pi}_{\varFirstPlain, \bm{\oneCeS}} \rvert$ and  $\lvert A^{\pi}_{\varFirstPlain} \rvert \ge \lvert A^{\pi}_{\varFirstPlain, \bm{\oneCeS}} \rvert$. Thus, we define an uncertainty set $\bm{\Gamma}$ in terms of  all the uncertainty sets $\bm{\Gamma}(\varFirstPlain)$ leading to a second-stage compatibility graph as follows:
\begin{subequations}
\label{UDef}
\begin{align}
\bm{\Gamma}(\varFirstPlain) &:= \left(\bm{\bigsCe^{\text{v}}}(\varFirstPlain), \bm{\bigsCe^{\text{a}}}(\varFirstPlain)\right) \text{ where,}\\
\bm{\bigsCe^{\text{v}}}(\varFirstPlain)  &:=\{\bm{\gamma^{\text{v}}} \in \{0,1\} ^{\midV \mid }\mid  \lvert V^{\pi}_{\varFirstPlain} \rvert - \lvert V^{\pi}_{\varFirstPlain, \bm{\oneCeS}} \rvert \le \sum_{u \in V} \gamma^{\text{v}}_{u} \le r^{\text{v}}\}\\
\bm{\bigsCe^{\text{a}}}(\varFirstPlain)  &:= \{\bm{\gamma^{\text{a}}} \in \{0,1\} ^{\mid A \mid}\mid  \lvert A^{\pi}_{\varFirstPlain} \rvert - \lvert A^{\pi}_{\varFirstPlain, \bm{\oneCeS}} \rvert \le \sum_{(\vertexa,\vertexb) \in A} \gamma^{\text{a}}_{\vertexa\vertexb} \le r^{\text{a}}  \}\\
\bm{\Gamma} &:= \bigcup\limits_{\varFirstPlain \in \mathcal{X}} \bm{\Gamma}(\varFirstPlain)
\end{align}
\end{subequations}

A failure scenario $\bm{\oneCeS} = (\gamma^{\text{v}}, \gamma^{\text{a}})$ is represented by binary vectors $\gamma^{\text{v}}$ and $\gamma^{\text{a}}$. A vertex $u \in V$ and  arc $(\vertexa,\vertexb) \in A$ from the first-stage compatibility graph fail under a realized scenario if $\gamma^{\text{v}}_{u} = 1$ and $\gamma^{\text{a}}_{\vertexa\vertexb} = 1$, respectively. The total number of vertex and arc failures in the first-stage compatibility graph is controlled by parameters $r^{\text{v}}$ and $r^{\text{a}}$, respectively. Therefore, the number of vertex failures in the transitory compatibility graph $D^{\pi}(\varFirstPlain)$ leading to a second-stage compatibility graph  $D^{\pi}(\varFirstPlain, \bm{\oneCeS})$ cannot exceed $r^{\text{v}}$. Likewise, the number of arc failures in $D^{\pi}(\varFirstPlain)$ cannot exceed $r^{\text{a}}$. Thus, the uncertainty set $\Gamma$ is the union over all failure scenarios leading to a second-stage compatibility graph when a set of transplants in the first stage has been proposed for transplant.
Note that this uncertainty set definition only distinguishes failures by element type (vertex or arc), which gives equal chances of failure and thus success to both non sensitized and sensitized patients.

\subsection{Recourse policies}
\label{sec:RecoursePolicies}
An important consideration made by KPDPs is the guideline according to which a selected matching is allowed to be repaired. Although, re-optimizing the deterministic KEP with non-failed vertices/arcs is an alternative \citep{Dutch2005}, some KPDPs opt for recovery strategies when failures in the matching given by the deterministic model are observed \citep{CBS2019, Manlove2015}. Thus, it is reasonable to use those strategies as recourse policies when uncertainty is considered. We consider the \textit{full-recourse policy} studied in \citep{Blom2021, Carvalho2020} and introduce a natural extension of this policy, that we refer to as \textit{the first-stage-only recourse policy}.

\subsubsection{Full recourse}
Under the full-recourse policy, pairs that were selected in the first stage but belong to failed components, are allowed to be re-arranged in the second stage within non-failed cycles and chains that may involve any other vertex (pair or singleton donor), regardless of whether that vertex was selected or not in the first stage. Figure \ref{fig:FullRecourse} shows an example of the full-recourse policy. The first stage solution depicted with bold arcs has a total weight of eight, since there are eight exchanges. Suppose there is a scenario in which $\gamma^{\text{v}}_{2} = 1$ and $\gamma^{\text{a}}_{56} = 1$. Assuming that $K = L = 4$, then the best recovery plan under this scenario, depicted by the recourse solution with shaded arcs, is to re-arrange vertices 3, 4 and 6 by bringing them together into a new cycle and include vertices 1 and 5 in a chain started by singleton donor 8, which was not selected in the first stage. Alternatively, vertices 1 and 5 could have been selected along with vertex 7 to form a cycle. In both cases, the recourse solution involves only five pairs from the first stage.

\input{Figures/RO_FullRecourse}

\subsubsection{First-stage-only recourse}

We refer to the first-stage-only, as a recourse policy in which only vertices selected in the first stage can be used to repair a first-stage solution, i.e., the new non-failed cycles and chains selected in the second stage, must include vertices from that first-stage solution only. It is easy to see that the recourse solution set of the first-stage-only recourse policy corresponds to a subset of that of the full recourse. Although more conservative, KPDPs can opt for the first-stage-only since in the full recourse there can be vertices selected in the second stage that were not selected in the first stage, and thus, have never been checked before by KPDP operators, adding uncertainty on the actual presence of vertices on a recourse solution under full recourse. The back-arcs recourse policy studied in \citep{Carvalho2020} also allows to recover a first-stage solution with pairs that were selected in that solution only, but such policy only allows to recover a cycle (chain) if there exists other cycles (chains) nested within it, making the back-arcs recourse more conservative than the first-stage-only recourse. In Figure \ref{fig:FullRecourse}, the recourse solution under the first-stage-only recourse would involve vertices 3, 4, and 6 in a cycle just as in the full-recourse policy, but chains started by vertex 8 and the cycle, vertex 7 belongs to, would not be within the feasible recourse set. Thus, the recourse objective value corresponds to only three pairs from the first stage.

\section{Robust model and first stage}
\label{RobustModels}

By observing that for a finite (yet possibly large) uncertainty set, the second optimization problem (the min problem), can be removed as an optimization level and included as a set of scenario constraints instead--- as in \citep{Carvalho2020},  Model \eqref{ROmodel} can be expressed as the following MIP robust formulation:
\vspace{-0.2cm}
\begin{subequations}
	\label{SingleROmodel0}
    \begin{align}
	\bm{P}(\policy, \bigsCe):  \max_{\varFirstPlain, Z_{P}} \quad& Z_{P}\\
	& Z_{P} \le  \max_{\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)} \weightRO\varReco & \bm{\oneCeS} \in \Gamma  \label{eq:scenarios}\\
	&\varFirstPlain \in \mathcal{X}
\end{align}
\end{subequations}
Observe that the optimization problem in the constraints set of Model \eqref{SingleROmodel0} is the recourse problem, which given a first-stage solution $\varFirstPlain \in \mathcal{X}$ and policy $\pi \in \Pi$, finds a recourse solution in the set of binary vectors $\setRecoSym^{\policy}(\varFirst, \oneCe)$ whose cycles and chains under scenario $\bm{\oneCeS} \in \Gamma$ have the largest number of re-arranged pairs from the first stage. Having the recourse problem in the constraints set is challenging since this one is solved for a fixed decision $\varFirstPlain$ as many times as the number of failure scenarios $\bm{\oneCeS} \in \Gamma$, which can be prohibitively large. To find a more tractable form, observe that the sense of the external and internal objectives in Model \eqref{SingleROmodel0} is maximization. We can then define a binary decision variable $\mathbf{y}^{\bm{\oneCeS}}$ for every scenario $\bm{\oneCeS} \in \Gamma$ whose feasible space corresponds to a recourse solution in $\setRecoSym^{\policy}(\varFirst, \oneCe)$. Thus, an equivalent model can see the inner optimization problem removed and the set $\setRecoSym^{\policy}(\varFirst, \oneCe)$ included as part of the constraints set for every failure scenario, as follows:
\vspace{-0.2cm}

\begin{subequations}
	\label{SingleROmodel}
    \begin{align}
	\bm{P}(\policy, \bigsCe)=  \max_{\varFirstPlain, Z_{P}} \quad& Z_{P}\\
	& Z_{P} \le  \weightRO\varReco^{\oneCe} & \bm{\oneCeS} \in \Gamma  \label{eq:scenariosBound}\\
 	&\mathbf{y}^{\bm{\oneCeS}} \in \setRecoSym^{\policy}(\varFirst, \oneCe) & \bm{\oneCeS} \in \Gamma  \label{eq:scenariosReco}\\
 	&\varFirstPlain \in \mathcal{X}
\end{align}
\end{subequations}

\noindent i.e., the first-stage solution and its corresponding recourse solution could be found in a single-level MIP formulation if
the set of scenarios $\Gamma$ could be enumerated. Observe that once a scenario $\bm{\oneCeS} \in \Gamma$ is fixed, $\setRecoSym^{\policy}(\varFirst, \oneCe)$ can be expressed by a set of linear constraints.  The position-indexed formulation for the robust KEP under full recourse proposed in \citep{Carvalho2020} follows the structure of Model \eqref{SingleROmodel}. We present such formulation and a variation of it for the first-stage-only recourse in the Online Supplement (see \ref{FullFirstSFormulation} and \ref{FirstStageOnlyFormulation}).

To overcome the large size of $\Gamma$, we solve the robust KEP in Model \eqref{SingleROmodel} iteratively, by finding a new failure scenario whose associated optimal recourse solution $\mathbf{y}^{\bm{\oneCeS}} \in \setRecoSym^{\policy}(\varFirst, \oneCe)$ has a number of re-arranged pairs from the first stage lower than the current value of Model \eqref{SingleROmodel}. The goal is to find a scenario, if any, that yields a recourse solution with an objective value lower than the current objective value of the robust KEP model. If such scenario is found, then a new set of recourse decision variables along with Constraints \eqref{eq:scenariosBound} and \eqref{eq:scenariosReco} are added to Model \eqref{SingleROmodel}. Algorithm \ref{Alg:ScenarioGeneration} shows the iterative approach used to solve  Model \eqref{SingleROmodel}. It starts with an empty restricted set of scenarios $\tilde{\Gamma}$.  At Step 1, $\bm{P}(\policy, \tilde{\bigsCe})$ is solved and its incumbent solution $(\tilde{Z}_{P}, \varFirstPlain)$ is retrieved. Then, at Step 2, the second-stage problem is solved to optimality for an incumbent solution $\varFirstPlain$ under policy $\pi$, i.e., a failure scenario $\oneCe^{\star} \in \Gamma$ causing the optimal recourse objective value to be the lowest among all possible failure scenarios is found. We refer to that scenario as the worst-case scenario for a first-stage solution $\varFirstPlain \in \mathcal{X}$. If such recourse objective value is lower than $\tilde{Z}_{P}$, then  $\oneCe^{\star}$ is added to the restricted set of scenarios $\tilde{\Gamma}$ and the corresponding Constraints \eqref{eq:scenariosBound} and \eqref{eq:scenariosReco} are added to Model \eqref{SingleROmodel}, point at which Model \eqref{SingleROmodel} is re-optimized.  We refer to Model \eqref{SingleROmodel} with a restricted set of scenarios $\tilde{\Gamma}$ as the first-stage problem or first-stage formulation to imply that the search of the optimal robust solution corresponding to some $\varFirstPlain \in \mathcal{X}$ continues. In principle, as long as a failure scenario $\bm{\oneCeS} \in \Gamma$ leads to an optimal recourse solution with an objective value lower than $\tilde{Z}_{P}$, that scenario could be added to Model \eqref{SingleROmodel}. However, for benchmark purposes, at Step 2 the worst-case scenario is found for a given first-stage solution $\varFirstPlain$ under policy $\pi$. If the optimal objective of the second-stage problem equals $\tilde{Z}_{P}$, then an optimal robust solution $(Z_{P}^{\star}, \varFirstPlain^{\star})$ is returned at Step 3.

 \begin{algorithm}[tbp]

	\algorithmicrequire { A policy $\pi \in \Pi$ and restricted set of scenarios $\tilde{\Gamma}$, $\tilde{\Gamma}:= \{\emptyset\}$}\\
	\algorithmicensure { Optimal robust solution $(Z_{P}^{\star}, \varFirstPlain^{\star})$}\\

	\textbf{Step 1:} Solve $\bm{P}(\policy, \tilde{\bigsCe})$ and obtain optimal solution $(\tilde{Z}_{P}, \varFirstPlain)$  \\
	\textbf{Step 2: } If $ \bm{\min}_{\bm{\oneCeS} \in \Gamma}\bm{\max}_{\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)} \mathbf{w}(\varFirst)^{\top}\mathbf{y} < \tilde{Z}_{P}$, then  \\
	\textbf{\textcolor{white}{Step 1: If }}  $\tilde{\Gamma} \gets \tilde{\Gamma} \cup \{\bm{\oneCeS}\}$, create recourse decision variable $\mathbf{y}^{\bm{\oneCeS}}$, add Constraints \eqref{eq:scenariosBound}, \eqref{eq:scenariosReco} and go to Step 1\\
	\textbf{Step 3: } $Z_{P}^{\star} \gets \tilde{Z}_{P}$; $\varFirstPlain^{\star} \gets \varFirstPlain$; Return $(Z_{P}^{\star}, \varFirstPlain^{\star})$

	\caption{Solving the robust KEP in Model \ref{SingleROmodel}}
	\label{Alg:ScenarioGeneration}

\end{algorithm}

Algorithm 	\ref{Alg:ScenarioGeneration} converges in a finite number of iterations due to the finiteness of $\mathcal{X}$ and $\Gamma$. Due to the large set of scenarios, Step 2 in Algorithm \ref{Alg:ScenarioGeneration} is critical to efficiently solve the robust problem. In subsequent sections, we decompose the second-stage problem into a master problem yielding a failure scenario and a sub-problem (the recourse problem) finding an alternative matching with the maximum number of re-arranged pairs from the first stage.

\section{New second-stage decompositions}
\label{SecondStage}

 In this section, we present two decompositions of the second-stage problem. Both consists of a feasibility-seeking master problem that finds a failure scenario and a sub-problem that finds an alternative matching under that scenario. Each decomposition solves a recourse problem with one of the two objective functions using cycles/chains as decision variables as proposed in \citep{Blom2021}. Although, the optimal solutions provided by both formulations are identical, one of the recourse solutions is found in the second-stage compatibility graph while the other one is found in the transitory graph. We use the structure of each solution set to formulate the master problem of each decomposition, accordingly.

\subsection{A basic feasibility-seeking formulation}
\label{sec:basicfeas}
In this section we introduce the first of the two new decompositions for the second-stage problem.

\subsubsection{The recourse problem}
Given a first-stage solution $\varFirstPlain \in \mathcal{X}$, let $\bigsCe(\varFirst) \subseteq \Gamma$ be the set of failure scenarios inducing digraph $D^{\pi}(\varFirstPlain, \bm{\oneCeS})$ with $\bm{\oneCeS} \in \bigsCe(\varFirst)$, as defined in Section \ref{Preliminaries}. The recourse problem for the basic decomposition consists of finding a matching of maximum weight in $D^{\pi}(\varFirstPlain, \bm{\oneCeS})$, i.e., a matching with the highest number of pairs selected in the first stage. We refer to $R^{\policy}(\varFirst, \oneCe)$ as the MIP formulation (Appendix \ref{sec:RecourseFormls}) solving the recourse problem in graph $D^{\pi}(\varFirstPlain, \bm{\oneCeS})$. Lastly, we refer to $\hat{\mathbf{y}}$ as an optimal recourse solution in $\setRecoSym^{\policy}(\varFirst, \oneCe)$ with objective value ${Z}^{\pi,\star}_{R}(\varFirst, \oneCe)$.

\subsubsection{The master problem: MasterBasic}
We continue to use $\gamma^{\text{v}}$ and $\gamma^{\text{a}}$ as binary vectors representing the failure of a vertex ($\gamma^{\text{v}}_{u} = 1 \ \forall u \in V$) and arc ($\gamma^{\text{a}}_{\vertexa\vertexb} = 1 \ \forall (\vertexa,\vertexb) \in A$), respectively. We let $\hat{\bigsCe}(\varFirst) \subseteq \bigsCe(\varFirst)$ be a subset of scenarios for which the recourse problem has already been solved under scenario $\hat{\oneCe} \in \hat{\bigsCe}(\varFirst)$. Thus, the master problem for the second-stage problem can be formulated as follows:\begin{subequations}
\label{mo:basicfeas}
    \begin{align}
        \tag{MB} \text{MasterBasic}(\varFirstPlain) \text{: }  &&& \qquad \qquad \text{Find } \bm{\oneCeS} \label{MasterBasic}\\
        && \sum_{c \in \mathcal{C}_{\cycleCap} \cup \mathcal{C}_{\chainCap}: \varFirstPlain_{c} = 1} &\left(\sum_{u \in V(c)} \gamma^{\text{v}}_{u} +  \sum_{(\vertexa,\vertexb) \in A(c)} \gamma^{\text{a}}_{\vertexa\vertexb} \right) \ge 1   && \varFirstPlain \in \mathcal{X}   \label{eq:AtLeastOneX}
        \\
         && \sum_{c \in \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \hat{\oneCe}): \hat{\mathbf{y}}_{c} = 1} &\left(\sum_{u \in V(c)} \gamma^{\text{v}}_{u} +  \sum_{(\vertexa,\vertexb) \in A(c)} \gamma^{\text{a}}_{\vertexa\vertexb} \right) \ge 1   && \hat{\mathbf{y}} \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe}); \hat{\oneCe} \in \hat{\bigsCe}(\varFirst)   \label{eq:AtLeastOne}\\
        &&& \qquad \qquad \bm{\oneCeS} \in \Gamma&& \label{basicGamma}
    \end{align}
\end{subequations}
where $\mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \hat{\oneCe}) = \cycleSet^{\pi}(\varFirstPlain, \hat{\oneCe}) \cup \chainSet^{\pi}(\varFirstPlain, \hat{\oneCe})$. Observe that Constraints \eqref{eq:AtLeastOneX}-\eqref{eq:AtLeastOne} correspond to covering constraints in a set cover problem, one of Karp's 21 NP-complete problems \citep{Karp1972}.

That is, at least one vertex or arc in \textit{every} cycle/chain selected in recourse solution $\mathbf{y} \in \setRecoSym^{\policy \star}(\varFirst, \hat{\oneCe})$ \textit{must} fail before finding the optimal worst-case scenario $\bm{\gamma}^{\star} \in \Gamma$ for a first-stage solution $\varFirstPlain \in \mathcal{X}$.  Algorithm \ref{Alg:BasicCovering} generates new failure scenarios $\hat{\oneCe} \in \bigsCe(\varFirst)$ until master problem \ref{MasterBasic} becomes infeasible, point at which the worst-case scenario, $\bm{\gamma}^{\star}$, and its associated optimal recourse solution value, i.e., the optimal objective value of the second-stage problem, $Z_{Q}^{\pi,\star}(\varFirst)$, have already been found. Algorithm  \ref{Alg:BasicCovering} starts with an empty subset of scenarios $\hat{\bigsCe}(\varFirst)$, and with an upper bound on the objective value of the second stage ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ equal to the objective value of the robust KEP in Model \eqref{SingleROmodel}, i.e., $\tilde{Z}_{P}$. \ref{MasterBasic} is solved for the first time to obtain a failure scenario $\hat{\oneCe} \in \bigsCe(\varFirst)$ and it is added to $\hat{\bigsCe}(\varFirst)$. At Step 1, the recourse formulation $R^{\policy}(\varFirst, \cdteOne)$ is solved and an optimal recourse solution $\mathbf{y}$ is obtained with objective value ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$. The recourse solution is then  added to $\setRecoSym^{\policy}(\varFirst, \hat{\oneCe})$ and a Constraint \eqref{eq:AtLeastOne} is created in \ref{MasterBasic}. If the objective value of the recourse solution ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$ is lower than the current upper bound ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$, then, the upper bound is updated, along with the incumbent failure scenario $\oneCe^{\prime}$. At Step 2, a new iteration starts and an attempt is made to find a feasible failure scenario in \ref{MasterBasic}. If such scenario exists, then Step 1 is repeated, otherwise the algorithm goes to Step 3, and an optimal solution ($\oneCe^{\star}, Z_{Q}^{\pi,\star}(\varFirst)$) to the second stage is returned. To prove the validity of Algorithm \ref{Alg:BasicCovering}, we state the following:
\begin{algorithm}[tbp]

	\algorithmicrequire { A recourse policy $\pi \in \Pi$ and feasible solution $\varFirstPlain \in \mathcal{X}$}\\
	\algorithmicensure { Optimal recovery plan value $Z_{Q}^{\pi,\star}(\varFirst)$ and worst-case scenario $\oneCe^{\star} \in \bigsCe(\varFirst)$}\\

	\textbf{Step 0: }  $i = 1 $; $\hat{\bigsCe}(\varFirst) = \emptyset$; ${\bar{\varCov}}^{\pi}_{Q}(\varFirst) \gets \tilde{Z}_{P}$; Solve \ref{MasterBasic} with Constraint \eqref{eq:AtLeastOneX} to obtain scenario $\hat{\oneCe}$; $\hat{\bigsCe}(\varFirst) \gets \hat{\bigsCe}(\varFirst) \cup \hat{\oneCe}$  \\
	\textbf{Step 1: }   Solve $R^{\policy}(\varFirst, \cdteOne)$ to obtain objective value ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$ and recourse solution $\hat{\varReco}$; create Constraint \eqref{eq:AtLeastOne}\\
	\textbf{\textcolor{white}{Step 1: }}
	If ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) < {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ then  ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)  = {Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$ and $\oneCe^{\prime} \gets \hat{\oneCe}$\\
	\textbf{Step 2: } $i \gets i + 1 $; Attempt to solve MasterBasic$(\varFirstPlain)$ to get a new candidate scenario $\hat{\oneCe}$;\\
	\textbf{\textcolor{white}{Step 2:} } If MasterBasic$(\varFirstPlain)$ is feasible go to Step 1;\\
	\textbf{Step 3: } $\oneCe^{\star} \gets \oneCe^{\prime}$; $Z_{Q}^{\pi,\star}(\varFirst) \gets {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$; Return $\oneCe^{\star}$ and $Z_{Q}^{\pi,\star}(\varFirst)$

	\caption{A basic feasibility-seeking algorithm for the second-stage master problem}
	\label{Alg:BasicCovering}

\end{algorithm}
\proposition Algorithm \ref{Alg:BasicCovering} returns the optimal objective value of the second stage $Z_{Q}^{\pi,\star}(\varFirst)$ and worst-case scenario $\bm{\gamma}^{\star} \in \bigsCe(\varFirst)$ for a first-stage decision $\varFirstPlain \in \mathcal{X}$.

\proof In the first part of the proof, we show that any optimal objective value of the recourse problem ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$, regardless of the scenario $\hat{\oneCe} \in \bigsCe(\varFirst)$ is an upper bound on the objective value of the second stage. In the second part, we show that the second-stage problem can be decomposed into an optimality-seeking master problem and a subproblem, also corresponding to the recourse problem. We then show that constraints in the optimality master problem have a one-to-one correspondence with those in \ref{MasterBasic}.

Part I.
Observe that given a candidate solution $\varFirstPlain \in \mathcal{X}$ and policy $\pi \in \Pi$
\begin{align*}
\max_{\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe})} \weightRO\varReco &\ge \min_{\bm{\oneCeS} \in \bigsCe(\varFirst)} \max_{\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)} \weightRO\varReco &  \hat{\oneCe} &\in \bigsCe(\varFirst)
\\
\sum_{c \in \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \hat{\oneCe}): \hat{\varReco}_{c} = 1} \mathbf{w_{\match}}(\varFirst) &\ge Z_{Q}^{\pi,\star}(\varFirst) & \hat{\varReco} &\in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe}); \hat{\oneCe} \in \bigsCe(\varFirst)\\
{Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) &\ge Z_{Q}^{\pi,\star}(\varFirst) & \hat{\oneCe} &\in \bigsCe(\varFirst)
\end{align*}
That is, the optimal objective value of a recourse solution $\hat{\mathbf{y}} \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe})$ regardless of the scenario $\hat{\oneCe} \in \bigsCe(\varFirst)$, is at least as big as the smallest value that $Z_{Q}^{\pi,\star}(\varFirst)$ can reach.

Part II.
In what follows $\mathbbm{1}_{c,\bm{\oneCeS}}$ is an indicating variable that takes on value one if cycle/chain $c \in \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \oneCe)$ fails under scenario $\bm{\oneCeS} \in \Gamma$. Let $\cycleSet^{\pi}(\varFirstPlain)$ and $\chainSet^{\pi}(\varFirstPlain)$ be the set of cycles and chains of the transitory graph $D^{\pi}(\varFirstPlain)$ that exists before a failure scenario is observed but after a set of transplants has already been proposed. Then, we define $\alpha_{c}$ as a binary decision variable for a cycle/chain $c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)$ that takes on value one if such cycle/chain fails, and zero otherwise. In Appendix \ref{Alg:CyChrecourse} we present a procedure to find $\cycleSet^{\pi}(\varFirstPlain)$ and $\chainSet^{\pi}(\varFirstPlain)$ given a first-stage solution $\varFirstPlain \in \mathcal{X}$. Note that since all feasible chains from length 1 to $L$ are found, the shortening of a chain when a failure occurs is represented by some $\alpha_{c}$ taking on value zero and another one taking on value one.
Then, the second-stage problem can be reformulated as follows:
\begin{subequations}
\begin{align}
    \label{eq:ReformScndS}
    &\min_{\bm{\oneCeS} \in \bigsCe(\varFirst)} \max_{\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)} \sum_{c \in \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \oneCe)} \mathbf{w_{\match}}(\varFirst)\mathbf{y}_{c}  \\
    =\min_{\bm{\oneCeS} \in \bigsCe(\varFirst)} \quad &Z^{\pi}_{Q}(\varFirst)\\
	& Z^{\pi}_{Q}(\varFirst) \ge  \max_{\mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)} \sum_{c \in \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \oneCe)} \left(\mathbf{w_{\match}}(\varFirst) - \mathbf{w_{\match}}(\varFirst) \mathbbm{1}_{c,\bm{\oneCeS}} \right) \mathbf{y}_{c} \\
	=\min_{\bm{\oneCeS} \in \bigsCe(\varFirst)} \quad &Z^{\pi}_{Q}(\varFirst)\\
	& Z^{\pi}_{Q}(\varFirst) \ge  \sum_{c \in \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \oneCe)} \left(\mathbf{w_{\match}}(\varFirst) - \mathbf{w_{\match}}(\varFirst) \mathbbm{1}_{c,\bm{\oneCeS}} \right) \mathbf{y}_{c} & \mathbf{y} \in \setRecoSym^{\policy}(\varFirst, \oneCe)\\
	=\min \quad &Z^{\pi}_{Q}(\varFirst) \tag{Q} \label{objMPOpt}\\
	& Z^{\pi}_{Q}(\varFirst) \ge  {Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) - \sum_{c \in \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \hat{\oneCe}): \hat{\mathbf{y}}_{c} = 1} \mathbf{w_{\match}}(\varFirst)\hat{\mathbf{y}}_{c} \alpha_{c} & \hat{\varReco} \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe}); \hat{\oneCe} \in \hat{\bigsCe}(\varFirst) \label{eq:solsTwo}\\
	& \alpha_{c} \le \sum_{u \in V(c)} \gamma^{\text{v}}_{u} + \sum_{(\vertexa,\vertexb) \in A(c)} \gamma^{\text{a}}_{\vertexa\vertexb}
    &c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain) \label{eq:Inter}\\
    &\bm{\oneCeS} \in \bigsCe(\varFirst) \label{eq:budget}\\
    &\alpha_c \in \{0,1\} & c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain) \label{eq:Bound}
    \end{align}
\end{subequations}

That is, for $Z^{\pi}_{Q}(\varFirst)$ to be as small as possible at least one cycle or chain, and thus, at least one vertex or arc must fail for some cycle/chain in every matching associated to an optimal recourse solution $\hat{\mathbf{y}} \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe})$ (Constraints \eqref{eq:solsTwo}). If it were not for the failure budget limiting the maximum number of failed vertices and arcs (Constraint \eqref{eq:budget}), $Z^{\pi}_{Q}(\varFirst)$ could reach zero. Note that if \ref{objMPOpt} is unable to cause the failure of a new optimal recourse solution $\hat{\varReco}$, is because in doing so Constraint \eqref{eq:budget} would be violated and from Part I, we know that the optimal objective value of that solution is at least $Z_{Q}^{\pi,\star}(\varFirst)$. Thus, the worst-case scenario $\oneCe^{\star}$  is found when there exists a Constraint \eqref{eq:solsTwo} associated to a recourse solution $\hat{\varReco}$ whose cycles/chains do not fail. Observe that there is a one-to-one correspondence between Constraints \eqref{eq:solsTwo} in \ref{objMPOpt} and Constraints \eqref{eq:AtLeastOne} in \ref{MasterBasic}. At the start of Algorithm \ref{Alg:BasicCovering}, when there is no known scenario, Constraint \eqref{eq:solsTwo} has  Constraint \eqref{eq:AtLeastOneX} as counterpart in \ref{MasterBasic}. Therefore, the smallest value of ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$ among all scenarios $\hat{\oneCe} \in \hat{\bigsCe}(\varFirst)$ before \ref{MasterBasic} becomes infeasible is the optimal value to the second stage. \hfill$\square$

\subsubsection{Lifting constraints}
Unlike valid inequalities, \textit{non-valid} inequalities cut off feasible solutions \citep{Atamturk2000, Hooker1994}, and therefore are invalid in the standard sense. Although, non-valid inequalities remove some integer solutions, all optimal solutions are preserved. Next, we derive the first family of non-valid inequalities to narrow down the search of the worst-case scenario in \ref{MasterBasic}.

Our goal is to strengthen the right-hand side of Constraints \eqref{eq:AtLeastOne} that have already been generated up to some iteration $i$ in Algorithm \ref{Alg:BasicCovering}, by updating the minimum number of vertices/arcs that should fail in each of those constraints whenever a smaller value of ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ is found.

For a recourse solution $\hat{\mathbf{y}} \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe})$ and assuming that the failure of a vertex/arc completely causes the failure of a cycle or chain, we sort cycle and chain weights  $\mathbf{w_{\match}}(\varFirst)$  $\forall \mathbf{y}_c = 1$ with $c \in \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \oneCe)$, in non-increasing order so that $\mathbf{w_{\match}}(\varFirst)_1 \ge \mathbf{w_{\match}}(\varFirst)_2 ... \ge \mathbf{w_{\match}}(\varFirst)_{\mid \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \oneCe) \mid}$ and let $H(\hat{\oneCe})$ be a parameter indicating the right-hand side value of its corresponding Constraint \eqref{eq:AtLeastOneX} - \eqref{eq:AtLeastOne}. We can now state the following:

\begin{proposition}
\label{prop:RHSi}
$H(\hat{\oneCe}) = t$ where $t$ is the smallest index for which the following condition is true: ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) - \sum_{t = 1}^{\mid \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \oneCe) \mid} \mathbf{w_{\match}}(\varFirst)_t < {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$.
\end{proposition}
\proof
Observe that unless optimal $Z^{\pi}_{Q}(\varFirst) < {Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) \ \forall \hat{\oneCe} \in \bigsCe(\varFirst)$, i.e., $Z^{\pi}_{Q}(\varFirst) < {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$. To satisfy this condition, a minimum number of cycles/chains must fail in every Constraint \eqref{eq:solsTwo}. Also, observe that Constraints \eqref{eq:Inter} imply that whenever at least one vertex/arc fails, so does its associated cycle/chain. Therefore, finding the minimum number of cycles/chains that should fail in $\ref{objMPOpt}$ to satisfy $Z^{\pi}_{Q}(\varFirst) < {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ implies finding the minimum number of vertices/arcs that should fail in Constraints \eqref{eq:AtLeastOneX} - \eqref{eq:AtLeastOne}. It is easy to see that by sorting the cycle/chain weight of every cycle/chain in non-increasing order, and then subtracting it in that order from ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$ until the subtraction is strictly lower to ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$, yields a valid lower bound on the number of cycles/chains that must fail.
\hfill$\square$

\subsection{An expanded feasibility-seeking decomposition}
\label{sec:ExtFeasForm}
Next, we introduce the second new decomposition for the second-stage problem.

\subsubsection{The recourse problem}
So far, we have solved the recourse problem in a realization of the second-stage compatibility graph $D^{\pi}(\varFirstPlain, \bm{\oneCeS})$. However, an optimal solution to the recourse problem $R^{\policy}(\varFirst, \oneCe)$ can also be found in the transitory graph $D^{\pi}(\varFirstPlain)$, by allowing failed cycles/chains into the optimal solution given by $R^{\policy}(\varFirst, \oneCe)$. Although, this solution does not contribute to more recourse objective value, as we will show, it can prevent some dominated scenarios from being explored, and therefore help reduce the number of times the recourse problem is resolved in Algorithm \ref{Alg:BasicCovering}. We refer to $\Rexp(\varFirst, \oneCe)$ (Appendix \ref{sec:RecourseFormls}) as the recourse problem solved in the transitory graph $D^{\pi}(\varFirstPlain)$, whose optimal recourse solutions are also optimal to $R^{\policy}(\varFirst, \oneCe)$. We refer the reader to Appendix \ref{sec:RecourseFormls} for a proof. The objective function in $\Rexp(\varFirst, \oneCe)$ has no meaning here beyond the fact that it is useful to find optimal solutions to the recourse problem $R^{\policy}(\varFirst, \oneCe)$ with failed cycles/chains. Thus,  we let $\bar{\varReco} \in \setRecoSym_{\text{exp}}^{\policy}(\varFirst, \oneCe)$ be an optimal recourse solution in the transitory graph $D^{\pi}(\varFirstPlain)$ that is also optimal to $R^{\policy}(\varFirst, \oneCe)$ under scenario $\bm{\oneCeS} \in \bigsCe(\varFirst)$. The set of solutions in the transitory graph $\setRecoSym_{\text{exp}}^{\policy}(\varFirst, \oneCe)$ is defined in the same way $\setRecoSym^{\policy}(\varFirst, \oneCe)$ is, except that $\cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS})$ and $\chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS})$ are replaced by $\cycleSet^{\pi}(\varFirstPlain)$ and   $\chainSet^{\pi}(\varFirstPlain)$, respectively.

\subsubsection{The master problem: MasterExp}
In the basic reformulation, we assumed the recourse solutions correspond to matchings with non-failed components only. In our expanded formulation we assume that recourse solutions can be expanded to fit some failed cycles/chains by solving the recourse problem in the transitory graph $D^{\pi}(\varFirstPlain)$. We let $\VarRecoOpExp(\hat{\oneCe}) \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe})$ be the subset of the optimal recourse solution in the transitory graph that has no failed cycles/chains and thus corresponds to a feasible solution in $\setRecoSym^{\policy}(\varFirst, \hat{\oneCe})$. Thus, the expanded feasibility-seeking reformulation is expressed as follows:
\begin{subequations}
\label{mo:extendedfeas}
    \begin{align}
        \tag{ME} \text{MasterExp}(\varFirstPlain) \text{: }  &&& \qquad \qquad \text{Find } \bm{\oneCeS} \label{MasterExp}\\
        && \sum_{c \in \mathcal{C}_{\cycleCap} \cup \mathcal{C}_{\chainCap}: \varFirstPlain_{c} = 1} &\left(\sum_{u \in V(c)} \gamma^{\text{v}}_{u} +  \sum_{(\vertexa,\vertexb) \in A(c)} \gamma^{\text{a}}_{\vertexa\vertexb} \right) \ge 1   && \varFirstPlain \in \mathcal{X}   \label{eq:AtLeastOneXExp}
        \\
         && \sum_{c \in \mathcal{C}_{K,L}^{\pi}(\varFirstPlain, \hat{\oneCe}): \hat{\varReco}_{c} = 1} &\left(\sum_{u \in V(c)} \gamma^{\text{v}}_{u} +  \sum_{(\vertexa,\vertexb) \in A(c)} \gamma^{\text{a}}_{\vertexa\vertexb} \right) \ge 1 &&  \VarRecoOpExp(\hat{\oneCe}) \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe}); \hat{\oneCe} \in \hat{\bigsCe}(\varFirst)   \label{eq:AtLeastOneExp}\\
        && \sum_{c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain): \hat{\varReco}_{c} = 1} &\left(\sum_{u \in V(c)} \gamma^{\text{v}}_{u}+ \sum_{(\vertexa,\vertexb) \in A(c)} \gamma^{\text{a}}_{\vertexa\vertexb} \right) \ge H_{\text{e}}(\hat{\oneCe})  && \ \bar{\varReco} \in \setRecoSym_{\text{exp}}^{\policy}(\varFirst, \hat{\oneCe}); \hat{\oneCe} \in \hat{\bigsCe}(\varFirst) \label{eq:AtLeastOneRHSExp}\\
        &&& \qquad \qquad \bm{\oneCeS} \in \Gamma&& \label{GammaExp}
    \end{align}
\end{subequations}

Constraints \eqref{eq:AtLeastOneXExp} and \eqref{eq:AtLeastOneExp} are equivalent to Constraints \eqref{eq:AtLeastOneX} and \eqref{eq:AtLeastOne}. Constraints \eqref{eq:AtLeastOneRHSExp} require that at least $H_{\text{e}}(\hat{\oneCe})$ vertices and arcs fail in an expanded recourse solution $\bar{\varReco} \in \setRecoSym_{\text{exp}}^{\policy}(\varFirst, \hat{\oneCe})$ which may include cycles and chains that fail under scenario $\hat{\oneCe} \in \hat{\bigsCe}(\varFirst)$.  Proposition \ref{prop:RHSExtdi} defines the value of $H_{\text{e}}(\hat{\oneCe})$. The goal of \ref{MasterExp} is to enforce the failure of two different recourse solutions with identical objective value under scenario $\hat{\oneCe} \in \hat{\bigsCe}(\varFirst)$, i.e. a recourse solution found in the second-stage compatibility graph $D^{\pi}(\varFirstPlain, \hat{\oneCe})$ and a solution found in the transitory graph $D^{\pi}(\varFirstPlain)$.

For a recourse solution $\bar{\varReco} \in \setRecoSym_{\text{exp}}^{\policy}(\varFirst, \hat{\oneCe})$ and again assuming that the failure of a vertex/arc completely causes the failure of a cycle or chain, we sort cycle and chain weights  $\mathbf{w_{\match}}(\varFirst)$  $\forall \mathbf{y}_c = 1$ with $c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)$, in non-increasing order so that $\mathbf{w_{\match}}(\varFirst)_1 \ge \mathbf{w_{\match}}(\varFirst)_2 ... \ge \mathbf{w_{\match}}(\varFirst)_{\mid \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain) \mid}$. Thus, we can now state,

\begin{proposition}
\label{prop:RHSExtdi}
$H_{\text{e}}(\hat{\oneCe}) = t$ where $t$ is the smallest index for which the following condition is true: ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) - \sum_{t = 1}^{\mid \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain) \mid} \mathbf{w_{\match}}(\varFirst)_t < {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$.
\end{proposition}
\proof
It follows by the same arguments given for Proposition
\ref{prop:RHSi}.

\noindent In the following example we see that \ref{MasterExp} can yield failure scenarios that dominate those in \ref{MasterBasic}.
\paragraph{Example}

Let us consider Figure \ref{fig:FullRecourse} again under full recourse. Given a first-stage solution $\varFirstPlain \in \mathcal{X}$ involving eight pairs in Figure \ref{fig:CompGraph}, the believed compatibility graph also corresponds to the transitory graph $D^{\pi}(\varFirstPlain)$. Once we observe failure scenario $\hat{\gamma}^{\text{v}}_{2} = 1$ and $\hat{\gamma}^{\text{a}}_{56} = 1$, the realization of the second-stage compatibility graph, $D^{\pi}(\varFirstPlain, \hat{\oneCe})$, is such that vertices 2, 9 and 10 do not belong to it. The optimal objective value to the recourse problem in $D^{\pi}(\varFirstPlain, \hat{\oneCe})$, i.e., $R^{\policy}(\varFirst, \cdteOne)$ is ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) = 5$ with an optimal solution $\hat{\varReco}$ involving cycles (3,4,6) and chain (8,1,5). When we solve the recourse problem in the transitory graph $D^{\pi}(\varFirstPlain)$, the optimal objective value is also 5, but its optimal recourse solution $\bar{\varReco} = \hat{\varReco} \cup \{(2,9,10)\}$ involves in addition to cycle (3,4,6) and chain (8,1,5), the failed cycle (2,9,10). A feasible scenario is highlighted in red for every iteration. Assuming $\bm{\oneCeS} \in \Gamma$, the first two iterations for \ref{MasterBasic} and \ref{MasterExp} are shown below:
\vspace{-1.5cm}
\begin{multicols}{2}
\begin{align*}
    i = 1 \ {\bar{\varCov}}^{\pi}_{Q}(\varFirst) = 8\\
    \text{MasterBasic}(\varFirstPlain) \text{: }\\
    {\color{red} \gamma^{\text{v}}_{2}}    + \gamma^{\text{v}}_{9}     + \gamma^{\text{v}}_{10} +
    \gamma^{\text{a}}_{2,9} + \gamma^{\text{a}}_{9,10} + \gamma^{\text{a}}_{10,2} + \gamma^{\text{v}}_{3}    +  \gamma^{\text{v}}_{4}    +
    \gamma^{\text{a}}_{3,4}\\    + \gamma^{\text{a}}_{4,3}     +
    \gamma^{\text{v}}_{1}    + \gamma^{\text{v}}_{5}     + \gamma^{\text{v}}_{6} +
    \gamma^{\text{v}}_{1,5}    + {\color{red} \gamma^{\text{v}}_{5,6}}
    \ge 1 \\
    i = 2, \ {\bar{\varCov}}^{\pi}_{Q}(\varFirst) = 5\\
    \gamma^{\text{v}}_{2}    + \gamma^{\text{v}}_{9}     + \gamma^{\text{v}}_{10} +
    \gamma^{\text{a}}_{2,9} + \gamma^{\text{a}}_{9,10} + \gamma^{\text{a}}_{10,2} + {\color{red}\gamma^{\text{v}}_{3}}     +  \gamma^{\text{v}}_{4}    +
    \gamma^{\text{a}}_{3,4}\\    + \gamma^{\text{a}}_{4,3}     +
    \gamma^{\text{v}}_{1}    + \gamma^{\text{v}}_{5}     + \gamma^{\text{v}}_{6} +
    \gamma^{\text{v}}_{1,5}    + {\color{red} \gamma^{\text{v}}_{5,6}}
    \ge 1 \rightarrow {\color{red} 2} \text{ by } \ref{prop:RHSi} \\
    {\color{red}\gamma^{\text{v}}_{3}}    + \gamma^{\text{v}}_{6}     + \gamma^{\text{v}}_{4} +
    \gamma^{\text{a}}_{3,6} + \gamma^{\text{a}}_{6,4}  + \gamma^{\text{a}}_{4,3}\\ + \gamma^{\text{v}}_{1}    +  \gamma^{\text{v}}_{5}    + \gamma^{\text{v}}_{8} +
    \gamma^{\text{a}}_{1,5}    + \gamma^{\text{a}}_{5,8}
    \ge 1
\end{align*}

\columnbreak
\begin{align*}
    i = 1, \ {\bar{\varCov}}^{\pi}_{Q}(\varFirst) = 8\\
    \text{MasterExp}(\varFirstPlain) \text{: }\\
    {\color{red} \gamma^{\text{v}}_{2}}    + \gamma^{\text{v}}_{9}     + \gamma^{\text{v}}_{10} +
    \gamma^{\text{a}}_{2,9} + \gamma^{\text{a}}_{9,10} + \gamma^{\text{a}}_{10,2} + \gamma^{\text{v}}_{3}    +  \gamma^{\text{v}}_{4}    +
    \gamma^{\text{a}}_{3,4}\\    + \gamma^{\text{a}}_{4,3}     +
    \gamma^{\text{v}}_{1}    + \gamma^{\text{v}}_{5}     + \gamma^{\text{v}}_{6} +
    \gamma^{\text{v}}_{1,5}    + {\color{red} \gamma^{\text{v}}_{5,6}}
    \ge 1\\
    i = 2, \ {\bar{\varCov}}^{\pi}_{Q}(\varFirst) = 5\\
    \gamma^{\text{v}}_{2}    + \gamma^{\text{v}}_{9}     + \gamma^{\text{v}}_{10} +
    \gamma^{\text{a}}_{2,9} + {\color{red}\gamma^{\text{a}}_{9,10}} + \gamma^{\text{a}}_{10,2} + {\color{red}\gamma^{\text{v}}_{3}}     +  \gamma^{\text{v}}_{4}    +
    \gamma^{\text{a}}_{3,4}\\    + \gamma^{\text{a}}_{4,3}     +
    \gamma^{\text{v}}_{1}    + \gamma^{\text{v}}_{5}     + \gamma^{\text{v}}_{6} +
    \gamma^{\text{v}}_{1,5}    +  \gamma^{\text{v}}_{5,6}
    \ge 1 \rightarrow {\color{red} 2} \text{ by } \ref{prop:RHSi}\\
    {\color{red}\gamma^{\text{v}}_{3}}    + \gamma^{\text{v}}_{6}     + \gamma^{\text{v}}_{4} +
    \gamma^{\text{a}}_{3,6} + \gamma^{\text{a}}_{6,4}  + \gamma^{\text{a}}_{4,3}\\ + \gamma^{\text{v}}_{1}    +  \gamma^{\text{v}}_{5}    + \gamma^{\text{v}}_{8} +
    \gamma^{\text{a}}_{1,5}    + \gamma^{\text{a}}_{5,8} \ge 1\\
    {\color{red}\gamma^{\text{v}}_{3}}    + \gamma^{\text{v}}_{6}     + \gamma^{\text{v}}_{4} +
    \gamma^{\text{a}}_{3,6} + \gamma^{\text{a}}_{6,4}  + \gamma^{\text{a}}_{4,3} + \gamma^{\text{v}}_{1}    +  \gamma^{\text{v}}_{5}\\    + \gamma^{\text{v}}_{8} +
    \gamma^{\text{a}}_{1,5}    + \gamma^{\text{a}}_{5,8} +
    \gamma^{\text{v}}_{2}    +  \gamma^{\text{v}}_{9}    + \gamma^{\text{v}}_{10} + \gamma^{\text{a}}_{2,9}   + {\color{red}\gamma^{\text{a}}_{9,10}}\\ + \gamma^{\text{a}}_{10,2} \ge 1 \rightarrow {\color{red} 2} \text{ by } \ref{prop:RHSExtdi}
\end{align*}
\end{multicols}
Observe that in the second iteration, the failure scenario that is feasible to \ref{MasterBasic} is not feasible to \ref{MasterExp}. The new failure scenario for \ref{MasterBasic} would lead to an optimal recourse solution with again ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) = 5$, whereas the optimal recourse solution for \ref{MasterExp} would lead to ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) = 3$. That is, in the third iteration the right-hand side of constraints \ref{MasterExp} will get updated with a new upper bound ${\bar{\varCov}}^{\pi}_{Q}(\varFirst) = 3$, leading \ref{MasterExp} to infeasibility sooner. On the other hand, \ref{MasterBasic} in the third iteration will need another attempt to ``discover'' a failure scenario that will bring down the ceiling of ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$.

\subsubsection{Dominating scenarios}
\label{DominatingScenarios}

A failure scenario $\tilde{\oneCe}^{\prime} \in \bigsCe(\varFirst)$ dominates another failure scenario $\tilde{\oneCe} \in \bigsCe(\varFirst)$ if the former implies the latter, i.e., $\varCov^{\star}_{R}(\varFirst,\oneCePrime) \le \varCov^{\star}_{R}(\varFirst, \oneCeNoPrime)$. Let $ I(\tilde{\oneCe}^{\prime})$  and $I(\tilde{\oneCe})$ be the number of failed vertices and arcs under their corresponding scenario. Moreover, let $C^{\policy}(\varFirst, \oneCePrime) \subseteq \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)$ and $C^{\policy}(\varFirst, \oneCeNoPrime) \subseteq \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)$ be the set of feasible cycles and chains including vertices and arcs that fail in the transitory graph $D^{\pi}(\varFirstPlain)$ under scenarios $\tilde{\oneCe}^{\prime}$ and $\tilde{\oneCe}$, respectively. We then state,

\begin{proposition}
\label{prop:dominance}
If $C^{\policy}(\varFirst, \oneCeNoPrime) \subseteq C^{\policy}(\varFirst, \oneCePrime)$, $\tilde{\oneCe}^{\prime}$ dominates $\tilde{\oneCe}$ and the following dominance inequality is valid for \ref{MasterBasic} and  \ref{MasterExp}.
\end{proposition}
\vspace*{-9mm}
\begin{align}
    \label{eq:dominance}
       \sum_{u: \tilde{\oneCe}_{u} = 1} \gamma^{\text{v}}_{u} + \sum_{(\vertexa,\vertexb): \tilde{\oneCe}_{\vertexa\vertexb} = 1} \gamma^{\text{a}}_{\vertexa\vertexb} \le I(\tilde{\oneCe}) \left(I(\tilde{\oneCe}^{\prime}) -
            \sum_{u: \tilde{\oneCe}^{\prime}_{u} = 1} \gamma^{\text{v}}_{u} - \sum_{(\vertexa,\vertexb): \tilde{\oneCe}^{\prime}_{\vertexa\vertexb} = 1} \gamma^{\text{a}}_{\vertexa\vertexb}
       \right)
\end{align}

\proof By definition  $C^{\policy}(\varFirst, \oneCeNoPrime) \subseteq C^{\policy}(\varFirst, \oneCePrime)$, thus, all cycles and chains that fail under $\tilde{\oneCe}$ also fail under $\tilde{\oneCe}^{\prime}$, which means that $\varCov^{\star}_{R}(\varFirst,\oneCePrime) \le \varCov^{\star}_{R}(\varFirst, \oneCeNoPrime)$. Thus, if $\tilde{\oneCe}^{\prime}$ occurs, another failure scenario should be proposed instead of $\tilde{\oneCe}$ to bring the value of ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ down.

A natural observation is that, finding all $\tilde{\oneCe}, \tilde{\oneCe}^{\prime} \in \bigsCe(\varFirst)$ satisfying Proposition \ref{prop:dominance} is not straightforward and there could be too many constraints of type \eqref{eq:dominance} to feed into our master problem formulations. We explore two alternatives to separate these dominating-scenario cuts: the first one consists on identifying a subset of scenarios that satisfy constraint \eqref{eq:dominance} a priori. The second one consists of attempting to solve \textit{exactly} \ref{MasterBasic} and  \ref{MasterExp} via a heuristics and then ``discovering'' dominating scenarios on the fly. Next, we present a subset of dominated scenarios following either of the two strategies.

\paragraph{Adjacent-failure separation}
When a vertex failure occurs in the transitory graph $D^{\pi}(\varFirstPlain)$, the number of failed cycles and chains do not get affected if an arc adjacent to that vertex also fails. Thus, for every vertex $u \in V$, we can build a dominating scenario in which the only non-zero value in vector is $\tilde{\oneCe}^{\prime\text{v}}$ is $\tilde{\oneCe}^{\prime\text{v}}_{u} = 1$, and a dominated scenario for all arcs either leaving $u$, i.e., $\tilde{\oneCe}^{\text{a}}_{\vertexa\vertexb} = 1$  or pointing towards it, i.e., $\tilde{\oneCe}^{\text{a}}_{\vertexb\vertexa} = 1$, respectively. Note that the following constraints satisfy Proposition \ref{prop:dominance}:
\begin{align}
    \label{eq:adjacent}
    \sum_{(\vertexa,\vertexb) \in A} \gamma^{\text{a}}_{\vertexa\vertexb} + \sum_{(\vertexb,\vertexa) \in A} \gamma^{\text{a}}_{\vertexb\vertexa} \le r^{\text{a}} \left(1 -  \gamma^{\text{v}}_{u} \right)&& u \in V
\end{align}
Constraints \eqref{eq:adjacent} can be added to \ref{MasterBasic} and  \ref{MasterExp} before the start of Algorithm \ref{Alg:BasicCovering}.

\paragraph{Single-vertex-arc separation}
\label{vxtarcsep}
Suppose we have found a set of proposed failed arcs $A(\tilde{\oneCe}^{\text{a}})$ such that $\gamma^{\text{a}}_{\vertexa\vertexb} = 1 \ \forall {(\vertexa,\vertexb)} \in A(\tilde{\oneCe}^{\text{a}})$, and a set of proposed failed vertices, $V(\tilde{\oneCe}^{\text{v}})$, such that $\tilde{\oneCe}^{\text{v}}_{u} = 1 \ \forall u \in V(\tilde{\oneCe}^{\text{v}})$. A realization of the second-stage compatibility graph corresponds to $D^{\pi}(\varFirstPlain, \tilde{\oneCe}) = (V^{\pi}_{\varFirstPlain} \setminus V(\tilde{\oneCe}^{\text{v}}), A^{\pi}_{\varFirstPlain} \setminus A(\tilde{\oneCe}^{\text{a}}))$. Then, the following two cases also satisfy Proposition \ref{prop:dominance}:

\begin{enumerate}
    \item \label{CaseOne} Suppose there is a candidate pair $\bar{v} \in V^{\pi}_{\varFirstPlain} \setminus V(\tilde{\oneCe}^{\text{v}})$ and $C^{\policy, \bar{\vertexb}}(\varFirst)$ is the set of feasible cycles and chains in $D^{\pi}(\varFirstPlain, \tilde{\oneCe})$ that include vertex $\bar{v}$. Then, if  $C^{\policy, \bar{\vertexb}}(\varFirst) = \emptyset$ scenario $\tilde{\oneCe}$ dominates scenario $\tilde{\oneCe} \cup \{\bar{v}\}$ and thus for ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ to decrease, another vertex $\bar{v}$ should be proposed to fail.

    \item \label{CaseTwo} Suppose there is a candidate arc $\bar{a} \in A^{\pi}_{\varFirstPlain} \setminus A(\tilde{\oneCe}^{\text{a}})$ and $C^{\policy,\bar{a}}(\varFirst)$ is the set of recourse cycles and chains in $D^{\pi}(\varFirstPlain, \tilde{\oneCe})$ that include arc $\bar{a}$. Then, if  $C^{\policy,\bar{a}}(\varFirst) = \emptyset$ scenario $\tilde{\oneCe} \cup \{\bar{v}\}$ and thus another arc $\bar{a}$ should be proposed to fail if ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ is to be lowered.
\end{enumerate}

 Instead of removing dominated scenarios from \ref{MasterBasic} and  \ref{MasterExp} through cutting planes, we incorporate the previous two cases in a heuristics that attempts to solve such master problems exactly, as shown in the next section.
\section{Solution Algorithms for the Second Stage}
\label{sec:HSAs}
This section presents solution algorithms to solve the second stage.
We refer to \textit{hybrid} solution algorithms as the combination of a linear optimization solver and a heuristics aiming to solve \textit{exactly} the second-stage problem. Our goal is to specialize the steps of Algorithm \ref{Alg:BasicCovering} to improve the efficiency of our final solution approaches.

\subsection{A feasibility-based solution algorithm for MasterBasic}
The first of our two feasibility-based solution algorithms has \ref{MasterBasic} as master problem, and it is referred to as FBSA\_MB. FBSA\_MB requires a policy $\pi \in \Pi$ and a first-stage solution $\varFirstPlain$ found at Step 0 of Algorithm \ref{Alg:ScenarioGeneration}. We refer to $\textbf{ToMng}(\cdot)$ as a function that ``extracts'' the matching from a recourse solution, which is added to a set $\mathcal{M}$ containing all matchings associated to the recourse solutions found up to some iteration $i$ of the algorithm. At Step 0, $\mathcal{M}$ takes as input the matching associated to the first-stage solution $\varFirstPlain \in \mathcal{X}$. The procedure \textbf{Heuristics}($\mathcal{M}$)---whose algorithmic details we present shortly, attempts to find a failure scenario satisfying the constraints in \ref{MasterBasic}. The heuristics returns a tuple $(\incumCe, \cover)$ with two outputs: The first one corresponds to a \textit{candidate} failure scenario $\oneCe^{\prime}$. The second output is $\textit{cover}$, a boolean variable that indicates whether $\oneCe^{\prime}$ satisfies Constraints \eqref{eq:AtLeastOne}. At Step 0, because there is only one matching in $\mathcal{M}$, it is trivial to heuristically choose one element (vertex or arc) that satisfies Constraint \eqref{eq:AtLeastOneX} and thus the result of the boolean variable $\textit{cover}$ is \textbf{true}. This failure scenario is then added to $\hat{\bigsCe}(\varFirst)$. At Step 1, we attempt to find the optimal recourse solution through a column generation (CG) algorithm, $\textbf{ColGen}(R^{\policy}(\varFirst, \cdteOne))$, for which we generate the sets $\cycleSet^{\pi}(\varFirstPlain)$ and $\chainSet^{\pi}(\varFirstPlain)$ every time a new first-stage decision is made. For very large instances, large-scale decomposition algorithms such as the one proposed in \citep{Riascos2020} can be used to find positive-price columns (cycles or chains) as opposed to searching through all cycles and chains. As usual in a CG algorithm, only positive-price columns are added to its master problem iteratively. Once the optimality of the CG master problem is proven, an upper bound $Z^{\text{UB}}_{\text{cg}}$ on the optimal value of the recourse problem is returned. Then, we take the decision variables from the master problem base and turn them into binary ones to obtain a feasible recourse solution $\tilde{\mathbf{y}}$ with objective value $Z^{\star}_{\text{cg}}$. If $Z^{\star}_{\text{cg}}$ equals the upper bound $Z^{\text{UB}}_{\text{cg}}$, then $\tilde{\mathbf{y}}$ is optimal to formulation $R^{\policy}(\varFirst, \cdteOne)$. If that is the case, then at Step 1, $\tilde{\mathbf{y}}$ becomes the optimal recourse solution $\hat{\varReco}$ and both ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$ and $\mathcal{M}$ are updated. Otherwise, we incur in the cost of solving $R^{\policy}(\varFirst, \cdteOne)$ from scratch as a MIP instance, and update ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$ and $\mathcal{M}$, correspondingly. If the new recourse value ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$ is smaller than the upper bound on the objective value of the second stage, ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$, then we update both  ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ and the incumbent failure scenario $\oneCe^{\star}$ that led to that value. Since a new lower bound has been found, the right-hand side of Constraints (\ref{eq:AtLeastOneX}-\ref{eq:AtLeastOne}) is updated following Proposition \ref{prop:RHSi}. At Step 2, a new iteration starts. We try to find a feasible failure scenario  in \ref{MasterBasic}+Consts.\eqref{eq:adjacent} through either \textbf{Heuristics}($\mathcal{M}$) or through solving \ref{MasterBasic}+Consts.\eqref{eq:adjacent} as a MIP instance. If a feasible failure scenario is found, then the recourse problem is solved newly at Step 1. Otherwise, at Step 3, the algorithm ends and returns the optimal recovery plan ($Z_{Q}^{\pi,\star}(\varFirst)$, $\oneCe^{\star}$).

\begin{algorithm}[tbp]

	\algorithmicrequire { A recourse policy $\pi \in \Pi$ and first-stage solution $\varFirstPlain \in \mathcal{X}$}\\
	\algorithmicensure { Optimal recovery plan value $Z_{Q}^{\pi,\star}(\varFirst)$ and worst-case scenario $\oneCe^{\star} \in \bigsCe(\varFirst)$}
    \begin{algorithmic}[1]
    \item[]  \textbf{Step 0: }\\
    \STATE $i = 1 $; $I \gets I \cup \{i\}$; ${\bar{\varCov}}^{\pi}_{Q}(\varFirst) \gets \tilde{Z}_{P}$; $\mathcal{M} \gets  \textbf{ToMng}(\varFirstPlain)$
	\STATE  $(\incumCe, \text{\textbf{true}}) \gets$ \text{\textbf{Heuristics}}($\mathcal{M}$) \\
	\STATE $\hat{\oneCe} \gets \oneCe^{\prime}$; $\hat{\bigsCe}(\varFirst) \gets \hat{\bigsCe}(\varFirst) \cup \hat{\oneCe}$
	\item[]  \textbf{Step 1: }\\
	\STATE $(\ZRecoCol, \ZRecoColUB, \tilde{\varReco}) \gets \textbf{ColGen}\left(R^{\policy}(\varFirst, \cdteOne) \right)$
	\IF{$Z^{\star}_{\text{cg}} = Z^{\text{UB}}_{\text{cg}}$}
	\STATE   ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) \gets Z^{\star}_{\text{cg}}$\\ $\hat{\varReco} \gets \tilde{\mathbf{y}}$; $\mathcal{M} \gets  \mathcal{M} \cup \textbf{ToMng}(\hat{\varReco})$
	\ELSE
	\STATE Solve $R^{\policy}(\varFirst, \cdteOne)$ to obtain solution $\hat{\varReco} \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe})$ with objective value ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$; $\mathcal{M} \gets  \mathcal{M} \cup \textbf{ToMng}(\hat{\varReco})$
	\ENDIF
	\IF{${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) < {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$}
	\STATE ${\bar{\varCov}}^{\pi}_{Q}(\varFirst) \gets {Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$; $\oneCe^{\star} \gets \hat{\oneCe}$
	\STATE Update $H(\hat{\oneCe})$ in \ref{MasterBasic}, \ $\forall \hat{\oneCe} \in \hat{\bigsCe}(\varFirst)$ following Proposition \ref{prop:RHSi}
	\ENDIF
	\item[]   \textbf{Step 2:} \\
    \STATE $i \gets i + 1 $;
    \STATE $(\incumCe, \cover) \gets \text{\textbf{Heuristics}}(\mathcal{M})$
    \IF{$\textit{cover} = \text{\textbf{true}}$}
    \STATE $\hat{\oneCe} \gets \oneCe^{\prime}$; $\hat{\bigsCe}(\varFirst) \gets \hat{\bigsCe}(\varFirst) \cup \hat{\oneCe}$
    \STATE Go to \textbf{Step 1}
    \ELSE
    \STATE Create \eqref{eq:AtLeastOne} for $\hat{\varReco} \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe})$. Attempt to solve \ref{MasterBasic}+Consts.\eqref{eq:adjacent} to get new candidate scenario $\hat{\oneCe}$
    \IF{\ref{MasterBasic} is feasible}
        \STATE $\hat{\bigsCe}(\varFirst) \gets \hat{\bigsCe}(\varFirst) \cup \hat{\oneCe}$
        \STATE Go to \textbf{Step 1}
    \ENDIF
    \ENDIF
    \STATE  \textbf{Step 3: } $Z_{Q}^{\pi,\star}(\varFirst) \gets {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$; Return $\oneCe^{\star}$ and $Z_{Q}^{\pi,\star}(\varFirst)$
	\caption{FBSA\_MB: A Feasibility-based Solution Algorithm for \ref{MasterBasic}}
	\label{Alg:BasicHybrid}
	\end{algorithmic}
\end{algorithm}

\subsection{A feasibility-based solution algorithm for MasterExp}
Our second feasibility-based solution algorithm has \ref{MasterExp} as the master problem of the second stage, and we refer to it as FBSA\_ME.
FBSA\_ME requires a recourse policy $\pi \in \Pi$ and a first-stage solution $\varFirstPlain \in \mathcal{X}$. In addition to the notation defined for FBSA\_MB, we introduce new one. We refer to $\mathcal{M}_{\text{exp}}$ as the set of matchings associated to the optimal recourse solutions when solving the recourse problem in the transitory graph $D^{\pi}(\varFirstPlain)$. The CG algorithm, $\textbf{XColGen}\left(\Rexp(\varFirst, \hat{\oneCe}) \right)$, returns a tuple with three values: $Z^{\text{UB}}_{\text{Xcg}}$, $Z^{\star}_{\text{Xcg}}$ and $\tilde{\mathbf{y}}$. $Z^{\text{UB}}_{\text{Xcg}}$  corresponds to the optimal objective value returned by the master problem of our CG algorithm; $Z^{\star}_{\text{Xcg}}$ is the feasible solution to the KEP after turning the decision variables of the optimal basis of the CG master problem into binaries. Lastly, $\tilde{\mathbf{y}}$ is the feasible recourse solution found by the CG algorithm with objective value $Z^{\star}_{\text{Xcg}}$. At the start, FBSA\_ME takes as input the matching associated to the first-stage solution $\varFirstPlain \in \mathcal{X}$ and \textbf{Heuristics}($\mathcal{M}$) returns the first failure scenario. At Step 1, we solve the linear relaxation of recourse problem $\Rexp(\varFirst, \oneCe)$ through $\textbf{XColGen}\left(\Rexp(\varFirst, \hat{\oneCe}) \right)$. If $Z^{\star}_{\text{Xcg}} = Z^{\text{UB}}_{\text{Xcg}}$ then a function $\textbf{TrueVal}(Z^{\star}_{\text{Xcg}})$ returns the weighted sum of the cycles and chains in $\tilde{\mathbf{y}}$ that did not fail under the current failure scenario $\hat{\oneCe} \in \hat{\bigsCe}(\varFirst)$. In case the feasible solution $Z^{\star}_{\text{Xcg}}$ has a lower value than $Z^{\text{UB}}_{\text{Xcg}}$, then the original recourse problem $R^{\policy}(\varFirst, \cdteOne)$ is solved as a MIP instance. The reason for this decision is that  $\Rexp(\varFirst, \oneCe)$ includes a larger set of cycle-and-chain decision variables, possibly leading to scalability issues when the recourse problem is solved as a MIP instance. For iterations where this occur, i.e., $Z^{\star}_{\text{Xcg}} < Z^{\text{UB}}_{\text{Xcg}}$, both $\mathcal{M}$ and $\mathcal{M}_{\text{exp}}$ take as input the matching associated to $\hat{\varReco}$. If the upper bound ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ is updated, so is the right-hand side of constraints in \ref{MasterExp}. At Step 2, a new iteration starts. A new attempt to find a feasible failure scenario is made first by \text{\textbf{Heuristics}}($\mathcal{M} \cup \mathcal{M}_{\text{exp}}$) and then by solving \ref{MasterExp}+Consts.\eqref{eq:adjacent} as a MIP instance. If a feasible scenario is found, then a new recourse solution is found at Step 1. Otherwise, FBSA\_ME returns an optimal solution to the second stage at Step 3.

\begin{algorithm}[tbp]

	\algorithmicrequire { A recourse policy $\pi \in \Pi$, a first-stage solution $\varFirstPlain \in \mathcal{X}$}\\
	\algorithmicensure { Optimal recovery plan value $Z_{Q}^{\pi,\star}(\varFirst)$ and worst-case scenario $\bm{\oneCeS}^{\star} \in \bigsCe(\varFirst)$}
    \begin{algorithmic}[1]
    \item[]  \textbf{Step 0: }\\
    \STATE $i = 1 $; ${\bar{\varCov}}^{\pi}_{Q}(\varFirst) \gets \tilde{Z}_{P}$; $\mathcal{M} \gets \textbf{ToMng}(\varFirstPlain)$\\
    \STATE  $(\incumCe, \text{\textbf{true}}) \gets$ \text{\textbf{Heuristics}}($\mathcal{M}$) \\
	\STATE $\hat{\oneCe} \gets \oneCe^{\prime}$; $\hat{\bigsCe}(\varFirst) \gets \hat{\bigsCe}(\varFirst) \cup \hat{\oneCe}$
	\item[]  \textbf{Step 1: }\\
	\STATE $(\ZRecoColexp, \ZRecoColUBexp, \tilde{\varReco}) \gets \textbf{XColGen}\left(\Rexp(\varFirst, \hat{\oneCe}) \right)$
	\IF{$Z^{\star}_{\text{Xcg}} = Z^{\text{UB}}_{\text{Xcg}}$}
	\STATE $\bar{\varReco} \gets \tilde{\mathbf{y}}$
	\STATE ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) \gets \textbf{TrueVal}(Z^{\star}_{\text{Xcg}})$
	\STATE $\mathcal{M}_{\text{exp}} \gets \mathcal{M}_{\text{exp}} \cup \textbf{ToMng}(\bar{\varReco})$; $\mathcal{M} \gets \mathcal{M} \cup \textbf{ToMng}(\VarRecoOpExp(\hat{\oneCe}))$
	\ELSE
	\STATE Solve $R^{\policy}(\varFirst, \cdteOne)$ to obtain recourse objective value ${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$ and recourse solution $\hat{\varReco}$;\\
	$\mathcal{M}_{\text{exp}} \gets \mathcal{M}_{\text{exp}} \cup \textbf{ToMng}(\hat{\varReco})$; $\mathcal{M} \gets \mathcal{M} \cup \textbf{ToMng}(\hat{\varReco})$
	\ENDIF
	\IF{${Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe}) < {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$}
	\STATE ${\bar{\varCov}}^{\pi}_{Q}(\varFirst) \gets {Z}^{\pi,\star}_{R}(\varFirst, \hat{\oneCe})$; $\oneCe^{\star} \gets \hat{\oneCe}$
	\STATE Update $H(\hat{\oneCe})$ and $H_{\text{e}}(\hat{\oneCe})$ in \ref{MasterExp}, \ $\forall \hat{\oneCe} \in \hat{\bigsCe}(\varFirst)$ following Propositions \ref{prop:RHSi} and \ref{prop:RHSExtdi}, respectively.
	\ENDIF
	\item[]   \textbf{Step 2:} \\
    \STATE $i \gets i + 1 $
    \STATE $(\incumCe, \cover) \gets \text{\textbf{Heuristics}}(\mathcal{M} \cup \mathcal{M}_{\text{exp}})$
    \IF{$\textit{cover} = \text{\textbf{true}}$}
    \STATE $\hat{\oneCe} \gets \oneCe^{\prime}$
    \STATE Go to \textbf{Step 1}
    \ELSE
    \STATE Create Const.\eqref{eq:AtLeastOneExp}  for $\VarRecoOpExp(\hat{\oneCe}) \in \setRecoSym^{\policy}(\varFirst, \hat{\oneCe})$ and Const.\eqref{eq:AtLeastOneRHSExp} for $\bar{\varReco} \in \setRecoSym_{\text{exp}}^{\policy}(\varFirst, \hat{\oneCe})$. Attempt to solve \ref{MasterExp}+Consts.\eqref{eq:adjacent} to get new candidate scenario $\hat{\oneCe}$;
    \IF{\ref{MasterExp} is feasible}
    \STATE $\hat{\bigsCe}(\varFirst) \gets \hat{\bigsCe}(\varFirst) \cup \hat{\oneCe}$
    \STATE Go to \textbf{Step 1}
    \ENDIF
    \ENDIF
    \STATE  \textbf{Step 3: } $Z_{Q}^{\pi,\star}(\varFirst) \gets {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$; Return $\oneCe^{\star}$ and $Z_{Q}^{\pi,\star}(\varFirst)$
	\caption{FBSA\_ME: A Feasibility-based Solution Algorithm for \ref{MasterExp}}
	\label{Alg:EnhancedHybrid}
	\end{algorithmic}
\end{algorithm}

\subsection{Hybrid solution algorithms}
The main change of the algorithms presented shortly with respect to the feasibility-based algorithms is the possibility of transitioning from the feasibility-seeking master problems to \ref{objMPOpt} after TR number of iterations. The goal is to obtain a lower bound on the objective value of the second stage, ${\bunderline{\varCov}}^{\pi}_{Q}(\varFirst)$, that can be compared to ${\bar{\varCov}}^{\pi}_{Q}(\varFirst)$ to prove optimality. We refer to these hybrid algorithms as HSA\_MB and HSA\_ME. The former has \ref{MasterBasic} as master problem, whereas the latter has \ref{MasterExp}. For both hybrid algorithms we solve the recourse problem $\Rexp(\varFirst, \hat{\oneCe})$ in the transitory graph, but in the case of HSA\_MB whenever an attempt to find a failure scenario occurs, it is done with respect to \ref{MasterBasic}+Consts.\eqref{eq:adjacent}. The reason for this approach is to accumulate the recourse solutions given by $\Rexp(\varFirst, \hat{\oneCe})$ and use them to solve \ref{objMPOpt} when the number of iterations exceeds TR. Algorithm \ref{Alg:Hybrid} presents the changes required in Algorithms \ref{Alg:BasicHybrid} and \ref{Alg:EnhancedHybrid} to obtain HSA\_MB and HSA\_ME. Particularly, Algorithm \ref{Alg:Hybrid} should be included in lines 12 and 14 of Algorithm \ref{Alg:BasicHybrid} and Algorithm \ref{Alg:EnhancedHybrid}, respectively.

\begin{algorithm}[tbp]

	\algorithmicrequire{ Parameter TR indicating  iterations threshold as of which \ref{objMPOpt} is solved}
    \begin{algorithmic}[1]
    \IF{$i \ge$ TR}
        \STATE Create one Const.\eqref{eq:solsTwo} per matching in $\mathcal{M}_{\text{exp}}$ and solve $\ref{objMPOpt}$ to obtain ${\bunderline{\varCov}}^{\pi}_{Q}(\varFirst)$ and failure scenario $\hat{\oneCe}$
        \IF{${\bunderline{\varCov}}^{\pi}_{Q}(\varFirst) = {\bar{\varCov}}^{\pi}_{Q}(\varFirst)$}
            \STATE $\oneCe^{\star} \gets \hat{\oneCe}$, Go to \textbf{Step 3} in  Algorithm \ref{Alg:BasicHybrid} or Algorithm \ref{Alg:EnhancedHybrid}
        \ELSE
            \STATE Go to \textbf{Step 1} in  Algorithm \ref{Alg:BasicHybrid} or Algorithm \ref{Alg:EnhancedHybrid}
        \ENDIF
    \ENDIF
	\caption{Additional steps for hybrid solution algorithms, HSA\_MB and HSA\_ME}
	\label{Alg:Hybrid}
	\end{algorithmic}
\end{algorithm}

\subsection{Heuristics}
We now discuss the heuristics (Algorithm \ref{Alg:Heuristics}), used in the feasibility-based and hybrid algorithms. Algorithm \ref{Alg:Heuristics} requires as input a set of matchings $W$. If a failure scenario $\oneCe^{\prime}$ is returned, it satisfies either \ref{MasterBasic}+Consts.\eqref{eq:adjacent} or \ref{MasterExp}+Consts.\eqref{eq:adjacent}, accordingly. The heuristics performs the adjacent-failure separation and the two single-vertex-arc separation cases presented in Section \ref{DominatingScenarios}.
A function \textbf{UniqueElms}($W$) returns the set of unique vertices and arcs among all matchings in $W$, which are then kept in $E$.  With some abuse of notation, we say that each vertex/arc $\text{e}_{n}  \in E$ with $n = 1,...\lvert E \rvert$ has an associated boolean variable $s_{n}$ and a calculated weight $\text{w}_{n}$. The boolean variable $s_{n}$ becomes \textbf{true} if element $\text{e}_{n}$ has been checked, i.e., either it has been proposed for failure in $\oneCe^{\prime}$ or whether it has been proven that $\text{e}_{n}$ is dominated according to Section \ref{DominatingScenarios}. Function $\text{\textbf{Weight}}(W)$ returns the weight $\text{w}_{n}$ corresponding to the number of times element $\text{e}_{n}$ is repeated in the set of matchings $W$. Moreover, a function $\text{\textbf{IsNDD}}(\Elem^\star_{n})$ determines whether element $\Elem^\star_{n}$ is a singleton donor. While it is true, a list of unique and non-checked elements $\mathcal{E}$ is created as long as the vertex and arc budgets, $r^{\text{v}}$ and $r^{\text{a}}$ are not exceeded, respectively. If $\mathcal{E}$ turns out to have no elements, the algorithm ends in line 10. Otherwise, the elements in $\mathcal{E}$ are sorted in non-increasing order of their weights, and among the ones with the highest weight, an element $\Elem^\star_{n}$ is selected randomly. In line 14, the single-vertex-arc separation described in Section \ref{vxtarcsep} is performed as long as $\Elem^\star_{n}$ is a pair, there is at least one arc or at least two vertices proposed for failure already. The reason we check $\Elem^\star_{n}$ is not a singleton donor is because by definition a singleton donor does not belong to a cycle and if removed as a vertex from the transitory or second-stage compatibility graph, its removal causes the failure of all chains triggered by it. Between lines 15 and 24 we perform the two single-vertex-arc separation procedures using the same notation as in Section \ref{vxtarcsep}. A boolean variable \textit{ans} remains \textbf{true} if $\Elem^\star_{n}$ is a singleton donor or a non-proven dominated vertex/arc. Element $\Elem^\star_{n}$ is labeled as checked by setting $\Elem^\star_{n} = \text{\textbf{true}}$. Then, if  \textit{ans} = \textbf{true}, it is checked whether $\Elem^\star_{n}$ is a vertex or an arc, and the proposed failure scenario $\bar{\bm{\gamma}}$ is updated, accordingly. If element $\Elem^\star_{n}$ is a vertex, in line 28 the set of arcs adjacent to $\Elem^\star_{n}$ are labeled as checked, so that $\bar{\bm{\gamma}}$ satisfies Constraints \eqref{eq:adjacent}. We say that scenario $\bar{\bm{\gamma}}$ covers all matchings in $W$, if for every matching in that set, there exists at least $H(\hat{\oneCe})$ or $H_{\text{e}}(\hat{\oneCe})$; $\hat{\oneCe} \in \hat{\bigsCe}(\varFirst)$ vertices/arcs in each matching that have been proposed for failure in $\bar{\bm{\gamma}}$. Recall that every matching in $W$ is associated with one constraint in either (\ref{eq:AtLeastOneX}-\ref{eq:AtLeastOne}) or (\ref{eq:AtLeastOneXExp}-\ref{eq:AtLeastOneRHSExp}). If $\bar{\bm{\gamma}}$ covers all matchings in $W$, then \textit{cover} = \textbf{true}. The heuristics is greedy in the sense that even when \textit{cover} = \textbf{true}, it will attempt to use up the vertex and arc budgets as checked in line 34. If another vertex/arc can still be proposed for failure, then a new iteration in the While loop starts in line 3. Thus, the heuristics ends at either lines 10 or 35.

\begin{algorithm}[tbp]

	\algorithmicrequire{ A set of matchings $W$}\\
	\algorithmicensure{ Failure scenario $\bar{\bm{\gamma}}$ and a boolean variable \textit{cover}\ indicating whether $\bar{\bm{\gamma}}$ covers matchings in $W$}

    \begin{algorithmic}[1]
    \item[] \textbf{Step 0: }
    \STATE \textit{cover} $=$ \textbf{false}
    ; $E \gets \textbf{UniqueElms}(W)$
    \item[] \textbf{Step 1: }
        \WHILE{\textit{true}}
        \STATE $\mathcal{E} = \emptyset$
        \FOR{$n = 1,..., \lvert E \rvert$}
            \IF{$\text{e}_{n} \in A$ and $s_{n} =$ \textbf{false} and $\sum_{u \in V} \bar{\bm{\gamma}}_{u}^{\text{v}}  < r^{\text{v}}$}
            \STATE $\text{w}_{n} = \text{\textbf{Weight}}(W)$
            ; $\mathcal{E} \gets \mathcal{E} \cup \{\text{e}_{n}\}$
            \ELSIF{$\text{e}_{n} \in V$ and $s_{n} =$ \textbf{false} and $\sum_{(\vertexa,\vertexb) \in A} \bar{\bm{\gamma}}_{\vertexa\vertexb}^{\text{a}} < r^{\text{a}}$}
            \STATE $\text{w}_{n} = \text{\textbf{Weight}}(W)$
            ; $\mathcal{E} \gets \mathcal{E} \cup \{\text{e}_{n}\}$
            \ENDIF
        \ENDFOR
        \IF{$\mathcal{E} = \emptyset$}
        \STATE Go to \textbf{Step 2}
        \ENDIF
        \STATE Sort $\mathcal{E}$ in non-increasing order of values s.t. $\text{w}_{1} \ge \text{w}_{2} ...\ge \text{w}_{\lvert E \rvert}$
        \STATE Select $\Elem^\star_{n} \in \mathcal{E}$ randomly among elements whose weight equals $\text{w}_{1}$
        \STATE \textit{ans} = \textbf{true}
        \item[] \textbf{---Start single-vertex-arc separation \ref{vxtarcsep}---}
        \IF{$(\sum_{u \in V} \bar{\bm{\gamma}}_{u}^{\text{v}} + \sum_{(\vertexa,\vertexb) \in A} \bar{\bm{\gamma}}_{\vertexa\vertexb}^{\text{a}}) \ge 1$ and $\text{\textbf{IsNDD}}(\Elem^\star_{n}) = \textbf{false}$ and $(\sum_{(\vertexa,\vertexb) \in A} \bar{\bm{\gamma}}_{\vertexa\vertexb}^{\text{a}} \ge 1 \text{ or } \sum_{u \in V} \bar{\bm{\gamma}}_{u}^{\text{v}} \ge 2)$}
        \STATE $V(\tilde{\oneCe}^{\text{v}}) \gets V(\bar{\bm{\gamma}}^{\text{v}})$; $A(\tilde{\oneCe}^{\text{a}}) \gets A(\bar{\bm{\gamma}}^{\text{a}})$
        \STATE \textit{ans} = \textbf{false}
            \IF{$\Elem^\star_{n} \in V$}
                \STATE $\bar{v} \gets \Elem^\star_{n}$; $C^{\policy, \bar{\vertexb}}(\varFirst) \gets$ Check Case \ref{CaseOne}
                \IF{$C^{\policy, \bar{\vertexb}}(\varFirst) \neq \emptyset$}
                    \STATE \textit{ans} = \textbf{true}
                \ENDIF
            \ELSE
                \STATE $\bar{a} \gets \Elem^\star_{n}$; $C^{\policy,\bar{a}}(\varFirst) \gets $ Check Case \ref{CaseTwo}
                \IF{$C^{\policy,\bar{a}}(\varFirst) \neq \emptyset$}
                    \STATE \textit{ans} = \textbf{true}
                \ENDIF
            \ENDIF
        \ENDIF
        \item[] \textbf{---End separation---}
        \STATE $\Elem^\star_{n} = \text{\textbf{true}}$
        \IF{\textit{ans} = \textbf{true}}
            \IF{$\Elem^\star_{n} \in V $}
                \STATE  $\bar{\bm{\gamma}}^{\text{v}}_{\Elem^\star_{n}} = 1$; $s_{n} =$ \textbf{true}  $\forall \ \text{e}_{n} \in \delta^{+}(\Elemstar_{n}) \cup \delta^{-}(\Elemstar_{n})$
            \ELSE
                \STATE  $\bar{\bm{\gamma}}^{\text{a}}_{\Elem^\star_{n}} = 1$
            \ENDIF
        \ENDIF
        \IF{$\bar{\bm{\gamma}} \text{ covers all matchings in }  W$}
            \STATE \textit{cover} = \textbf{true}
        \ENDIF
        \IF{\textit{cover} = \textbf{true}}
            \IF{$\sum_{u \in V} \bar{\bm{\gamma}}_{u}^{\text{v}} = r^{\text{v}}$ and $\sum_{(\vertexa,\vertexb) \in A} \bar{\bm{\gamma}}_{\vertexa\vertexb}^{\text{a}} = r^{\text{a}}$}
                \STATE Go to \textbf{Step 2}
            \ENDIF
        \ENDIF
        \ENDWHILE
        \STATE \textbf{Step 2: } Return $\bar{\bm{\gamma}}$ and \textit{cover}
	\caption{Heuristics}
	\label{Alg:Heuristics}
	\end{algorithmic}
\end{algorithm}

\section{Computational Experiments}
\label{Experiments}

In this section we present the results of our computational experience. We use the same instances tested in \citep{Blom2021, Carvalho2020}. Although, there are three sets, each with 20, 50 and 100 vertices, our analysis focuses on the set with 100 vertices for performance purposes under homogeneous failure and on the sets 50 and 100 for our policy-based analysis under the non-homogeneous case. There are 30 instances within every instance set. In the first part of this section, we compare the efficiency of our solution approaches with respect to the state-of-the-art algorithm addressing the full-recourse policy under homogeneous failure, Benders-PICEF, proposed in \citep{Blom2021}. In the second part, we analyze the performance and practical impacts of our approaches under non-homogeneous failure for the two policies presented in Section \ref{sec:RecoursePolicies}.  All our implementations are coded in C++, including the state-of-the-art algorithm we compare against, on a machine with Debian GNU/Linux as operating system and a 3.60GHz processor Intel(R) Core(TM). We use CPLEX 12.10 as an LP/MIP solver across all algorithms. A time limit of one hour is given to every run. The TR value for the HSA\_ MB and HSA\_ME algorithms was 150 iterations across all runs.

\subsection{Benchmark under homogeneous failure}

Current state of the art algorithms only address homogeneous failure \citep{Carvalho2020, Blom2021} where a worst-case scenario can be found by only considering vertices. In this section, we compare our solution algorithms under non-homogeneous failure with the Benders-type of decomposition proposed by \citet{Blom2021} for the full-recourse policy, referred to as Benders-PICEF. Benders-PICEF is a decomposition whose master problem and sub-problem (recourse problem), are hybrid formulations adapting aspects of the position-indexed formulation proposed by \citet{Dickerson2016} to model chains and aspects of the cycle formulation to model cycles. Unlike the implementation in \citep{Blom2021}, our implementation of Benders-PICEF generates and stores in memory cycles from the transitory graph given a first-stage solution, which we used to build their position-indexed recourse formulation.

Figure \ref{fig:Performance} shows the performance profile for five algorithms, one of them being Benders-PICEF. The other four correspond to the solution algorithms proposed in this work: FBSA\_MB, FBSA\_ME, HSA\_MB and HSA\_ME. Recall that FBSA\_MB and FBSA\_ME do not transition to their optimization problem counterpart, \ref{objMPOpt}. Among the two, Figure \ref{fig:Performance} shows that solving the recourse problem in the transitory graph pays off for FBSA\_ME. Although Benders-PICEF solves more instances in general than FBSA\_MB and FBSA\_ME, the performance of FBSA\_ME noticeably outperforms that of Benders-PICEF when the maximum length of cycles is four and that of chains is three and up to three vertices are allowed to fail. In the same settings, FBSA\_MB is comparable to Benders-PICEF. However, as soon as the feasibility-seeking master problems transition to their optimization counterpart, the performance of HSA\_MB and HSA\_ME is consistently ahead across all other algorithms and settings. As we show shortly, in most cases HSA\_MB and HSA\_ME need a small percentage of iterations in the optimization version of the master problem of the second stage to converge. Benders-PICEF is substantially fast when cycles and chains of size up to three and four are considered, respectively. The increase in the cycle length and budget failure make it challenging for Benders-PICEF to keep up.

\begin{figure}[tbp]
  \centering
  \includegraphics[width=\linewidth]{Figures/performance_profile.pdf}
  \caption{Performance profile for multiple $r^{\text{v}}$ values and $r^{\text{a}} = 0$ under full recourse}
  \label{fig:Performance}
\end{figure}

Table \ref{tab:performance} summarizes the behaviour of FBSA\_ME, HSA\_ME and Benders-PICEF. We start by explaining the lower level columns in the table that have not yet been defined. Starting on the left-hand side of the table we find column total, which corresponds to the average total time spent optimizing an instance. Then, columns Alg\ref{Alg:Heuristics}, \ref{MasterExp},  \ref{RecoP:Objexp}, CG and \ref{objMPOpt} correspond to the average percentage of time that a run spent on the following items in the second stage, in that order: time spent by the heuristics in Algorithm \ref{Alg:Heuristics} while attempting to find a feasible scenario in \ref{MasterExp}, time solving \ref{MasterExp} as a MIP instance when the heuristics failed to find a feasible scenario, time solving the recourse problem \ref{RecoP:Objexp} as a MIP instance when the CG algorithm failed to find an optimal recourse solution and the time spent by the CG algorithm attempting to solve to optimality the recourse problem \ref{RecoP:Objexp} and lastly, the time spent solving \ref{objMPOpt} as a MIP instance when more than TR = 150 iterations passed without \ref{MasterExp} becoming infeasible. The remaining percentage of time to complete 100\% of the total time corresponds to solving the first-stage formulation and finding cycles/chains for the transitory graph. Following the left-to-right order, there is columns 1stS and 2SndS. 1stS indicates the average total number of first-stage decisions that were required before finding the robust solution. 2SndS is the average total number of iterations spent on solving the second-stage problem for all the first-stage decisions. That is, on average column 2SndS over column 1stS indicates the number of iterations that were needed per first-stage iteration to solve the second-stage problem. Then, columns Alg\ref{Alg:Heuristics}-true, \ref{MasterExp},  \ref{RecoP:Objexp}, CG-true and \ref{objMPOpt} indicate the average total number of iterations spent on each of those processes. Particularly, column Alg\ref{Alg:Heuristics}-true indicates the average number of iterations the heuristics successfully found a feasible failure scenario. Its corresponding column on the average percentage with respect to the total time does include all iterations spent by the heuristics (those in column 2SndS), regardless of whether it was successful or not. Similarly, column CG-true indicates the average total number of iterations the CG algorithm found an optimal recourse solution. Also, note the column Time-CG does include the total time taken by the CG algorithm to run regardless of its result. To know the average number of iterations per first-stage iteration, the previous columns should be divided by column 1stS.

The first observation is that the CG algorithm successfully finds optimal recourse solutions in most cases and it is responsible for most of the average total time for FBSA\_BE and HSA\_ME.
On the other hand, the average total number of iterations needed by FBSA\_ME to converge were significantly higher than those needed by HSA\_ME and yet the average total time per iteration of the second stage with respect to the total time (2ndS/total) is efficient. FBSA\_ME clearly generates scenarios that \ref{objMPOpt} would not explore for the expressiveness of the cycle-and-chain decision variables and the minimization objective, both properties that FBSA\_MB and FBSA\_ME lack. However, also for the full recourse policy, \citet{Blom2021} tested a master problem analogous to \ref{objMPOpt} and showed that due to the large number of cycles and chains in the formulation, its scalability is limited as the size of cycles and chains grows. In fact, when looking at the average number of iterations spent on \ref{objMPOpt} and its corresponding percentage of the total time, and then comparing those two columns for Alg\ref{Alg:Heuristics} and \ref{MasterExp}, we see that (i) the heuristics even when close to 1700 iterations, only accounts for about 26\% of the time (ii) even when the heuristics fails and \ref{MasterExp} is solved as a MIP instance, around 1000 iterations are needed to account for about 39\% of the total time, while for \ref{objMPOpt}, only below 200 iterations are needed to account for about the same percentage. Note that a lower bound need not to be found through \ref{objMPOpt}. For instance, we could have obtained it through the master problem of Benders-PICEF (MPBP), whose iterations are less expensive in terms of time when compared to \ref{objMPOpt}. Observe that in some cases the average total number of second iterations spent by HSA\_ME is a third of those spent by FBSA\_ME, indicating that when shortly transitioning to \ref{objMPOpt}, the hybrid algorithms are able to converge quickly in all the tested settings. This short transition is seen when dividing the average total number of iterations spent on the second stage (2ndS) over the ones spent on the first stage (1stS). Recall that iterations above TR = 150 are the ones spent on solving \ref{objMPOpt} for a given first-stage decision. Thus, the feasibility-seeking master problems are able to find near-optimal failure scenarios within the first hundreds of iterations but in the absence of a lower bound, may require thousands to reach infeasibility and thus prove optimality.

\begin{table}[tbp]
    \caption{Performance comparison of FBSA\_ME, HSA\_ME and Benders-PICEF under homogeneous failure and full recourse for $\lvertP \rvert = 100$. MPBP and RPBP are the master problem and   recourse problem presented in \citep{Blom2021}, respectively. A column is left empty if it does not apply. Data includes all runs.}
    \label{tab:performance}
    \begin{adjustbox}{width=1\textwidth}
        \centering
        \input{99_table_performance}
    \end{adjustbox}
\end{table}

\subsection{Analysis under non-homogeneous failure}
In this part of the analysis, we focus on understanding both the scalability of the solution algorithms under non-homogeneous failure and the impact of the two studied recourse policies on the total number of pairs that can be re-arranged into new cycles and chains, and the percentage of those that correspond to highly-sensitized patients. Pairs in the instances published by \cite{Carvalho2020} have an associated panel reactive antibody (PRA), which determines how likely is that a patient may reject a potential donor. The higher this value the more sensitized a patient becomes and thus a patient is less likely to get a compatible donor. Typically, a patient with a PRA greater or equal to 90\% is considered highly sensitized. Table \ref{tab:policiesk3} summarizes the results  when the solution algorithm used is HSA\_MB and the longest cycle has three exchanges.  A similar table for cycle length four is presented in Appendix \ref{CycleLengthFourNonHomoFail}. In addition to the columns described for Table \ref{tab:performance}, there are three new ones: $r^{\text{a}}$, HSP(\%) and DomS. $r^{\text{a}}$ is the average number of arcs that fail in an instance set, corresponding to either 5\% or 10\% of the arcs in the deterministic solution of an instance. Thus, in this column there are two unique values corresponding to 5\% or 10\% of those arcs. Column $r^{\text{v}}$ corresponds as before, to the  maximum number of failed vertices. HSP(\%) refers to the average percentage of highly-sensitized patients (PRA $>$ 90\%) that are able to be re-arranged into new cycles and chains in the second stage with respect to the total number of highly-sensitized patients in that instance. DomS is the average total number of dominated scenarios that are found by the single-vertex-arc separation procedure described in Section \ref{vxtarcsep}. The average total number of dominated scenarios for instances in Table \ref{tab:performance} was negligible and thus, not presented. The data in this table includes all runs, optimal or not, except for column HSP(\%) where only instances that were solved to optimality are included. In terms of performance, the non-homogeneous case is more difficult to solve to judge by  the average total time (total), the average total number of first-stage iterations (1stS), and the average percentage of time with respect to the total that takes solving the optimality problem \ref{objMPOpt} after 150 iterations (\ref{objMPOpt}(\%)). The average number of dominated scenarios is particularly high for the first-stage-only recourse. This behaviour may be explained because when a failure occurs, the transitory graph under this policy is smaller and thus more susceptible to having vertices and arcs that cannot longer be part of cycles and chains. In terms of the robust objective, all instances that were able to be solved optimally under both policies, obtained the same objective. This interesting fact, indicates that for the tested instances, there exists a set of transplants that allow to recover pairs among themselves, and they are as many as those that can be recovered by the full-recourse policy. The percentage of highly-sensitized patients that can be recovered vary, being 30\% approximately the average. It seems to increase for larger instances and when the recourse policy considered is the first-stage-only recourse. The length of chains does seem to have a positive effect on some settings but it is not a generalized effect. Naturally, the fact that there are runs for which the optimal robust value is unknown indicates the analysis is not yet conclusive.

\begin{table}[tbp]
    \caption{Policies comparison for $K = 3$ under HSA\_MB and non-homogeneous failure.}
    \label{tab:policiesk3}
    \begin{adjustbox}{width=\textwidth}
        \centering
        \input{policies_table_K3_aBudget_5_10}
    \end{adjustbox}
\end{table}

\section{Conclusion}
\label{sec:Conclusion}
We present a general solution framework for KPDPs to find robust matchings that after failure can be repaired through a predefined recourse policy. We achieve this goal by solving a two-stage RO problem. We showed two decompositions where the master problems are a feasibility-seeking problem, which only require a polynomial number of decision variables, a desirable property for scalability purposes. This advantage comes at the price of easily computing a lower bound. To overcome this drawback, we proposed separating a family of dominated scenarios using a heuristics that also attempts to find a feasible failure scenario to the master problems. Our final solution algorithms solve the two-stage robust problem exactly. We compared our solution methods with the state of the art under homogeneous failure, since our work is the first attempt to solve the two-stage robust problem in kidney exchange under non-homogeneous failure. Some of our algorithms are capable to outperform the state of the art in some settings when no lower bound is known. When allowing our feasibility-based solution algorithms to transition to their optimization counterpart, they consistently outperform the state-of-the-art algorithm. On the other hand, under non-homogeneous failure, we compared the two policies studied in this paper in terms of efficiency but also in terms of their ability to re-assign highly-sensitized patients into new cycles and chains. We found that although the percentage of highly-sensitized that can be re-arranged varies across runs, in most cases at least 30\% of highly-sensitized patients seem to be recovered in the second stage.

\section{Robust formulation for full recourse}
\label{sec:fullROFormulation}
Our solution approach supports the use of any MIP formulation that has the structure shown in Section \ref{RobustModels}. For the results presented in this paper, we adapt a variant presented by \cite{Carvalho2020} of the position-indexed cycle edge formulation (PICEF) proposed by \cite{Dickerson2016}. Cycles are modeled through cycle variables $z_c \ \forall c \in \mathcal{C}_{\cycleCap}$ for first-stage decisions and through $\varRecoZ_\match^{\oneCe} \ \forall c \in \mathcal{C}_{\cycleCap}$  for recourse cycles under scenario $\bm{\oneCeS} \in \Gamma$.  Chains, on the other hand, are modeled through first-stage decision variables $\delta_{\vertexa\vertexb\ell}$, indexed by arc $(\vertexa,\vertexb) \in A$ and the feasible position $\ell \in \mathcal{L}(\vertexa, \vertexb)$ of that arc within a chain. The set $\mathcal{L}(\vertexa, \vertexb) \subseteq \mathcal{L} = \{1,...,L\}$ corresponds to the set of positions for which that arc is reached from some singleton donor in a simple path with $\ell \le L$ arcs. For vertices $u \in N$, the set of possible arc positions becomes $\mathcal{L}(\vertexa, \vertexb)  = \{1\}$, since singleton donors always start a chain. To identify $\mathcal{L}(\vertexa, \vertexb)$ for the other arcs, a shortest-path based search can be performed \citep{Dickerson2016}. Likewise, recourse chain decision variables for every scenario $\bm{\oneCeS} \in \Gamma$ are denoted by $\delta^{\oneCe}_{\vertexa\vertexb\ell}$. A binary decision variable $t^{\oneCe}_{\vertexb}$ is also defined for every pair $v \in P$ and scenario $\bm{\oneCeS} \in \Gamma$ to identify the pairs that are selected in both the first stage and in the second stage under some scenario $\bm{\oneCeS} \in \Gamma$. Moreover, we denote by $\cycleSet^{\vertexb}$ and $\cycleSet^{\vertexa\vertexb}$ the set of feasible cycles including vertex $v \in P$ and the set of feasible cycles including arc $(\vertexa,\vertexb) \in A$.
\label{FullFirstSFormulation}
\begin{subequations}
\begin{align}
    \max \qquad Z \label{objmaxRO}\\
    Z - \sum_{v \in P} t^{\oneCe}_{\vertexb} \le 0 && \bm{\oneCeS} \in \Gamma \label{selidxF}\\
    t^{\oneCe}_{\vertexb} - \sum_{c \in \cycleSet^{\vertexb}} z_c - \sum_{\ell \in \mathcal{L}} \sum_{(\vertexa,\vertexb) \in \arcSet_{\ell}} \delta_{\vertexa\vertexb\ell} \le 0 && \bm{\oneCeS} \in \Gamma, v \in P \label{FirstSSol}\\
    t^{\oneCe}_{\vertexb} - \sum_{c \in \cycleSet^{\vertexb}} \varRecoZ_\match^{\oneCe} - \sum_{\ell \in \mathcal{L}} \sum_{(\vertexa,\vertexb) \in \arcSet_{\ell}} \delta^{\oneCe}_{\vertexa\vertexb\ell} \le 0 && \bm{\oneCeS} \in \Gamma, v \in P \label{SecondSSol}\\
    \sum_{u: (\vertexb,\vertexa)}\delta^{\oneCe}_{\vertexb\vertexa 1} \le 1 - \gamma^{\text{v}}_{v} && \bm{\oneCeS} \in \Gamma, v \in N \label{FailedNDD}\\
    \sum_{c \in \cycleSet^{\vertexb}} \varRecoZ_\match^{\oneCe} - \sum_{\ell \in \mathcal{L}} \sum_{(\vertexa,\vertexb) \in \arcSet_{\ell}} \delta^{\oneCe}_{\vertexa\vertexb\ell} \le 1 - \gamma^{\text{v}}_{v} && \bm{\oneCeS} \in \Gamma, v \in P \label{FailedPair}\\
    \sum_{c \in \cycleSet^{\vertexa\vertexb}} \varRecoZ_\match^{\oneCe} - \sum_{\ell \in \mathcal{L}(\vertexa, \vertexb)} \delta^{\oneCe}_{\vertexa\vertexb\ell} \le 1 - \gamma^{\text{a}}_{\vertexa\vertexb} && \bm{\oneCeS} \in \Gamma, (\vertexa,\vertexb) \in A \label{FailedArc}\\
    \sum_{u:(\vertexa,\vertexb) \in \arcSet_{\ell}} \delta^{\oneCe}_{\vertexa\vertexb\ell} -  \sum_{u:(\vertexb,\vertexa) \in \arcSet_{\ell}} \delta^{\oneCe}_{\vertexb\vertexa(\ell + 1)} \le 0 && \bm{\oneCeS} \in \Gamma, v \in P, \ell \in \mathcal{L} \setminus \{L - 1\} \label{ChainPos}\\
    \sum_{u: (\vertexb,\vertexa)}\delta_{\vertexb\vertexa 1} \le 1 && v \in N \label{FailedNDDf}\\
    \sum_{c \in \cycleSet^{\vertexb}} \varRecoZ_\match - \sum_{\ell \in \mathcal{L}} \sum_{(\vertexa,\vertexb) \in \arcSet_{\ell}} \delta_{\vertexa\vertexb\ell} \le 1 && v \in P\\
    \sum_{u:(\vertexa,\vertexb) \in \arcSet_{\ell}} \delta_{\vertexa\vertexb\ell} -  \sum_{u:(\vertexb,\vertexa) \in \arcSet_{\ell}} \delta_{\vertexb\vertexa(\ell + 1)} \le 0 && \bm{\oneCeS} \in \Gamma, v \in P, \ell \in \mathcal{L} \setminus \{L - 1\} \label{ChainPosf}\\
    t^{\oneCe}_{\vertexb} \ge 0 && \bm{\oneCeS} \in \Gamma, v \in P\\
    z_c, \varRecoZ_\match^{\oneCe} \in \{0,1\} && \bm{\oneCeS} \in \Gamma, c \in \mathcal{C}_{\cycleCap}\\
    \delta_{\vertexa\vertexb\ell}, \delta^{\oneCe}_{\vertexa\vertexb\ell} \in \{0,1\} && \bm{\oneCeS} \in \Gamma, (\vertexa,\vertexb) \in A, \ell \in \mathcal{L}(\vertexa, \vertexb) \label{varNature}
\end{align}
\label{for:PICEF_RO}
\end{subequations}

Constraints \eqref{selidxF} are used to determine the scenario binding the number of patients that receive a transplant in both stages. Such scenario is the worst-case scenario. The objective \eqref{objmaxRO} is then equivalent to the maximum number of patients from the first stage that can be recovered in the second stage under the worst-case scenario.  Constraints \eqref{FirstSSol} and \eqref{SecondSSol} assure that a pair $v$ is counted as recovered in the objective if it is selected in the first-stage solution (Constraints \eqref{FirstSSol}) and it is also selected in the second stage under scenario $\bm{\oneCeS} \in \Gamma$ (Constraints \eqref{SecondSSol}). Constraints \eqref{FailedNDD} to Constraints \eqref{FailedArc} guarantee that the solution obtained for every scenario $\bm{\oneCeS} \in \Gamma$ is vertex disjoint and only uses non-failed vertices/arcs. Particularly, Constraints \eqref{FailedNDD} assure that if a singleton donor fails under some scenario $\bm{\oneCeS} \in \Gamma$, i.e., $\gamma^{\text{v}}_{v} = 1$ then its corresponding arcs in position one cannot be used to trigger a chain, but if the vertex associated to the single donor does not fail, it can donate to at most one patient in a pair. Similarly, Constraints \eqref{FailedPair} guarantee that if a pair fails, then it cannot be present in neither a cycle nor a chain. Constraints \eqref{FailedArc} ensure that when an arc $(\vertexa,\vertexb) \in A$ fails under some scenario $\bm{\oneCeS} \in \Gamma$, it does not get involved in neither a cycle or a chain. Constraints \eqref{ChainPos} assure the continuity of a chain by selecting arcs in consecutive positions. Constraints \eqref{FailedNDDf} to Constraints \eqref{ChainPosf} select a solution corresponding to matching in the first stage. The remaining constraints correspond to the nature of the decision variables.

\section{Robust formulation for first-stage-only recourse}
\label{sec:fisrtOnlyROFormulation}
In addition to the constraints defining formulation \eqref{for:PICEF_RO}, a new one is introduced to limit the recourse solutions under every scenario to include only vertices that were selected in the first stage.
\begin{subequations}
\label{FirstStageOnlyFormulation}
\begin{align}
    \max \qquad &Z \\
    \ref{selidxF} &-\ref{varNature}&\\
    \sum_{c \in \cycleSet^{\vertexb}} \varRecoZ_\match^{\oneCe} - \sum_{\ell \in \mathcal{L}} \sum_{(\vertexa,\vertexb) \in \arcSet_{\ell}} \delta^{\oneCe}_{\vertexa\vertexb\ell} &\le \sum_{c \in \cycleSet^{\vertexb}} z_c - \sum_{\ell \in \mathcal{L}} \sum_{(\vertexa,\vertexb) \in \arcSet_{\ell}} \delta_{\vertexa\vertexb\ell} & \bm{\oneCeS} \in \Gamma, v \in P
\end{align}
\end{subequations}

\section{The recourse problem}
\label{Alg:CyChrecourse}

We present in this section two algorithms to enumerate the feasible cycles and chains in $\mathcal{C}_{\cycleCap}^{\pi}(\varFirstPlain)$ and $\mathcal{C}_{\chainCap}^{\pi}(\varFirstPlain)$, respectively, that leads to a transitory graph $D^{\pi}(\varFirstPlain)$ and a a realization of the second-stage compatibility graph $D^{\pi}(\varFirstPlain, \bm{\oneCeS})$ under scenario $\bm{\oneCeS} \in \bigsCe(\varFirst)$.

\subsection{Cycles and chains for the full-recourse policy}

We start by defining some notation. Let $\pairSet(\varFirstPlain) = V(\varFirstPlain) \cap P$ be an auxiliary set, corresponding to the pairs selected in the first-stage solution. Moreover, we denote by $\mathcal{C}_{K}^{u}$  the set of feasible \textit{cycles} that include vertex $u \in \pairSet(\varFirstPlain)$. Lastly, consider $R$ as an auxiliary vertex set. Algorithm \ref{Alg:FullRecoCycleSet} iteratively builds $\mathcal{C}_{\cycleCap}^{\text{Full}}(\varFirstPlain)$. At the start $R$ and $\mathcal{C}_{\cycleCap}^{\text{Full}}(\varFirstPlain)$ are empty. Within the While loop, a pair $u$ from the first-stage solution is selected. Then, in line 4, a deep search procedure, starting from vertex $u$, is used to find $\mathcal{C}_{K}^{u}$ in graph $\tilde{D} = (V \setminus R, A)$. Note that if $R \neq \emptyset$, the new cycles are found in a graph where the previous selected vertices (the ones in set $R$) are removed, since otherwise, cycles already in $\mathcal{C}_{K}^{u}$ could be found again. The new cycles are then added to $\mathcal{C}_{\cycleCap}^{\text{Full}}(\varFirstPlain)$ and vertex $u$ is removed from $P(\varFirstPlain)$. When no more vertices are left in that set, the algorithm ends.

\begin{algorithm}[tbp]

	\algorithmicrequire { Set with pairs from the first-stage solution, $\pairSet(\varFirstPlain)$}\\
	\algorithmicensure { Set $\mathcal{C}_{\cycleCap}^{\text{Full}}(\varFirstPlain)$}
    \begin{algorithmic}[1]
    \item[] \textbf{Step 0: }
	\STATE  $R = \emptyset$; $\mathcal{C}_{\cycleCap}^{\text{Full}}(\varFirstPlain) = \emptyset$  \\
	\item[] \textbf{Step 1: }
	\WHILE{$\pairSet(\varFirstPlain) \neq \emptyset$}
	\STATE \text{Select vertex} $u \in \pairSet(\varFirstPlain) $
	\STATE \text{Find} $\mathcal{C}_{K}^{u}$ \text{in graph } $\tilde{D} = (V \setminus R, A)$ \text{from vertex } $u$

	\STATE $\mathcal{C}_{\cycleCap}^{\text{Full}}(\varFirstPlain) \gets \mathcal{C}_{\cycleCap}^{\text{Full}}(\varFirstPlain) \cup \mathcal{C}_{K}^{u}$
	\STATE $\pairSet(\varFirstPlain)  \gets \pairSet(\varFirstPlain)  \setminus \{u\}$
	\STATE $R \gets R \cup \{u\}$

	\ENDWHILE
	\item[] \textbf{Step 2: }
	\STATE Return $\mathcal{C}_{\cycleCap}^{\text{Full}}(\varFirstPlain)$
	\caption{Obtaining $\mathcal{C}_{\cycleCap}^{\pi}(\varFirstPlain)$ with $\pi = \text{Full}$}
	\label{Alg:FullRecoCycleSet}
	\end{algorithmic}
\end{algorithm}
The correctness of Algorithm \ref{Alg:FullRecoCycleSet} follows from the fact that only cycles/chains with at least one vertex from the first stage contribute to the weight of a recourse solution. Thus, it suffices to find such cycles per every vertex in $\pairSet(\varFirstPlain)$. A similar reasoning is used when finding chains. To this end, we include additional notation. Let $\tilde{N} = N$ be an auxiliary set that corresponds to the set of singleton donors. Moreover, let $\mathcal{C}_{\ell}^{u}$ be the set of chains that include at least one pair in $\pairSet(\varFirstPlain)$ and are triggered by vertex $u \in N$ with exactly $1 \le \ell \le L$ arcs. Algorithm \ref{Alg:FullRecoChainSet} iteratively builds the set of chains that include at least one pair that is selected in the first stage.

\begin{algorithm}[tbp]

	\algorithmicrequire { A first-stage solution $\varFirstPlain \in \mathcal{X}$}\\
	\algorithmicensure { Set $\mathcal{C}_{\chainCap}^{\text{Full}}(\varFirstPlain)$}
    \begin{algorithmic}[1]
    \item[] \textbf{Step 0: }
	\STATE  $R = \emptyset$; $\mathcal{C}_{\chainCap}^{\text{Full}}(\varFirstPlain) = \emptyset$  \\
	\item[] \textbf{Step 1: }
	\WHILE{$\tilde{N} \neq \emptyset$}
    	\STATE \text{Select vertex} $u \in \tilde{N}$
    	\FORALL{$ 1 \le \ell \le L$}
        	\STATE \text{Find} $\mathcal{C}_{\ell}^{u}$ \text{in graph } $\graph = (\vertexSet, \arcSet)$ \text{from vertex } $u$

        	\STATE $\mathcal{C}_{\chainCap}^{\text{Full}}(\varFirstPlain) \gets \mathcal{C}_{\chainCap}^{\text{Full}}(\varFirstPlain) \cup \mathcal{C}_{\ell}^{u}$

        \ENDFOR
        \STATE $\tilde{N} \gets \tilde{N} \setminus \{u\}$
	\ENDWHILE
	\item[] \textbf{Step 2: }
	\STATE Return $\mathcal{C}_{\chainCap}^{\text{Full}}(\varFirstPlain)$
	\caption{Obtaining $\mathcal{C}_{\chainCap}^{\pi}(\varFirstPlain)$ with $\pi = \text{Full}$}
	\label{Alg:FullRecoChainSet}
	\end{algorithmic}
\end{algorithm}

\subsection{Cycles and chains for the first-stage-only recourse policy}

Algorithm \ref{Alg:FullRecoCycleSet} can be modified to accommodate the first-stage-only recourse for cycles. Particularly, we can replace $\mathcal{C}_{\cycleCap}^{\text{Full}}(\varFirstPlain)$ by $\mathcal{C}_{\cycleCap}^{\text{1stSO}}(\varFirstPlain)$, where the latter is the set of simple cycles with at least one vertex in $\pairSet(\varFirstPlain)$ satisfying the first-stage-only recourse policy. In line 4, the vertex set $V$ in graph $\tilde{D}$ is replaced by $\pairSet(\varFirstPlain)$ so that only pairs from the first stage can be part of the allowed cycles. The arc set of $\tilde{D}$ can then be defined such that every arc in it has a starting and terminal vertex in $\pairSet(\varFirstPlain)$. Likewise, Algorithm \ref{Alg:FullRecoChainSet} can also support chains for the first-stage-only recourse. The only change in Algorithm 2, is to replace graph $\graph = (\vertexSet, \arcSet)$ by graph $\tilde{D} = (V(\varFirstPlain), \tilde{A})$ where every arc in the arc set $\tilde{A}$ has both extreme vertices in $V(\varFirstPlain)$.

The algorithms just described are used to obtain the cycles and chains that can participate in a recourse solution when the recourse problem is solved as a sub-problem in the robust decomposition presented in the next section.

\subsection{Formulations for the recourse problem}
\label{sec:RecourseFormls}
In this section we present the cycle-and-chain MIP formulations presented in \citep{Blom2021} adapted to the problem we study. We note, however, that a MIP formulation for the recourse problem does not require the explicit enumeration of cycles and chains. The advantage of enumeration is that different policies can be easily addressed, in particular the full recourse and the first-stage-only recourse.

 Recall that $\cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \subseteq \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)$ is the set of non-failed cycles/chains under scenario $\bm{\oneCeS} \in \Gamma$ and policy $\pi \in \Pi$, i.e., $\sum_{u \in V(c)} \gamma^{\text{v}}_{u} + \sum_{(\vertexa,\vertexb) \in A(c)} \gamma^{\text{a}}_{\vertexa\vertexb} = 0 \ \forall c \in \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS})$. We present the recourse problem based on the so-called cycle formulation \citep{Abraham2007}, as follows:
\begin{subequations}
	\label{RecoPModel}
    \begin{align}
    	R^{\policy}(\varFirst, \oneCe):  \max_{y} \quad&  \sum_{c \in \cyclechainSet^{\policy}{(\varFirst, \oneCe)}}\mathbf{w_{\match}}(\varFirst) y_{c} \label{RecoP:Obj} \tag{R}\\
    	& \sum_{c: u \in V(c)} y_{c} \le  1 &  u \in V \label{eq:uniqueC}\\
    	&y_{c} \in \{0,1\} & c \in \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS})
    \end{align}
\end{subequations}

\noindent Here, $y_{c}$ is a decision variable for every cycle/chain $c \in \cyclechainSet^{\policy}{(\varFirst, \oneCe)}$, taking on value one if selected, and zero otherwise. Constraints \eqref{eq:uniqueC} ensure that a vertex belongs to at most one cycle/chain. An optimal solution to formulation $R^{\policy}(\varFirst, \oneCe)$ finds a matching with the greatest number of matched pairs from the first stage after observing failure scenario $\bm{\oneCeS}$. Thus, by solving formulation \eqref{RecoPModel}, a new Constraint \eqref{eq:solsTwo} can be created.  \cite{Blom2021} proposed to expand recourse solutions by including, in addition to the optimal non-failed cycles/chains found by formulation \eqref{RecoPModel}, failed cycles and chains while guaranteeing that the solution is still a matching. Although, an expanded solution does not contribute to more recourse value under the failure scenario in consideration, it may imply other violated constraints as follows: consider two recourse solutions $\bar{\varReco} \in \setRecoSym_{\text{exp}}^{\policy}(\varFirst, \oneCe)$ and $\hat{\varReco} \in \setRecoSym^{\policy}(\varFirst, \oneCe)$, one in the transitory compatibility graph and another one in the second-stage compatibility graph, respectively, and also assume that $\hat{\varReco} \subseteq \bar{\varReco}$. Then, constraint \eqref{eq:solsTwo} associated to $\hat{\varReco}$ is directly implied by that of $\bar{\varReco}$, i.e., if the constraint corresponding to $\hat{\varReco}$ is violated, so is the constraint corresponding to $\bar{\varReco}$. We find expanded recourse solutions by solving a deterministic KEP in the transitory graph $D^{\pi}(\varFirstPlain)$ instead of the second-stage graph $D^{\pi}(\varFirstPlain, \bm{\oneCeS})$ in formulation \eqref{RecoPModel}, and by assigning new weights to all cycles/chains $c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)$ as in \citep{Blom2021}. The new weights, assigned to each cycle $c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)$, are given by
\begin{align}
\label{expRecoObFcn}
\mathbf{\hat{w}_{\match}}(\varFirst,\oneCe) = \left\{
\begin{array}{ll}
\mathbf{w_{\match}}(\varFirst) \lvert V \rvert + 1      & \mbox{if } V(c) \subseteq V_{\bm{\oneCeS}}\\
1      & \mbox{otherwise }
\end{array}
\right.
\end{align}
We denote by $\Rexp(\varFirst, \oneCe)$ the resulting recourse problem with expanded solutions,
\begin{subequations}
	\label{RecoPModelexp}
    \begin{align}
    	\Rexp(\varFirst, \oneCe):  \max_{y} \quad&  \sum_{c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)}\mathbf{\hat{w}_{\match}}(\varFirst,\oneCe) y_{c} \label{RecoP:Objexp} \tag{RE}\\
    	& \sum_{c: u \in V(c)} y_{c} \le  1 &  u \in V \label{eq:uniqueCexp}\\
    	&y_{c} \in \{0,1\} & c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)
    \end{align}
\end{subequations}
The following lemma, based on \citep{Blom2021}, states that the set of cycles/chains that do not fail in a recourse solution optimal to $\Rexp(\varFirst, \oneCe)$ is an optimal recourse solution to the original recourse problem $R^{\policy}(\varFirst, \oneCe)$.
\begin{lemma}
\label{lemma:exp}
For a recourse solution $\bar{\varReco} \in \setRecoSym_{\text{exp}}^{\policy}(\varFirst, \oneCe)$ that is optimal to $\Rexp(\varFirst, \oneCe)$, its set of non-failed cycles/chains, $\VarRecoOpExp(\oneCe) \subseteq \bar{\varReco}$, under scenario $\bm{\oneCeS} \in \bigsCe(\varFirst)$ is an optimal recourse solution to $R^{\policy}(\varFirst, \oneCe)$.
\end{lemma}
\proof
Let ${Z}^{\pi,\star}_{RE}(\varFirst, \oneCe)$ be the optimal objective value to solution $\bar{\varReco} \in \setRecoSym_{\text{exp}}^{\policy}(\varFirst, \oneCe)$ and consider $\vert V \rvert/2$ as the maximum number of cycles/chains that can originate in a feasible matching, i.e., the maximum number of decision variables for which $\bar{\varReco}_{c} = 1 \forall c \in \cycleSet^{\pi}(\varFirstPlain) \cup \chainSet^{\pi}(\varFirstPlain)$. Moreover, let $\mathbbm{1}_{c}$ be an indicator variable that takes on value one if $\bar{\varReco}_{c} = 1 \forall c \notin \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS})$ and zero otherwise. Then, from \eqref{expRecoObFcn} we know that
\begin{subequations}
    \begin{align}
        {Z}^{\pi,\star}_{RE}(\varFirst, \oneCe) = & \sum_{c \in \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS}): \bar{\varReco}_{c} = 1} \left( \mathbf{w_{\match}}(\varFirst) \lvert V \rvert + 1 \right) + \sum_{c \notin \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS}): \bar{\varReco}_{c} = 1} \mathbbm{1}_{c}
        \\
        =&\lvert V \rvert \sum_{c \in \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS}): \bar{\varReco}_{c} = 1} \mathbf{w_{\match}}(\varFirst)  + \sum_{i = 1}^{\vert V \rvert/2} 1 + \sum_{i = 1}^{\vert V \rvert/2} 1\\
        =&z^{\star}\lvert V \rvert  + \vert V \rvert \label{result}
    \end{align}
\end{subequations}

Now, suppose $\VarRecoOpExp(\oneCe)$ is not optimal to $R^{\policy}(\varFirst, \oneCe)$, therefore $\sum_{c \in \cycleSet^{\pi}(\varFirstPlain, \bm{\oneCeS}) \cup \chainSet^{\pi}(\varFirstPlain, \bm{\oneCeS}): \bar{\varReco}_{c} = 1} \mathbf{w_{\match}}(\varFirst)$ can be at most $z^{\star} - 1$. If that is true, then, when replacing $z^{\star}$ in \eqref{result} by $z^{\star} - 1$, we obtain that  ${Z}^{\pi,\star}_{RE}(\varFirst, \oneCe) = z^{\star}\lvert V \rvert  + \vert V \rvert = z^{\star}\lvert V \rvert$, which is a contradiction. Thus, it follows that $\VarRecoOpExp(\oneCe)$ must be optimal to $R^{\policy}(\varFirst, \oneCe)$. \hfill$\square$

It is worth noting that we formulated the recourse problem by means of cycle-and-chain decision variables, but since it is reduced to a deterministic KEP, the recourse problem can be solved via multiple formulations/algorithms from the literature, e.g., \citep{Omer2022, Blom2021, Riascos2020}.

\section{Additional results for non-homogeneous failure}
\label{CycleLengthFourNonHomoFail}
The data  in Table \ref{tab:policiesk4} includes all runs, optimal or not, except for column HSP(\%) where only instances that were solved to optimality are included. The interpretation of the displayed columns correspond to those in Table \ref{tab:policiesk3}.

\begin{table}[htpb]
    \caption{Policies comparison for $K = 4$ under HSA\_MB and non-homogeneous failure.}
    \label{tab:policiesk4}
    \begin{adjustbox}{width=\textwidth}
        \centering
        \input{policies_table_K4_aBudget_5_10}
    \end{adjustbox}
\end{table}

redpajama_set_name: RedPajamaArXiv