# Capacity Expansion and Reliability Evaluation on the Networks Flows with Continuous Stochastic Functional Capacity

Authors: F. Hamzezadeh; H. Salehi Fathabadi
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

In many systems such as computer network, fuel distribution, and transportation system, it is necessary to change the capacity of some arcs in order to increase maximum flow value from sources to sink t, while the capacity change incurs minimum cost. In real-time networks, some factors cause loss of arc’s flow. For example, in some flow distribution systems, evaporation, erosion or sediment in pipes waste the flow. Here we define a real capacity, or the so-called functional capacity,which is the operational capacity of an arc. In other words, the functional capacity of an arc equals the possible maximum flow that may pass through the arc. Increasing the functional arcs capacities incurs some cost. There is a certain resource available to cover the costs. First, we construct a mathematical model to minimize the total cost of expanding the functional capacities to the required levels. Then, we consider the loss of flow on each arc as a stochastic variable and compute the system reliability.


---

## Body

## 1. Introduction

Given a directed network flow with unique sources and unique sink t, one of the common problems is the maximum flow problem where the value of flow from s to t should be maximized. Various algorithms have been presented to solve this problem. The first algorithm developed by Ford and Fulkerson [1] was called Augmenting Path Algorithm. Karzanov [2] introduced the first preflow-push algorithm on layered networks. He obtained an O
(
n
3
) algorithm. Capacity scaling is another polynomial algorithm developed by Ahuja and Orlin [3]. It seems that the best available time bounds algorithms to solve this problem are based on Alon [4] and Ahuja and Orlin [5].The budgeted capacity expansion problem has been investigated for different systems. One of them is flow expansion on transportation networks with budget constraints. This problem was studied by Elalouf et al. [6]. The general budget-restricted max flow problem was first discussed by Eiselt and Frajer [7]. Also, another algorithm for optimal expansion problems was provided by Ahuja et al. [8].Many physical flow systems are regarded as stochastic network flows. In such a system, the system reliability is an important criterion for system performance. Several studies have evaluated network reliability of maximum flow. Yeh evaluated the reliability factor of a network, where arc capacities are stochastic. He defined a simple approach to evaluate reliability of a multistate network [9]. Xiao et al. [10] presented a model for reliability computation in power distribution system. Later, the presented approach in [9] was considerably improved by Salehi Fathabadi and Forghani-elahabadi [11]. In another paper, Yeh [12] designed a survivable network under cost constraints and computed its reliability. For this case, Salehi Fathabadi and Khodaei [13] presented a different method to find the optimal system parameters and computed its reliability. Lin and Yeh [14] proposed a genetic algorithm to find maximal reliability of networks. Also Lin studied stochastic flow network with two commodities [15] and network reliability with budget constraint [16]. In all of the above studies the probability function of the arcs’ capacity was assumed to be discrete. However, in many real-life systems, where the flow is liquid, this assumption is not applicable.In this paper, we consider network flow systems in which the functional capacities of the arcs are continuous random variables. The investigated problem is to expand the nominal capacities of arcs so that the system would be capable of securing the demands, while the expansion cost is minimal. Then, we evaluate the reliability of the systems as the probability that the network can transfer a desired amount of flow from the source,s, to the sink, t. The former goal is achieved by running the algorithm CEA, which is explained in Section 3 and the later goal is accomplished in Section 4.Regarding the previous studies [17, 18], our contribution has been compiled based on the following. (i) We define and use the arcs’ functional capacities which are quite different from arcs’ nominal capacities in real-life systems. (ii) The probability functions of the stochastic functional capacities are continuous. (iii) The capacity expansion cost is minimum. The capacity expansion takes place in a discrete manner until the maximum flow reaches the required level. This paper has been arranged as follows. Section 2 defines notations, primary assumptions, and the related theorems. Also, the mathematical model of the problem is constructed in Section 2. Section 3 explains the capacity expansion algorithm. System reliability is computed in Section 4 and eventually a numerical example will be considered in Section 5.


## 2. Notations and Assumptions

We use the following definitions and assumptions throughout this paper.G
(
V
,
A
): A directed network flow with a unique source s and a unique sink t, where V is the set of nodes and A
⊆
V
×
V is the set of arcs.
u
i
j: Nominal capacity of (
i
,
j
)
∈
A (the initial built-in capacity of arc
(
i
,
j
)).
u
i
j
f: Functional capacity of arc
(
i
,
j
)
∈
A, (the current operational capacity of arc
(
i
,
j
)
∈
A).
w
i
j: Amount of capacity expansion on arc
(
i
,
j
)
∈
A.
M
i
j: Maximum capacity expansion for arc
(
i
,
j
)
∈
A.
c
i
j: Expansion cost per unit of capacity on arc
(
i
,
j
)
∈
A.
α
i
j: Loss factor on (
i
,
j
)
∈
A. The fraction of arc’s capacity is lost due to some stochastic events. Then α
i
j
′
=
1
-
α
i
j is fraction of arc’s capacity that is able to transmit the flow. We call them transmission factor.
P
i: The ith simple path from s to t. A simple path does not include repeated arcs and/or nodes.
Ω
r: The rth category r
=
1,2
,
…
,
R. Each category includes several subsets of transmission factors. In addition, each category is related to set of simple paths that are capable of sending maximum flow from s to t.The network flow satisfies the following assumption.(i)
Each node is perfectly reliable. This means that the amount of flow passing through a node does not change.
(ii)
The loss factors and transmission factors of different arcs are statistically independent random variable.


