Problem instance number | Weak bound (relaxed formulation I) | Hybrid formulation bound (relaxed weak formulation with most promising strong linking constraints added) | Strong bound (relaxed formulation II) | |||
Value | CPU time | Value | CPU time | Value | CPU time | |
P1 | 1,349,044,304 | 0.953 | 1,349,310,336 | 1.076 | 1,350,052,277 | 1.328 |
P2 | 1,341,330,308 | 0.891 | 1,341,585,965 | 1.079 | 1,342,364,193 | 1.344 |
P3 | 1,357,367,491 | 0.875 | 1,357,634,078 | 1.040 | 1,358,357,501 | 1.313 |
P4 | 1,344,761,701 | 0.907 | 1,345,022,451 | 1.072 | 1,345,749,092 | 1.312 |
P5 | 1,353,950,432 | 0.906 | 1,354,231,377 | 1.065 | 1,354,948,263 | 1.343 |
P6 | 1,345,725,674 | 0.86 | 1,345,986,206 | 1.060 | 1,346,727,389 | 1.328 |
P7 | 1,350,064,031 | 0.875 | 1,350,340,929 | 0.991 | 1,351,070,255 | 1.344 |
P8 | 1,349,599,349 | 0.859 | 1,349,856,043 | 1.048 | 1,350,587,142 | 1.312 |
P9 | 1,347,042,608 | 0.875 | 1,347,306,898 | 1.071 | 1,348,010,275 | 1.328 |
P10 | 1,359,202,269 | 0.891 | 1,359,485,934 | 1.034 | 1,360,184,283 | 1.313 |
P11 | 1,347,843,751 | 0.875 | 1,348,111,163 | 1.080 | 1,348,840,103 | 1.328 |
P12 | 1,347,079,789 | 0.859 | 1,347,339,910 | 0.996 | 1,348,069,301 | 1.344 |
P13 | 1,345,959,280 | 0.875 | 1,346,232,645 | 1.005 | 1,346,948,448 | 1.36 |
P14 | 1,352,533,674 | 0.844 | 1,352,817,571 | 0.995 | 1,353,537,564 | 1.359 |
P15 | 1,344,792,939 | 0.891 | 1,345,071,043 | 1.021 | 1,345,811,206 | 1.312 |
P16 | 1,346,897,235 | 0.828 | 1,347,173,079 | 1.006 | 1,347,857,811 | 1.344 |
P17 | 1,335,591,579 | 0.765 | 1,335,869,115 | 0.905 | 1,336,633,363 | 1.344 |
P18 | 1,352,021,379 | 0.813 | 1,352,281,103 | 0.976 | 1,353,033,815 | 1.344 |
P19 | 1,340,538,436 | 0.828 | 1,340,813,112 | 0.994 | 1,341,534,569 | 1.375 |
P20 | 1,358,293,736 | 0.796 | 1,358,553,985 | 0.893 | 1,359,285,053 | 1.329 |
P21 | 1,349,182,387 | 0.828 | 1,349,458,565 | 0.983 | 1,350,197,272 | 1.343 |
P22 | 1,350,465,764 | 0.844 | 1,350,736,127 | 0.978 | 1,351,464,235 | 1.328 |
P23 | 1,342,712,142 | 0.828 | 1,342,975,448 | 0.978 | 1,343,717,026 | 1.344 |
P24 | 1,349,696,083 | 0.812 | 1,349,955,090 | 0.925 | 1,350,685,192 | 1.312 |
P25 | 1,344,666,743 | 0.813 | 1,344,942,265 | 0.967 | 1,345,654,739 | 1.281 |
P26 | 1,349,872,300 | 0.812 | 1,350,155,773 | 0.941 | 1,350,889,585 | 1.328 |
P27 | 1,346,328,212 | 0.797 | 1,346,606,633 | 0.951 | 1,347,349,390 | 1.344 |
P28 | 1,349,420,910 | 0.812 | 1,349,697,811 | 0.919 | 1,350,411,598 | 1.359 |
P29 | 1,350,343,978 | 0.828 | 1,350,602,029 | 1.010 | 1,351,345,376 | 1.313 |
P30 | 1,358,015,527 | 0.828 | 1,358,295,142 | 0.945 | 1,359,024,827 | 1.313 |