Measuring and optimizing system reliability: a stochastic programming approach

Abstract

We propose a computational framework to quantify (measure) and to optimize the reliability of complex systems. The approach uses a graph representation of the system that is subject to random failures of its components (nodes and edges). Under this setting, reliability is defined as the probability of finding a path between sources and sink nodes under random component failures and we show that this measure can be computed by solving a stochastic mixed-integer program. The stochastic programming setting allows us to account for system constraints and general probability distributions to characterize failures and allows us to derive optimization formulations that identify designs of maximum reliability. We also propose a strategy to approximately solve these problems in a scalable manner by using purely continuous formulations.

Appendix: Quality of relaxation for simple setting

Theorem 1

The relaxation of problem (3.1) is exact.

Proof

We express problem (3.1) (denoted as P) in vector form as:

$$\begin{aligned} \begin{array}{lll} \psi (A,\xi ) =&{}\underset{y, z}{\text{max}} &{} (1-y) \\ &{}\text {s.t.} &{} A(\xi ) z = {\hat{d}} \cdot (1-y) \\ &{}&{} z \ge 0 \\ &{}&{} y \in \{0, 1\}, \end{array} \end{aligned}$$

where we define ${\hat{d}} := -d$ to express the constraints in a standard linear form. The relaxed problem (denoted as ${\bar{P}}$) is obtained by replacing $y\in \{0,1\}$ with ${\bar{y}} \in [0, 1]$. We denote optimal solutions for ${\bar{P}}$ and P as ${\bar{y}}^*$ and $y^*$, respectively. We show that ${\bar{P}}$ delivers optimal solutions for P by analyzing three possible cases. First consider the case in which ${\hat{d}} \in {\mathcal {R}}(A(\xi ))$ (where ${\mathcal {R}}(\cdot )$ denotes the range of the input matrix) and there exists a nontrivial flow solution ($z^*_j > 0$ for some j) such that $A(\xi )z^* = {\hat{d}}$. This implies that all values of y are feasible since $(1-y){\hat{d}} \in {\mathcal {R}}(A(\xi )), \ \forall y \in {\mathbb {R}}$. Thus, $y^* = {\bar{y}}^* = 0$ must be optimal solutions (yielding the largest possible objective), since any other feasible value of y would have a lower objective. The second case is that in which ${\hat{d}} \in {\mathcal {R}}(A(\xi ))$ and there does not exist a nontrivial solution ($z^*_j > 0$ for some j) such that $A(\xi )z^* = {\hat{d}}$. In this case, the only feasible solution is the trivial solution $z^* = 0$ and thus $y^* = {\bar{y}}^* = 1$. The third and final case corresponds to ${\hat{d}} \notin {\mathcal {R}}(A(\xi ))$; it follows that $(1-y){\hat{d}} \in {\mathcal {R}}(A(\xi ))$ if and only if $y=1$ since any scalar multiple of ${\hat{d}}$ will lie outside of ${\mathcal {R}}(A(\xi ))$ except for the trivial case that ${\hat{d}} = 0$. Thus, the only feasible (and, therefore, optimal) solution to both problems is $y^* = {\bar{y}}^* = 1$. $\square$