Capacity and Flow

Optimization

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Routing Restrictions
• Link Modularity
• Example
• Convex Function
• Concluding Remarks

Lecture Outline

• Introduction

• Bifurcated Flows with Linear Function
• Routing Restrictions
• Link Modularity
• Example
• Convex Function
• Concluding Remarks

Introduction (1)

• Network design problems called also capacity

and flow assignment (CFA) problems are one of

the most frequently encountered problems in

network optimization

• They are used in the case when a new network is

designed or an existing network is

incremented

• The objective is usually network cost defined as

the cost of network links and other network

performance metrics (e.g., delay, survivability)

• According to the modeled computer network,

various kinds of multicommodity flows with a range

of constraints are used

CFA Problems

• Bifurcated multicommodity flows

– Linear objective
– Convex objective
– Modularity

• Non-bifurcated multicommodity flows

– Linear objective
– Convex objective
– Modularity

Lecture Outline

• Introduction

• Bifurcated Flows with Linear Function

• Routing Restrictions
• Link Modularity
• Example
• Convex Function
• Concluding Remarks

Bifurcated Flows - Linear Function

(1)

• CFA (Capacity and Flow Assignment) problem
• Bifurcated unicast flows (e.g., IP protocol)
• Objective is to minimize network cost function
• Both link-path and node-link formulations can

be used

Bifurcated Flows - Linear Function

(2)

Given: network topology, unicast demands,

candidate paths

Minimize: network cost (linear)

Over: bifurcated flows (routing), link capacity

Link-Path Formulation (1)

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



e

unit (marginal) cost of link e

Link-Path Formulation (2)

variables
x

dp

flow allocated to path p of demand d

(continuous

non-negative)

y

e

capacity of link e (continuous non-negative)

objective
minimize F = 

e



e

y

e

constraints


p

x

dp

= h

d

, d = 1,2,…,D



d



p



edp

x

dp

 y

e

, e = 1,2,…,E.

Shortest Path Allocation Rule

• Since the link capacity variable y

e

is continuous,

for optimal solution the capacity constraint is
binding, i.e., the link flow must be equal to the link
capacities (otherwise, the objective includes cost
of an unused capacity)

F = 

e



e

y

e

= 

e



e



d



p



edp

x

dp

= 

d



p

x

dp



e



edp



e

= 

d



p



dp

x

dp

• For each demand, allocate its entire demand

volume to its shortest path, with respect to links
unit costs and candidate path. If there is more
than one shortest path for a demand then the
demand volume can be split among the shortest
paths in an arbitrary way

Decoupled Link-Path

Formulation

variables
x

dp

flow allocated to path p of demand d

(continuous
non-negative)

objective
minimize F = 

d



p



dp

x

dp

constraints


p

x

dp

= h

d

, d = 1,2,…,D.

The solution yields shortest path algorithm applied for

each demand

Node-Link Formulation (1)

indices
d = 1,2,…,D

demands

e = 1,2,…,Elinks
v = 1,2,…,Vnodes
constants
a

ev

= 1, if link e originates at node v; 0, otherwise

b

ev

= 1, if link e terminates in node v; 0,

otherwise

h

d

volume of demand d



e

unit (marginal) cost of link e

Node-Link Formulation (2)

constants
s

d

source node of demand d

t

d

destination node of demand d

variables
x

ed

flow of demand d sent on link e (continuous

non-negative)

y

e

capacity of link e (continuous non-negative)

Node-Link Formulation (3)

objective
minimize F = 

e



e

y

e

constraints


e

 a

ev

x

ed

 – 

e

 b

ev

x

ed

 =  h

d

,   if v = s

d

v = 1,2,…,V

d = 1,2,…,D



e

 a

ev

x

ed

 – 

e

 b

ev

x

ed

 = –h

d

,   if v = t

d

v = 1,2,…,V

d = 1,2,…,D



e

 a

ev

x

ed

 – 

e

 b

ev

x

ed

 = 0,  if v  s

d

,t

d

v = 1,2,…,V

d = 1,2,…,D



d

x

ed

 y

e

, e = 1,2,…,E.

Formulation Comparison (1)

• V – number of nodes, P – average number of

candidate paths, k – average number of adjacent
nodes, V



(V) – number of demand origin nodes

Formulation

Number of

variables

Number of constraints

Link-path

PxV



(V



1 )+0.5kxV

=O(V

2

)

PxV



(V



1 )+0.5kxV

=O(V

2

)

Node-link

0.5kxVxV



(V



1 )x

=O(V

3

)

VxV



(V



1 )+0.5kxV

=O(V

3

)

