## 5 Computational Experiments
### Performance Analysis  
Table 1 shows the comparison between the linear relaxation of Formulation 4 and the linear relaxations of the formulations described in [17; 18; 19] when considering [PERSON]'s instances. Some of the values presented in the table refer to the computational tests performed in [PERSON]'s Ph.D. thesis (namely those reported in Tables 2.7 ad 2.8 of [10]). Specifically, the first column provides the name of the instances analyzed. The second column provides the corresponding optimal values. The third column provides the linear programming relaxations of the formulations described in [17; 18; 19], denoted as \(M_{C}\), \(M_{W}\), and \(M_{M}\), respectively. The fourth column provides the values of the _gap_ of formulations \(M_{C}\), \(M_{W}\), and \(M_{M}\) expressed in percentage, _i.e._, the difference between the optimal value to a given instance of the MCSP and the objective function value of the linear programming relaxation at the root node of the respective search tree, divided by the optimal value. The fifth column provides the linear programming relaxations of the formulations \(M_{C}\) and \(M_{M}\) when considering the constraints (16) and (45) in [PERSON]'s Ph.D. thesis (denoted as \(M_{C}^{+}\) and \(M_{M}^{+}\), respectively) and the sixth column provides the corresponding gaps. The seventh and the eighth columns provide the lower bounds and the gaps of the shortest path formulation [15] as modified in [10], hereafter denoted as \"SR\". This formulation consider a relaxation of the MCSP obtained when partitioning the MCSP into a set of independent sub-problems, one for each row of the matrix \(A\). Finally, the ninth column provides the linear programming relaxations of Formulation 4, the tenth column provides the corresponding gaps, and the eleventh column provides the gaps when ceiling the values of the corresponding linear relaxation of Formulation 4. Table 1 shows that the formulations described in [17; 18; 19] are characterized by equal linear relaxations. These values prove to be very poor, by giving rise to gaps that range from 63% for the instance \"p10-10-10-2\" to more than 79% for the instance \"p7-7-15-4\". Stronger lower bounds can be obtained when adding to \(M_{C}\) and \(M_{M}\) the constraints (2.16) and (2.45) described in [PERSON]'s Ph.D. thesis [10]. In this situation, the gaps range from 18.52% for the instance \"p10-10-10-3\" to 44.70% for the instance \"p7-7-15-4\". The lower bounds provided by SR prove to be even tighter, by giving rise to gaps ranging from 0% for the instance \"p9-9-10-1\" to 25% for the instances \"p6-6-15-4\" and \"p7-7-15-4\". The linear relaxations of Formulation 4 prove to be the tightest on the considered instances, by giving rise to gaps that are not worse than to those provided by SR. In particular, Table 1 shows that the gaps of Formulation 4 range from 0% for the instance \"p9-9-10-1\" to 14.50% for the instance \"p6-6-15-4\". A part from specific cases, the percental gain in terms of gap provided by the linear relaxations of Formulation 4 with respect to SR ranges from a minimum 0.15% for the instance \"p6-6-15-2\" to 12.55% for the instance \"p8-8-15-0\". Only for the instances \"p7-7-15-2\", \"p8-8-15-4\", \"p9-9-10-10-1\", \"p10-10-10-0\" and \"p10-10-10-1\" the linear relaxation of Formulation 4 provides lower bounds equal to those provided by SR. It is worth noting that, as the value of the optimal solution to the MCSP has to be integral, the linear relaxation of Formulation 4 can be ceiled. If this operation is performed, we obtain the values reported in column eleventh of Table 1 which show that the gaps of Formulation 4 approach