# A Minimal Path-Based Method for Computing Multistate Network Reliability

Authors: Xiu-Zhen Xu; Yi-Feng Niu; Can He
Journal: Complexity
 (2020)

---

## Abstract

Most of modern technological networks that can perform their tasks with various distinctive levels of efficiency are multistate networks, and reliability is a fundamental attribute for their safe operation and optimal improvement. For a multistate network, the two-terminal reliability at demand leveld, defined as the probability that the network capacity is greater than or equal to a demand of d units, can be calculated in terms of multistate minimal paths, called d-minimal paths (d-MPs) for short. This paper presents an efficient algorithm to find all d-MPs for the multistate two-terminal reliability problem. To advance the solution efficiency of d-MPs, an improved model is developed by redefining capacity constraints of network components and minimal paths (MPs). Furthermore, an effective technique is proposed to remove duplicate d-MPs that are generated multiple times during solution. A simple example is provided to demonstrate the proposed algorithm step by step. In addition, through computational experiments conducted on benchmark networks, it is found that the proposed algorithm is more efficient.


---

## Body

## 1. Introduction

The economic development and social well-being of modern society are increasingly dependent on the quality of service (QoS) of a variety of technological networks, such as computer and communication networks [1, 2], manufacturing networks [3], logistics/supply chain networks [4–7], and power transmission networks [8], and a major challenge which we have to face is ensuring their safety and normal operation against potential malfunctions. Reliability is a fundamental attribute for the safe operation of modern technological networks [9], and demands for the quantification of network reliability are steadily growing in the networked society [10].A network that can have a number of distinctive levels of performance is called multistate network [11, 12]. Most of modern technological networks are often deemed as multistate networks for reliability analysis. For instance, a computer network can be modeled as a multistate network with a set of edges (links) and a set of nodes, in which an edge represents a transmission line and a node denotes a computer center involving several routers or switches. In practice, a transmission line is composed of several physical lines, such as fiber cables, twisted pairs, or coaxial cables, and all of the physical lines may provide a specific capacity or fail, that is, every transmission line has multiple capacities (states) with a probability distribution, which results in a number of different levels of transmission capacity for the whole computer network. Such a computer network is thus treated as a typical multistate network. Multistate network with components having many different states (different levels of performance) is an extension of the traditional binary-state network with components having only two possible states: either completely failed or perfectly functioning [13–16]. Given a multistate network, the two-terminal reliability at demand level d, denoted as Rd, is defined as the probability that the network capacity is greater than or equal to a demand of d units. A variety of algorithms have been presented to calculate Rd, and these algorithms can be broadly categorized into direct methods and indirect methods [17]. One important type of indirect method for the exact evaluation of Rd is using d-minimal paths (d-MPs). A d-MP, say x, is a minimal network state vector with the max-flow of the network under x being equal to d. Provided that all d-MPs are found, the well-known Inclusion-Exclusion method [14], the Sum of Disjoint Products method [18–20], or the State Space Decomposition method [21] are available to exactly compute the two-terminal reliability at demand level d. Thus, solving all d-MPs is a critical issue to the two-terminal reliability at demand level d.There are two important mathematical models with respect to thed-MP problem. The first mathematical model for solving d-MPs is originally proposed by Lin et al. [22]. This model requires all minimal paths (MPs) and contains three constraints that are established by the network structure and the flow-conservation law. An MP is a subset of edges, such that if any edge is removed from it, the remaining is no longer a path. The second mathematical model for solving d-MPs is proposed by Yeh [23]. This model without requiring MPs information is a component-based formulation with three constraints. Note that the model by Yeh [23] is derived from the well-known max-flow mathematical programming model; thus, it is more applicable to directed networks. Based on the model of Yeh, Xu et al. [24] combined the max-flow algorithm and the implicit enumeration method to seek d-MPs. Niu et al. [25] recently improved the model by Yeh [23] and pointed out that if the model is applied to an undirected network, each undirected edge in the network should be treated as two directed edges with the opposite direction. In such a case, however, the number of variables in the model is dramatically increased, which could significantly add to the difficulty of the d-MP problem.The model by Lin et al. [22] applicable to both directed networks and undirected networks has been widely used by most of the existing algorithms [26–30]. For example, Lin [26] proposed a simple method to solve d-MPs of a network with unreliable nodes; Yeh [27] proposed a cycle-checking method to verify whether a feasible solution to the model is a d-MP; Chen and Lin [28] suggested the fast enumeration method to solve all of the feasible solutions to the model; Forghani-Elahabad and Bonani [29] proposed an improved enumeration method to search for d-MPs. Lin and Chen [30] recently proposed a new max-flow evaluation method to find d-MPs.In addition to the methods based on the above two models, there are also several other methods for solvingd-MPs. For example, Satitsatian and Kapur [31] proposed an approximate algorithm to find a subset of d-MPs using the minimal improvement paths algorithm; Ramirez-Marquez et al. [32] proposed an algorithm to find potential d-MPs using the information sharing approach that a selected number of edges share information among each other. Different from the abovementioned methods that find d-MPs for a fixed demand level d, Bai et al. [33] considered the problem of finding all d-MPs for all possible demand levels and proposed a recursive method to solve it. By overcoming the obstacles of the method by Bai et al. [33], Yeh [34] recently proposed a new addition-based algorithm with better time complexity.As stated earlier, the model by Lin et al. [22] has been extensively applied to the d-MP problem. And yet, we note that the capacity constraints in this model are too relaxed, such that a large number of enumerations need to be implemented in order to find all d-MPs, which to an extent influences the computational efficiency. Recently, Niu et al. [25] improved Yeh’s model [23] by imposing stronger capacity constraints on network components. Because the capacity constraints of network components in both models are identical, the ideas in [25] can also be used to improve the model by Lin et al. [22]. In addition, the major cost for solving d-MPs from the model by Lin et al. [22] lies in identifying duplicate d-MPs, and an effective and efficient method for removing duplicates is always desirable. This paper is devoted to developing a new efficient algorithm for finding all d-MPs. To advance the solution efficiency of d-MPs, an improved model is constructed by redefining capacity constraints of network components and MPs. The constructed model is an improvement to the model by Lin et al. [22]. Furthermore, a technique with better efficiency is proposed to remove duplicate d-MPs. The time complexity of the proposed algorithm is analyzed, and a simple example is provided to illustrate the proposed algorithm. Finally, through computational experiments, it is found that the proposed algorithm is more efficient in finding all d-MPs.The rest of this paper is organized as follows. Section2 introduces the multistate network model, the fundamental results for solving d-MPs, and the Inclusion-Exclusion method. In Section 3, an improved model for finding d-MPs is constructed, and an efficient technique is developed to remove duplicate d-MPs. Also, an algorithm for solving d-MPs without duplicates is proposed, together with a discussion on its time complexity. In Section 4, an illustrative example is provided to demonstrate the proposed algorithm. Computational experiments on two benchmark networks are performed in Section 5 to investigate the efficiency of the proposed algorithm through comparisons with the existing methods. Section 6 presents the concluding remarks.


## 2. Preliminaries

### 2.1. Multistate Network

Consider a multistate networkGV,E,W with the unique source node s and the unique sink node t, where V=s,1,2,…,n,t is the set of nodes, E=e1,e2,…,em is the set of edges, and W=W1,W2,…,Wm is the largest state vector with Wi being the largest capacity of ei for 1≤i≤m. A network state vector x=x1,x2,…,xm indicates the current capacity of each edge in the network, where the state of ei is defined by xi taking integer values from 0 to Wi. The max-flow of the network under x (or the network capacity under x) is denoted by Mx, and Mx is always called the structure function of a multistate network [25, 31, 35]. By D, the max-flow of the network under the largest state vector W is denoted, i.e., D=MW. Then, Mx≤D holds for any state vector x.The multistate network discussed herein satisfies the following assumptions [28, 30]. (1) Each node is perfectly reliable, which means no capacity constraint is imposed on nodes. (2) The state/capacity of each edge ei1≤i≤m is a nonnegative integer-valued random variable which takes values from 0 to Wi according to a given distribution. (3) The states/capacities of different edges are statistically independent. (4) All flows in the network obey the conservation law, i.e., total flows into and from a node (not source and sink nodes) are all equal.


