# A Matheuristic for Joint Optimal Power and Scheduling Assignment in DVB-T2 Networks +
## 3 Strengthening the Initial MILP Formulation  
DVB-MILP represents a straightforward model for DVB design that is based on the direct inclusion of the SIR constraints, as made in most other works addressing the WND (e.g., [13; 14; 26; 33]). Nevertheless, such straightforward modeling presents remarkable drawbacks:  
* The fading coefficients typically lead to (very) ill-conditioned coefficient matrices, since they commonly vary in really wide ranges, and this leads to numerical instabilities even in state-of-the-art optimization software used to solve the problem (see [54] for a detailed discussion). * The big-Ms constitute notorious coefficients whose inclusion in a model is well-known to lead to weak bounds that badly affects the performance of optimization software (see e.g., [55]). * Due to the combined presence of the fading and big-M coefficients and their effects on the solution process, solutions returned by solvers typically contains errors under the form of SIR constraints that are recognized as satisfied when they actually are not; coverage plans can thus actually be wrong (see [26; 46; 47] and especially [54] for a more specialistic discussion, attributing errors to floating-point arithmetic used in solvers). As a consequence, if we use DVB-MILP, we can hope to get reliable and optimal solutions only for small-sized instances, while, in the case of large realistic instances, even getting solutions of reasonable quality can represent a major challenge for state-of-the-art optimization software. It is relevant to remark that, though such issues are known, only few works have tried to tackle them (we refer the reader to [26; 33] for a survey of such works). Our new matheuristic addresses the highlighted difficulties, in particular by also using a strengthened optimization model obtained according to the procedure presented below. The first step to obtain a model mathematically stronger than DVB-MILP is to discretize the power emissions of stations: we define a set \(\mathcal{P}=\{P_{1},\ldots,P_{m}\}\) of power values that represent feasible power emissions of any station and we introduce the set of corresponding power level indices \(L=\{1,2,\ldots,m\}\). The second step consists of replacing each continuous power variable \(p_{sd}\) with the linear combination of a set of new binary variables \(z_{sdl}\in\{0,1\}\) that multiplies the feasible power values of \(\mathcal{P}\):  
\[p_{sd}=\sum_{l\in L}P_{l}\cdot z_{sdl}\.\]  
A variable \(z_{sdl}\) is such that:  
\[z_{sdl}=\left\{ \begin{array}{ll}1&\text{if $s\in S$ emits with power value $P_{l}$ in direction $d$}\\ 0&\text{otherwise.}\end{array} \right.\]  
Moreover, we must impose that every station \(s\in S\) emits by one single power value. Therefore, for every station \(s\) and direction \(d\), it is necessary to add the following constraint  
\[\sum_{l\in L}z_{sdl}\leq 1\]  
for each station \(s\) and direction \(d\) (note that having \(\sum_{l\in L}z_{sdl}=0\) corresponds to a non-activated station emitting at zero power). Such constraints go under the name of Generalized Upper Bound (GUB) constraints. By exploiting the new binary power emission variables, we obtain the following new purely binary version of SIR constraints:  
\[\sum_{\sigma\in\mathcal{U}(s,t)}a_{t\sigma}\cdot\left(\sum_{l\in L}p_{l}\cdot z _{\sigma\delta(\sigma,t)l}\right)-\phi\sum_{\sigma\in\mathcal{I}(s,t)}a_{t \sigma}\cdot\left(\sum_{l\in L}p_{l}\cdot z_{\sigma\delta(\sigma,t)l}\right)+ M(1-x_{ts})\ \geq\ \phi\cdot N. \tag{8}\]  
We denote by DVB-PI the Power-Indexed (PI) version of DVB-MILP that employs the binary variables \(z_{sdl}\) and includes the modified SIR constraints (8) and the corresponding GUB constraints. Expliting the presence of the GUB constraints, following the approach initially proposed in [26; 33], we can replace the SIR constraints in Equation (8) with a set of _GUB cover inequalities_. For an exhaustive introduction to simple and GUB cover inequalities and to their GUB version, we refer the reader to [53; 56].