XU Bei ,FANG Yining ,BAI Guanghan ,ZHANG Yun’an ,and TAO Junyong

1.Laboratory of Science and Technology on Integrated Logistics Support,College of Intelligent Sciences and Technology,National University of Defense Technology,Changsha 410073,China;2.School of General Aviation,Nanchang Hangkong University,Nanchang 330063,China

Abstract:The reliability evaluation of a multistate network is primarily based on d-minimal paths/cuts (d-MPs/d-MCs).However,being a nondeterminism polynomial hard (NP-hard) problem,searching for all d-MPs is a rather challenging task.In existing implicit enumeration algorithms based on minimal paths (MPs),duplicate d-MP candidates may be generated.An extra step is needed to locate and remove these duplicate d-MP candidates,which costs significant computational effort.This paper proposes an efficient method to prevent the generation of duplicate d-MP candidates for implicit enumeration algorithms for d-MPs.First,the mechanism of generating duplicate d-MP candidates in the implicit enumeration algorithms is discussed.Second,a direct and efficient avoiding-duplicates method is proposed.Third,an improved algorithm is developed,followed by complexity analysis and illustrative examples.Based on the computational experiments comparing with two existing algorithms,it is found that the proposed method can significantly improve the efficiency of generating d-MPs for a particular demand level d.

Keywords:reliability,multistate network,d-minimal path (d-MP),duplicate.

1.Introduction

The multistate network which consists of components that have three or more possible states plays a major role in model society,such as oil/gas production and transportation networks [1],computer and communication systems [2,3],power transmission and distribution systems[4],supply chain networks [5],and other complex systems [6-10].Reliability as an important index for evaluating multistate network performance is defined as the probability that the maximal flow from the source node to the sink node is no less than a demandd.

Consider a two-terminal multistate network with one source node and one sink node,it is a nondeterminism polynomial hard (NP-hard) problem to evaluate its reliability [11].In general,these approaches of evaluating reliability can be divided into the direct method and the indirect method.The direct method includes the statespace decomposition method [8,12,13],the Petri-net method [14],and the Monte-Carlo simulation method [15].The indirect method was firstly proposed in [16],which pointed out that the reliability of the multistate network could be indirectly calculated by thed-minimal paths(d-MPs) and thed-minimal cuts (d-MCs).These indirect approaches can be classified into two types: one is based on the prior knowledge of MPs (MCs) [17-23],and the other does not need MPs (MCs) in advance [24-26].In this paper,we focus on the method based on MPs.

With MPs in advance,Lin et al.[17] first introduced the implicit enumeration method to searchd-MPs for a particulard.He proposed the well-known three-constraints method in 1995 by solving a mathematical programming model imposed by the network structure and the flow-conservation law to search ford-MP candidates in a multistate network.Lin [19] improved the efficiency of the three-constraints method by reducing three constraints to two constraints.Yeh [20] developed an algorithm to remove redundantd-MP candidates by detecting cycles.Forghani-Elahabad et al.[27] further improved the verification method [20] to filter out reald-MP.In 2016,Chen et al.[18] introduced fast enumeration (FE)to rearrange the mathematical programming model,which has been proven to significantly improve algorithm efficiency.Meanwhile,Chen et al.[18] indicated there are duplicates ind-MP candidates when the feasible flow vectors are transformed into state vectors.In order to locate and remove duplicated-MP candidates,Chen adopted a recursive comparison by comparing each newly generatedd-MP candidate with all the otherd-MP candidates,which is tedious and time-consuming.In 2020,Xu et al.[28] proposed another technique to convert the vector comparison to a number comparison by transformedd-MP candidates into a unique number.

For the sake of obtaining alld-MPs for all possible demanddin one time,Bai et al.[21] developed an addition-based algorithm based on a breadth-first search to work out it by combining MPs and real (d-1)-MP.Yeh[22] improved Bai’s algorithm and presented a logarithmic prime method to remove duplicated-MPs instead of a recursive comparison method.

Nevertheless,both the techniques proposed by Xu et al.[28] and Yeh [22] still need to generate the duplicates before they are detected and removed.The number ofd-MP candidates is huge and grows exponentially with the increase of the network size,so the methods [22,28]may need significant memory and require additional time and steps to remove duplicates.Bai et al.[29] discussed the mechanism of generating duplicated-MP candidates from the aspect of network structure and proposed a method to prevent these duplicated-MP candidates before they are formed in the addition-based algorithm.However,it is not suitable for the algorithms [18-20,27,28]grounded on the implicit enumeration method [17].

