クラス分けの最適化（PuLPを使った数理最適化）

数理最適化用のモジュール PuLP を使ってグループ分けの最適化を勉強したので、その備忘録として記事にしました。
下記の本を参考にしています。

（PulPについては、こちらの Qiitaの記事参照）

最適化したい課題

グループディスカッション形式の社内交流会において、そのグループ分けを行いたい。
参加者は、社内のさまざま部署、勤務地から参加しているため、なるべく同じ部署・勤務地の人が同じグループにならないといった制約や、前回の交流会で同じグループになった方は今回は違うグループに振り分けたい、などいくつか条件があるのでそれを満たしつつ、いい感じにグループを振り分けたい。というもの

数理最適化条件を列挙してみる

• 1グループあたりの人数：8人
• 同じ部署の人が同じグループにならないようにする
• 同じ勤務地の人が同じグループにならないようにする
• 過去同じグループになった人が同じグループにならないようにする
• 勤続年数がバラけるように振り分ける

実装

（ダミーデータ・コードへのリンク）

モジュールインポート

import pandas as pd
import pulp
import itertools
import math
import matplotlib.pyplot as plt

ファイル読み込み

# ファイル読み込み
df = pd.read_excel(r'22年度交流会参加者_ダミーデータ.xlsx',dtype='str')

# 前処理
df.dropna(how='all',axis=1,inplace=True)
df.dropna(how='all',axis=0,inplace=True)

df['年目'] = df['年目'].astype(int)

df.head()

データはこんな感じ

過去に同じグループになった人同士のリストをつくる

#これまでの交流会の班の列
past_group_col = df.loc[:,"21年度の班":].columns.tolist()

# 同じ班になったことのある人のデータ格納用データフレーム
df_duplicated = pd.DataFrame()

for past_group in past_group_col:

    df_temp = df[['社員番号', past_group]]

    # 各グループごとにメンバーを抜き出して、重複メンバーデータフレームに追加
    for group_num in df_temp['21年度の班'].dropna().unique():

        group_member = df_temp.loc[df_temp['21年度の班']==group_num, '社員番号'].values
        member_combination = itertools.combinations(group_member,2)
        df_comb_temp = pd.DataFrame(member_combination)

        df_duplicated = pd.concat([df_duplicated,df_comb_temp],axis=0)

# 重複している行を削除
df_duplicated.reset_index(drop=True,inplace=True)
df_duplicated.drop_duplicates(inplace=True)

df_duplicated.head()

過去にペアになったことのある人の情報が入ったデータフレーム

数理モデリングと実装

グループ分けの条件に応じて、数理最適化の条件を決めていく

# 数理モデルのインスタンス作成（今回は目的関数を最大化する）
problem = pulp.LpProblem('ClassAssignmentProblem', pulp.LpMaximize)

# 1グループ8人以内として何グループ作るか計算
num_of_groups = math.ceil(len(df)/8)
min_num_of_member = math.floor(len(df)/num_of_groups)
max_num_of_member = math.ceil(len(df)/num_of_groups)

print('グループ数：',num_of_groups)
print(f'メンバー数：{min_num_of_member}人〜{max_num_of_member}人')
"""output
グループ数： 14
メンバー数：7人〜8人
"""

# 参加者のリスト
participants_list = df['社員番号'].tolist()

# 交流会のグループのリスト
group_list = [f'{group+1}班' for group in range(num_of_groups)]

# 参加者とグループのペアのリスト
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')

要件0.

参加者（ $p$ ）は、それぞれ1つのグループ（ $g$ ）に割り当てる。

$$ \sum_{g\in G}x_{p,g}=1 \qquad (p\in P) $$

for p in participants_list:
    problem.addConstraint(pulp.lpSum([x[p,g] for g in group_list])==1)

要件1.

各クラスの人数は○人以上、○人以下とする

先ほど求めた、各グループの下限、上限人数を設定（今回は7人以上8人以下）

$$ \sum_{p\in P}x_{p,g} \leq max\_member \qquad (g\in G) $$

$$ \sum_{p\in P}x_{p,g} \geq min\_member \qquad (g\in G) $$

for g in group_list:
    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)

要件2.

同じ部署の人が同じグループにならないようにする

各部署に対して、各グループに何人以上〜何人以下であればOKなのか計算する。
例）e部署が22人参加なので、14グループで割ると1グループあたり1人以上2人以下

$$ \sum_{p\in P_{head.}}x_{p,g} \geq 最小人数 \qquad (g\in G)$$

$$ \sum_{p\in P_{head.}}x_{p,g} \leq 最大人数 \qquad (g\in G)$$

# 各部署の人のリスト
for head_temp in df['部署名'].unique():
    head_part_list = df.loc[df['部署名']==head_temp,'社員番号'].tolist()

    max_num_temp = math.ceil(len(head_part_list)/num_of_groups)
    min_num_temp = math.floor(len(head_part_list)/num_of_groups)
    print(f'{head_temp}:{min_num_temp}名〜{max_num_temp}名')

    for g in group_list:
        problem.addConstraint(
            pulp.lpSum([x[p,g] for p in head_part_list]) <= max_num_temp)
        problem.addConstraint(
            pulp.lpSum([x[p,g] for p in head_part_list]) >= min_num_temp)

