Algorithms for frequency assignment problems

Frequency assignment problems occur when a network of radio links has to be established. Each link has to be assigned an operating frequency from a set of available frequencies. The assignment has to satisfy certain interference limiting restrictions defined on pairs of links. Moreover, the number of frequencies used is to be minimized. These problems have been investigated 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, as well as approximation techniques such as simulated annealing, taboo search, variable-depth search, genetic algorithms, and potential reduction methods. These algorithms were tested and compared on a set of real-life instances.