The opportunity and mechanism of duplicated-MP candidates generated in the two kinds of methods are different.In the addition-based method,duplicated-MP candidates are generated in the process of adding MP to(d-1)-MP.However,the duplicates in the implicit enumeration algorithms [17-20,27,28] are generated when the flow state vector is transformed into the system state vector.Thus,there is a need to develop a new method to prevent the duplicated-MP candidates from generating for the implicit enumeration algorithms of searchingd-MPs for a particulard,given MPs.

The purpose of this article is to develop a method to obtaind-MPs for a particular demand leveldwithout duplicates in implicit enumeration algorithms.This paper makes four contributions.(i) We analyze the mechanism of duplicates generation in the well-known implicit enumeration algorithm.(ii) We develop a direct method to prevent the duplicates generation,followed by the proof.(iii) By incorporating the proposed method,an improved algorithm is proposed to searchd-MPs for a particulardwithout duplicates,followed by complexity analysis.(iv) Based on the computational experiments comparing with two existing algorithms,it is found that the proposed method can significantly improve the efficiency of generatingd-MPs for a particular demand level.

The remainder of the work is described as follows: In Section 2,notions and assumptions are provided.In Section 3,the main concepts of existing implicit enumeration algorithms are analyzed.Section 4 analyzes the mechanism of duplicates generation and proposes the avoiding-duplicate method.The proposed algorithm and complexity analysis are described in Section 5.Section 6 investigates the efficiency of the proposed algorithm comparing with two existing algorithms.Finally,Section 7 draws the conclusions of this paper.

2.Notations and assumptions

2.1 Notation

2.2 Assumptions

(i) All nodes are perfect.When both nodes and edges are failure-prone,an approach reported in [30] can be used to transform the network into one with perfect nodes.

(ii) The capacity of each component is a non-negative integer-valued random variable,which takes integer values from 0 to its maximum capacity following the given probability distribution.

(iii) The capacities of different components are statistically independent.

(iv) The network does not contain an isolated node.

3.Preliminary

Assuming givenρ1,ρ2,···,ρm,which are the sets of components fromstotcontained in MP1,MP2,···,MPm,respectively,and the flow traveling through MPj(1 ≤j≤m) is denoted byfj.The following constraints proposed by Lin et al.[17] are the fundamental of existing implicit enumeration algorithms in searching ford-MPs.

(i) The summation of the flow on all the MPs is equal to the demand leveld;which can be described by the following mathematical formula:

(ii) The current flowfjon the MPjis less than or equal to the minimum value of all maximum capacities of components contained in that ρi:

wheresj=min{Mi|ai∈ρi} represents the maximum flow on M Pj.

(iii) The total flow throughaicannot exceed the maximal capacity ofai.Then,Fis feasible if

whereMirepresents the max capacity of the componentai.

Enumerate the feasible flow vector=(f1,f2,···,fm)that satisfied the above three constraints.Then systemstate vectorX=(x1,x2,···,xn) is ad-MP candidate,where

Generally,three steps have been used in the algorithms [17-20,27,28] grounded on the implicit enumeration method.

Step 1Search for alld-MP candidates.

Step 2Verifyd-MP candidates to obtain reald-MPs.

Step 3Remove duplicated-MPs.

For Step 2,Yeh [22] developed an efficient method to filter out reald-MP by detecting cycles based on the following theorem,whose proof can be found in [22] and is omitted here.

Theorem 1[22] Ad-MP candidateX=(x1,x2,···,xm)is ad-MP if and only if

(i) Its capacity level isd.

(ii) There is no directed cycle inX.

To improve the above verifying method,Forghani-Elahabad [27] proved that constraint (i) in Theorem 1 is redundancy.

Theorem 2[27] Ifsatisfies the constraints (1)-(3),andXis transformed fromby use of (4),then the capacity ofXisd.

According to Theorem 2,it is only required to verify if there is a directed cycle in the network under the candidate.

For Step 3,the algorithms [17,18,20,25] adopted a method of pairwise comparison by comparing each newly generatedd-MP candidate with all the otherd-MP candidates to locate and remove duplicates,which costs significant computational effort.

Xu et al.[28] converted the system-state vectorX=(x1,x2,···,xn) into a unique number byΦ(X)=then sorting and comparing these numbers to remove duplicated-MP candidates based on Theorem 3.

Theorem 3[28] For any two system-state vectorsXandY,Φ(X)=Φ(Y) if and only ifX=Y.

However,both the pairwise comparison method and Xu’s method still need to generate the duplicates,which requires extra storage space and steps to detect and remove these duplicates.Thus it is necessary to study a method to prevent duplicates in advance for the implicit enumeration method ford-MPs for a specifiedd.

4.The proposed avoiding-duplicates method

