Doi: 10. 1016/S0305-0548(03)00202-8

1.26
1.36
1.66
1.44
1.67
1.43
1.88
1.68
1.76
1.21
1.74
1.59
1.29
1.41
1.1
1.55
1.8
1.53
1.1
6.42
1.66
1.59
1.26
2.65
t = 10.33
1.43
1.36
1.29
4.06
3.12
6.17
1.68
4.64
2.88
1.67
t = 13.35
Fig. 1. Sample network with two aggregation trees. The numbers stand for the tra3c of the links or nodes. The picture
on the right shows an access network, which can be built based on the input given on the left.
that the addition operator is de/ned for it. The maximum number of levels (depth constraint) of the
resulting aggregation trees is given by L ¿ 2; the roots are in level 1. The maximum indegree of the
nodes in each level is given by D
k
¿ 0; k =1; : : : ; L, where D
L
=0 as the lowest level leaf nodes have
no incoming links. The input function C
Eq
(i; l; t) returns the cost of the equipment to be installed
into node i ∈ N, if it is placed at level 1 6 l 6 L in an aggregation tree, and if it aggregates t ∈ T
amount of tra3c. The input function C
Li
(i; j; t) returns the cost of a link between nodes i; j ∈ N,
i = j, if it carries t ∈ T aggregated tra3c.
2.3. Output
The task is to interconnect the set of nodes to form a set of trees with the least possible cost. The
decision variable x
ij
∈ {0; 1} equals to 1 i? node i is connected upwards to node j in the aggregation
tree containing it, ∀i; j ∈ N. Variable 1 6 l
i
6 L denotes the level of node i in the tree containing
it, where l
i
= 1 for a root node, l
i
= 2 for a child node of a root, etc., ∀i ∈ N. We derive some
auxiliary variables from these two sets of variables: l
ik
∈ {0; 1} equals to 1 i? node i is at level k in
the tree containing it, ∀i ∈ N, k = 1; : : : ; L, while t
i
∈ T denotes the total aggregated tra3c in node
i, ∀i ∈ N.
2.4. Problem formulation
The access network planning problem is then:
min


n

i=1
n

j=1;j

=i
x
ij
C
Li
(i; j; t
i
) +
n

i=1
C
Eq
(i; l
i
; t
i
)


(1)
with respect to
l
ik
=

1 if l
i
= k;
0 if l
i
= k;
∀i ∈ N; k ∈ {1; : : : ; L};
(2)
t
j
= T
j
+
n

i=1;i

=j
x
ij
t
i
∀j ∈ N;
(3)

---

62
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
n

j=1;j

=i
x
ij
= 1 − l
i1
∀i ∈ N;
(4)
n

i=1;i

=j
x
ij
6
L

k=1
l
jk
D
k
∀j ∈ N;
(5)
x
ij
= 1 ⇒ l
i
= l
j
+ 1 ∀i; j ∈ N;
(6)
x
ij
∈ {0; 1} ∀i; j ∈ N; i = j;
(7)
l
i
∈ {1; : : : ; L} ∀i ∈ N;
(8)
l
ik