# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 6 Computational Results
### MILP Formulations Results
#### 6.2.1 Solving CG Sub-Problems  
If CG sub-problems with one technician having a similar polyhedral structure with the entire compact MILP formulation, the efficiency of straightforward MILP solving is very different. For some mid size instances, it can be less time consuming to solve the entire MILP with a compact formulation rather than solving a single technician CG sub-problem. It is paradoxical, and DW reformulation decomposes the original MILP with iterations of smaller problems. The reason for such paradoxical situations is that sub-problems are of a different nature. Seeing CG sub-problems as shortest path problems, many distances are negative in providing a negatively reduced cost. In the original MILP problems, all the distances are positive. For sub-problems, cycles with negatively reduced cost may appear, and this tends to produce many sub-tours with negatively reduced costs in continuous \begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline  & **(1)–(8)** & **(1)–(8)** & **(1)–(8)** & **(1)–(8)** & **(12)–(19)** & **(12)–(19)** & **(12)–(19)** & **(27)–(29)** \\
**Bound** & **LP** & **nod1** & **LP** & **nod1** & **LP** & **nod1** & **LP** & **nod1** & **LP** \\
**Cuts** & **No** & **No** & (10) & **(10)** & **No** & **No** & **(21)** & **(21)** & **No** \\ \hline data\_3\_1\_10 & 45.7\% & 8.7\% & 11.9\% & 3.2\% & 28.1\% & 3.3\% & 8.8\% & 1.0\% & 1.8\% \\ data\_3\_5\_10 & 43.4\% & 0.0\% & 9.7\% & 0.0\% & 23.4\% & 0.0\% & 8.0\% & 0.0\% & 0.0\% \\ \hline data\_5\_1\_20 & 44.8\% & 29.5\% & 27.9\% & 11.6\% & 35.7\% & 17.9\% & 22.0\% & 13.7\% & 1.9\% \\ data\_5\_3\_20 & 52.7\% & 30.3\% & 30.8\% & 17.7\% & 39.0\% & 19.9\% & 22.7\% & 15.5\% & 0.6\% \\ data\_5\_5\_20 & 58.1\% & 28.7\% & 27.5\% & 14.6\% & 42.1\% & 18.5\% & 25.1\% & 14.1\% & 0.3\% \\ \hline data\_8\_1\_20 & 40.5\% & 20.6\% & 20.8\% & 10.6\% & 32.6\% & 10.6\% & 16.8\% & 7.8\% & 1.3\% \\ data\_8\_3\_20 & 54.7\% & 28.5\% & 28.6\% & 17.1\% & 35.2\% & 14.8\% & 20.0\% & 11.2\% & 1.8\% \\ data\_8\_5\_20 & 60.6\% & 26.7\% & 25.9\% & 11.2\% & 39.7\% & 8.1\% & 21.3\% & 1.6\% & 0.5\% \\ \hline data\_10\_10\_40 & 55.9\% & 25.0\% & 25.8\% & 14.3\% & 40.8\% & 19.4\% & 20.7\% & 13.9\% & 2.0\% \\ \hline data\_15\_10\_40 & 55.6\% & 18.9\% & 19.6\% & 10.7\% & 35.8\% & 11.0\% & 13.4\% & 6.3\% & 0.6\% \\ data\_15\_20\_40 & 53.9\% & 14.2\% & 16.1\% & 6.1\% & 32.1\% & 7.5\% & 13.1\% & 4.8\% & 0.7\% \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of the average gaps to dual bounds given by some variants of MILP formulations to the optimal solutions on a set of 55 instances solvable to optimality with Cplex. The results are gathered on instances with the same number of technicians, skills and interventions. LP denotes the linear relaxation, whereas nod1 denotes the bounds obtained after the cutting plane passes of Cplex at the root node before branching. relaxations. When solving sub-problems with many sub-tours of negative costs with an MILP solver, the lower bounds are of a poor quality and many sub-tours are generated in many nodes of the B&B tree. This induces that the convergence to optimality is difficult in this case. Note that this critical situation appears more often in the first iterations of the CG algorithm when the dual values are not stabilized and have values of \(\pi_{j}\) in the worst case \(\pi_{j}=P_{j}\) occurs when penalization is used in the RMP in the case of unbalanced dual variables. In the last iterations of the CG algorithm, having more stable dual variables induces less complications, and straightforward MILP solving is more efficient at these iterations compared to the first iterations. A good point is that primal heuristics of MILP solvers (relying on branching, in particular, diving heuristic) remains efficient for finding columns with a negative reduced cost for sub-problems in the first iterations, which is enough to continue the CG algorithm without solving optimality the first sub-problems.