A tight reformulation of the power-and-frequency assignment problem in wireless networks

One major task in wireless network planning is to assign emission powers and frequencies to transmitters so as to maximize the customers coverage (Power and Frequency Assignment Problem, PFAP). We present an optimization model which can be applied whenever the coverage is evaluated through a ¯nite set of testpoints, and the coverage condition of one testpoint can be cast into a linear function of the wanted and interfering signals. This happens, for instance, in mobile telephony and audio/video broadcasting. Natural compact integer programming formulations for PFAP often show large integrality gap and cannot be used to solve instances of practical interest. We present a non-compact Set Packing formulation for PFAP obtained by applying the Dantzig-Wolfe decomposition to the natural formulation. The pricing problem consists in optimizing the emission powers in a single frequency network, for which effective algorithms are available. Experiments show that the non-compact formulation is very tight and the resulting branch-and-price algorithm solves to optimality practically relevant instances of the Italian broadcasting system.