## C Test Results (DL and MCF comparison)

This appendix includes the detailed test results obtained using the adapted DL and MCF formulations, with SANDA used to prevent less than *p* cycles. Only instances with *n* ≤ 76 were considered, and only the LP gaps were calculated. One last observation is in order: we were so far unable to determine the optimal values of instances brazil58 (with *p* = 4) and pr76 (with *p* = 2). However, we have obtained intervals to which the optimal values are guaranteed to belong. They are [21898.1533, 22211] and [104500, 106362.1561]. To calculate the gaps for these two instances, we have used the upper bounds of the corresponding intervals. Even if these upper bounds are not guaranteed to be the optimal values, the differences in the average gaps should not be substantial, as all other gaps were calculated using the corresponding optimal values.

<table><caption>Table 16: LP gaps (%) obtained with models for the HpMP including the adapted DL and MCF constraints</caption><thead><tr><th rowspan="2">Instance</th><th rowspan="2">p</th><th colspan="2">Model</th></tr><tr><th>DL / SANDA</th><th>MCF / SANDA</th></tr></thead><tbody><tr><td rowspan="3">gr24</td><td>2 = p<sub>1</sub></td><td>1.09%</td><td><strong>0.15%</strong></td></tr><tr><td>3</td><td>0.2%</td><td><strong>0.04%</strong></td></tr><tr><td>4</td><td>0.2%</td><td>0.2%</td></tr><tr><td rowspan="3">fri26</td><td>2 = p<sub>1</sub></td><td>3.4%</td><td><strong>0.71%</strong></td></tr><tr><td>3</td><td>2.55%</td><td><strong>1.44%</strong></td></tr><tr><td>4</td><td>2.76%</td><td><strong>2.43%</strong></td></tr><tr><td rowspan="3">bayg29</td><td>2 = p<sub>1</sub></td><td>1.02%</td><td><strong>0.13%</strong></td></tr><tr><td>3</td><td>0.13%</td><td>0.13%</td></tr><tr><td>4</td><td>0.19%</td><td>0.19%</td></tr><tr><td rowspan="3">swiss42</td><td>2</td><td>3.23%</td><td><strong>0.92%</strong></td></tr><tr><td>3</td><td>2.84%</td><td><strong>2.00%</strong></td></tr><tr><td>4 = p<sub>1</sub></td><td>1.42%</td><td>1.42%</td></tr><tr><td rowspan="3">att48</td><td>2</td><td>3.24%</td><td><strong>2.15%</strong></td></tr><tr><td>3</td><td>1.43%</td><td><strong>1.03%</strong></td></tr><tr><td>4 = p<sub>1</sub></td><td>0.73%</td><td><strong>0.68%</strong></td></tr><tr><td rowspan="3">gr48</td><td>2</td><td>2.81%</td><td><strong>2.00%</strong></td></tr><tr><td>3</td><td>2.05%</td><td><strong>1.76%</strong></td></tr><tr><td>4 = p<sub>1</sub></td><td>1.49%</td><td><strong>1.47%</strong></td></tr><tr><td rowspan="3">hk48</td><td>2</td><td>1.43%</td><td><strong>0.6%</strong></td></tr><tr><td>3</td><td>0.76%</td><td><strong>0.67%</strong></td></tr><tr><td>4 = p<sub>1</sub></td><td>0.66%</td><td><strong>0.65%</strong></td></tr><tr><td rowspan="4">eil51</td><td>2</td><td>1.42%</td><td><strong>1.09%</strong></td></tr><tr><td>3</td><td>0.55%</td><td>0.55%</td></tr><tr><td>4</td><td>0.66%</td><td>0.66%</td></tr><tr><td>p<sub>1</sub></td><td>0.86%</td><td>0.86%</td></tr><tr><td rowspan="4">berlin52</td><td>2</td><td>0.58%</td><td><strong>0.00%</strong></td></tr><tr><td>3</td><td>0.04%</td><td><strong>0.00%</strong></td></tr><tr><td>4</td><td>0.27%</td><td><strong>0.25%</strong></td></tr><tr><td>p<sub>1</sub></td><td>0.22%</td><td>0.22%</td></tr><tr><td rowspan="4">brazil58</td><td>2</td><td>7.12%</td><td><strong>0.78%</strong></td></tr><tr><td>3</td><td>6.76%</td><td><strong>5.17%</strong></td></tr><tr><td>4</td><td>5.92%</td><td><strong>4.95%</strong></td></tr><tr><td>p<sub>1</sub></td><td>3.9%</td><td><strong>3.6%</strong></td></tr><tr><td rowspan="4">st70</td><td>2</td><td>5.15%</td><td><strong>0.44%</strong></td></tr><tr><td>3</td><td>4.33%</td><td><strong>1.42%</strong></td></tr><tr><td>4</td><td>3.55%</td><td><strong>1.55%</strong></td></tr><tr><td>p<sub>1</sub></td><td>1.52%</td><td><strong>1.26%</strong></td></tr><tr><td rowspan="4">eil76</td><td>2</td><td>0.45%</td><td><strong>0.35%</strong></td></tr><tr><td>3</td><td>0.22%</td><td><strong>0.18%</strong></td></tr><tr><td>4</td><td>0.13%</td><td>0.13%</td></tr><tr><td>p<sub>1</sub></td><td>0.41%</td><td>0.41%</td></tr><tr><td rowspan="4">pr76</td><td>2</td><td>6.93%</td><td><strong>4.69%</strong></td></tr><tr><td>3</td><td>5.47%</td><td><strong>4.44%</strong></td></tr><tr><td>4</td><td>4.66%</td><td><strong>4.42%</strong></td></tr><tr><td>p<sub>1</sub></td><td>2.37%</td><td>2.37%</td></tr></tbody></table>
D Test Results (Comparison with literature algorithms for the H<sub>p</sub>MP)

