Vol.2, No.x, April 2015, pp.xx-xx ISSN xxxx-xxxx 2015 4 30 2015 5 25 253-8550 1100 Tel 0467-53-2111( ) Fax 0467-54-3734 http://www.bunkyo.ac.jp/faculty/business/
1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The Boston Public Schools system, BPS (Deferred Acceptance system, DA) (Top Trading Cycles system, TTC) cf. [13] [1] cf. [7, 14, 15, 11] cf. [13, 7] 3 BPS DA TTC cf. [13] TTC DA cf. [14] 3 DA TTC DA DA (DA) cf. [13] DA cf. [13] DA (cf. [13]) 2
3 4 BPS, DA, TTC 3 cf. [2] 1 3 2 1 1 2 1 1 GPA GPA 1 3 1 [9] 1 1 cf. [13] GPA 3
TTC cf. [2] cf. [2] DA 2 2.1 n = 204 m = 9 i j x ij = 1 x ij = 0 {0, 1}- b = 25 i j c ij max. s.t. n m c ij x ij (2.1) i=1 j=1 n x ij b j (j = 1,, m) (2.2) i=1 m x ij = 1 (i = 1,, n) (2.3) j=1 x ij {0, 1} (i = 1,, n, j = 1,, m) (2.4) (2.4) {0, 1}- (2.2) (2.3) (2.1) (2.2) (2.4) max. m c ij x ij ( i {1, 2,, n}) (2.5) j=1 1 (2.1) (2.5) cf. [6] 4
[8, 9] 3 45 17 200 17 9 17 1 2 2 1 2 100 9 2 10 204 9 3 1 3 1 100 2 60 3 30 4 9-999 cf. [2] [ 1 2 ] = 40 > 30 = [ 2 3 ] 9 3 3 3 2 3 10 2.1 25 1.1 cf. [2, 3] 2.1: 10 \ 1 2 3 1 33.9 30.8 31.6 96.3 2 29.0 30.4 28.2 87.5 3 33.5 29.7 23.8 87.0 4 20.5 20.2 23.2 63.8 5 22.0 22.5 22.5 67.0 6 20.5 22.9 21.8 65.3 7 9.0 10.7 13.5 33.2 8 9.5 10.8 14.4 34.7 9 11.4 11.7 11.5 34.6 5
Excel python2.7 gurobi5.6.3 32bit CPU Intel(R) Core(TM) i7 [2.93GHz] 4GB 1 2.2 2.2 10 1 3 9 1 3 4 6 7 9 2.2: 1 3 10 25 d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 94.3 92.5 95.0 93.3 90.7 93.7 93.7 93.8 93.5 93.5 93.4 1 175 171 182 170 165 175 172 177 174 173 173.4 2 29 26 17 34 28 25 32 21 26 28 26.6 3 0 7 5 0 11 4 0 6 4 3 4.0 204 204 204 204 204 204 204 204 204 204 1 25 25 25 25 25 25 25 25 25 25 25.0 2 25 25 25 25 25 25 25 25 25 25 25.0 3 25 25 25 25 25 25 25 25 25 25 25.0 4 25 25 25 21 25 25 22 25 25 25 24.3 5 25 25 25 25 25 25 25 25 25 25 25.0 6 25 25 25 25 25 25 25 25 25 25 25.0 7 11 15 16 24 18 19 17 15 19 15 16.9 8 21 21 20 13 17 15 17 16 15 22 17.7 9 22 18 18 21 19 20 23 23 20 17 20.1 204 204 204 204 204 204 204 204 204 204 2.2 8 1 1 2 3 4 0 9 3 1.1 1 1 1 2.3, 2.4 10 24 3 26 2 7 9 6
2.3: 1 3 10 24 d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 93.2 91.0 93.5 92.4 89.4 92.3 92.8 92.3 92.1 92.1 92.1 1 171 167 177 166 161 170 169 170 169 168 168.8 2 31 25 19 37 28 27 33 27 28 30 28.5 3 2 12 8 1 15 7 2 7 7 6 6.7 204 204 204 204 204 204 204 204 204 204 1 24 24 24 24 24 24 24 24 24 24 24.0 2 24 24 24 24 24 24 24 24 24 24 24.0 3 24 24 24 24 24 24 24 24 24 24 24.0 4 24 24 24 24 24 24 24 24 24 24 24.0 5 24 24 24 24 24 24 24 24 24 24 24.0 6 24 24 24 24 24 24 24 24 24 24 24.0 7 13 20 19 24 19 19 19 19 23 18 19.3 8 24 22 20 14 19 23 17 17 17 23 19.6 9 23 18 21 22 22 18 24 24 20 19 21.1 204 204 204 204 204 204 204 204 204 204 2.4: 1 3 10 26 d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 95.1 94.0 96.3 94.1 92.1 95.1 94.3 95.1 94.9 94.9 94.6 1 179 175 185 174 168 179 175 180 178 178 177.1 2 25 27 19 30 30 25 29 23 26 26 26.0 3 0 2 0 0 6 0 0 1 0 0 0.9 204 204 204 204 204 204 204 204 204 204 1 26 26 26 26 26 26 26 26 26 26 26.0 2 26 26 26 26 26 26 26 26 26 26 26.0 3 26 26 26 26 26 26 26 26 26 26 26.0 4 24 26 26 23 26 26 19 26 26 26 24.8 5 23 26 26 26 26 26 26 26 26 26 25.7 6 26 26 26 24 26 26 26 26 26 26 25.8 7 10 16 15 22 15 19 16 12 20 13 15.8 8 24 18 19 13 17 13 16 14 10 19 16.3 9 19 14 14 18 16 16 23 22 18 16 17.6 204 204 204 204 204 204 204 204 204 204 25 7
2.3 1 GPA GPA 2 1 N(2, 1) 10 GPA 2015 4 2 4 GPA 2 1.98, 0.68) 3 (1.88, 0.67 4 (1.87, 0.68 2.1 GPA 0.2 2.1: GPA 0.2 GPA 2 1 1 3 1 1 100 GPA GPA 2.67 1 102.67 1 100 100 104 1 [9] 2 A, B GPA 3 2 1 GPA 1 2 3 A 103 63 33 B 102 62 32 8
(2.1) (A 1, B 2 )103 + 62 = 102 + 63(B 1, A 2 ) 1 1 1 2 3 A 103 60 30 B 102 60 30 (A 1, B 2 )103 + 60 > 102 + 60(B 1, A 2 ) A 1 2 1 3 2 GP A, 1.5 GP A, 1 GP A 1 2 3 A 106.0 64.5 33.0 B 104.0 63.0 32.0 (A 1, B 2 )106.0 + 63.0 > 104.0 + 64.5(B 1, A 2 ) A 1 2 2.5, 2.6 204 GPA 10 GPA 1 204 1 3 2.5 4 9(2) 1(1) GPA 4 9(2) 9 2 GPA 1(1) 1 1 1 3 10 16 5% 8% 9
2.5: 1 GPA 4 9(2) 1(1) 9 6(2) 1(1) 11 5(2) 1(1) 5 9(2) 3(1) 1 7(3) 1(1) 23 5(2) 1(1) 11 6(2) 5(1) 25 9(3) 1(1) 12 7(2) 1(1) 6 4(2) 3(1) 40 9(2) 3(1) 16 7(3) 5(1) 40 6(2) 3(1) 22 7(2) 1(1) 7 6(2) 3(1) 52 9(2) 3(1) 50 9(3) 6(2) 95 1(1) 8(3) 31 7(2) 3(1) 21 7(2) 2(1) 57 5(2) 6(1) 59 5(1) 6(2) 106 9(3) 3(1) 47 8(2) 3(1) 29 5(2) 3(1) 62 9(2) 3(1) 86 9(3) 1(1) 127 5(2) 1(1) 53 8(2) 5(1) 46 4(2) 1(1) 77 5(2) 2(1) 111 9(2) 4(1) 142 3(1) 9(3) 92 6(2) 2(1) 48 7(3) 1(1) 79 4(2) 2(1) 147 2(2) 3(1) 148 1(1) 5(2) 113 2(1) 7(2) 63 3(1) 6(2) 95 3(1) 8(2) 149 8(3) 5(1) 149 6(2) 1(1) 117 3(1) 7(2) 86 2(1) 9(2) 151 2(1) 5(2) 154 4(1) 7(2) 189 1(1) 6(2) 120 1(1) 4(2) 125 1(1) 6(2) 153 1(1) 4(2) 159 1(1) 7(3) 198 1(1) 6(2) 156 3(1) 4(2) 133 3(1) 5(2) 154 3(1) 5(2) 160 1(1) 2(2) 201 3(1) 5(2) 157 5(1) 4(2) 144 1(1) 9(3) 155 2(1) 8(2) 182 5(1) 8(3) 158 3(1) 4(2) 157 6(2) 8(3) 165 3(1) 9(2) 189 5(1) 7(3) 187 6(2) 3(1) 168 3(1) 4(2) 183 1(1) 5(2) 196 3(1) 8(3) 196 3(1) 6(2) 196 1(1) 4(2) 197 6(1) 8(2) 203 1(1) 6(2) 7 7(3) 2(1) 4 7(2) 2(1) 4 8(3) 3(1) 13 8(3) 2(1) 1 6(2) 1(1) 15 4(2) 2(1) 6 8(2) 3(1) 12 6(2) 3(1) 14 8(3) 3(1) 13 9(2) 2(1) 16 7(2) 3(1) 22 5(2) 3(1) 19 7(2) 1(1) 50 9(2) 1(1) 50 8(2) 5(1) 27 7(2) 5(1) 72 9(2) 1(1) 34 6(2) 3(1) 62 8(2) 4(1) 58 9(2) 4(1) 42 9(3) 2(1) 77 9(2) 1(1) 46 9(2) 1(1) 66 1(1) 7(2) 87 9(2) 2(1) 45 7(2) 5(1) 88 9(2) 1(1) 64 5(2) 2(1) 71 8(2) 4(1) 92 5(1) 8(2) 62 5(1) 7(2) 113 1(1) 9(2) 86 3(1) 5(2) 72 5(2) 3(1) 95 4(1) 8(2) 65 2(1) 8(3) 127 2(1) 9(2) 123 1(1) 9(2) 84 9(2) 4(1) 132 1(1) 6(2) 86 9(3) 1(1) 130 1(1) 9(2) 128 4(2) 2(1) 112 4(1) 8(2) 159 2(1) 7(2) 118 4(2) 1(1) 132 1(1) 9(2) 141 3(1) 6(2) 113 4(1) 7(2) 182 2(1) 7(2) 139 1(1) 4(2) 143 1(1) 9(2) 150 2(1) 9(3) 125 5(2) 2(1) 150 2(1) 4(2) 158 6(2) 1(1) 151 3(1) 4(2) 128 2(1) 5(2) 169 3(1) 7(2) 172 3(1) 5(2) 171 1(1) 9(2) 144 4(1) 9(2) 175 2(1) 8(3) 202 3(1) 6(2) 197 2(1) 6(2) 167 3(1) 7(3) 195 1(1) 8(3) 186 3(1) 5(2) 202 5(1) 8(2) 197 2(1) 9(3) 1 2.5 2 2.6 10 3 d3, d6, d10 2 2 3 1 10
2.6: 1 3 GPA 4 9(2) 1(1) 9 6(2) 1(1) 11 5(2) 1(1) 5 9(2) 3(1) 1 7(3) 1(1) 23 5(2) 1(1) 11 6(2) 5(1) 25 9(3) 1(1) 12 7(2) 1(1) 6 4(2) 3(1) 40 9(2) 3(1) 16 7(3) 5(1) 40 6(2) 3(1) 22 7(2) 1(1) 7 6(2) 3(1) 52 9(2) 3(1) 50 9(3) 6(2) 68 9(3) 1(1) 31 7(2) 3(1) 21 7(2) 2(1) 57 5(2) 6(1) 59 5(1) 6(2) 95 1(1) 8(3) 47 8(2) 3(1) 29 5(2) 3(1) 62 9(2) 3(1) 86 9(3) 1(1) 106 9(3) 3(1) 53 8(2) 5(1) 46 4(2) 1(1) 77 5(2) 2(1) 111 9(2) 4(1) 139 3(1) 9(3) 92 6(2) 2(1) 48 7(3) 1(1) 79 4(2) 2(1) 147 2(2) 3(1) 142 3(1) 9(3) 113 2(1) 7(2) 63 3(1) 6(2) 95 3(1) 8(2) 149 8(3) 5(1) 148 1(1) 5(2) 117 3(1) 7(2) 86 2(1) 9(2) 151 2(1) 5(2) 154 4(1) 7(2) 149 6(2) 1(1) 120 1(1) 4(2) 125 1(1) 6(2) 153 1(1) 4(2) 159 1(1) 7(3) 189 1(1) 6(2) 156 3(1) 4(2) 133 3(1) 5(2) 154 3(1) 5(2) 160 1(1) 2(2) 198 1(1) 6(2) 157 5(1) 4(2) 144 1(1) 9(3) 155 2(1) 8(2) 182 5(1) 8(3) 158 3(1) 4(2) 157 6(2) 8(3) 165 3(1) 9(2) 189 5(1) 7(3) 187 6(2) 3(1) 168 3(1) 4(2) 183 1(1) 5(2) 196 3(1) 8(3) 196 3(1) 6(2) 196 1(1) 4(2) 197 6(1) 8(2) 203 1(1) 6(2) 7 7(3) 2(1) 4 7(2) 2(1) 4 8(3) 3(1) 13 8(3) 2(1) 1 6(2) 1(1) 15 4(2) 2(1) 6 8(2) 3(1) 12 6(2) 3(1) 14 8(3) 3(1) 13 9(2) 2(1) 16 7(2) 3(1) 22 5(2) 3(1) 19 7(2) 1(1) 50 9(2) 1(1) 50 8(2) 5(1) 19 2(1) 4(2) 72 9(2) 1(1) 34 6(2) 3(1) 62 8(2) 4(1) 58 9(2) 4(1) 27 7(2) 5(1) 77 9(2) 1(1) 46 9(2) 1(1) 66 1(1) 7(2) 87 9(2) 2(1) 42 9(3) 2(1) 88 9(2) 1(1) 64 5(2) 2(1) 71 8(2) 4(1) 92 5(1) 8(2) 45 7(2) 5(1) 113 1(1) 9(2) 86 3(1) 5(2) 72 5(2) 3(1) 95 4(1) 8(2) 62 5(1) 7(2) 127 2(1) 9(2) 123 1(1) 9(2) 84 9(2) 4(1) 117 1(1) 6(2) 86 9(3) 1(1) 130 1(1) 9(2) 128 4(2) 2(1) 112 4(1) 8(2) 132 1(1) 6(2) 118 4(2) 1(1) 132 1(1) 9(2) 141 3(1) 6(2) 113 4(1) 7(2) 156 7(3) 1(1) 145 1(1) 9(3) 143 1(1) 9(2) 150 2(1) 9(3) 125 5(2) 2(1) 159 2(1) 7(2) 150 2(1) 4(2) 158 6(2) 1(1) 151 3(1) 4(2) 128 2(1) 5(2) 182 2(1) 7(2) 169 3(1) 7(2) 172 3(1) 5(2) 171 1(1) 9(2) 144 4(1) 9(2) 199 3(1) 9(3) 175 2(1) 8(3) 202 3(1) 6(2) 197 2(1) 6(2) 167 3(1) 7(3) 203 6(2) 3(1) 195 1(1) 8(3) 186 3(1) 5(2) 202 5(1) 8(2) 197 2(1) 9(3) 1 2 2 1 1 1 11
GPA 1 2 1 3 2.2 2.4 10 2040 204 10 GPA 4 0 GPA 1,2,3 1 2 3 2.2: 2.2 25 1.1 85% 1 13% 2 3 2.2 2.3,2.4 2.3 2.4 1 1 3 2.5, 2.6 12
2.3: 1 GPA 2.4: 1 3 GPA 2.4 DA GPA 13
A, B GPA α, β, δ, γ GPA 1 2 3 A 3.0 δ β α 106.0 64.5 33.0 B 2.0 β γ α 104.0 63.0 32.0 (A, α), (B, β) (A, β) A, B α, β (A, α), (B, β) (A, β), (B, α) 33.0 + 104.0 = 137.0 > 96.5 = 64.5 + 32.0 A 3 α 2 β 1 2 GPA 1 2 3 A 3.0 β( ) δ( ) α 106.0 64.5 33.0 B 2.0 β γ α 104.0 63.0 32.0 A (A, α), (B, β) (A, β), (B, α) 33.0 + 104.0 = 137.0 < 138.0 = 106.0 + 32.0 A 1,2,3 100,60,30 GPA 1 2 3 A a G δ β α a 1 a 2 a 3 B b G β γ α b 1 b 2 b 3 14
A,B a 1,, a 3, b 1,, b 3 GPA a 1 > b 1 > a 2 > b 2 > a 3 > b 3 (A, α), (B, β) (A, β), (B, α) a 3 + b 1 > a 2 + b 3 a 1 = b 1 > a 2 = b 2 > a 3 = b 3 A GPA 1 2 3 A a G β( ) δ( ) α ā 1 ā 2 a 3 B b G β γ α b 1 b 2 b 3 ā 1 > b 1 > ā 2 > b 2 > a 3 > b 3 ā 1 b 1 > a 3 b 3 A (A, α), (B, β) (A, β), (B, α) a 3 + b 1 < ā 1 + b 3 A 1 2 ā 1 = b 1 > ā 2 = b 2 > a 3 = b 3 DA yes DA DA 1.1 2 3 1 3 1 15
DA 4 GPA 2.7, 2.8 2.7: DA 1 d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 1 171 164 177 165 151 171 166 166 166 166 166.3 2 18 15 7 20 29 14 16 26 18 13 17.6 3 6 14 9 9 7 8 13 3 9 7 8.5 4 5 5 4 5 11 7 5 6 6 7 6.1 5 4 4 5 3 4 3 3 2 3 8 3.9 6 0 2 0 2 1 1 1 1 2 2 1.2 7 0 0 2 0 1 0 0 0 0 1 0.4 8 0 0 0 0 0 0 0 0 0 0 0.0 9 0 0 0 0 0 0 0 0 0 0 0.0 204 204 204 204 204 204 204 204 204 204 4 9 9 11 11 10 17 11 9 9 11 18 11.6 2.8: DA 2 25 d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 1 25 25 25 25 25 25 25 25 25 25 25.0 2 25 25 25 25 25 25 25 25 25 25 25.0 3 25 25 25 25 25 25 25 25 25 25 25.0 4 25 25 25 25 25 25 21 25 25 25 24.6 5 25 25 25 25 25 25 25 25 25 25 25.0 6 25 25 25 25 25 25 25 25 25 25 25.0 7 12 15 12 25 17 19 18 16 17 19 17.0 8 24 22 21 9 17 19 16 16 18 18 18.0 9 18 17 21 20 20 16 24 22 19 17 19.4 204 204 204 204 204 204 204 204 204 204 2.7 10 1 9 1 9 2 4 9 d1 1 171 2 18 3 6 4 5 5 4 6 9 0 4 5 9 7 d3 d5 d10 11.6 4 7 204 3 16
2.2 2.8 1 9 3 1,2,3 3 4,5,6 6 d7 4 2.2 6 d4,d7 4 1 3 DA [4] DA 4 4 3 1.1 [9] A, B GPA α, β, δ, γ, ϵ GPA 1 2 3 A 3.0 α β γ 106.0 64.5 33.0 B 2.0 α δ ϵ 104.0 63.0 32.0 2 1 α 2 3 25 A,B 24 α 1 A,B 1 A 2 β A B 2 δ B 1 B δ (A, α), (B, ϵ) (A, β), (B, α) 2 1 2 (A, α), (B, ϵ) (A, β), (B, α) 106.0 + 32.0 = 138.0 < 168.5 = 64.5 + 104.0 17
2 1 2 A,B A 1 B 1 1 3 2 DA [17, 16, 18] DA 3 3 GPA 18
[1] D. Gale and L.S. Shapley, College admissions and the stability of marriage, American Mathematical Monthly, Vol.69 (1962) 9-15. [2] (1997). [3], :, 36 (1991) 85-89. [4], :, TORSJ Vol.51 (2008) 71-93. [5], :. OR 2005, (2005), 98 99. [6] (2000). [7] :, 14.2 (2002) 779-830. [8] :, 35 (2006) 367-378. [9] :, 44 (2011) 59-73. [10] :, (2013). [11] :, RAMP 25 (2013) 30-45. [12] :, (2010) 229-238. [13] NTT (2010). [14] :, RAMP 25 (2013) 1-16. [15] :, RAMP 25 (2013) 17-29. [16] Canadian Resident Matching Service, http://www.carms.ca/. [17] National Resident Matching Program, http://www.nrmp.org/. [18], http://www.jrmp.jp/. 19
The use of an optimization technique to solve student sectioning problems Keisuke Hotta Faculty of Business Administration, Bunkyo University khotta@shonan.bunkyo.ac.jp Recieved: 30 April 2015 / Accepted: 25 May 2015 Abstract The focus of this study is to examine typical student sectioning problems. All students have their preferences to each section. The goal is to make an assignment decision to comply with their wishes as much as possible. To solve this problem, various approaches and algorithms have been proposed and discussed. In the field of mechanism design, both the deferred acceptance system and the top trading cycles system are considered to be a good method. It is studied well whether a solution provided by each method has desirable properties such as Pareto optimality, stability and strategy-proofness. In contrast, approaches using an optimization model are also studied. Studies of the model mainly focus on how to express student preferences in order to get a desirable solution. This study shows that the optimization approach is superior to the deferred acceptance to deal with some problems of student sectioning at a university. In addition, this research will clarify whether the solution by the optimization model has the desirable properties such as stability and strategy-proofness. Keyword: student sectioning problem, optimization, Boston public schools system, deferred acceptance system, top trading cycles system, Gale-Shapley algorithm, mechanism design, Pareto optimality, stability, strategy-proofness Faculty of Business Administration, Bunkyo University 1100 Namegaya, Chigasaki, Kanagawa 253-8550, JAPAN Tel +81-467-53-2111, Fax +81-467-54-3734 http://www.bunkyo.ac.jp/faculty/business 20