Models and solution techniques for frequency assignment problems (Q5907051)

This paper is a survey on the frequency assignment problem. This problem arises in mobile telephony, radio and TV broadcasting, satellite communication and military operations. All these applications lead to many different models and within the models to many different types of instances. Nevertheless, all of them share two common features: a set of wireless communication connections must be assigned frequencies such that data transmission between the two endpoints of each connection is possible and the frequencies assigned to two connections may incur interference to one another, resulting in general loss of the signal. The authors develop an overview of the models and methods that the literature, which has grown quickly over the past years, provides on frequency assignment problems. This paper only deals with fixed channel assignment, i.e. static models where the set of connections remains stable over time. The focus of this paper is mainly on the practical relevance of mathematical optimization techniques for frequency assignment. The authors present the practical settings of the problem in such a way that the common features are emphasized. The authors also categorize the models in four standard classes, that mainly differ in the objective to be optimized. For each of the models, they discuss: 1. Structural properties of the models, including bounding techniques based on (combinatorial) relaxations; 2. Exact optimization methods, such as branch-and-cut, branch-and-price and combinatorial enumeration and 3. Heuristic methods, such as local search, genetic algorithms, neural networks and constraint programming.