Bounds on Reliability of Larger Systems by Linear Programming with Delayed Column Generation

Abstract

In order to accurately assess the reliability of a real-world complex system, the joint distribution of component events is needed. In reality, however, such complete information to model the joint distributions of system components is rarely available. As a way to resort only to the available information while excluding any assumptions on the form of distributions, a linear programming (LP) bounds method was developed in 2003, which computes the narrowest bounds possible for given information regarding marginal and joint failure probabilities. However, the number of variables of the optimization problem exponentially increases as that of component events increases, requiring an insurmountable memory for larger systems. In order to overcome such memory issue, an alternative formulation of the LP bounds method is proposed in this paper. Specifically, an iteration of binary integer programming (BIP) is formulated based on the inclusion relationships between the events of consideration. As a result, the memory requirement can be significantly alleviated with the trade-off of the computational cost required for repeated optimizations of smaller BIP problems. Then, the major bottleneck is changed from the number of component events to that of constraints given as information to narrow the bounds. This paper also provides empirical suggestions on the selection of a subset of constraints to further extend the applicability of the proposed methodology to even larger systems. Five numerical examples of series, parallel, and general system reliability problems are provided to demonstrate the method and its applications.