An efficient variable ordering heuristic for binary decision diagram–based reliability analysis of network with imperfect nodes

Zhusheng Pan, Liudong Xing, Yuchang Mo and Wenbai Li

Journal of Risk and Reliability, 2017, vol. 231, issue 6, 628-642

Abstract: While most of the research efforts on network reliability analysis have focused on networks with imperfect links but perfectly reliable nodes, binary decision diagram–based methods have recently been developed to determine reliability of networks with imperfect links and imperfect nodes. The smaller the binary decision diagram size is, the better the performance of the binary decision diagram–based algorithm will be. The binary decision diagram size heavily depends on the chosen variable ordering. As finding the optimal variable ordering is a nondeterministic polynomial time-complete problem, a heuristic is typically used. Various heuristics based on depth-first search, breadth-first search, and network-driven search have been developed for network reliability analysis. However, they often assume the networks have perfectly reliable nodes. This article advances the state-of-the-art by proposing a new ordering heuristic for the binary decision diagram–based reliability analysis of networks with imperfect links/edges and nodes. Empirical studies show that the proposed new ordering heuristic can generate significantly smaller binary decision diagram size for a wide variety of network structures than the traditional depth-first search–based, breadth-first search–based, network-driven search–based heuristics for most cases, enabling efficient binary decision diagram–based reliability analysis of large-scale networks considering both link and node failures. Robustness of the proposed heuristic is also investigated through empirical studies.

Keywords: Network reliability; binary decision diagram; edge expansion diagram; ordering heuristic; imperfect node (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1177/1748006X17721789 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:risrel:v:231:y:2017:i:6:p:628-642

DOI: 10.1177/1748006X17721789

Access Statistics for this article

More articles in Journal of Risk and Reliability
Bibliographic data for series maintained by SAGE Publications ().