# Decision Diagram Based Symbolic Algorithm for Evaluating the Reliability of a Multistate Flow Network

Authors: Rongsheng Dong; Yangyang Zhu; Zhoubo Xu; Fengying Li
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Evaluating the reliability of Multistate Flow Network (MFN) is an NP-hard problem. Ordered binary decision diagram (OBDD) or variants thereof, such as multivalued decision diagram (MDD), are compact and efficient data structures suitable for dealing with large-scale problems. Two symbolic algorithms for evaluating the reliability of MFN, MFN_OBDD and MFN_MDD, are proposed in this paper. In the algorithms, several operating functions are defined to prune the generated decision diagrams. Thereby the state space of capacity combinations is further compressed and the operational complexity of the decision diagrams is further reduced. Meanwhile, the related theoretical proofs and complexity analysis are carried out. Experimental results show the following: (1) compared to the existing decomposition algorithm, the proposed algorithms take less memory space and fewer loops. (2) The number of nodes and the number of variables of MDD generated in MFN_MDD algorithm are much smaller than those of OBDD built in the MFN_OBDD algorithm. (3) In two cases with the same number of arcs, the proposed algorithms are more suitable for calculating the reliability of sparse networks.


---

## Body

## 1. Introduction

With the development of science and technology, network models have been applied to many systems in various fields, such as computer networking, communication, transportation, gas and oil production, power transmission, and logistics [1–3]. In the real world, many systems/networks have been abstracted as multistate systems (MSSs) [4–6], multistate networks (MSNs) [7–9], or stochastic flow networks (SFNs) [10–12]. The components (transmission lines or nodes) of the MSN have several states (failure, working perfectly, and demotion work), so each state of the components is usually modeled to a certain capacity with a probability. The MSNs that satisfy the conservation law are denoted multistate flow networks (MFNs), which are more adaptive to real-word network models [3, 13–16].Network failures can be disastrous and losses great, so network reliability evaluation has become a major prerequisite to ensure proper functioning of a network [3, 9]. Network reliability is defined as the probability that a required amount of flow (such as data, power, etc.) is transmitted successfully from source node s to sink nodet [3]. The reliability evaluation of a network is NP-hard problem [9]. A lot of algorithms have been provided based on some assumptions, including inclusion and exclusion method [10–12], and sum of disjoint products method [13]. These algorithms can provide an exact value of reliability, but they are limited to the enumeration of the variable combinations. Some approximation algorithms, like the upper and lower bound method [2], Monte Carlo simulation [17], and so forth possess relatively high efficiency but cannot get an exact value. Decision diagrams (DDs) have the advantages of high compactness and operability and of being able to express variable combinations implicitly and are thus one of the more feasible strategies to alleviate the problem of combinatorial explosion. Moreover, DDs can obtain an exact result with Shannon expansion or the extended form. Therefore, the decision diagram has been frequently used to evaluate network reliability because of the aforementioned advantages [18–24]. These algorithms are mainly for evaluating the reliability of the networks with two-state component [18] or a single path transmission [19–23].For a multistate flow network, most existing reliability evaluation algorithms are based on the set of minimal cuts/paths [24, 25], and generating the set of minimal cuts/paths is another NP-hard problem [1, 26]. Jane and Laih have studied the reliability computation of two-terminal MFNs using a decomposition algorithm, which is better than the exhaustive enumeration method with a lower space complexity, with the prior requirement that the state vectors (d_flows) satisfy the demand without minimal cuts/paths [1, 7]. For the case of maximum flow and minimum cost, Terruggia and Bobbio presented a multivalued decision diagram (MDD) based method, which takes full advantage of the operation technology of multivalued decision diagrams so that the reliability evaluation of a MFN is simple and efficient, with a set of minimal cuts [24].Thus, for calculating the reliability of a MFN, we attempt to propose an exact algorithm that simultaneously solves the following problems: (1) avoid searching for all minimal cuts/paths, and (2) alleviate enumerating the state space as far as possible. In view of this, first, we extend the formal definition of the MFN model to implement symbolic algorithms in this paper, and next two decision diagram based exact algorithms, MFN_OBDD and MFN_MDD, are proposed. A state vector (flow(d)) that satisfies the flow requirement is obtained by using the maximum flow algorithm in a constructed virtual network in the proposed algorithms, without locating all minimal cuts/paths. In MFN_OBDD, the ordered binary decision diagram (OBDD) structure and its operation technology are introduced, a capacity/state of each arc is represented by a Boolean variable, and four operating functions are defined. The reliability of a MFN is then described and solved accurately. The MDD structure with multibranch and operation technology is introduced; each arc is denoted by a multivalue variable, and three operating functions are defined in MFN_MDD. The correctness and efficiency of the algorithm are verified by experiments. Compared to the spatial decomposition algorithm of Jane and Laih [1], the proposed algorithms, which lower the computational complexity, do not require enumerating and decomposing the state space of the components.The remainder of this article is organized as follows. In Section2, an extended formal MFN model and a definition of MFN reliability are provided. In Section 3, elementary knowledge of OBDD and MDD is reviewed. In Section 4, the OBDD-based algorithm, MFN_OBDD, and the MDD-based algorithm, MFN_MDD, are proposed, and both their computational and storage complexity are analyzed. In Section 5, computational experiments are presented, and comparisons between the proposed algorithms and the decomposition algorithm of Jane and Laih are made. Conclusions are finally drawn in Section 6.


## 2. Multistate Flow Network Model and Reliability

In this section, a two-terminal (one source and one sink) MFN is modeled. LetG=s,t,V,A,S,C,P,D,d be a MFN where s is the source,t is the sink, V=vi∣1≤i≤n with s,t∈V is the set of vertexes, A=ai∣1≤i≤n with A⊂V×V is the set of arcs, C=Ci∣1≤i≤n with Ci=ci,0,ci,1,…,ci,si-1 is the set of ai’s capacities, S={si∣1≤i≤n,si=Ci} is the set of capacity numbers, P={Pi∣1≤i≤n} with Pi=pi,0,pi,1,…,pi,si-1 is the set of ai’s capacity probabilities, pci,j=pi,j, D=d0,d1,…,dk is the set of the output flows from s to t, obviously, max⁡di is the maximum flow of the network, d is the demand transmitted from s to t, and d∈D,0≤d≤max⁡di. In addition, the following mapping relationship was established:(1)C1×C2×⋯×Cn⟶D.An important property of MFN is that each node satisfies the flow conservation law. For a node, the total amount of traffic input is equal to the total output flow. Thus, the flow from the source into the network is equal to the output from the sink.In this paper, networkG must satisfy the following assumptions:(1)
Each vertex is perfectly reliable. For the unreliable vertex case, vertexes and arcs can be treated as components of the same type.(2)
The capacity of each arc is stochastic with a given probability distribution.(3)
The capacities of different arcs are stochastically independent.The vector of capacitiesc=c1,c2,…,cn denotes the state vector of the network where ci≤Ci is the state of ai. Fc denotes the maximum flow from s to t. Vector c is satisfiable for a specified demand d if Fc≥d; otherwise it is unsatisfiable. A satisfiable flow(d) can be obtained by Lemma 1.Lemma 1 (see [1]).
Given a MFN,G=s,t,V,A,S,C,P,D,d, and a satisfiable state vector flow(d) can be obtained at least when c- is satisfiable, where flowd=f1d,f2d,…,fnd with Fflowd=d consists of flows fid through each arc ai, and c-=(c1max,c2max,…,cnmax) with cimax=max⁡ci,0,ci,1,…,ci,si-1 is the vector of the maximum capacities of arcs.Proof.
Construct a new networkG∗ based on the network G with a fictitious vertex s∗ and a fictitious arc a0 that has a fixed capacity d from s∗ to s. Obviously, a0 is a minimal cut set of network G∗. According to the maximum-flow minimum-cut theorem, the maximum flow from s∗ to t is d. Each arc of G∗, ai∈A, 1≤i≤n, has a flow recorded as fid when G∗ obtains the maximum flow. These flows constitute a state vector as f1d,f2d,…,fnd; that is, there is a feasible flow recorded as flowd=f1d,f2d,…,fnd to satisfy the demand d. Therefore, the lemma is proved.For a MFN, we deduce the conclusion from the above. Ifc_ is satisfiable for demand d with c_=flowd=f1d,f2d,…,fnd, Fc_=d, and Fc-≥d, then Fc≥d with c∈Ω and Ω={c1,c2,…,cn∣fid≤ci≤cimax,ci∈Ci}=c_,c¯. According to Corollary 1 of [1], a flow(d) may be obtained in Om3 time.In this paper, we study the reliability evolution of a MFN with a demandd. Then the MFN’s reliability is defined as follows.Definition 2.
For a MFNG with demand d from source s to sink t, the probability of the state space corresponding to the satisfiable vectors of the network with d is the reliability of the MFN. That is, the reliability of G is(2)Reld=Pc∣Fc≥d=Pc1,c2,…,cn∣Fc≥d,ci∈Ci=⋃Pc1,c2,…,cn∣Fc≥d,ci∈Ci.


