Getting Started with the BRC Algorithm

Note

The Branch and Bound Algorithm for Reliability of Coherent Systems (BRC) is an efficient method for analysing system reliability with discrete-state component events and a binary-state system event. It identifies (sub-)minimal survival and failure rules while computing system failure probability using a branch-and-bound approach.

Introduction

The BRC algorithm identifies (sub-)minimal survival and failure rules and computes the system failure probability using a branch-and-bound approach.

BRC applies to any general coherent system, meaning systems where an improvement in component states never leads to a worse system state.

The figure below illustrates the BRC process (or more details, refer to the official publication on arXiv):

BRC Algorithm — **Illustration of the BRC algorithm.**

Code Demonstration

The Jupyter notebook for this tutorial is available on GitHub.

MBNPy Version

This tutorial uses MBNPy v0.1.2.

Installation

Ensure you have the required dependencies installed before running the tutorial:

import networkx as nx
import matplotlib.pyplot as plt
from mbnpy import cpm, variable, inference
from networkx.algorithms.flow import shortest_augmenting_path
from mbnpy import brc
import numpy as np

Example: Five-Edge Network

Network Topology

We analyse the five-edge network below:

nodes = {'n1': (0, 0),
         'n2': (1, 1),
         'n3': (1, -1),
         'n4': (2, 0)}

edges = {'e1': ['n1', 'n2'],
         'e2': ['n1', 'n3'],
         'e3': ['n2', 'n3'],
         'e4': ['n2', 'n4'],
         'e5': ['n3', 'n4']}

# Plot network
plt.figure(figsize=(4,3))
G = nx.Graph()
for node in nodes:
    G.add_node(node, pos=nodes[node])
for e, pair in edges.items():
    G.add_edge(*pair, label=e)

pos = nx.get_node_attributes(G, 'pos')
edge_labels=nx.get_edge_attributes(G, 'label')
nx.draw(G, pos, with_labels=True)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()

Network Topology — **Network topology with five edges.**

Defining Component Events

The state of each edge is represented by a binary variable:

varis = {}
for k, v in edges.items():
    varis[k] = variable.Variable(name=k, values=[0, 1])  # 0 = non-functional, 1 = functional

print(varis['e1'])

The probabilities of each component event:

probs = {'e1': {0: 0.01, 1: 0.99},
         'e2': {0: 0.01, 1: 0.99},
         'e3': {0: 0.05, 1: 0.95},
         'e4': {0: 0.05, 1: 0.95},
         'e5': {0: 0.10, 1: 0.90}}

Defining the System Event

The system’s state is determined by connectivity between an origin-destination (OD) pair.

A system function must: - Take a dictionary of component states as input. - Return:

System value (informational).

System state (‘s’ for survival, ‘f’ for failure).

Minimum component state that guarantees the system state.

The function is implemented as follows:

def net_conn(comps_st, od_pair, edges, varis):
    G = nx.Graph()
    for k, x in comps_st.items():
        G.add_edge(edges[k][0], edges[k][1])
        G[edges[k][0]][edges[k][1]]['capacity'] = varis[k].values[x]

    # Perform max-flow analysis
    G.add_edge(od_pair[1], 'new_d', capacity=1)
    f_val, f_dict = nx.maximum_flow(G, od_pair[0], 'new_d')

    if f_val > 0:
        return f_val, 's', {k: 1 for k, x in f_dict.items() if x > 0}
    else:
        return f_val, 'f', None

The OD pair is set to (‘n1’, ‘n4’):

od_pair = ('n1', 'n4')

Running the BRC Algorithm

Now, we run the BRC algorithm, ensuring that the analysis is complete (pf_bnd_wr=0.0):

brs, rules, sys_res, monitor = brc.run(probs, sys_fun, max_sf=np.inf, max_nb=np.inf, pf_bnd_wr=0.0)

BRC output

*** Analysis completed with 8 system function runs ***
System failure probability: 5.16e-3
Found non-dominated rules (failure: 4, survival: 4)

Extracting System Rules

To retrieve these rules, use:

print(rules['s'])  # Survival rules
print(rules['f'])  # Failure rules

This returns:

Survival Rules: [{'e1': 1, 'e4': 1}, {'e2': 1, 'e5': 1}, {'e2': 1, 'e3': 1, 'e4': 1}, {'e1': 1, 'e3': 1, 'e5': 1}]
Failure Rules: [{'e4': 0, 'e5': 0}, {'e1': 0, 'e2': 0}, {'e1': 0, 'e3': 0, 'e5': 0}, {'e2': 0, 'e3': 0, 'e4': 0}]

Computing Component Importance Measure

Conditional probability-based importance measure (CPIM) is calculated as:

\[P(X_n=0 | S=0) = \frac{P(X_n=0, S=0)}{P(S=0)}\]

def get_cim(comp_name, cpms, varis, pf):
    var_elim_names = [e for e in edges if e != comp_name]
    cpm_s_x = inference.variable_elim(cpms, [varis[e] for e in var_elim_names])
    p_s0_x0 = sum(cpm_s_x.p[np.where((cpm_s_x.C == [0, 0]).all(axis=1))])
    return p_s0_x0[0] / pf

cims = {comp: get_cim(comp, cpms, varis, 5.16e-3) for comp in edges}
print(cims)

Results: {‘e1’: 0.036, ‘e2’: 0.031, ‘e3’: 0.059, ‘e4’: 0.928, ‘e5’: 0.934}

Component importance visualisation:

The BRC algorithm calculates system failure probability for general coherent systems.
It identifies (sub-)minimal survival and failure rules.
Identified rules are used to decompose system event space into failure and survival branches.
Branches can be used to compute advanced probability queries such as component importance measures.