The problem of network design, where two designated terminals are connected with a given probability is a challenging and well-known #P-hard problem that has an application within the Supply Chain Management. On the other hand, business process requirements dictate that the constructed network must be optimal in regards to various costs. In this paper, we introduce the Bi-objective Efficient 2-Terminal Reliability Problem aimed to design Pareto-optimal solutions with respect to both criteria. We propose a proof-of-concept of the branch-and-price algorithm relying on Dantzig-Wolfe decomposition, probability relaxation, and column generation techniques, integrated within the well-known \(\varepsilon \) -constraint method. Numerical evaluation over benchmarking instances demonstrate high performance of our approach.