## 3. Ordered Binary Decision Diagram and Multivalued Decision Diagram

In this section, we review the concept of ordered binary decision diagrams (OBDD) and Multivalued Decision Diagram (MDD). An OBDD is a directed acyclic tree for Shannon decomposition and provides a compact, canonical, and efficiently manipulative representation for Boolean functions. A MDD is an extension of an OBDD.


### 3.1. Ordered Binary Decision Diagram

IfF denotes a Boolean expression on X=x1,x2,…,xn with xi1≤i≤n being a Boolean variable of X, theite (If-Then-Else) format of a binary decision diagram (BDD) is defined as(3)F=itex,F1,F2=x·F1+x′·F2,where x∈X, x′ is the complement of x (if x=0, x′=1; else if x=1, x′=0), F1=Fx=1, and F2=Fx=0. A BDD has two terminal nodes that correspond to Boolean constants, 0 and 1, respectively. Each nonterminal node denotes a Boolean variable x with two branches corresponding to the Boolean expressions F1 of x=1 and F2 of x=0 for Shannon decomposition. Then each nonterminal node in BDD represents anite(x, F1, and F2) and it is different from the others.An ordered binary decision diagram (OBDD) is a BDD with a constant order for Boolean variables. The order of the Boolean variables from root to terminal is descending or increasing. Some operations can be defined between two OBDDs with the same variable order, and a new compact OBDD with the same variable order is obtained by an operation.For example, Figure1 shows the complete binary tree (Figure 1(a)) and the OBDD (Figure 1(b)) for the Boolean expression W=x1·x2+x1′·x3 with the variable order Π:x3≻x2≻x1. Obviously, the OBDD stores the same information with fewer nodes. If we trace the path ①→③→⑤→⑦ and reach terminal node 1, the value of W=x1·x2+x1′·x3 with variable assignment x1,x2,x3 = (0, 0, 1) is 1. Figure 1(c) shows the OBDD for expression U=x1·x2+x2′·x3 with the same variable order, and Figure 1(d) shows the new OBDD obtained by an operation “·” (conjunctive,And) between the two OBDDs.Figure 1
OBDD: (a) the complete binary tree ofW=x1⋅x2+x1′⋅x3; (b) the OBDD ofW; (c) the OBDD of U; (d) the OBDD of W⋅U.
(a) (b) (c) (d)


### 3.2. Multivalued Decision Diagram

A multivalued discrete functionF denotes the operation with n multivalued variables x1,x2,…,xn mapping to the range R.(4)F:L1×L2×⋯×Ln⟶R,where Li=0,1,…,li-1 is the domain of variable xi and R=r0,r1,…,rk-1 is the range.A MDD is a variant of a BDD. IfF denotes an expression on X=x1,x2,…,xn, thecase format of a MDD is defined as(5)F=casex,Fx=0,Fx=1,…,Fx=l-1=x=0·Fx=0+x=1·Fx=1+⋯+x=l-1·Fx=l-1=∑i=0l-1x=i·Fx=i,where x∈X. A MDD has k=R terminal nodes that correspond to the constants, r0,r1,…,rk-1, respectively, and each nonterminal node denotes a variable x with Di branches corresponding to the expressions Fx=i. Then each nonterminal node in a MDD represents acase format.Similar to an OBDD, a new compact MDD is obtained by an operation between two different MDDs with the same variable order, and Property1 is applicable for an OBDD or MDD. For example, Figure 2 shows the complete tree (Figure 2(a)) and the MDD (Figure 2(b)) for the numerical function W=x1·x2+x3 with the variable order Π:x3≻x2≻x1, L1=0,1, L2=0,1, and L3=0,1,2. Obviously, the MDD stores the same information with quite a few nodes. If we trace the path x3=1→x2=1→x1=1→2 and reach terminal node 1, the value of W=x1·x2+x3 with variable assignment x1,x2,x3 = (1, 1, 1) is 2. Figure 2(c) shows the MDD for the expression U=x1·x2·x3 with the same variable order, and Figure 2(d) shows the new MDD obtained by an operation “∗” (multiplication) between the two MDDs (if W=1 and U=2, then W∗U=2). In fact, the MDD can be further simplified. For W∗U, if W∗U>0 satisfies the requirement, terminal nodes 2 and 6 can be combined in one node 1 (True). This process will be used in our algorithm.Figure 2
MDD: (a) the complete tree ofW=x1⋅x2+x3; (b) the MDD ofW; (c) the MDD ofU; (d) the MDD of W∗U.
(a) (b) (c) (d)Property 1.
Applying the operation for a nonnull OBDD (or MDD)W and U will unite the intersecting spaces.


## 3.1. Ordered Binary Decision Diagram

IfF denotes a Boolean expression on X=x1,x2,…,xn with xi1≤i≤n being a Boolean variable of X, theite (If-Then-Else) format of a binary decision diagram (BDD) is defined as(3)F=itex,F1,F2=x·F1+x′·F2,where x∈X, x′ is the complement of x (if x=0, x′=1; else if x=1, x′=0), F1=Fx=1, and F2=Fx=0. A BDD has two terminal nodes that correspond to Boolean constants, 0 and 1, respectively. Each nonterminal node denotes a Boolean variable x with two branches corresponding to the Boolean expressions F1 of x=1 and F2 of x=0 for Shannon decomposition. Then each nonterminal node in BDD represents anite(x, F1, and F2) and it is different from the others.An ordered binary decision diagram (OBDD) is a BDD with a constant order for Boolean variables. The order of the Boolean variables from root to terminal is descending or increasing. Some operations can be defined between two OBDDs with the same variable order, and a new compact OBDD with the same variable order is obtained by an operation.For example, Figure1 shows the complete binary tree (Figure 1(a)) and the OBDD (Figure 1(b)) for the Boolean expression W=x1·x2+x1′·x3 with the variable order Π:x3≻x2≻x1. Obviously, the OBDD stores the same information with fewer nodes. If we trace the path ①→③→⑤→⑦ and reach terminal node 1, the value of W=x1·x2+x1′·x3 with variable assignment x1,x2,x3 = (0, 0, 1) is 1. Figure 1(c) shows the OBDD for expression U=x1·x2+x2′·x3 with the same variable order, and Figure 1(d) shows the new OBDD obtained by an operation “·” (conjunctive,And) between the two OBDDs.Figure 1
OBDD: (a) the complete binary tree ofW=x1⋅x2+x1′⋅x3; (b) the OBDD ofW; (c) the OBDD of U; (d) the OBDD of W⋅U.
(a) (b) (c) (d)


## 3.2. Multivalued Decision Diagram

