# A Matheuristic for Joint Optimal Power and Scheduling Assignment in DVB-T2 Networks +
## 4 A Matheuristic for DVB Design  
Though DVB-PI+ constitutes a binary linear program that can be easily passed to any optimization software to be solved, even a sophisticated last generation solver like CPLEX [58] may experience a very hard time just trying to identify solutions of reasonable quality. Furthermore, CPLEX also exhibits a very slow convergence to optimal solutions. In order to tackle such computational issues, we propose to solve DVB-PI+ through a new matheuristic algorithm that combines a Genetic Algorithm (GA) with relaxation-based variable fixing and exact large neighborhood searches.  
GAs correspond to heuristics for optimization problems that draw inspiration from the evolutionary dynamics of populations and have known a wide success in many different application contexts. For a thorough introduction to GAs, we refer an interested reader to [59; 60; 61]. Any GA is based on maintaining a population, in which every individual provides a feasible solution to the optimization problem. The feasible solution is encoded in the _chromosome_ of the individual and a _fitness function_ is used to evaluate how good the chromosome is, and thus, the corresponding feasible solution. During the execution of the GA, the population evolves, iteration after iteration, by means of procedures that resemble the process of natural selection, implementing the crossover of individuals' chromosomes, chromosome mutation and the death of individuals.  
In our case, we strengthen the performance of a GA by combining it with _relaxation-based variable fixing_, in which the value of decision variables is set a-priori considering the value of variables in an optimal solution to a suitable (tight) linear relaxation of the problem, followed by _exact large neighborhood searches_, where the search for solutions of improved quality in a large neighborhood is expressed as an optimization problem solved exactly through a state-of-the-art solver. The rationale at the basis of the approach is that, while a state-of-the-art solver may find difficulties in solving a complete hard optimization problem, it may instead tackle effectively and efficiently suitable subproblems of it, obtained by fixing variables and exploring related large neighborhoods. We were attracted by the possibility of defining a matheuristic by combining a GA with tight linear relaxations and exact ILP search, since such an original combination allows the ability to explore the solution space of DVB-PI fast and effectively, exploiting the valuable tight linear relaxations associated with the strengthened formulation DVB-PI+.  
The overall scheme of the GA that we consider is provided in Algorithm 1.  
```
1:Creation of the initial population
2:while an arrest condition is not satisfied do
3: Selection of individuals for generating the offspring
4: Crossover of individuals' chromosomes for generating the offspring
5: Mutation of a portion of the population
6: Death of a portion part of the population
7:endwhile
8:Improvement by ILP Heuristic
```  
**Algorithm 1** General Genetic Algorithm (GA-alg).  
We now proceed to discuss in detail the features of all the steps of the algorithm.