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,365,932,733 | 0.969 | 1,366,215,071 | 1.085 | 1,366,941,579 | 1.562 |
P2 | 1,356,964,622 | 1.062 | 1,357,249,992 | 1.144 | 1,357,960,054 | 1.572 |
P3 | 1,366,670,095 | 1.093 | 1,366,946,572 | 1.248 | 1,367,675,025 | 1.65 |
P4 | 1,364,344,024 | 1.047 | 1,364,630,536 | 1.145 | 1,365,354,097 | 1.578 |
P5 | 1,359,252,277 | 1.109 | 1,359,550,905 | 1.265 | 1,360,243,625 | 1.578 |
P6 | 1,362,703,027 | 1.031 | 1,362,989,604 | 1.137 | 1,363,687,229 | 1.547 |
P7 | 1,357,648,342 | 1.094 | 1,357,931,004 | 1.248 | 1,358,646,263 | 1.532 |
P8 | 1,361,734,440 | 1.078 | 1,362,015,230 | 1.234 | 1,362,771,012 | 1.578 |
P9 | 1,363,335,394 | 1.094 | 1,363,626,057 | 1.226 | 1,364,326,431 | 1.578 |
P10 | 1,354,662,978 | 1.062 | 1,354,940,548 | 1.126 | 1,355,672,184 | 1.625 |
P11 | 1,359,010,784 | 1.031 | 1,359,297,671 | 1.111 | 1,360,015,221 | 1.578 |
P12 | 1,360,290,820 | 1.031 | 1,360,566,551 | 1.118 | 1,361,275,760 | 1.484 |
P13 | 1,359,813,107 | 1.015 | 1,360,106,147 | 1.136 | 1,360,804,455 | 1.516 |
P14 | 1,360,229,705 | 1.094 | 1,360,524,059 | 1.190 | 1,361,194,499 | 1.563 |
P15 | 1,357,065,375 | 1 | 1,357,352,530 | 1.080 | 1,358,068,651 | 1.485 |
P16 | 1,366,116,379 | 1.063 | 1,366,414,875 | 1.185 | 1,367,101,877 | 1.797 |
P17 | 1,354,295,387 | 1.016 | 1,354,575,049 | 1.166 | 1,355,307,736 | 1.547 |
P18 | 1,362,453,698 | 1.093 | 1,362,753,165 | 1.196 | 1,363,466,065 | 1.656 |
P19 | 1,351,212,750 | 1.047 | 1,351,506,098 | 1.133 | 1,352,228,221 | 1.594 |
P20 | 1,354,546,726 | 1.062 | 1,354,825,085 | 1.156 | 1,355,567,185 | 1.593 |
P21 | 1,361,671,542 | 1.078 | 1,361,968,932 | 1.167 | 1,362,652,718 | 1.515 |
P22 | 1,365,090,355 | 1.031 | 1,365,366,240 | 1.125 | 1,366,081,015 | 1.531 |
P23 | 1,353,711,255 | 1.015 | 1,353,984,975 | 1.125 | 1,354,692,174 | 1.594 |
P24 | 1,359,167,606 | 1.078 | 1,359,454,798 | 1.239 | 1,360,142,833 | 1.547 |
P25 | 1,354,759,090 | 1.078 | 1,355,052,259 | 1.185 | 1,355,756,040 | 1.546 |
P26 | 1,360,824,145 | 0.984 | 1,361,122,302 | 1.101 | 1,361,829,294 | 1.594 |
P27 | 1,357,519,457 | 1.047 | 1,357,817,161 | 1.210 | 1,358,490,606 | 1.516 |
P28 | 1,355,437,009 | 1.047 | 1,355,724,226 | 1.148 | 1,356,416,967 | 1.562 |
P29 | 1,360,832,833 | 0.985 | 1,361,119,561 | 1.126 | 1,361,815,955 | 1.578 |
P30 | 1,349,511,932 | 1.062 | 1,349,797,353 | 1.191 | 1,350,507,838 | 1.578 |