不協和音のないパートへの割当 -最適な割当から安定な割当へ- / modeling-on-assignment-problem-in-wind-orchestra-via-stable-matching

安定マッチングと呼ばれるある意味で安定なペアリングを求める問題が ILP として定式化できることを紹介し，吹奏楽部における学生のパートへの割当へ応用した事例をお話しします．

Transcript

1. ෆڠ࿨Իͷͳ͍ύʔτ΁ͷׂ౰ –࠷దͳׂ౰͔Β҆ఆͳׂ౰΁– ҏ౾Ӭ ༸Ұ 2020/01/30 (last update: 2020/01/31) Optimization Night #2
2. ࣗݾ঺հ ҏ౾Ӭ ༸Ұʢ͍ͣͳ͕ Α͏͍ͪʣ ॴଐ ਆಸ઒େֶ ޻ֶ෦ʢॿڭʣ ઐ໳ ਺ཧ࠷దԽɼΦϖϨʔγϣϯζɾϦαʔν ݚڀ಺༰ ωοτϫʔΫ্ͷΫϥελϦϯά΍ϥϯΩϯάʹؔ͢Δ ϞσϦϯάͱΞϧΰϦζϜઃܭ 2 / 15
3. എܠ ࠓճͷൃද͸ɼਆಸ઒େֶ ࡾ޷෣͞Μͷଔۀ࿦จʹؔ͢Δ΋ͷͰ͢ ͳ͓ɼࢲ͸ਧ૗ָ΍Իָʹؔͯ͠͸શ͘ͷૉਓͰ͢... ਧ૗ָ෦ͷݱঢ় • େ͖͘ 12 ύʔτʢ໦؅ 5, ۚ؅ 5ɼݭָث 1ɼଧָث 1ʣʹ෼͚ΒΕɺ ৽ೖ෦һ͸ೖ෦࣌ʹॴଐύʔτΛܾఆ • ίϯΫʔϧͰ͸՝୊ۂʹ͓͚Δָثฤ੒ͷࢦఆ΍ ग़৔ਓ਺ 55 ਓͱ͍͏੍໿͕͋Δ ໰୊఺ • ৽ೖ෦һͷҙࢥʹ͙ͦΘͳ͍ύʔτʹׂΓ౰ͯΔͱɼ Ϟνϕʔγϣϯͷ௿Լ΍࠷ѱͷ৔߹ୀ෦͢ΔՄೳੑ͕͋Δ • ύʔτͷฤ੒ʹภΓ͕͋Δͱԋ૗৔ෆརʹͳͬͯ͠·͏ 3 / 15
4. എܠ • ֶੜʢ৽ೖ෦һʣ ... ͜Ε·Ͱͷܦݧ౳͔Βر๬ָثʢύʔτʣΛද໌ • ίϯϚεɾύʔτϦʔμʔ ... ֶੜͷܦྺ΍ΦʔσΟγϣϯͳͲΛجʹֶੜʹର͢Δر๬ද໌ • ࢦಋऀ ... ͦΕͧΕͷر๬Λ΋ͱʹύʔτ΁ͷׂ౰ΛٻΊΔ ʢฤ੒ͷόϥϯεɼੈ୅ަ୅ʢ4 ೥ޙͷ෦಺ߏ੒ʣ΋ҙࣝʣ → ҆ఆϚονϯάͷ֓೦Λ༻͍ͯɼΑΓྑ͍ύʔτ΁ͷׂ౰ΛٻΊΔ 4 / 15
5. ࠷దͳׂ౰ vs. ҆ఆͳׂ౰ • N: ֶੜͷू߹ • P: ύʔτͷू߹ • Lj : ύʔτ j ͷఆһͷԼݶ • N(j): ύʔτ j Λر๬͢Δֶੜͷू߹ • P(i): ֶੜ i Λड͚ೖΕՄೳͳύʔτू߹ • Uj : ύʔτ j ͷఆһͷ্ݶ ܾఆม਺ xij = { 1 (ֶੜ i Λύʔτ j ΁ׂΓ౰ͯΔ) 0 (ͦΕҎ֎). ʢ࠷దԽΞϓϩʔνʣ ޮ༻ʢຬ଍౓ʣuij ͕༩͑ΒΕ্ͨͰɼ ԿΒ͔ͷ໨తؔ਺Λ࠷దԽ max. f(uij , xij ) s.t. ∑ j∈P (i) xij ≤ 1 (i ∈ N), Lj ≤ ∑ i∈N(j) xij ≤ Uj (j ∈ P). ʢ҆ఆϚονϯάʹΑΔΞϓϩʔνʣ ֶੜͱύʔτ͸ɼͦΕͧΕʹର͢Δر๬ Λॱংʢ⪰ʣͰද໌ s.t. ∑ j∈P (i) xij ≤ 1 (i ∈ N), Lj ≤ ∑ i∈N(j) xij ≤ Uj (j ∈ P), +҆ఆੑΛ՝੍͢໿. 5 / 15
6. ҆ఆϚονϯά • ҆ఆϚονϯά ⇔ ϒϩοΩϯάϖΞ͕͍ͳ͍Ϛονϯά • ϒϩοΩϯάϖΞ ≈ ۦ͚མͪͦ͠͏ͳϖΞ ʢఆٛʣ உੑ i ͱঁੑ j ͕Ϛονϯά x ʹ͓͚Δ ϒϩοΩϯάϖΞ ⇔ (1) i ͱ j ͸ݱࡏϚον͍ͯ͠ͳ͍ (2) i ͸ಠ਎ or ݱࡏͷ૬खΑΓ j Λ޷Ή (3) j ͸ಠ਎ or ݱࡏͷ૬खΑΓ i Λ޷Ή 1 2 3 A B C 1 2 2 1 3 2 1 B A C A B C B A ଟରҰϚονϯάʢஉੑΛֶੜɼঁੑΛύʔτʹஔ͖׵͑ʣ ʹ͓͚ΔϒϩοΩϯάϖΞ... (1), (2) (3’) ύʔτ j ʹ഑ଐ͞Ε͍ͯΔֶੜͷਓ਺͸ఆһͷ্ݶະຬ or ݱࡏ഑ଐ͞Ε͍ͯΔֶੜΑΓ΋ֶੜ i Λ޷Ή 6 / 15
7. ҆ఆϚονϯά • ҆ఆϚονϯά ⇔ ϒϩοΩϯάϖΞ͕͍ͳ͍Ϛονϯά • ϒϩοΩϯάϖΞ ≈ ۦ͚མͪͦ͠͏ͳϖΞ ʢఆٛʣ உੑ i ͱঁੑ j ͕Ϛονϯά x ʹ͓͚Δ ϒϩοΩϯάϖΞ ⇔ (1) i ͱ j ͸ݱࡏϚον͍ͯ͠ͳ͍ (2) i ͸ಠ਎ or ݱࡏͷ૬खΑΓ j Λ޷Ή (3) j ͸ಠ਎ or ݱࡏͷ૬खΑΓ i Λ޷Ή 1 2 3 A B C 1 2 2 1 3 2 1 B A C A B C B A ଟରҰϚονϯάʢஉੑΛֶੜɼঁੑΛύʔτʹஔ͖׵͑ʣ ʹ͓͚ΔϒϩοΩϯάϖΞ... (1), (2) (3’) ύʔτ j ʹ഑ଐ͞Ε͍ͯΔֶੜͷਓ਺͸ఆһͷ্ݶະຬ or ݱࡏ഑ଐ͞Ε͍ͯΔֶੜΑΓ΋ֶੜ i Λ޷Ή 6 / 15
8. ҆ఆϚονϯά • ҆ఆϚονϯά ⇔ ϒϩοΩϯάϖΞ͕͍ͳ͍Ϛονϯά • ϒϩοΩϯάϖΞ ≈ ۦ͚མͪͦ͠͏ͳϖΞ ʢఆٛʣ உੑ i ͱঁੑ j ͕Ϛονϯά x ʹ͓͚Δ ϒϩοΩϯάϖΞ ⇔ (1) i ͱ j ͸ݱࡏϚον͍ͯ͠ͳ͍ (2) i ͸ಠ਎ or ݱࡏͷ૬खΑΓ j Λ޷Ή (3) j ͸ಠ਎ or ݱࡏͷ૬खΑΓ i Λ޷Ή 1 2 3 A B C 1 2 2 1 3 2 1 B A C A B C B A ଟରҰϚονϯάʢஉੑΛֶੜɼঁੑΛύʔτʹஔ͖׵͑ʣ ʹ͓͚ΔϒϩοΩϯάϖΞ... (1), (2) (3’) ύʔτ j ʹ഑ଐ͞Ε͍ͯΔֶੜͷਓ਺͸ఆһͷ্ݶະຬ or ݱࡏ഑ଐ͞Ε͍ͯΔֶੜΑΓ΋ֶੜ i Λ޷Ή 6 / 15
9. ҆ఆϚονϯά • ҆ఆϚονϯά ⇔ ϒϩοΩϯάϖΞ͕͍ͳ͍Ϛονϯά • ϒϩοΩϯάϖΞ ≈ ۦ͚མͪͦ͠͏ͳϖΞ ʢఆٛʣ உੑ i ͱঁੑ j ͕Ϛονϯά x ʹ͓͚Δ ϒϩοΩϯάϖΞ ⇔ (1) i ͱ j ͸ݱࡏϚον͍ͯ͠ͳ͍ (2) i ͸ಠ਎ or ݱࡏͷ૬खΑΓ j Λ޷Ή (3) j ͸ಠ਎ or ݱࡏͷ૬खΑΓ i Λ޷Ή 1 2 3 A B C 1 2 2 1 3 2 1 B A C A B C B A ۦ͚མͪ ଟରҰϚονϯάʢஉੑΛֶੜɼঁੑΛύʔτʹஔ͖׵͑ʣ ʹ͓͚ΔϒϩοΩϯάϖΞ... (1), (2) (3’) ύʔτ j ʹ഑ଐ͞Ε͍ͯΔֶੜͷਓ਺͸ఆһͷ্ݶະຬ or ݱࡏ഑ଐ͞Ε͍ͯΔֶੜΑΓ΋ֶੜ i Λ޷Ή 6 / 15
10. ҆ఆϚονϯά • ҆ఆϚονϯά ⇔ ϒϩοΩϯάϖΞ͕͍ͳ͍Ϛονϯά • ϒϩοΩϯάϖΞ ≈ ۦ͚མͪͦ͠͏ͳϖΞ ʢఆٛʣ உੑ i ͱঁੑ j ͕Ϛονϯά x ʹ͓͚Δ ϒϩοΩϯάϖΞ ⇔ (1) i ͱ j ͸ݱࡏϚον͍ͯ͠ͳ͍ (2) i ͸ಠ਎ or ݱࡏͷ૬खΑΓ j Λ޷Ή (3) j ͸ಠ਎ or ݱࡏͷ૬खΑΓ i Λ޷Ή 1 2 3 A B C 1 2 2 1 3 2 1 B A C A B C B A ଟରҰϚονϯάʢஉੑΛֶੜɼঁੑΛύʔτʹஔ͖׵͑ʣ ʹ͓͚ΔϒϩοΩϯάϖΞ... (1), (2) (3’) ύʔτ j ʹ഑ଐ͞Ε͍ͯΔֶੜͷਓ਺͸ఆһͷ্ݶະຬ or ݱࡏ഑ଐ͞Ε͍ͯΔֶੜΑΓ΋ֶੜ i Λ޷Ή 6 / 15
11. ੔਺ઢܗ࠷దԽ໰୊ʢILPʣͱͯ͠ͷఆࣜԽ max. ∑ i∈N ∑ j∈P (i) xij ϖΞ਺࠷େԽ s.t. ∑ j∈P (i) xij ≤ 1 (i ∈ N), Lj ≤ ∑ i∈N(j) xij ≤ Uj (j ∈ P), Uj ≤ Uj ∑ q∈P ⪰ j (i) xiq + ∑ p∈N⪰ i (j) xpj ϒϩοΩϯάϖΞΛഉআ (i ∈ N, j ∈ P(i)). • P⪰ j (i) ֶੜ i ͕ύʔτ j ͱಉఔ౓Ҏ্ʹر๬͢Δύʔτͷू߹ • N⪰ i (j) ύʔτ j ֶ͕ੜ i ͱಉఔ౓Ҏ্ʹड͚ೖΕͯྑ͍ͱߟ͑Δֶੜͷू߹ ⇡ P⌫( )= { } ⇡ N⌫( )= { } 7 / 15
12. ҰൠʹఆһͷԼݶ੍໿Λ՝͢ͱ҆ఆϚονϯά͕ଘࡏ͢Δͱ͸ݶΒͳ͍ 1 → ଘࡏ͠ͳ͍৔߹ʹ΋ɼԿΒ͔ͷҙຯͰ҆ఆϚονϯάʹׂ͍ۙ౰ΛٻΊ͍ͨ → ҆ఆϚονϯάʹׂ͍ۙ౰ ≈ ϒϩοΩϯάϖΞ਺͕࠷খͷϚονϯά ܾఆม਺ yij = { 1 (ֶੜ i ͱύʔτ j ͕ϒϩοΩϯάϖΞͱͳΔ) 0 (ͦΕҎ֎). max. a ∑ i∈N ∑ j∈P (i) xij ϖΞ਺࠷େԽ −b ∑ i∈N ∑ j∈P (i) yij ϒϩοΩϯάϖΞ਺࠷খԽ s.t. ∑ j∈P (i) xij ≤ 1 (i ∈ N), Lj ≤ ∑ i∈N(j) xij ≤ Uj (j ∈ P), (1 − yij )Uj ≤ Uj ∑ q∈P ⪰ j (i) xiq + ∑ p∈N⪰ i (j) xpj (i ∈ N, j ∈ P(i)). 1্ݶ੍໿͚ͩͰ͋Ε͹ɼৗʹ҆ఆϚονϯά͸ଘࡏ͢Δ 8 / 15
13. ܭࢉػ࣮ݧʢ1ʣ σʔλʢر๬Ϧετ, ఆһͷ্Լݶʣ • ر๬Ϧετ... ਧ૗ָ෦ʹॴଐ͢Δֶ෦ 1 ೥ੜʢ36 ਓʣ & ίϯϚε΁ͷΞϯέʔτʹج͖ͮ࡞੒ • ఆһͷԼݶ... ύʔτ಺ͷηΫγϣϯʹ 1 ਓͣͭ഑ஔͨ͠৔߹ͷਓ਺ • ఆһͷ্ݶ... ίϯΫʔϧʹग़৔Մೳͳ࠷େਓ਺ ܭࢉػ؀ڥ • PC: Core i5 @3.4GHz, 40GB memory • MIP solver: Python API of Gurobi 8.0 Fl Ob Fg Cl Sax Tp Hr Tb Euph Tuba Cb Perc set of parts 0 2 4 6 8 10 12 # of students minimum quota maximum quota (a,b)=(0.5,0.5) • ܭࢉ࣌ؒ: 0.016 ඵ • ҆ఆϚονϯά͕ಘΒΕͨ • શͯͷֶੜ͸ɼୈ 2 ر๬Ҏ্ͷ ύʔτʹׂΓ౰ͯΒΕͨ • ΫϥϦωοτύʔτ͸ఆһ্ݶΑ Γᴴ͔ʹগͳ͍ਓ਺ׂ͕Γ౰ͯΒ Ε͍ͯΔ → ਧ૗ָͷಛੑ্ɼશମͷ໿ 40% Λ઎ΊΔ͜ͱ͕ཧ૝త → ฤ੒ͷόϥϯε͕ෆे෼ 9 / 15
14. ฤ੒ͷόϥϯε΋ߟྀͨ͠ఆࣜԽ ഑ଐਓ਺Λఆһͷ্ԼݶʹऩΊΔ͚ͩͰͳ͘ฤ੒ͷόϥϯε΋ߟྀ͍ͨ͠ → ֤ύʔτʹ഑ଐ਺ͷ໨ඪ஋ Tj Λઃఆ 2 → εϥοΫม਺ S+ j , S− j Λಋೖ͠ɼ഑ଐ਺͕ Tj ʹͰ͖ΔݶΓۙ͘ͳΔΑ͏ఆࣜԽ max. a ∑ i∈N ∑ j∈P (i) xij ϖΞ਺࠷େԽ −b ∑ i∈N ∑ j∈P (i) yij ϒϩοΩϯάϖΞ਺࠷খԽ −c ∑ j∈P (S+2 j + S−2 j ) ໨ඪ஋ͱͷζϨΛ࠷খԽ s.t. ∑ j∈P (i) xij ≤ 1 (i ∈ N), Lj ≤ ∑ i∈N(j) xij ≤ Uj (j ∈ P), (1 − yij )Uj ≤ Uj ∑ q∈P ⪰ j (i) xiq + ∑ p∈N⪰ i (j) xpj (i ∈ N, j ∈ P(i)), (Tj − ∑ i∈N(j) xij ) + S+ j − S− j = 0 (j ∈ P). 2ࠓճ͸্Լݶͷதԝ஋ʹઃఆ 10 / 15
15. ܭࢉػ࣮ݧʢ2ʣ Fl Ob Fg Cl Sax Tp Hr Tb Euph Tuba Cb Perc set of parts 0 2 4 6 8 10 12 # of students minimum quota maximum quota (a,b)=(0.5,0.5) → Fl Ob Fg Cl Sax Tp Hr Tb Euph Tuba Cb Perc set of parts 0 2 4 6 8 10 12 # of students minimum quota maximum quota (a,b,c)=(0.1,0.5,0.4) • ܭࢉ࣌ؒ: 0.05 ඵ • ϒϩοΩϯάϖΞ਺͸ 6 • શͯͷֶੜ͸ɼୈ 3 ر๬Ҏ্ͷύʔτʹׂΓ౰ͯΒΕͨ • ઌͷ݁Ռͱൺ΂Δͱɼฤ੒ͷόϥϯε΋վળ 11 / 15
16. ·ͱΊ • ҆ఆϚονϯάΛٻΊΔ໰୊ͷ ILP ఆࣜԽΛ঺հ → ৽ͨʹ௥Ճ͢΂੍͖໿ʢཁ݅ʣ͕ੜͨ͡ࡍ΋ରԠ͕༰қ → ൚༻࠷దԽιϧόʔͰٻղՄೳ • ਧ૗ָ෦ʹ͓͚Δύʔτ΁ͷׂ౰ʹద༻ • ֶੜͱύʔτ૒ํͷر๬ͱฤ੒ͷόϥϯεΛߟׂྀͨ͠౰ΛٻΊͨ 12 / 15
17. ࢀߟจݙ • ٱอװ༤ɼాଜ໌ٱɼদҪ஌ݾʢฤʣ ɼ ʮԠ༻਺ཧܭըϋϯυϒοΫʯ ɼே૔ॻ ళɼ2002. • M. Baïou and M. Balinski, “The stable admissions polytope,” Mathematical Programming, Ser.A, Vol.87, pp.427–439, 2000. • M. Delorme et al., “Mathematical models for stable matching problems with ties and incomplete lists,” European Journal of Operational Research, Vol.277, pp.426–441, 2019. 13 / 15
18. ʢଟରҰʣϚονϯάʹ͓͚Δ҆ఆੑ੍໿ ر๬Ϧετʹؔ͢ΔԾఆ • ϖΞʹͳΓͨ͘ͳ͍૬ख͸Ϧετʹॻ͔ͳͯ͘΋ྑ͍ʢෆ׬શϦετʣ • ಉ͘͡Β͍޷Ή૬खʹ͸ಉॱҐΛڐ͢ • ͓ޓ͍ʹر๬Ϧετʹهࡌ͍͋ͬͯ͠ΔϖΞ͚ͩΛر๬Ϧετʹ࢒͢ ʢఆٛʣ ֶੜ i ͱύʔτ j ͕Ϛονϯά x ʹ͓͚ΔϒϩοΩϯάϖΞ ⇔ (1) ֶੜ i ͱύʔτ j ͸ݱࡏϚον͍ͯ͠ͳ͍ (2) ֶੜ i ͸Ͳͷύʔτʹ΋഑ଐ͞Ε͍ͯͳ͍ or ݱࡏͷ഑ଐύʔτΑΓ j Λ޷Ή (3) ύʔτ j ʹ഑ଐ͞Ε͍ͯΔֶੜͷਓ਺͸ఆһͷ্ݶະຬ or ݱࡏ഑ଐ͞Ε͍ͯΔֶੜΑΓ΋ֶੜ i Λ޷Ή ֶੜ i ͱύʔτ j ͕ϒϩοΩϯάϖΞͰͳ͍ ⇔ Uj ≤ Uj ∑ q∈P ⪰ j (i) xiq + ∑ p∈N⪰ i (j) xpj 14 / 15
19. ʢଟରҰʣϚονϯάʹ͓͚Δ҆ఆੑ੍໿ (ରۮΛࣔ͢) Uj > Uj ∑ q∈P ⪰ j (i) xiq + ∑ p∈N ⪰ i (j) xpj ΛԾఆ͢ΔͱɼҎԼ͕੒Γཱͭɽ ∑ q∈P ⪰ j (i) xiq = 0 (1) ∧ ∑ p∈N ⪰ i (j) xpj < Uj (2). ֶੜ i ͸ߴʑ 1 ͭͷύʔτʹׂ౰ΒΕ͍ͯΔ͜ͱͱࣜ (1) ΑΓɼͲͷύʔτʹ΋ׂ౰ΒΕ͍ͯͳ͍ or P \ P ⪰ j (i) ʹଐ͢ Δύʔτʢj ΑΓ΋޷·͘͠ͳ͍ύʔτʣʹׂ౰ΒΕ͍ͯΔɽ ύʔτ j ʹؔͯ͠͸ɼ഑ଐ͞Ε͍ͯΔֶੜͷਓ਺͕ Uj ະຬͷ৔߹͸ (i, j) ͕ϒϩοΩϯάϖΞͰ͋Δ͜ͱ͸໌Β͔ͳͷ Ͱɼ഑ଐ͞Ε͍ͯΔֶੜ਺͕ Uj ʹҰக͢Δ৔߹ɼͭ·Γ ∑ p∈N(j)\N ⪰ i (j) xpj + ∑ p∈N ⪰ i (j) xpj = Uj (3) ͕੒Γཱͭ৔߹Λߟ͑Δɽࣜ (2) ͱ (3) ͔Βɼύʔτ j ʹগͳ͘ͱ΋ 1 ਓ͸ N(j) \ N⪰ i (j) ʹଐ͢Δֶੜʢi ΑΓ޷· ͘͠ͳֶ͍ੜʣ͕഑ଐ͞Ε͍ͯΔɽ͕ͨͬͯ͠ɼֶੜ i ͱύʔτ j ͸Ϛονϯά x ʹ͓͚ΔϒϩοΩϯάϖΞͰ͋Δɽ ٯʹ͍ͭͯ΋ɼ্هͷٞ࿦ΛԼ͔Β୧Δ͜ͱͰಉ༷ʹࣔͤΔɽ 15 / 15