Medium size instances Sample Clauses

Medium size instances. Figures 6, 7 and 8 present the aggregated results for the set of medium size instances, using the same conventions as in the previous Section 9. 1. For most instances, none of the exact methods terminate within one hour, proving optimality. The heuristic ▇▇-▇▇ always stops before the time limit (in less than 1900 seconds - Figures 6(a), 7(a)). It obtains an exact solution for 8% of the instances (Figures 6(b), 8(a)). ▇▇-▇▇ provides solutions that are at least as good as the exact methods for 55.2% of the instances and mostly outperforms CPLEX methods (CP-B&C, CP-Bend) (see Figure 8(b)). We observe that the heuristic method has a small integrality gap, below 1% (Figure 8(a)). This means that the lower bound computed in the first phase is tight. Among exact methods, the combinatorial algorithm CBA provides the best feasible solution faster than the two CPLEX methods (see performance profile BCBA in Figure 7(b)). CPLEX methods tend to continuously improve their incumbent solution, slowly closing the gap to their respective LBs. However, the lower bound computed by the CBA method alone remains relatively weak, which translates into values of GCBA between 1.9% and 3.5% (see performance profile GCBA in Figure 8(a)).