Example (1)

• The network consits of 4 nodes and 5 links
• There are 3 demands between nodes 1-2, 1-3, 2-3
• Link-path notation

1

3

4

2

e=1

e=2

e=5

e=4

e=3

Example (2)

1

3

4

2

Link

e = 1

e = 2

e = 3

e = 4

e = 5

Node

2-3

2-4

3-4

1-4

1-3

Cost



1

= 2



2

= 1



3

= 1



4

= 3



5

= 1

e=1

e=2

e=5

e=4

e=3

Example (3)

Demand

1

2

3

Nodes

1-2

1-3

2-3

Volume

h

1

= 15

h

2

= 20

h

3

= 10

Path

P

11

={2,4}

P

21

={5}

P

31

={1}

Pat

P

22

={3,4}

P

32

={2,3}

1

3

4

2

e=1

e=2

e=5

e=4

e=3

Example (4)

e=1

e=2

e=5

e=4

e=3

link/path P

11

={2,4

}

P

21

={5} P

22

={3,4

}

P

31

={1} P

32

={2,3

}

e = 1

0

0

0

1

0

e = 2

1

0

0

0

1

e = 3

0

0

1

0

1

e = 4

1

0

1

0

0

e = 5

0

1

0

0

0

1

4

2

3

Example (5)

minimize
F = 2y

1

+ y

2

+ y

3

+ 3y

4

+ y

5

constraints
x

11

+ x

21

+ x

22

+ x

31

+ x

32

= 15 (h

1

)

x

11

+

x

21

+ x

22

+ x

31

+ x

32

= 20 (h

2

)

x

11

+ x

21

+ x

22

+

x

31

+ x

32

= 10 (h

3

)

x

11

+ x

21

+ x

22

+

x

31

+ x

32

 y

1

x

11

+ x

21

+ x

22

+ x

31

+ x

32

 y

2

x

11

+ x

21

+

x

22

+ x

31

+ x

32

 y

3

x

11

+ x

21

+ x

22

+ x

31

+ x

32

 y

4

x

11

+

x

21

+ x

22

+ x

31

+ x

32

 y

5

x

11

, x

21

, x

22

, x

31

,

x

32

 0,

y

1

, y

2

, y

3

, y

4

, y

5

 0

e

x

11

x

21

x

22

x

31

x

32

1

0

0

0

1

0

2

1

0

0

0

1

3

0

0

1

0

1

4

1

0

1

0

0

5

0

1

0

0

0

Incremental Network Design

(1)

• CFA (Capacity and Flow Assignment) network

extension problem

• Bifurcated unicast flows (e.g., IP protocol)
• Objective is to minimize network cost of

additional capacity added to the network

• Link-path formulation

Incremental Network Design

(2)

Given: network topology, unicast demands,

candidate paths, link capacity

Minimize: network extension cost (linear)

Over: bifurcated flows (routing), additional link

capacity

Incremental Network Design

