%!Tex root=./SEMR_Template_en.tex
\section{Mixed-integer models}\label{sec:mip}

% As was mentioned in the previous section, the feasible solution of the TTRP is a subgraph $G'$ where $s$ and $t$ are connected with a probability at least $1-\F$. 
% % Such a value can be computed with a famous Moore-Shannon technique \cite{MooreShannon} that is based on the recurrent equations. Unfortunately, it takes an exponential time, and we will use it only as an oracle for the given subgraph $G'$ to determine the probability of $s$-$t$ diconnectness. 
% However, the problem of finding the whole subgraph $G'$ is too hard to implement. To cope with it, we will use the representation $G'$ as a set $\R$ of $s$-$t$ routes and obtain $G'$ with a column generation technique. For the sake of convenience, we will use the probability $\F$ of $s$-$t$ disconnectness as well. 

% In the rest of this section we consider the Compact Formulation (CF) model that we further transform to the Master Problem (MP) with the well-known Dantzig-Wolfe decomposition and propose the Integer Pricing Problem (IPP).

We start with description of a non-linear Integer Programming (IP) model of the considered problem. Following to the terminology proposed in \cite{Desrosiers2024}, we call it an \textit{original} formulation of our problem.   

\subsection{Original formulation}

In our model, we encode an arbitrary feasible solution $G' \subset G$ it terms of the following decision variables:
\begin{enumerate}
	\item[-] $\xi_e\in\{0,1\}$, where $\xi_e = 1$, if $e\in E'$;
	\item[-] $x_0^{\pi}\in\{0,1\}$, where $x_0^{\pi} = 1$, if the route $\pi$ belongs to $G'$;
	\item[-] $x_e^{\pi}\in\{0,1\}$, where $x_e^{\pi} = 1$, if the arc $e$ belongs to $\pi$.