### 2.2. CalculatingRd in Terms of D-MPs

As mentioned before, once alld-MPs are found, the well-known Inclusion-Exclusion method [14], the Sum of Disjoint Products method [18–20], or the State Space Decomposition method [21] are available to calculate Rd. While the Inclusion-Exclusion method is not as efficient as the Sum of Disjoint Products method [18–20] or the State Space Decomposition method [21], it is simple and easy to understand. Therefore, we briefly introduce how it performs in calculating Rd. Assume y1,y2,…,yσ are all d-MPs, and let B1=x|x≥y1,B2=x|x≥y2,…,Bσ=x|x≥yσ, where x=x1,x2,…,xm,yi=y1i,y2i,…,ymi, and x≥yi means that xj≥yji for j=1,2,…,m; then, Rd can be calculated via the Inclusion-Exclusion method as follows:(1)Rd=PrB1∪B2∪⋯∪Bσ=∑i=1σPrBi−∑j=2σ∑i=1j−1PrBi∩Bj+⋯+−1σ−1PrB1∩B2∩⋯∩Bσ,where(2)PrBi=Prx|x≥yi=∏k=1mPrxk≥yki,PrBi∩Bj=Prx|x≥maxyi,yj=∏k=1mPrxk≥maxyki,ykj,…,PrB1∩B2∩⋯∩Bσ=Prx|x≥maxy1,y2,…,yσ=∏k=1mPrxk≥maxyk1,yk2,…,ykσ.In addition, it should be pointed out that when the number ofd-MPs is huge, the Sum of Disjoint Products method [18–20] or the State Space Decomposition method [21] is applicable to the calculation of Rd. Readers are encouraged to refer to [18–21] for the details of the two methods.


### 2.3. The Fundamental Results for Solvingd-MPs

A state vectorx is a d-MP if and only if (1) Mx=d and (2) Mx−0ei<d for each xi>0, where 0ei=0,…,0,1,0,…,0, i.e., capacity is 1 for ei and 0 for other edges, that is, two conditions must be fulfilled for a d-MP x. The first condition suggests that the network capacity under x is equal to d, and the second reveals that capacity degradation of any edge with nonzero capacity would lead to a smaller network capacity (below d). The above definition implicitly demonstrates that a d-MP is also the minimal state vector satisfying the demand level d.The well-known model proposed by Lin et al. [22] is one of the two fundamental models with respect to d-MPs. Suppose that there are totally p MPs, P1,P2,…,Pp, from the source node s to the sink node t in the network, and the flow travelling through Pj1≤j≤p is denoted by fj1≤j≤p. A flow vector f=f1,f2,…,fp consists of flows travelling through all MPs. The following model by Lin et al. [22] is the foundation of most of the existing algorithms.Lemma 1.
A state vectorx=x1,x2,…,xm is a d-MP candidate when its corresponding flow vector f=f1,f2,…,fp satisfies the following conditions:(3)f1+f2+⋯+fp=d,(4)0≤fj≤Uj,for1≤j≤p,(5)0≤∑ei∈Pjfj≤Wi,for1≤i≤m,(6)xi=∑ei∈Pjfj,for1≤i≤m,where Ui=minWi|ei∈Pj is the maximal capacity of Pj1≤j≤p. Since each unit of flow sent from source node s to sink node t should travel through one of the MPs, the summation of flows travelling through all MPs must be equal to d, which is reflected by condition (3). Condition (4) points out that the flow travelling through Pj should not exceed the maximal capacity of Pj1≤j≤p, and condition (5) indicates that the flow through ei should not be above the largest capacity of ei1≤i≤m. Equation (6) pinpoints the relationship between the current state of ei and the flow through ei1≤i≤m. Generally, the algorithms [22, 26–30] grounded on Lemma 1 consist of three steps:Step 1: solve alld-MP candidatesStep 2: verifyd-MP candidates to obtain real d-MPsStep 3: remove duplicated-MPs.Eachd-MP is also a d-MP candidate, and most of the existing methods need to search for all d-MP candidates prior to determining all d-MPs (Step 1). The feasible solutions derived from Lemma 1 are d-MP candidates. A d-MP candidate is not necessarily a d-MP; then, a verification step is required (Step 2). The methods for verifying d-MP candidates include the direct verification method [30], the comparison method [22, 26, 28], and the cycle-checking method [27]. The direct verification method is mainly based on the definition of d-MPs, that is, every d-MP candidate x derived from Lemma 1 is verified to determine whether it satisfies Mx−0ei<d for each xi>0. If the answer is “yes,” x is a d-MP; otherwise, x is not a d-MP. The rationale behind the comparison method is that, for a d-MP candidate x, if there exists no d-MP candidate y such that x>yx>y means xi≥yi for i=1,2,…,m and xj≥yj for at least one j1≤j≤m, then x is a d-MP. A major drawback for the comparison method is the high-computational complexity. The cycle-checking method is to check whether the network under x has a cycle. In contrast to the direct verification method and the comparison method, the cycle-checking method holds the efficiency advantage, but it is more applicable to directed networks. The set of d-MPs derived from Step 2 may contain duplicate d-MPs which significantly contribute to the computational burden of reliability evaluation but have no effect on the final reliability value, and then there is need to remove duplicate d-MPs (STEP 3).


## 2.1. Multistate Network

Consider a multistate networkGV,E,W with the unique source node s and the unique sink node t, where V=s,1,2,…,n,t is the set of nodes, E=e1,e2,…,em is the set of edges, and W=W1,W2,…,Wm is the largest state vector with Wi being the largest capacity of ei for 1≤i≤m. A network state vector x=x1,x2,…,xm indicates the current capacity of each edge in the network, where the state of ei is defined by xi taking integer values from 0 to Wi. The max-flow of the network under x (or the network capacity under x) is denoted by Mx, and Mx is always called the structure function of a multistate network [25, 31, 35]. By D, the max-flow of the network under the largest state vector W is denoted, i.e., D=MW. Then, Mx≤D holds for any state vector x.The multistate network discussed herein satisfies the following assumptions [28, 30]. (1) Each node is perfectly reliable, which means no capacity constraint is imposed on nodes. (2) The state/capacity of each edge ei1≤i≤m is a nonnegative integer-valued random variable which takes values from 0 to Wi according to a given distribution. (3) The states/capacities of different edges are statistically independent. (4) All flows in the network obey the conservation law, i.e., total flows into and from a node (not source and sink nodes) are all equal.


## 2.2. CalculatingRd in Terms of D-MPs