A multivalued discrete functionF denotes the operation with n multivalued variables x1,x2,…,xn mapping to the range R.(4)F:L1×L2×⋯×Ln⟶R,where Li=0,1,…,li-1 is the domain of variable xi and R=r0,r1,…,rk-1 is the range.A MDD is a variant of a BDD. IfF denotes an expression on X=x1,x2,…,xn, thecase format of a MDD is defined as(5)F=casex,Fx=0,Fx=1,…,Fx=l-1=x=0·Fx=0+x=1·Fx=1+⋯+x=l-1·Fx=l-1=∑i=0l-1x=i·Fx=i,where x∈X. A MDD has k=R terminal nodes that correspond to the constants, r0,r1,…,rk-1, respectively, and each nonterminal node denotes a variable x with Di branches corresponding to the expressions Fx=i. Then each nonterminal node in a MDD represents acase format.Similar to an OBDD, a new compact MDD is obtained by an operation between two different MDDs with the same variable order, and Property1 is applicable for an OBDD or MDD. For example, Figure 2 shows the complete tree (Figure 2(a)) and the MDD (Figure 2(b)) for the numerical function W=x1·x2+x3 with the variable order Π:x3≻x2≻x1, L1=0,1, L2=0,1, and L3=0,1,2. Obviously, the MDD stores the same information with quite a few nodes. If we trace the path x3=1→x2=1→x1=1→2 and reach terminal node 1, the value of W=x1·x2+x3 with variable assignment x1,x2,x3 = (1, 1, 1) is 2. Figure 2(c) shows the MDD for the expression U=x1·x2·x3 with the same variable order, and Figure 2(d) shows the new MDD obtained by an operation “∗” (multiplication) between the two MDDs (if W=1 and U=2, then W∗U=2). In fact, the MDD can be further simplified. For W∗U, if W∗U>0 satisfies the requirement, terminal nodes 2 and 6 can be combined in one node 1 (True). This process will be used in our algorithm.Figure 2
MDD: (a) the complete tree ofW=x1⋅x2+x3; (b) the MDD ofW; (c) the MDD ofU; (d) the MDD of W∗U.
(a) (b) (c) (d)Property 1.
Applying the operation for a nonnull OBDD (or MDD)W and U will unite the intersecting spaces.


## 4. Symbolic Algorithms for MFN Reliability Evaluation

Because of the efficient data structures of decision diagrams, we take advantage of a decision diagram to evaluate the reliability of a MFN defined in Section2. We present the MFN_OBDD algorithm based on OBDD in Section 4.1 and the MFN_MDD algorithm based on MDD in Section 4.2. An example of the proposed algorithms is given in Section 4.3 and the complexity analysis of the algorithms is provided in Section 4.4. It is worth declaring that we are not discussing the decision diagram variables order, because it is an independent NP-hard problem. In this paper, the variables order is determined by the indexes of the edges and the edge states.


### 4.1. OBDD-Based Algorithm MFN_OBDD for Reliability Evaluation

The OBDD is used to study two-state system because of the two branches of the nodes in an OBDD. In this section, we propose an OBDD-based algorithm, MFN_OBDD, for the reliability evaluation of a MFN. The method for variable encoding refers to Zang et al.’s algorithm [19]; that is, each state of an arc is represented by a Boolean variable.The algorithm MFN_OBDD is comprised of two major parts: (1) generation of the OBDD that implicitly expresses all of the state vectors that satisfy the demandd, without listing the vectors; and (2) calculation of the reliability of the MFN by using the defined specific function and traversing the obtained OBDD. The steps of MFN_OBDD are performed as follows.Step 1.
Let each state of an arc be a Boolean variable.A={a1,a2,…,an}, and Ci=ci,0,ci,1,…,ci,si-1, for arc ai, ai,j∣0≤j≤si-1 denotes the set of state variables, and c(ai,j)=ci,j. According to the index of arcs, an≻⋯≻a1≻a2, and the index of states of ai, ai,si-1⋯≻ai,j⋯≻ai,1≻ai,0, we specify the variable order of the OBDDs to be Π:an,sn-1≻⋯an,1≻an,0⋯≻a1,(s1-1)≻⋯≻a1,0.Step 2.
According to Corollary1 in [1], we can obtain a flow flow(d)1=f1da1,a2,…,a2=(f1,1d,f1,2d,…,f1,nd); let c_=flowd1. The maximum capacities of arcs consist of the upper bound vector c-=(c1max,c2max,…,cnmax). Thus, all state vectors in the vector space Ω=c1,c2,…,cn∣f1,id≤ci≤cimax,ci∈Ci=c_,c¯ satisfy demand d. Then we generate the OBDD of Ω.Step  2.1. Generate the BDD of ai,j with cai,j≥f1,id with a defined operating function, named ai,j _BDD. The generation process is based on the following rules in the function:(6)ai,jBDD=StateBDDai,j,ci,j,f1,id=1,ai,j=1,ci,j≥f1,id,0,otherwise,ci,j∈Ci,j∈0,1,…,si-1,i∈1,2,…,n.Step  2.2. Construct the OBDD of arc ai with cai≥f1,id, named ai_OBDD, with a function as defined in the following formula:(7)ai_OBDD=ArcOBDDai,ai,1_BDD,ai,2_BDD,…,ai,si-1_BDD=ai,1_BDD+ai,2_BDD+⋯+ai,si-1_BDD=1,∃j,ai,j_BDD.high=1,0,otherwise,j∈0,1,…,si-1,i∈1,2,…,n,where “+” between ai,1_BDD and ai,2_BDD denotes a basic operation of BDD, that is calledOr, usually equivalent to disjunctive. And “ai,j_BDD.high” represents the high branch.Step  2.3. Use f1d_OBDD with a null initialization to save the OBDD of the state space Ω, and generate f1d_OBDD by a function as created in the following formula:(8)f1d_OBDD=FlowOBDDa1,a2,…,an=a1_OBDD·a2_OBDD·…·an_OBDD=1,∀i,ai_OBDD=1,0,otherwise,i∈1,2,…,n,where “·” between a1_OBDD and a2_OBDD denotes a basic operation of BDD, that is calledAnd, usually equivalent to conjunctive.Step 3.
The final OBDD is stored ind_OBDD, and the initialization is null.d_OBDD is generated with a function as the following:(9)d_OBDD=DemandOBDDd_OBDD,f1d_OBDD=d_OBDD+f1d_OBDD=1,d_OBDD=1∨f1d_OBDD=1,0,otherwise.Step 4.
Loop to execute Steps  2 and  3 until all flow(d)k is searched. A new flow satisfying the demandd, flowdk=fkda1,a2,…,an=(fk,1d,fk,2d,…,fk,nd), is obtained, and fkd_OBDD is generated under Π; then execute DemandOBDD() with replacing fkd_OBDD to f1d_OBDD in formula (9).Step 5.
Obtain the OBDD that implicitly expresses all the state vectors satisfying the demandd. Then construct a specific function, which is implemented with Lemma 3 and the Proof, with the state probability to traversed_OBDD, and the reliability of G is obtained.
In algorithm MFN_OBDD above, Steps  1–4 generate the OBDD that implicitly expresses all the state vectors satisfying the demandd, and Step  5 calculates the MFN reliability.Lemma 3.
If theite operation ofd_OBDD is defined as(10)F=iteai,j,U,W=ai,j·U+ai,j′·W,then the reliability can be calculated by a formula as(11)PF=1=pi,j·PU=1+PW=1,where pi,j is the probability of ci,j.Proof.
In algorithm MFN_OBDD, we note thatai,j is a Boolean variable that has two branches, but the probability of ci,j is fixed and unique. So we write a function(12)hai,j=1,ai,j=0,pi,j,ai,j=1,which can be explained as a virtual probability distribution of ai,j. Thus, the following deduction is produced:(13)PF=1=Eai,j·U+ai,j′·W=Eai,j·EU=1+Eai,j′·EW=1=hai,j=1·PU=1+hai,j=0·PW=1=pi,j·PU=1+PW=1.
That is, we can calculate the reliability of MFN_OBDD with this deduction whend_OBDD is traversed; Reld=PF=1. Therefore, the lemma is proved.


### 4.2. MDD-Based Algorithm MFN_MDD for Reliability Evaluation