\end{enumerate} 
In addition, we employ the following technical notation: $\mathbf{x}^\pi = [x_0^{\pi}, x_e^{\pi} \colon e\in E]$.
Thus, we obtain the following integer program:
\begin{eqnarray}
\text{(IP)}: \min\sum_{e\in E} c_e\xi_e\label{eq:cf1}\\
\notag
s.t. \phantom{XXXXXXX} \\
{\mathds{P}}(G')\leq \F\label{eq:cf2}\\
x_e^{\pi}\leq\xi_e,\ (e\in E), & (\pi\in \R)\label{eq:cf3}\\
x_e^{\pi}\leq x_{0}^{\pi}, & (e\in E)\label{eq:cf4}\\
\sum_{(i,j)\in E}x_{(i,j)}^{\pi}-\sum_{(j,i)\in E}x_{(j,i)}^{\pi}=
\left\{
\begin{array}{rl}
x_0^{\pi},& i=s\\
-x_0^{\pi},& i=t\\
0,& \text{otherwise}
\end{array}\right. & (\pi\in\R) \label{eq:cf5}\\
{\bf x}^{\pi}\neq{\bf x}^{\sigma}, & (\pi,\sigma\in \R)\label{eq:cf6}\\
x_e^{\pi}, x_0^{\pi}, \xi_e \in\{0,1\}, & \left(\begin{array}{c}e\in E\\ 
\pi\in\R
\end{array}\right)\label{eq:cf7}.
% \xi_e\in\{0,1\} & (e\in E)\label{eq:cf8}.
\end{eqnarray}
The objective \eqref{eq:cf1} is to minimize the cost of the subgraph $G'$, while equation \eqref{eq:cf2} defines a reliability constraint. Equations \eqref{eq:cf3} and \eqref{eq:cf4} establish relations between corresponding decision variables. Equations \eqref{eq:cf5} set the flow conser-vation constraints, while equations \eqref{eq:cf6} guarantee uniqueness of routes that induce subgraph $G'$.

\subsubsection{Probability Relaxation}
Generally speaking, the model IP is non-linear and makes difficult application of the traditional column generation approach. Therefore, we proceed with the relaxation of this model relying on the following technical statement.
\begin{theorem}[\cite{Casazza2021}]\label{thm:1}
Let $\pi_1,\pi_2,\ldots,\pi_k$ be the routes in $G$, where route $\pi_i$ fails with probability ${\mathds{P}}(\pi_i)$, while all of them fail simultaneously with probability \\
${\mathds{P}}(\pi_1,\pi_2,\ldots,\pi_k)$. Then, 
$
\prod_{i = 1}^k{\mathds{P}}(\pi_i)\leq {\mathds{P}}(\pi_1,\pi_2,\ldots,\pi_k).
$
\end{theorem}

Suppose that subgraph $G'$ is induced by some routes $\pi_1,\pi_2,\ldots,\pi_k$. By Theorem \ref{thm:1}, $\prod_{i = 1}^k{\mathds{P}}(\pi_i)\leq {\mathds{P}}(G')$. Therefore, inequality \eqref{eq:cf2} implies \\$\prod_{\pi\in\R}{\mathds{P}}(\pi)^{x_0^\pi}\leq \F$, i.e. 

% The Theorem \ref{thm:1} allows us to relax constraint \eqref{eq:cf2} with $\prod_{\pi_i\in\R}{\mathds{P}}(\pi_i)\leq\F$. In turn, such equation can be easily linearized by taken a logarithm both on the LHS and RHS. Denoting by $\tilde{\mathds{P}}(\pi_i)=\log_2{\mathds{P}}(\pi_i)$ and $\tilde\F=\log_2\F$, we have 
\begin{equation}
\sum_{\pi\in\R}\tilde{\mathds{P}}(\pi)x_0^\pi\leq\tilde\F,\label{eq:probability_relaxed}
\end{equation}
where $\tilde{\mathds{P}}(\pi)=\log_2{\mathds{P}}(\pi)$ and $\tilde\F=\log_2\F$. In the sequel, along with IP model, we consider its relaxation RP, obtained by replacing \eqref{eq:cf2} with \eqref{eq:probability_relaxed}.
\subsection{Dantzig-Wolfe decomposition}

Since both IP and RP are non-compact formulations, we apply the column generation based methods \cite{Desrosiers2024,uchoa2024optimizing}. As it follows from the structure of those formulations, it is convenient to employ the classic Dantzig-Wolfe decomposition.
Indeed, it is easy to see that for an arbitrary route $\pi\in\R$, $\mathbf{x}^\pi\in \D$, where
% The Dantzig-Wolfe decomposition is based on the partition of the CF model constraints onto the two subsets $\A$ and $\D$ that are called {\it linking} and {\it block} \cite{Desrosiers2024}. It is easy to see, that the Compact Formulation has the block-diagonal structure where each block is associated with an appropriate route $\pi$. Hence, the subset $\D$ has the following structure:
$$
\D=\left\{\x\in\{0,1\}^{|E|+1}\left| \begin{array}{cc}\sum\limits_{(i,j)\in E}x_{(i,j)}-\sum\limits_{(j,i)\in E}x_{(j,i)}=&
\begin{cases}
x_0,\ i=s\\
-x_0,\ i=t\\
0,\ \text{otherwise}
\end{cases}\\[5ex]
x_e\leq x_{0}, &\ (e\in E)
\end{array}\right.\right\}.
$$
% Let $\D^\pi$ be the block constraints associated with route $\pi$.

By Minkowski-Weyl theorem, an arbitrary vector $\mathbf{x}\in \text{conv}(\D)$ is represented as a convex combination of the extreme points $p\in P$ of this polytope: 

% Following to the Dantzig-Wolfe decomposition, we should write the vector $\x^\pi\in\D$ as a linear combination of points $P$ and rays $R$ of the convex hull of $\D$:
\begin{eqnarray}
\x=\sum_{p\in P}\x^p\lambda_p\label{eq:DW_dec1}\\
\sum_{p\in P}\lambda_p = 1 \ \lambda_p\geq 0.\label{eq:DW_dec2}
\end{eqnarray}
% where equation \eqref{eq:DW_dec2} is a convex constraint. 
Furthermore, in our case, $P=\D=\R$, and for any $\mathbf{x}^\pi \in \D$, $\x^\pi=\x^p$, $\lambda_p=x_0^p$, for some $p\in P$. 
After substitution of $\mathbf{x}^\pi$ into RP formulation, we obtain the following problem:
\begin{eqnarray}
\min\sum_{e\in E} c_e\xi_e\\
\notag
s.t. \phantom{XXXX}\\
\sum_{p\in P}\tilde{\mathds{P}}(\x^p)\lambda_p\leq\tilde\F\\
x_e^p\lambda_p\leq \xi_e, & \left(\begin{array}{c}\label{eq:aggr}
e\in E, \\
p\in P
\end{array}\right)\\
\lambda_p\in\{0,1\},& (p\in P)\\
\xi_e\in\{0,1\} & (e\in E).
\end{eqnarray}
Further, we aggregate constraints \eqref{eq:aggr} in order to make the obtained Master Problem smaller. In addition, in order to speed-up the subsequent branching procedure, we append the following valid inequality:
\begin{equation}
\sum_{p\in P}\lambda_p\geq k_{min},\label{eq:min_routes}
\end{equation}
where  $k_{min}=\left\lceil\frac{\tilde\F}{\tilde{\mathds{P}}(\x^{p^*})}\right\rceil$, and $p^*$ is the most reliable $s$-$t$ route in graph $G$.

Finally, we obtain the following Integer Master Problem:
% After aggregation of these equations we obtain the following Master Problem:
% Summarizing the above argumentations, we obtain the following Master Problem:
\begin{eqnarray}
\text{(IMP)}: \min\sum_{e\in E} c_e\xi_e\label{eq:mp1}\\
\notag
s.t.\phantom{XXXXXXX}\\
\sum_{p\in P}\tilde{\mathds{P}}(\x^p)\lambda_p\leq\tilde\F\label{eq:mp2}\\
\sum_{p\in P}x_e^p\lambda_p\leq M\xi_e, & (e\in E),\label{eq:mp3}\\
\sum_{p\in P}\lambda_p\geq k_{min},\\\label{eq:mp4}
\lambda_p\in\{0,1\},& (p\in P)\label{eq:mp5}\\
\xi_e\in\{0,1\}, & (e\in E)\label{eq:mp6}
\end{eqnarray}
for an appropriate big number $M$. 

\subsection{Column generation}

We proceed with the LP-relaxation of model \eqref{eq:mp1}-\eqref{eq:mp6} that is obtained by replacing \eqref{eq:mp5} and \eqref{eq:mp6} by $0\leq\lambda_p\leq1$, $(p\in P)$ and $\xi_e\geq0$, $(e\in E)$ respectively.
To obtain its optimal solution, we apply the well-known column generation framework by considering a {\it Restricted Master Problem} (RMP) over some subset $P'\subset P$.
To guarantee the feasibility of the RMP, we initialize it with a set of artificial variables such that each of them is penalized in the objective function. The new columns are obtained step-by-step by the following scheme.

Let $\alpha$ and $\beta_e, (e\in E)$ be the dual variables corresponding to the constraints \eqref{eq:mp2} and \eqref{eq:mp3} respectively. Then, the  Dual problem of the RMP (DRMP) containing $P'$ columns is formulated as follows:
\begin{eqnarray}
\text{(DRMP}(P')): \max\ -\alpha\tilde{\F} + \gamma k_{min}\label{eq:dual1}\\
\notag
s.t.\phantom{XXXXXXXXXXX}\\
-\alpha\tilde{{\mathds{P}}}(\x^p)-\sum_{e\in E}\beta_ex_e^p + \gamma\leq 0, & (p\in P')\label{eq:dual2}\\
M\beta_e - c_e \leq 0, & (e\in E)\label{eq:dual3}\\
\alpha\geq 0,\label{eq:dual4}\\
\beta_e\geq 0. & (e\in E)\label{eq:dual5}
\end{eqnarray}

Suppose that $(\bar\alpha, \bar\beta_e, \bar\gamma)$ is an optimal solution of the DRMP$(P')$. In order to be appended as a new column, route $p$ should satisfy the constraint 
\begin{equation}
\bar\alpha\tilde{\mathds{P}}(\mathbf{x}^p)+\sum_{e\in E}\bar\beta_ex_e^p - \bar\gamma<0.\label{eq:reduced_cost}
\end{equation}
 If such a route $p$ exists, we append it to the RMP and continue the column generation process. Otherwise, the column generation procedure is complete. 

In order to find such a route $p$:
\begin{itemize}
	% \item[-] introduce the variables $x_{e,p}\in\{0,1\}$ defining whether arc $e\in E$ included to route $p$ or not.
	\item[-] if $\bar\alpha=0$, we find a route $p$ satisfying $\sum_{e\in E}\bar\beta_ex_e^p < \bar\gamma$ by solving the shortest path problem in the auxiliary graph $\tilde G=(\tilde V,\tilde E)$ where edges $e\in \tilde E$ have weights $\bar\beta_e$;
	\item[-] if $\bar\alpha>0$, we solve a pricing problem which is equivalent to the collection of the following auxiliary problems:
	\begin{equation}
	\text{AUX}(d)\colon\min\left\{\tilde{\mathds{P}}(\x^p)\colon p\in P\setminus P', \sum_{e\in E}\bar\beta_ex_e^p=d\right\}\label{eq:pricing_aux}.
	\end{equation}
\end{itemize}
Indeed, to find a desired route $p$, we have to minimize the LHS of \eqref{eq:reduced_cost} that is equivalent to minimizing $\tilde{\mathds{P}}(\mathbf{x}^p)$ for some fixed value $d$. 

Since $\log_2$ is a monotonically increasing function, the problem AUX$(d)$ is equivalent to the following problem:
\begin{equation*}
\text{SUR}(d)\colon\max\left\{\sum_{e\in E}x_e^p\log_2 p_e\colon p\in P\setminus P',\ \sum_{e\in E}\bar\beta_ex_e^p=d\right\}.
\end{equation*}
It easy to see, that the problem SUR$(d)$ linearly depends only on $x_e^p$ variables, which is the main advantage over the AUX$(d)$. 

In order to add a new column to the RMP, we should solve the following family of problems P$(d)$, parametrized by values $d$:
\begin{eqnarray}
\text{(P}(d))\colon\max\ \sum_{e\in E}x_e\log_2 p_e\label{eq:pp1}\\
\notag
s.t.\phantom{XXXXXXXXX}\\
\sum_{(i,j)\in E}x_{(i,j)}-\sum_{(j,i)\in E}x_{(j,i)}=&
\begin{cases}
1,\ i=s\\
-1,\ i=t\\
0,\ \text{otherwise}
\end{cases}\\
\sum_{e\in E(p)}x_e\leq |E(p)|-1, & (p\in P')\label{eq:pp2}\\
\sum_{e\in E}\bar\beta_ex_e=d\label{eq:pp3}\\
x_e\in\{0,1\}, & (e\in E)\label{eq:pp4}.
\end{eqnarray}
Here, constraints \eqref{eq:pp2} guarantee that no column is appended to the RMP twice, and equation \eqref{eq:pp3} binds the values $\xi_e$ with the parameter $d$. 

If at least one of the problem P$(d)$ provides a route satisfying \eqref{eq:reduced_cost} we add it to the RMP$(P')$. 

To reduce the number of the pricing problems, we consider the following heuristic. Since $p^*$ is the most reliable $s$-$t$ route, we obtain the following simple inequality: $\tilde{\mathds{P}}(\x^{p^*})\leq \tilde{\mathds{P}}(\x^p)\leq -\frac{d-\gamma}{\bar\alpha}$, which helps us to discard problems P$(d)$, where $d<-\bar\alpha\tilde{\mathds{P}}(\x^{p^*})+\gamma$.





