# Matheuristics and Column Generation for a Basic Technician Routing Problem
## 4 Matheuristics Based on Compact MILP Formulations
### MILP Neighborhoods for Local Optimizations  
Neighborhoods and heuristic operators can be designed generically from an MILP formulation defining a sub MILP of reduced size (that can be parametric) and imposing values relative to some variables. Such local optimization solving sub-MILP are used in \"variable fixing\" heuristics (as in [5]) or in Fix-and-Optimize (FO) (as in [70]). In special cases, heuristic operators and local optimization can be implemented without using MILP computations; the computational experiments aim to provide results with respect to designing operators for the TRPTW problem and to select the promising operators that require careful implementation.  
Commonly to the two last MILP formulations, different variable fixing strategies are processed on assignments \(x_{i,j}\in\{0,1\}\) for \(i\in\mathcal{I}\), with \(x_{i,j}=1\) if and only if job \(j\) is realized by technician \(i\). \(x_{i,j}\) is binary and a linear expression of previous variables \(u_{i,j,n}\) and \(z_{i,j,n^{\prime},k}\).  
\[\forall i\in\mathcal{I},\forall j\in\mathcal{J}_{i},\quad x_{i,j}=\sum_{n\in \mathcal{N}_{i}}u_{i,j,n}=\sum_{k=1}^{K_{i}}\sum_{n^{\prime}\in\mathcal{N}_{i }}z_{i,j,n^{\prime},k}\in\{0,1\} \tag{22}\]  
A constraint \(x_{i,j}=0\) for a given \(i\in\mathcal{I}\) and \(j\in\mathcal{J}\) imposes that variables \(u_{i,j,n},u_{i,n,j}\) or \(z_{i,j,n,k}\) are zeros for all \(k\) and \(n\in\mathcal{N}\). A constraint \(x_{i,j}=1\) for a given \(i\in\mathcal{I}\) and \(j\in\mathcal{J}\) imposes that variables \(u_{i^{\prime},j,n},u_{i^{\prime},nj}\) or \(z_{i^{\prime},j,n,k}\) are zeros for all \(j^{\prime},k\) and \(i^{\prime}\
eq i\) with elementarity constraints (2) and (13). Such choices of fixing variables allow having balanced sub-problems as in divide-and-conquer strategies instead of the straightforward fixing on original variables \(u_{i,j,n}\) and \(z_{i,j,n^{\prime},k}\), which results in unbalanced sub-problems. This is denoted with the fixing operator \(\mathcal{F}^{assign,=}\).  
\[\mathcal{F}^{assign,=}_{i,j}(b):\qquad\quad x_{i,j}=b,\qquad\qquad\forall i\in \mathcal{I},\forall j\in\mathcal{J},\forall b\in\{0,1\} \tag{23}\]  
A variant is the fixing operator \(F^{assign,\leqslant}\) with inequality constraints. A constraint \(x_{i,j}\leqslant 0\) is equivalent to \(x_{i,j}=0\) such as previously described, and a constraint \(x_{i,j}\leqslant 1\) allows another technician to realize job \(j\).  
\[\mathcal{F}^{assign,\leqslant}_{i,j}(b):\qquad\quad x_{i,j}\leqslant b,\qquad \qquad\forall i\in\mathcal{I},\forall j\in\mathcal{J},\forall b\in\{0,1\} \tag{24}\]Previous strategies limit the assignments between jobs and technicians. One may wish to impose some orders in the interventions processed by a given technician. Additional constraints \(t_{j}\leqslant t_{j^{\prime}}\) are little nretest as they are almost always non active in the B&B search because of the weakness of big M constraints. Hence, a fixing strategy is based on the implications on the \(u_{i,n,n^{\prime}}\) or \(z_{i,n,n^{\prime},k}\) variables.  
\[\mathcal{F}^{order}_{i,j,j^{\prime}}: u_{i,j,j^{\prime}}=\sum_{k=1}^{K_{i}}z_{i,j,j^{\prime},k}=0, \forall i\in\mathcal{I},\forall(j,j^{\prime})\in\mathcal{J}_{i}^{2} \tag{25}\]  
With many constraints \(\mathcal{F}^{order}_{i,j,j^{\prime}}\), it breaks possibilities of sub-tours, which has positive impacts for the LP relaxation quality and the B&B solving capacities of such reduced MILP.