A MDD with multibranches has often been used for reliability evaluation of multistate networks. Here, a MDD-based algorithm, MFN_MDD, is proposed for evaluating the MFN reliability. In algorithm MFN_MDD, each arc is represented by a multivalued variable.The algorithm MFN_MDD consists mainly of two parts: (1) construction of the MDD that implicitly expresses all of the state vectors satisfying the demandd, without listing the vectors, and (2) obtaining the MFN reliability by traversing the MDD. The steps in executing algorithm MFN_MDD are as follows.Step 1.
Let each arcai be a MDD variable. The variable order is specified by Π′:an≻⋯≻a2≻a1.Step 2.
It is the same as Step  2 in algorithm MFN_OBDD, and we obtain the flow(d)1 and the space Ω. The MDD of Ω is generated following Steps  2.1 and  2.2.Step  2.1. In order to simplify the format of MDD, generate the MDD with only two terminal nodes (0, 1) of arc ai, named ai_MDD, with a defined operation. The MDD is generated according to the following rules:(14)ai_MDD=ArcMDDai,ci,j,f1,id=1,ci,j≥f1,id,0,ci,j<f1,id,ci,j∈Ci,i∈1,2,…,n,j∈0,1,…,si-1.Step  2.2. According to the variable order Π′, the MDD, named f1d_MDD, is constructed relying on the operation defined with following formula:(15)f1d_MDD=FlowMDDa1_MDD,a2_MDD,…,an_MDD=a1_MDD·a2_MDD·…·an_MDD=1,∀ai_MDD.statej=1,0,otherwise,i∈1,2,…,n,j∈0,1,…,si-1,where “·” between a1_MDD and a2_MDD denotes a basic operation of MDD, similar to BDD, that is calledAnd, usually equivalent to conjunctive.Step 3.
Generate the result MDD, namedd_MDD with a null initialization, with the operation function defined in the following formula:(16)d_MDD=DemandMDDd_MDD,f1d_MDD=d_MDD+f1d_MDD=1,d_MDD=1∨f1d_MDD=1,0,otherwise,where “+” betweend_MDD and f1d_MDD denotes another basic operation of MDD, that is calledOr, usually equivalent to disjunctive.Step 4.
Loop to execute Steps  2 and  3 until all flow(d)i is searched the same as in Step  4 in algorithm MFN_OBDD, and a flow flow(d)k=fkda1,a2,…,an=(fk,1d,fk,2d,…,fk,nd) is obtained. Then fkd_MDD is generated under Π′, andd_MDD is constructed by DemandOBDD() with replacing fkd_MDD with f1d_MDD in formula (16).Step 5.
At this point,d_MDD obtained can implicitly express all of the state vectors satisfying the demand d. Then, a specific function is constructed with Lemma 4 and the Proof with the state probability to traversed_MDD, and the reliability of G is obtained.Lemma 4.
Ifcase of thed_MDD algorithm MFN_MDD is defined as(17)F=caseai,Fsai=0,Fsai=1,…,Fsai=si-1,where s(ai)=j denotes that ai is in the state of j with capacity ci,j, then the reliability can be calculated by a formula as(18)PF=1=∑j=0si-1pi,j·PFsai=j=1,where pi,j is the probability of ci,j.Proof.
In algorithm MFN_MDD, executing Step  1 obtainsflowdk=fk,1d,fk,2d,…,fk,nd satisfying demand d, and each state vector in flowdi,c- is satisfiable. After executing Steps  2 and 3,d_MDD is obtained. All of the paths ind_MDD from root to terminal node 1 represent the disjoint state space for demandd, named Ωflowd=c∣c∈⋃kflowdk,c¯={c∣F(c)≥d}. Thus, according to Definition 2, we can calculate the reliability, Reld=P{c∣Fc≥d}, with the state probability pi,j to traversed_MDD. Then,(19)P=c∣Fc≥d=PF=1=∑j=0sn-1psan=j·PFsan=j=1=∑j=0sn-1pn,j·PFsan=j=1,and because the root is an, we traversed_MDD starting with an above. Thus, the exact reliability is obtained, and thus the lemma is proved.


### 4.3. Illustrated Example

A multistate computer network described in [1, 7] is depicted in Figure 3 and is used to illustrate the proposed algorithms MFN_OBDD and MFN_MDD. The data of the arcs are shown in Table 1. Vertex 1 is the source, and vertex 4 is the sink. The demand from s to t reached 3; that is, d=3.Table 1
Data of arcs of Figure3.
Arc States/capacities Probabilities 0 1 2 3 0 1 2 3 a 1 0 1 2 3 0.05 0.10 0.25 0.60 a 2 0 1 — — 0.10 0.90 — — a 3 0 1 — — 0.10 0.90 — — a 4 0 1 — — 0.10 0.90 — — a 5 0 1 2 — 0.10 0.30 0.60 — a 6 0 1 2 — 0.05 0.25 0.70 —Figure 3
A multistate computer network.


#### 4.3.1. Algorithm MFN_OBDD Process

For the example depicted in Figure3, the steps of executing algorithm MFN_OBDD are as follows: (1) each state of an arc corresponds to a Boolean variable. For arc a1 with four states, four variables, a1,0, a1,1, a1,2, and a1,3, are set up. The Boolean variables for Figure 3 are listed in Table 2, and the variable order is specified with Π:a6,2≻a6,1≻a6,0≻a5,2≻⋯≻a1,3≻a1,2≻a1,1≻a1,0. (2) A flow, flow(3)1=2,1,0,0,2,1, is obtained, and c¯=(3,1,1,1,2,2). (3) For each variable, ai,j _BDD is constructed. The BDDs of the variables a1,0–a1,3 are shown in Figures 4(b)–4(e), respectively. (4) According to the variable order, ai_OBDD of all arcs are generated applying the operationOr. Figures 4(f)–4(k) show the OBDDs of a1–a6. (5) f1d_OBDD shown in Figure 4(a) is obtained using the operationAnd; thend_OBDD =d_OBDDOrf1d_OBDD, and the OBDD is the same as Figure 5(a). (6) A new flow flow(3)2=2,1,1,0,1,2 is obtained, and Steps  2–5 are repeated. Thus, f2d_OBDD is shown as Figure 5(b); the newd_OBDD is as depicted in Figure 6(a). (7) To obtain a new flow flow(3)3=(3,0,1,0,2,1) again, f3d_OBDD is as depicted in Figure 5(c), and the newd_OBDD is as depicted in Figure 6(b). (8) No more new flows are obtained. Thus, the OBDD in Figure 6(b) is the resultd_OBDD, and we traversed_OBDD with probabilities based on Lemma 3 to calculate the reliability with d=3; Rel(3)=0.611415.Table 2
Boolean variables of arcs of Figure3.
Variable Capacity Probability a 1 , 0 0 0.05 a 1 , 1 1 0.10 a 1 , 2 2 0.25 a 1 , 3 3 0.60 a 2 , 0 0 0.10 a 2 , 1 1 0.90 a 3 , 0 0 0.10 a 3 , 1 1 0.90 a 4 , 0 0 0.10 a 4 , 1 1 0.90 a 5 , 0 0 0.10 a 5 , 1 1 0.30 a 5 , 2 2 0.60 a 6 , 0 0 0.05 a 6 , 1 1 0.25 a 6 , 2 2 0.70Figure 4
a i , j _BDD and ai_OBDD in MFN_OBDD: (a) the original BDD of a1,0; (b)–(e) a1,0_BDD–a1,3_BDD; (f)–(k) a1_OBDD–a6_OBDD with ci≥f1,id.Figure 5
f k d_OBDD in MFN_OBDD: (a)–(c) f1d_OBDD()–f3d_OBDD.
(a)
f 1 d_OBDD (b)
f 2 d_OBDD (c)
f 3 d_OBDDFigure 6
d_OBDDs: (a)d_OBDD after first loop; (b) resultd_OBDD.
(a) (b)


#### 4.3.2. Algorithm MFN_MDD Process

