An efficient algorithm for the reliability evaluation of multistate flow networks under budget constraints

Abstract

Many real-world systems can be modeled by multi-state flow networks (MFNs) and their reliability evaluation features in designing and control of these systems. Considering the cost constraint makes the problem of reliability evaluation of an MFN more realistic. For a given demand value d and a given cost limit c, the reliability of an MFN at level (d, c) is the probability of transmitting at least d units from the source node to the sink node through the network within the cost of c. This article addresses the so-called (d, c)-MC problem, i.e., the problem of reliability evaluation of an MFN with cost constraint in terms of minimal cuts. It presents new results on which a new algorithm is based. This algorithm finds all (d, c)-MC candidates without duplicates and verifies them more efficiently than existing ones. The complexity results for this algorithm and an example of its use are provided. Finally, numerical experiments with R language implementations of the presented algorithm and other competitive algorithms are considered. Both the time complexity analysis and numerical experiments demonstrate the presented algorithm to be more efficient than the fastest competing algorithms in 81.41–85.11% of cases.

Keywords:

• Multistate flow network (MFN)
• network reliability
• cost constraint
• minimal cut (MC)
• (d, c)-MC

Data availability statement

The data that support the findings of this study are openly available in repository IEEEDataPort at http://doi.org/10.21227/8fmh-3d09.

Nomenclature

$G(V,E,W,C)$ an MFN with the set of nodes $V=\{1,\dots ,n\},$ the source node 1, the sink node n, the set of edges $E=\{e_1,\dots ,e_m\},$ the largest System State Vector (SSV) $W=(W_1,\dots ,W_m),$ where $W_i=W(e_i)$ denotes the maximum state of e_i, and $C=(c_1,\dots ,c_m)$ with c_i denoting the cost of sending one unit product through e_i, for $i\in \{1,\dots ,m\}.$

c the total budget of the network

Cut an edge set such that there exists no path from the source node to the sink node in graph $G(V,E,W,C)$ after removing this edge set

Minimal cut a cut whose proper subsets are no a cut

MCs the list of all MCs $K_1,\dots ,K_p$

$X\le Y$ if $X(e_i)\le Y(e_i)$ for all $i\in \{1,\dots ,m\}$

X < Y if $X\le Y$ and there exists $i\in \{1,\dots ,m\}$ such that $X(e_i)<Y(e_i)$

state vector any vector $X=(x_1,\dots ,x_m)$ such that $0\le X\le W$

$\mathcal{P}(S)$ the power set of a set S

${\mathbb{N}}_0$ the set of non-negative integers, i.e., ${\mathbb{N}}_0=\mathbb{N}\cup \left\{0\right\}$

${\mathbb{N}}_0^k$ the Cartesian product $\underset{k}{\underbrace{{\mathbb{N}}_0\times \cdots \times {\mathbb{N}}_0}}$

$\#S$ the number of elements of the set S

n $=\#V$

m $=\#E$

p $=\#\mathit{MCs}$

$X(e_i)$ a state of the edge e_i denoting the amount of flow permitted to travel through e_i under an SSV X

$\mathit{LCB}(e_i)$ LCB of e_i, i.e., the minimal capacity of e_i such that the maximum flow from the source node to the sink node equals d

U(X) $=\{e\in E:X(e)<W(e)\}$ – the set of unsaturated edges of X

$Ca{p}_X(K)$ $=\sum _{e\in K}X(e)$ – the capacity of MC K under X

Cap(K) $=Ca{p}_W(K)$ – the capacity of MC K (under W)

M(X) $=\min \{Ca{p}_X(K):K\in \mathit{MCs}\}$ – the maximum flow under X

D $=M(W)$ – the maximum flow under W

C(X) $=c_1·x_1+\dots +c_m·x_m$ – the associated cost with X

$W(0_i)$ a special SSV with the state of e_i equal to 0 and the state of other edges equal to their largest state W

${\overline{l}}_i$ $=\max \{0,d-M(W(0_i))\}$

${\underset{¯}{l}}_i$ $=\max \{-1,d-M(W(0_i))\}$

d-MC an SSV X such that M(X) = d and M(Y ) > d for all Y > X

(d, c)-MC a d-MC X such that $C(X)\le c$

$M_{\mathit{ind}}(X)$ $=\min \{Ca{p}_X(K_i):i\in \mathit{ind}\},$ where $\mathit{ind}\subseteq \{1,\dots ,p\}$

Ind_U $=\{i\in \{1,\dots ,p\}:U\subseteq K_i\},$ where $U\subseteq E$

$M_{In{d}_{U(X)}}(X)$ $=\min \{Ca{p}_X(K_i):U(X)\subseteq K_i\}$

i(U) $=\{i\in In{d}_U:{\forall }_{j}Cap(K_i\setminus U)\le \mathit{Cap}(K_j\setminus U)\},$ where $U\subseteq E$

${\widehat{X}}_j$ the costliest d-MC candidate obtained from K_j

${\check{X}}_j$ the most cost-effective d-MC candidate obtained from K_j

Q₁ $=\{j\in \{1,\dots ,p\}:C({\widehat{X}}_j)\le c\}$ – the set of indices j of MCs such that the associated cost with the costliest d-MC candidate obtained from K_j is not greater than the total budget of the network

Q₂ $=\{j\in \{1,\dots ,p\}:C({\check{X}}_j)>c\}$ – the set of indices j of MCs such that the associated cost with the most cost effective d-MC candidate obtained from K_j is greater than the total budget of the network

L₁ the list of all at least two element distinct subsets of MCs

L₂ the list such that its ith element is the set of indices of all MCs including i-th element of L₁, i.e. $L_2[i]=In{d}_{L_1[i]}$

N the number of items in lists L₁ and L₂

$R_{(d+1,c)}$ the network reliability at level $(d+1,c),$ i.e. $P(M(X)>d\hspace{1em}\&\hspace{1em}C(X)\le c)$

Assumptions

MFNs satisfy the following assumptions from Ahuja et al. (1993):

1. Each node is perfectly reliable.

2. The capacity of each edge is a non-negative integer-valued random variable according to a given distribution.

3. The capacities of different edges are statistically independent.

4. All flows in the network obey the conservation law.

Additional information

Notes on contributors

Paweł Marcin Kozyra

Paweł Marcin Kozyra received a PhD degree in mathematics from the Polish Academy of Sciences Institute of Mathematics, Poland, in 2017. He is an assistant with Faculty of Applied Mathematics, Silesian University of Technology, Poland. He has authored/coauthored several articles in international refereed journals, such as IEEE Transactions on Reliability, Journal of Risk and Reliability, Journal of Integer Sequences, Annals of the Institute of Statistical Mathematics, Statistics: A Journal of Theoretical and Applied Statistics, Communications in Statistics - Theory and Methods, and Probability and Mathematical Statistics. His research interests include reliability theory, multistate flow networks, graph theory, statistics, and combinatorics.