Lower Bounds LB based on constraint propagation (immediate selection) and linear programming (Brucker, Knust [2000]) Problem UBbest LB^0 LB -------------------------- 1 1 77 77 77 1 2 68 68 68 1 3 68 68 68 1 4 91 91 91 1 5 73 71 73 1 6 66 61 66 1 7 72 61 70 1 8 75 71 75 1 9 85 85 85 1 10 80 80 80 2 1 65 65 65 2 2 82 82 82 2 3 78 78 78 2 4 78 78 78 2 5 54 54 54 2 6 64 64 64 2 7 53 53 53 2 8 66 66 66 2 9 65 65 65 2 10 69 69 69 3 1 60 60 60 3 2 69 69 69 3 3 105 105 105 3 4 81 81 81 3 5 83 83 83 3 6 57 57 57 3 7 59 59 59 3 8 55 52 53 3 9 67 67 67 3 10 69 67 69 4 1 84 84 84 4 2 60 60 60 4 3 58 58 58 4 4 65 65 65 4 5 75 75 75 4 6 71 71 71 4 7 67 67 67 4 8 65 65 65 4 9 75 75 75 4 10 77 77 77 5 1 77 67 72 5 2 106 89 96 5 3 81 64 75 5 4 72 59 63 5 5 108 89 94 5 6 75 64 71 5 7 75 63 66 5 8 78 65 72 5 9 83 82 82 5 10 82 77 79 6 1 60 60 60 6 2 67 66 66 6 3 72 72 72 6 4 67 67 67 6 5 78 78 78 6 6 55 53 53 6 7 61 60 60 6 8 72 72 72 6 9 64 64 64 6 10 74 74 74 7 1 77 77 77 7 2 85 85 85 7 3 62 62 62 7 4 63 63 63 7 5 71 71 71 7 6 65 65 65 7 7 89 89 89 7 8 66 66 66 7 9 44 44 44 7 10 82 82 82 8 1 64 64 64 8 2 61 61 61 8 3 79 79 79 8 4 64 64 64 8 5 83 83 83 8 6 56 56 56 8 7 62 62 62 8 8 66 66 66 8 9 58 58 58 8 10 97 97 97 9 1 89 79 82 9 2 84 74 77 9 3 102 89 91 9 4 90 73 79 9 5 87 76 77 9 6 113 94 100 9 7 113 93 100 9 8 99 85 89 9 9 102 87 91 9 10 96 82 85 10 1 85 85 85 10 2 62 62 62 10 3 72 72 72 10 4 80 80 80 10 5 79 79 79 10 6 67 67 67 10 7 69 69 69 10 8 65 64 64 10 9 73 73 73 10 10 73 73 73 11 1 71 71 71 11 2 61 61 61 11 3 76 76 76 11 4 69 69 69 11 5 65 65 65 11 6 70 70 70 11 7 70 70 70 11 8 69 69 69 11 9 62 62 62 11 10 58 58 58 12 1 59 59 59 12 2 58 58 58 12 3 75 75 75 12 4 69 69 69 12 5 63 63 63 12 6 54 54 54 12 7 71 71 71 12 8 60 60 60 12 9 59 59 59 12 10 79 79 79 13 1 115 103 104 13 2 109 100 101 13 3 90 81 82 13 4 106 91 97 13 5 100 89 91 13 6 96 85 90 13 7 90 78 80 13 8 124 109 112 13 9 104 91 95 13 10 120 109 112 14 1 61 59 59 14 2 65 65 65 14 3 62 61 61 14 4 65 65 65 14 5 59 59 59 14 6 65 65 65 14 7 69 69 69 14 8 88 88 88 14 9 61 61 61 14 10 73 67 68 15 1 84 84 84 15 2 89 89 89 15 3 72 72 72 15 4 75 75 75 15 5 70 70 70 15 6 76 76 76 15 7 64 64 64 15 8 79 79 79 15 9 72 72 72 15 10 61 61 61 16 1 64 64 64 16 2 64 64 64 16 3 53 53 53 16 4 60 60 60 16 5 66 66 66 16 6 66 66 66 16 7 82 82 82 16 8 68 68 68 16 9 54 54 54 16 10 68 68 68 17 1 86 76 83 17 2 69 67 69 17 3 89 83 89 17 4 71 71 71 17 5 59 52 58 17 6 69 67 68 17 7 83 81 83 17 8 85 70 81 17 9 76 76 76 17 10 72 66 72 18 1 81 81 81 18 2 69 69 69 18 3 77 77 77 18 4 71 71 71 18 5 80 80 80 18 6 61 61 61 18 7 93 93 93 18 8 78 78 78 18 9 69 69 69 18 10 97 97 97 19 1 62 62 62 19 2 83 83 83 19 3 83 83 83 19 4 67 67 67 19 5 73 73 73 19 6 69 69 69 19 7 60 60 60 19 8 87 87 87 19 9 69 69 69 19 10 78 78 78 20 1 60 60 60 20 2 78 78 78 20 3 69 69 69 20 4 86 86 86 20 5 71 71 71 20 6 97 97 97 20 7 74 74 74 20 8 65 65 65 20 9 74 74 74 20 10 70 70 70 21 1 103 88 91 21 2 108 99 102 21 3 87 75 80 21 4 95 80 83 21 5 89 75 81 21 6 84 70 77 21 7 103 90 95 21 8 110 93 100 21 9 89 73 78 21 10 80 75 77 22 1 64 62 62 22 2 83 83 83 22 3 70 70 70 22 4 73 65 70 22 5 76 76 76 22 6 79 79 79 22 7 69 69 69 22 8 59 59 59 22 9 65 65 65 22 10 70 70 70 23 1 75 75 75 23 2 69 69 69 23 3 78 78 78 23 4 83 83 83 23 5 72 72 72 23 6 81 81 81 23 7 60 60 60 23 8 72 72 72 23 9 64 64 64 23 10 68 68 68 24 1 65 65 65 24 2 55 55 55 24 3 67 67 67 24 4 78 78 78 24 5 76 76 76 24 6 75 75 75 24 7 68 68 68 24 8 81 81 81 24 9 80 80 80 24 10 66 66 66 25 1 116 101 103 25 2 101 86 90 25 3 115 98 103 25 4 110 93 97 25 5 100 84 86 25 6 114 99 102 25 7 92 81 83 25 8 102 85 89 25 9 100 87 89 25 10 110 91 98 26 1 80 80 80 26 2 66 63 63 26 3 76 71 72 26 4 67 65 65 26 5 61 61 61 26 6 74 73 73 26 7 72 72 72 26 8 89 89 89 26 9 65 62 62 26 10 85 85 85 27 1 96 96 96 27 2 74 74 74 27 3 76 76 76 27 4 60 60 60 27 5 78 78 78 27 6 64 64 64 27 7 83 83 83 27 8 88 88 88 27 9 76 76 76 27 10 57 57 57 28 1 92 92 92 28 2 64 64 64 28 3 72 72 72 28 4 84 84 84 28 5 71 71 71 28 6 89 89 89 28 7 75 75 75 28 8 62 62 62 28 9 74 74 74 28 10 74 74 74 29 1 106 94 96 29 2 135 119 122 29 3 123 112 114 29 4 139 123 126 29 5 113 99 102 29 6 157 142 143 29 7 126 113 114 29 8 105 90 96 29 9 116 101 104 29 10 123 108 111 30 1 70 70 70 30 2 70 65 66 30 3 82 80 80 30 4 76 76 76 30 5 76 72 72 30 6 68 68 68 30 7 87 77 83 30 8 63 63 63 30 9 98 98 98 30 10 87 81 82 31 1 65 65 65 31 2 74 74 74 31 3 66 66 66 31 4 68 68 68 31 5 72 72 72 31 6 72 72 72 31 7 76 76 76 31 8 75 75 75 31 9 86 86 86 31 10 56 56 56 32 1 69 69 69 32 2 114 114 114 32 3 85 85 85 32 4 56 56 56 32 5 77 77 77 32 6 93 93 93 32 7 76 76 76 32 8 76 76 76 32 9 74 74 74 32 10 77 77 77 33 1 105 90 103 33 2 100 100 100 33 3 79 79 79 33 4 81 81 81 33 5 108 98 107 33 6 75 65 71 33 7 78 70 75 33 8 79 74 77 33 9 108 102 108 33 10 84 75 83 34 1 72 71 72 34 2 68 68 68 34 3 61 61 61 34 4 83 83 83 34 5 80 80 80 34 6 81 81 81 34 7 85 83 83 34 8 63 63 63 34 9 77 77 77 34 10 92 92 92 35 1 78 78 78 35 2 77 77 77 35 3 89 89 89 35 4 72 72 72 35 5 76 76 76 35 6 79 79 79 35 7 73 73 73 35 8 78 78 78 35 9 76 76 76 35 10 71 71 71 36 1 61 61 61 36 2 75 75 75 36 3 81 81 81 36 4 85 85 85 36 5 57 57 57 36 6 76 76 76 36 7 71 71 71 36 8 69 69 69 36 9 86 86 86 36 10 77 77 77 37 1 97 83 85 37 2 95 76 81 37 3 139 126 134 37 4 101 85 96 37 5 98 83 88 37 6 102 83 89 37 7 110 93 100 37 8 93 81 88 37 9 96 83 89 37 10 96 88 94 38 1 73 73 73 38 2 77 71 71 38 3 77 77 77 38 4 58 58 58 38 5 103 103 103 38 6 86 86 86 38 7 74 74 74 38 8 71 68 70 38 9 66 66 66 38 10 66 63 63 39 1 80 80 80 39 2 84 84 84 39 3 83 83 83 39 4 92 92 92 39 5 73 73 73 39 6 84 83 84 39 7 68 68 68 39 8 77 77 77 39 9 72 72 72 39 10 74 74 74 40 1 86 86 86 40 2 81 81 81 40 3 70 70 70 40 4 87 87 87 40 5 83 83 83 40 6 69 69 69 40 7 68 68 68 40 8 80 80 80 40 9 90 90 90 40 10 73 73 73 41 1 122 107 110 41 2 114 100 101 41 3 100 85 88 41 4 133 115 118 41 5 117 103 105 41 6 135 120 120 41 7 132 116 124 41 8 135 120 123 41 9 132 113 117 41 10 111 100 104 42 1 83 83 83 42 2 68 68 68 42 3 78 73 73 42 4 103 95 100 42 5 73 73 73 42 6 82 82 82 42 7 59 55 55 42 8 82 78 78 42 9 71 70 70 42 10 87 87 87 43 1 108 108 108 43 2 85 85 85 43 3 74 74 74 43 4 75 74 74 43 5 64 64 64 43 6 84 84 84 43 7 89 89 89 43 8 69 69 69 43 9 70 70 70 43 10 78 78 78 44 1 84 84 84 44 2 68 68 68 44 3 87 87 87 44 4 77 77 77 44 5 74 74 74 44 6 81 81 81 44 7 76 76 76 44 8 83 83 83 44 9 65 65 65 44 10 65 65 65 45 1 98 88 89 45 2 146 132 134 45 3 144 130 132 45 4 109 99 100 45 5 108 98 99 45 6 146 132 132 45 7 124 112 113 45 8 131 117 119 45 9 126 113 114 45 10 117 101 102 46 1 79 78 78 46 2 78 78 78 46 3 80 79 79 46 4 74 71 71 46 5 91 84 87 46 6 90 87 87 46 7 79 75 75 46 8 75 72 72 46 9 69 61 65 46 10 89 82 84 47 1 75 75 75 47 2 66 66 66 47 3 69 69 69 47 4 76 76 76 47 5 87 87 87 47 6 76 76 76 47 7 68 68 68 47 8 71 71 71 47 9 76 76 76 47 10 66 66 66 48 1 71 71 71 48 2 87 87 87 48 3 84 84 84 48 4 62 62 62 48 5 101 101 101 48 6 66 66 66 48 7 77 77 77 48 8 88 88 88 48 9 82 82 82 48 10 70 70 70 ------------------------------- verified 340 average error LB all 2.1 maximal error LB all 14.7 average error LB 0.2 7.2 average error LB0 0.2 11.1