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

Abstract

In various efforts to secure the resilience of community, accurate reliability analysis of civil systems is critical considering their pivotal functions. As such systems generally consist of multiple components, their reliability analysis requires complete information to construct joint probabilistic dis-tributions of component events, which is rarely available in practice. In order to obtain the best estimates on the system reliability based on the available information, the linear programming (LP) bounds method was proposed (Song and Der Kiureghian 2003).The method obtains bounds on system reliability by solv-ing LP problems constructed by decomposing the event space into mutually exclusive and collectively exhaustive (MECE) events. Despite the optimality and flexibility of the LP bounds method, there is a limitation in the size of systems as the number of MECE events increases exponentially in regards to that of component events. In order to address this issue, this paper develops an alternative LP bounds formu-lation by employing delayed column generation, in which the LP is solved as an iteration of smaller binary integer programming (BIP). The BIP can be formulated by Boolean algebra that represents the inclusion relationships between component events, system event, and constraint events. The proposed formulation requires polynomial memory in regards to the number of constraints, allowing the evaluation of the LP bounds for larger systems and changing the major bottleneck from the number of components to that of constraint events incorporated into the LP. Four numerical examples are provided to illustrate and demonstrate the proposed method.