\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}


\usepackage{dsfont} %math fonts



\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]





%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}


\def\udcs{519.853.65} %Here the author places classificators of the paper according to Russian classification system
\def\mscs{90X10} %Here the author places  classificators according to the AMS classification list.
\setcounter{page}{144}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}



\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{ÑÈÁÈÐÑÊÈÅ ÝËÅÊÒÐÎÍÍÛÅ}} \\[2mm]
     {\LARGE \textsf{ÌÀÒÅÌÀÒÈ×ÅÑÊÈÅ ÈÇÂÅÑÒÈß}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Èíñòèòóò ìàòåìàòèêè èì. Ñ.Ë.Ñîáîëåâà ÑÎ ÐÀÍ}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Vol. 20, No. 2, pp. 144--145 (2023) \hspace{\fill}{\rm\small ÓÄÊ \udcs \hspace{-4mm}}}
     \newline  %Volume, pages in Russian, filled by Editorial board
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\newcommand{\F}{\mathfrak{F}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\R}{\mathfrak{R}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\x}{{\bf x}}


\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\proofname}{Proof.}
\renewcommand{\figurename}{Fig.}

\renewcommand{\tablename}{Tab.}




\thispagestyle{empty}

\title[B\&P algorithm for the E$2$TTP]{\large Branch-and-Price algorithm for the Efficient 2-Terminal Reliability Problem}


\author[R.A. RUDAKOV]{{\bf R.A. Rudakov}\protect\orcidicon{0000-0002-1750-1368}}
\author[D.M. KHACHAY]{{\bf D.M. Khachay}\protect\orcidicon{0000-0001-9276-4128}}
\author[Y.Y. OGORODNIKOV]{{\bf Y.Y. Ogorodnikov}\protect\orcidicon{0000-0002-1750-1368}}
\author[M.Y. KHACHAY]{{\bf M.Y. Khachay}\protect\orcidicon{0000-0003-3555-0080}}


\address{Roman Alexandrovich Rudakov  
\newline\hphantom{iii} Krasovsky Institute of Mathematics and Mechanics,
\newline\hphantom{iii} S.Kovalevskaya Str, 16,
\newline\hphantom{iii} 620108, Yekaterinburg, Russia}%
\email{\textcolor{blue}{r.rudakov@imm.uran.ru}}%