This appendix includes the computational times obtained in many instances using the SANDA<sup>+</sup> formulation and three other algorithms from the literature for the H<sub>p</sub>MP.

<table><caption>Table 17: CPU times obtained with three algorithms from the literature and SANDA<sup>+</sup> (part 1)</caption><thead><tr><th></th><th>p</th><th>Erdoğan et al.</th><th>Bektaş et al.</th><th>Barbato & Gouveia</th><th>SANDA<sup>+</sup></th></tr></thead><tbody><tr><td rowspan="5">gr24</td><td>2</td><td>0.31</td><td>N/A</td><td><b>0</b></td><td>0.45</td></tr><tr><td>3</td><td>0.25</td><td>N/A</td><td><b>0</b></td><td>0.11</td></tr><tr><td>4</td><td>0.27</td><td>N/A</td><td><b>0</b></td><td>0.1</td></tr><tr><td>6</td><td>0.51</td><td>N/A</td><td><b>0.23</b></td><td>0.98</td></tr><tr><td>8</td><td><b>0.24</b></td><td>N/A</td><td>0.29</td><td>1.23</td></tr><tr><td rowspan="5">fri26</td><td>2</td><td>0.41</td><td>N/A</td><td><b>0</b></td><td>0.75</td></tr><tr><td>3</td><td>0.31</td><td>N/A</td><td><b>0.01</b></td><td>0.89</td></tr><tr><td>5</td><td>0.44</td><td>N/A</td><td><b>0</b></td><td>0.3</td></tr><tr><td>6</td><td>0.37</td><td>N/A</td><td><b>0</b></td><td>0.2</td></tr><tr><td>8</td><td>0.21</td><td>N/A</td><td><b>0</b></td><td>0.15</td></tr><tr><td rowspan="5">bayg29</td><td>2</td><td>0.56</td><td>N/A</td><td><b>0</b></td><td>0.32</td></tr><tr><td>4</td><td>0.5</td><td>N/A</td><td><b>0</b></td><td>0.15</td></tr><tr><td>5</td><td>0.53</td><td>N/A</td><td><b>0.01</b></td><td>0.35</td></tr><tr><td>7</td><td>2.15</td><td>N/A</td><td><b>1.35</b></td><td>5.69</td></tr><tr><td>9</td><td><b>1.73</b></td><td>N/A</td><td>2.44</td><td>11.3</td></tr><tr><td rowspan="5">swiss42</td><td>4</td><td>1.37</td><td>1</td><td><b>0.02</b></td><td>2.29</td></tr><tr><td>6</td><td>1.7</td><td>1</td><td><b>0.06</b></td><td>0.73</td></tr><tr><td>8</td><td>1.56</td><td>1</td><td><b>0.04</b></td><td>0.59</td></tr><tr><td>10</td><td>2.02</td><td>1</td><td><b>0.07</b></td><td>1.63</td></tr><tr><td>14</td><td>1.12</td><td>1</td><td><b>0.19</b></td><td>5.93</td></tr><tr><td rowspan="5">att48</td><td>4</td><td>3.73</td><td>1</td><td><b>0.01</b></td><td>0.76</td></tr><tr><td>6</td><td>3.41</td><td>1</td><td><b>0.03</b></td><td>0.49</td></tr><tr><td>9</td><td>3.99</td><td>2</td><td><b>0.33</b></td><td>5.01</td></tr><tr><td>12</td><td>3.99</td><td>4</td><td><b>3.36</b></td><td>12.62</td></tr><tr><td>16</td><td>285.9</td><td>N/A</td><td><b>1.28</b></td><td>2.13%</td></tr><tr><td rowspan="5">gr48</td><td>4</td><td>2.82</td><td>3</td><td><b>0.08</b></td><td>5.32</td></tr><tr><td>6</td><td>1.76</td><td>2</td><td><b>0.02</b></td><td>0.51</td></tr><tr><td>9</td><td>13.7</td><td>13</td><td><b>6.3</b></td><td>41.57</td></tr><tr><td>12</td><td><b>4.91</b></td><td>8</td><td>22.95</td><td>21.84</td></tr><tr><td>16</td><td>24.25</td><td>208</td><td><b>1.28</b></td><td>261.29</td></tr><tr><td rowspan="5">hk48</td><td>4</td><td>3.48</td><td>2</td><td><b>0.1</b></td><td>3.85</td></tr><tr><td>6</td><td>2.88</td><td><b>0</b></td><td><b>0</b></td><td>0.34</td></tr><tr><td>9</td><td>3.05</td><td>2</td><td><b>0.32</b></td><td>3.53</td></tr><tr><td>12</td><td>3.41</td><td>4</td><td><b>2.25</b></td><td>12.82</td></tr><tr><td>16</td><td>10.04</td><td>118</td><td><b>0.19</b></td><td>33.79</td></tr><tr><td rowspan="5">eil51</td><td>5</td><td>4.58</td><td>4</td><td><b>0.08</b></td><td>0.79</td></tr><tr><td>7</td><td>6.88</td><td>5</td><td><b>0.72</b></td><td>2.62</td></tr><tr><td>10</td><td>41.32</td><td><b>10</b></td><td>15.7</td><td>79.34</td></tr><tr><td>12</td><td>14.41</td><td><b>14</b></td><td>24.05</td><td>85.54</td></tr><tr><td>17</td><td>50.96</td><td>1701</td><td><b>1.48</b></td><td>1612.63</td></tr><tr><td rowspan="5">berlin52</td><td>5</td><td>3.66</td><td>2</td><td><b>0.19</b></td><td>2.12</td></tr><tr><td>7</td><td>2.57</td><td>1</td><td><b>0</b></td><td>0.29</td></tr><tr><td>10</td><td>4.43</td><td>2</td><td><b>0.18</b></td><td>2.54</td></tr><tr><td>13</td><td>4.68</td><td>2</td><td><b>1.93</b></td><td>11.47</td></tr><tr><td>17</td><td>48.81</td><td>36</td><td><b>5.22</b></td><td>1167.73</td></tr></tbody></table>
<table><caption>Table 18: CPU times obtained with three algorithms from the literature and SANDA<sup>+</sup> (part 2)</caption><thead><tr><th></th><th>p</th><th>Erdoğan et al.</th><th>Bektaş et al.</th><th>Barbato & Gouveia</th><th>SANDA<sup>+</sup></th></tr></thead><tbody><tr><td rowspan="5">brazil58</td><td>5</td><td>78.9</td><td>12</td><td><strong>0.73</strong></td><td>1.05%</td></tr><tr><td>8</td><td>36.95</td><td>6</td><td><strong>0.14</strong></td><td>20.44</td></tr><tr><td>11</td><td>5.14</td><td>5</td><td><strong>0.01</strong></td><td>0.96</td></tr><tr><td>14</td><td>4.72</td><td>2</td><td><strong>0.99</strong></td><td>1.94</td></tr><tr><td>19</td><td>31.13</td><td>71</td><td><strong>0.76</strong></td><td>468.27</td></tr><tr><td rowspan="5">st70</td><td>7</td><td>18.11</td><td>5</td><td><strong>0.41</strong></td><td>58.34</td></tr><tr><td>10</td><td>12.56</td><td>4</td><td><strong>0.14</strong></td><td>9.38</td></tr><tr><td>14</td><td>8.66</td><td>3</td><td><strong>0.08</strong></td><td>2.1</td></tr><tr><td>17</td><td>11.16</td><td>9</td><td><strong>0.71</strong></td><td>6</td></tr><tr><td>23</td><td>1137.77</td><td>N/A</td><td><strong>192.41</strong></td><td>3.09%</td></tr><tr><td rowspan="5">eil76</td><td>7</td><td>20.97</td><td>10</td><td><strong>0.3</strong></td><td>7.25</td></tr><tr><td>10</td><td>18.6</td><td>38</td><td><strong>2.14</strong></td><td>17.25</td></tr><tr><td>15</td><td>207.04</td><td><strong>58</strong></td><td>89.3</td><td>370.04</td></tr><tr><td>19</td><td>371.35</td><td><strong>133</strong></td><td>1.87%</td><td>1.30%</td></tr><tr><td>25</td><td><strong>1025.73</strong></td><td>N/A</td><td>3.12%</td><td>19.01%</td></tr><tr><td rowspan="5">pr76</td><td>7</td><td>25.29</td><td>5</td><td><strong>0.14</strong></td><td>2.93</td></tr><tr><td>10</td><td>224.4</td><td><strong>8</strong></td><td>8.85</td><td>10.54</td></tr><tr><td>15</td><td>0.70%</td><td><strong>34</strong></td><td>224.94</td><td>379.36</td></tr><tr><td>19</td><td>45.62</td><td><strong>7</strong></td><td>287.79</td><td>55.23</td></tr><tr><td>25</td><td>867.49</td><td><strong>12</strong></td><td>38.56</td><td>1372.67</td></tr><tr><td rowspan="5">rat99</td><td>9</td><td>90.16</td><td>12</td><td><strong>0.72</strong></td><td>5.49</td></tr><tr><td>14</td><td>2.55%</td><td><strong>23</strong></td><td>387.77</td><td>249.09</td></tr><tr><td>19</td><td>2.19%</td><td><strong>43</strong></td><td>1.90%</td><td>170.65</td></tr><tr><td>24</td><td>1.17%</td><td><strong>44</strong></td><td>7.24%</td><td>239.46</td></tr><tr><td>33</td><td>2.85%</td><td>3003</td><td><strong>16.11</strong></td><td>2.14%</td></tr><tr><td rowspan="5">kroA100</td><td>10</td><td>2993.41</td><td>151</td><td><strong>3.29</strong></td><td>0.39%</td></tr><tr><td>14</td><td>40.47</td><td>95</td><td><strong>0.74</strong></td><td>5.52</td></tr><tr><td>20</td><td>57.24</td><td>30</td><td><strong>5.46</strong></td><td>23.13</td></tr><tr><td>25</td><td>77.87</td><td><strong>51</strong></td><td>435.69</td><td>471.45</td></tr><tr><td>33</td><td>2.43%</td><td>N/A</td><td><strong>2504.77</strong></td><td>29.41%</td></tr><tr><td rowspan="5">kroB100</td><td>10</td><td>1575.86</td><td>145</td><td><strong>2.84</strong></td><td>748.38</td></tr><tr><td>14</td><td>1292.72</td><td>143</td><td><strong>1.67</strong></td><td>95.18</td></tr><tr><td>20</td><td>114.7</td><td>75</td><td><strong>0.39</strong></td><td>1.87</td></tr><tr><td>25</td><td>34.89</td><td>16</td><td><strong>3.12</strong></td><td>15.43</td></tr><tr><td>33</td><td><strong>2.23%</strong></td><td>N/A</td><td>4.46%</td><td>6.89%</td></tr><tr><td rowspan="5">kroC100</td><td>10</td><td>93.61</td><td>98</td><td><strong>2.35</strong></td><td>98.97</td></tr><tr><td>14</td><td>77.78</td><td>67</td><td><strong>6.58</strong></td><td>8.13</td></tr><tr><td>20</td><td>229.62</td><td>55</td><td><strong>23.12</strong></td><td>116.93</td></tr><tr><td>25</td><td>197.6</td><td>436</td><td>543.1</td><td><strong>146.43</strong></td></tr><tr><td>33</td><td>4.03%</td><td>N/A</td><td><strong>2942.86</strong></td><td>50.20%</td></tr><tr><td rowspan="5">kroD100</td><td>10</td><td>50.5</td><td>48</td><td><strong>0.14</strong></td><td>3.27</td></tr><tr><td>14</td><td>46.87</td><td>42</td><td><strong>0.08</strong></td><td>6.71</td></tr><tr><td>20</td><td>254.33</td><td>197</td><td><strong>14.88</strong></td><td>124.69</td></tr><tr><td>25</td><td><strong>154.5</strong></td><td>160</td><td>155.73</td><td>205.02</td></tr><tr><td>33</td><td><strong>1.02%</strong></td><td>N/A</td><td>1.62%</td><td>11.01%</td></tr></tbody></table>
<table><caption>Table 19: CPU times obtained with three algorithms from the literature and SANDA<sup>+</sup> (part 3)</caption><thead><tr><th></th><th>p</th><th>Erdoğan et al.</th><th>Bektaş et al.</th><th>Barbato & Gouveia</th><th>SANDA<sup>+</sup></th></tr></thead><tbody><tr><td rowspan="5">kroE100</td><td>10</td><td>28.92</td><td>25</td><td><strong>0.09</strong></td><td>10.73</td></tr><tr><td>14</td><td>28.45</td><td>37</td><td><strong>0.42</strong></td><td>4.59</td></tr><tr><td>20</td><td>51.43</td><td>65</td><td><strong>4.11</strong></td><td>15.21</td></tr><tr><td>25</td><td>62.6</td><td>92</td><td>38.75</td><td><strong>33.9</strong></td></tr><tr><td>33</td><td>3054.13</td><td>N/A</td><td><strong>1429.21</strong></td><td>3.14%</td></tr><tr><td rowspan="5">rd100</td><td>10</td><td>177.19</td><td>147</td><td><strong>2.66</strong></td><td>181.31</td></tr><tr><td>14</td><td>42.96</td><td>57</td><td><strong>0.15</strong></td><td>11.2</td></tr><tr><td>20</td><td>149.61</td><td>101</td><td><strong>13.76</strong></td><td>55.12</td></tr><tr><td>25</td><td>51.3</td><td>42</td><td><strong>8.43</strong></td><td>14.82</td></tr><tr><td>33</td><td>1.66%</td><td>N/A</td><td><strong>0.29%</strong></td><td>5.85%</td></tr><tr><td rowspan="5">pr124</td><td>12</td><td>N/A</td><td>N/A</td><td><strong>32.64</strong></td><td>3.58%</td></tr><tr><td>17</td><td>N/A</td><td>N/A</td><td><strong>255.94</strong></td><td>0.63%</td></tr><tr><td>24</td><td>N/A</td><td>N/A</td><td><strong>2.22</strong></td><td>7.97</td></tr><tr><td>31</td><td>N/A</td><td>N/A</td><td><strong>5.26</strong></td><td>23.43</td></tr><tr><td>41</td><td>N/A</td><td>N/A</td><td><strong>221.92</strong></td><td>22.81%</td></tr><tr><td rowspan="5">u159</td><td>15</td><td>N/A</td><td>N/A</td><td><strong>2.77</strong></td><td>160.65</td></tr><tr><td>22</td><td>N/A</td><td>N/A</td><td><strong>16.54</strong></td><td>21.83</td></tr><tr><td>31</td><td>N/A</td><td>N/A</td><td>0.14%</td><td><strong>324.73</strong></td></tr><tr><td>39</td><td>N/A</td><td>N/A</td><td>2.74%</td><td><strong>480.53</strong></td></tr><tr><td>53</td><td>N/A</td><td>N/A</td><td><strong>129.42</strong></td><td>100.00%</td></tr><tr><td rowspan="5">rat195</td><td>19</td><td>N/A</td><td>N/A</td><td><strong>2978.33</strong></td><td>3455.48</td></tr><tr><td>27</td><td>N/A</td><td>N/A</td><td>6.25%</td><td><strong>0.72%</strong></td></tr><tr><td>39</td><td>N/A</td><td>N/A</td><td>22.20%</td><td><strong>1.19%</strong></td></tr><tr><td>48</td><td>N/A</td><td>N/A</td><td>32.22%</td><td><strong>6.89%</strong></td></tr><tr><td>65</td><td>N/A</td><td>N/A</td><td><strong>1595.81</strong></td><td>100.00%</td></tr><tr><td rowspan="5">d198</td><td>19</td><td>N/A</td><td>N/A</td><td><strong>0.85%</strong></td><td>3.13%</td></tr><tr><td>28</td><td>N/A</td><td>N/A</td><td><strong>1.45</strong></td><td>255.76</td></tr><tr><td>39</td><td>N/A</td><td>N/A</td><td><strong>103.62</strong></td><td>139.54</td></tr><tr><td>49</td><td>N/A</td><td>N/A</td><td>2.65%</td><td><strong>644.58</strong></td></tr><tr><td>66</td><td>N/A</td><td>N/A</td><td><strong>2.53%</strong></td><td>100.00%</td></tr><tr><td rowspan="5">pr226</td><td>22</td><td>N/A</td><td>N/A</td><td><strong>4.39%</strong></td><td>6.78%</td></tr><tr><td>32</td><td>N/A</td><td>N/A</td><td><strong>1.03%</strong></td><td>1.47%</td></tr><tr><td>45</td><td>N/A</td><td>N/A</td><td><strong>0.95</strong></td><td>143.52</td></tr><tr><td>56</td><td>N/A</td><td>N/A</td><td>47.40%</td><td><strong>69.24</strong></td></tr><tr><td>75</td><td>N/A</td><td>N/A</td><td><strong>69.69%</strong></td><td>100.00%</td></tr><tr><td rowspan="5">gil262</td><td>26</td><td>N/A</td><td>N/A</td><td><strong>26.86</strong></td><td>4.39%</td></tr><tr><td>37</td><td>N/A</td><td>N/A</td><td><strong>167.72</strong></td><td>1677.69</td></tr><tr><td>52</td><td>N/A</td><td>N/A</td><td><strong>0.28%</strong></td><td>13.21%</td></tr><tr><td>65</td><td>N/A</td><td>N/A</td><td><strong>23.77%</strong></td><td>100.00%</td></tr><tr><td>87</td><td>N/A</td><td>N/A</td><td><strong>32.56%</strong></td><td>100.00%</td></tr><tr><td rowspan="5">rd400</td><td>40</td><td>N/A</td><td>N/A</td><td><strong>39.96</strong></td><td>100.00%</td></tr><tr><td>57</td><td>N/A</td><td>N/A</td><td><strong>496.84</strong></td><td>1.12%</td></tr><tr><td>80</td><td>N/A</td><td>N/A</td><td><strong>16.32%</strong></td><td>100.00%</td></tr><tr><td>100</td><td>N/A</td><td>N/A</td><td><strong>38.55%</strong></td><td>100.00%</td></tr><tr><td>133</td><td>N/A</td><td>N/A</td><td><strong>51.22%</strong></td><td>100.00%</td></tr></tbody></table>