Lower Bounds LB based on constraint propagation (immediate selection) and linear programming (Brucker, Knust [2000]) Problem UBbest LB -------------------------- 1 1 107 101 1 2 110 106 1 3 125 122 1 4 97 97 1 5 112 108 1 6 84 84 1 7 117 109 1 8 109 108 1 9 112 109 1 10 108 102 2 1 87 86 2 2 75 73 2 3 92 90 2 4 95 94 2 5 103 100 2 6 92 90 2 7 90 90 2 8 83 81 2 9 95 92 2 10 97 93 3 1 80 79 3 2 88 88 3 3 100 100 3 4 71 71 3 5 84 84 3 6 102 102 3 7 93 93 3 8 77 77 3 9 86 86 3 10 103 103 4 1 74 74 4 2 107 107 4 3 95 95 4 4 75 75 4 5 74 74 4 6 90 90 4 7 81 81 4 8 90 90 4 9 79 79 4 10 77 77 5 1 92 92 5 2 80 80 5 3 72 72 5 4 97 97 5 5 77 77 5 6 88 88 5 7 84 84 5 8 78 78 5 9 106 106 5 10 92 92 6 1 152 132 6 2 144 125 6 3 139 135 6 4 160 151 6 5 131 115 6 6 163 140 6 7 177 154 6 8 155 138 6 9 172 144 6 10 180 156 7 1 106 97 7 2 119 105 7 3 103 92 7 4 116 103 7 5 137 123 7 6 129 113 7 7 123 112 7 8 102 90 7 9 93 84 7 10 123 110 8 1 95 95 8 2 106 95 8 3 97 90 8 4 98 89 8 5 107 99 8 6 88 82 8 7 89 87 8 8 89 87 8 9 97 87 8 10 94 91 9 1 88 88 9 2 94 94 9 3 87 87 9 4 89 83 9 5 114 114 9 6 98 98 9 7 80 80 9 8 80 80 9 9 87 87 9 10 84 84 10 1 111 111 10 2 91 91 10 3 99 99 10 4 95 95 10 5 97 97 10 6 92 92 10 7 79 79 10 8 114 114 10 9 77 77 10 10 66 66 11 1 183 155 11 2 167 145 11 3 211 186 11 4 209 175 11 5 223 191 11 6 226 189 11 7 172 148 11 8 171 151 11 9 181 167 11 10 191 163 12 1 145 125 12 2 123 110 12 3 141 130 12 4 132 121 12 5 170 153 12 6 128 115 12 7 125 115 12 8 125 109 12 9 109 100 12 10 148 142 13 1 132 121 13 2 91 88 13 3 121 114 13 4 117 107 13 5 93 89 13 6 102 95 13 7 112 107 13 8 97 90 13 9 88 82 13 10 96 84 14 1 88 84 14 2 95 89 14 3 88 88 14 4 90 85 14 5 100 93 14 6 91 91 14 7 92 89 14 8 114 108 14 9 101 101 14 10 84 80 15 1 81 81 15 2 75 75 15 3 87 87 15 4 82 82 15 5 87 87 15 6 97 97 15 7 75 75 15 8 126 126 15 9 109 109 15 10 91 91 16 1 206 179 16 2 243 218 16 3 246 219 16 4 208 189 16 5 208 184 16 6 217 194 16 7 193 174 16 8 205 182 16 9 215 188 16 10 226 202 17 1 147 135 17 2 128 120 17 3 112 106 17 4 124 117 17 5 134 122 17 6 141 133 17 7 153 141 17 8 132 126 17 9 140 128 17 10 140 131 18 1 142 137 18 2 120 111 18 3 103 96 18 4 104 98 18 5 121 117 18 6 139 130 18 7 121 111 18 8 108 101 18 9 94 76 18 10 100 96 19 1 88 88 19 2 85 81 19 3 87 83 19 4 109 97 19 5 106 101 19 6 92 88 19 7 93 93 19 8 94 93 19 9 90 84 19 10 88 88 20 1 89 89 20 2 99 99 20 3 78 74 20 4 89 89 20 5 69 69 20 6 80 80 20 7 81 81 20 8 107 107 20 9 80 80 20 10 81 81 21 1 115 109 21 2 118 109 21 3 143 132 21 4 135 131 21 5 110 104 21 6 109 107 21 7 112 104 21 8 127 125 21 9 102 97 21 10 103 96 22 1 101 97 22 2 107 107 22 3 97 94 22 4 90 90 22 5 93 93 22 6 103 99 22 7 133 133 22 8 103 97 22 9 109 107 22 10 79 79 23 1 107 107 23 2 116 116 23 3 99 99 23 4 106 106 23 5 99 99 23 6 106 106 23 7 104 104 23 8 101 101 23 9 107 107 23 10 100 100 24 1 93 93 24 2 91 91 24 3 89 89 24 4 101 101 24 5 86 86 24 6 95 95 24 7 112 110 24 8 104 104 24 9 82 82 24 10 91 91 25 1 82 82 25 2 108 108 25 3 100 100 25 4 117 117 25 5 100 100 25 6 92 91 25 7 92 92 25 8 80 78 25 9 94 94 25 10 92 92 26 1 177 153 26 2 175 147 26 3 172 153 26 4 179 151 26 5 161 136 26 6 193 167 26 7 167 141 26 8 184 162 26 9 181 158 26 10 193 160 27 1 111 105 27 2 119 105 27 3 147 139 27 4 110 103 27 5 115 101 27 6 153 130 27 7 129 114 27 8 146 135 27 9 135 118 27 10 118 105 28 1 111 104 28 2 111 110 28 3 101 101 28 4 115 107 28 5 102 102 28 6 103 103 28 7 112 102 28 8 102 96 28 9 100 94 28 10 120 109 29 1 104 104 29 2 91 91 29 3 99 93 29 4 81 77 29 5 102 102 29 6 92 88 29 7 97 97 29 8 80 80 29 9 97 97 29 10 96 96 30 1 102 102 30 2 112 112 30 3 108 108 30 4 83 83 30 5 85 81 30 6 79 79 30 7 93 93 30 8 79 79 30 9 93 93 30 10 86 86 31 1 210 178 31 2 204 174 31 3 181 156 31 4 233 194 31 5 212 184 31 6 202 181 31 7 217 189 31 8 204 172 31 9 202 173 31 10 242 201 32 1 152 142 32 2 137 121 32 3 151 133 32 4 142 125 32 5 143 131 32 6 134 120 32 7 126 117 32 8 142 130 32 9 131 123 32 10 137 125 33 1 110 104 33 2 116 105 33 3 110 100 33 4 117 105 33 5 146 131 33 6 118 115 33 7 127 120 33 8 116 106 33 9 119 108 33 10 110 101 34 1 80 75 34 2 108 102 34 3 103 98 34 4 95 94 34 5 105 100 34 6 100 100 34 7 105 105 34 8 91 85 34 9 97 90 34 10 101 101 35 1 87 87 35 2 113 111 35 3 77 77 35 4 101 101 35 5 94 92 35 6 86 86 35 7 99 99 35 8 101 101 35 9 91 91 35 10 86 86 36 1 220 199 36 2 233 206 36 3 240 217 36 4 247 217 36 5 240 212 36 6 237 207 36 7 219 194 36 8 181 156 36 9 232 202 36 10 228 198 37 1 151 137 37 2 149 140 37 3 146 135 37 4 169 155 37 5 213 191 37 6 171 153 37 7 168 149 37 8 188 168 37 9 149 137 37 10 137 126 38 1 111 104 38 2 129 118 38 3 159 153 38 4 146 137 38 5 117 110 38 6 127 118 38 7 107 102 38 8 130 120 38 9 139 134 38 10 145 136 39 1 96 95 39 2 112 104 39 3 115 109 39 4 101 97 39 5 106 106 39 6 95 95 39 7 107 101 39 8 100 93 39 9 95 89 39 10 113 104 40 1 83 79 40 2 90 90 40 3 87 87 40 4 112 112 40 5 101 101 40 6 90 90 40 7 91 91 40 8 97 97 40 9 117 117 40 10 96 96 41 1 127 125 41 2 141 139 41 3 142 132 41 4 116 107 41 5 138 137 41 6 113 103 41 7 110 102 41 8 138 135 41 9 121 112 41 10 137 128 42 1 110 104 42 2 126 126 42 3 106 104 42 4 104 104 42 5 120 114 42 6 119 106 42 7 123 123 42 8 114 108 42 9 104 102 42 10 118 110 43 1 105 105 43 2 120 120 43 3 95 95 43 4 105 101 43 5 105 105 43 6 98 93 43 7 122 121 43 8 115 115 43 9 105 105 43 10 113 113 44 1 100 100 44 2 112 112 44 3 107 107 44 4 95 95 44 5 98 98 44 6 106 106 44 7 98 98 44 8 108 107 44 9 91 91 44 10 98 98 45 1 108 108 45 2 91 91 45 3 98 98 45 4 103 103 45 5 116 114 45 6 125 125 45 7 103 103 45 8 103 103 45 9 114 114 45 10 99 99 46 1 194 160 46 2 206 173 46 3 181 151 46 4 177 160 46 5 158 133 46 6 184 169 46 7 177 150 46 8 184 163 46 9 174 146 46 10 194 165 47 1 143 121 47 2 135 118 47 3 129 118 47 4 138 116 47 5 130 117 47 6 143 126 47 7 122 111 47 8 139 121 47 9 148 135 47 10 136 126 48 1 103 95 48 2 116 110 48 3 113 104 48 4 131 119 48 5 112 104 48 6 108 97 48 7 109 102 48 8 117 108 48 9 115 109 48 10 114 105 49 1 96 96 49 2 112 102 49 3 98 93 49 4 98 91 49 5 89 84 49 6 128 128 49 7 100 97 49 8 114 112 49 9 99 97 49 10 98 92 50 1 116 116 50 2 112 112 50 3 111 111 50 4 101 95 50 5 100 100 50 6 102 102 50 7 137 137 50 8 112 112 50 9 101 101 50 10 103 103 51 1 219 185 51 2 233 199 51 3 231 190 51 4 224 196 51 5 243 205 51 6 229 192 51 7 221 184 51 8 219 185 51 9 224 189 51 10 242 200 52 1 187 160 52 2 192 166 52 3 139 124 52 4 176 155 52 5 175 156 52 6 207 179 52 7 155 140 52 8 165 146 52 9 155 139 52 10 152 130 53 1 149 136 53 2 119 108 53 3 115 104 53 4 150 135 53 5 116 107 53 6 109 100 53 7 122 116 53 8 145 133 53 9 171 152 53 10 136 123 54 1 108 101 54 2 134 134 54 3 111 111 54 4 122 119 54 5 110 106 54 6 111 103 54 7 114 103 54 8 105 98 54 9 110 103 54 10 109 103 55 1 103 99 55 2 83 83 55 3 126 126 55 4 90 90 55 5 106 106 55 6 102 98 55 7 105 105 55 8 101 101 55 9 94 94 55 10 100 100 56 1 249 218 56 2 215 187 56 3 253 220 56 4 235 205 56 5 294 261 56 6 224 199 56 7 297 260 56 8 301 265 56 9 300 264 56 10 272 237 57 1 194 172 57 2 167 150 57 3 190 173 57 4 205 185 57 5 185 167 57 6 197 175 57 7 173 154 57 8 169 154 57 9 174 155 57 10 174 155 58 1 147 133 58 2 130 121 58 3 125 116 58 4 151 137 58 5 123 115 58 6 147 134 58 7 153 141 58 8 138 125 58 9 136 125 58 10 138 124 59 1 116 112 59 2 109 103 59 3 109 108 59 4 111 107 59 5 108 103 59 6 118 111 59 7 116 108 59 8 114 105 59 9 121 116 59 10 137 126 60 1 101 101 60 2 84 81 60 3 91 87 60 4 105 101 60 5 107 103 60 6 110 110 60 7 97 90 60 8 102 101 60 9 101 101 60 10 90 87 ------------------------------- verified 202 average error LB all 5.5 maximal error LB all 19.1