The usefulness of (d,b)-MCs and (d,b)-MPs in network reliability evaluation under delivery or maintenance cost constraints

Reliability and delivery cost or maintenance cost are important indicators showing the stability and the quality of operation of a multi-state flow network. Many authors developed (d,b)-minimal cut based or (d,b)-minimal path based algorithms to compute the network reliability, i.e., the probability that a demand d can be delivered from the source node to the sink node subject to the constraint that the total delivery cost (maintenance cost) is not greater than b. It is proven that contrary to prevalent methods in existing literature, both (d,b)-minimal cuts and (d,b)-minimal paths are insufficient to compute the exact value of the reliability of a multi-state flow network under budget or maintenance budget constraints. Moreover, it is also shown how this value can be determined.