Lower Bounds LB2 based on LP of Mingozzi et al. [1998], and immediate selection (Brucker et al. [1998]), calculated with column generation by Baar et al. [1998] Problem LB2 ------------ 1 1 67 1 2 92 1 3 59 1 4 77 1 5 84 1 6 63 1 7 83 1 8 85 1 9 66 1 10 87 2 1 96 2 2 114 2 3 75 2 4 70 2 5 100 2 6 67 2 7 92 2 8 82 2 9 79 2 10 80 3 1 81 3 2 84 3 3 71 3 4 104 3 5 75 3 6 68 3 7 87 3 8 86 3 9 61 3 10 65 4 1 93 4 2 89 4 3 67 4 4 92 4 5 88 4 6 78 4 7 80 4 8 69 4 9 79 4 10 68 5 1 71 5 2 90 5 3 77 5 4 90 5 5 101 5 6 75 5 7 98 5 8 84 5 9 98 5 10 88 6 1 82 6 2 86 6 3 75 6 4 80 6 5 71 6 6 98 6 7 71 6 8 67 6 9 68 6 10 94 7 1 88 7 2 77 7 3 80 7 4 86 7 5 79 7 6 90 7 7 90 7 8 60 7 9 83 7 10 98 8 1 96 8 2 78 8 3 70 8 4 77 8 5 63 8 6 70 8 7 77 8 8 68 8 9 97 8 10 88 9 1 90 9 2 113 9 3 95 9 4 104 9 5 122 9 6 104 9 7 101 9 8 108 9 9 102 9 10 100 10 1 77 10 2 95 10 3 112 10 4 94 10 5 78 10 6 92 10 7 83 10 8 81 10 9 88 10 10 75 11 1 86 11 2 99 11 3 69 11 4 64 11 5 81 11 6 78 11 7 95 11 8 82 11 9 81 11 10 81 12 1 71 12 2 71 12 3 93 12 4 73 12 5 83 12 6 81 12 7 77 12 8 83 12 9 77 12 10 86 13 1 124 13 2 112 13 3 102 13 4 105 13 5 107 13 6 113 13 7 111 13 8 109 13 9 114 13 10 110 14 1 89 14 2 79 14 3 94 14 4 88 14 5 84 14 6 76 14 7 86 14 8 80 14 9 112 14 10 85 15 1 76 15 2 71 15 3 82 15 4 92 15 5 93 15 6 61 15 7 82 15 8 82 15 9 83 15 10 78 16 1 85 16 2 71 16 3 73 16 4 69 16 5 71 16 6 74 16 7 65 16 8 71 16 9 66 16 10 71 17 1 79 17 2 88 17 3 87 17 4 94 17 5 113 17 6 94 17 7 73 17 8 113 17 9 80 17 10 81 18 1 101 18 2 94 18 3 83 18 4 98 18 5 90 18 6 83 18 7 73 18 8 92 18 9 79 18 10 94 19 1 98 19 2 83 19 3 89 19 4 77 19 5 66 19 6 136 19 7 66 19 8 91 19 9 121 19 10 85 20 1 85 20 2 76 20 3 86 20 4 86 20 5 88 20 6 83 20 7 82 20 8 85 20 9 76 20 10 89 21 1 93 21 2 97 21 3 101 21 4 93 21 5 92 21 6 87 21 7 91 21 8 94 21 9 99 21 10 94 22 1 108 22 2 85 22 3 83 22 4 96 22 5 96 22 6 71 22 7 90 22 8 97 22 9 97 22 10 75 23 1 90 23 2 84 23 3 116 23 4 85 23 5 95 23 6 87 23 7 77 23 8 92 23 9 126 23 10 87 24 1 84 24 2 92 24 3 69 24 4 81 24 5 85 24 6 79 24 7 87 24 8 88 24 9 80 24 10 89 25 1 106 25 2 115 25 3 107 25 4 123 25 5 105 25 6 106 25 7 114 25 8 127 25 9 93 25 10 112 26 1 90 26 2 85 26 3 80 26 4 96 26 5 82 26 6 108 26 7 82 26 8 82 26 9 87 26 10 92 27 1 96 27 2 81 27 3 91 27 4 79 27 5 99 27 6 87 27 7 73 27 8 72 27 9 84 27 10 97 28 1 80 28 2 76 28 3 86 28 4 78 28 5 88 28 6 102 28 7 97 28 8 110 28 9 120 28 10 68 29 1 122 29 2 117 29 3 132 29 4 135 29 5 110 29 6 111 29 7 155 29 8 143 29 9 113 29 10 112 30 1 102 30 2 76 30 3 102 30 4 104 30 5 83 30 6 90 30 7 84 30 8 82 30 9 84 30 10 90 31 1 79 31 2 69 31 3 106 31 4 79 31 5 79 31 6 80 31 7 97 31 8 83 31 9 72 31 10 99 32 1 78 32 2 78 32 3 89 32 4 104 32 5 93 32 6 86 32 7 87 32 8 79 32 9 95 32 10 91 33 1 82 33 2 110 33 3 108 33 4 90 33 5 108 33 6 88 33 7 95 33 8 100 33 9 87 33 10 113 34 1 83 34 2 89 34 3 82 34 4 76 34 5 80 34 6 89 34 7 92 34 8 81 34 9 109 34 10 101 35 1 98 35 2 92 35 3 96 35 4 86 35 5 103 35 6 72 35 7 78 35 8 85 35 9 76 35 10 82 36 1 97 36 2 114 36 3 84 36 4 79 36 5 98 36 6 99 36 7 89 36 8 84 36 9 102 36 10 109 37 1 93 37 2 98 37 3 117 37 4 104 37 5 105 37 6 108 37 7 106 37 8 99 37 9 110 37 10 104 38 1 83 38 2 77 38 3 88 38 4 89 38 5 84 38 6 88 38 7 85 38 8 91 38 9 95 38 10 108 39 1 106 39 2 119 39 3 83 39 4 81 39 5 85 39 6 102 39 7 85 39 8 81 39 9 79 39 10 100 40 1 95 40 2 91 40 3 77 40 4 106 40 5 92 40 6 86 40 7 87 40 8 79 40 9 98 40 10 86 41 1 126 41 2 148 41 3 139 41 4 137 41 5 114 41 6 118 41 7 138 41 8 144 41 9 104 41 10 137 42 1 106 42 2 93 42 3 94 42 4 102 42 5 105 42 6 89 42 7 83 42 8 105 42 9 82 42 10 85 43 1 99 43 2 91 43 3 102 43 4 94 43 5 98 43 6 114 43 7 88 43 8 100 43 9 88 43 10 92 44 1 100 44 2 92 44 3 110 44 4 89 44 5 84 44 6 96 44 7 93 44 8 99 44 9 96 44 10 86 45 1 139 45 2 133 45 3 142 45 4 122 45 5 161 45 6 160 45 7 124 45 8 147 45 9 141 45 10 149 46 1 103 46 2 98 46 3 112 46 4 88 46 5 91 46 6 83 46 7 89 46 8 87 46 9 78 46 10 114 47 1 82 47 2 90 47 3 102 47 4 93 47 5 93 47 6 98 47 7 94 47 8 98 47 9 86 47 10 65 48 1 83 48 2 89 48 3 86 48 4 91 48 5 75 48 6 114 48 7 103 48 8 74 48 9 89 48 10 93