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,356,765,481 | 1 | 1,356,988,805 | 1.028 | 1,357,747,787 | 1.375 |
P2 | 1,348,578,687 | 0.906 | 1,348,784,480 | 0.934 | 1,349,566,313 | 1.375 |
P3 | 1,350,776,977 | 0.89 | 1,351,005,393 | 0.910 | 1,351,787,791 | 1.391 |
P4 | 1,356,692,279 | 0.89 | 1,356,918,304 | 0.913 | 1,357,678,393 | 1.337 |
P5 | 1,359,305,911 | 0.953 | 1,359,517,283 | 0.975 | 1,360,284,488 | 1.39 |
P6 | 1,349,187,512 | 0.922 | 1,349,390,565 | 0.951 | 1,350,173,750 | 1.359 |
P7 | 1,347,497,209 | 0.953 | 1,347,721,702 | 0.979 | 1,348,495,827 | 1.406 |
P8 | 1,351,561,595 | 0.922 | 1,351,780,684 | 0.943 | 1,352,539,359 | 1.39 |
P9 | 1,352,908,377 | 0.906 | 1,353,135,936 | 0.935 | 1,353,917,629 | 1.375 |
P10 | 1,355,180,785 | 0.906 | 1,355,411,030 | 0.928 | 1,356,176,036 | 1.359 |
P11 | 1,349,471,170 | 0.968 | 1,349,679,258 | 0.990 | 1,350,467,442 | 1.422 |
P12 | 1,347,863,661 | 0.922 | 1,348,079,993 | 0.948 | 1,348,867,681 | 1.422 |
P13 | 1,354,473,571 | 0.922 | 1,354,688,119 | 0.947 | 1,355,463,506 | 1.359 |
P14 | 1,350,205,726 | 0.922 | 1,350,433,235 | 0.948 | 1,351,193,519 | 1.344 |
P15 | 1,349,060,862 | 0.922 | 1,349,290,067 | 0.945 | 1,350,041,009 | 1.375 |
P16 | 1,347,587,320 | 0.859 | 1,347,789,863 | 0.886 | 1,348,577,355 | 1.453 |
P17 | 1,351,522,612 | 0.813 | 1,351,733,179 | 0.839 | 1,352,521,657 | 1.359 |
P18 | 1,348,302,161 | 0.828 | 1,348,510,204 | 0.847 | 1,349,326,170 | 1.422 |
P19 | 1,357,334,766 | 0.828 | 1,357,545,560 | 0.852 | 1,358,323,179 | 1.406 |
P20 | 1,346,200,443 | 0.844 | 1,346,428,489 | 0.867 | 1,347,193,192 | 1.485 |
P21 | 1,356,509,204 | 0.828 | 1,356,734,656 | 0.852 | 1,357,494,571 | 1.391 |
P22 | 1,350,745,322 | 0.829 | 1,350,970,356 | 0.852 | 1,351,735,380 | 1.438 |
P23 | 1,356,703,210 | 0.812 | 1,356,919,469 | 0.832 | 1,357,678,909 | 1.422 |
P24 | 1,357,978,256 | 0.844 | 1,358,191,187 | 0.864 | 1,358,962,351 | 1.5 |
P25 | 1,349,813,482 | 0.828 | 1,350,026,212 | 0.848 | 1,350,818,186 | 1.422 |
P26 | 1,354,216,441 | 0.937 | 1,354,434,470 | 0.963 | 1,355,225,303 | 1.516 |
P27 | 1,354,135,174 | 0.844 | 1,354,343,981 | 0.871 | 1,355,144,688 | 1.344 |
P28 | 1,345,665,627 | 0.844 | 1,345,879,453 | 0.869 | 1,346,652,596 | 1.407 |
P29 | 1,353,034,625 | 0.859 | 1,353,261,123 | 0.883 | 1,354,003,682 | 1.375 |
P30 | 1,352,589,054 | 0.844 | 1,352,793,971 | 0.869 | 1,353,593,395 | 1.343 |