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

parts already planned).
5.2.2. TreePlan
The original TreePlan [
18
] algorithm determines the number and position of nodes that will be at
level 1 and assigns all other nodes to them to form trees. Then method TreeMake [
19
] determines
the nodes to be in level 2; : : : ; L, separately for each tree created by TreePlan. Both algorithms select
nodes to be in the considered level l by a simulated annealing technique, then they build up the rest
of the network under level l by applying operation Tree. During the simulated annealing process,
the actual node set in level l is modi/ed by selecting a new node to be in level l or by removing
one from there or by applying both at the same time. The SA process is used to decide whether a
modi/cation results in a better network con/guration or not. The decision is based on the cost as
in the Top-Down algorithm.
5.2.3. Random
First we select a node randomly and put it into the /rst level. Then, iteratively, we pick a node
randomly and connect it to an already connected node (we consider nodes in level 1 as connected).
The choice of a parent node for the connection is random. If a new connection con4icts with the
limitations or implies in/nite cost, then we discourage ourselves to try this parent node again and we
do not consider this parent as connected node further on. If no new connection can be established,
we put a node randomly to the /rst level to form a new root.
5.3. Algorithms for improvement phase
In the improvement phase, we systematically revise the connections and the hierarchy level for
each node. We apply operation ReclusterLevel and LocalOpt to optimize one level at a time.

---

72
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
In each round of the algorithm, we step down in the hierarchy. At the end of a round, we also apply
operation LocalOpt allow modi/cations also to nodes situated in non-adjacent levels. We iterate the
rounds until no further improvements are found. During the iteration, we adaptively advance the
complexity of the compound operations.
We present our algorithm called Full-Iteration by specifying one round of the improvement
phase:
(1) (New round) Improve the actual solution by going through the hierarchy level by level. To
achieve this we have a loop with l = 1; : : : ; L − 1, and:
(a) (Cluster) Apply ReclusterLevel to recompute the number and position of concentrators in
hierarchy level l.
(b) (Level Opt) Apply LocalOpt to optimize the connections between levels l and l + 1.
(2) (Thorough Opt) Apply LocalOpt with all the nodes independently from their levels in order to
further improve the connections.
(3) (Evaluation) Calculate the network cost and evaluate the solution:
(a) (Advance complexity) If the improvement of the costs between the actual and the previous
round is not satisfactory then advance the complexity of the compound operations if it is
possible and go to Step 1.
(b) (Termination) If the solution improved then go to Step 1 else stop.
The complexity of operations Recluster and LocalOpt controls the actual choice of the modular
steps used in these operations. (Note that operation Recluster is the core of ReclusterLevel.) For
operation Recluster the modular steps are: the allocation step and the involved local optimization
steps. For operation LocalOpt the complexity is controlled by the option of applying this operation
tree-by-tree separately or on the entire network.
The advance of the complexity allows us to /nd an equilibrium between the running time of the
algorithm and the quality of the solution. We have 9 degrees of the complexity in the improvement
phase:
• Apply LocalOpt tree-by-tree and