For the example depicted in Figure3, steps in executing algorithm MFN_MDD are as follows: (1) each arc is a multistate variable, and the variable order is specified with Π′:a6≻a5≻⋯≻a2≻a1. (2) A flow, flow(3)1=2,1,0,0,2,1, is obtained. (3) For each variable, ai_MDD is constructed. In Figure 7, MDDs of a1–a6 are shown. (4) According to the variable order, f1d_MDD shown in Figure 8(a) is generated using operationAnd; then,d_MDD =d_MDDOrf1d_MDD, and the OBDD is the same as that depicted in Figure 8(a). (5) flow(3)2=(2,1,1,0,1,2) is obtained, and Steps  2–4 are repeated. Thus, f2d_MDD is shown as Figure 8(b), and the newd_MDD is shown as Figure 9(a). (6) flow(3)3=(3,0,1,0,2,1), and f3d_MDD is shown as Figure 8(c) and the newd_MDD as Figure 9(b). (7) The OBDD depicted in Figure 9(b) is the resultd_MDD, and the reliability with d=3 is calculated by traversing thed_OBDD with probabilities based on Lemma 4; Rel(3)=0.611415.Figure 7
a i_MDD in MFN_MDD: (a) the original MDD of a1; (b)–(g) a1_MDD–a6_MDD, respectively.Figure 8
f k d_MDD in MFN_MDD: (a) f1d_MDD; (b) f2d_MDD; (c) f3d_MDD.
(a) (b) (c)Figure 9
d_MDDs: (a)d_MDD after first loop; (b) resultd_MDD.
(a) (b)


### 4.4. Complexity Analysis of the Algorithms

For the algorithm MFN_OBDD, Step  1 takesn CPU time, and a flow(d) is obtained in Step  2 in Om3 CPU time according to Corollary 1 in [1]; the operationAnd orOr of OBDD takes On1n2 time, where n1 and n2 denote the numbers of the two operated OBDDs, respectively. If C=max⁡Ci represents the maximum number of states for the arcs, then generating OBDD(ai) takes O(|C|(|C|-1)/2) time; and thus Steps  2.1–2.3 take O(n·(C·C-1/2)+2C·2n·C-1/(2|C|-1)) time and looping Steps  2–4 take Om3+n·C2·#T time, where #T denotes the number of flow(d) that is unspecified, and the maximum flow is NP-hard, and #T in theory grows exponentially. According to Theorem 1 in [17], traversingd_OBDD to obtain the reliability takes OC·2n-1 time in the worst case. Therefore, the algorithm MFN_OBDD takes OC·2n+m3+n·C2·#T time.For the proposed MFN_MDD algorithm, Steps  2.1-2.2 takeOn·C+n·(n-1)/2 time; and looping of Steps  2–4 take Om3+n·C+nn-1/2+Cn·#T time. Theorem 1 in [17] states that it takes OCn/n to traverse thed_MDD in the worst case, so the computational complexity of MFN_MDD is Om3+n·C+n2+Cn·#T.For the decomposition algorithm of [1], thewhile … do loop repeats unspecified times #T1, and it takes another #T2 time because the number of flow(d) is unspecified. Thus, the algorithm takes Om3·#T1·#T2 at least. Obviously, the proposed algorithms have certain advantages.The state vectors are stored in the decision diagrams (OBDDs or MDDs), which are tree date structures for the algorithm proposed in this paper. In the worst case, the OBDD takesO2n·|C| storage space in MFN_OBDD, and the MDD takes OCn storage space in MFN_MDD. And the decomposition algorithm of [1] requires On·∏i=1nni memory space in the worst case. However, because of the implicit expression in a decision diagram, the number of nodes is far less than the number in the worst case.


## 4.1. OBDD-Based Algorithm MFN_OBDD for Reliability Evaluation

The OBDD is used to study two-state system because of the two branches of the nodes in an OBDD. In this section, we propose an OBDD-based algorithm, MFN_OBDD, for the reliability evaluation of a MFN. The method for variable encoding refers to Zang et al.’s algorithm [19]; that is, each state of an arc is represented by a Boolean variable.The algorithm MFN_OBDD is comprised of two major parts: (1) generation of the OBDD that implicitly expresses all of the state vectors that satisfy the demandd, without listing the vectors; and (2) calculation of the reliability of the MFN by using the defined specific function and traversing the obtained OBDD. The steps of MFN_OBDD are performed as follows.Step 1.
Let each state of an arc be a Boolean variable.A={a1,a2,…,an}, and Ci=ci,0,ci,1,…,ci,si-1, for arc ai, ai,j∣0≤j≤si-1 denotes the set of state variables, and c(ai,j)=ci,j. According to the index of arcs, an≻⋯≻a1≻a2, and the index of states of ai, ai,si-1⋯≻ai,j⋯≻ai,1≻ai,0, we specify the variable order of the OBDDs to be Π:an,sn-1≻⋯an,1≻an,0⋯≻a1,(s1-1)≻⋯≻a1,0.Step 2.
According to Corollary1 in [1], we can obtain a flow flow(d)1=f1da1,a2,…,a2=(f1,1d,f1,2d,…,f1,nd); let c_=flowd1. The maximum capacities of arcs consist of the upper bound vector c-=(c1max,c2max,…,cnmax). Thus, all state vectors in the vector space Ω=c1,c2,…,cn∣f1,id≤ci≤cimax,ci∈Ci=c_,c¯ satisfy demand d. Then we generate the OBDD of Ω.Step  2.1. Generate the BDD of ai,j with cai,j≥f1,id with a defined operating function, named ai,j _BDD. The generation process is based on the following rules in the function:(6)ai,jBDD=StateBDDai,j,ci,j,f1,id=1,ai,j=1,ci,j≥f1,id,0,otherwise,ci,j∈Ci,j∈0,1,…,si-1,i∈1,2,…,n.Step  2.2. Construct the OBDD of arc ai with cai≥f1,id, named ai_OBDD, with a function as defined in the following formula:(7)ai_OBDD=ArcOBDDai,ai,1_BDD,ai,2_BDD,…,ai,si-1_BDD=ai,1_BDD+ai,2_BDD+⋯+ai,si-1_BDD=1,∃j,ai,j_BDD.high=1,0,otherwise,j∈0,1,…,si-1,i∈1,2,…,n,where “+” between ai,1_BDD and ai,2_BDD denotes a basic operation of BDD, that is calledOr, usually equivalent to disjunctive. And “ai,j_BDD.high” represents the high branch.Step  2.3. Use f1d_OBDD with a null initialization to save the OBDD of the state space Ω, and generate f1d_OBDD by a function as created in the following formula:(8)f1d_OBDD=FlowOBDDa1,a2,…,an=a1_OBDD·a2_OBDD·…·an_OBDD=1,∀i,ai_OBDD=1,0,otherwise,i∈1,2,…,n,where “·” between a1_OBDD and a2_OBDD denotes a basic operation of BDD, that is calledAnd, usually equivalent to conjunctive.Step 3.
The final OBDD is stored ind_OBDD, and the initialization is null.d_OBDD is generated with a function as the following:(9)d_OBDD=DemandOBDDd_OBDD,f1d_OBDD=d_OBDD+f1d_OBDD=1,d_OBDD=1∨f1d_OBDD=1,0,otherwise.Step 4.
Loop to execute Steps  2 and  3 until all flow(d)k is searched. A new flow satisfying the demandd, flowdk=fkda1,a2,…,an=(fk,1d,fk,2d,…,fk,nd), is obtained, and fkd_OBDD is generated under Π; then execute DemandOBDD() with replacing fkd_OBDD to f1d_OBDD in formula (9).Step 5.
Obtain the OBDD that implicitly expresses all the state vectors satisfying the demandd. Then construct a specific function, which is implemented with Lemma 3 and the Proof, with the state probability to traversed_OBDD, and the reliability of G is obtained.
In algorithm MFN_OBDD above, Steps  1–4 generate the OBDD that implicitly expresses all the state vectors satisfying the demandd, and Step  5 calculates the MFN reliability.Lemma 3.
If theite operation ofd_OBDD is defined as(10)F=iteai,j,U,W=ai,j·U+ai,j′·W,then the reliability can be calculated by a formula as(11)PF=1=pi,j·PU=1+PW=1,where pi,j is the probability of ci,j.Proof.
In algorithm MFN_OBDD, we note thatai,j is a Boolean variable that has two branches, but the probability of ci,j is fixed and unique. So we write a function(12)hai,j=1,ai,j=0,pi,j,ai,j=1,which can be explained as a virtual probability distribution of ai,j. Thus, the following deduction is produced:(13)PF=1=Eai,j·U+ai,j′·W=Eai,j·EU=1+Eai,j′·EW=1=hai,j=1·PU=1+hai,j=0·PW=1=pi,j·PU=1+PW=1.
That is, we can calculate the reliability of MFN_OBDD with this deduction whend_OBDD is traversed; Reld=PF=1. Therefore, the lemma is proved.