In this section,we discuss the mechanism of generating duplicated-MP candidates in the implicit enumeration method and propose a direct avoiding-duplicates method to obtaind-MPs without duplicates.

4.1 Mechanism of generating duplicate d-MP candidates

For implicit enumeration algorithms,there may have duplicates when the feasible flow vectors are transformed into state vectors [18].Define=(f1,f2,···,fm)is thekth flow vector when system demand isd.The following observation is given.

Observation 1Different flow vectors=(f1,f2,···,fm)may be transformed into the same state vectorX=(x1,x2,···,xm).

Take the network of Fig.1 from [26] as an example,and eight MPs for the network are shown in Table 1.Five duplicate 2-MP candidates (marked by *) shown in Table 2 can be driven by the well-known implicit enumeration method in Subsection 2.1.Such as=(1,0,0,1,0,0,0,0) and=(0,1,1,0,0,0,0,0) are two different flow vectors,but they can be transformed into the same state vectorX=(2,0,1,1,1,0,1,1,1).

Fig.1 A network example from [21]

Table 1 All the MPs in Fig.1

Table 2 Duplicate 2-MP candidates of the network in Fig.1

Table 3 Duplicate 3-MP candidates of the network of Fig.1

Based on Lemma 1,the following theorem indicates all the duplicated-MP candidates (d＞2) are related to duplicate 2-MP candidates.

ProofAccording to [29],if and only if thed-MP candidate flow through one of the two types of network blocks in Fig.2,in which the in-degree and out-degree of nodeviare both greater than 2,there must exists anotherd-MP candidate equal to it.

Fig.2 Two types of network blocks that generate duplicate d-MPs

4.2 The proposed method

Based on Property 1 and Property 2,an efficient and direct method with lower complexity is proposed to obtain reald-MPs without duplicates.

Then we can give the following avoiding-duplicates method.

5.The improved algorithm

Section 4 proposes an avoiding-duplicates method that can incorporate into all the algorithms that are grounded on the implicit enumeration method to searchd-MPs without duplicates.In this section,we propose an improved algorithm based on Theorem 5 to illustrate the application of the propose avoiding-duplicates method.

5.1 The proposed algorithm

Using the proposed avoiding-duplicates method,we suggest an algorithm for searching ford-MPs below.

Input:A multistate networkG(V,E,W) with demand leveld.

Output:Alld-MPs without duplicates.

Step 0Obtainfor 0 ≤j≤m.

Step 1Use the fast enumeration method to search for all feasible flow vectorsto constraints (1),(3),and(5).

Step 2Transform eachintoX=(x1,x2,···,xn) via(4).

Step 3Deleted-MP candidatesX=(x1,x2,···,xn) with cycles to obtain reald-MPs.

Step 0 is a preprocessing step for calculatingin constrains (5).In Step 1,the fast enumeration method reported by Chen et al.[18] has been used to obtain all feasible vectors.Fast enumeration has been proved to be more efficient than the traditional enumeration method and the details can be referred to Chen et al.[18].Constrain (5) is incorporated in Step 1 to tighten the upper bounds and prevent the flow vectors associated with duplicated-MP candidates from generating.Step 2 transforms all the feasible flow vectors to system-state vectors.Alld-MP candidates are verified in Step 3 to remove thosed-MP candidates with cycles.Notice that there is no additional step required to remove duplicates.

5.2 Complexity analysis

5.3 Illustration example

In this section,we take the network of Fig.1 for example to illustrate the process of searching ford-MPs.The required demanddis 3.The max capacity vectorM=(2,2,1,1,2,1,1,2,2)and the max flow vectorS=(1,1,1,1,1,2,1,1).

Step 0Obtain R(MP1)=?,R(MP2)={3,6},R(MP3)={2},R(MP4)={6},R(MP5)={6,7},R(MP6)={2,4,5},R(MP7)={5},R (MP8)=?.

Step 1Find all feasible solutions=(f1,f2,···,fm)of the constraints (1),(3),and (5) by applying fast enumeration:

There are eight feasible solutions: (0,0,1,0,0,0,1,1),(0,0,1,0,0,1,0,1),(1,0,1,0,0,0,1,0),(1,0,0,0,0,1,1,0),(1,0,0,1,0,0,0,1),(1,0,1,0,0,0,0,1),(1,0,0,0,0,0,1,1),(1,0,0,0,0,1,0,1).

Step 3There is no cycle in the network of Fig.1.

At the end of the step:

6.Efficiency investigation

In this section,the efficiency of the proposed algorithm is investigated.

