Draft of the lecture (modification 2)

Course:
Teacher:
Specialization:
Semester:
Telecommunication network design
Piotr Chołda
Networks and services
2nd sem. MSc stud., Fall
..............................................................................
Draft of the lecture
November 13, 2014
1
Lecture VII (November 13th , 2014): discrete/integer
programming in network design — topology
design, dimensioning with modular capacity,
linearization of non-linear goal functions
1. Topological Design with a Fixed Charge Model (TDFCM), L-P formulation:
• Indices:
? e = 1, 2, . . . , E candidate links;
? d = 1, 2, . . . , D demands;
? p = 1, 2, . . . , Pd candidate paths of flows realizing demand d.
• Variables:
? xdp
? ye
? ue
flow realizing demand d on path p,
capacity to be installed on link e,
= 1 if link e is to be installed;
= 0, otherwise (binary decision variable).
• Constants:
? δedp = 1 if link e belongs to path p realizing demand d;
= 0 otherwise;
? hd volume of demand d;
? ξe
fixed unit cost of capacity usage on link e;
? κe
cost of ‘opening’ (i.e., installation) of link e;
? W
‘big W ’ (sufficiently large value).
P
• Goal function: min F(y, u) = e (ξe ye + κe ue ).
• Constraints:
P
?
x = hd
d = 1, 2, . . . , D;
Pp Pdp
?
δ
x
=
y
e = 1, 2, . . . , E;
edp
dp
e
d
p
? ye ≤ W ue
e = 1, 2, . . . , E;
? y and x—non-negative continuous and u—binary.
2. Topology design with candidate locations for nodes:
• add binary decision variable uv indicating installation of node v;
Page 1
Course:
Teacher:
Specialization:
Semester:
Telecommunication network design
Piotr Chołda
Networks and services
2nd sem. MSc stud., Fall
..............................................................................
• add uv to the goal function (with the respective installation cost);
• add costants describing incidence of links and nodes (the same as aev
and bev in the N-L formulation);
P
• add constraints: e (aev + bev )ue ≤ W uv v = 1, 2, . . . , V .
3. Network design with modular capacity (M : module size of the link capacity, e.g., M = 10 Gb/s):
• ye —integer variable, MI(L)P problem (xdp are continuous):
P P
? LINK constraints: d p δedp xdp ≤ M ye e = 1, 2, . . . , E;
? PATH constraints: no changes.
• udp —binary variables (flows are non-bifurcated, single path routing
for a demand), ye —integer variable, I(L)P problem:
P P
? LINK constraints: d p δedp hd udp ≤ M ye e = 1, 2, . . . , E;
P
? PATH constraints: p udp = 1 d = 1, 2, . . . , D.
4. Modular dimensioning:
• Multiple modules: Mk , k = 1, 2, . . . , K:
?
?
?
?
?
?
ξek cost of capacity module k on link e (constant);
Mk size of module k (constant);
yek number of modules k to be installed on link e (variable);
P P
goal function: min F(y) = e k ξek yek ;
P P
P
d
p δedp xdp ≤
k Mk yek e = 1, 2, . . . , E;
yek —integer variable.
• Incremental modular function: mk , k = 1, 2, . . . , K:
?
?
?
?
?
uek determines if capacity module k is used on link e (variable);
P P
goal function: min F(u) = e k ξek uek ,
P P
P
d
p δedp xdp ≤
k mk uek e = 1, 2, . . . , E,
ue1 ≥ ue2 ≥ · · · ≥ ueK
e = 1, 2, . . . , E,
uek —binary variable.
• The values of ξek or Mk /mk may be different in both approaches.
P
5. Design with non-linear goal function: min F(y) = e ξe f (ye ):
• f (z): convex function (delay, penalty), convex set, epigraph, strictly
convex function;
• f (z): concave function (link dimensioning with the ‘economies of
scales’ due to diminishing marginal return, utility function), concave
set.
6. Convex programming (CXP): global minimum identical with local minimum, no duality gap.
7. Concave programming (CVP): much more complex to obtain the global
minimum than for CXP.
8. Network design with penalty-like goal function, bifurcated solution, linearization.
Page 2
Course:
Teacher:
Specialization:
Semester:
Telecommunication network design
Piotr Chołda
Networks and services
2nd sem. MSc stud., Fall
..............................................................................
9. Network design with utility-like goal function, linearization with usage of
binary variables.
10. Yaged’s method: a heuristic for solving of a concave problem.
1.1
Exercises
1. A fragment of an optimization task is given below. In the given form it
is not a proper instance of MILP. (a) Why? (b) Correct it, so that it is
a proper MILP task. (c) Interpret the meaning of variables udp and the
constraints.
• Indices:
? e = 1, 2, . . . , E
? d = 1, 2, . . . , D
? p, q = 1, 2, . . . , Pd
demand d.
links;
demands;
candidate paths for flows that can realize
• Constants:
? δedp = 1 if link e belongs to path p that can realize demand d;
otherwise 0
• Variables:
? we
? udp
weight of link e, non-negative continuous value;
binary value;
• Constraints:
? ∀d=1,2,...,D
P
p
? ∀d=1,2,...,D ∀q=1,2,...,Pd
udp = 1;
P
P
p=1,2,...,Pd e
δedp we udp ≤
P
δedq we .
e
2. Formulate a set of equalities/inequalities (using some additional variables,
e.g., integral, or some constants, if necessary) that can be used to describe
the relationship between value of variable x (giving the link load, 0 ≤
x ≤ 40) and value y = f (x), i.e., a cost of the capacity usage on this
link (having those equalities/inequalities, and using a selected value of x,
we should be able to calculate the value of y). The constraints should be
formulated according to the rules related to formulation of Mixed Integer
Linear Programming (MILP) problems, in which a goal function (a cost
of the link usage) is minimized. The relationship between y and x is given
in Figure 1.
1.2
1.2.1
Reading
Contents of the lecture
Problems described in this lecture are generally dealt with in the following
position:
• Michał Pióro and Deepankar Medhi. Routing, Flow and Capacity Design
in Communication and Computer Networks. Morgan Kaufmann Publishers—
Elsevier, San Francisco, CA, 2004: chapter 4.3, 5.5-5.6, 6.1-6.3.
Page 3
Course:
Teacher:
Specialization:
Semester:
Telecommunication network design
Piotr Chołda
Networks and services
2nd sem. MSc stud., Fall
Cost of the capacity usage, y = f (x)
..............................................................................
400
300
200
10
20
40
Link load (capacity usage), x
Figure 1: An example of a concave tariff, linear within segments, used in Exercise 2.
1.2.2
Obligatory paper
Tamra Carpenter and Hanan Luss. Telecommunications Access Network Design.
In Mauricio G. C. Resende and Panos M. Pardalos, editors, Handbook of Optimization in Telecommunications, chapter 13, pages 313–339. Springer Science
+ Business Media, Inc., New York, NY, 2006—except for Section Survivable
Access Network Design.
On the basis of the paper, elaborate on the following: backbone/core vs.
access network, nodes in these networks, reasons for distinguishing at least two
types of networks — multi-commodity network flow problem — various cost
functions: fixed charge cost, piecewise concave cost, step cost — concentrator
location problem: a simple model, multi-level trees, and a hierarchical model,
problem conditions related to various transmission technologies.
1.2.3
Auxiliary references
• Michał Pióro and Deepankar Medhi. Routing, Flow and Capacity Design
in Communication and Computer Networks. Morgan Kaufmann Publishers—
Elsevier, San Francisco, CA, 2004.
• Poompat Saengudomlert. Optimization for Communications and Networks. CRC Press/Science Publishers, Boca Raton, FL, 2012.
• Laurence A. Wolsey. Integer Programming. John Wiley & Sons, Inc., New
York, NY, 1998.
Page 4

Download Report