As mentioned before, once alld-MPs are found, the well-known Inclusion-Exclusion method [14], the Sum of Disjoint Products method [18–20], or the State Space Decomposition method [21] are available to calculate Rd. While the Inclusion-Exclusion method is not as efficient as the Sum of Disjoint Products method [18–20] or the State Space Decomposition method [21], it is simple and easy to understand. Therefore, we briefly introduce how it performs in calculating Rd. Assume y1,y2,…,yσ are all d-MPs, and let B1=x|x≥y1,B2=x|x≥y2,…,Bσ=x|x≥yσ, where x=x1,x2,…,xm,yi=y1i,y2i,…,ymi, and x≥yi means that xj≥yji for j=1,2,…,m; then, Rd can be calculated via the Inclusion-Exclusion method as follows:(1)Rd=PrB1∪B2∪⋯∪Bσ=∑i=1σPrBi−∑j=2σ∑i=1j−1PrBi∩Bj+⋯+−1σ−1PrB1∩B2∩⋯∩Bσ,where(2)PrBi=Prx|x≥yi=∏k=1mPrxk≥yki,PrBi∩Bj=Prx|x≥maxyi,yj=∏k=1mPrxk≥maxyki,ykj,…,PrB1∩B2∩⋯∩Bσ=Prx|x≥maxy1,y2,…,yσ=∏k=1mPrxk≥maxyk1,yk2,…,ykσ.In addition, it should be pointed out that when the number ofd-MPs is huge, the Sum of Disjoint Products method [18–20] or the State Space Decomposition method [21] is applicable to the calculation of Rd. Readers are encouraged to refer to [18–21] for the details of the two methods.


## 2.3. The Fundamental Results for Solvingd-MPs

A state vectorx is a d-MP if and only if (1) Mx=d and (2) Mx−0ei<d for each xi>0, where 0ei=0,…,0,1,0,…,0, i.e., capacity is 1 for ei and 0 for other edges, that is, two conditions must be fulfilled for a d-MP x. The first condition suggests that the network capacity under x is equal to d, and the second reveals that capacity degradation of any edge with nonzero capacity would lead to a smaller network capacity (below d). The above definition implicitly demonstrates that a d-MP is also the minimal state vector satisfying the demand level d.The well-known model proposed by Lin et al. [22] is one of the two fundamental models with respect to d-MPs. Suppose that there are totally p MPs, P1,P2,…,Pp, from the source node s to the sink node t in the network, and the flow travelling through Pj1≤j≤p is denoted by fj1≤j≤p. A flow vector f=f1,f2,…,fp consists of flows travelling through all MPs. The following model by Lin et al. [22] is the foundation of most of the existing algorithms.Lemma 1.
A state vectorx=x1,x2,…,xm is a d-MP candidate when its corresponding flow vector f=f1,f2,…,fp satisfies the following conditions:(3)f1+f2+⋯+fp=d,(4)0≤fj≤Uj,for1≤j≤p,(5)0≤∑ei∈Pjfj≤Wi,for1≤i≤m,(6)xi=∑ei∈Pjfj,for1≤i≤m,where Ui=minWi|ei∈Pj is the maximal capacity of Pj1≤j≤p. Since each unit of flow sent from source node s to sink node t should travel through one of the MPs, the summation of flows travelling through all MPs must be equal to d, which is reflected by condition (3). Condition (4) points out that the flow travelling through Pj should not exceed the maximal capacity of Pj1≤j≤p, and condition (5) indicates that the flow through ei should not be above the largest capacity of ei1≤i≤m. Equation (6) pinpoints the relationship between the current state of ei and the flow through ei1≤i≤m. Generally, the algorithms [22, 26–30] grounded on Lemma 1 consist of three steps:Step 1: solve alld-MP candidatesStep 2: verifyd-MP candidates to obtain real d-MPsStep 3: remove duplicated-MPs.Eachd-MP is also a d-MP candidate, and most of the existing methods need to search for all d-MP candidates prior to determining all d-MPs (Step 1). The feasible solutions derived from Lemma 1 are d-MP candidates. A d-MP candidate is not necessarily a d-MP; then, a verification step is required (Step 2). The methods for verifying d-MP candidates include the direct verification method [30], the comparison method [22, 26, 28], and the cycle-checking method [27]. The direct verification method is mainly based on the definition of d-MPs, that is, every d-MP candidate x derived from Lemma 1 is verified to determine whether it satisfies Mx−0ei<d for each xi>0. If the answer is “yes,” x is a d-MP; otherwise, x is not a d-MP. The rationale behind the comparison method is that, for a d-MP candidate x, if there exists no d-MP candidate y such that x>yx>y means xi≥yi for i=1,2,…,m and xj≥yj for at least one j1≤j≤m, then x is a d-MP. A major drawback for the comparison method is the high-computational complexity. The cycle-checking method is to check whether the network under x has a cycle. In contrast to the direct verification method and the comparison method, the cycle-checking method holds the efficiency advantage, but it is more applicable to directed networks. The set of d-MPs derived from Step 2 may contain duplicate d-MPs which significantly contribute to the computational burden of reliability evaluation but have no effect on the final reliability value, and then there is need to remove duplicate d-MPs (STEP 3).


## 3. The Proposed Algorithm

### 3.1. An Improved Model

A flow vectorf=f1,f2,…,fp satisfying conditions (3)–(5) is said to be a feasible flow vector. It is obvious that solving all of the feasible flow vectors is the first step and also the major obstacle for finding all d-MP candidates. The burden of solving feasible flow vectors is greatly dependent on the capacity ranges determined by conditions (4) and (5); thus, the solution efficiency would be improved if the capacity ranges in conditions (4) and (5) can be shrunk. As can be seen below, the lower bounds in condition (5) have the potential to be raised and the upper bounds in conditions (4) and (5) have the potential to be dropped.Now, we define a special state vectorW0i=W1,W2,…,Wi−1,0,Wi+1,…,Wm in which capacity level is 0 for ei and capacity level is the largest capacity for other edges; then, a crucial necessary condition for a state vector to be a d-MP can be attained.Theorem 1.
For a state vectorx=x1,x2,…,xm, if it is a d-MP, then xi≥Li for 1≤i≤m, where Li=maxd−MW0i,0.Proof.
By definition,Li≥0 holds. If Li=0, it is easy to have xi≥Li.
IfLi≥0, it implies Li=d−MW0i>0. Given that MW≥d holds, if d−MW0i>0, i.e., MW0i<d, it means that at least d−MW0i units of flow must travel through ei in order for d units of flow to be transmitted from s to t. If x is a d-MP, then Mx=d follows from the definition, i.e., d units of flow can be transmitted from s to t under x. As a result, it is deduced that xi≥d−MW0i=Li, which completes the proof.
In fact, Theorem1 reveals that Li1≤i≤m is an improved lower capacity bound of ei in d-MPs, and thus can be employed in condition (5) to shorten the capacity range. By the renowned max-flow algorithm, computing MW0i requires O(mnlog n) time [36]; then, the time complexity of determining all Li for 1≤i≤m is O(m2nlog n).Corollary 1.
The time complexity of finding allLi for 1≤i≤m is O(m2nlog n).Note thatf1+f2+⋯+fp=d in condition (3) means fj≤d for 1≤i≤m. Also, it is clear that ∑ei∈Pjfj≤f1+f2+⋯+fp=d holds. Hence, the upper bounds in conditions (4) and (5) can be replaced by minUj,d and minWi,d, respectively, that is, the following improved model can be constructed to solve all d-MP candidates.Theorem 2.
A state vectorx=x1,x2,…,xm is a d-MP candidate when its corresponding flow vector f=f1,f2,…,fn satisfies the following conditions:(7)f1+f2+⋯+fp=d,(8)0≤fj≤minUj,d,for1≤j≤p,(9)Li≤∑ei∈Pjfj≤minWi,d,for1≤i≤m,(10)xi=∑ei∈Pjfj,for1≤i≤m.Proof.
Directly from Theorem1 and Lemma 1.
It can be easily understandable that Theorem2 is an improvement to Lemma 1 due to the stronger capacity constraints (8) and (9). Here, we adopt an example to illustrate the advantage of Theorem 2 in comparison with Lemma 1. The network in Figure 1 is a simple network with two MPs: P1=e1,e2 and P2=e3, and the largest state vector is W=3,2,2. Given the demand level d=3, a 3-MP candidate x=x1,x2,x3, by Lemma 1, should satisfy the following conditions:(11)f1+f2=3,(12)0≤f1≤2,(13)0≤f2≤2,(14)0≤x1=f1≤3,(15)0≤x2=f1≤2,(16)0≤x3=f2≤2,that is,(17)f1+f2=3,(18)0≤f1≤2,(19)0≤f2≤2,(20)x1=f1,(21)x2=f1,(22)x3=f2.
Then, a total number of 9 flow vectors determined by conditions (18) and (19) need to be checked to solve 3-MP candidates in the worst case. When d=3, L1=max0,d−MW01=max0,3−2=1; similarly, L2=1;L3=1;minUj,d=2 for j=1,2;minW1,d=3andminW2,d=minW3,d=2. Thus, a 3-MP candidate x=x1,x2,x3, by Theorem 2, should satisfy the following conditions:(23)f1+f2=3,0≤f1≤2,0≤f2≤2,1≤x1=f1≤3,1≤x2=f1≤2,1≤x3=f2≤2,that is,(24)f1+f2=3,(25)1≤f1≤2,(26)1≤f2≤2,(27)x1=f1,(28)x2=f1,(29)x3=f2.
As a result, a total number of 4 flow vectors determined by conditions (25) and (26) need to be checked to solve 3-MP candidates in the worst case. By comparison, it can be seen that Theorem 2 holds an advantage over Lemma 1 owing to a smaller number of flow vectors to be checked.Figure 1
A simple network.


