## 5 Computational Experiments
### Performance Analysis
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline
**Instance** & **Optimum** & **LB** & **Gap (\%)** & **LB** & **Gap (\%)** & **LB** & **Gap (\%)** & **LB** & **Gap (\%)** & **Gap (\%)** \\  & & \(M_{C},M_{W},M_{M}\) & & \(M_{C}^{+},M_{M}^{+}\) & & **SR** & & **F4** & & \([LB_{F4}]\) \\ \hline p6-6-15-0 & 7 & 1.80 & 74.29 & 4.84 & 30.85 & 6.00 & 14.29 & **6.19** & **11.57** & **0.00** \\ p6-6-15-1 & 7 & 1.87 & 73.33 & 4.78 & 31.78 & 6.00 & 14.29 & **6.34** & **9.43** & **0.00** \\ p6-6-15-2 & 7 & 1.60 & 77.14 & 4.38 & 37.49 & 6.00 & 14.29 & **6.01** & **14.14** & **0.00** \\ p6-6-15-3 & 7 & 1.67 & 76.19 & 4.37 & 37.55 & 6.00 & 14.29 & **6.13** & **12.43** & **0.00** \\ p6-6-15-4 & 8 & 2.53 & 68.33 & 5.53 & 30.82 & 6.00 & 25.00 & **6.84** & **14.50** & **12.50** \\ \hline p7-7-15-0 & 8 & 2.27 & 71.67 & 5.41 & 32.32 & 7.00 & 12.50 & **7.70** & **3.75** & **0.00** \\ p7-7-15-1 & 8 & 2.60 & 67.50 & 5.51 & 31.09 & 7.00 & 12.50 & **7.11** & **11.13** & **0.00** \\ p7-7-15-2 & 8 & 1.87 & 76.67 & 5.03 & 37.08 & 7.00 & 12.50 & 7.00 & 12.50 & 12.50 \\ p7-7-15-3 & 9 & 2.40 & 73.33 & 5.94 & 34.01 & 7.00 & 22.22 & **7.70** & **14.44** & **11.11** \\ p7-7-15-4 & 8 & 1.67 & 79.17 & 4.42 & 44.70 & 6.00 & 25.00 & **6.89** & **13.88** & **12.50** \\ \hline p8-8-15-0 & 9 & 2.53 & 71.85 & 6.13 & 31.90 & 7.00 & 22.22 & **8.13** & **9.67** & **0.00** \\ p8-8-15-1 & 8 & 2.33 & 70.83 & 5.51 & 31.07 & 7.00 & 12.50 & **7.52** & **6.00** & **0.00** \\ p8-8-15-2 & 9 & 2.13 & 76.30 & 5.81 & 35.50 & 8.00 & 11.11 & **8.06** & **10.44** & **0.00** \\ p8-8-15-3 & 9 & 2.13 & 76.30 & 5.61 & 37.66 & 8.00 & 11.11 & **8.07** & **10.33** & **0.00** \\ p8-8-15-4 & 9 & 2.40 & 73.33 & 6.04 & 32.90 & 8.00 & 11.11 & 8.00 & 11.11 & **11.11** \\ \hline p9-9-10-0 & 9 & 2.60 & 71.11 & 6.45 & 28.32 & 8.00 & 11.11 & **8.50** & **5.56** & **0.00** \\ p9-9-10-1 & 8 & 2.50 & 68.75 & 5.65 & 29.34 & 8.00 & 0.00 & 8.00 & 0.00 & 0.00 \\ p9-9-10-2 & 8 & 2.20 & 72.50 & 5.40 & 32.48 & 7.00 & 12.50 & **7.68** & **4.00** & **0.00** \\ p9-9-10-3 & 9 & 2.30 & 74.44 & 5.80 & 35.53 & 8.00 & 11.11 & **8.14** & **9.56** & **0.00** \\ p9-9-10-4 & 9 & 2.80 & 68.89 & 5.96 & 33.83 & 8.00 & 11.11 & **8.58** & **4.67** & **0.00** \\ \hline p10-10-10-0 & 10 & 2.90 & 71.00 & 6.55 & 34.50 & 9.00 & 10.00 & 9.00 & 10.00 & **10.00** \\ p10-10-10-1 & 10 & 3.10 & 69.00 & 7.22 & 27.84 & 9.00 & 10.00 & 9.00 & 10.00 & **10.00** \\ p10-10-10-2 & 10 & 3.70 & 63.00 & 7.28 & 27.25 & 9.00 & 10.00 & **9.50** & **5.00** & **0.00** \\ p10-10-10-3 & 10 & 3.60 & 64.00 & 8.15 & 18.52 & 9.00 & 10.00 & **9.35** & **6.50** & **0.00** \\ p10-10-10-4 & 10 & 3.40 & 66.00 & 7.29 & 27.13 & 9.00 & 10.00 & **9.18** & **8.20** & **0.00** \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of the linear relaxation of Formulation 4 _vs._ the linear relaxations of the formulations described in [17; 18; 15; 17; 19] when considering the instances of the minimum cardinality segmentation problem (MCSP) described in [10]. 0% in 72% of the instances analyzed. In accordance with [9], provided a tight primal bound for the problem, this fact can be used to speed up or to even avoid the use of the exhaustive search. A drawback of current implementation of Formulation 4 is represented by the solution times which usually are longer than those described in [9; 10]. In particular, computational experiments have shown that the branch-and-price approach for Formulation 4 is unable to solve any of the considered instances within the time limit. This fact appears to be due to a number of technical details related to the implementation of Formulation 4, included the choice of the primal bound, the branching rules, the poor current ability to handle the combined partition network and the use of an interpreted