組合せ最適化でチーム分けする

これなに

Master's Apprenticesの記事で、「ワークショップのチーム分けを組合せ最適化問題として解く」というのを、定式化して解いてみました。

問題

6人(P,Q,R,S,T,U)を3チーム(A,B,C)に分けたい。4つのコミュニケーション能力とその合計をなるべく均等にしたい。詳しくは元記事を見てください。

コミュニケーション能力の得点表

6人のコミュニケーション能力は、コントローラ、プロモータ、サポータ、アナライザごとに下記のように得点化されています。例えば、Pさんのコントローラ能力は6点です。

python

import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
得点 = pd.DataFrame([[6,0,1,3],[2,-1,3,5],[2,4,0,0],[3,4,5,0],[0,2,1,4],[2,3,-1,1]],
    columns='コントローラ プロモータ サポータ アナライザ'.split(),index=list('PQRSTU'))
チーム数,メンバ数 = 3,得点.shape[0]
print(得点)

	コントローラ	プロモータ	サポータ	アナライザ
P	6	0	1	3
Q	2	-1	3	5
R	2	4	0	0
S	3	4	5	0
T	0	2	1	4
U	2	3	-1	1

定式化してPythonで解く

なるべく均等にするには、ばらつきを最小化できればいいですが、素直に定式化すると非線形(2次式)になり解きづらくなります。今回はチーム数が少ないので、最大と最小の差を最小化しましょう。経験的にグループ数が小さければ、分散最小と同じような効果が得られます。
ここでは、チーム内のばらつきの重みを1、チーム間のばらつきの重みを1.5とします。

python

m = LpProblem() # 数理モデル
x = np.array(addbinvars(メンバ数,チーム数)) # 割当
y = np.array(addvars(チーム数,2)) # チーム内の最小と最大
z = addvars(2) # チーム間の最小と最大
m += lpSum(y[:,1]-y[:,0]) + 1.5*(z[1]-z[0]) # 目的関数
for i in range(メンバ数):
    m += lpSum(x[i]) == 1 # どこかのチームに所属
for j in range(チーム数):
    m += lpDot(得点.sum(1),x[:,j]) >= z[0]
    m += lpDot(得点.sum(1),x[:,j]) <= z[1]
    for k in range(得点.shape[1]):
        m += lpDot(得点.iloc[:,k],x[:,j]) >= y[j,0]
        m += lpDot(得点.iloc[:,k],x[:,j]) <= y[j,1]
m.solve() # 求解
結果x = np.vectorize(value)(x)
print(['ABC'[i] for i in (結果x@range(チーム数)).astype(int)])
>>>
['C', 'A', 'A', 'B', 'C', 'B']

元記事と同じ分け方が得られました。
(元記事では、近似解法でしたが、こちらは厳密に解いています)

最大と最小の差分を最小化する方法は、今回用いた汎用ソルバーには、不得意なアプローチなので、大規模になると、計算時間が急激に増えることにご注意ください。その場合は、「ある範囲を外れるとペナルティがつく」ように変更すると、解きやすくなります。

参考
- 組合せ最適化でグループ分け
- 組合せ最適化で、ゲームのグループ分け

以上