### 3.2. Removing Duplicated-MPs

The set ofd-MPs derived from Lemma 1 or Theorem 2 may contain duplicate d-MPs in the sense that one d-MP has the potential to be generated multiple times. Removing duplicate d-MPs is the most time-consuming step of the d-MP problem [22, 26–30]. The traditional method for removing duplicate d-MPs is the component-wise comparison method. Although the component-wise comparison method is simple and easy to understand, it has the deficiency of poor computational efficiency. In this section, an efficient technique will be developed to remove duplicate d-MPs and its computational efficiency is higher than the component-wise comparison method. Given a state vector x, its associated value Φ(x) is defined as follows:(30)Φx=log∑i=1mxiπi−1.Then, the following theorem indicates that there exists a one-to-one relationship between the state vectorx and its associated value Φ(x).Theorem 3.
For any two state vectorsx and y, Φx=Φy if and only if x=y.Proof.
(1)
Ifx=y, then Φx=Φy is directly from the definition of associated value.(2)
By definition,Φx=log∑i=1mxiπi−1 and Φy=log∑i=1myiπi−1. If Φx=Φy, then one can have log∑i=1mxiπi−1=log∑i=1myiπi−1, i.e., ∑i=1mxiπi−1=∑i=1myiπi−1, that is, ∑i=1mxi−yiπi−1=0 holds. Notice that ∑i=1mxi−yiπi−1=0 is a polynomial equation with integer coefficient, and π is a transcendental number; it follows that ∑i=1mxi−yiπi−1=0 if and only if all of its coefficients are equal to 0. Thus, xi−yi=0 for all i=1,2,…,m when ∑i=1mxi−yiπi−1=0 holds, which means x=y.
The aim of introducing the concept of the associated value is to transfer each state vector into a unique number. Based on the relationship between a state vector and its associated value, the task of removing duplicated-MPs can be accomplished by sorting all of the associated values. For example, consider the network in Figure 1, and it is trivial to obtain that x=1,1,2 and y=2,2,1 are all the 3-MPs. By equation (30), Φx=log1×π0+1×π1+2×π2=3.173075 and Φy=log2×π0+2×π1+1×π2=2.898824. Because Φx=3.173075≠Φy=2.898824, it is directly concluded that x=1,1,2 and y=2,2,1 are not duplicates each other.
For a state vectorx, it takes Om time to calculate its associated value Φx. Suppose that σ is the total number of d-MP candidates; then, it requires Omσ time to calculate all of the associated values and takes Oσlogσ time to removing duplicates by using the quick sort or merge sort method. Therefore, the time complexity of removing duplicate d-MPs is Omσ+Oσlogσ=Oσlogσ. Note that the time complexity of the traditional comparison method is Omσ2. Because Oσlogσ≪Omσ2, the method based on Theorem 3 is more efficient in removing duplicates. Therefore, the developed technique is a favorable alternative to remove duplicate d-MPs.


### 3.3. An Algorithm for Findingd-MPs

Using the obtained results, we suggest an algorithm to solve alld-MPs below. Given that all MPs are known in advance, all d-MPs without duplicates can be obtained using the following steps.Input: A multistate network GV,E,W with demand level d.Output: All d-MPs without duplicates.Step 0. Calculate minUj,d for 1≤j≤p, minWi,d and Li=max0,d−MW0i for 1≤i≤m, and let Ω=∅.Step 1. Use the fast enumeration algorithm to solve all of the feasible solutions (i.e., feasible flow vectors) to conditions (7)–(9), and transform each feasible solution into its corresponding d-MP candidate by equation (10). Suppose x1,x2,…,xσ are all the obtained d-MP candidates.Step 2. For each d-MP candidate xj=x1j,x2j,…,xmj1≤j≤σ, if Mxij−0ei<d for all xij>0, then calculate Φxj by equation (30), and let Ω=Ω∪Φxj.Step 3. Use the quick sort or merge sort method to remove all duplicate elements in Ω, and the remaining elements correspond to all of the d-MPs without duplicates.Step 0 is a preprocessing step for calculating lower and upper capacity bounds in conditions (8) and (9). In Step 1, all d-MP candidates are solved by using the enumeration method. In particular, we notice that the fast enumeration method reported by Chen [37] has been proven to be more efficient than the traditional enumeration method; thus, it is used to solve all of the feasible flow vectors in Step 1. The details regarding the fast enumeration method can be referred to Chen [37] and Chen and Lin [28]. All d-MP candidates are verified in Step 2, and the associated value Φxj corresponding to each d-MP xj is calculated. Step 3 is to remove duplicate d-MPs.The computational complexity of every step is analyzed as follows. Step 0 takesO(mp) time and O(m) time to compute all minUj,d1≤j≤p and all minWj,d1≤i≤m, respectively. By Corollary 1, finding all Li=max0,d−MW0i1≤i≤m requires Om2nlogn time. Thus, the computational complexity of Step 0 is Omp+Om+Om2nlogn=Omp. As analyzed in Section 3.1, it takes O∏i=1πqk time to generate all feasible flow vectors, where π is the number of groups of alternative orders arranged by the fast enumeration method and qk is the total number of enumerations in the ith group. It requires Omσp to transform all feasible flow vectors into d-MP candidates, where σ is the number of all feasible flow vectors, i.e., the number of d-MP candidates. As a result, the computational complexity of Step 1 is O∏i=1πqk+Omσp. Checking all d-MP candidates requires Om2nlogn time, and it takes Omσ time to calculate all associated values in the worst case; then, Step 2 totally takes Om2σnlogn time. Using the quick sort or merge sort method to remove duplicates in Ω requires Oσlogσ time in the worst case, so the computational complexity of Step 3 is Oσlogσ.Given that the method by Chen and Lin [28] is regarded as an efficient algorithm for finding d-MPs, we compare it with the proposed algorithm in terms of computational complexity. In addition, while the method by Lin and Chen [30] is a newly reported method and is also considered to be efficient in solving d-MPs, it does not include the step of removing duplicates. Therefore, it is unfair to compare it with the proposed algorithm from the perspective of computational complexity. However, we will compare both algorithms through numerical examples in Section 5 when the step of removing duplicates is incorporated into the method by Lin and Chen [30].Recall that the method by Chen and Lin [28] is based on Lemma 1 to search for all d-MP candidates. Note that the role of Step 1 for solving all d-MP candidates in the proposed algorithm is identical with that of Steps 1 and 2 in the method by Chen and Lin [28]. The theoretical results in Section 3.2 indicate that the time complexity of finding d-MP candidates based on Theorem 1 is upper bounded by the one based on Lemma 1; therefore, it is easy to conclude that the proposed algorithm holds an advantage over Chen and Lin’s method [28] in solving d-MP candidates.Moreover, the role of Steps 2 and 3 in the proposed algorithm is equivalent to that of Step 3 in the method by Chen and Lin. Step 3 of Chen and Lin’s method utilizes the component-wise comparison method to find outd-MPs and remove duplicate d-MPs at the same time, so its computational complexity is Omσ2. And yet, the computational complexity of Steps 2 and 3 in the proposed algorithm is totally Om2σnlogn+Oσlogσ=Om2σnlogn. Because Om2σnlogn<Omσ2, the computational complexity of the proposed algorithm in finding out d-MPs and removing duplicate d-MPs is lower than that of Chen and Lin’s method [28]. Note that even though one more Step 0 needs to be implemented by the proposed algorithm compared with the method of Chen and Lin [28], it has no impact on the computational complexity of the whole algorithm considering Omp<Om2σnlogn<Omσp. Therefore, the proposed algorithm has a distinct efficiency advantage in solving d-MPs.