(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



e

unit (marginal) cost of link e

Incremental Network Design

(3)

variables
x

dp

flow allocated to path p of demand d

(continuous

non-negative)

y

e

additional capacity of link e (continuous non-

negative)

objective
minimize F = 

e



e

y

e

constraints


p

x

dp

= h

d

, d = 1,2,…,D



d



p



edp

x

dp

 c

e

+ y

e

, e = 1,2,…,E.

Optimization

• Network design problems with linear cost and

bifurcated flowscan be solve by the Simplex
method

• For larger networks heuristics can be applied

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function

• Routing Restrictions

• Link Modularity
• Example
• Convex Function
• Concluding Remarks

Path Diversity (1)

• CFA (Capacity and Flow Assignment) problem
• Bifurcated unicast flows
• Objective is to minimize network cost function
• Link-path formulation
• Path diversity requirement to force splitting

demand volumes into more than one path

Path Diversity (2)

Given: network topology, unicast demands,

candidate paths, diversity factor for each demand

Minimize: network cost (linear)

Over: bifurcated flows (routing), link capacity

Path Diversity (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



e

unit (marginal) cost of link e

n

d

diversity factor for demand d

Path Diversity (3)

variables
x

dp

flow allocated to path p of demand d (continuous

non-negative)

y

e

capacity of link e (continuous non-negative)

objective
minimize F = 

e



e

y

e

constraints


p

x

dp

= h

d

, d = 1,2,…,D



d



p



edp

x

dp

 y

e

, e = 1,2,…,E

x

dp

≤ h

d

/n

d

, d= 1,2,...,D p = 1,2, ...,P

d

.

Single Path Routing (1)

• CFA (Capacity and Flow Assignment) problem
• Objective is to minimize network cost function
• Link-path formulation
• Single path routing, i.e., Non-bifurcated flows

Single Path Routing (2)

Given: network topology, unicast demands,

candidate paths

Minimize: network cost (linear)

Over: Non-bifurcated flows (routing), link capacity

Single Path Routing (3)

variables (additional)
u

dp

binary variable corresponding to the flow

allocated

to path p of demand d

objective
minimize F = 

e



e

y

e

constraints
x

dp

= h

d

u

dp

, d = 1,2,…,D p = 1,2,…,P

d



p

u

dp

= 1, d = 1,2,…,D



d



p



edp

x

dp

 y

e

, e = 1,2,…,E.

Optimization

• With continuous capacity the problem can be

solved by Shortest Path Allocation Rule

• With integer capacity the the single path problem

is linear, integer (binary) and NP-complete

(equivalent to non-bifurcated flow problem)

• To find optimal solution branch-and-bound or

branch-and-cut algorithm must be constructed

• The solution process can be divided into two

phases: capacity assignment and flow

assignment, i.e., Top-Down approach

• Heuristics can be used, e.g., Flow Deviation,

evolutionary algorithm, etc.

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Routing Restrictions

• Link Modularity

• Example
• Convex Function
• Concluding Remarks

Link Modularity (1)

• Link modularity is a common feature in

communications networks, i.e., link capacity must
be a multiple of particular module of capacity

• Link modularity follows from technological

constraints, e.g., SDH/SONET, WDM

• To include link modularity condition in the model,

the link capacity variable must be integer

Link Modularity (2)

Link load

Link cost

M

2M

3M

4M

5M

Continuous
link capacity

Modular
link capacity

Modular Links Problem (1)

• CFA (Capacity and Flow Assignment) problem
• Bifurcated unicast flows (e.g., IP protocol)
• Objective is to minimize network cost function
• Modular link modeling
• Link-path formulation

Modular Links Problem (2)

Given: network topology, unicast demands,

candidate paths, link modules

Minimize: network cost (linear)

Over: bifurcated flows (routing), link capacity

Modular Links Problem (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



e

cost of one capacity module on link e

M

size of the link capacity module

Modular Links Problem (4)

variables
x

dp

flow allocated to path p of demand d

(continuous
non-negative)

y

e

capacity of link e as the number of modules (non-
negative integer)

objective
minimize F = 

e



e

y

e

constraints


p

x

dp

= h

d

, d = 1,2,…,D



d



p



edp

x

dp

 My

e

, e = 1,2,…,E.

Optimization

• The modular links problem is linear, integer and

NP-complete

• To find optimal solution branch-and-bound or

branch-and-cut algorithm must be constructed

• The solution process can be divided into two

phases: capacity assignment and flow
assignment, i.e., Top-Down approach

• Heuristics can be used, e.g., Flow Deviation,

evolutionary algorithm, etc.

Candidate Link Capacity (1)

• In some cases the telecoms propose to customers

a set of possible candidate links, e.g., DSL links
in the Internet access

• Each candidate link has a fixed capacity
• The customer is to select one of the candidate

links

• Usually, the cost of a capacity unit (e.g., 1

Mbps) decrases with the increase of the
candidate link capacity, i.e., the cost function is
concave

Candidate Link Capacity (2)

Link load

Link cost

M

2M

3M

4M

5M

Candidate
link capacity

Candidate Links Problem (1)

• CFA (Capacity and Flow Assignment) problem
• Bifurcated unicast flows (e.g., IP protocol)
• Objective is to minimize network cost function
• Candidate link modeling
• Link-path formulation

Candidate Links Problem (2)

Given: network topology, unicast demands,

candidate paths, candidate links

Minimize: network cost (linear)

Over: bifurcated flows (routing), link capacity

Candidate Links Problem (3)

indices (additional)
k = 1,2,…,K

e

candidate link types for link e

constants (additional)



ek

cost of candidate link type k on link e

c

ek

capacity of candidate link type k on link e

variables
x

dp

flow allocated to path p of demand d

(continuous
non-negative)

y

ek

= 1, if link type k is selected for link e; 0,

otherwise

Candidate Links Problem (4)

objective
minimize F = 

e



k



ek

y

ek

constraints


p

x

dp

= h

d

, d = 1,2,…,D



k

y

ek

= 1, e = 1,2,…,E



d



p



edp

x

dp

 

k

c

ek

y

ek

, e = 1,2,…,E.

Optimization

• The modular links problem is linear, integer

(binary) and NP-complete

• To find optimal solution branch-and-bound or

branch-and-cut algorithm must be constructed

• The solution process can be divided into two

phases: capacity assignment and flow
assignment, i.e., Top-Down approach

• Heuristics can be used, e.g., Flow Deviation,

evolutionary algorithm, etc.

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Routing Restrictions
• Link Modularity

• Example

• Convex Function
• Concluding Remarks

Example (1)

1

2

3

4

Szczecin-Gdańsk
<1,2> c=? Mbps
<2,1> c=? Mbps
Szczecin-Wrocław
<1,3> c=? Mbps
<3,1> c=? Mbps
Gdańsk-Wrocław
<2,3> c=? Mbps
<3,2> c=? Mbps
Gdańsk-
Warszawa
<2,4> c=? Mbps
<4,2> c=? Mbps
Wrocław-
Warszawa
<3,4> c=? Mbps
<4,3> c=? Mbps

???

???

???

???

???

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

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

Example (3)

• Integer link capacity variables are denoted as c12, c21,

etc.

• The capacity module is 2 Mbps, only for links 34 and 43

it is 1 Mbps

Link costs:
• Szczecin-Gdańsk <1,2> 700 euro/month for 2 Mbps
• Szczecin-Wrocław <1,3> 900 euro/month for 2 Mbps
• Gdańsk-Wrocław <2,3> 800 euro/month for 2 Mbps
• Gdańsk-Warszawa <2,4> 500 euro/month for 2 Mbps
• Wrocław-Warszawa <3,4> 400 euro/month for 1 Mbps

Example (4)

Capacity constraints

• c12: x1 + x3 + v3 – 2c12 <= 0

• c21: y2 – 2c21 <= 0

• c13: x2 + x4 + y2 – 2c13 <= 0

• c31: v3 – 2c31 <= 0

• c23: x3 + y1 – 2c23 <= 0

• c32: x4 + v2 – 2c32 <= 0

• c24: x1 + x4 + y3 + v2 + v3 – 2c24 <= 0

• c42: - 2c42 <= 0

• c34: x2 + x3 + v1 – c34 <= 0

• c43: y3 – c43 <= 0

1

2

3

4

Example (5)

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}

Capacity constraints

0 <= c12 <= 3 (maximum 3 modules of 2 Mbps)
0 <= c21 <= 3
0 <= c13 <= 3
0 <= c31 <= 3
0 <= c23 <= 3
0 <= c32 <= 3
0 <= c24 <= 3
0 <= c42 <= 3
0 <= c34 <= 3 (maximum 3 modules of 1 Mbps)
0 <= c43 <= 3

1

2

3

4

Example (6)

• File cap1.lp
• Solution

c12 = 2 c21 = 0 c13 = 0 c31 = 0 c23 = 1
c32 = 0 c24 = 2 c42 = 0 c34 = 3 c43 = 1

• 700c12 + 700c21 + 900c13 + 900c31 + 800c23

+ 800c32 + 500c24 + 500c42 + 400c34 +
400c43 =
700x2 + 800x1 + 500x2 + 400x3 + 400 = 4800
euro/month

Example (7)

Maximum number of modules set to 4 (cap2.lp)
0 <= c12 <= 4 etc.
Solution: 4800 euro/month
Maximum number of modules set to 2 (cap3.lp)
0 <= c12 <= 2 etc.
Solution: 5600 euro/month
Maximum number of modules set to 2, capacity can

be continuous (not integer) (cap4.lp)

Solution: 4450 euro/month

Example (8)

Non-bifurcated flows
Maximum number of modules set to 2, capacity can be

continuous (cap5.lp)

Solution: None
Maximum number of modules set to 3, capacity can be

continuous (cap6.lp)

Solution: 4200 euro/month
Maximum number of modules set to 3, capacity integer

(cap7.lp)

Solution: 5200 euro/month

Example (9)

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Routing Restrictions
• Link Modularity
• Example

• Convex Function

• Concluding Remarks

Convex Problem (1)

• CFA (Capacity and Flow Assignment) problem
• Non-bifurcated unicast flows
• Objective is to minimize function including

network delay and network cost function

• Candidate link modeling
• Link-path formulation

Convex Problem (2)

Given: network topology, unicast demands,

candidate paths, candidate links

Minimize: network delay + network cost

Over: Non-bifurcated flows (routing), link capacity

Convex Problem (3)

indices
d = 1,2,…,D

demands

p = 1,2,…,P

d

candidate paths for demand d

e = 1,2,…,Elinks
k = 1,2,…,K

e

candidate link types for link e

Convex Problem (4)

constants



edp

= 1, if link e belongs to path p of demand d; 0,

otherwise

h

d

volume of demand d



ek

cost of candidate link type k on link e

c

ek

capacity of candidate link type k on link e

variables
x

dp

1, if path p is used to realize demand d; 0,

otherwise

y

ek

= 1, if link type k is selected for link e; 0, otherwise

f

e

flow on link e (non-negative, continuous)

Convex Problem (5)

objective
minimize F = 

e

f

e

/(

k

c

ek

y

ek

– f

e

) + 

e



k



ek

y

ek

constraints


d



p



edp

h

d

x

dp

= f

e

e = 1,2,…,E



p

x

dp

= 1, d = 1,2,…,D



k

y

ek

= 1, e = 1,2,…,E

f

e

 

k

c

ek

y

ek

, e = 1,2,…,E.

Lagrangian Relaxation (1)

Since the objective function is increasing in f

e

, the

problem can be reformulated as

objective
minimize F = 

e

f

e

/(

k

c

ek

y

ek

– f

e

) + 

e



k



ek

y

ek

constraints



d



p



edp

h

d

x

dp

 f

e

, e = 1,2,…,E



p

x

dp

= 1, d = 1,2,…,D



k

y

ek

= 1, e = 1,2,…,E

0  f

e

 

k

c

ek

y

ek

, e = 1,2,…,E.

Lagrangian Relaxation (2)

Let  = [



1

,



2

,…,



E

] be a vector of Lagrangian

multipliers

Flow f

e

definition constraint is relaxed and the

corresponding Lagrangian function is as follows

L()=(

e

f

e

/(

k

c

ek

y

ek

– f

e

) + 

e



k



ek

y

ek

) + 

e



e

(

d



p



edp

h

d

x

dp

– f

e

)

= 

e

f

e

/(

k

c

ek

y

ek

– f

e

) + 

e



k



ek

y

ek

– 

e



e

f

e

+ 

e



d



p



edp



e

x

d

x

dp

Since variables f

e

and x

dp

are not linked, we receive D +

E subproblems, that can be solved independently

Lagrangian Relaxation (3)

First subproblem is formulated for variables x

dp

for

each link d = 1,2,…,D

objective
minimize L

d

() = 

e



p



edp



e

h

d

x

dp

constraints


p

x

dp

= 1.

To solve the problem, a shortest path p = 1,2,…,P

d

under the metric



e

must be find, using any

shortest path algorithm

Lagrangian Relaxation (4)

Second subproblem is formulated for variables y

ek

and f

e

for each link e = 1,2,…,E

objective
minimize L

e

() = f

e

/(

k

c

ek

y

ek

– f

e

) + 

k



ek

y

ek

–



e

f

e

constraints


k

y

ek

= 1,

0  f

e

 

k

c

ek

y

ek

.

Lagrangian Relaxation (5)

Since K

e

is relatively small for each link, we can solve

the problem for each k = 1,2,…,K

e

separately

objective
minimize L

e

(,k) = f

e

/(c

ek

– f

e

) +



ek

–



e

f

e

constraints
0  f

e

 c

ek

.

The solution is

Next the subgradient method can be applied




















ek

e

ek

e

e

ek

ek

e

c

λ

c

λ

λ

c

c

k

f

1

for

0

1

for

)

(

Lecture Outline

• Introduction
• Bifurcated Flows with Linear Function
• Routing Restrictions
• Link Modularity
• Example
• Convex Function

• Concluding Remarks

Concluding Remarks

• Network design problems problems are one of the

most popular problems in network optimization

• Network design problems with bifurcated flows

and continuous linear link costs can be solved by

standard optimization methods, e.g., Simplex

• Network design problems with Non-bifurcated

flows or/and modular links 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

• Capacity and flow assignment problems are mostly

simpler than corresponding flow assignment

problems

Further Reading

• M. Pióro, D. Medhi, Routing, Flow, and Capacity Design in

Communication and Computer Networks, Morgan Kaufman
Publishers 2004

• A. Kasprzak, Algorytmy równoczesnej optymalizacji

przepływów, przepustowości kanałów i struktur
topologicznych sieci teleinformatycznych, Wydawnictwo
Politechniki Wrocławskiej, Wrocław, 1989 (in polish)

• B. Gavish, S. Huntler, An Algorithm for Optimal Route

Selection in SNA Networks, IEEE Trans. Commun., Vol. COM-
31, No. 10, 1983, pp. 1154-1160

• B. Gavish, I. Neuman, A System for Routing and Capacity

Assignment in Computer Communication Networks, IEEE
Trans. Commun., Vol. 37, No. 4, 1989, pp. 360-366