希望調査をもとに参加者のグループ配属を最適化する（主に制約条件の書き方のメモ）

# この記事は？
pythonのpulpソルバを使用してグループ分けを実現するためのtipsを備忘録として残しておく．
本記事の内容は個人の学習記録であり，所属する組織とは無関係である．

# シチュエーション

内容の異なる複数のグループワークがあり，参加者はどれか一つだけに参加するシチュエーションを考える．
参加者の全てのグループの志望度（例えば10段階評価）の調査が完了している．

# 目的
参加者全体の達成志望度が最大になる班分けの実行．
その際に，各グループの定員などの制約条件も満たすようにする．

# 方法
pythonのpulpパッケージを使用する．
使用方法等の説明は[分かりやすい記事](https://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17)に譲る．

# データ
参加者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  |
|  ...  |  ...  |  ...  |  ...  |  ...  |

 
```python
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

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

#### 全てのグループの定員は偏らないようにする
参加者数をグループ数で割った下図の商 ~ +1 の範囲内に収める
```python
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)
```

#### (オプション)ある特定の参加者属性が偏らないようにする
上記と同様

```python
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)
```

割合を一定範囲で収めたい，等のゆるい制約を貸す場合は場合は以下のように書ける
```python
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以下

```python
ID1, ID2 = "0001", "0002"
for g in groups:
    problem += x[ID1, g] + x[ID2, g] <= 1
```

#### (オプション)ある特定の参加者同士が同じグループになるようにする
同じグループになる = 1になるグループが同じ = 各グループの差が0

```python
ID1, ID3 = "0001", "0003"
for g in groups:
    problem += x[ID1, g] - x[ID3, g] == 0
```

# 最適化問題を解く
```python
status = problem.solve()
```

# 結果の抜き出し
```python
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')
```

# 多くの参加者の希望が第一希望になっているかを確認する
```python
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)
```