## 3.1. An Improved Model

A flow vectorf=f1,f2,…,fp satisfying conditions (3)–(5) is said to be a feasible flow vector. It is obvious that solving all of the feasible flow vectors is the first step and also the major obstacle for finding all d-MP candidates. The burden of solving feasible flow vectors is greatly dependent on the capacity ranges determined by conditions (4) and (5); thus, the solution efficiency would be improved if the capacity ranges in conditions (4) and (5) can be shrunk. As can be seen below, the lower bounds in condition (5) have the potential to be raised and the upper bounds in conditions (4) and (5) have the potential to be dropped.Now, we define a special state vectorW0i=W1,W2,…,Wi−1,0,Wi+1,…,Wm in which capacity level is 0 for ei and capacity level is the largest capacity for other edges; then, a crucial necessary condition for a state vector to be a d-MP can be attained.Theorem 1.
For a state vectorx=x1,x2,…,xm, if it is a d-MP, then xi≥Li for 1≤i≤m, where Li=maxd−MW0i,0.Proof.
By definition,Li≥0 holds. If Li=0, it is easy to have xi≥Li.
IfLi≥0, it implies Li=d−MW0i>0. Given that MW≥d holds, if d−MW0i>0, i.e., MW0i<d, it means that at least d−MW0i units of flow must travel through ei in order for d units of flow to be transmitted from s to t. If x is a d-MP, then Mx=d follows from the definition, i.e., d units of flow can be transmitted from s to t under x. As a result, it is deduced that xi≥d−MW0i=Li, which completes the proof.
In fact, Theorem1 reveals that Li1≤i≤m is an improved lower capacity bound of ei in d-MPs, and thus can be employed in condition (5) to shorten the capacity range. By the renowned max-flow algorithm, computing MW0i requires O(mnlog n) time [36]; then, the time complexity of determining all Li for 1≤i≤m is O(m2nlog n).Corollary 1.
The time complexity of finding allLi for 1≤i≤m is O(m2nlog n).Note thatf1+f2+⋯+fp=d in condition (3) means fj≤d for 1≤i≤m. Also, it is clear that ∑ei∈Pjfj≤f1+f2+⋯+fp=d holds. Hence, the upper bounds in conditions (4) and (5) can be replaced by minUj,d and minWi,d, respectively, that is, the following improved model can be constructed to solve all d-MP candidates.Theorem 2.
A state vectorx=x1,x2,…,xm is a d-MP candidate when its corresponding flow vector f=f1,f2,…,fn satisfies the following conditions:(7)f1+f2+⋯+fp=d,(8)0≤fj≤minUj,d,for1≤j≤p,(9)Li≤∑ei∈Pjfj≤minWi,d,for1≤i≤m,(10)xi=∑ei∈Pjfj,for1≤i≤m.Proof.
Directly from Theorem1 and Lemma 1.
It can be easily understandable that Theorem2 is an improvement to Lemma 1 due to the stronger capacity constraints (8) and (9). Here, we adopt an example to illustrate the advantage of Theorem 2 in comparison with Lemma 1. The network in Figure 1 is a simple network with two MPs: P1=e1,e2 and P2=e3, and the largest state vector is W=3,2,2. Given the demand level d=3, a 3-MP candidate x=x1,x2,x3, by Lemma 1, should satisfy the following conditions:(11)f1+f2=3,(12)0≤f1≤2,(13)0≤f2≤2,(14)0≤x1=f1≤3,(15)0≤x2=f1≤2,(16)0≤x3=f2≤2,that is,(17)f1+f2=3,(18)0≤f1≤2,(19)0≤f2≤2,(20)x1=f1,(21)x2=f1,(22)x3=f2.
Then, a total number of 9 flow vectors determined by conditions (18) and (19) need to be checked to solve 3-MP candidates in the worst case. When d=3, L1=max0,d−MW01=max0,3−2=1; similarly, L2=1;L3=1;minUj,d=2 for j=1,2;minW1,d=3andminW2,d=minW3,d=2. Thus, a 3-MP candidate x=x1,x2,x3, by Theorem 2, should satisfy the following conditions:(23)f1+f2=3,0≤f1≤2,0≤f2≤2,1≤x1=f1≤3,1≤x2=f1≤2,1≤x3=f2≤2,that is,(24)f1+f2=3,(25)1≤f1≤2,(26)1≤f2≤2,(27)x1=f1,(28)x2=f1,(29)x3=f2.
As a result, a total number of 4 flow vectors determined by conditions (25) and (26) need to be checked to solve 3-MP candidates in the worst case. By comparison, it can be seen that Theorem 2 holds an advantage over Lemma 1 owing to a smaller number of flow vectors to be checked.Figure 1
A simple network.


## 3.2. Removing Duplicated-MPs

The set ofd-MPs derived from Lemma 1 or Theorem 2 may contain duplicate d-MPs in the sense that one d-MP has the potential to be generated multiple times. Removing duplicate d-MPs is the most time-consuming step of the d-MP problem [22, 26–30]. The traditional method for removing duplicate d-MPs is the component-wise comparison method. Although the component-wise comparison method is simple and easy to understand, it has the deficiency of poor computational efficiency. In this section, an efficient technique will be developed to remove duplicate d-MPs and its computational efficiency is higher than the component-wise comparison method. Given a state vector x, its associated value Φ(x) is defined as follows:(30)Φx=log∑i=1mxiπi−1.Then, the following theorem indicates that there exists a one-to-one relationship between the state vectorx and its associated value Φ(x).Theorem 3.
For any two state vectorsx and y, Φx=Φy if and only if x=y.Proof.
(1)
Ifx=y, then Φx=Φy is directly from the definition of associated value.(2)
By definition,Φx=log∑i=1mxiπi−1 and Φy=log∑i=1myiπi−1. If Φx=Φy, then one can have log∑i=1mxiπi−1=log∑i=1myiπi−1, i.e., ∑i=1mxiπi−1=∑i=1myiπi−1, that is, ∑i=1mxi−yiπi−1=0 holds. Notice that ∑i=1mxi−yiπi−1=0 is a polynomial equation with integer coefficient, and π is a transcendental number; it follows that ∑i=1mxi−yiπi−1=0 if and only if all of its coefficients are equal to 0. Thus, xi−yi=0 for all i=1,2,…,m when ∑i=1mxi−yiπi−1=0 holds, which means x=y.
The aim of introducing the concept of the associated value is to transfer each state vector into a unique number. Based on the relationship between a state vector and its associated value, the task of removing duplicated-MPs can be accomplished by sorting all of the associated values. For example, consider the network in Figure 1, and it is trivial to obtain that x=1,1,2 and y=2,2,1 are all the 3-MPs. By equation (30), Φx=log1×π0+1×π1+2×π2=3.173075 and Φy=log2×π0+2×π1+1×π2=2.898824. Because Φx=3.173075≠Φy=2.898824, it is directly concluded that x=1,1,2 and y=2,2,1 are not duplicates each other.
For a state vectorx, it takes Om time to calculate its associated value Φx. Suppose that σ is the total number of d-MP candidates; then, it requires Omσ time to calculate all of the associated values and takes Oσlogσ time to removing duplicates by using the quick sort or merge sort method. Therefore, the time complexity of removing duplicate d-MPs is Omσ+Oσlogσ=Oσlogσ. Note that the time complexity of the traditional comparison method is Omσ2. Because Oσlogσ≪Omσ2, the method based on Theorem 3 is more efficient in removing duplicates. Therefore, the developed technique is a favorable alternative to remove duplicate d-MPs.


