この記事は？
pythonのpulpソルバを使用してグループ分けを実現するためのtipsを備忘録として残しておく．
本記事の内容は個人の学習記録であり，所属する組織とは無関係である．
シチュエーション
内容の異なる複数のグループワークがあり，参加者はどれか一つだけに参加するシチュエーションを考える．
参加者の全てのグループの志望度（例えば10段階評価）の調査が完了している．
目的
参加者全体の達成志望度が最大になる班分けの実行．
その際に，各グループの定員などの制約条件も満たすようにする．
方法
pythonのpulpパッケージを使用する．
使用方法等の説明は分かりやすい記事に譲る．
データ
参加者IDをindexに持ち，各グループの希望度やグループ分けに使用する参加者の属性が格納された下記のようなデータフレーム(df 表1)．下記条件のものを想定．
・各参加者の希望度は０以上の実数で合計値が参加者間で一定に調整されている．
・参加者の属性はバイナリデータである．
表1. 想定データ(df)
| ID | group_A | group_B | ... | group_X | flag_0 | flag_1 | ... |
|---|---|---|---|---|---|---|---|
| 0000 | 0 | 8 | ... | 0 | 1 | 0 | ... |
| 0001 | 2 | 3 | ... | 3 | 1 | 1 | ... |
| 0002 | 3 | 5 | ... | 0 | 0 | 1 | ... |
| ... | ... | ... | ... | ... | ... | ... | ... |
目的関数・問題設定
指定した制約条件下でD・t(X)が最大となるようにXを設定する．
D: 参加者の志望度行列(表1の左部分)
X: 参加者配属行列(配属する場合は1, 配属しない場合は0が格納された行列, 表2)
表2. 参加者配属行列
| ID | group_A | group_B | ... | group_X |
|---|---|---|---|---|
| 0000 | 0 | 1 | ... | 0 |
| 0001 | 0 | 0 | ... | 1 |
| 0002 | 1 | 0 | ... | 0 |
| ... | ... | ... | ... | ... |
import pulp
# 問題の宣言
problem = pulp.LpProblem('GroupAssignmentProblem',
pulp.LpMaximize)
# 参加者のリスト
participants_list = df['ID'].tolist()
# グループのリスト
group_list = ["group_A","group_B",...,"group_X"]
# 参加者とグループのペアのリスト
participant_group = [(p,g) for p in participants_list for g in group_list]
# 参加者をどのクラスに割り当てるかを変数xとして定義する
# 各参加者が各グループに属するか否かを 0 or 1 で最適化するので、Binaryを指定
x = pulp.LpVariable.dicts('x', participant_group, cat='Binary')
# 目的関数の追加
problem += pulp.lpSum([x[p,g] * df.loc[df["ID"]==p,g].values for p in participants_list for g in groups])
制約条件の追加
線形な数式で表せる条件でないと実装できない
各参加者は必ずどれか一つのグループに所属する
全ての参加者pにおいて，sum(x[p,:]) == 1
for p in participants_list:
problem.addConstraint(
pulp.lpSum([x[p,g] for g in groups])==1)
全てのグループの定員は偏らないようにする
参加者数をグループ数で割った下図の商 ~ +1 の範囲内に収める
num_of_groups = len(groups)
min_num_of_member = math.floor(len(df)/num_of_groups)
max_num_of_member = math.ceil(len(df)/num_of_groups)
for g in groups:
problem.addConstraint(
pulp.lpSum([x[p,g] for p in participants_list]) >= min_num_of_member)
problem.addConstraint(
pulp.lpSum([x[p,g] for p in participants_list]) <= max_num_of_member)
(オプション)ある特定の参加者属性が偏らないようにする
上記と同様
min_num_of_flag_0 = math.floor(sum(df["flag_0"]==1)/num_of_groups)
max_num_of_flag_0 = math.ceil(sum(df["flag_0"]==1)/num_of_groups)
flag_0_list = df.loc[df["flag_0"]==1,"ID"].to_list()
for g in groups:
problem.addConstraint(
pulp.lpSum([x[p,g] for p in flag_0_list]) >= min_num_of_flag_0)
problem.addConstraint(
pulp.lpSum([x[p,g] for p in flag_0_list]) <= max_num_of_flag_0)
割合を一定範囲で収めたい，等のゆるい制約を貸す場合は場合は以下のように書ける
flag_1_list = df.loc[df["flag_1"]==1,:].index.to_list()
th_flag_1 = np.ceil(min_num_of_member * 0.4)
for g in groups:
problem.addConstraint(
pulp.lpSum([x[p,g] for p in flag_1_list]) >= th_flag_1)
(オプション)ある特定の参加者同士が同じグループにならないようにする
同じグループにならない = 両者の要素が互いに1になるグループが存在しない = 各グループ足しても1以下
ID1, ID2 = "0001", "0002"
for g in groups:
problem += x[ID1, g] + x[ID2, g] <= 1
(オプション)ある特定の参加者同士が同じグループになるようにする
同じグループになる = 1になるグループが同じ = 各グループの差が0
ID1, ID3 = "0001", "0003"
for g in groups:
problem += x[ID1, g] - x[ID3, g] == 0
最適化問題を解く
status = problem.solve()
結果の抜き出し
result_array = [[key[0],key[1]] for key in x.keys() if x[key].value()==1]
df_result = pd.DataFrame(result_array, columns=['ID','groups'])
df_result = df_result.set_index('ID')
多くの参加者の希望が第一希望になっているかを確認する
RANK = []
for id in df_result.index:
R = df_result.loc[id, groups].rank(ascending=False,method='min')[df_result.loc[id].groups]
RANK.append(R)
import matplotlib.pyplot as plt
plt.rcParams['pdf.fonttype'] = 42
plt.rcParams['font.family'] = 'Arial'
plt.grid()
plt.hist(RANK)