ZMPST 05 Flow optimization

background image

Flow Optimization

background image

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks

background image

Lecture Outline

Introduction

• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks

background image

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

background image

Flow Optimization Problems

• Bifurcated multicommodity flows

– Linear objective
– Convex objective

• Non-bifurcated multicommodity flows

– Linear objective
– Convex objective

background image

Lecture Outline

• Introduction

Bifurcated Flows with Linear Function

• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks

background image

Bifurcated Flows - Linear

Function (1)

FA (Flow Assignment) problem
Bifurcated unicast flows (e.g., IP protocol)
Link-path formulation
No objective function, allocation problem

background image

Bifurcated Flows - Linear

Function (2)

Given: network topology, link capacity, unicast

demands, candidate paths

Minimize:

Over: bifurcated flows

background image

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

background image

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.

background image

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

background image

Bifurcated Flows - Linear

Function (6)

Given: network topology, link capacity, unicast

demands, candidate paths

Minimize: additional link capacity

Over: bifurcated flows

background image

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.

background image

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

background image

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

background image

Problem Size (2)

Average number of paths for 10-node network and hop limit

background image

Problem Size (3)

Average number of paths for 36-node network and hop limit

background image

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

background image

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)

background image

• 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)

background image

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}

background image

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)

background image

• 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}

background image

• 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}

background image

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)

background image

• 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)

background image

• 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)

background image

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function

Column Generation Technique

• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks

background image

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

)

background image

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

background image

Candidate Paths

Candidate paths P

cand

Allowable paths P

allow

All possible paths P

all

background image

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.

background image

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

background image

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

background image

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

background image

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

background image

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})

background image

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique

Bifurcated Flows with Convex Function

• Flow Deviation Method
• Non-bifurcated Flows
• Concluding Remarks

background image

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

background image

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

background image

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

background image

Linear approximation (1)

background image

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
ra

k

y + b

k

, k = 1,2,…,K.

background image

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function

Flow Deviation Method

• Non-bifurcated Flows
• Concluding Remarks

background image

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)

background image

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

background image

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.

background image

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

background image

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method

Non-bifurcated Flows

• Concluding Remarks

background image

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

background image

Given: network topology, link capacity, unicast

demands, candidate paths

Minimize:

Over: Non-bifurcated flows

Non-bifurcated Flows – Linear Function

(2)

background image

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)

background image

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)

background image

• 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)

background image

FA (Flow Assignment) problem
Non-bifurcated unicast flows
Link-path formulation
• Objective function is network delay

Non-bifurcated Flows–Convex Function

(1)

background image

Given: network topology, link capacity, unicast

demands, candidate paths

Minimize: network delay

Over: Non-bifurcated flows

Non-bifurcated Flows–Convex Function

(2)

background image

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)

background image

• 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)

background image

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

background image

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

background image

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.

background image

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

).

background image

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.

background image

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.

background image

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

background image

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

background image

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

background image

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

background image

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

)

background image

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Column Generation Technique
• Bifurcated Flows with Convex Function
• Flow Deviation Method
• Non-bifurcated Flows

Concluding Remarks

background image

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

background image

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


Document Outline


Wyszukiwarka

Podobne podstrony:
ZMPST 06 Capacity and Flow Optimization
ZMPST 02 Optimization Methods
podrecznik 2 18 03 05
regul praw stan wyjątk 05
ZMPST Wstep
05 Badanie diagnostyczneid 5649 ppt
Podstawy zarządzania wykład rozdział 05
05 Odwzorowanie podstawowych obiektów rysunkowych
05 Instrukcje warunkoweid 5533 ppt
05 K5Z7
05 GEOLOGIA jezior iatr morza
derivation flow equation prof J Kleppe
05 IG 4id 5703 ppt
05 xml domid 5979 ppt
Świecie 14 05 2005
Wykł 05 Ruch drgający

więcej podobnych podstron