## 3.3. An Algorithm for Findingd-MPs

Using the obtained results, we suggest an algorithm to solve alld-MPs below. Given that all MPs are known in advance, all d-MPs without duplicates can be obtained using the following steps.Input: A multistate network GV,E,W with demand level d.Output: All d-MPs without duplicates.Step 0. Calculate minUj,d for 1≤j≤p, minWi,d and Li=max0,d−MW0i for 1≤i≤m, and let Ω=∅.Step 1. Use the fast enumeration algorithm to solve all of the feasible solutions (i.e., feasible flow vectors) to conditions (7)–(9), and transform each feasible solution into its corresponding d-MP candidate by equation (10). Suppose x1,x2,…,xσ are all the obtained d-MP candidates.Step 2. For each d-MP candidate xj=x1j,x2j,…,xmj1≤j≤σ, if Mxij−0ei<d for all xij>0, then calculate Φxj by equation (30), and let Ω=Ω∪Φxj.Step 3. Use the quick sort or merge sort method to remove all duplicate elements in Ω, and the remaining elements correspond to all of the d-MPs without duplicates.Step 0 is a preprocessing step for calculating lower and upper capacity bounds in conditions (8) and (9). In Step 1, all d-MP candidates are solved by using the enumeration method. In particular, we notice that the fast enumeration method reported by Chen [37] has been proven to be more efficient than the traditional enumeration method; thus, it is used to solve all of the feasible flow vectors in Step 1. The details regarding the fast enumeration method can be referred to Chen [37] and Chen and Lin [28]. All d-MP candidates are verified in Step 2, and the associated value Φxj corresponding to each d-MP xj is calculated. Step 3 is to remove duplicate d-MPs.The computational complexity of every step is analyzed as follows. Step 0 takesO(mp) time and O(m) time to compute all minUj,d1≤j≤p and all minWj,d1≤i≤m, respectively. By Corollary 1, finding all Li=max0,d−MW0i1≤i≤m requires Om2nlogn time. Thus, the computational complexity of Step 0 is Omp+Om+Om2nlogn=Omp. As analyzed in Section 3.1, it takes O∏i=1πqk time to generate all feasible flow vectors, where π is the number of groups of alternative orders arranged by the fast enumeration method and qk is the total number of enumerations in the ith group. It requires Omσp to transform all feasible flow vectors into d-MP candidates, where σ is the number of all feasible flow vectors, i.e., the number of d-MP candidates. As a result, the computational complexity of Step 1 is O∏i=1πqk+Omσp. Checking all d-MP candidates requires Om2nlogn time, and it takes Omσ time to calculate all associated values in the worst case; then, Step 2 totally takes Om2σnlogn time. Using the quick sort or merge sort method to remove duplicates in Ω requires Oσlogσ time in the worst case, so the computational complexity of Step 3 is Oσlogσ.Given that the method by Chen and Lin [28] is regarded as an efficient algorithm for finding d-MPs, we compare it with the proposed algorithm in terms of computational complexity. In addition, while the method by Lin and Chen [30] is a newly reported method and is also considered to be efficient in solving d-MPs, it does not include the step of removing duplicates. Therefore, it is unfair to compare it with the proposed algorithm from the perspective of computational complexity. However, we will compare both algorithms through numerical examples in Section 5 when the step of removing duplicates is incorporated into the method by Lin and Chen [30].Recall that the method by Chen and Lin [28] is based on Lemma 1 to search for all d-MP candidates. Note that the role of Step 1 for solving all d-MP candidates in the proposed algorithm is identical with that of Steps 1 and 2 in the method by Chen and Lin [28]. The theoretical results in Section 3.2 indicate that the time complexity of finding d-MP candidates based on Theorem 1 is upper bounded by the one based on Lemma 1; therefore, it is easy to conclude that the proposed algorithm holds an advantage over Chen and Lin’s method [28] in solving d-MP candidates.Moreover, the role of Steps 2 and 3 in the proposed algorithm is equivalent to that of Step 3 in the method by Chen and Lin. Step 3 of Chen and Lin’s method utilizes the component-wise comparison method to find outd-MPs and remove duplicate d-MPs at the same time, so its computational complexity is Omσ2. And yet, the computational complexity of Steps 2 and 3 in the proposed algorithm is totally Om2σnlogn+Oσlogσ=Om2σnlogn. Because Om2σnlogn<Omσ2, the computational complexity of the proposed algorithm in finding out d-MPs and removing duplicate d-MPs is lower than that of Chen and Lin’s method [28]. Note that even though one more Step 0 needs to be implemented by the proposed algorithm compared with the method of Chen and Lin [28], it has no impact on the computational complexity of the whole algorithm considering Omp<Om2σnlogn<Omσp. Therefore, the proposed algorithm has a distinct efficiency advantage in solving d-MPs.


## 4. An Illustrative Example

