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 77 1 2 68 1 3 68 1 4 91 1 5 73 1 6 61 1 7 61 1 8 71 1 9 85 1 10 80 2 1 65 2 2 82 2 3 78 2 4 78 2 5 53 2 6 64 2 7 49 2 8 66 2 9 65 2 10 64 3 1 60 3 2 69 3 3 105 3 4 81 3 5 83 3 6 57 3 7 59 3 8 52 3 9 67 3 10 69 4 1 84 4 2 60 4 3 58 4 4 65 4 5 75 4 6 71 4 7 67 4 8 65 4 9 75 4 10 77 5 1 67 5 2 89 5 3 64 5 4 59 5 5 89 5 6 65 5 7 63 5 8 65 5 9 82 5 10 77 6 1 60 6 2 66 6 3 72 6 4 67 6 5 78 6 6 53 6 7 60 6 8 72 6 9 64 6 10 74 7 1 77 7 2 85 7 3 62 7 4 63 7 5 71 7 6 65 7 7 89 7 8 66 7 9 44 7 10 82 8 1 64 8 2 61 8 3 79 8 4 64 8 5 83 8 6 56 8 7 62 8 8 66 8 9 58 8 10 97 9 1 79 9 2 74 9 3 89 9 4 73 9 5 76 9 6 94 9 7 93 9 8 85 9 9 87 9 10 82 10 1 85 10 2 62 10 3 72 10 4 80 10 5 79 10 6 67 10 7 69 10 8 64 10 9 73 10 10 73 11 1 71 11 2 61 11 3 76 11 4 69 11 5 65 11 6 70 11 7 70 11 8 69 11 9 62 11 10 58 12 1 59 12 2 58 12 3 75 12 4 69 12 5 63 12 6 54 12 7 71 12 8 60 12 9 59 12 10 79 13 1 103 13 2 100 13 3 81 13 4 91 13 5 89 13 6 85 13 7 78 13 8 109 13 9 91 13 10 109 14 1 59 14 2 65 14 3 61 14 4 65 14 5 59 14 6 65 14 7 69 14 8 88 14 9 61 14 10 67 15 1 84 15 2 89 15 3 72 15 4 75 15 5 70 15 6 76 15 7 64 15 8 79 15 9 72 15 10 61 16 1 64 16 2 64 16 3 53 16 4 60 16 5 66 16 6 66 16 7 82 16 8 68 16 9 54 16 10 68 17 1 76 17 2 69 17 3 89 17 4 71 17 5 58 17 6 67 17 7 83 17 8 70 17 9 76 17 10 72 18 1 81 18 2 69 18 3 77 18 4 71 18 5 80 18 6 61 18 7 93 18 8 78 18 9 69 18 10 97 19 1 62 19 2 83 19 3 83 19 4 67 19 5 73 19 6 68 19 7 60 19 8 87 19 9 67 19 10 78 20 1 60 20 2 78 20 3 69 20 4 86 20 5 71 20 6 97 20 7 74 20 8 65 20 9 74 20 10 70 21 1 88 21 2 99 21 3 78 21 4 80 21 5 75 21 6 70 21 7 90 21 8 93 21 9 73 21 10 75 22 1 62 22 2 83 22 3 70 22 4 65 22 5 76 22 6 79 22 7 69 22 8 59 22 9 65 22 10 70 23 1 75 23 2 69 23 3 78 23 4 83 23 5 72 23 6 81 23 7 60 23 8 72 23 9 64 23 10 68 24 1 65 24 2 55 24 3 67 24 4 78 24 5 76 24 6 75 24 7 68 24 8 81 24 9 80 24 10 66 25 1 101 25 2 86 25 3 98 25 4 93 25 5 84 25 6 99 25 7 81 25 8 85 25 9 87 25 10 91 26 1 80 26 2 63 26 3 71 26 4 65 26 5 61 26 6 73 26 7 72 26 8 89 26 9 62 26 10 85 27 1 96 27 2 74 27 3 76 27 4 60 27 5 78 27 6 64 27 7 83 27 8 88 27 9 76 27 10 57 28 1 92 28 2 64 28 3 72 28 4 84 28 5 71 28 6 89 28 7 75 28 8 62 28 9 74 28 10 74 29 1 94 29 2 119 29 3 112 29 4 123 29 5 99 29 6 142 29 7 113 29 8 90 29 9 101 29 10 108 30 1 70 30 2 65 30 3 80 30 4 76 30 5 72 30 6 68 30 7 77 30 8 63 30 9 98 30 10 81 31 1 65 31 2 74 31 3 66 31 4 68 31 5 72 31 6 72 31 7 76 31 8 75 31 9 86 31 10 56 32 1 69 32 2 114 32 3 85 32 4 56 32 5 77 32 6 93 32 7 76 32 8 76 32 9 74 32 10 77 33 1 90 33 2 100 33 3 79 33 4 81 33 5 98 33 6 65 33 7 70 33 8 74 33 9 108 33 10 75 34 1 71 34 2 68 34 3 61 34 4 83 34 5 80 34 6 81 34 7 83 34 8 62 34 9 77 34 10 92 35 1 78 35 2 77 35 3 89 35 4 72 35 5 75 35 6 79 35 7 73 35 8 78 35 9 76 35 10 70 36 1 61 36 2 75 36 3 81 36 4 85 36 5 57 36 6 76 36 7 71 36 8 69 36 9 86 36 10 77 37 1 83 37 2 76 37 3 126 37 4 85 37 5 83 37 6 83 37 7 93 37 8 81 37 9 83 37 10 91 38 1 73 38 2 71 38 3 77 38 4 58 38 5 103 38 6 86 38 7 74 38 8 68 38 9 66 38 10 63 39 1 80 39 2 84 39 3 83 39 4 92 39 5 73 39 6 83 39 7 68 39 8 77 39 9 72 39 10 74 40 1 86 40 2 81 40 3 70 40 4 87 40 5 83 40 6 69 40 7 68 40 8 80 40 9 90 40 10 73 41 1 107 41 2 100 41 3 85 41 4 115 41 5 103 41 6 120 41 7 116 41 8 120 41 9 113 41 10 100 42 1 83 42 2 68 42 3 73 42 4 95 42 5 73 42 6 82 42 7 55 42 8 78 42 9 70 42 10 87 43 1 108 43 2 85 43 3 74 43 4 74 43 5 64 43 6 84 43 7 89 43 8 69 43 9 70 43 10 78 44 1 84 44 2 68 44 3 87 44 4 77 44 5 74 44 6 81 44 7 76 44 8 83 44 9 65 44 10 65 45 1 88 45 2 132 45 3 130 45 4 99 45 5 98 45 6 132 45 7 112 45 8 117 45 9 113 45 10 101 46 1 78 46 2 78 46 3 79 46 4 71 46 5 84 46 6 87 46 7 75 46 8 72 46 9 62 46 10 82 47 1 75 47 2 66 47 3 69 47 4 76 47 5 87 47 6 76 47 7 68 47 8 71 47 9 76 47 10 66 48 1 71 48 2 87 48 3 84 48 4 62 48 5 101 48 6 66 48 7 77 48 8 88 48 9 82 48 10 70