%!Tex root=./SEMR_Template_en.tex
\section{Branch-and-price algorithm}\label{sec:bpnc}


We start with solution of LP-relaxation of IMP using column generation procedure discussed in Section \ref{sec:mip}. If we managed to find an integer solution satisfying the reliability constraint \eqref{eq:cf2}, which is validated by the application of the classic Moore-Shannon algorithm \cite{MooreShannon}, then we have an optimal solution. Otherwise, we proceed with branching.

\subsection{Branching scheme}\label{ssec:branching_scheme}

Let $(\bar\xi_e,\bar\lambda_p)$ is an optimal solution of LP-relax-ation of the IMP. In the case when the $\bar\xi_e$ values are fractional, we {\it branch on arcs.}

To proceed, we choose the most fractional arc $\tilde e=\text{argmin}_{e\in E}\left|\bar\xi_e-0.5\right|$ and spawn  two child nodes in the branching tree.
In the first child, we append constraint $\xi_{\tilde e}=0$ that implies reduction of edge $\tilde e$ in the node subgraph. Moreover, all routes $\{p\colon x_{\tilde e}^p=1\}$ are declined in the IMP. In the second child, we simplify the IMP objective and remove constraint $\sum_{p}x_{\tilde e}^p\lambda_p\leq M\xi_{\tilde e}$. We should note that in both cases the pricing problem keeps its structure. 