## 4.2. MDD-Based Algorithm MFN_MDD for Reliability Evaluation

A MDD with multibranches has often been used for reliability evaluation of multistate networks. Here, a MDD-based algorithm, MFN_MDD, is proposed for evaluating the MFN reliability. In algorithm MFN_MDD, each arc is represented by a multivalued variable.The algorithm MFN_MDD consists mainly of two parts: (1) construction of the MDD that implicitly expresses all of the state vectors satisfying the demandd, without listing the vectors, and (2) obtaining the MFN reliability by traversing the MDD. The steps in executing algorithm MFN_MDD are as follows.Step 1.
Let each arcai be a MDD variable. The variable order is specified by Π′:an≻⋯≻a2≻a1.Step 2.
It is the same as Step  2 in algorithm MFN_OBDD, and we obtain the flow(d)1 and the space Ω. The MDD of Ω is generated following Steps  2.1 and  2.2.Step  2.1. In order to simplify the format of MDD, generate the MDD with only two terminal nodes (0, 1) of arc ai, named ai_MDD, with a defined operation. The MDD is generated according to the following rules:(14)ai_MDD=ArcMDDai,ci,j,f1,id=1,ci,j≥f1,id,0,ci,j<f1,id,ci,j∈Ci,i∈1,2,…,n,j∈0,1,…,si-1.Step  2.2. According to the variable order Π′, the MDD, named f1d_MDD, is constructed relying on the operation defined with following formula:(15)f1d_MDD=FlowMDDa1_MDD,a2_MDD,…,an_MDD=a1_MDD·a2_MDD·…·an_MDD=1,∀ai_MDD.statej=1,0,otherwise,i∈1,2,…,n,j∈0,1,…,si-1,where “·” between a1_MDD and a2_MDD denotes a basic operation of MDD, similar to BDD, that is calledAnd, usually equivalent to conjunctive.Step 3.
Generate the result MDD, namedd_MDD with a null initialization, with the operation function defined in the following formula:(16)d_MDD=DemandMDDd_MDD,f1d_MDD=d_MDD+f1d_MDD=1,d_MDD=1∨f1d_MDD=1,0,otherwise,where “+” betweend_MDD and f1d_MDD denotes another basic operation of MDD, that is calledOr, usually equivalent to disjunctive.Step 4.
Loop to execute Steps  2 and  3 until all flow(d)i is searched the same as in Step  4 in algorithm MFN_OBDD, and a flow flow(d)k=fkda1,a2,…,an=(fk,1d,fk,2d,…,fk,nd) is obtained. Then fkd_MDD is generated under Π′, andd_MDD is constructed by DemandOBDD() with replacing fkd_MDD with f1d_MDD in formula (16).Step 5.
At this point,d_MDD obtained can implicitly express all of the state vectors satisfying the demand d. Then, a specific function is constructed with Lemma 4 and the Proof with the state probability to traversed_MDD, and the reliability of G is obtained.Lemma 4.
Ifcase of thed_MDD algorithm MFN_MDD is defined as(17)F=caseai,Fsai=0,Fsai=1,…,Fsai=si-1,where s(ai)=j denotes that ai is in the state of j with capacity ci,j, then the reliability can be calculated by a formula as(18)PF=1=∑j=0si-1pi,j·PFsai=j=1,where pi,j is the probability of ci,j.Proof.
In algorithm MFN_MDD, executing Step  1 obtainsflowdk=fk,1d,fk,2d,…,fk,nd satisfying demand d, and each state vector in flowdi,c- is satisfiable. After executing Steps  2 and 3,d_MDD is obtained. All of the paths ind_MDD from root to terminal node 1 represent the disjoint state space for demandd, named Ωflowd=c∣c∈⋃kflowdk,c¯={c∣F(c)≥d}. Thus, according to Definition 2, we can calculate the reliability, Reld=P{c∣Fc≥d}, with the state probability pi,j to traversed_MDD. Then,(19)P=c∣Fc≥d=PF=1=∑j=0sn-1psan=j·PFsan=j=1=∑j=0sn-1pn,j·PFsan=j=1,and because the root is an, we traversed_MDD starting with an above. Thus, the exact reliability is obtained, and thus the lemma is proved.


## 4.3. Illustrated Example

A multistate computer network described in [1, 7] is depicted in Figure 3 and is used to illustrate the proposed algorithms MFN_OBDD and MFN_MDD. The data of the arcs are shown in Table 1. Vertex 1 is the source, and vertex 4 is the sink. The demand from s to t reached 3; that is, d=3.Table 1
Data of arcs of Figure3.
Arc States/capacities Probabilities 0 1 2 3 0 1 2 3 a 1 0 1 2 3 0.05 0.10 0.25 0.60 a 2 0 1 — — 0.10 0.90 — — a 3 0 1 — — 0.10 0.90 — — a 4 0 1 — — 0.10 0.90 — — a 5 0 1 2 — 0.10 0.30 0.60 — a 6 0 1 2 — 0.05 0.25 0.70 —Figure 3
A multistate computer network.


### 4.3.1. Algorithm MFN_OBDD Process

For the example depicted in Figure3, the steps of executing algorithm MFN_OBDD are as follows: (1) each state of an arc corresponds to a Boolean variable. For arc a1 with four states, four variables, a1,0, a1,1, a1,2, and a1,3, are set up. The Boolean variables for Figure 3 are listed in Table 2, and the variable order is specified with Π:a6,2≻a6,1≻a6,0≻a5,2≻⋯≻a1,3≻a1,2≻a1,1≻a1,0. (2) A flow, flow(3)1=2,1,0,0,2,1, is obtained, and c¯=(3,1,1,1,2,2). (3) For each variable, ai,j _BDD is constructed. The BDDs of the variables a1,0–a1,3 are shown in Figures 4(b)–4(e), respectively. (4) According to the variable order, ai_OBDD of all arcs are generated applying the operationOr. Figures 4(f)–4(k) show the OBDDs of a1–a6. (5) f1d_OBDD shown in Figure 4(a) is obtained using the operationAnd; thend_OBDD =d_OBDDOrf1d_OBDD, and the OBDD is the same as Figure 5(a). (6) A new flow flow(3)2=2,1,1,0,1,2 is obtained, and Steps  2–5 are repeated. Thus, f2d_OBDD is shown as Figure 5(b); the newd_OBDD is as depicted in Figure 6(a). (7) To obtain a new flow flow(3)3=(3,0,1,0,2,1) again, f3d_OBDD is as depicted in Figure 5(c), and the newd_OBDD is as depicted in Figure 6(b). (8) No more new flows are obtained. Thus, the OBDD in Figure 6(b) is the resultd_OBDD, and we traversed_OBDD with probabilities based on Lemma 3 to calculate the reliability with d=3; Rel(3)=0.611415.Table 2
Boolean variables of arcs of Figure3.
Variable Capacity Probability a 1 , 0 0 0.05 a 1 , 1 1 0.10 a 1 , 2 2 0.25 a 1 , 3 3 0.60 a 2 , 0 0 0.10 a 2 , 1 1 0.90 a 3 , 0 0 0.10 a 3 , 1 1 0.90 a 4 , 0 0 0.10 a 4 , 1 1 0.90 a 5 , 0 0 0.10 a 5 , 1 1 0.30 a 5 , 2 2 0.60 a 6 , 0 0 0.05 a 6 , 1 1 0.25 a 6 , 2 2 0.70Figure 4
a i , j _BDD and ai_OBDD in MFN_OBDD: (a) the original BDD of a1,0; (b)–(e) a1,0_BDD–a1,3_BDD; (f)–(k) a1_OBDD–a6_OBDD with ci≥f1,id.Figure 5
f k d_OBDD in MFN_OBDD: (a)–(c) f1d_OBDD()–f3d_OBDD.
(a)
f 1 d_OBDD (b)
f 2 d_OBDD (c)
f 3 d_OBDDFigure 6
d_OBDDs: (a)d_OBDD after first loop; (b) resultd_OBDD.
(a) (b)