## 3. Problem Statement

AssumeG
=
(
V
,
A
) is a network flow with node set, V; arc set, A; source node s; and sink node t. We assume G includes n nodes and m arcs. Each arc, (
i
,
j
), has a nominal capacity of u
i
j. There are some factors in this network that cause loss of flow on each arc. For example, in a water distribution system, evaporation, erosion, or sediment in pipes waste the flow in some parts. For each arc we define a real capacity or the so-calledfunctional capacity and denote it by u
i
j
f. u
i
j
f equals the real amount of maximum flow that can pass along the arc
(
i
,
j
). According to the current functional capacities, the real maximum flow value from s to t is v. This value is equal to the functional capacity of the current minimum cut, (
S
,
S
-
) [19]. We are going to expand the nominal capacity, u
i
j, such that the real maximum flow value is increased by v
0 and the total expansion cost is minimized. We know that the expansion cost on arc(
i
,
j
), for each unit of capacity, is c
i
j and the maximum capacity expansion is M
i
j units. For each arc, say, (
i
,
j
), there is a loss factor, α
i
j, which is a continuous random variable in interval [
0,1
] and shows the fraction of nominal capacity that is wasted. Thus transmission factor (α
i
j
′
=
1
-
α
i
j, for all (
i
,
j
)
∈
A) is computable for any arc. Note that this factor is a continuous random number in interval [
0,1
] as well. Therefore, the functional capacity of arc
(
i
,
j
) is computed as u
i
j
f
=
α
i
j
′
u
i
j. u
i
j
f
s satisfy 0
≤
u
i
j
f
=
α
i
j
′
u
i
j
≤
u
i
j, (
i
,
j
)
∈
A.Now using the above notations and assuming(
S
,
S
-
) is the current minimum s
-
t cut, the mathematical model of the problem is constructed as
(1)
min
⁡
z
=
∑
(
i
,
j
)
∈
A
c
i
j
w
i
j
,
(2)
s
.
t
.
∑
j
∈
V
x
i
j
-
∑
j
∈
V
x
j
i
=
{
v
+
v
0
,
if
i
=
s
,
0
,
if
i
≠
s
,
t
,
-
(
v
+
v
0
)
,
if
i
=
t
,
(3)
∑
(
i
,
j
)
∈
(
S
,
S
-
)
α
i
j
′
u
i
j
=
v
,
(4)
0
≤
x
i
j
≤
α
i
j
′
(
u
i
j
+
w
i
j
)
,
(
i
,
j
)
∈
A
,
(5)
α
i
j
′
∈
[
0,1
]
,
(
i
,
j
)
∈
A
.
Constraints (2) show the flows are balanced at each node other than the source and sink; for the source and sink nodes the amount of out-flow from s equals the amount of in-flow to t and equals v
+
v
0. Constraint (3) shows that the maximum flow, before changing the arcs’ capacities, is equal to v. The constraints (4) guaranty the arc flows do not exceed the functional arcs’ capacities. Finally, continuity of α
i
j
′
s, and therefore continuity of x
i
j are the impact of constraints (5).


### 3.1. The Capacity Expansion Algorithm (CEA)

It should be noted that, according to the current functional capacities, the value of the maximum flow isv and is equal to the capacity of the minimum s
-
t cut, (
S
,
S
-
). Using the functional capacity, we assume that the current maximum flow is denoted by x
=
{
x
i
j
}
(
i
,
j
)
∈
A and generates the residual network G
(
x
). Suppose P
k is a path from s to t in G. The current amount of flow passing through this path is equal to δ
k
=
min
⁡
{
u
i
j
f
∣
(
i
,
j
)
∈
P
k
}. For some arcs, (
i
,
j
)
∈
P
k say, it may be δ
k
<
u
i
j
f. In this case, (
i
,
j
) has some residual (free) capacity that may be used, without any cost, to increase the flow on (
i
,
j
). If δ
k
=
u
i
j
f, for an arc
(
i
,
j
)
∈
P
k, there is no free capacity left on (
i
,
j
) and the capacity of this arc must be increased incurring some cost. According to this point, we define capacity expanding cost for each arc and find the cheapest path from the source node to the sink node. For this purpose the residual network and an auxiliary network calledexpansion-cost-network are constructed. We denote the later one by G
(
cos
⁡
⁡
t
) and it is constructed as follows.G
(
cos
⁡
⁡
t
) include all nodes of G
(
x
). For every arc
(
i
,
j
)
∈
G
(
x
) two directed arcs in opposite directions between i and j are drawn in G
(
cos
⁡
t
). Note that, if there already are two arcs between i and j with opposite directions, no more arcs are drawn between these nodes. The arc
(
i
,
j
) shows the possibility of expanding capacity with cost c
i
j
′ on (
i
,
j
)
∈
G
(
cos
⁡
⁡
t
). The artificial arc
(
j
,
i
) represents the possibility of reducing the expanded capacity on (
i
,
j
)
∈
G
(
cos
⁡
⁡
t
). It is important to note that, when there is a positive amount of flow going from node i to node j through the arc
(
i
,
j
), we may decrease it by assuming an artificial arc from j to i with some positive flow x
j
i and cost c
j
i
′. Each arc in G
(
cos
⁡
⁡
t
) is labeled by c
i
j
′, which is the expansion or narrowing cost per unit of capacity. If the flow on arc(
i
,
j
) is smaller than the functional capacity, namely, δ
k
<
u
i
j
f, then this arc steel has room to increase the flow. Hence there is no need to increase the current capacity. The labels for this case are set as c
i
j
′
=
c
j
i
′
=
0. Otherwise, the capacity of (
i
,
j
) should be expanded. At this stage of the algorithm, if the capacity of this arc has not been expanded so far, namely, w
i
j
=
0, then increasing the capacity is possible. Hence we set c
i
j
′
=
c
i
j and c
j
i
′
=
0. If 0
<
w
i
j
<
M
i
j, then, for a better solution, we may increase the capacity or reduce the increased capacity. Therefore the labels are set as c
i
j
′
=
c
i
j, c
j
i
′
=
-
c
i
j. Eventually, if the expanded capacity value on arc
(
i
,
j
) is equal to M
i
j the capacity expansion is not possible and we can only reduce it. So, the costs are set as c
i
j
′
=
+
∞ and c
j
i
′
=
-
c
i
j [6].After setting the labels inG
(
cos
⁡
⁡
t
), the cheapest simple path from the source to the sink is found; the capacities are extended on this path as much as possible and the current iteration is ended with computing the maximum flow. This process is repeated until the value of the maximum flow becomes equal to v
+
v
0.


### 3.2. Pseudocode of CEA

For more details see  Pseudocode1.Pseudocode 1:
Start
Read the nominal capacities,u
i
j s, and subset of the transmission factors, α
i
j
′  s, of the original network, G.
Calculate functional capacity,u
i
j
f  s, of each arc.
Find the maximum flow, MAX.
WhileMAX <v
+
v
0
Do
Define the residual graphG
(
x
) and G(cost) as follow
V
G
(
cos
⁡
t
)
=
V
G
(
x
) and A
G
(
cos
⁡
t
)
=
{
(
i
,
j
)
,
(
j
,
i
)
∣
(
i
,
j
)
o
r
(
j
,
i
)
∈
A
G
(
x
)
}
and let a label for each arc which show the cost of arc expansion as following:
Foreach (
i
,
j
)
∈
A
G
(
cos
⁡
t
)
Do
if
u
i
j
′
=
u
i
j
f
-
x
i
j
>
0 and u
j
i
′
=
x
i
j
>
0
then
setc
i
j
′
=
0   and   c
j
i
′
=
0
else
if
u
i
j
′
=
0 and u
j
i
′
=
0
if
w
i
j
=
0
then
set c
i
j
′
=
c
i
j and c
j
i
′
=
0
else if
0
<
w
i
j
<
M
i
j
then
set c
i
j
′
=
c
i
j and c
j
i
′
=
-
c
i
j
else if
w
i
j
=
M
i
j
then
set c
i
j
′
=
∞ and  c
j
i
′
=
-
c
i
j
end if
end if
end if
Find the shortest path P in G(cost) regarding c
′ value
if (sum of the costs on the shortest path < +∞)
∀
(
i
,
j
)
∈
P replace the new capacity in G as follow:
if
c
i
j
′
=
0 and c
j
i
′
=
0 then
setw
i
j
new
=
0  and   u
i
j
new
=
u
i
j
elseif
c
i
j
′
>
0 and c
j
i
′
≤
0 or c
i
j
′
≤
0 and c
j
i
′
>
0 then
setw
i
j
new
=
min
⁡
{
min
⁡
{
M
p
q
-
w
p
q
∣
(
p
,
q
)
∈
P
,
c
p
q
′
>
0
,
c
q
p
′
≤
0
}
,
min
⁡
{
u
p
q
-
x
p
q
∣
(
p
,
q
)
∈
P
,
c
p
q
′
=
0
,
c
q
p
′
=
0
}
,
min
⁡
{
u
p
q
+
w
p
q
∣
(
p
,
q
)
∈
P
,
c
p
q
′
≤
0
,
c
q
p
′
>
0
}
} and  u
i
j
new
=
u
i
j
+
w
i
j
new
end if
end if
end For
Calculate functional capacity using new capacity
Find maximum flow, MAX.
end while
end.


### 3.3. Algorithm’s Complexity

We now consider the complexity of CEA. We might compute the computational time of this algorithm as allocated to the following four basic operations.(1)
Construction ofG
(
x
) and G
(
cos
⁡
⁡
t
): concerning residual network, the algorithm allocates costs to the arcs of G
(
cos
⁡
⁡
t
). If the network contains m arcs, costs of 2
m arcs would be calculated and assigned to the arcs. Thus the algorithm performs this operation in O
(
m
) time.
(2)
Finding the shortest path: the algorithm finds the cheapest (shortest) path from the source to the sink according to the cost vectorc
′. FIFO implementation of the modified label correcting algorithm is the best known algorithm for this purpose. The runtime of this algorithm is O
(
n
m
), [19].
(3)
Capacity expansions: for each arc belonging to the cheapest path, it would be examined whether capacity expansions are required or not. This operation would be implemented inO
(
m
) time.
(4)
Computing the maximum flow: at this stage, the maximum flow algorithm is run. The order of the best known algorithm (highest label preflow push) isO
(
n
2
m
) [19].The above steps are repeated until the maximum flow for the first time becomes equal to or greater thanv
+
v
0. Suppose S
(
v
0
) is the maximum number overall repetition needed to reach this threshold. Finally we have the following result.Theorem 1.
The capacity expansion algorithm (CEA) runs inO
(
S
(
v
0
)
(
m
+
n
m
+
n
2
m
)
) time.


## 3.1. The Capacity Expansion Algorithm (CEA)

It should be noted that, according to the current functional capacities, the value of the maximum flow isv and is equal to the capacity of the minimum s
-
t cut, (
S
,
S
-
). Using the functional capacity, we assume that the current maximum flow is denoted by x
=
{
x
i
j
}
(
i
,
j
)
∈
A and generates the residual network G
(
x
). Suppose P
k is a path from s to t in G. The current amount of flow passing through this path is equal to δ
k
=
min
⁡
{
u
i
j
f
∣
(
i
,
j
)
∈
P
k
}. For some arcs, (
i
,
j
)
∈
P
k say, it may be δ
k
<
u
i
j
f. In this case, (
i
,
j
) has some residual (free) capacity that may be used, without any cost, to increase the flow on (
i
,
j
). If δ
k
=
u
i
j
f, for an arc
(
i
,
j
)
∈
P
k, there is no free capacity left on (
i
,
j
) and the capacity of this arc must be increased incurring some cost. According to this point, we define capacity expanding cost for each arc and find the cheapest path from the source node to the sink node. For this purpose the residual network and an auxiliary network calledexpansion-cost-network are constructed. We denote the later one by G
(
cos
⁡
⁡
t
) and it is constructed as follows.G
(
cos
⁡
⁡
t
) include all nodes of G
(
x
). For every arc
(
i
,
j
)
∈
G
(
x
) two directed arcs in opposite directions between i and j are drawn in G
(
cos
⁡
t
). Note that, if there already are two arcs between i and j with opposite directions, no more arcs are drawn between these nodes. The arc
(
i
,
j
) shows the possibility of expanding capacity with cost c
i
j
′ on (
i
,
j
)
∈
G
(
cos
⁡
⁡
t
). The artificial arc
(
j
,
i
) represents the possibility of reducing the expanded capacity on (
i
,
j
)
∈
G
(
cos
⁡
⁡
t
). It is important to note that, when there is a positive amount of flow going from node i to node j through the arc
(
i
,
j
), we may decrease it by assuming an artificial arc from j to i with some positive flow x
j
i and cost c
j
i
′. Each arc in G
(
cos
⁡
⁡
t
) is labeled by c
i
j
′, which is the expansion or narrowing cost per unit of capacity. If the flow on arc(
i
,
j
) is smaller than the functional capacity, namely, δ
k
<
u
i
j
f, then this arc steel has room to increase the flow. Hence there is no need to increase the current capacity. The labels for this case are set as c
i
j
′
=
c
j
i
′
=
0. Otherwise, the capacity of (
i
,
j
) should be expanded. At this stage of the algorithm, if the capacity of this arc has not been expanded so far, namely, w
i
j
=
0, then increasing the capacity is possible. Hence we set c
i
j
′
=
c
i
j and c
j
i
′
=
0. If 0
<
w
i
j
<
M
i
j, then, for a better solution, we may increase the capacity or reduce the increased capacity. Therefore the labels are set as c
i
j
′
=
c
i
j, c
j
i
′
=
-
c
i
j. Eventually, if the expanded capacity value on arc
(
i
,
j
) is equal to M
i
j the capacity expansion is not possible and we can only reduce it. So, the costs are set as c
i
j
′
=
+
∞ and c
j
i
′
=
-
c
i
j [6].After setting the labels inG
(
cos
⁡
⁡
t
), the cheapest simple path from the source to the sink is found; the capacities are extended on this path as much as possible and the current iteration is ended with computing the maximum flow. This process is repeated until the value of the maximum flow becomes equal to v
+
v
0.


## 3.2. Pseudocode of CEA

For more details see  Pseudocode1.Pseudocode 1:
Start
Read the nominal capacities,u
i
j s, and subset of the transmission factors, α
i
j
′  s, of the original network, G.
Calculate functional capacity,u
i
j
f  s, of each arc.
Find the maximum flow, MAX.
WhileMAX <v
+
v
0
Do
Define the residual graphG
(
x
) and G(cost) as follow
V
G
(
cos
⁡
t
)
=
V
G
(
x
) and A
G
(
cos
⁡
t
)
=
{
(
i
,
j
)
,
(
j
,
i
)
∣
(
i
,
j
)
o
r
(
j
,
i
)
∈
A
G
(
x
)
}
and let a label for each arc which show the cost of arc expansion as following:
Foreach (
i
,
j
)
∈
A
G
(
cos
⁡
t
)
Do
if
u
i
j
′
=
u
i
j
f
-
x
i
j
>
0 and u
j
i
′
=
x
i
j
>
0
then
setc
i
j
′
=
0   and   c
j
i
′
=
0
else
if
u
i
j
′
=
0 and u
j
i
′
=
0
if
w
i
j
=
0
then
set c
i
j
′
=
c
i
j and c
j
i
′
=
0
else if
0
<
w
i
j
<
M
i
j
then
set c
i
j
′
=
c
i
j and c
j
i
′
=
-
c
i
j
else if
w
i
j
=
M
i
j
then
set c
i
j
′
=
∞ and  c
j
i
′
=
-
c
i
j
end if
end if
end if
Find the shortest path P in G(cost) regarding c
′ value
if (sum of the costs on the shortest path < +∞)
∀
(
i
,
j
)
∈
P replace the new capacity in G as follow:
if
c
i
j
′
=
0 and c
j
i
′
=
0 then
setw
i
j
new
=
0  and   u
i
j
new
=
u
i
j
elseif
c
i
j
′
>
0 and c
j
i
′
≤
0 or c
i
j
′
≤
0 and c
j
i
′
>
0 then
setw
i
j
new
=
min
⁡
{
min
⁡
{
M
p
q
-
w
p
q
∣
(
p
,
q
)
∈
P
,
c
p
q
′
>
0
,
c
q
p
′
≤
0
}
,
min
⁡
{
u
p
q
-
x
p
q
∣
(
p
,
q
)
∈
P
,
c
p
q
′
=
0
,
c
q
p
′
=
0
}
,
min
⁡
{
u
p
q
+
w
p
q
∣
(
p
,
q
)
∈
P
,
c
p
q
′
≤
0
,
c
q
p
′
>
0
}
} and  u
i
j
new
=
u
i
j
+
w
i
j
new
end if
end if
end For
Calculate functional capacity using new capacity
Find maximum flow, MAX.
end while
end.


## 3.3. Algorithm’s Complexity

We now consider the complexity of CEA. We might compute the computational time of this algorithm as allocated to the following four basic operations.(1)
Construction ofG
(
x
) and G
(
cos
⁡
⁡
t
): concerning residual network, the algorithm allocates costs to the arcs of G
(
cos
⁡
⁡
t
). If the network contains m arcs, costs of 2
m arcs would be calculated and assigned to the arcs. Thus the algorithm performs this operation in O
(
m
) time.
(2)
Finding the shortest path: the algorithm finds the cheapest (shortest) path from the source to the sink according to the cost vectorc
′. FIFO implementation of the modified label correcting algorithm is the best known algorithm for this purpose. The runtime of this algorithm is O
(
n
m
), [19].
(3)
Capacity expansions: for each arc belonging to the cheapest path, it would be examined whether capacity expansions are required or not. This operation would be implemented inO
(
m
) time.
(4)
Computing the maximum flow: at this stage, the maximum flow algorithm is run. The order of the best known algorithm (highest label preflow push) isO
(
n
2
m
) [19].The above steps are repeated until the maximum flow for the first time becomes equal to or greater thanv
+
v
0. Suppose S
(
v
0
) is the maximum number overall repetition needed to reach this threshold. Finally we have the following result.Theorem 1.
The capacity expansion algorithm (CEA) runs inO
(
S
(
v
0
)
(
m
+
n
m
+
n
2
m
)
) time.


## 4. System Reliability

In order to increase the maximum flow value to the required value, the above algorithm computes the optimal capacity expansion while assuming deterministic transmission factors. But, in case of randomness the algorithm may be used only for observation values of these factors. System reliability is defined as the probability that the maximum flow value satisfies a certain condition, such as appraising some demands [3, 13]. Since the loss factors, transmission factors, and, therefore, the functional capacities are stochastic, the final value of maximum flow is also stochastic. In order to establish an approach for evaluating the system reliability of such systems, we assume the loss factors are continuous uniform random variables and generate N uniformly distributed pseudo-random numbers in the interval [
0,1
]. The method to generate these numbers is multiplication congruent [20]. Then we calculate the transmission factors for any arc using loss factors. Note these factors are continuous uniform random numbers in the interval [
0,1
] as well. We denote them by α
1
′
,
α
2
′
,
…
,
α
N
′. We consider several subsets of these numbers and denote them by A
j, j
=
1,2
,
…
,
L. Each subset includes m members. At the beginning of each run of CEA, we take one of these subsets as the arcs’ transmission factors and run the algorithm. At the end of CEA a set of paths that transfer at least v
+
v
0 unit of flow from s to t is generated. It is clear that the generated paths and their number depend on the given subset of transmission factors. Furthermore, there may be subsets of transmission factors that generate similar set of paths. We consider the subsets of transmission factors that generate the same set of paths as a category and assume that the number of categories is R (R
≤
L). We denote the categories by Ω
r,  r
=
1,2
,
…
,
R. Also we assume that the number of paths associated to the rth category is K
r.Now we considerv
-
r as the final value of maximum flow in each category and compute the density function of v
-
r. Since 0
≤
α
i
j
′
≤
1,  u
i
j
f
s are continuous uniform random variables on interval [
0
,
u
i
j
] with density function of f
(
u
i
j
f
)
=
(
1
/
u
i
j
)
I
[
o
,
u
i
j
]. The number of paths generated at each run of CEA depends on the applied subset of transmission factors. For each path P
i associated with the rth category, the flow value on P
i is computed as
(6)
δ
i
r
=
min
⁡
⁡
{
u
p
q
f
∣
(
p
,
q
)
∈
P
i
}
,
i
=
1,2
,
…
,
K
r
,
r
=
1,2
,
…
,
R
.
The total flow value v
-
r is equal to the sum of all flow values on the generated paths. That is, v
-
r
=
∑
i
=
1
K
r
δ
i
r. The distribution functions of δ
i
r may be computed according to the following theorem. Then we determine density function of v
-
r.Theorem 2 (see [21]).
Ift
1
,
t
2
,
…
,
t
n are independent random variables with distribution function F
t
i
(
t
) and T
(
1
)
=
min
⁡
{
t
1
,
t
2
,
…
,
t
n
}, then F
T
(
1
)
(
t
)
=
1
-
∏
i
=
1
n
[
1
-
F
t
i
(
t
)
], [21].Now, we apply the following procedure to compute the network reliability.


### 4.1. Computing the Network Reliability

After running CEAL times with input of A
j, j
=
1,2
,
…
,
L, and determining the categories Ω
r, r
=
1,2
,
…
,
R, the following procedure is performed to compute the network reliability.Step 1.
From each category,Ω
r, r
=
1,2
,
…
,
R, select one subset of transmission factors, A
r say.Step 2.
For eachr
=
1,2
,
…
,
R and i
=
1,2
,
…
,
K
r, compute
(7)
δ
i
r
=
min
⁡
⁡
{
u
p
q
f
∣
(
p
,
q
)
∈
P
i
}
,
i
=
1,2
,
…
,
K
r
,
r
=
1,2
,
…
,
R
.Step 3.
Find the probability function ofδ
i
r, where i
=
1,2
,
3
,
…
,
K
r and r
=
1,2
,
…
,
R.Step 4.
Calculatev
-
r
=
∑
i
=
1
K
r
δ
i
r and its probability functions [21].Step 5.
Compute the conditional probability; that is,p
r (v
-
r
>
v
∣
α
i
′
,
i
=
1,2
,
…
,
m), r
=
1,2
,
…
,
R.Now the system’s reliability is computed using the following equation:(8)
p
(
v
-
>
v
)
=
∑
r
=
1
R
p
r
(
v
-
r
>
v
∣
α
i
′
,
i
=
1,2
,
…
,
m
)
R
.


## 4.1. Computing the Network Reliability

After running CEAL times with input of A
j, j
=
1,2
,
…
,
L, and determining the categories Ω
r, r
=
1,2
,
…
,
R, the following procedure is performed to compute the network reliability.Step 1.
From each category,Ω
r, r
=
1,2
,
…
,
R, select one subset of transmission factors, A
r say.Step 2.
For eachr
=
1,2
,
…
,
R and i
=
1,2
,
…
,
K
r, compute
(7)
δ
i
r
=
min
⁡
⁡
{
u
p
q
f
∣
(
p
,
q
)
∈
P
i
}
,
i
=
1,2
,
…
,
K
r
,
r
=
1,2
,
…
,
R
.Step 3.
Find the probability function ofδ
i
r, where i
=
1,2
,
3
,
…
,
K
r and r
=
1,2
,
…
,
R.Step 4.
Calculatev
-
r
=
∑
i
=
1
K
r
δ
i
r and its probability functions [21].Step 5.
Compute the conditional probability; that is,p
r (v
-
r
>
v
∣
α
i
′
,
i
=
1,2
,
…
,
m), r
=
1,2
,
…
,
R.Now the system’s reliability is computed using the following equation:(8)
p
(
v
-
>
v
)
=
∑
r
=
1
R
p
r
(
v
-
r
>
v
∣
α
i
′
,
i
=
1,2
,
…
,
m
)
R
.


## 5. Numerical Example

In order to illustrate how the algorithm works, we apply it to the network flow shown in Figure1. In this example, we assume v
=
3.89 and v
0
=
3.28. We generate the following sequence of pseudo-random numbers, transmission factor, and its subsequences:
(9)
(
α
1
,
α
2
,
α
3
,
α
4
,
α
5
,
α
6
)
=
(
0.11,0.1,0.34,0.01,0.2,0.8
)
,
(
α
1
′
,
α
2
′
,
α
3
′
,
α
4
′
,
α
5
′
,
α
6
′
)
=
(
0.89,0.9,0.66,0.99
≅
1,0.8,0.2
)
,
A
1
=
(
0.89,0.9,0.66,0.99
≅
1,0.8
)
,
A
2
=
(
0.89,0.2,0.9,0.8,0.99
≅
1
)
,
A
3
=
(
0.89,0.9,0.2,0.99
≅
1,0.8
)
,
A
4
=
(
0.89,0.66,0.9,0.8,0.99
≅
1
)
,
A
5
=
(
0.2,0.8,0.99
≅
1,0.66,0.89
)
.
Note that A
j, j
=
1,2
,
…
,
5, has been arranged as (
α
s
1
′
,
α
1
t
′
,
α
12
′
,
α
s
2
′
,
α
2
t
′
).Figure 1
An example of network flow; arc labels present as(
u
i
j
,
M
i
j
,
c
i
j
).We useA
j, j
=
1,2
,
…
,
5, as transmission factors and run CEA to find the related paths from node s to node t. For example, we consider A
1 and run algorithm CEA. For more explanation, we describe one stage of implementing this algorithm using A
1 in Figure 2.The network after one stage of running CEA usingA
1.
(a)
Functional capacity—maximum flow: 3.89 unit
(b)
Shortest path inG
(
cos
⁡
⁡
t
): 1$
(c)
Extended capacities
(d)
Functional capacity—maximum flow: 5.57 unitNote that we show the shortest (cheapest) path in Figure2(b) by solid line and other arcs by dotted line. The result of running CEA using A
1 is shown in Figure 3.The result of running CEA usingA
1.
(a)
Extended capacities
(b)
Functional capacitiesAlso note that the dotted lines in networks Figures3(a) and 3(b) from note 1 to node 2 in the last stage indicate that no increase has taken place on this arc and that no flow passes through this arc. We see that A
3 generates the same set of paths with A
1; that is, (
s
,
1
,
t
) and (
s
,
2
,
t
). Therefore we put A
1 and A
3 in category 1, Ω
1. Also, A
2 and A
4 generate the same paths: (
s
,
1
,
t
), (
s
,
1,2
,
t
), and (
s
,
2
,
t
). Hence we put A
2 and A
4 in category 2, Ω
2. The result of running CAE using A
2 is shown in Figure 4.The result of running CEA usingA
2.
(a)
Extended capacities
(b)
Functional capacitiesWe discard the factorA
5, because this subset of the transmission factors reduces the functional capacity of the arcs originating from source to the extent that these arcs are unable to carry at least v
+
v
0 unit of flow. For more explanation, the result of running CEA using A
5 is shown in Figure 5.The result of running CEA usingA
5.
(a)
Extended capacities
(b)
Functional capacitiesNow, we apply the following steps to compute the network reliability.Step 1.
We choose the subsetA
1 from Ω
1.Step 2.
Letδ
1
1
=
min
⁡
{
u
s
1
f
,
u
1
t
f
} and δ
2
1
=
min
⁡
{
u
s
2
f
,
u
2
t
f
} where u
i
j
f are random variables that have uniform distribution on [
0
,
u
i
j
]; that is, u
s
1
f
~
U
[
0,3
], u
1
t
f
~
U
[
0,5
], u
s
2
f
~
U
[
0,6
], and u
2
t
f
~
U
[
0,6
].Step 3.
Density functions ofδ
1
1 and δ
2
1 are computed as f
δ
1
1
(
δ
1
1
)
=
(
8
/
15
)
-
(
2
/
5
)
δ
1
1 and f
δ
2
1
(
δ
2
1
)
=
(
1
/
3
)
-
(
1
/
18
)
δ
2
1. Also f
δ
1
1
,
δ
2
1
(
δ
1
1
,
δ
2
1
)
=
f
δ
1
1
(
δ
1
1
). f
δ
2
1
(
δ
2
1
)
=
(
(
8
/
15
)
-
(
2
/
5
)
δ
1
1
)
I
(
0,3
)
(
δ
1
1
)
(
(
1
/
3
)
-
(
1
/
18
)
δ
2
1
)
I
(
0,6
)
(
δ
2
1
).Step 4.
Letv
-
1
=
δ
1
1
+
δ
2
1 and
(10)
f
v
-
1
(
v
-
1
)
=
{
8
45
v
-
1
-
1
27
(
v
-
1
)
2
+
1
180
(
v
-
1
)
3
,
0
≤
v
-
1
<
3
,
54
135
-
1
18
v
-
1
,
3
≤
v
-
1
<
6
,
162
135
-
297
135
×
6
v
-
1
+
30
135
×
6
(
v
-
1
)
2
-
1
135
×
6
(
v
-
1
)
3
,
6
≤
v
-
1
<
9
.Step 5.
Now we can calculate the following conditional probability:(11)
P
1
(
v
-
1
>
3.89
∣
α
1
′
=
0.89
,
α
2
′
=
0.9
,
α
3
′
=
0.66
,
P
1
(
v
-
1
>
3.89
∣
∣
α
4
′
=
0.99
≅
1
,
α
5
′
=
0.8
)
=
0.29
.
Also we implement the above steps for A
2 from Ω
2 and get the following probability:
(12)
P
2
(
v
-
2
>
3.89
∣
α
1
′
=
0.89
,
α
2
′
=
0.2
,
α
3
′
=
0.9
,
P
1
(
v
-
1
>
3.89
∣
∣
α
4
′
=
0.8
,
α
5
′
=
0.99
≅
1
)
=
0.37
.
Finally, we can calculate the system reliability:
(13)
p
(
v
-
>
3.89
)
=
0.33
.
Although the reliability network in this example was equal to 0.33, yet this is an effective algorithm which presents a new method for calculating the reliability in networks with continuous components. Although previous algorithms [11–14] also have presented methods for calculating the reliability in the network, but in all of these methods, components, including arcs’ capacity, have been assumed to be discrete, while this assumption is not true for all networks. By presenting this algorithm, we have created an innovation in regard with reliability of networks with continuous capacities. Finally, we would give another example and calculate the reliability of a network in order to elucidate efficiency of these algorithms.


### 5.1. Another Example

In order to elucidate efficiency of CEA, we consider the network flow shown in Figure6. Also we assume v
=
7.25 and v
0
=
5.05. We generate the following pseudo-random numbers and transmission factors:
(14)
(
α
1
,
α
2
,
α
3
,
α
4
,
α
5
,
α
6
,
α
7
,
α
8
,
α
9
,
α
10
)
=
(
0.15,0.32,0.1,0.3,0.11,0.34,0.8,0.7,0.6,0.01
)
,
(
α
1
′
,
α
2
′
,
α
3
′
,
α
4
′
,
α
5
′
,
α
6
′
,
α
7
′
,
α
8
′
,
α
9
′
,
α
10
′
)
=
(
0.85,0.68,0.9,0.7,0.89,0.66,0.2,0.3,0.4,0.99
)
.
We consider several subsets A
j of these numbers that each subset includes m members. Note that A
j has been arranged as A
j
=
(
α
s
1
′
,
α
13
′
,
α
3
t
′
,
α
s
2
′
,
α
12
′
,
α
24
′
,
α
34
′
,
α
4
t
′
). Also, we implement CEA using A
j. In order to classify the result, we place the result of implementing CEA and reliability algorithm in Table 1.Table 1
Final result of example.
r
Category
The subset ofA
j related to Ω
r
The corresponding set of paths withΩ
r
Conditional probability
1
Ω
1
(0.85, 0.9, 0.89, 0.99, 0.3, 0.7, 0.2, 0.68)
(s, 1, 3, t)
0.43
(0.66, 0.68, 0.7, 0.85, 0.3, 0.89, 0.2, 0.9)
(s, 2, 4, t)
2
Ω
2
(0.99, 0.85, 0.89, 0.4, 0.66, 0.7, 0.2, 0.68)(0.85, 0.89, 0.9, 0.4, 0.3, 0.7, 0.2, 0.68)
(s, 1, 3, t)
0.52
(s, 2, 4, t)
(s, 1, 2, 4, t)
3
Ω
3
(0.89, 0.9, 0.4, 0.85, 0.2, 0.68, 0.66, 0.99)(0.89, 0.9, 0.4, 0.7, 0.3, 0.68, 0.66, 0.99)
(s, 1, 3, t)
0.57
(s, 2, 4, t)
(s, 1, 3, 4, t)
4
Ω
4
(0.99, 0.9, 0.66, 0.4, 0.3, 0.7, 0.68, 0.89)
(s, 1, 3, t)
0.64
(s, 2, 4, t)
(s, 1, 2, 4, t)
(s, 1, 3, 4, t)Figure 6
An example of the network flow; arc labels present as(
u
i
j
,
M
i
j
,
c
i
j
).We discard the subset(
0.2,0.9,0.7,0.3,0.66,0.7,0.68,0.4
) or (
0.85,0.9,0.2,0.7,0.8,0.9,0.4,0.3
) because these subsets of transmission factors reduce the functional capacity of the arcs which originate from the source or reach the sink, to the extent that these arcs are unable to carry at least v
+
v
0 unit of flow.Finally we can calculate the system reliability as follows:(15)
p
(
v
-
>
7.25
)
=
0.54
.


## 5.1. Another Example

In order to elucidate efficiency of CEA, we consider the network flow shown in Figure6. Also we assume v
=
7.25 and v
0
=
5.05. We generate the following pseudo-random numbers and transmission factors:
(14)
(
α
1
,
α
2
,
α
3
,
α
4
,
α
5
,
α
6
,
α
7
,
α
8
,
α
9
,
α
10
)
=
(
0.15,0.32,0.1,0.3,0.11,0.34,0.8,0.7,0.6,0.01
)
,
(
α
1
′
,
α
2
′
,
α
3
′
,
α
4
′
,
α
5
′
,
α
6
′
,
α
7
′
,
α
8
′
,
α
9
′
,
α
10
′
)
=
(
0.85,0.68,0.9,0.7,0.89,0.66,0.2,0.3,0.4,0.99
)
.
We consider several subsets A
j of these numbers that each subset includes m members. Note that A
j has been arranged as A
j
=
(
α
s
1
′
,
α
13
′
,
α
3
t
′
,
α
s
2
′
,
α
12
′
,
α
24
′
,
α
34
′
,
α
4
t
′
). Also, we implement CEA using A
j. In order to classify the result, we place the result of implementing CEA and reliability algorithm in Table 1.Table 1
Final result of example.
r
Category
The subset ofA
j related to Ω
r
The corresponding set of paths withΩ
r
Conditional probability
1
Ω
1
(0.85, 0.9, 0.89, 0.99, 0.3, 0.7, 0.2, 0.68)
(s, 1, 3, t)
0.43
(0.66, 0.68, 0.7, 0.85, 0.3, 0.89, 0.2, 0.9)
(s, 2, 4, t)
2
Ω
2
(0.99, 0.85, 0.89, 0.4, 0.66, 0.7, 0.2, 0.68)(0.85, 0.89, 0.9, 0.4, 0.3, 0.7, 0.2, 0.68)
(s, 1, 3, t)
0.52
(s, 2, 4, t)
(s, 1, 2, 4, t)
3
Ω
3
(0.89, 0.9, 0.4, 0.85, 0.2, 0.68, 0.66, 0.99)(0.89, 0.9, 0.4, 0.7, 0.3, 0.68, 0.66, 0.99)
(s, 1, 3, t)
0.57
(s, 2, 4, t)
(s, 1, 3, 4, t)
4
Ω
4
(0.99, 0.9, 0.66, 0.4, 0.3, 0.7, 0.68, 0.89)
(s, 1, 3, t)
0.64
(s, 2, 4, t)
(s, 1, 2, 4, t)
(s, 1, 3, 4, t)Figure 6
An example of the network flow; arc labels present as(
u
i
j
,
M
i
j
,
c
i
j
).We discard the subset(
0.2,0.9,0.7,0.3,0.66,0.7,0.68,0.4
) or (
0.85,0.9,0.2,0.7,0.8,0.9,0.4,0.3
) because these subsets of transmission factors reduce the functional capacity of the arcs which originate from the source or reach the sink, to the extent that these arcs are unable to carry at least v
+
v
0 unit of flow.Finally we can calculate the system reliability as follows:(15)
p
(
v
-
>
7.25
)
=
0.54
.


## 6. Conclusion

In this study, first, we proposed an algorithm to change the arcs capacities so that the maximum flow value exceeds a predefined value and the total cost of change is minimum. In the algorithm (CEA), arc capacities were expanded on the cheapest paths from the source node to the sink node. Then, system reliability was evaluated when the arcs’ functional capacities were stochastic with continuous probability function. There are several different methods in the literature for evaluating of network reliability, when the random components are mostly discrete. In contrast, we studied that system which has continuous random components. For each arc, a functional capacity was defined that had continuous uniform distribution on[
0
,
u
i
j
] and then, the network reliability is calculated.



---

*Source: 876260-2014-08-19.xml*