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