Search

We address the question of defining a robust optimization approach to model and solve a DVB-T network design problem, while taking into account the uncertainty that naturally affects the propagation of wireless signals. The robust counterpart of the Mixed Integer Linear Programming model that represents the design problem exploits multiband uncertainty, a cardinality-constrained uncertainty model that employs multiple deviation bands. Since the robust counterpart may prove challenging to solve also for state-of-the-art optimization solvers, we propose a matheuristic for its solution. The matheuristic combines a variable fixing procedure exploiting suitable (tight) linear relaxations of the model with exact large neighborhood search. Results of computational tests considering realistic instances are reported to assess the performance of the approach, showing that the matheuristic can generate solutions of higher value than a commercial optimization solver within the available time budget.

Because of the introduction and spread of the second generation of the Digital Video Broadcasting—Terrestrial standard (DVB-T2), already active television broadcasters and new broadcasters that have entered in the market will be required to (re)design their networks. This is generating a new interest for effective and efficient DVB optimization software tools. In this work, we propose a strengthened binary linear programming model for representing the optimal DVB design problem, including power and scheduling configuration, and propose a new matheuristic for its solution. The matheuristic combines a genetic algorithm, adopted to efficiently explore the solution space of power emissions of DVB stations, with relaxation-guided variable fixing and exact large neighborhood searches formulated as integer linear programming (ILP) problems solved exactly. Computational tests on realistic instances show that the new matheuristic performs much better than a state-of-the-art optimization solver, identifying solutions associated with much higher user coverage.