Network Reliability Optimization

Network reliability optimization problems first appeared for telecommunication and transport systems. These days, they also have applications in computer networks, and electric and gas networks. In the modern world, the consequences of a network failing can be catastrophic in terms of cost and even lives lost. Since many non-mathematical professionals need to design networks of various kinds, network optimization is a great example of how math consulting can deliver value for industry.

The goal of reliability optimization is to minimize the cost of the network, while ensuring it still meets some minimum standard of “reliability”, represented by the probability of the network failing.¬†¬†Conceptually, a network can be represented by an undirected graph \(G = (N,E)\) with nodes \(N\) and edges \(E\):

Let \(x_{ij}\) represent which nodes we build connections between, i.e.\(x_{ij}=1\) if there is an edge between node \(i\) and node \(j\) and \(x_{ij}=0\) otherwise. Let \(c_{ij}\) represent the cost of building a connection between node \(i\) and node \(j\). Then the cost of building the network is

\[C(x) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n}c_{ij}x_{ij}.\]

Let \(p\) represent the probability that a node will be operational. There are two commonly used standards for when a network is considered to be operational, depending on the application:

  1. Two specified nodes are connected
  2. Every node is connected to every other node

It is then possible to assign to every network \(x\) a reliability \(R(x)\), which is the probability that the network will be operational. Suppose our tolerance for network failure is \(R_{min}\). Then we wish to minimize the cost function \(C(x)\) subject to the constraint \(R(x) \geq R_{min}\).

Mathematically speaking, network reliability problems are examples of integer programming problems, and can be solved in a variety of ways, such as using genetic algorithms.