%!Tex root=SEMR_Template_en.tex
\section{Related Work}\label{sec:rw}

The E2TRP is closely related to the classic 2-Terminal Reliability Problem, included by Valiant into the list of first thirteen \#P-complete problems \cite{Valiant}. Due to the proven intractability of such problems, many researchers have focused their efforts on design of approximation algorithms and schemes, and finding non-trivial polynomial-time solvable subclasses. In \cite{two-terminal-old}, authors proposed a linear-time algorithm for $k$-TRP over series-parallel networks. 
Subsequent work by \cite{Tanguy2007-1,Tanguy2007-2} examined two-terminal reliability using a product of transfer matrices, accounting for the independent reliability of each edge and node. Further advancements were made in \cite{Zenklusen2011}, where a Monte Carlo-based algorithm was introduced to handle large-scale networks more efficiently. More recently, a fully polynomial-time randomized approximation scheme (FPRAS) was developed for Directed Acyclic Graphs (DAGs) in \cite{Feng2024}.
The obtained results on the 2-TRP and related problems indeed represent state-of-the-art in the field of algorithmic design. Unfortunately, they hardly ap-plicable to an analysis of supply chain resilience, as the aspect of cost mini-mization is being omitted.

% On the other hand, the problem of designing reliable supply chains supply chains, where the goal is the minimization of overall costs was studied extensively in the literature \cite{SABOUHI2021,SAZVAR2021,Sundarakani2021,SURYAWANSHI2022,KATOOZIAN2022,Canas2024}. However, in terms of the algorithmic study, these papers refer to mostly heuristics and metaheuristics, while completely neglecting any accuracy guarantees or even exact algorithms.

Another direction to ensure reliability in networks is related to  design of so-called \textit{backup paths} (see, e.g. \cite{PioroMedhi,Ogorodnikov2022}). In \cite{CHENG201540}, the authors approximated resilience of the supply chain in terms of the resource constrained shortest-path problem. In the similar way, Redmond et al. \cite{Redmond2019} proposed a reliable approach for multi-leg flights. Furthermore, in \cite{Ogorodnikov2024}, backup facility concept was generalized for the case of more complex supply chain topology.
However, as it was shown \cite{Casazza2021}, the approach based on backup paths and facilities can provide solutions that may be far from optimal, or even violate the reliability constraint. 

Finally, the Resilient Path Selection Problem introduced in \cite{Casazza2021}, seems to be the most close to the problem considered in our paper. The authors proposed a MILP-based formulation and the respective branch-and-price algorithm for the RPSP, as well as the results of its competitive numerical evaluation.  Unfortunately, their method exhibited several shortcomings, primarily induced by the non-linearity of the RPSP and intractability of the 2-TRP. In particular, in attempt to improve performance of their algorithm, the authors replaced time-consuming Moore-Shannon algorithm of reliability calculation with a Bayesian Network, which resulted in non-feasible solutions. 

In this paper, we try to bridge some of these gaps. Our contribution is two-fold:
\begin{itemize}
	\item[-] by applying the most recent results \cite{Desrosiers2024} in the field of Dantzig-Wolfe decomposition for integer programs and column generation, we intro-duce a branch-and-price algorithm for the non-linear Efficient 2-Terminal Reliability Problem;
	\item[-] numerical evaluation of the proposed algorithm against the benchmar-king instances from \cite{Casazza2021} demonstrates its ability to obtain feasible and optimal solutions.
\end{itemize}	
