# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 5 Dantzig-Wolfe Reformulation and CG Matheuristics
### Tabu Search Intensification  
A general difficulty to implement CG algorithms is that dual variables converge erratically. This is closely related to properties of linear optimization as the optimums are extreme points. A consequence for CG algorithm is that many iterations are necessary to have good dual variables to generate the most appropriate columns, with an erratic convergence of dual variables. Stabilization techniques enforce smoothing the convergence of dual variables in order to reduce the number of iterations that converge for the CG algorithm and, thus, reduce the computation time needed for CG convergence. Mathematical properties can not only be exploited for stabilization but also heuristics [75].  
This section is motivated by the following fact: Many good columns can be obtained with slight modifications from a good column. At one iteration, high values of \(\pi\) indicate the jobs that are likely used in a new column. A kernel of jobs with high \(\pi_{j}\) values can be combined in several interesting columns regarding the reduced costs. Using such a property, it is interesting to aggressively generate columns with local search moves from interesting columns. This section introduces a Tabu Search (TS) matheuristic to generate quickly a pool of good solutions.  
Let \(x_{i,j}=\sum_{n^{\prime}\in\mathcal{N}_{i}}u_{i,j,n^{\prime}}\), the binaries indicating if technician \(i\in\mathcal{I}_{0}\) realizes job \(j\). Having \(M\) feasible solutions as previously calculated, we denote with \(\bar{x}_{i,j}^{m}\) the value of these variables. To forbid already generated columns, we add the following \"no-good-cuts\" constraints similarly to [76], which defines a variable fixing strategy.  
\[\forall m\in\llbracket 1,M],\sum_{i,j:\underline{x}_{i,j}^{m}=1}(1-x_{i,j}^{m})+ \sum_{i:j:\underline{x}_{i,j}^{m}=0}x_{i,j}^{m}\geqslant 1 \tag{42}\]In order to search around the last solution \(\tilde{x}^{M}_{i,j}\), allowing \(K\) modifications from the \(M\)-th solution, it can also be written as a linear constraint that defines a variable fixing strategy.  
\[\sum_{i,j;\tilde{x}^{M}_{i,j}=1}(1-x^{M}_{i,j})+\sum_{i,j;\tilde{x}^{M}_{i,j}=0}x ^{M}_{i,j}\leqslant K \tag{43}\]  
These constraints allow generating a TS procedure in Algorithm 8 in order to aggressively generate columns. In the case of the classic CG algorithm, the input for \(\mathcal{I}_{0}\) is a singleton. Adding such constraints in the CG sub-problems can be solved with Branch and Bound for small MILP computations. For larger MILP computations, these constraints respect the structures of the MILP matheuristics in order to quickly find good solutions. We note that the aggressive generation of negatively reduced cost columns with a tabu search was also introduced in [77] for a significative acceleration of CG in practice.  
```
- \(\mathcal{I}_{0}\) a subset of technicians
- the current value in the RMP of dual variables \((\sigma,\pi)\)
- a set of initial columns \(c\in\prod_{i\in\mathcal{I}_{0}}\mathcal{P}_{i}\) with a negative reduced cost in (35)
- an integer \(M\in\mathbb{N}\), a maximal number of TS iterations
- an integer \(K\in\mathbb{N}\), a maximal number of assignment modifications TSintensification\((\mathcal{I}_{0},K,M)\)  //Initialization:  MILP, a MILP formulation for (35) related to technician \(i\)  \(p=c\) initial columns  Taboo list of columns \(l=\{c\}\)  an integer \(n=0\) to denote iterations  //Loop to generate columns with negative reduced costs do:  Add constraint (43) in MILP with columns of \(p\)  Add constraint (42) in MILP with columns of \(p\)  solve MILP  remove constraint (43) in MILP with columns of \(p\)  update \(p\), the optimal columns in the last MIP  update \(l\) adding the columns of \(p\) with a negative reduced cost in \(l\) while\(n<M\) and ReducedCost\((p)<0\) return\(l//\) the list of columns to add in the next RMP
```  
**Algorithm 8** Tabu search intensification