%!Tex root=./SEMR_Template_en.tex
\section{Problem Statement}\label{sec:ps}

\subsection{Informal description}
It is convenient to setup the E2TTP in terms of a given transportation network~$G$ two its nodes - \textit{supplier} and \textit{consumer} -  are dedicated and called \textit{terminals}. Direct link providing transportation from some node $u$  to node $v$ is represented by the arc $e=(u,v)$, which is assigned by a \textit{cost} (charge of use) $c_e$ and \textit{reliability} $p_e$. It is assumed that each arc can be unavailable with probability $q_e=1-p_e$ independently of all others. 
For each subnet $G'\subset G$, its cost accumulates the costs of all the constituent arcs, while the reliability is equal to the probability that terminals $s$ and $t$ are turn to be connected in $G'$.  
%Also, we are given a dedicated terminals $s$ and $t$. 
% Then, we aim to find a subset of links of minimum total charges such that $s$ and $t$ are connected with a probability at least the given threshold or, that is the same, disconnected at most with a given failure one.  

Thus, the goal is to minimize cost of a subnet $G'$, subject to the constraint on its reliability to be no lower than the given probability threshold.  

% containing the terminals $s$ and $t$ such that the terminals $s$ and $t$ are connected with a probability at least the given threshold $1-\F$ or, that is the same, disconnected with a probability at most $\F$. 

\subsection{Mathematical formulation}

An arbitrary instance of the E2TRP is given by a tuple $(G, s, t, \F)$, where
\begin{enumerate}
	\item[(i)] $G=(V,E,c,p)$ is an edge-weighted digraph, such that 
	\begin{enumerate}
		\item[-] the node set $V$ contains supplier $s$ and consumer $t$;%  $\{s,t\}$;
		\item[-] the weighting functions $c\colon E\to\RR_+$ and $p\colon E\to[0,1]$, to any arc $e\in E$,  assign  its cost $c_e$ and reliability $p_e$, respectively;
	\end{enumerate}
	\item[(ii)] the value $0<\F<1$ is a given unreliability threshold. 
\end{enumerate}
We rely on the classic generalized Erd\H{o}s-R\'enyi model (see, e.g. \cite{Bollobas2001}). According to this model, the arcs of $G$ fail mutually independently, such that each $e\in E$ turns to be unavailable (fails) with a given probability $q_e=1-p_e$. 


A non-empty subgraph $G'=(V',E')\subset G$,  $\{s,t\}\subset V'$, is called a feasible solution of E2TRP, if terminals $s$ and $t$ are connected in $G'$ with probability at least $1-\F$.  
% \begin{enumerate}
% 	\item[(i)] $\{s,t\}\in V'$;
% 	% \item[(ii)] $s$ and $t$ nodes are disconnected with a failure probability at most $\F$. 
% 	\item[(ii)] the nodes $s$ and $t$ are connected with a probability at least $1-\F$.
% \end{enumerate}

% For any feasible solution $G'$, its cost is defined by the formula 
The goal is to find a minimum cost feasible solution $G'$, where \[\text{cost}(G')=\sum_{e\in E'}c_e.\] 

% Thus, the goal is to find a feasible solution of the minimum cost. 

% Thus, for any {\it route} $\pi$ that is any sequence of arcs the failure probability is defined by the formula
% \begin{equation}
% \Prob(\pi)=1-\prod_{e\in\pi}(1-p_e).\label{eq:route_failure_probability}
% \end{equation}

% Notice, that we can consider $0<p_e<1,\ (e\in E)$ w.l.o.g. Indeed, if $p_e=1$ for some arc $e\in E$, we just remove this arc from the graph $G$ on the preprocessing stage. On the contrary, the value $p_e=0$ means that the arc $e$ never fails and, therefore, makes no contribution in \eqref{eq:route_failure_probability}. 

In the sequel, we assume that, for each arc $e\in E$, $c_e>0$ and $p_e\in (0,1]$. We also assume that $p_e\neq 0$ because otherwise we can just remove an arc $e$ from the graph $G$. Then, w.l.o.g.  we can restrict ourselves to consideration of only feasible solutions that can be represented as a union of some family of possible $s$-$t$-routes $\R$ in the given graph $G$. 
% In turn, for an arbitrary such route $\pi$, its failure   
