## 4 Mathematical Programming Relaxations
### Preprocessing Reductions and Dual Bounds  
This section aims to reduce the size of the MILP computation to provide dual bounds. The crucial point is to prove that the pre-processing reductions are exact processing operations, valid for optimal solutions of \(LB\) or \(LB(k)\) relaxations, or guarantee to provide lower bounds for \(LB\) or \(LB(k)\). Firstly, we mention the results proven in [17] that, under some conditions, time step aggregations applied to problems \(LB\) or \(LB(k)\) provide dual bounds for \(LB\) and \(LB(k)\). Therefore, we denote the following MILP as a general expression for \(LB\) or \(LB(k)\):  
\[ \begin{array}{ll}v=\min_{x,y}&c_{x}x+\sum_{t}\mathbf{F}_{t}c_{t}y_{t}\\ s.t:&T^{1}x+\sum_{t}\mathbf{F}_{t}W^{1}y_{t}&\geqslant h^{1}\\ \forall t,&T^{2}_{t}x+W^{2}y_{t}&\geqslant h^{2}_{t}\end{array}  \tag{39}\]  
Here, \(y_{t}\geqslant 0\) denotes the time-indexed variables, i.e., the production variables \(p^{T2}_{i,k,s,t}\) and \(p^{T1}_{j,s,t}\), whereas \(x\) denotes the vector of the other variables. A first important point is to notice that \(W^{1},W^{2}\) do not depend on \(t\) in the MILP equations defining \(LB\) and \(LB(k)\). Two additional hypotheses are crucial. Firstly, \(\mathbf{F}_{t}\) is constant over time, and we denote \(\mathbf{F}=\mathbf{F}_{t}\) in that context. Secondly, we have to suppose that T1 production costs are constant over weeks, defining \(c_{w}\) quantities:  
\[\forall w\in\mathcal{W},\forall(t,t^{\prime}),w_{t}=w_{t^{\prime}}\Longrightarrow c _{t}=c_{t^{\prime}}=c_{w} \tag{40}\]  
To define the time step aggregated version of (39), we define \(\alpha=\mathbf{F}/128\), representing the proportion of a time period in a weekly period, and the aggregations \(T^{2}_{w}=\sum_{t,w_{t}=w}\alpha T^{2}_{t}\), \(h^{2}_{w}=\sum_{t,w_{t}=w}\alpha t^{2}_{t}\). Defining weekly production variables \(y_{w}\), which represent \(y_{w}=\sum_{t,w_{t}=w}\alpha y_{t}\), we have the following aggregated version of MILP (39):  
\[ \begin{array}{ll}v_{agg}=\min_{x,y\geqslant 0}&c_{x}x+\sum_{w} \mathbf{F}c_{w}y_{w}\\ s.t:&T^{1}x+\sum_{w}\mathbf{F}W^{1}y_{w}\geqslant h^{1}\\ \forall w,&T^{2}_{w}x+W^{2}y_{w}\geqslant h^{2}_{w}\end{array}  \tag{41}\]  
Proposition 2: _If the hypothesis (40) is valid, aggregating production time steps to weeks provide a dual bound for the disaggregated problem: \(v_{agg}\leqslant v\). Dual bounds for the EURO/ROADEF Challenge 2010 can be computed from the time -step aggregated versions of \(LB\) and \(LB(k)\) under the hypothesis that (40) is fulfilled._  
We mention and prove now two propositions allowing for dealing with less variables in the previous MILP computations giving dual bounds for the EURO/ROADEF Challenge 2010. Propositions 3 and 4 are exact pre-processing results, allowing for deleting some variables in the MILP computations. Proposition 3: _Denoting \(\mathbf{L}_{i,k}=\left\lceil\frac{W}{T}\frac{\mathbf{Rmin}_{i,k}-\mathbf{A}_{ i,k}}{\mathbf{F}_{t}}\right\rceil\) with \(P_{i}=\max_{t}\mathbf{Pmax}_{i,t}\), \(\mathbf{To}_{i,k}\) and \(\mathbf{Ta}_{i,k}\) can be strengthened in \(\widetilde{T}_{i,k}\) and \(\widetilde{T}_{i,k}\) with induction relations:_  
\[\forall i\in\mathcal{I},k>0,\quad\widetilde{T}_{0i,k}=\max(\mathbf{T}\mathbf{ o}_{i,k},\widetilde{T}_{0i,k-1}+\mathbf{Da}_{i,k-1}+\mathbf{L}_{i,k}) \tag{42}\]  
\[\forall i\in\mathcal{I},k<K,\quad\widetilde{T}_{i,k}=\min(\mathbf{Ta}_{i,k}, \widetilde{T}_{0i,k+1}-\mathbf{Da}_{i,k}-\mathbf{L}_{i,k}) \tag{43}\]\(\widetilde{To}_{i,k}\) are first tightened by induction with \(k\) increasing, and then \(\widetilde{Ta}_{i,k}\) are computed using \(\widetilde{To}_{i,k}\) values._  
Proof. : \(\mathbf{L}_{i,k}=\left\lceil W\frac{\mathbf{Rmin}_{i,k}-\mathbf{A}_{i,k}}{ \mathbf{F}TP_{i}}\right\rceil\) is a first lower bound for the length of production cycle \((i,k)\).