The classical bridge network shown in Figure2 is adopted to demonstrate how the proposed algorithm works. The data of edges are presented in Table 1. The network in Figure 2 has 4 MPs from s to t: P1=e1,e2, P2=e1,e3,e5, P3=e4,e5, and P4=e4,e3,e2. Suppose the demand level is d=3; then, all 3-MPs can be obtained using the following steps.Step 0: minU1,d=min2,3=2, similarly, minU2,d=1,minU3,d=2,minU4,d=1,andminW1,d=min3,3=3, similarly, minW2,d=2,minW3,d=1,minW4,d=2,minW5,d=2,andL1=max0,d−MW0i=max0,1=1, similarly, L2=1,L3=0,L4=0,andL5=1.Step 1: use the fast enumeration method to solve all of the feasible solutions f=f1,f2,f3,f4 to the following conditions:(31)f1+f2+f3+f4=3,0≤f1≤2,0≤f2≤1,0≤f3≤2,0≤f4≤1,1≤f1+f2≤3,1≤f1+f4≤2,0≤f2+f4≤1,0≤f3+f4≤2,1≤f2+f3≤2.The derived feasible solutions aref1=1,0,2,0, f2=1,0,1,1, f3=1,1,1,0, f4=2,0,1,0, and f5=2,1,0,0. By equation (11), Transform fj1≤j≤5 into its corresponding d-MP candidate: f1⟶x1=1,1,0,2,2, f2⟶x2=1,2,1,2,1, f3⟶x3=2,1,1,1,2, f4⟶x4=2,2,0,1,1, and f5⟶x5=3,2,1,0,1.Step 2: for x1=1,1,0,2,2,Mx1−0e1=2<3,Mx1−0e2=2<3,Mx1−0e3=2<3, Mx1−0e4=2<3,andMx1−0e5=2<3, then Φx1=5.564414, and Ω=Ω∪5.564414. Similarly, for x2=1,2,1,2,1,Mx2−0ei=2<3 for all xi2>0, then Φx2=5.173743 and Ω=Ω∪5.173743; for x3=2,1,1,1,2,Mx3−0ei=2<3 for all xi3>0, then Φx3=5.484115 and Ω=Ω∪5.484115; for x4=2,2,0,1,1,Mx4−0ei=2<3 for all xi4>0, then Φx4=4.917778 and Ω=Ω∪4.917778; for x5=3,2,1,0,1,Mx5−0ei=2<3, for all xi5>0, then Φx5=4.758422 and Ω=Ω∪4.758422.Step 3: there is no duplicate in Ω, then the elements in Ω correspond to all of the 3-MPs without duplicates: x1=1,1,0,2,2,x2=1,2,1,2,1,x3=2,1,1,1,2,x4=2,2,0,1,1,andx5=3,2,1,0,1.Figure 2
The bridge network.Table 1
The data of edges for the bridge network in Figure2.
EdgeStatesState probabilitiese101230.0020.0130.1250.860e2012—0.0050.0100.985—e301——0.1100.890——e4012—0.0030.0120.985—e5012—0.0060.0150.979—The solution results are summarized in Table2, indicating there are totally five 3-MPs generated. Using the Inclusion-Exclusion method shown in Section 2.2, the final network reliability for this example is calculated as R3=0.986002.Table 2
Solution results of the proposed algorithm.
jFeasible solutionfjThe corresponding 3-MP candidateA 3-MP?ΦxjA duplicate 3-MP1f1 = (1, 0, 2, 0)x1 = (1, 1, 0, 2, 2)Yes5.564414No2f2 = (1, 0, 1, 1)x2 = (1, 2, 1, 2, 1)Yes5.173743No3f3 = (1, 1, 1, 0)x3 = (2, 1, 1, 1, 2)Yes5.484115No4f4 = (2, 0, 1, 0)x4 = (2, 2, 0, 1, 1)Yes4.917778No5f5 = (2, 1, 0, 0)x5 = (3, 2, 1, 0, 1)Yes4.758422No


## 5. Efficiency Investigation by Numerical Examples

In this section, we investigate the efficiency of the proposed algorithm. As mentioned inSection 2.2, Lemma 1 proposed by Lin et al. [22] is one of the most important models with respect to d-MPs, and is also the foundation of most of the existing methods [26–30]. As an improvement to Lemma 1, Theorem 2 is the foundation of the proposed algorithm. So, we compare the proposed algorithm with the ones based on Lemma 1. Also, given that the methods by Chen and Lin [28] and Lin and Chen [30] are newly developed algorithms and also considered to be efficient in solving d-MPs, we implement the numerical experiments to compare the proposed algorithm with them. Meanwhile, since Lin and Chen [30] did not consider the step of removing duplicate d-MPs, we incorporate the proposed technique into the method of Lin and Chen for a fair comparison. All of the three algorithms require MPs as prior knowledge. Actually, MPs can be easily determined using the existing methods, such as the methods by Chen and Lin [38] and Bai et al. [39], so it is unnecessary to include this procedure when we compare the efficiency. All algorithms are coded in MATLAB 2009 and are implemented on a PC with Intel(R) Core (TM) i5-3210M 2.50 GHz CPU and 8 GB of RAM.


### 5.1. Example 1

First, we consider the network shown in Figure3. The largest state vector is set to W=7,5,6,4,4,5,4,6,7, and the max-flow of the network under the largest state vector W is D=12. To draw a full picture of the efficiency of different algorithms, all of the demand levels from 1 to 12 are examined, i.e., 1-MPs, 2-MPs, …, and 12-MPs are solved. In numerical experiments, we are interested in the required computational time for finding all d-MPs. In addition, we use ratios, defined as the CPU time consumed by the reported methods by Chen and Lin [28] and Lin and Chen [30] divided by the CPU time consumed by the proposed algorithm, respectively, to exhibit the relative efficiency for the sake of intuitively capturing the performances of different algorithms. The computational results are summarized in Table 3, including the number of d-MPs, the CPU times in seconds consumed by different algorithms and their ratios. By Table 3, we make the following observations.Figure 3
A test network for example 1.Table 3
Results of different algorithms for solving the network in Figure3.
d# ofd-MPsComputational time (s)RatioTCLTLCTTCL/TTLC/T1130.3710.3720.0655.7085.7232590.4570.5160.0964.7605.37531751.6821.3340.2546.6225.252441013.9034.6390.95114.6194.878571988.87114.0612.91630.4774.8226916339.61434.4747.36746.0994.6807894774.96967.59515.70849.3364.3038632845.70391.78222.16238.1604.1419389460.93882.05818.49624.9214.43710200124.69747.2189.45313.1914.995117918.32419.6653.7924.8325.18612191.2414.6610.9851.2604.732Note:TCL and TLC are the computational times of Chen and Lin’s algorithm [28] and Lin and Chen’s algorithm [30], respectively, and T is the computational time of the proposed algorithm.Compared with the method by Chen and Lin [28], the proposed algorithm spends a smaller amount of CPU time in solving d-MPs for every demand level d. Thus, the proposed algorithm is more efficient than Chen and Lin’s method. Notice that the ratio TCL/T, representing the advantage of proposed algorithm over the method by Chen and Lin for finding d-MPs, is greater than 4 for every demand level d except d=12, indicating that the proposed algorithm holds a distinct advantage in most cases. Furthermore, when the demand level d is intermediate d=5,6,7,8, the ratio TCL/T is above 30, which exhibits the considerable advantage of the proposed algorithm.The CPU time consumed by the proposed algorithm is less than that consumed by Lin and Chen’s method [30] in terms of solving d-MPs for every demand level d, showing the proposed algorithm outperforms the method by Lin and Chen as well. It is noted that the ratio TLC/T, representing the advantage of proposed algorithm over Lin and Chen’s method for finding d-MPs, is between 4 and 6 for every demand level d, thereby the proposed algorithm has a distinct advantage in all cases.


### 5.2. Example 2

In this section, we consider a relatively larger network in Figure4 and consider two scenarios, where the largest states of all edges are equal to 4 and 5, respectively. For each scenario, five demand levels, i.e., d=D/2−2,D/2−1,D/2,D/2+1,andD/2+2, where D is the max-flow of the network under the largest state vector, are examined. We still use ratios, defined as the CPU time consumed by the reported methods by Chen and Lin [28] and Lin and Chen [30] divided by the CPU time consumed by the proposed algorithm, respectively, to exhibit the relative efficiency. The experimental results are summarized in Table 4, including the number of d-MPs, the CPU times in seconds consumed by different algorithms and their ratios.Figure 4
A test network for example 2.Table 4
Results of different algorithms for solving the network in Figure4.
Scenariod# ofd-MPsComputational time (s)RatioTCLTLCTTCL/TTLC/TWi = 4D = 821126.1316.8691.4354.2724.787339215.68514.92611.1831.4031.33541057215.08467.20861.7633.4821.08859041104.979258.804172.5446.4041.50066341983.916545.056267.2657.4232.039Wi = 5D = 10339264.24662.90211.2615.7055.58641057264.896115.44661.7914.2871.868524084875.036455.861278.65217.4951.63662182NAa2320.584815.486—2.84671736NAa8070.5021538.119—5.247aNot completed within 20000 CPU seconds.It can be seen from Table4 that all ratios (TCL/T and TLC/T) that denote the advantage of proposed algorithm over the methods by Chen and Lin [28] and Lin and Chen [30] for finding d-MPs are greater than 1 for every demand level dd=D/2−2,D/2−1,D/2,D/2+1,D/2+2 in both scenarios; then, the proposed algorithm is more efficient than both methods. It is noteworthy that the method by Chen and Lin cannot find all 6-MPs (7-MPs) within 20000 CPU seconds, while the proposed algorithm requires 815.486 CPU seconds (1538.119 CPU seconds) that is far less than 20000 CPU seconds to generate all 6-MPs (7-MPs). In addition, the efficiency difference between the proposed algorithm and the method by Chen and Lin [28] is more prominent than that between the proposed algorithm and the method by Lin and Chen [30].As an NP-hard problem, searching ford-MPs is a challenging task. The comparative results derived from Table 4 reveals that the proposed algorithm does contribute to the efficiency improvement of solving d-MPs without duplicates. Thus, the suggested algorithm can be used to accelerate the computation of network reliability. Network reliability is a key performance parameter in network design and improvement [9]. By employing the proposed algorithm, the network supervisor can efficiently capture the quality of service of real-world systems to make managerial decisions, especially to figure out the bottleneck of network improvement in many enterprises or organizations.


