# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 5 Dantzig-Wolfe Reformulation and CG Matheuristics
### Extended Formulation and Column Generation  
Similarly to [11], we have an extended MILP formulation by enumerating all possible (and non empty) routes \(\mathcal{P}_{i}\) for each technician \(i\). The cost of a route \(p\in\mathcal{P}_{i}\) is denoted \(L_{i,p}\). The variables of the MILP formulation are \(z_{i,p}\in\{0,1\}\) such that \(z_{i,p}=1\) if route \(p\in\mathcal{P}_{i}\) is chosen, and \(y_{j}\in\{0,1\}\) with \(y_{j}=1\) if job \(j\) is not planned. For all \(j\in\mathcal{J}\) and \(p\in\mathcal{P}_{i}\), we used the characteristics function \(\mathbbm{1}_{j\in p}\in\{0,1\}\) defined with \(\mathbbm{1}_{j\in p}=1\) if and only if job \(j\) is realized in route \(p\). TRPTW can be written as the following extended MILP. \[\min_{y,z} \sum_{i\in\mathcal{I}}\sum_{p\in\mathcal{P}_{i}}L_{i,p}z_{i,p}+ \sum_{j\in\mathcal{J}}P_{j}y_{j} \tag{27}\] \[s.t: \sum_{i\in\mathcal{I}}\sum_{p\in\mathcal{P}_{i}}\mathbbm{1}_{j \in p}z_{i,p}+y_{j}\geqslant 1\quad\forall j\in\mathcal{J},\] (28) \[\sum_{p\in\mathcal{P}_{i}}z_{i,p}\leqslant 1 \forall i\in\mathcal{I},\] (29) \[z_{i,p},y_{j}\in\{0,1\} \tag{30}\]  
Contraints (28) express that a job \(j\) is either postponed in the case \(y_{j}=1\) or at least in one of the selected routes. Note that, here, elementarity is not a necessary condition; it is implied by the optimality with triangle inequality and not necessary for the validity of the MILP formulation contrary to previous compact MILP formulations. Constraints (29) enforce that at most one route is chosen for each technician, and it is possible to have only zeros for technicians that are not leaving their depots. The difficulty is that \(\mathcal{P}_{i}\) cannot be enumerated. The LP relaxation of this extended MILP formulation is solved by the CG algorithm, adding iteratively new routes. By having a subset of routes \(\mathcal{C}_{i}\subset\mathcal{P}_{i}\), the Restricted Master Problem (RMP) denotes the previous LP relaxation applied to a subset of variables. \[ \begin{array}{lcl}\text{RMP}(\mathcal{C}_{i})=\min_{z_{i,p},y_{j}>0}&\sum_{ i\in\mathcal{I}}\sum_{p\in\mathcal{C}_{i}}L_{i,p}z_{i,p}+\sum_{j\in\mathcal{J}}P_{j}y _{j}&\\ s.t:&\sum_{i\in\mathcal{I}}\sum_{p\in\mathcal{C}_{i}}\mathbbm{1}_{j\in p}z_{i, p}+y_{j}\geqslant 1\quad(\pi)\quad\forall j\in\mathcal{J},\\ &\sum_{k\in\mathcal{C}_{i}}z_{i,p}\leqslant 1\quad\quad\quad\quad\quad\quad\quad (\sigma)\quad\forall i\in\mathcal{I},\end{array}  \tag{31}\]  
\(\pi\) and \(\sigma\) denote, respectively, the dual variables associated with the constraints (28) and (29). The RMP is always feasible as it contains a solution with empty routes for technicians and the maximal number of penalization. Using strong duality, the dual problem of continuous RMP (31) is feasible and has the same value as the primal problem. \[\text{RMP}(\mathcal{C}_{i})=\max_{\pi,\sigma\geqslant 0} \sum_{j\in\mathcal{J}}\pi_{j}-\sum_{i\in\mathcal{I}}\sigma_{i} \tag{32}\] \[\forall i\in\mathcal{I},\forall p\in\mathcal{C}_{i}, -\sigma_{i}+\sum_{j\in\mathcal{J}}\mathbbm{1}_{j\in p}\pi_{j} \leqslant L_{i,p}\quad(z_{i,p})\] (33) \[\forall j\in\mathcal{J}, \pi_{j}\leqslant P_{j} (y_{j}) \tag{34}\]  
In the dual areas, cuts have to be added until there is no violation of constraints (33). The reduced cost associated to a route \((i,p)\) appears; \(RC_{i,p}=L_{i,p}+\sigma_{i}-\sum_{j\in\mathcal{J}}\mathbbm{1}_{j\in p}\pi_{j}\). Variables must be added in the RMP if their reduced cost is strictly negative. If the remaining variables have a positive reduced cost, the RMP gives the LP relaxation of (27)-(29). Thisnegativity question among a non-enumerable set is formulated as an optimization problem, minimizing the reduced costs of the columns that are not in \(\cup_{i}\mathcal{C}_{i}\). These negativity questions are decomposed for all technicians, \(RC^{*}=\min_{i}RC^{*}_{i}\), where \(RC^{*}_{i}\) is the minimization problem over the possible routes for technician \(i\), and \(RC^{*}\geqslant 0\) ensures that the RMP gives the LP relaxation of (27)-(29).