%!Tex root=./SEMR_Template_en.tex
\section{Introduction}\label{sec:intro}
Global conflicts, pandemics and economical instability have demonstrated how fragile and uncertain the international trade may be \cite{Bouchery2017}. A recent analysis shows that annually, over 75\% of businesses encounter disruptions in their supply chains resulting from diverse factors, such as labor disputes, logistical delays, severe weather events, fluctuations in currency exchange rates, energy shortages, breakdowns in service provision, and IT system failures (see e.g. \cite{Sundarakani2021}). Therefore, addressing the reliability and resilience of supply chains and their associated networks is a task of critical importance \cite{Dolgui2020}.

% Recent studies have explored strategies such as implementing backup paths, which provide alternative routes for goods and services during disruptions, significantly enhancing network robustness \cite{TANG200812,Ivanov2020}. These backup paths allow supply chains to maintain functionality even when primary paths fail, thereby ensuring operational continuity \cite{Roshani2024}.

% It is worth to mention that random graph models, particularly the Erdős–Rényi model, have been extensively utilized to analyze and enhance supply chain resilience \cite{Dolgui2020}. 

The most straightforward and widely known mathematical model \cite{TANG200812,Ivanov2020} designed to simulate resilient supply chains is represented by a transportation network with dedicated single supplier and customer nodes, whose reliability is described in terms of the classic Erd\"os-R\'{e}nyi random graphs model. In this context, the problem is to minimize total operational cost, subject to reliability constraint.

In their recent paper \cite{Casazza2021}, Casazza and Ceselli introduced a close optimization problem in the field of communication networks, called Resilient Path Selection Problem (RPSP). Their goal was to find an economically efficient subnet of the given network, while providing the reliability guarantees.

Evidently, provided that the network is completely reliable, the RPSP is equivalent to the classic Shortest-Path Problem and solvable to optimality by Dijkstra algorithm. On the other hand, reaching the required level of reliability is quite challenging. In the literature, the problem to verify the reliability constraint for a given network is known as the 2-Terminal Reliability Problem (2-TRP), dated to the seminal papers of Moore and Shannon \cite{MooreShannon} and Valiant \cite{Valiant}. Since its introduction, this problem has been studied exten-sively for decades by researchers in counting complexity and approximation algorithms (see e.g. \cite{Provan1986,Colbourn1991,Zenklusen2011,CenHeLiPan2024}).


In this paper, we introduce the Efficient 2-Terminal Reliability Problem (E2TRP) - an adaptation of both RPSP and 2-TRP for the resilient supply chains. By extending the algorithmic results of \cite{Casazza2021}, we propose an exact branch-and-price algorithm for this problem and show it's ability to obtain feasible, suboptimal, and even optimal solutions by the results of comparative numerical evaluation.



