Complexity of different ILP models of the frequency assignment problem
Zoltán Ádám Mann, Anikó Szajkó · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · 2012
The frequency assignment problem (FAP) arises in wireless communication networks, such as cellular phone communication systems, television broadcasting, WLANs, and military communication systems. In all these applications, the task is to assign frequencies to a set of transmitters, subject to interference constraints. The exact form of the constraints and the objective function vary according to the specific application. Integer linear programming (ILP) is widely used to solve the different flavors of the FAP. For most FAP versions, there are more than one natural ILP formulations, e.g. using a large number of binary variables or a smaller number of integer variables. A common experience with these solution techniques, as well as with NP-hard optimization problems in general, is a high variance in problem complexity. Some problem instances are tremendously hard to solve optimally. There are also examples of relatively big problem instances that are nevertheless quite easy to solve. In general, it is hard to predict how long it will take to solve a given problem instance. This