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

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.