이게 뭐야

당신은 결혼식 2차 회의 간사입니다.
9명의 참가자가 3명씩 3개의 그룹으로 나뉘어 게임을 합니다.
이 게임은 4회 진행됩니다.
두 사람 모두 같은 그룹이 되는 것이 한 번이 되도록 그룹화를 생각해 봅시다.



※ LocalSolver 예제 컬렉션 의 Social golfer 을 힌트로 하고 있습니다.

공식화 & Python

조합 최적화 을 사용하여 해결합시다. 예를 들어, PuLP와 pandas 사용 .
"누가, 언제, 어느 그룹인가"가 성립하는지를 0-1 변수 Var로 나타냅니다.

python3

import pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
from itertools import permutations
uss = [chr(65+i) for i in range(9)] # Users
a = pd.DataFrame([(us,wk,gr) for us in uss for wk in range(4)
        for gr in range(3)], columns=['User','Time','Group'])
a['Var'] = addbinvars(len(a)) # 変数
a[:3] # 先頭の3行表示

사용자
시간
그룹
Var




0
A
0
0
v0001


1
A
0
1
v0002


2
A
0
2
v0003

공식화

목적 함수
없음


제약
각 사람마다 한 번에 한 그룹에 속

1그룹은 3명

두 사람 모두 동일한 그룹이 될 횟수는 1 회까지 (동일한 그룹 일 때 1이되는 변수 사용)



python3

m = LpProblem() # 数理モデル
for _,v in a.groupby(['User','Time']):
    m += lpSum(v.Var) == 1 # 各人各回で1つのグループに所属
for _,v in a.groupby(['Time','Group']):
    m += lpSum(v.Var) == 3 # 1グループは3人
for uu in permutations(uss,2):
    y = addvars(4*3) # 同一のグループのとき1になる変数
    m += lpSum(y) <= 1 # どの2人も、同一グループになる回数は1回まで
    for w,(_,v) in zip(y, a[a.User.isin(uu)].groupby(['Time','Group'])):
        m += lpSum(v.Var) <= 1+w # yとVarの関係
m.solve()
a['Val'] = a.Var.apply(value)
a[a.Val>0].groupby(['Time','Group']).User.sum() # 結果表示

결과

Time  Group
0     0        AFI
      1        EGH
      2        BCD
1     0        ABH
      1        CEF
      2        DGI
2     0        ACG
      1        BEI
      2        DFH
3     0        BFG
      1        ADE
      2        CHI

보충 - 그 1

솔직하게 공식화하면 목적 함수가 2차 비선형 최적화가 됩니다. 그대로는 MIP 솔버로는 풀 수 없기 때문에, 쌍마다 새로운 변수(y)를 추가하는 것으로(변수는 많아집니다만) 선형 최적화가 됩니다.
그렇다고 해도 규모가 큰 경우에는 국소 탐색법 등의 근사해법이 더 효과적일 수 있습니다.

보충 - 그 2

PuLP의 LpProblem은 문제가 아니라 모델입니다!

문제 : 해결하고 싶은 것

모델 : 컴퓨터로 취급 할 수 있도록 표현 된 것

결과를 검토할 때 변경하는 것은 문제가 아니라 모델!

이상