## 3 New Compact Models
### The Reduced Model  
It can be observed that by removing the set of constraints (4)-(6) from the model described in Section 3.1, the set of constraints (11) in general still enforces the precedence relationships between \(s\) and \(t\) with \((s,t)\in R\), apart from the following special case. A directed path that visits \(t\) before visiting \(s\) implies that \(d_{t}\leq d_{s}\), which violates the set of constraints (11). However, the set of constraints (11) might fail to enforce a precedence relationship between \(s\) and \(t\) if a zero-cost path in \(G\) that reaches \(s\) from \(t\) exists. Therefore, variables \(u_{j}^{t}\) and constraints (4)-(6) need to be defined only for those \(t\) for which there exist at least an \(s\) for which \((s,t)\in R\) and a zero-cost path that connects \(t\) to \(s\) is available in \(G\)  
Figure 2: Example of how a precedence-violating path is detected using constraints (4)–(6).  
The identification of such pairs \((s,t)\in R\) for which a zero-cost path exists has, however, to be performed in a preprocessing phase, adding some complexity to the overall process. The procedure we devised for the retrieval of such pairs will be detailed in Section 3.2.1.  
The reduced set of constraints can be described formally as follows. Let \(G_{0}\;=\;(V_{0},\;A_{0},\;R)\) be the graph obtained from \(G\) by considering only arcs with cost zero and the relevant nodes. Therefore, \(A_{0}=\{(i,j)\in A\,|\,c_{ij}=0\}\) and \(V_{0}=\{i\;\in\;V\,|\,\exists j\;\in\;V:(i,j)\in A_{0}\text{ or }(j,i)\in A_{0}\}\) (a node is considered relevant for the residual precedence constraints if it has at least an outgoing or incoming zero-cost arc). Let \(SP_{ij}\subseteq A_{0}\) be a shortest path that starts from \(i\) to \(j\) in \(G\), and let \(c(SP_{ij})=\sum_{(k)\in SP_{ij}}c_{kl}\) be its cost. For each \(t\in V^{R}\), let \(V_{0}(t)=\{s\in V_{0}\,|\,\exists\,(s,t)\in R\text{ with }c(P_{ls})=0\}\) be the set of vertices involved in a precedence constraint with \(t\) as a head, and such that a zero-cost path from \(t\) to \(s\) exists. Finally, let \(V_{0}^{R}=\{t\in V^{R}\,|\,V_{0}(t)\
eq\mathcal{O}\}\) be the set of vertices involved as a head in at least one precedence constraint for which an inverse zero-cost path exists.  
The _Reduced_ model can be obtained from the _Complete_ model described in Section 3.1 by substituting constraints (4)-(6) and (14) with the following specialized version of them, characterized by a reduced domain:  
\[u_{s}^{t} =0 \forall t\in V_{0}^{R},s\in V_{0}(t) \tag{17}\] \[u_{t}^{t} =1 \forall t\in V_{0}^{R}\] (18) \[u_{j}^{t} -u_{i}^{t}-x_{ij}\geq-1 \forall t\in V_{0}^{R},(i,j)\in A_{0}\] (19) \[u_{j}^{t} \geq 0 \forall t\in V_{0}^{R},j\in V_{0} \tag{20}\]  
Notice that the domain of the \(u\) variables is reduced according to (20).  
Compared to the model introduced in Section 3.1, and given that zero-cost paths are rare, the _Reduced_ model uses less variables and constraints (although the theoretical complexity remains unchanged), thus further reducing the memory footprint. However, it might be characterized by a weaker linear relaxation due to the elimination of redundancy in the constraints, on top of having the burden of a preprocessing phase.