Searching for <i>d-</i>MPs for All Level <i>d</i> in Multistate Two-Terminal Networks Without Duplicates
Guanghan Bai, Bei Xu, Xiaoguang Chen, Yun-An Zhang, Junyong Tao
Abstract
The reliability evaluation of multistate networks is primarily using minimal path (cut) vectors, namely d-MPs (d-MCs), which are the lower (upper) boundary vectors that satisfy the system demand d. The generation of all d-MPs (d-MCs) is an NP-hard problem. Thus, it is important to develop an efficient algorithm to search for d-MPs (d-MCs). Existing algorithms searching for d-MPs based on MPs all generate duplicate d-MP candidates, and extra steps are required to detect and remove those duplicates. In this article, we propose an improved algorithm to search for d-MPs for all d levels without generating duplicate d-MP candidates for two-terminal multistate networks. First, we discover and prove the mechanism of generating duplicate d-MP candidates based on MPs. Second, a novel method is proposed to prevent generating duplicate d-MP candidates. Third, an improved algorithm is developed by combining the proposed method to search for d-MPs without generating duplicate d-MP candidates for all d levels. Through computational experiments, it is found that the proposed algorithm is more efficient than existing algorithms for finding all d-MPs for all possible d values.