## 5.1. Example 1

First, we consider the network shown in Figure3. The largest state vector is set to W=7,5,6,4,4,5,4,6,7, and the max-flow of the network under the largest state vector W is D=12. To draw a full picture of the efficiency of different algorithms, all of the demand levels from 1 to 12 are examined, i.e., 1-MPs, 2-MPs, …, and 12-MPs are solved. In numerical experiments, we are interested in the required computational time for finding all d-MPs. In addition, we use ratios, defined as the CPU time consumed by the reported methods by Chen and Lin [28] and Lin and Chen [30] divided by the CPU time consumed by the proposed algorithm, respectively, to exhibit the relative efficiency for the sake of intuitively capturing the performances of different algorithms. The computational results are summarized in Table 3, including the number of d-MPs, the CPU times in seconds consumed by different algorithms and their ratios. By Table 3, we make the following observations.Figure 3
A test network for example 1.Table 3
Results of different algorithms for solving the network in Figure3.
d# ofd-MPsComputational time (s)RatioTCLTLCTTCL/TTLC/T1130.3710.3720.0655.7085.7232590.4570.5160.0964.7605.37531751.6821.3340.2546.6225.252441013.9034.6390.95114.6194.878571988.87114.0612.91630.4774.8226916339.61434.4747.36746.0994.6807894774.96967.59515.70849.3364.3038632845.70391.78222.16238.1604.1419389460.93882.05818.49624.9214.43710200124.69747.2189.45313.1914.995117918.32419.6653.7924.8325.18612191.2414.6610.9851.2604.732Note:TCL and TLC are the computational times of Chen and Lin’s algorithm [28] and Lin and Chen’s algorithm [30], respectively, and T is the computational time of the proposed algorithm.Compared with the method by Chen and Lin [28], the proposed algorithm spends a smaller amount of CPU time in solving d-MPs for every demand level d. Thus, the proposed algorithm is more efficient than Chen and Lin’s method. Notice that the ratio TCL/T, representing the advantage of proposed algorithm over the method by Chen and Lin for finding d-MPs, is greater than 4 for every demand level d except d=12, indicating that the proposed algorithm holds a distinct advantage in most cases. Furthermore, when the demand level d is intermediate d=5,6,7,8, the ratio TCL/T is above 30, which exhibits the considerable advantage of the proposed algorithm.The CPU time consumed by the proposed algorithm is less than that consumed by Lin and Chen’s method [30] in terms of solving d-MPs for every demand level d, showing the proposed algorithm outperforms the method by Lin and Chen as well. It is noted that the ratio TLC/T, representing the advantage of proposed algorithm over Lin and Chen’s method for finding d-MPs, is between 4 and 6 for every demand level d, thereby the proposed algorithm has a distinct advantage in all cases.


## 5.2. Example 2

In this section, we consider a relatively larger network in Figure4 and consider two scenarios, where the largest states of all edges are equal to 4 and 5, respectively. For each scenario, five demand levels, i.e., d=D/2−2,D/2−1,D/2,D/2+1,andD/2+2, where D is the max-flow of the network under the largest state vector, are examined. We still use ratios, defined as the CPU time consumed by the reported methods by Chen and Lin [28] and Lin and Chen [30] divided by the CPU time consumed by the proposed algorithm, respectively, to exhibit the relative efficiency. The experimental results are summarized in Table 4, including the number of d-MPs, the CPU times in seconds consumed by different algorithms and their ratios.Figure 4
A test network for example 2.Table 4
Results of different algorithms for solving the network in Figure4.
Scenariod# ofd-MPsComputational time (s)RatioTCLTLCTTCL/TTLC/TWi = 4D = 821126.1316.8691.4354.2724.787339215.68514.92611.1831.4031.33541057215.08467.20861.7633.4821.08859041104.979258.804172.5446.4041.50066341983.916545.056267.2657.4232.039Wi = 5D = 10339264.24662.90211.2615.7055.58641057264.896115.44661.7914.2871.868524084875.036455.861278.65217.4951.63662182NAa2320.584815.486—2.84671736NAa8070.5021538.119—5.247aNot completed within 20000 CPU seconds.It can be seen from Table4 that all ratios (TCL/T and TLC/T) that denote the advantage of proposed algorithm over the methods by Chen and Lin [28] and Lin and Chen [30] for finding d-MPs are greater than 1 for every demand level dd=D/2−2,D/2−1,D/2,D/2+1,D/2+2 in both scenarios; then, the proposed algorithm is more efficient than both methods. It is noteworthy that the method by Chen and Lin cannot find all 6-MPs (7-MPs) within 20000 CPU seconds, while the proposed algorithm requires 815.486 CPU seconds (1538.119 CPU seconds) that is far less than 20000 CPU seconds to generate all 6-MPs (7-MPs). In addition, the efficiency difference between the proposed algorithm and the method by Chen and Lin [28] is more prominent than that between the proposed algorithm and the method by Lin and Chen [30].As an NP-hard problem, searching ford-MPs is a challenging task. The comparative results derived from Table 4 reveals that the proposed algorithm does contribute to the efficiency improvement of solving d-MPs without duplicates. Thus, the suggested algorithm can be used to accelerate the computation of network reliability. Network reliability is a key performance parameter in network design and improvement [9]. By employing the proposed algorithm, the network supervisor can efficiently capture the quality of service of real-world systems to make managerial decisions, especially to figure out the bottleneck of network improvement in many enterprises or organizations.


## 6. Concluding Remarks

Reliability evaluation is an effective manner to capture the operational state of practical networks. One important type of method for multistate network reliability evaluation is usingd-MPs. This paper presents a new efficient method to search for d-MPs for the multistate network reliability problem. On the one hand, an improved model is constructed to solve d-MPs by redefining capacity constraints of network components and MPs, and the model is an improvement to the well-known fundamental model. On the other hand, a technique superior to the traditional comparison method is proposed to remove duplicate d-MPs. The computational complexity of the proposed algorithm is analyzed, and a simple example is provided to illustrate the proposed algorithm. In addition, through computational experiments, it is found that the proposed algorithm is more efficient in terms of finding all d-MPs.For future research, there is still potential for improving the suggested algorithm. For instance, transmission cost is also an important attribute of real-world networks, such as transportation networks or power transmission networks, and thus, extending the suggested algorithm to network reliability subject to cost constraint is worthy of study. Furthermore, it is interesting to study how to modify the suggested algorithm to be an approximate algorithm for tradeoff between execution time and the obtained set ofd-MPs.



---

*Source: 8060794-2020-10-22.xml*