\address{Daniil Michaelovich Khachay
\newline\hphantom{iii} P\^{o}le Universitaire L\'{e}onard de Vinci, Research Center, Paris, France}%
\email{\textcolor{blue}{daniil.khachai@devinci.fr}}%

\address{Yuri Yurievich Ogorodnikov
\newline\hphantom{iii} Krasovsky Institute of Mathematics and Mechanics,
\newline\hphantom{iii} S.Kovalevskaya Str, 16,
\newline\hphantom{iii} 620108, Yekaterinburg, Russia}%
\email{\textcolor{blue}{yogorodnikov@imm.uran.ru}}

\address{Michael Yurievich Khachay
\newline\hphantom{iii} Krasovsky Institute of Mathematics and Mechanics,
\newline\hphantom{iii} S.Kovalevskaya Str, 16,
\newline\hphantom{iii} 620108, Yekaterinburg, Russia}%
\email{\textcolor{blue}{mkhachay@imm.uran.ru}}%

\thanks{\sc Rudakov, R.A., Khachay, D.M., Ogorodnikov, Y.Y., Khachay, M.Y.,
Branch-and-Price algorithm for the Efficient 2-Terminal Reliability Problem}
\thanks{\copyright \ 2025 Rudakov R.A., Khachay D.M., Ogorodnikov Y.Y., Khachay M.Y..}
\thanks{\it Received January, 1, 2023, Published December, 31, 2023}%


\semrtop \vspace{1cm}
\maketitle {\small

\vspace{-12pt}
\centerline{{\it Communicated by} {\sc P.P. Petrov}
%({\it filled by Editorial board})
}

\bigskip
\bigskip

\begin{quote}
\noindent{\bf Abstract:} The Two-Terminal Reliability Problem, which assesses the probability of connection between two designated nodes in a network subject to the failures, remains a challenging and well-recognized \#P-hard problem. In the recent years, along with the guaranteed reliability of the network, the question of the overall cost minimization became quite significant. In this paper, we intro-duce a proof-of-concept of the Branch-and-Price algorithm that relies on the well-known decomposition and column generation techniques in order to efficiently solve this problem. Numerical evaluation over benchmarking instances demonstrate the high per-formance of the proposed algorithm.\medskip

\noindent{\bf Keywords:} $2$-Terminal Reliable Problem, Erd\"os-R\'{e}nyi random graphs, MIP models,  Dantzig-Wolfe decomposition, branch-and-price.
 \end{quote}
}

\bigskip

\input{introduction}
\input{related_work}
\input{problem_statement}
\input{models}
\input{BPnC}
\input{experiments}
\input{conclusion} 



\bigskip
\begin{thebibliography}{1}

\bibitem{Bollobas2001} B. Bollob\'as, {\it Random Graphs (Second edition)}, Cambridge Studies in Advanced Mathematics 73, Cambridge University Press, 2 edn. (2001).

\bibitem{Bouchery2017} Y. Bouchery, C. Corbett, J. Fransoo, T. Tan (eds.), 
\href{https://doi.org/10.1007/978-3-031-45565-0}{\it Sustainable Supply Chains: A Research-Based Textbook on Operations and Strategy}, Springer Series in Supply Chain Management, Springer (2024).

\bibitem{Casazza2021} M. Casazza, A. Ceselli, 
\href{https://doi.org/10.1016/j.cor.2020.105191}{\it Optimization algorithms for resilient path selection in networks}, Computers \& Operations Research {\bf 128}, 105191 (2021).

\bibitem{CenHeLiPan2024} R. Cen, W. He, J. Li, D. Panigrahi,
\href{https://doi.org/10.1137/1.9781611977912.62}{\it Beyond the Quadratic Time Barrier for Network Unreliability}, pp. 1542–1567.

\bibitem{CHENG201540} J. Cheng, A. Lisser,
\href{https://doi.org/10.1016/j.dam.2014.05.009}{\it Maximum probability shortest path problem}, Discrete Applied Mathematics {\bf 192}, 40–48 (2015), 11th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012)

\bibitem{Colbourn1991} C.J. Colbourn, 
\href{https://doi.org/10.1007/BF02061656}{\it Combinatorial aspects of network reliability}, Annals of Operations Research {\bf 33}(1), 1–15 (Jan 1991). 

\bibitem{Desrosiers2024} J. Desrosiers, M. L\"ubbecke, G. Desaulniers, J.B. Gauthier, {\it Branch-and-price}, Les cahiers du gerad, GERAD (10 2024).

\bibitem{Dolgui2020}  A. Dolgui, D. Ivanov, D. Rozhkov, 
\href{https://doi.org/10.1080/00207543.2019.1627438}{\it Does the ripple effect influence the bullwhip effect? An integrated analysis of structural and operational dynamics in the supply chain}, International Journal of Production Research {\bf 58}(5), 1285–1301 (2020). 

\bibitem{Feng2024} W. Feng, H. Guo, 
\href{https://doi.org/10.4230/LIPIcs.ICALP.2024.62}{\it An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs}, Leibniz International Proceedings in Informatics (LIPIcs), vol. 297, pp. 62:1–62:19. Schloss Dagstuhl – Leibniz-Zentrum f\"ur Informatik, Dagstuhl, Germany (2024), \href{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.62}{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.62}.

\bibitem{GUROBI} Gurobi Optimization, L.: \href{https://www.gurobi.com/documentation/9.5/refman/index.html}{\it Gurobi optimizer reference manual (2024)}.

\bibitem{Ivanov2020}  D. Ivanov, A. Dolgui, \href{https://doi.org/10.1080/00207543.2020.1750727}{\it Viability of intertwined supply networks: extending the supply chain resilience angles towards survivability. a position paper motivated by covid-19 outbreak}, International Journal of Production Research {\bf 58}(10), 2904–2915 (2020).

\bibitem{MooreShannon} E. Moore, C. Shannon, \href{https://doi.org/10.1016/0016-0032(56)90559-2}{\it Reliable circuits using less reliable relays}, Journal of the Franklin Institute {\bf 262}(3), 191–208 (1956).

\bibitem{Ogorodnikov2024}  Y. Ogorodnikov, R. Rudakov, D. Khachai, M. Khachai, \href{https://doi.org/10.1134/S0965542524700441}{\it Fault-tolerant families of production plans: Mathematical model, computational complexity, and branch-and-bound algorithms}, Computational Mathematics and Mathematical Physics {\bf 64}(6), 1193–1210 (2024).

\bibitem{Ogorodnikov2022}  Y. Ogorodnikov, R. Rudakov, D. Khachai, M. Khachay, \href{https://doi.org/10.1016/j.ifacol.2022.09.455}{\it A problem-specific branch-and-bound algorithm for the protected shortest simple path problem with must-pass nodes}, IFAC-PapersOnLine {\bf 55}, 572–577 (2022).

\bibitem{PioroMedhi} M. Pi\'oro, D. Medhi, \href{https://doi.org/10.1016/B978-012557189-0/50025-1}{\it Routing, Flow, and Capacity Design in Communication and Computer Networks}, The Morgan Kaufmann Series in Networking, San Francisco (2004). 

\bibitem{Provan1986} J.S. Provan, \href{https://doi.org/10.1137/0215050}{\it The complexity of reliability computations in planar and acyclic graphs}, SIAM Journal on Computing {\bf 15}(3), 694–702 (1986). 

\bibitem{Redmond2019} M. Redmond, A.M. Campbell, J.F. Ehmke, \href{https://doi.org/10.1002/net.21866}{\it The most reliable flight itinerary problem}, Networks {\bf 73}(3), 325–343 (2019).

\bibitem{two-terminal-old} A. Satyanarayana, R.K. Wood, \href{https://doi.org/10.1137/0214057}{\it A linear-time algorithm for computing k-terminal reliability in series-parallel networks}, SIAM Journal on Computing {\bf 14}(4), 818–832 (1985). 

\bibitem{Sundarakani2021} B. Sundarakani, V. Pereira, A. Ishizaka, \href{https://doi.org/10.1108/IJLM-12-2019-0333}{\it Robust facility location decisions for resilient sustainable supply chain performance in the face of disruptions}, The International Journal of Logistics Management {\bf 32}(2), 357–385 (2021). 

\bibitem{TANG200812} C. Tang, B. Tomlin, \href{https://doi.org/10.1016/j.ijpe.2008.07.008}{\it The power of flexibility for mitigating supply chain risks}, International Journal of Production Economics {\bf 116}(1), 12–27 (2008). 

\bibitem{Tanguy2007-1} C. Tanguy, \href{https://doi.org/10.1109/DRCN.2007.4762273}{\it Exact two-terminal reliability of some directed networks}, In: 2007 6th International Workshop on Design and Reliable Communication Networks. pp. 1–8 (2007). 

\bibitem{Tanguy2007-2} C. Tanguy, \href{https://doi.org/10.1088/1751-8113/40/47/005}{\it What is the probability of connecting two points?} Journal of Physics A: Mathematical and Theoretical {\bf 40}(47), 14099 (nov 2007). 

\bibitem{uchoa2024optimizing} E. Uchoa, A. Pessoa, L. Moreno, {\it Optimizing with Column Generation: Advanced branch-cut-and-price algorithms (Part I)}, Tech. Rep. L-2024-3, Cadernos do LOGIS-UFF, Universidade Federal Fluminense, Engenharia de Produ\c{c}\~ao (August 2024)

\bibitem{Valiant} L.G Valiant, \href{https://doi.org/10.1137/0208032}{\it The complexity of enumeration and reliability problems}, SIAM Journal on Computing {\bf 8}(3), 410–421 (1979). 

\bibitem{Zenklusen2011} R. Zenklusen, M. Laumanns, \href{https://doi.org/10.1002/net.20412}{\it High-confidence estimation of small s-t reliabilities in directed acyclic networks}, Networks {\bf 57}(4), 376–388 (2011). 

\end{thebibliography}


% \begin{thebibliography}{1} % Ññûëêè íà ëèòåðàòóðó ïðèâîäÿòñÿ òîëüêî íà àíãëèéñêîì ÿçûêå (äàæå åñëè ó èñòî÷íèêà íåò àíãëîÿçû÷íîé âåðñèè).

% \bibitem{1} D.G. Northcott,
% \href{https://doi.org/10.1017/CBO9780511565908}{\it Ideal Theory}, Cambridge University Press, Cambridge, 1953.

% \bibitem{2} I.I. Ivanov,
% \href{https://doi.org/10.1002/cpa.20282}{\it Some properties of commutative algebras}, Siberian Electronic
% Mathematical Reports, {\bf 1} (2004), 142--143.

% \bibitem{3} A.V. Tetenov, M. Samuel, D.A. Vauilin,
% \href{https://doi.org/10.21538/0134-4889-2017-23-4-281-291}{\it On dendrites generated by polyhedral systems and their ramification points}, Trudy Inst. Mat. Mekh. UrO RAN, \textbf{23}:4 (2017), 281--291.

% \end{thebibliography}

\end{document}
