これなに
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']
元記事と同じ分け方が得られました。
(元記事では、近似解法でしたが、こちらは厳密に解いています)
最大と最小の差分を最小化する方法は、今回用いた汎用ソルバーには、不得意なアプローチなので、大規模になると、計算時間が急激に増えることにご注意ください。その場合は、「ある範囲を外れるとペナルティがつく」ように変更すると、解きやすくなります。
参考
以上