Chen’s algorithm [18] and Xu’s algorithm [28] are two recent algorithms that are considered to be efficient algorithms to search ford-MPs based on the implicit enumeration method.We compare the efficiency of the proposed algorithm with the two algorithms through two experiments.All the three algorithms are programmed in Matlab 2016 and implemented on a personal computer with Intel(R) Core (TM) i5 2.40 GHz CPU,and 16 GB of RAM.We record the CPU time of the three algorithms for 20 replicates.The results are listed in Table 4 and Table 5.represents the number ofd-MPs for leveld.is the number of duplicated-MP candidates prevented by the proposed algorithm.The ratios are defined as the CPU time consumed by Chen’s algorithm[18],Xu’s algorithm [28] divided by CPU time consumed by the proposed algorithm (denoted byTChen/TandTXu/T).TChen/TandTXu/Trepresent the advantage of the proposed algorithm over Chen’s algorithm and Xu’s algorithm for finding alld-MPs without duplicates for leveld,respectively.

Table 4 CPU time of Chen’s algorithm and the proposed algorithm

Table 5 Comparisons between Chen’s algorithm and the proposed algorithm

6.1 Example 1

We consider the network shown in Fig.3 as the first example.Let the capacities for all these components set to 10.To fully explore the computational efficiency of different algorithms,multiple demand levelsdare solved for the network.Computational results are presented in Table 4,according to which we make the following observations.

Fig.3 A network for Example 1

As shown in Table 4,when the capacities of all components are fixed,the two reported algorithms [18,28] and the proposed algorithm obtain the same number of reald-MPs.While the proposed algorithm prevents a huge number of duplicated-MP candidates in advance.For example,whend=12,81 838 duplicated-MP candidates are prevented,which saves a large amount of CPU time and storage space.

Table 4 lists parts of the results fordfrom 2 to 20.Compared with the method of Chen et al.[18],the proposed algorithm takes a small amount of CPU time in searchingd-MPs for every leveld.Particularly,whendis 6,8,10,12,the ratioTChen/Tis 46.094 7,50.305 5,78.718 5 and 31.902,respectively.

Compared with Xu’s algorithm [28],when the demand leveld=2 andd=4,the proposed algorithm is less efficient.This is because whendis small,the number of duplicated-MP candidates is small.The time saved by(5) does not offset the time spent obtainingHowever,whend＞4,with the number ofd-MP candidates increasing,the proposed algorithm holds a distinct advantage,especially when the leveldis intermediate(10,12,14,16).

6.2 Example 2

In this section,we use 3×ntwo-terminal grid networks of different sizes to do the comparisons with Chen’s algorithm [18] and Xu’s algorithm [28].Fig.4 shows two typical two-terminal grid networks with 3×3 nodes and3×4 nodes.The experiment starts with 3×3 grid networks and increases by three nodes at a time,until the total nodes reach 3×6.Assume the demand is 4 for all four cases.The largest capacities of all components are set to 4.Computational results are presented in Table 5 and Fig.5.

Fig.4 Typical rectangular grid networks of 3×3 and 3×4

Fig.5 Ratio of the CPU time in grid networks of different sizes

The number of MPs of the four grid networks is 12,38,125,414.All three algorithms generate the same sets of real 4-MPs for all four grid networks considered.A large number of duplicate 4-MP candidates are prevented by the proposed algorithm.Especially,for the 3×6 grid network,the total number of 4-MP duplicates is 41 687 596,which is 55.566 4 times of real 4-MPs.This indicates that a large amount of space has been saved by the proposed algorithm.

We compare the efficiency of the three algorithms.As shown in Table 5,the proposed algorithm is more efficient than Chen’s algorithm [18] and Xu’s algorithm [28]for all four grid networks.In addition,both the CPU time ratios increase as the network size increases which can be seen in Fig.5.Particularly,when the network is a3×6 grid network,the ratios are about 47.666 8 times of Chen’s algorithm [18] and 9.789 4 times of Xu’s algorithm [28].

According to the observations,the proposed algorithm has a distinct advantage in both space efficiency and time efficiency.

7.Conclusions

Thed-MP problem plays an important role in multi-state two-terminal reliability evaluation,and as an NP-hard problem,remains interesting to investigate.This paper focuses on the problem of duplicated-MP candidates in implicit enumeration ford-MPs discusses and proves the mechanism of their generation.A direct and efficient algorithm is proposed to obtaind-MPs without duplicates.Through complexity analysis and numerical experiments,it is found that the proposed algorithm holds a distinct advantage over the existing algorithms.

The proposed algorithm can also be applied to directed or undirected networks and searches for alld-MPs with given MPs.Future research is encouraged to inspect multiterminal and multistate networks,or multi-commodities networks to solve more real-life problems.