Telecommunication Optimization

(1)

1

Introduction to Telecommunication Optimization

Thomas Stidsen

tks@imm.dtu.dk

Informatics and Mathematical Modeling Technical University of Denmark

(2)

Thomas Stidsen 2

Learning Objectives

After this lecture you will:

Have learned a brief overview of telecommunication history

Have heard a little about network components Have been introduced to the graph model

Have been introduced to a number of different optimization problems and their models

(3)

3

Brief Telecommunication History I

The optical telegraph 1792-1846, Claude Chappe

The (Electrical) Telegraph 1837, Samuel Morse The telphone 1876, Alexander Graham Bell

The Radiotelegrap 1895, Guglielmo Marconi 1930 automatic switches ....

(4)

Thomas Stidsen 4

Brief Telecommunication History II

(The computer 1941, Konrad Zuse, based on telecommunication components ...)

1960’ies satellites, Internet (TCP/IP protocol) 1980’ies optics, mobile phones

1990’ies www

2000’ies WiFi, UMTS, MPLS, WiMax ....

(5)

5

Telecommunication Optimization

The objective when optimizing is always to plan the use of scarce recourses and at the same time to

enhance communication. In Telecommunication these are usually:

Network Costs (investments in network components)

User utility (price, speed, availability, reliability)

(6)

Thomas Stidsen 6

Transfer Technologies

Ok, lets ignore the old technologies and look at the

“new” ones:

Satellites: Wide coverage, but slow data rate and long transmission times

Optics: The “unknown revolution”: HUGE increases in capacities ....

Wireless technologies ....

(7)

7

Graph Model

Switches = Nodes Cables = Links

Circuits = Paths

B

C

D

5

A

(8)

Thomas Stidsen 8

Network Hierarchy

Backbone

Regional/National Access

(9)

9

Network Hierarchy

00 11

Metro ring

Metro ring Metro ring

ring Federal

(10)

Thomas Stidsen 10

Planning Horizon

Strategic: New Networks, expansion of network Tactical: Where to route new requests

Real Time: How to recover

(11)

11

Detailed modeling (How realistic a model ?)

Whenever doing OR there is a tradeoff of what should be modeled:

capacity on links/nodes transmission time

costs

protection technology routing weights

length limits

... (and many more)

(12)

Thomas Stidsen 12

Plan for the course

Today: Intro, routing (Multi Commodity Flow Problem)

14/9: Network Design

21/9: Protection techniques

(13)

13

The Multi Commodity Flow Problem

The mother of all routing problems. Given:

A network of nodes and links/arcs (and architecture)

A connection demand Component limitations ...

(14)

Thomas Stidsen 14

MCF Terms

x^kl_ij : The fraction of the demand from k to l which flow from i to j

c_ij: Cost per capacity unit

CAP_{ij_}: Maximal capacity through the link Dkl: How many connections should be

established between node k and node l

(15)

Thomas Stidsen 15

Multi Commodity Flow Problem (MCF)

The mother of all routing problems

Min: X

kl

X

ij

c_ij · D_kl · x^kl_ij

s.t.:

X

j

x^kl_ij − X

j

x^kl_ji =





1 i = k

−1 i = l X 0

kl

(x^kl_ij + x^kl_ji) · Dkl ≤ CAP_{ij_} ∀{ij} x^kl_ij ∈ [0, 1]

(16)

Thomas Stidsen 16

MCF comments

There are polynomially many variables, but O(N⁴) is still a lot ...

There are specialized solvers ...

(17)

17

Multi Commodity flow (MCF)

There are MANY different variations Typically MCF is a lower bound

Problem becomes much harder when variables obtain integer values

Solution method: Column Generation/Branch and price

(18)

Thomas Stidsen 18

LP programs with many variables !

The crucial insight: The number of non-zero variables (the basis variables) is equal to the number of constraints, hence eventhough the number of possible variables (columns) may be large, we only need a small subset of these in the optimal solution.

Basis Non−basis

(19)

19

The Simplex Algorithm

Assume we want to minimize:

select initial solution

while variables with negative reduced cost exists

Find the most negative reduced cost (new basic var) Find variable to replace (new non-basic var)

Update variable values end while

What if we have extremely many variables ? Then we have a problem: It will take too long time to

check the reduced costs !

(20)

Thomas Stidsen 20

MCF (path formulation)

y_p^kl: The fraction of the demand from k to l which flows on path p

c^kl_p : Cost per capacity unit

CAP_{ij_}: Maximal capacity through the link

A^kl_p,{ij_}: Incidence matrix, to indicate which links are used by which paths

Dkl: How many connections should be established between node k and node l

(21)

21

Multi Commodity Flow Problem (MCF)

The mother of all routing problems

Min: X

kl

X

p

c^kl_p · D_kl · y_p^kl s.t.:

X

p

y_p^kl = 1 ∀kl X

kl

X

p

A^kl_p,{ij_} · D_kl · y_p^kl ≤ CAP_{ij_} ∀{ij} y_p^kl ∈ R+

(22)

Thomas Stidsen 22

Reduced costs

The reduced costs for the non-basic variables in each generation is then: cˆ = c_N − c_BB⁻¹N, or ˆ

cj = cj − cBB⁻¹Nj (where Nj is the j⁰ column in the N matrix.

Hence cˆ_j = P

i π_iaⁱ_j − α, where π_i = c_BB⁻¹

The reduced costs: The reduction in objective function if non-basic variable is increased by one unit. If it is negative, the path can improve the objective.

(23)

23

Problems

What are the main problems if we want to use column generation ?

How to solve the subproblem efficient ? How to get integer solutions ?