This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Aardal, K. Articles by Tiourine, S. Search for Related Content

Algorithms for Radio Link Frequency Assignment: The Calma Project

Department of Mathematics, Utrecht University, Budapestlaan 6, 3584 CD Utrecht, The Netherlands
Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, 5600 MB Eindhoven, The Netherlands
Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, 5600 MB Eindhoven, The Netherlands
Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, 5600 MB Eindhoven, The Netherlands
aardal{at}math.uu.nl
wscor{at}win.tue.nl
jkl{at}win.tue.nl
sergey.tiourine{at}carmen.se

The radio link frequency assignment problem occurs when a network of radio links has to be established. Each link must be assigned an operating frequency from a given domain. The assignment has to satisfy certain restrictions so as to limit the interference between links. The number of frequencies used is to be minimized.

Problems of this type were investigated within the CALMA project by a consortium consisting of research groups from Delft, Eindhoven, London, Maastricht, Norwich, and Toulouse. The participants developed optimization algorithms based on branch-and-cut and constraint satisfaction, and approximation techniques including a variety of local search methods, genetic algorithms, neural networks, and potential reduction. These algorithms were tested and compared on a set of real-life instances.

Subject classifications: Programming/integer: comparison of algorithms. Communications: frequency assignment.
History: Received November 1999; revision received July 2001; accepted October 2001.