A Unified View In Planning Broadcasting Networks

The migration from analog to digital systems in audio/video broadcasting involves challenging replanning of antenna diagrams and frequencies of transmitters. We introduce a hierarchy of subproblems arising at both regulation authorities and broadcasters within this complex and costly process. Heuristic and exact integer programming algorithms for such problems are illustrated within a common framework and their merits and drawbacks are discussed. We show that, in this context, the classical graph-based reformulation of the frequency assignment problem cannot be exploited. However, non-compact Set-packing and Set-covering formulationscan be derived by applying respectively the Dantzig-Wolfe and Benders' decompositions to the natural, unstructured, MILP formulation.