% {\it Probability branching.} 
In the case when the obtained integer solution $\bar\xi_e$ violates the reliability constraint \eqref{eq:cf2}, we proceed with {\it probability branching.}. 
% Any time when a solution with integer $\bar\xi_e$ values is found we obtain a subgraph $G'(V(E'),E')$, $E'=\{e\in E\colon \bar\xi_e=1\}$. Then, we compute the probability  of $s-t$ connectedness $\bar\F$ in $G'$ with the well-known Moore-Shannon algorithm (unlike the Bayesian Network described in \cite{Casazza2021}) and, if $\bar\F\leq\F$, we have found the new incumbent. Otherwise, we should proceed with the branching on the 'subgraphs' in order to get an another solution satisfying the probability condition. 
We spawn two child nodes in the branching tree as follows:
\begin{itemize}
	\item[-] We ruin the subgraph $G'$ by appending the constraint $\sum_{e\in E'}\xi_e\leq |E'|-1$. In other words, we restrict to use the subgraph $G'$ as the part of a solution.
	\item[-] We save the subgraph $G'$ as a part of solution but enhance it by an appropriate way. To append additional edges, we include the following constraints  
	\begin{align*}
	\xi_e=1,\ (e\in E'),\\
	\sum_{e\in E}\xi_e\geq |E'|+1.
	% \sum_{p \in P'}\lambda_p\geq \left\lceil \sum_{p \in P'}\bar\lambda_p \right\rceil+1. &
	\end{align*}
\end{itemize}
Once the child nodes are obtained, we apply the column generation procedure for each of them. By construction, those pricing problems retain their structure as well. 


\subsection{Primal Heuristics}

To speed up the convergence of the search proce-dure, we apply the following primal heuristics in parallel. Each time when some of them manage to find an incumbent solution, we update the record upper bound. 

{\it Start greedy heuristic.} Before the column generation begins, we construct a set of independent routes as follows. At first, we find the shortest route and reduce its corresponding arcs from graph. Then, we repeat it until the graph is $s$-$t$ connected or the probability condition is met. The resulted set of routes will induce a subgraph that is a new incumbent.

{\it Local search.} For any branching node we construct the following model from the routes $\{p\in P'\colon \lambda_p > 0\}$:
    \begin{align}
        \min \sum_{e \in E}c_e \xi_e \\
        \sum_{p \in P'}\tilde{\mathds{P}}(\x^p)\lambda_p \leq \tilde\F \\
        \sum_{p \in P'}x_e^p\lambda_p \leq \xi_e\ (e \in E)\label{eq:constr} \\
        \xi_e \in \{0,1\},\ \lambda_p \in \{0,1\} \label{eq:vars}
    \end{align}
Due to the constraints \eqref{eq:constr} and \eqref{eq:vars}, the obtained solution consists of edge-disjoined $s$-$t$ routes. Therefore, this solution is feasible for the initial E2TRP. 


\subsection{Pruning}

We prune a branch any time when one of the following condition in the current node is met:
\begin{itemize}
	\item the obtained local Lower Bound (LB) is greater than the current Upper Bound (UB) - the cost of the best known incumbent solution;
	\item the nodes $s$ and $t$ are located in different connected components of current subgraph;
	\item integer solution satisfying reliability constraint \eqref{eq:cf2} (incumbent) is found;
	\item the LP-relaxation of the current MP is infeasible.
\end{itemize}

% \subsection{Column generation speed-up techniques}

% To reduce spending time on column generation we apply the following speed-up techniques.

% {\it  The upper bound of the route cost.} To reduce route enumeration number and improve $RMP$ objective the constraint $\sum_{e \in E}c_ex_e \leq UB$ is added to the $IPP$ model where $UB$ is current upper bound value.

% {\it Reducing enumeration number.} In a case, when the value $\bar\alpha>0$ we need to enumerate all posible $d$ values and solve $AUX(d)$ for the each one. Unfortunately, this procedure is exhaustive because of a huge number of $\bar\beta_e>0$. To reduce the enumeration we apply the following technique:
% \begin{itemize}
% 	\item at first, we find a route $p'$ minimizing $\bar\alpha{\mathds{P}}(\x^p)$. Since $\bar\alpha>0$ is a constant, the task is to find the most relible route;
% 	\item if a route $p'$ has negative reduced cost, then we can append it as a new column to the $RMP(P')$;
% 	\item otherwise, we continue the IPP solving and try to find a new route by adding the constraint $\sum_{e \in E(p')}\xi_e \leq |E(p')|-1$ to the subproblem model. Note that a route $p'$ provides minimal value of $\bar\alpha{\mathds{P}}(\x^p)$ and any other route has a value that is greater than or equal to $\bar\alpha{\mathds{P}}(\x^{p'})$ . Therefore, we must reduce the other term $\sum_{e \in E}\bar\beta_e x_e$ to find a solution with a negative reduced cost. To do this, constraints $\sum_{e \in E}\bar\beta_e x_e \leq \sum_{e \in E(p')\bar\beta_e}$ are added and procedure is repeated again.
% \end{itemize}

% {\it Column generation heuristic and reduced cost lower bound.} Whenever $\alpha \neq 0$ before exact subproblem solving the next two procedures are applied.

% The first procedure is a heuristic that tries to find the new shortest route. If such a path has negative reduced cost then we add it as a new column to the $RMP$. Moreover, if cost of this route is greater than $UB$, then we can terminate column generation process.

% The second procedure is to compute the lower bound of a reduced cost. Since $\tilde{\mathds{P}}(\x^p)$ is non-linear function, we can put a constant $\tilde{\mathds{P}}(\x^{p^*})$ instead and minimize linear part of reduced cost $\sum_{e\in E}\bar\beta_e\xi_e$, where $p^*$ is the most reliable route in current solution tree node. If a new route $p'$ has negative reduced cost, then we can add it as a new column to the $RMP$ model. Otherwise, if the following condition is met
% $$
% \bar\alpha\tilde{\mathds{P}}(\x^{p^*}) + \sum_{e \in E(p')}\bar\beta_e - \bar\gamma \geq 0
% $$
% then there is no any route with negative reduced cost and the column generation procedure can be stopped.

% {\it Convergence improvement.} Column generation process can take a lot of time to converge due to the so-called {\it heading-in} and {\it tailing-off} effects. To solve heading-in effect we initialize model in root node by routes satisfying the relaxed probability constaraint \eqref{eq:probability_relaxed}. To cope with the tailing-off effect the early stoping criterion is used. Namelly, if $RMP$ objective value does not change significantly a certain number of iterations then we terminate the column generation process. In our algorithm we do it when objective changes by less then 1 percent during 20 iterations.