Flow Optimization
Flow Optimization
Lecture Outline
• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks
Lecture Outline
• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks
Introduction
• Flow assignment (FA) problems are considered in
an existing network, which is in an operational
phase and augmenting of its resources (links,
capacity) is not possible in a short time perspective
• The motivation is to change the network routing
(flow assignment) in order to improve a selected
network performance metric (e.g., cost, delay,
survivability)
• According to the modeled computer network,
various kinds of multicommodity flows with a range
of constraints are used
Flow Optimization Problems
• Bifurcated multicommodity flows
– Linear objective
– Convex objective
• Non-bifurcated multicommodity flows
– Linear objective
– Convex objective
Lecture Outline
• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks
Bifurcated Flows - Linear
Function (1)
• FA (Flow Assignment) problem
• Bifurcated unicast flows (e.g., IP protocol)
• Link-path formulation
• No objective function, allocation problem
Bifurcated Flows - Linear
Function (2)
Given: network topology, link capacity, unicast
demands, candidate paths
Minimize:
Over: bifurcated flows
Bifurcated Flows - Linear
Function (3)
indices
d = 1,2,…,D
demands
p = 1,2,…,P
d
candidate paths for demand d
e = 1,2,…,Elinks
constants
edp
= 1, if link e belongs to path p realizing
demand d; 0, otherwise
h
d
volume of demand d
c
e
capacity of link e
Bifurcated Flows - Linear
Function (4)
variables
x
dp
flow allocated to path p of demand d
(continuous
non-negative)
constraints
p
x
dp
= h
d
, d = 1,2,…,D
d
p
edp
x
dp
c
e
, e = 1,2,…,E.
Bifurcated Flows - Linear
Function (5)
• This is an allocation problem without any
objective function and the optimization goal is to
find any feasible (satisfying all constraints)
solution
• It is possible that in some case no feasible
solution exists
• The problem is a linear with continuous variables,
so the Simplex method can be used to find
optimal solution
• If the problem is feasible, then there is a solution
x with at most D + E non-zero flows
Bifurcated Flows - Linear
Function (6)
Given: network topology, link capacity, unicast
demands, candidate paths
Minimize: additional link capacity
Over: bifurcated flows
Bifurcated Flows - Linear
Function (7)
variables
x
dp
flow allocated to path p of demand d
(continuous
non-negative)
z
additional link capacity (of unrestricted sign)
objective
minimize z
constraints
p
x
dp
= h
d
, d = 1,2,…,D
d
p
edp
x
dp
c
e
+ z , e = 1,2,…,E.
Bifurcated Flows - Linear
Function (8)
• The problem is always feasible
• If its optimal objective, z, is non-positive then the
corresponding optimal flows x
dp
determine a
feasible solution for the previous allocation
problem
• The problem is a linear and can be solved using
Simplex method
Problem Size (1)
• In the link-path formulation the size of the flow
assignment problem is a function of the number
of candidate paths
• The number of candidate paths increases
exponentially with the network size
• Thus, in the problem we can use only a subset
of candidate paths
• To reduce the number of candidate paths only
shortest path can be used (hop-limit approach)
• Another approach is Column Generation
Technique using Lagrangian relaxation
Problem Size (2)
Average number of paths for 10-node network and hop limit
Problem Size (3)
Average number of paths for 36-node network and hop limit
Example (1)
1
2
3
4
Szczecin-Gdańsk
<1,2> c=3 Mbps
<2,1> c=3 Mbps
Szczecin-Wrocław
<1,3> c=5 Mbps
<3,1> c=5 Mbps
Gdańsk-Wrocław
<2,3> c=2 Mbps
<3,2> c=2 Mbps
Gdańsk-
Warszawa
<2,4> c=5 Mbps
<4,2> c=5 Mbps
Wrocław-
Warszawa
<3,4> c=4 Mbps
<4,3> c=4 Mbps
3
5
2
5
4
Demands (node pairs):
• Szczecin (1) – Warszawa (4) (demand value x)
• Gdańsk (2) – Wrocław (3) (demand value y)
• Wrocław (3) – Warszawa (4) (demand value v)
1
2
3
4
3
5
2
5
4
Example (2)
• Link-path notation
Candidate paths
• x1={1,2,4}; x2={1,3,4}; x3={1,2,3,4};
x4={1,3,2,4}
• y1={2,3}; y2={2,1,3}; y3={2,4,3}
• v1={3,4}; v2={3,2,4}; v3={3,1,2,4}
Constraints
• x: x1 + x2 + x3 +x4 = x
• y: y1 + y2 + y3 = y
• v: v1 + v2 + v3 = v
1
2
3
4
3
5
2
5
4
Example (3)
Capacity constraints
• c12: x1 + x3 + v3 - z <= 3
• c21: y2 - z <= 3
• c13: x2 + x4 + y2 - z <= 5
• c31: v3 - z <= 5
• c23: x3 + y1 - z <= 2
• c32: x4 + v2 - z <= 2
• c24: x1 + x4 + y3 + v2 + v3 - z <= 5
• c42: - z <= 5
• c34: x2 + x3 + v1 - z <= 4
• c43: y3 - z <= 4
1
2
3
4
3
5
2
5
4
Example (4)
x1={1,2,4}; x2={1,3,4};
x3={1,2,3,4}; x4={1,3,2,4}
y1={2,3); y2={2,1,3};
y3={2,4,3}
v1={3,4}; v2={3,2,4};
v3={3,1,2,4}
Variable constraints
• 0 <= x1 <= x
• 0 <= x2 <= x
• 0 <= x3 <= x
• 0 <= x4 <= x
• 0 <= y1 <= y
• 0 <= y2 <= y
• 0 <= y3 <= y
• 0 <= v1 <= v
• 0 <= v2 <= v
• 0 <= v3 <= v
• -inf <= z <= +inf
1
2
3
4
3
5
2
5
4
Example (5)
• Bifurcated flows
• Demand value: x = 3 y = 3 v = 3
Solution
• x1 = 2 x2 = 1 x3 = 0 x4 = 0
• y1 = 1 y2 = 2 y3 = 0
• v1 = 2 v2 = 1 v3 = 0
• z = -1
• Residual capacity r12=3-2=1 r21=3-2=1
r13=5-3=2 r31=5-0=5 r23=2-0=2 r32=2-1=1
r24=5-3=2 r42=5-0=5 r34=4-2=2 r43=4-0=4
1
2
3
4
3
5
2
5
4
Example (6)
x1={1,2,4}; x2={1,3,4};
x3={1,2,3,4) ; x4={1,3,2,4}
y1={2,3}; y2={2,1,3};
y3={2,4,3}
v1={3,4}; v2={3,2,4};
v3={3,1,2,4}
• Non-bifurcated flows (binary
variables)
• Demand value: x = 3 y = 3 v
= 3
Solution
• x1 = 1 x2 = 0 x3 = 0 x4 = 0
• y1 = 0 y2 = 1 y3 = 0
• v1 = 1 v2 = 0 v3 = 0
• z = 0
• Residual capacity r12=3-3=0
r21=3-3=0
r13=5-3=2 r31=5-0=5 r23=2-0=2
r32=2-0=2
r24=5-3=2 r42=5-0=5 r34=4-3=0
r43=4-0=4
1
2
3
4
3
5
2
5
4
Example (7)
x1={1,2,4}; x2={1,3,4};
x3={1,2,3,4}; x4={1,3,2,4}
y1={2,3}; y2={2,1,3};
y3={2,4,3}
v1={3,4}; v2={3,2,4};
v3={3,1,2,4}
Node-link notation
• 1_x: x12 + x13 – x21 – x31 = x
• 2_x: x21 + x23 + x24 - x12 – x32 – x42 = 0
• 3_x: x31 + x32 + x34 - x13 - x23 - x43 = 0
• 4_x: x42 + x43 – x24 – x34 = -x
1
2
3
4
3
5
2
5
4
Example (8)
• 1_y: y12 + y13 – y21 – y31 = 0
• 2_y: y21 + y23 + y24 - y12 – y32 – y42 = y
• 3_y: y31 + y32 + y34 - y13 - y23 - y43 = -y
• 4_y: y42 + y43 – y24 – y34 = 0
• 1_v: v12 + v13 – v21 – v31 = 0
• 2_v: v21 + v23 + v24 - v12 – v32 – v42 = 0
• 3_v: v31 + v32 + v34 - v13 - v23 - v43 = v
• 4_v: v42 + v43 – v24 – v34 = -v
1
2
3
4
3
5
2
5
4
Example (9)
• c12: x12 + y12 + v12 - z <= 3
• c21: x21 + y21 + v21 - z <= 3
• c13: x13 + y13 + v13 - z <= 5
• c31: x31 + y31 + v31 - z <= 5
• c23: x23 + y23 + v23 - z <= 2
• c32: x32 + y32 + v32 - z <= 2
• c24: x24 + y24 + v24 - z <= 5
• c42: x42 + y42 + v42 - z <= 5
• c34: x34 + y34 + v34 - z <= 4
• c43: x43 + y43 + v43 - z <= 4
1
2
3
4
3
5
2
5
4
Example (10)
Lecture Outline
• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks
Column Generation
Technique (1)
• The node-link formulation takes (indirectly) into
account all possible paths in the network (the
set of all network paths is denoted by P
all
)
• The link-path formulation uses a predefined lists
of candidate paths (the set of candidate paths
is denoted by P
cand
)
• The allowable paths that can appear on the
candidate lists are restricted by some
requirement, e.g., hop limit (the set of allowable
paths is denoted by P
allow
)
Column Generation
Technique (2)
• The size of link-path formulation depends on the
size of candidate paths set
• If only a limited set of candidate paths is
considered, the obtained solution has no
optimality guarantee
• Column generation is a technique that
generates iteratively sets of candidate paths
so that the current problem remains of relatively
small size reasonable but after some interations a
global optimal solution can be obtained
Candidate Paths
Candidate paths P
cand
Allowable paths P
allow
All possible paths P
all
Formulation (1)
variables
x
dp
flow allocated to path p of demand d, x=(x
dp
:
d =1,2,...,D, p =1,2,...,P
d
)
z
e
variable measuring overload of link e, z=(z
e
:
e =
1,2,...,E)
objective
minimize
e
z
e
constraints
p
x
dp
= h
d
, d = 1,2,…,D
d
p
edp
x
dp
c
e
+ z
e
, e = 1,2,…,E
x 0, z 0.
Formulation (2)
minimize
e
z
e
h
d
–
p
x
dp
= 0, d = 1,2,…,D (
d
)
d
p
edp
x
dp
– c
e
– z
e
0, e = 1,2,…,E (
e
)
Lagrangian function L(x,z;
,
) is as follows
e
z
e
+
d
d
(h
d
p
x
dp
) +
e
e
(
d
p
edp
x
dp
c
e
z
e
) =
d
d
h
d
e
e
c
e
+
e
(1
e
)z
e
+
d
p
(
e
edp
e
d
) x
dp
Formulation (3)
d
d
h
d
e
e
c
e
+
e
(1
e
)z
e
+
d
p
(
e
edp
e
d
) x
dp
Optimality conditions for any saddle point (x,z;
,
)
0
e
1 for e = 1,2,…,E
d
p
(
e
edp
x
dp
) < c
e
e
= 0 for e = 1,2,…,E
z
e
> 0
e
= 1
for e = 1,2,…,E
d
= min {
e
edp
e
: p = 1,2,…,P
d
}
for d = 1,2,…,D
e
edp
e
>
d
x
dp
= 0 for d = 1,2,…,D, p = 1,2,…,P
d
Formulation (4)
If the optimal dual variable (multiplier) π
e
is treated
as the weight (metric, dual cost) of link e, then
above properties have the following
interpretation:
• The weights are real numbers from interval [0,1]
• The quantity
e
edp
e
is the length of path p of
demand d according to the weight system
e
• If link e is not saturated (i.e.,
d
p
(
e
edp
x
dp
) < c
e
)
then
e
= 0
• 0 <
e
< 1 implies that link e is saturated but not
overloaded
Formulation (5)
• z
e
> 0 means that link e is overloaded and implies
that
e
= 1
• For each demand d,
d
denotes the length of the
shortest candidate path
• For the current list of allowable paths the non-
zero primal optimal flows can be assigned only to
the shortest paths from the list,i.e., x
dp
> 0
implies
e
edp
e
=
d
Proposition
• Let (x,z;
,
) be a saddle point of restricted problem
• Let P
d
P
allow
be the shortest path for demand d
(among all allowable paths) according to optimal
multipliers
, and let
d
(
) = |P
d
| denote the
corresponding length of P
d
• If for all d
d
(
) =
d
then the primal solution (x, z) is
optimal in the wider sense
• Otherwise, if for some demand d a path P
d
with
d
(
) <
d
does exist, then the primal solution (x, z) can be
possibly (but not necessarily) improved by adding
path P
d
to the current routing list of the paths
allowable for d (P
cand
= P
cand
∪ {Pd})
Lecture Outline
• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks
Delay Function (1)
• The network delay function was defined by
Kleinrock in 1964
where is the network throughput, f(x,y) denotes
the flow on link (x,y) and c(x,y) is the capacity of
link (x,y)
• The Kleinrock function is convex and
differentiable
A
y
x,
y
x,
f
y
x,
c
y
x,
f
γ
1
T
Delay Function (2)
• The Independence Assumption: Each time
that a message is received at a node within the
net, a new length is chosen for this message
independently from an exponential distribution
• Each link behaves as independent M/M/1 queue
system regardless of traffic interaction of various
demands
• Store-and-forward network is considered
Optimization of Convex
Function
• Direct methods, e.g., FD (Flow Deviation), GP
(Gradient Projection), EF (Extremal Flows)
• Other heuristics
• Linear approximation of the convex function
using a set of linear functions and next the
application of linear programming algorithms,
e.g., Simplex
Linear approximation (1)
Linear approximation (2)
Let a set of function
f
k
(z) = a
k
z + b
k
, s
k-1
z < s
k
, k = 1,2,…,K
be a linear approximation of a convex function f(z)
The considered problem of the convex function
optimization can be substituted by a following
problem
objective
minimize r = f(y)
constraints
r a
k
y + b
k
, k = 1,2,…,K.
Lecture Outline
• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks
Algorithm FD (1)
• Let f = [f
1
,f
2
,…,f
E
] be a vector of feasible bifurcated
multicommodity flows in all links e = 1,2,…,E
• Let us assume that P(f) is a convex objective function
• FD operator which maps a flow f into another flow
FD(v,
) f = (1 –
)f +
v
• where v is a shortest route flow under metric l
e
= P /
f
e
, which is partial derivative of function P
is a step size that minimizes P[(1 –
)f +
v] (0
1)
Algorithm FD (2)
Phase 1:
Step 0. With RE
0
= 1, let f
0
be the shortest flow
computed
at f = 0. Let n = 0.
Step 1. Let
If
n
/ RE
n
< 1 , let f
0
= f
n
/ RE
n
and go to Phase 2.
Otherwise, let RE
n+1
= RE
n
(1 –
|1 –
n
|)/
n
, where
is a proper tolerance,
0 <
< 1.
Let g
n+1
= f
n
(RE
n+1
/ RE
n
). Go to 2.
e
n
e
e
n
c
f
σ
E
,...,
2
,
1
max
Algorithm FD (3)
Step 2. Let f
n+1
= FD g
n+1
Step 3. If n = 0, go to 5.
Step 4. If |
e
l
e
(v
e
– g
en+1
)| <
and |RE
n+1
– RE
n
| <
where
and
are proper positive tolerances, v is the
shortest route computed at g
n+1
, stop: the problem
is infeasible within tolerances
and
. Otherwise,
and go to 5.
Step 5. Let n = n + 1 and go to 1.
Algorithm FD (4)
Phase 2:
Step 0. Let n = 0
Step 1. f
n+1
= FD f
n
Step 2. If |
e
l
e
(v
e
– f
en
)| <
where
is a proper positive tolerances, stop: f
n
is
optimal within tolerance
. Otherwise, let n = n + 1
and go to 1
Lecture Outline
• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks
Non-bifurcated Flows – Linear Function
(1)
• FA (Flow Assignment) problem
• Non-bifurcated unicast flows (e.g., MPLS
protocol)
• Link-path formulation
• No objective function, allocation problem
Given: network topology, link capacity, unicast
demands, candidate paths
Minimize:
Over: Non-bifurcated flows
Non-bifurcated Flows – Linear Function
(2)
indices
d = 1,2,…,D
demands
p = 1,2,…,P
d
candidate paths for demand d
e = 1,2,…,Elinks
constants
edp
= 1, if link e belongs to path p realizing
demand d; 0, otherwise
h
d
volume of demand d
c
e
capacity of link e
Non-bifurcated Flows – Linear Function
(3)
variables
x
dp
= 1, if path p is used to realize demand d; 0,
otherwise (binary)
constraints
p
x
dp
= 1, d = 1,2,…,D
d
p
edp
x
dp
h
d
c
e
, e = 1,2,…,E.
Non-bifurcated Flows – Linear Function
(4)
• This is an integer and NP-hard problem without
any objective
• It is possible that in some case no feasible
solution exists
• The problem can be solved in optimal way using
branch and bound or branch and cut methods
• The following cuts can be used:
– Mixed-Integer Rounding
– Cover Inequality
• However, only for relatively small networks (10-20
nodes) the optimal solution can found in reasonable
time
Non-bifurcated Flows – Linear Function
(5)
• FA (Flow Assignment) problem
• Non-bifurcated unicast flows
• Link-path formulation
• Objective function is network delay
Non-bifurcated Flows–Convex Function
(1)
Given: network topology, link capacity, unicast
demands, candidate paths
Minimize: network delay
Over: Non-bifurcated flows
Non-bifurcated Flows–Convex Function
(2)
variables
x
dp
= 1, if path p is used to realize demand d; 0,
otherwise (binary)
f
e
flow on link e (non-negative, continuous)
objective
minimize F =
e
f
e
/ (c
e
– f
e
)
constraints
p
x
dp
= 1, d = 1,2,…,D
f
e
=
d
p
edp
x
dp
h
d
, e = 1,2,…,E
f
e
c
e
, e = 1,2,…,E.
Non-bifurcated Flows–Convex Function
(3)
• Direct methods, e.g., FD (Flow Deviation)
• Other heuristics, e.g., evolutionary algorithm,
ant algorithm
• Linear approximiation of the objective function
and next the application of algorithms developed
for linear problems
• Branch and bound or branch and cut methods
Non-bifurcated Flows–Convex Function
(4)
Algorithm NBFD (1)
• Algorithm NBFD (Non-Bifurcated FD) is based on
the FD algorithm proposed by Fratta et al.
• To find a feasible, initial solution algorithm
similar to Phase 1 of FD can be used
• Selection X is a set of all variables x
dp
that are
equal to 1. X determines the unique set of
currently selected paths
• DEL(H) denotes the delay function for a feasible
selection H
Algorithm NBFD (2)
• f
e
=
d
p
edp
x
dp
h
d
denotes the flow on link e = 1,2,
…,E
• l
e
= c
e
/ (c
e
– f
e
)
2
is a link metric calculated as
partial derivative of the delay function
• Operator first(B) returns the index of the first
demand in set B. F and H are selections
Algorithm NBFD (3)
Step 1. Find feasible selection X
1
. Set r = 1, and go to
step 2.
Step 2. Compute SR(X
r
), defined as the set of shortest
routes under metric l
e
for each demand.
Step 3. Set H = X
r
and let K be a set of all demands.
a) Find d = first(K). Set F = (H – {x
dk
}) {x
di
}, where
x
dk
H and x
di
SR(X
r
).
b) If F is a feasible selection and DEL(F) < DEL(H), let
H = F.
c) Set K = K – {d}. If K = , go to 4. Otherwise, go to 3a.
Step 4. If H = X
r
, stop. The algorithm cannot improve the
solution any further. Otherwise, let X
r+1
= H, r = r + 1
and go to 2.
Branch and Bound
Algorithm (1)
Let U
r
and T
r
be sets of variables constantly and
momentarily fixed in the r-th iteration, respectively
F* denotes the best solution, LB
r
a lower bound of X
r
Let X
1
is the initial solution. Let U
1
= , T
1
= ,
F
*
= , r = 1
Step 1. If for at least one link e, the fixed flow
exceeds the capacity, go to 5. Otherwise, find the
lower bound LB
r
.
If LB
r
F
*
go to 5. Otherwise, go to 2.
Step 2. If there is at least one link e that f
e
> c
e
, go to
4. Otherwise, find F(X
r
). If F(X
r
) < F* , then set F
*
=
F(X
r
).
Branch and Bound
Algorithm (2)
Step 3. If there are not any variables for the choice
operation go to 5. Otherwise, choose the normal
variable x
dk
and a reverse variable x
di
. Next
generate selection X
s
= (X
r
– {x
dk
}) {x
di
},
U
s
= U
r
{x
di
}, T
s
= T
r
. Go to 1.
Step 4. If there are not any variables for the choice
operation go to 5. Otherwise, choose the normal
variable x
dk
and a reverse variable x
di
. Next
generate selection X
s
= (X
r
– {x
dk
}) {x
di
},
U
s
= U
r
{x
di
}, T
s
= T
r
. Go to 1.
Branch and Bound
Algorithm (3)
Step 5. Backtrack to the predecessor X
p
of the
selection X
r
. If X
r
has no predecessor, then stop the
algorithm. The selection X
*
associated with the
current solution F
*
is optimal.
Otherwise, update the current selection X
p
in the
following way. If X
r
has been generated by the
reverse variable x
di
, set
T
p
= T
p
{x
di
}. If the backtracking is performed for
(P
d
– 1) time by a reverse variable of the normal
variable x
dk
, then
U
p
= U
p
{x
dk
}, T
p
= T
p
– {x
dp
: p = 1,2,…,P
d
}. Go to
1.
Example (1)
• 3 demands d = 1,2,3
• 3 candidate paths for each demand p = 1,2,3
• Decision variables x
dp
:
– For demand d = 1: x
11
,x
12
,x
13
– For demand d = 2: x
21
,x
22
,x
23
– For demand d = 3: x
31
,x
32
,x
33
Example (2)
X
1
={x
11
,x
21
,x
31
}
X
2
={x
11
,x
21
,x
32
}
X
3
={x
11
,x
22
,x
32
}
X
4
={x
12
,x
22
,x
32
} X
5
={x
13
,x
22
,x
32
}
X
6
={x
11
,x
23
,x
32
}
X
7
={x
11
,x
21
,x
33
}
Choice
x
31
x
32
U
2
= {x
32
}
T
2
= {}
Choice
x
21
x
22
U
3
=
{x
32
,x
22
}
T
3
= {}
Choice
x
11
x
12
U
4
=
{x
32
,x
22
,x
12
}
T
4
= {}
Backtrack
x
11
x
12
U
3
= {x
32
,x
22
}
T
3
= {x
12
}
Choice
x
11
x
13
U
5
=
{x
32
,x
22
,x
13
}
T
5
= {x
12
}
Backtrack
x
11
x
13
U
3
=
{x
32
,x
22
,x
11
}
T
3
= {}
Backtrack
x
21
x
22
U
2
= {x
32
}
T
2
= {x
22
}
Choice
x
21
x
23
U
6
= {x
32
,x
23
}
T
6
= {x
22
}
Lower bound
x
21
x
23
U
2
= {x
32
,x
21
}
T
2
= {}
Lower bound
x
31
x
32
U
1
= {}
T
1
= {x
32
}
Choice
x
31
x
33
U
7
= {x
33
}
T
7
= {}
Lower bound
x
31
x
33
U
1
= {x
31
}
T
1
= {}
Lower bound
Stop
Evolutionary Algorithm (1)
• The chromosome has as many alleles as
demands the network
• Each allele represents the number of
selected path
(variables x
dp
)
• For example, the following chromosome cr=213
means that demand with index 1 uses path 2,
demand 2 uses path 1, and finally demand 3 uses
path 3
• Only limited set of candidate paths is
considered
Evolutionary Algorithm (2)
• Crossover and mutation operators are modified
in such way, that applying those operators results
a feasible solution
• It means that allele does not exceed the
number of possible path for the considered
demand
• The problem for evolutionary algorithm should be
formulated in such a way, that the fitness
function returns non-negative value that is to be
maximized and the problem can not have any
constraints
Evolutionary Algorithm (2)
• In the considered problem we use penalty
method to include capacity constraints into the
objective function
• We define the function of a chromosome cr in
the population as follows
F(cr)
penalty
= F(cr) + PN
e
h(cr,e)
• where (cr,e) is a the capacity constraint
exceeding for chromosome cr and link link e
• Additionally, we can add a scaling factor M, to
promote the best individuals in the population
and the fitness is as follows
fitness(cr) = M(F
max
F(cr)
penalty
)
Lecture Outline
• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks
Concluding Remarks
• Bifurcated multicommodity flows problems with
linear objective function can be solved by
standard optimization methods, e.g., Simplex
• Non-bifurcated multicommodity flows problems
belong to the class of MIP problems and to obtain
optimal solution branch and bound or branch
and cut methods must be applied, however only
for small networks
• For larger networks, computational
inteligence methods are more useful
• Convex function problems can be attacked by
linear approximation or classical approaches like
Lagrangian relaxation
Further Reading
• M. Pióro, D. Medhi, Routing, Flow, and Capacity Design in Communication and
Computer Networks, Morgan Kaufman Publishers 2004
• A. Kasprzak, Rozległe sieci komputerowe z komutacją pakietów, Oficyna
Wydawnicza Politechniki Wrocławskiej, Wrocław 1997 (in Polish)
• L. Fratta, M Gerla, L. Kleinrock, The Flow Deviation Method: An Approach to
Store-and-Forward Communication Network Design, Networks, Vol. 3, 1973, s.
97–133
• B. Gavish, S. Huntler, An Algorithm for Optimal Route Selection in SNA
Networks, IEEE Trans. Commun., Vol. COM-31, No. 10, 1983, s. 1154-1160
• K. Walkowiak, Genetic approach to virtual paths assignment in survivable ATM
networks, Proc. of 7th International Conference on Soft Computing MENDEL,
Brno, 2001, s. 13-18.
• K. Walkowiak, Ant algorithms for design of computer networks, Proc. of 7th
International Conference on Soft Computing MENDEL, Brno, 2001, s. 149-154.
• M. Przewoźniczek, K. Walkowiak, Quasi-hierarchical Evolution Algorithm for
Flow Assignment in Survivable Connection-Oriented Networks, International
Journal of Applied Mathematics and Computer Science, No. 4, Vol. 16, 2006, s.
101-116