Large size instances Sample Clauses

Large size instances. The results of our tests on large instances are shown in Figures 9, 10 and 11. The trends observed for medium size instances are again present and accentuated here. Even though its completion time is steadily increasing, the heuristic XX-XX is the only one that terminates (for 93% of the instances) within one hour of running time (Figure 9(a)). The remaining 7% take on average 16.7% more than 1 hour, and the last instance takes up to 29% above the time limit. Yet, XX-XX provides the best solution for more than 90% of the instances (Figure 9(b)). The first phase RL provides an exact solution for 4.4% of the large instances. However, the optimality gap GRL−RP is smaller than for any other method and in fact always smaller than 0.5% (Figure 11(a)). Only our Combinatorial Benders Algorithm can sometimes match or improve the solution found by XX-XX (for about 16% of the large instances). For the remaining instances, the relative gap ∆QCBA to the heuristic value is 0.18% on average. Furthermore, it is interesting to note that CBA generally finds its best solution faster than any other method, including the heuristic (Figure 10(b)). On large size instances, CP-B&C frequently (41%) fails to detect a single feasible solution (upper bound). As a consequence, ∆QCP −B&C and GCP −B&C are very large for these instances (Figure 11). Conversely, CP-Bend (classical) decomposition is still able to find one. However, the lower bound provided by CP-B&C is systematically tighter than that of CP-Bend. On average, LCP −B&C is 1.26% and 2.48% closer to the optimal value than LCP −Bend and LCBA respectively, while it is looser than LRL−RP in 0.61%. Figure 10: Efficiency: performance profile of total running time FA and of running time until best found solution BA - large instances Figure 11: Effectiveness: performance profile of optimality gap GA and of gap to best known value ∆QA - large instances