Algorithms for radio link frequency assignment

Abstract

The radio link frequency assignment problem occurs when a network of radio links has to be established. Each link must be assigned anoperating frequency from a given domain. The assignment has to satisfy certain restrictions so as to limit the interference between links.The number o f frequencies used is to be minimized.Problems o fthis type were investigated within the CALMA project by a consortium consisting o fresearch groups from Del ft, Eindhoven,London, Maastricht, Norwich, and Toulouse. The participants developed optimization algorithms based on branch-and-cut and constraintsatisfaction, and approximation techniques including a variety of local search methods, genetic algorithms, neural networks, and potentialreduction. These algorithms were tested and compared on a set o freal-li fe instances.