An updated version to be published in
Annals of Operations Research is now available
online. Alternatively, the manuscript can be downloaded here.
Authors: Karen I. Aardal, Stan P.M. van Hoesel, Arie M.C.A. Koster, Carlo Mannino, and Antonio Sassano.
Title: Models and Solution Techniques for Frequency Assignment Problems
Reference: published in 4OR, volume 1, number 4, pages 261 - 317 (2003). Slighty older version also available as ZIB-Report 01-40, December 2001:
An updated version to be published in
Annals of Operations Research is now available
online. Alternatively, the manuscript can be downloaded here.
Abstract: Wireless communication is used in many different
situations such as mobile telephony, radio and TV broadcasting,
satellite communication, and military operations. In each of these
situations a frequency assignment problem arises with application
specific characteristics. Researchers have developed different
modelling ideas for each of the features of the problem, such as the
handling of interference among radio signals, the availability of
frequencies, and the optimization criterion.
This survey gives an
overview of the models and methods that the literature provides on the
topic. We present a broad description of the practical settings in
which frequency assignment is applied. We also present a
classification of the different models and formulations described in
the literature, such that the common features of the models are
emphasized. The solution methods are divided in two
parts. Optimization and lower bounding techniques on the one hand, and
heuristic search techniques on the other hand. The literature is
classified according to the used methods. Again, we emphasize the
common features, used in the different papers. The quality of the
solution methods is compared, whenever possible, on publicly available
benchmark instances.
Keywords: frequency assignment
MSC: 90-02, 90C35, 05C90