Models and methods for frequency assignment with cumulative interference constraints

In this paper, a realistic modeling of interferences for frequency assignment in hertzian telecommunication networks is presented. In contrast with traditional interference models based only on binary interference constraints involving two frequencies, this new approach considers the case of cumulative disruptions that are modeled through a unique non-binary constraint. To deal with these complex constraints, we propose extensions of classical integer linear programming formulations. On a set of realistic instances, we propose hybrid constraint programming and large neighborhood search solution methods to solve minimum interference and minimum span frequency assignment problems. We compare their performances with those of existing heuristics. Finally, we show how the end-user benefits from using the cumulative model instead of the traditional one.