"""
a部署:0名〜1名
b部署:0名〜1名
c部署:0名〜1名
d部署:0名〜1名
e部署:1名〜2名
f部署:0名〜1名
g部署:0名〜1名
h部署:0名〜1名
i部署:0名〜1名
j部署:0名〜1名
k部署:0名〜1名
l部署:0名〜1名
m部署:0名〜1名
n部署:0名〜1名
o部署:0名〜1名
"""

要件3.

同じ勤務地の人が同じグループにならないようにする

各本部に対して、各グループに何人以上〜何人以下であればOKなのか計算する。
例）本社勤務が65人参加なので、14グループで割ると1グループあたり4人以上5人以下

$$ \sum_{p\in P_{place.}}x_{p,g} \geq 最小人数 \qquad (g\in G)$$

$$ \sum_{p\in P_{place.}}x_{p,g} \leq 最大人数 \qquad (g\in G)$$

# 各地区の人のリスト
for place_temp in df['勤務地'].unique():
    place_part_list = df.loc[df['勤務地']==place_temp,'社員番号'].tolist()

    max_num_temp = math.ceil(len(place_part_list)/num_of_groups)
    min_num_temp = math.floor(len(place_part_list)/num_of_groups)
    print(f'{place_temp}:{min_num_temp}名〜{max_num_temp}名')

    for g in group_list:
        problem.addConstraint(
            pulp.lpSum([x[p,g] for p in place_part_list]) <= max_num_temp)
        problem.addConstraint(
            pulp.lpSum([x[p,g] for p in place_part_list]) >= min_num_temp)
"""
大阪:2名〜3名
東京:4名〜5名
名古屋:0名〜1名
"""

要件4.

過去同じグループになったペアは、同一班に割り当てない

ある参加者があるグループに属するかどうか $x_{p1,g}$ は、0 or 1 で表されているので、
「特定のペア（p1とp2）が同一グループに属さない」という条件は以下の式で表される。

$$ x_{p1,g} + x_{p2,g} \leq 1 \qquad (c\in C, (s1,s2)\in SS)$$

# 特定のペアのリスト
pair_list = df_duplicated.values.tolist()

# 特定ペアの生徒
for p1, p2 in pair_list:
    for g in group_list:
        problem.addConstraint(x[p1,g] + x[p2,g] <= 1)

要件5.

入社年度がなるべくバラけるようにする

以下の手順で数理最適化モデルに落とし込む

1. 入社年度順で生徒を各グループに割り当てる（初期グループ案）
2. グループ間で配置換えを繰り返し、要件を満たすようにグループを再編する（グループ案）
   （要するに、入社年度を考慮して決めた初期グループ案と、近いグループ案が採用されるようにする）

• 定数：初期クラスの編成フラグ

$$init\_flag_{p,g} \qquad (p \in{P}, g\in{G})$$

• 目的関数：初期グループ編成と、グループ案をできるだけ一致させる

  $$ maximize \quad \sum_{p\in{P},g\in{G}} x_{p,g}\centerdot init\_flag_{p,g}$$

補足説明：ある参加者がグループに初期グループ案、グループ案の両方に属するのならば、$1\times1$ で1を取る、それ以外の場合は、どちらかが0になるので0を取る。

# 初期グループ案を作成
# 入社年度を基に順位を付与する
df['score_rank'] = df['年目'].rank(ascending=False, method='first') 
df['init_group'] = df['score_rank'].map(lambda x:x % num_of_groups)

# 班名に変換
group_dict = {i:group for i, group in enumerate(group_list)}
df['init_group'] = df['init_group'].map(group_dict)

# init_flagを作成
init_flag = {(p,g):0 for p in participants_list for g in group_list}

for row in df.itertuples():
    init_flag[row.社員番号, row.init_group] = 1

# 目的関数:初期クラス編成と最適化結果のクラス編成をできるだけ一致させる
problem.setObjective(
    pulp.lpSum([x[p,g] * init_flag[p,g] for p,g in participant_group]))

最適化を解く

problem.solve()とすることでソルバーを実行する。

（status（返り値）とpulp.LpStatusについて）

• status:1, pulp.LpStatus:Optimal => 最適解が得られている
• status:0, pulp.LpStatus:Not Solved => 最適解が得られなかった
• status:-1, pulp.LpStatus:Ifeasible => そもそも問題に解が存在しない

status = problem.solve()
print('##########')
print(status)
print(pulp.LpStatus[status])
print("##########")

"""output
 Result - Optimal solution found

    Objective value:                82.00000000
    Enumerated nodes:               0
    Total iterations:               0
    Time (CPU seconds):             0.16
    Time (Wallclock seconds):       0.25

    Option for printingOptions changed from normal to all
    Total time (CPU seconds):       0.17   (Wallclock seconds):       0.28

    ##########
    1
    Optimal
    ##########
"""

"Optimal"と表示されているので、今回は最適解が得られたことが分かる。

結果の抽出と出力

#　結果の抜き出し
result_array = [[key[0],key[1]] for key in x.keys() if x[key].value()==1]
df_result = pd.DataFrame(result_array, columns=['社員番号','グループ案'])
df_result.sort_values('グループ案',inplace=True)

# 社員のデータと結合
merge_cols = ['社員番号','年目','部署名','氏名','勤務地'] + past_group_col
df_result = pd.merge(df_result, df.loc[:, merge_cols], on='社員番号')

df_result.head()

結果を保存する。

df_result.to_excel(r'グループ分け案.xlsx',index=False)

参考

参考HP

• 最適化におけるPython

書籍