A greedy branch-and-bound inclusion-exclusion algorithm for calculating the exact multi-state network reliability

作者：Yeh Wei Chang^*

来源：IEEE Transactions on Reliability, 2008, 57(1): 88-93.

DOI：10.1109/TR.2008.916871

• branch-and-bound
• d-minimal path/cut
• greedy procedure
• inclusion-exclusion principle
• multi-state network
• network reliability

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.

• 出版日期2008-3
• 单位清华大学