Lower Bounds LB based on constraint propagation (immediate selection) and linear programming (Brucker, Knust [2000]) Problem UBbest LB^0 LB -------------------------- 1 1 73 67 72 1 2 92 92 92 1 3 66 59 64 1 4 86 76 85 1 5 87 85 87 1 6 74 62 70 1 7 91 83 90 1 8 95 85 93 1 9 72 66 70 1 10 90 87 89 2 1 96 96 96 2 2 114 114 114 2 3 75 75 75 2 4 70 70 70 2 5 100 100 100 2 6 67 67 67 2 7 92 92 92 2 8 82 82 82 2 9 79 79 79 2 10 80 80 80 3 1 81 81 81 3 2 84 84 84 3 3 71 71 71 3 4 104 104 104 3 5 75 75 75 3 6 68 68 68 3 7 87 87 87 3 8 86 86 86 3 9 61 61 61 3 10 65 65 65 4 1 93 93 93 4 2 89 89 89 4 3 67 67 67 4 4 92 92 92 4 5 88 88 88 4 6 78 78 78 4 7 80 80 80 4 8 69 69 69 4 9 79 79 79 4 10 68 68 68 5 1 78 71 73 5 2 94 90 90 5 3 91 77 82 5 4 104 90 95 5 5 114 101 107 5 6 88 75 82 5 7 109 98 105 5 8 106 84 93 5 9 119 98 104 5 10 98 88 94 6 1 82 82 82 6 2 86 86 86 6 3 77 75 75 6 4 80 80 80 6 5 71 71 71 6 6 98 98 98 6 7 71 71 71 6 8 68 67 67 6 9 68 68 68 6 10 94 94 94 7 1 88 88 88 7 2 77 77 77 7 3 80 80 80 7 4 86 86 86 7 5 79 79 79 7 6 90 90 90 7 7 90 90 90 7 8 60 60 60 7 9 83 83 83 7 10 98 98 98 8 1 96 96 96 8 2 78 78 78 8 3 70 70 70 8 4 77 77 77 8 5 63 63 63 8 6 70 70 70 8 7 77 77 77 8 8 68 68 68 8 9 97 97 97 8 10 88 88 88 9 1 109 90 98 9 2 132 113 119 9 3 105 95 97 9 4 131 104 117 9 5 145 122 125 9 6 123 104 110 9 7 112 101 102 9 8 120 108 109 9 9 120 102 105 9 10 115 100 102 10 1 77 77 77 10 2 95 95 95 10 3 112 112 112 10 4 94 94 94 10 5 78 78 78 10 6 92 92 92 10 7 83 83 83 10 8 81 81 81 10 9 88 88 88 10 10 75 75 75 11 1 86 86 86 11 2 99 99 99 11 3 69 69 69 11 4 64 64 64 11 5 81 81 81 11 6 78 78 78 11 7 95 95 95 11 8 82 82 82 11 9 81 81 81 11 10 81 81 81 12 1 71 71 71 12 2 71 71 71 12 3 93 93 93 12 4 73 73 73 12 5 83 83 83 12 6 81 81 81 12 7 77 77 77 12 8 83 83 83 12 9 77 77 77 12 10 86 86 86 13 1 142 124 127 13 2 131 112 118 13 3 112 102 104 13 4 116 105 108 13 5 120 107 108 13 6 129 113 116 13 7 128 111 115 13 8 120 109 112 13 9 129 114 116 13 10 124 110 112 14 1 89 89 89 14 2 79 79 79 14 3 94 94 94 14 4 88 88 88 14 5 84 84 84 14 6 76 76 76 14 7 86 86 86 14 8 80 80 80 14 9 112 112 112 14 10 85 85 85 15 1 76 76 76 15 2 71 71 71 15 3 82 82 82 15 4 92 92 92 15 5 93 93 93 15 6 61 61 61 15 7 82 82 82 15 8 82 82 82 15 9 83 83 83 15 10 78 78 78 16 1 85 85 85 16 2 71 71 71 16 3 73 73 73 16 4 69 69 69 16 5 71 71 71 16 6 74 74 74 16 7 65 65 65 16 8 71 71 71 16 9 66 66 66 16 10 71 71 71 17 1 92 78 90 17 2 100 88 94 17 3 89 86 88 17 4 94 93 94 17 5 113 113 113 17 6 94 94 94 17 7 80 73 80 17 8 113 104 113 17 9 96 80 93 17 10 89 81 85 18 1 101 101 101 18 2 94 94 94 18 3 83 83 83 18 4 98 98 98 18 5 90 90 90 18 6 83 83 83 18 7 73 73 73 18 8 92 92 92 18 9 79 79 79 18 10 94 94 94 19 1 98 98 98 19 2 83 83 83 19 3 89 89 89 19 4 77 77 77 19 5 66 66 66 19 6 136 136 136 19 7 66 66 66 19 8 91 91 91 19 9 121 121 121 19 10 85 85 85 20 1 85 85 85 20 2 76 76 76 20 3 86 86 86 20 4 86 86 86 20 5 88 88 88 20 6 83 83 83 20 7 82 82 82 20 8 85 85 85 20 9 76 76 76 20 10 89 89 89 21 1 111 93 101 21 2 118 97 106 21 3 127 101 110 21 4 106 93 101 21 5 115 92 99 21 6 108 87 95 21 7 110 91 99 21 8 113 93 100 21 9 125 99 108 21 10 110 94 101 22 1 108 108 108 22 2 85 85 85 22 3 83 83 83 22 4 96 96 96 22 5 96 96 96 22 6 71 71 71 22 7 90 90 90 22 8 97 97 97 22 9 101 97 101 22 10 75 75 75 23 1 90 90 90 23 2 84 84 84 23 3 116 116 116 23 4 85 85 85 23 5 95 95 95 23 6 87 87 87 23 7 77 77 77 23 8 92 92 92 23 9 126 126 126 23 10 87 87 87 24 1 84 84 84 24 2 92 92 92 24 3 69 69 69 24 4 81 81 81 24 5 85 85 85 24 6 79 79 79 24 7 87 87 87 24 8 88 88 88 24 9 80 80 80 24 10 89 89 89 25 1 128 106 114 25 2 135 115 120 25 3 128 107 111 25 4 142 123 127 25 5 118 105 109 25 6 123 106 112 25 7 133 114 120 25 8 144 127 129 25 9 109 93 97 25 10 133 112 118 26 1 90 90 90 26 2 85 85 85 26 3 80 80 80 26 4 98 96 96 26 5 86 82 82 26 6 108 108 108 26 7 82 82 82 26 8 83 82 82 26 9 87 87 87 26 10 92 92 92 27 1 96 96 96 27 2 81 81 81 27 3 91 91 91 27 4 79 79 79 27 5 99 99 99 27 6 87 87 87 27 7 73 73 73 27 8 72 72 72 27 9 84 84 84 27 10 97 97 97 28 1 80 80 80 28 2 76 76 76 28 3 86 86 86 28 4 78 78 78 28 5 88 88 88 28 6 102 102 102 28 7 97 97 97 28 8 110 110 110 28 9 120 120 120 28 10 68 68 68 29 1 139 122 125 29 2 129 117 120 29 3 148 132 135 29 4 154 135 138 29 5 125 110 114 29 6 128 111 116 29 7 175 155 158 29 8 160 143 145 29 9 132 113 118 29 10 128 112 117 30 1 102 102 102 30 2 76 76 76 30 3 102 102 102 30 4 104 104 104 30 5 85 83 83 30 6 90 90 90 30 7 85 84 84 30 8 82 82 82 30 9 96 83 90 30 10 90 90 90 31 1 79 79 79 31 2 69 69 69 31 3 106 106 106 31 4 79 79 79 31 5 79 79 79 31 6 80 80 80 31 7 97 97 97 31 8 83 83 83 31 9 72 72 72 31 10 99 99 99 32 1 78 78 78 32 2 78 78 78 32 3 89 89 89 32 4 104 104 104 32 5 93 93 93 32 6 86 86 86 32 7 87 87 87 32 8 79 79 79 32 9 95 95 95 32 10 91 91 91 33 1 99 82 94 33 2 112 109 112 33 3 108 105 108 33 4 92 90 91 33 5 109 108 109 33 6 88 88 88 33 7 109 95 105 33 8 110 100 107 33 9 95 86 93 33 10 114 113 114 34 1 83 83 83 34 2 89 89 89 34 3 82 82 82 34 4 81 76 81 34 5 83 80 81 34 6 89 89 89 34 7 92 92 92 34 8 81 80 81 34 9 109 109 109 34 10 101 101 101 35 1 98 98 98 35 2 92 92 92 35 3 96 96 96 35 4 86 86 86 35 5 103 103 103 35 6 72 72 72 35 7 78 78 78 35 8 85 85 85 35 9 76 76 76 35 10 82 82 82 36 1 97 97 97 36 2 114 114 114 36 3 84 84 84 36 4 79 79 79 36 5 98 98 98 36 6 99 99 99 36 7 89 89 89 36 8 84 84 84 36 9 102 102 102 36 10 109 109 109 37 1 111 93 99 37 2 116 98 103 37 3 133 117 123 37 4 124 104 111 37 5 129 105 110 37 6 134 108 117 37 7 123 106 112 37 8 122 99 106 37 9 124 110 115 37 10 126 104 111 38 1 85 83 83 38 2 78 77 77 38 3 89 88 88 38 4 89 89 89 38 5 86 84 84 38 6 88 88 88 38 7 85 85 85 38 8 91 91 91 38 9 95 95 95 38 10 108 108 108 39 1 106 106 106 39 2 119 119 119 39 3 83 83 83 39 4 81 81 81 39 5 85 85 85 39 6 102 102 102 39 7 85 85 85 39 8 81 81 81 39 9 79 79 79 39 10 100 100 100 40 1 95 95 95 40 2 91 91 91 40 3 77 77 77 40 4 106 106 106 40 5 92 92 92 40 6 86 86 86 40 7 87 87 87 40 8 79 79 79 40 9 98 98 98 40 10 86 86 86 41 1 145 126 128 41 2 174 148 151 41 3 167 139 146 41 4 157 137 140 41 5 132 114 115 41 6 139 118 123 41 7 161 138 143 41 8 168 144 147 41 9 122 104 109 41 10 155 137 141 42 1 106 106 106 42 2 102 93 97 42 3 94 94 94 42 4 102 102 102 42 5 105 105 105 42 6 89 89 89 42 7 87 83 83 42 8 105 105 105 42 9 84 82 82 42 10 91 85 86 43 1 99 99 99 43 2 91 91 91 43 3 102 102 102 43 4 94 94 94 43 5 98 98 98 43 6 114 114 114 43 7 88 88 88 43 8 100 100 100 43 9 88 88 88 43 10 92 92 92 44 1 100 100 100 44 2 92 92 92 44 3 110 110 110 44 4 89 89 89 44 5 84 84 84 44 6 96 96 96 44 7 93 93 93 44 8 99 99 99 44 9 96 96 96 44 10 86 86 86 45 1 150 139 142 45 2 153 133 136 45 3 159 142 143 45 4 139 122 125 45 5 180 161 162 45 6 182 160 162 45 7 140 124 127 45 8 165 147 149 45 9 162 141 144 45 10 170 149 154 46 1 105 103 103 46 2 98 98 98 46 3 113 112 112 46 4 94 88 90 46 5 91 91 91 46 6 83 83 83 46 7 89 89 89 46 8 98 87 93 46 9 90 78 85 46 10 114 114 114 47 1 82 82 82 47 2 90 90 90 47 3 102 102 102 47 4 93 93 93 47 5 93 93 93 47 6 98 98 98 47 7 94 94 94 47 8 98 98 98 47 9 86 86 86 47 10 65 65 65 48 1 83 83 83 48 2 89 89 89 48 3 86 86 86 48 4 91 91 91 48 5 75 75 75 48 6 114 114 114 48 7 103 103 103 48 8 74 74 74 48 9 89 89 89 48 10 93 93 93 ------------------------------- verified 350 average error LB all 2.1 maximal error LB all 14.7 average error LB 0.2 7.9 average error LB0 0.2 12.1