The Orientation Model for Frequency Assignment Problems
| TR 98-01 | Ralf Borndörfer, Andreas Eisenblätter, Martin Grötschel, Alexander Martin
The Orientation Model for Frequency Assignment Problems | |
Abstract: 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.
Keywords: Minimum-Cost Flow Problems,
Cellular Radio Telephone Systems,
Frequency Assignment Problem,
Integer Programming
MSC: 90B10, 90B12, 90B80, 90C10