### 4.3.2. Algorithm MFN_MDD Process

For the example depicted in Figure3, steps in executing algorithm MFN_MDD are as follows: (1) each arc is a multistate variable, and the variable order is specified with Π′:a6≻a5≻⋯≻a2≻a1. (2) A flow, flow(3)1=2,1,0,0,2,1, is obtained. (3) For each variable, ai_MDD is constructed. In Figure 7, MDDs of a1–a6 are shown. (4) According to the variable order, f1d_MDD shown in Figure 8(a) is generated using operationAnd; then,d_MDD =d_MDDOrf1d_MDD, and the OBDD is the same as that depicted in Figure 8(a). (5) flow(3)2=(2,1,1,0,1,2) is obtained, and Steps  2–4 are repeated. Thus, f2d_MDD is shown as Figure 8(b), and the newd_MDD is shown as Figure 9(a). (6) flow(3)3=(3,0,1,0,2,1), and f3d_MDD is shown as Figure 8(c) and the newd_MDD as Figure 9(b). (7) The OBDD depicted in Figure 9(b) is the resultd_MDD, and the reliability with d=3 is calculated by traversing thed_OBDD with probabilities based on Lemma 4; Rel(3)=0.611415.Figure 7
a i_MDD in MFN_MDD: (a) the original MDD of a1; (b)–(g) a1_MDD–a6_MDD, respectively.Figure 8
f k d_MDD in MFN_MDD: (a) f1d_MDD; (b) f2d_MDD; (c) f3d_MDD.
(a) (b) (c)Figure 9
d_MDDs: (a)d_MDD after first loop; (b) resultd_MDD.
(a) (b)


## 4.3.1. Algorithm MFN_OBDD Process

For the example depicted in Figure3, the steps of executing algorithm MFN_OBDD are as follows: (1) each state of an arc corresponds to a Boolean variable. For arc a1 with four states, four variables, a1,0, a1,1, a1,2, and a1,3, are set up. The Boolean variables for Figure 3 are listed in Table 2, and the variable order is specified with Π:a6,2≻a6,1≻a6,0≻a5,2≻⋯≻a1,3≻a1,2≻a1,1≻a1,0. (2) A flow, flow(3)1=2,1,0,0,2,1, is obtained, and c¯=(3,1,1,1,2,2). (3) For each variable, ai,j _BDD is constructed. The BDDs of the variables a1,0–a1,3 are shown in Figures 4(b)–4(e), respectively. (4) According to the variable order, ai_OBDD of all arcs are generated applying the operationOr. Figures 4(f)–4(k) show the OBDDs of a1–a6. (5) f1d_OBDD shown in Figure 4(a) is obtained using the operationAnd; thend_OBDD =d_OBDDOrf1d_OBDD, and the OBDD is the same as Figure 5(a). (6) A new flow flow(3)2=2,1,1,0,1,2 is obtained, and Steps  2–5 are repeated. Thus, f2d_OBDD is shown as Figure 5(b); the newd_OBDD is as depicted in Figure 6(a). (7) To obtain a new flow flow(3)3=(3,0,1,0,2,1) again, f3d_OBDD is as depicted in Figure 5(c), and the newd_OBDD is as depicted in Figure 6(b). (8) No more new flows are obtained. Thus, the OBDD in Figure 6(b) is the resultd_OBDD, and we traversed_OBDD with probabilities based on Lemma 3 to calculate the reliability with d=3; Rel(3)=0.611415.Table 2
Boolean variables of arcs of Figure3.
Variable Capacity Probability a 1 , 0 0 0.05 a 1 , 1 1 0.10 a 1 , 2 2 0.25 a 1 , 3 3 0.60 a 2 , 0 0 0.10 a 2 , 1 1 0.90 a 3 , 0 0 0.10 a 3 , 1 1 0.90 a 4 , 0 0 0.10 a 4 , 1 1 0.90 a 5 , 0 0 0.10 a 5 , 1 1 0.30 a 5 , 2 2 0.60 a 6 , 0 0 0.05 a 6 , 1 1 0.25 a 6 , 2 2 0.70Figure 4
a i , j _BDD and ai_OBDD in MFN_OBDD: (a) the original BDD of a1,0; (b)–(e) a1,0_BDD–a1,3_BDD; (f)–(k) a1_OBDD–a6_OBDD with ci≥f1,id.Figure 5
f k d_OBDD in MFN_OBDD: (a)–(c) f1d_OBDD()–f3d_OBDD.
(a)
f 1 d_OBDD (b)
f 2 d_OBDD (c)
f 3 d_OBDDFigure 6
d_OBDDs: (a)d_OBDD after first loop; (b) resultd_OBDD.
(a) (b)


## 4.3.2. Algorithm MFN_MDD Process

For the example depicted in Figure3, steps in executing algorithm MFN_MDD are as follows: (1) each arc is a multistate variable, and the variable order is specified with Π′:a6≻a5≻⋯≻a2≻a1. (2) A flow, flow(3)1=2,1,0,0,2,1, is obtained. (3) For each variable, ai_MDD is constructed. In Figure 7, MDDs of a1–a6 are shown. (4) According to the variable order, f1d_MDD shown in Figure 8(a) is generated using operationAnd; then,d_MDD =d_MDDOrf1d_MDD, and the OBDD is the same as that depicted in Figure 8(a). (5) flow(3)2=(2,1,1,0,1,2) is obtained, and Steps  2–4 are repeated. Thus, f2d_MDD is shown as Figure 8(b), and the newd_MDD is shown as Figure 9(a). (6) flow(3)3=(3,0,1,0,2,1), and f3d_MDD is shown as Figure 8(c) and the newd_MDD as Figure 9(b). (7) The OBDD depicted in Figure 9(b) is the resultd_MDD, and the reliability with d=3 is calculated by traversing thed_OBDD with probabilities based on Lemma 4; Rel(3)=0.611415.Figure 7
a i_MDD in MFN_MDD: (a) the original MDD of a1; (b)–(g) a1_MDD–a6_MDD, respectively.Figure 8
f k d_MDD in MFN_MDD: (a) f1d_MDD; (b) f2d_MDD; (c) f3d_MDD.
(a) (b) (c)Figure 9
d_MDDs: (a)d_MDD after first loop; (b) resultd_MDD.
(a) (b)


## 4.4. Complexity Analysis of the Algorithms

For the algorithm MFN_OBDD, Step  1 takesn CPU time, and a flow(d) is obtained in Step  2 in Om3 CPU time according to Corollary 1 in [1]; the operationAnd orOr of OBDD takes On1n2 time, where n1 and n2 denote the numbers of the two operated OBDDs, respectively. If C=max⁡Ci represents the maximum number of states for the arcs, then generating OBDD(ai) takes O(|C|(|C|-1)/2) time; and thus Steps  2.1–2.3 take O(n·(C·C-1/2)+2C·2n·C-1/(2|C|-1)) time and looping Steps  2–4 take Om3+n·C2·#T time, where #T denotes the number of flow(d) that is unspecified, and the maximum flow is NP-hard, and #T in theory grows exponentially. According to Theorem 1 in [17], traversingd_OBDD to obtain the reliability takes OC·2n-1 time in the worst case. Therefore, the algorithm MFN_OBDD takes OC·2n+m3+n·C2·#T time.For the proposed MFN_MDD algorithm, Steps  2.1-2.2 takeOn·C+n·(n-1)/2 time; and looping of Steps  2–4 take Om3+n·C+nn-1/2+Cn·#T time. Theorem 1 in [17] states that it takes OCn/n to traverse thed_MDD in the worst case, so the computational complexity of MFN_MDD is Om3+n·C+n2+Cn·#T.For the decomposition algorithm of [1], thewhile … do loop repeats unspecified times #T1, and it takes another #T2 time because the number of flow(d) is unspecified. Thus, the algorithm takes Om3·#T1·#T2 at least. Obviously, the proposed algorithms have certain advantages.The state vectors are stored in the decision diagrams (OBDDs or MDDs), which are tree date structures for the algorithm proposed in this paper. In the worst case, the OBDD takesO2n·|C| storage space in MFN_OBDD, and the MDD takes OCn storage space in MFN_MDD. And the decomposition algorithm of [1] requires On·∏i=1nni memory space in the worst case. However, because of the implicit expression in a decision diagram, the number of nodes is far less than the number in the worst case.


## 5. Experimental Results

In this paper, the algorithm MFN_OBDD is implemented based on the software package CUDD developed at the University of Colorado [27], while the algorithm MFN_MDD is programmed using the MDD package MEDDLY developed at Iowa State University. Both of the proposed algorithms are executed on a workstation running in Ubuntu 14.04 with 3.3 GHz, with 4 GB of RAM.Figure10 depicts a multistate network with 12 vertexes and 21 arcs from [1]. Vertex 1 is the source and vertex 12 is the sink. Each arc has three states with probabilities as specified in Table 3. Table 4 shows the experimental results for both the proposed algorithms and the decomposition algorithm of [1] with demand d ranging from 1 to 5. Studying Table 4 leads us to conclude the following:(1)
For the same demand, the number of decision diagram nodes generated in the MFN_MDD algorithm is less than the collections of [1] and MFN_OBDD’s nodes is and no more than 65. When demand is small, for example, d=1,2,3, the collections generated in the algorithm in [1] are less than MFN_OBDD’s nodes, but more than MFN_OBDD’s nodes when demand is large (d=4,5). In addition, the number of nodes in MFN_MDD is far less than the collections number in [1]. However, according to the size of defined collection or node in different algorithms, the storage space is ordered as [1] > MFN_OBDD > MFN_MDD.(2)
The CPU time for executing the proposed algorithms increases with increasingd, and the CPU time for executing the MFN_MDD algorithm is less than that for the MFN_OBDD algorithm. The execution efficiency of MFN_MDD algorithm is higher than the algorithm in [1] with a small demand (d=1,2). And in other cases, the execution efficiency of proposed algorithm is slightly lower than the algorithm in [1].(3)
The loops number of proposed algorithms depend on the demandd. In most cases, it is much smaller than the loops number of the decomposition algorithm in [1].Table 3
States and probabilities of arcs for Figure10.
Arcs States Probabilities 0 1 2 0 1 2 1 0 3 5 0.1163 0.0616 0.8221 2 0 3 5 0.1624 0.1224 0.7152 3 0 3 5 0.2014 0.900 0.7086 4 0 3 5 0.0689 0.1155 0.8156 5 0 3 5 0.1863 0.1366 0.6771 6 0 3 5 0.2244 0.0214 0.7542 7 0 3 5 0.1260 0.0495 0.8245 8 0 3 5 0.2220 0.1334 0.6445 9 0 3 5 0.1265 0.0762 0.7973 10 0 3 5 0.2993 0.0343 0.6664 11 0 3 5 0.3016 0.0813 0.6171 12 0 3 5 0.2385 0.0785 0.6830 13 0 3 5 0.3460 0.0269 0.6272 14 0 3 5 0.3512 0.0441 0.6048 15 0 3 5 0.0373 0.0830 0.8797 16 0 3 5 0.0326 0.0182 0.9492 17 0 3 5 0.0231 0.1268 0.8501 18 0 3 5 0.3935 0.0625 0.5440 19 0 3 5 0.0651 0.0457 0.8893 20 0 3 5 0.0052 0.0411 0.9537 21 0 3 5 0.0222 0.0192 0.9586Table 4
Experimental results for different algorithms.
Demand Reference [1] Proposed algorithms MFN_OBDD MFN_MDD Loop Collection1 Storage (bytes) CPU time (s) Loop Node Storage (bytes) CPU time (s) Node Storage (bytes) CPU time (s) 1 294 51,744 0.016 636 611 7,332 0.024046 42 1,848 0.001928 17 2 294 51,744 0.016 636 611 7,332 0.216549 43 1,892 0.010049 153 3 294 51,744 0.016 636 611 7,332 1.3385 43 1,892 0.032208 969 4 9486 1,669,536 0.268 20,002 3,514 42,144 6.64096 51 2,244 0.475073 4,845 5 9486 1,669,536 0.268 20,002 3,514 42,144 27.7825 62 2,728 1.28560 20,349 1: collection is the main data structure of the algorithm in [1]. It contains the lower bound of edge state vector, the upper bound of edge state vector, the edge state flow vector, the vector of nonzero state edges, and two constants.Figure 10
A multistate network.In order to analyze the proposed algorithms, we select four more networks generated randomly; three of them, depicted in Figures11(a)–11(c), are from [14], and that depicted in Figure 11(d) is from [1]. In this experiment, we specify that each arc of the five networks (including Figure 10) has three capacities, 0, 1, and 3, and the probabilities of states 0, 1, and 3 for each arc are 0.05, 0.25, and 0.70, respectively. Moreover, the demand is d=3. Table 5 lists the experimental results for the proposed algorithms. Two conclusions can be drawn from studying Table 5:(1)
For the same network, the number of nodes and the number of variables of the DD generated in the MFN_MDD algorithm are both less than that of MFN_OBDD. The MFN_OBDD algorithm takes more CPU time to run. Because a state is a Boolean variable in the MFN_OBDD algorithm and the MFN_MDD algorithm makes an arc into a multivalue variable, the DD generated in the MFN_OBDD algorithm has a larger scale, thus leading to the conclusions described directly above.(2)
If the number of arcs is fixed and the number of vertexes is increased, such as in the networks depicted in Figures11(b), 11(c), and 7, the experiments show that the number of nodes generated in either MFN_OBDD or MFN_MDD algorithm decreases. The CPU time also decreases. Therefore, in the case of the same arc number, both of the proposed algorithms have more advantages for sparse networks.Table 5
Experimental results for proposed algorithms.
Network Reliability MFN_OBDD MFN_MDD Figure Vertex Arc Variable Node CPU Time (s) Variable Node CPU time (s) Figure11(a) 7 22 0.967046 43 1534 0.826896 16 50 0.046191 Figure11(b) 10 21 0.970909 64 33933 9.37805 21 64 2.46028 Figure11(c) 11 21 0.947015 64 8223 1.63739 21 64 0.304223 Figure10 12 21 0.949288 64 6374 1.30824 21 42 0.01145 Figure11(d) 15 30 0.974668 91 254307 340.043 30 91 253.156Figure 11
Four multistate networks.
(a) (b) (c) (d)


## 6. Conclusions

In this paper, we have extended the definition of a MFN model and have proposed the MFN_OBDD algorithm based on BDD and the MFN_MDD algorithm based on MDD to solve the problems in evaluating MFN reliability. The algorithms were applied to a simple MFN, and the attendant processes verified the feasibility of the algorithms. Experiments were carried out on five different networks, and the results show that (1) for the same network, the MFN_OBDD algorithm is more effective than the algorithm presented in [1] in terms of storage; in addition, due to the multibranch nature of a MDD, the storage efficiency of the MFN_MDD algorithm is better than that of the MFN_OBDD algorithm; (2) the runtime and the variables number of generated decision diagram in MFN_MDD algorithm are both less than those of the MFN_OBDD algorithm; (3) the storage space and CPU time of the proposed algorithms depend on the demand; and (4) the proposed algorithms have more advantages for sparse networks with the same number of arcs. The correctness, accuracy, and validity of the proposed algorithms were verified by the experiments. Furthermore, it would be worthwhile to improve the efficiency of algorithms’ implementation.



---

*Source: 6908120-2016-12-25.xml*