An improved algorithm for finding minimum-risk 3-state-device networks

Abstract

We investigate a network optimization problem previously treated by Jenney and Sherwin and by Page and Perry: Find a minimum-risk series-parallel network topology for n devices (“components”) which can experience “open-mode” and “shorted-mode” failure states. While the complete enumeration algorithms developed so far for solving this problem only work up to about n = 9 components, we can improve the performance by additionally exploiting the associativity of both the series and the parallel arrangement operator. In our approach, series-parallel networks are represented by special unordered rooted trees. These trees are enumerated by a fast “next tree” algorithm that only applies local changes to a given tree. The gain in performance is theoretically analyzed, and experimental results are presented. Further possible improvements using partial enumeration based on a dominance structure are sketched.

Keywords:

• Networks
• trees
• series-parallel
• 3-state device
• open and shorted failure
• risk

C.R.Categories:

• F2.2
• G 2.1
• G 2.2
• I 2.8