A Greedy Branch-and-Bound Inclusion-Exclusion Algorithm for Calculating the Exact Multi-State Network Reliability
Wei‐Chang Yeh · IEEE Transactions on Reliability · 2008
In this study, a new IE (Inclusion-Exclusion Principle) involving some intuitive properties that characterize the structure of the intersections of d-minimal paths (d-MP)/d-minimal cuts (d-MC), and the relationships between d-MP/d-MC is developed to improve the IE for calculating the exact multi-state network (MSN) reliability. The proposed IE (called the Greedy-B&B-IE) developed first a greedy procedure for reordering d-MP/d-MC to speed up the procedure in detecting & deleting dominated terms. Then, a Branch-and-Bound (B&B)-based technique is proposed to implement the IE to reduce the number of intersections, and decrease the number of multiplications required for calculating the probability value of each term.