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

Improvement phase
Initial solution
yes
no
Fig. 2. The framework of our algorithm.
our algorithm is 4exible and depending on the requirements we can o?er solutions faster or better
solutions relatively slower.
The framework of our algorithm is shown in Fig.
2
.
The operations are discussed in Section
5.1
. The algorithms for initial solution are described in
Section
5.2
and the improvement algorithm is given in Section
5.3
. Finally, Section
5.4
shortly deals
with some built-in enhancement issues, which speed up the computation. The pseudocodes of the
algorithms are given in the Appendix
A
.
5.1. Operations
We have four basic operations and three compound operations. The basic operations are: Cluster,
Tree, Moves and Swaps. The compound operations are: Recluster, ReclusterLevel and LocalOpt.
The de/nitions of the operations are given below. The relation between the operations is shown in
Fig.
3
.
5.1.1. Basic operations
5.1.1.1. Cluster. This operation divides a given input set of nodes (P) into a number of distinct
subsets G
i
(called clusters) (i = 1; : : : ; K), which represent the best con/guration. The centers of the
clusters will be on level l, which is an input parameter of the operation. The cost of a con/guration
is derived from (i) connecting all nodes in each cluster to the corresponding cluster center put in
level l (from now called the median) and (ii) installing equipment in the median nodes, then (iii)
connecting these median nodes upwards to higher level. The clustering is based on the well-known
K-means algorithm [
28
]. To /nd the best value of K, we repeat the K-means algorithm for multiple

---

68
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
Moves
Tree
Cluster
Swaps
Recluster
ReclusterLevel
Full-Iterate
(improvement phase)
LocalOpt
Top-Down
(initial solution)
Basic
operations
Compound
operations
The two
phases of our
novel
algorithm
Fig. 3. The relations between the operations.
values of K between K
min
and K
max
. The upper bound is K
max
= |P| − F, where F is the number
of nodes in P that are forbidden to be in level l. The lower bound is K
min
=  |P|=(U
l
+ 1) , where
U
l
is the maximal number of nodes that can be connected to a median in level l (U
l
is calculated
from the depth and degree constraints). We do not try out all possible values of K between K
min
and K
max
. We start from K = K
min
. Then we continue with K ← K + 1 in the next round. We stop
to advance K if we did not get better solution in the last K
la
rounds, where K
la
is a look-ahead
parameter set to a small value.
Operation Cluster involves three modular elements, which depend on the context in which the
clustering is applied: the allocation step (for creating clusters by allocating nodes to selected me-
dians), the relocation step (for choosing a new median in a cluster) and the cost-calculation step
(for the evaluation of a network con/guration). Since operation Cluster is the basis of compound
operation Recluster and the Top-Down algorithm, the above three modular elements will be de/ned
in both procedures separately.
5.1.1.2. Tree. The purpose of this operation is to build up a tree topology from a given input set
of nodes, which topology satis/es the level and degree constraints as well as the /xed and forbidden
node constraints. The inputs of the operation are a node set P, the root r ∈ P of the tree and desired
hierarchy level l of this root. The operation uses two sets of nodes, the set of yet unconnected nodes
and the set of nodes that has already been connected to the tree. The latter ones serve as possible
parent nodes for the unconnected ones. Initially, only the root r considered as parent. We connect
the unconnected nodes one by one to extend the tree, where we choose the least cost node–parent
pair in each step. The operation is accelerated by considering only a small random sample from
the unconnected node set in each step. Moreover, if we /nd that the tree could not be extended
at a particular parent node after several attempts (because of constraint-, equipment- or link type
violation), then we discourage ourselves to try this parent node again and we remove it from the set
of possible parents. Operation Tree is used for quick and greedy cost-approximation of particular
tree sections in the Top-Down algorithm. When operation Cluster have created clusters in level l,

---

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