Аннотация:

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 $\texttt{#}$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.