Decision Diagram Based Symbolic Algorithm for Evaluating the Reliability of a Multistate Flow Network
| Autor: | Fengying Li, Rongsheng Dong, Zhoubo Xu, Yangyang Zhu |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
021103 operations research
Theoretical computer science Article Subject Binary decision diagram lcsh:Mathematics General Mathematics Reliability (computer networking) 0211 other engineering and technologies General Engineering 02 engineering and technology lcsh:QA1-939 Flow network Data structure Mathematical proof lcsh:TA1-2040 0202 electrical engineering electronic engineering information engineering Decomposition (computer science) State space Influence diagram 020201 artificial intelligence & image processing lcsh:Engineering (General). Civil engineering (General) Algorithm Mathematics |
| Zdroj: | Mathematical Problems in Engineering, Vol 2016 (2016) |
| ISSN: | 1563-5147 1024-123X |
| DOI: | 10.1155/2016/6908120 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|