# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 5 Dantzig-Wolfe Reformulation and CG Matheuristics
### POPmusic-CG Decomposition  
Dual variables associated with jobs can be interpreted as marginal costs to realize such jobs. When continuous RMP does not use any variable visiting a job \(j\), we have \(\pi_{j}=P_{j}\). When the dual variables are not stabilized, it induces sub-problems generating columns with jobs with the highest values \(\pi_{j}\) in (35). Hence, independent computations of (35) are likely to visit the same jobs, with the highest values of \(\pi_{j}\). These generated columns are likely to be redundant in the recombination induced by the next RMP computation. It suggests incorporating diversification in the CG algorithm. We investigate combined subproblems for a subset of technicians \(\mathcal{I}_{0}\subset\mathcal{I}\) (typically two or three technicians), imposing a total diversification in these sub-problems with the following MILP formulation.  
\[RC^{*}_{\mathcal{I}_{0}}= \min_{u,t}\,\sum_{i\in\mathcal{I}_{0}}\left(\sigma_{i}+\sum_{n,n^{ \prime}\in\mathcal{N}_{i}}(D_{n,n^{\prime}}-\pi_{j})u_{i,n,n^{\prime}}\right)\] \[s.t:\forall j\in\mathcal{J} \sum_{i\in\mathcal{I}_{0}}\sum_{n\in\mathcal{N}_{i}}u_{i,j,n}\leqslant 1\] \[\forall i\in\mathcal{I}_{0},\forall j\in\mathcal{J}, \sum_{n\in\mathcal{N}_{i}}u_{i,n,j}=\sum_{n^{\prime}\in\mathcal{N} _{i}}u_{i,j,n^{\prime}}\] \[\forall i\in\mathcal{I}_{0},\forall n\in\mathcal{N}_{i}, \sum_{n^{\prime}\in\mathcal{N}_{i}}u_{i,n,n^{\prime}}=1\] \[\forall i\in\mathcal{I}_{0},\forall j\in\mathcal{J}, u_{i,j,j}\leqslant 0\] \[\forall i\in\mathcal{I}_{0},\forall(j,j^{\prime})\in\mathcal{J}^{2}, t_{j}+L_{j}+T_{j,j^{\prime}}\leqslant t_{j^{\prime}}+\left(1-u_{i,j,j^{ \prime}}\right)\cdot M_{i,j}^{3}\] \[\forall i\in\mathcal{I}_{0},\forall j\in\mathcal{J}, T_{i}^{start}+T_{i,j}\leqslant t_{j}+\left(1-u_{i,i,j}\right)\cdot M_{i,j}^{2}\] \[\forall i\in\mathcal{I}_{0},\forall j\in\mathcal{J}, t_{j}+L_{j}+T_{i,j}\leqslant T_{i}^{end}+\left(1-u_{i,j,i}\right)\cdot M_{j,j ^{\prime}}^{1}\] \[\forall j\in\mathcal{J} \sum_{i\in\mathcal{I}_{0}}\sum_{n\in\mathcal{N}_{i}}u_{i,n,n^{ \prime}}\in\{0,1\}\]  
Sup-problem (36) can be seen as a concatenation of the technician sub-problems (35) in \(\mathcal{I}_{0}\subset\mathcal{I}\). The first constraint enforces that each job can be affected with respect to at least one technician in \(\mathcal{I}_{0}\) for a total diversity among the new columns. One may consider a multi-objective extension and generate columns for \(\mathcal{I}_{0}\subset\mathcal{I}\) and consider the partial diversity in another objective.  
The process gives rise to Algorithm 6, where the partitions of technicians vary each iterations, similarly to POPMUSIC heuristics (Partial optimization metaheuristic under special intensification conditions [72]). Note than POPMUSIC matheuristics are efficient as primal heuristics without computations of dual bounds for vehicle routing problems [74].  
```
\(\mathcal{C}\) set of initial columns. do:  solve RMP (31) with columns defined in \(\mathcal{C}\)  store dual variables \(\sigma\) and \(\pi\) and optimal cost from (31)  compute \(\mathcal{P}_{I}\) a partition of \(\mathcal{I}\) in small subsets for each subset \(\mathcal{I}_{0}\in\mathcal{P}_{I}\) :  solve (36) with a matheuristic with last \((\sigma,\pi)\) values for each column \(c\) with a negative reduced cost  add the column to \(\mathcal{C}\) endfor while: columns are added in \(\mathcal{C}\) return the last cost of the RMP (31) and updated set of columns \(\mathcal{C}\)
```  
**Algorithm 6** POPMUSIC column generation algorithm