Magnitude Relation of the All-terminal Reliability of Network Systems

摘要

We concern the minimization problem of the total construction cost subject to the condition that the all-terminal reliability is not less than a reliability threshold. Although algorithm for solving this problem has been developed based on the so-called branch and bound method, it is known that the implement of the existing algorithm requires a fair amount of time, especially in the case that the number of edges is quite greater than the number of nodes. To reduce the computational time, we apply factoring method to classify network systems into several types (groups), and specify the type which has greater all-terminal reliability than the other types. Furthermore, we derive the exact maximum all-terminal reliability of the network systems with n + 4 edges. Our proposal directly leads to a significant improvement of the overall efficiency of the optimization algorithm.