## 5 Computational Experiments
### Implementing Formulation 1  
One of the main difficulties in designing a solution approach for Formulation 1 consists of devising effective branching rules when the binary variables are priced out at run time. In particular, a typical problem is that there may be no easy way to forbid that a variable that was fixed at 0 by branching could still be a feasible solution for the pricing problem. However, if the value of \(H\) is relatively small, it is possible to overcome this issue by branching on \"arc variables\" rather than on \"path variables\". Specifically, let us add in Formulation 1 a new decision (arc) variable \(x_{\alpha}\) equal to 1 if arc \(\alpha\in\mathcal{A}\) is used and 0 otherwise. Then, an alternative formulation for the MCSP is:  
**Formulation 4**. : _- Path-Arc Integer Master Problem (PA-IMP)_  
\[\min\sum_{w=1}^{H}d_{w} \tag{40a}\] \[s.t. d_{w}\geq\sum_{p\in\mathcal{P}_{i}}\ell_{w}(p)\;\lambda_{p}^{i} \forall i\in[m],\forall w\in[H]\] (40b) \[\sum_{p\in\mathcal{P}_{i}}\lambda_{p}^{i}=1 \forall i\in[m]\] (40c) \[\sum_{ \begin{subarray}{c}p\in\mathcal{P}_{i}:\\ \alpha\in p\end{subarray} }\lambda_{p}^{i}\leq x_{\alpha} \forall\alpha\in[\mathcal{A}_{i}],\;\forall i\in[m]\] (40d) \[\sum_{\alpha\in\mathcal{A}_{i}}x_{\alpha}=n-1 \forall i\in[m]\] (40e) \[\lambda_{p}^{i}\in\{0,1\} \forall i\in[m],\;\forall p\in\mathcal{P}_{i}\] (40f) \[x_{\alpha}\in\{0,1\} \forall\alpha\in\mathcal{A}\] (40g) \[d_{w}\in\mathbb{Z}_{+} \forall w\in[H]. \tag{40h}\]  
In particular, Formulation 4 has the same constraints that Formulation 1 plus constraints Equation (40d) that impose that only selected arcs can be used in a path \(p\in\mathcal{P}_{i}\), \(i\in[m]\) and constraints Equation (40e) that impose that in each path in \(D_{i}\) is made up of exactly \(n-1\) arcs. **Proposition 2**. : _In any feasible solution to Formulation 4, the integrality of variables \(x_{\alpha}\) together with constraints Equations (40c) and (40d) suffice to guarantee the integrality of variables \(\lambda_{p}^{i}\)._  
Proof. : Assume by contradiction that there exists a feasible solution to the PA-IMP in which there are both a row \(\tilde{i}\in[m]\) and a path \(p_{\tilde{i}}\) such that \(0<\lambda_{p_{\tilde{i}}}^{\tilde{i}}<1\). Then, due to constraint Equation (40c), there also exists at least another nonzero fractional path variable encoding an alternative path for row \(\tilde{i}\). These two paths must differ for at least one arc. We denote \(\alpha_{1}\) as the arc used by path \(\lambda_{p_{\tilde{i}}}^{\tilde{i}}\) and \(\alpha_{2}\) as the arc used by the other fractional variable. Because of constraint Equations (40d) and (40g), this fact implies that both variables \(x_{\alpha_{1}}\) and \(x_{\alpha_{2}}\) are equal to one, which implies that constraint Equation (40e) must be violated for \(\tilde{i}\). This, in turn, contradicts the feasibility of the solution. An immediate consequence of the above proposition is that  
**Proposition 3**. : _The integrality constraint on variables \(\lambda_{p}^{i}\) in Formulation 4 can be relaxed._  
It is worth noting that the number of arcs in the combined partition network associated with the matrix \(A\) grows exponentially in function of \(H\). Hence, we stress that the introduction of the arc variables is practical only for small values of \(H\). As for Formulation 1, the linear programming relaxation of Formulation 4, denoted as PA-RLMP, can be solved via column generation techniques [23]. To this end, we define the following dual variables associated to constraints Equations (40b)-(40e), namely \(\pi_{i,w}\), for all \(i\in[m]\) and \(w\in[H]\); \(\mu_{i}\), for all\(i\in[m]\); \(\eta_{i\alpha}\), for all \(\alpha\in[\mathcal{A}_{i}]\), \(i\in[m]\); and \(\omega_{i}\), for all \(i\in[m]\).