## 90B80 Discrete location and assignment [See also 90C10]

### Refine

#### Document Type

- ZIB-Report (2)

#### Language

- English (2)

#### Has Fulltext

- yes (2)

#### Is part of the Bibliography

- no (2)

#### Keywords

#### Institute

- ZIB Allgemein (2)

In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to be re-optimized on a regular basis. Besides the balancing objective also the number of rearrangements have to be taken into account. In this paper we present two alternative formulations to deal with both requirements. Computational results show that for both formulations (near) optimal solutions can be obtained within reasonable time limits.

Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem.