Radio Frequency Assignment: Optimization Techniques

The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimise interference and the spectrum required. Some different variations of the problem are presented in this report to- gether with the results obtained so far for them. In this work we will study mainly the so-called “Fixed Spectrum Problem”, where there is a fixed avail- able spectrum of frequencies and the aim is to minimise interference. There are two main approaches to model the frequency assignment prob- lem: the so-called “Binary Constraints Model”, historically the most studied in the literature, where only interference from a single transmitter at a time is considered, and the more realistic “Multiple Interference Model”, where interferences from more than one transmitter are considered at the same mo- ment. For this last model a deeply theoretical study does not yet exist in the literature. The fixed spectrum problem, represented by the binary constraints model has been heavily studied in the last few years, but no general-purpose lower bound has been presented yet. We analyse some Integer Programming for- mulation to understand whether they can be suitable for developing lower bounds. The multiple interference model is studied and some new algorithms, both heuristic and exact, are presented for it, together with the relevant computational results. Our aim is to understand the potential of this model. The report concludes by outlining some proposals for future work.