この記事は?
pythonのpulpソルバを使用してグループ分けを実現するためのtipsを備忘録として残しておく.
本記事の内容は個人の学習記録であり,所属する組織とは無関係である.
シチュエーション
内容の異なる複数のグループワークがあり,参加者はどれか一つだけに参加するシチュエーションを考える.
参加者の全てのグループの志望度(例えば10段階評価)の調査が完了している.
目的
参加者全体の達成志望度が最大になる班分けの実行.
その際に,各グループの定員などの制約条件も満たすようにする.
方法
pythonのpulpパッケージを使用する.
使用方法等の説明は分かりやすい記事に譲る.
データ
参加者IDをindexに持ち,各グループの希望度やグループ分けに使用する参加者の属性が格納された下記のようなデータフレーム(df 表1).下記条件のものを想定.
・各参加者の希望度は0以上の実数で合計値が参加者間で一定に調整されている.
・参加者の属性はバイナリデータである.
表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)