妻の雑務を最適化したい（Streamlit＋PuLPでグループ分け最適化アプリ）

# はじめに

こんにちは！
私は業務で、数理最適化を活用したシステム開発、および導入支援に従事しています。

本記事は、私の妻が担当した **雑務（部署の懇親会のグループ分け）** を題材として、それを**数理最適化問題**に落とし込み、条件を満たすようなグループ分けを求める簡易的なアプリをPythonで実装してみました。

「とりあえず動くものを作る」という意識で取り組んだため、もし特に数理最適化周りについて、より効率的なアプローチをご存じの方、また思いついた方は、ぜひご指摘いただけると幸いです。
 

# 具体的に・・・

「部署の懇親会のグループ分け」の背景や概要は以下の通りとのことでした。

- 部署全体の人数は **100人程度**、またその部署内に**いくつかのチーム**が存在する。
- この部署には、特に若手について、**別チームの社員との親交が薄い**という課題があった。
- そこで、**別チームの若手同士や、若手と年次が上の社員の親睦を深める**ために懇親会が開催されることとなった（以下、年次が上の社員を「ベテラン」と呼びます）。
- 懇親会は全員参加の予定であるため、**当日はいくつかのグループ**に分かれる。（**このグループ分けを妻が担当**）
- グループごとに、**若手の人数はなるべく均等**にしたい。
- 各グループ内の社員の**所属チームはなるべくばらける**ようにしたい。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/6081d7c4-945f-618e-fef6-886d59b48b92.png)

このようなグループ分けを、妻は手動で実施していたとのことなのですが、 **「できるだけ、チーム・年齢層がばらばらになるように、100人のグループ分けをすること」 は、人力では至難の業**であり、実際に妻もだいぶ苦戦していました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/1983c2ee-161e-fe5d-867b-64904d80bf96.png)


一方、この手のグループ分けは**数理最適化**の得意とするところであり、同じ条件ではないですが、 **「数理最適化でグループ分け」** に取り組んだ記事[^1]や書籍[^2]もいくつか存在します。

そこで、「じゃあ、やってみよう」と思い、実際に取り組んでみたというのが、この記事の前振りとなります。




# 実装した簡易アプリ

実装した簡易アプリは以下の通りです。（雑なUIで恐縮ですが。。）

![movie6.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/7044d3f5-bbc5-c22f-743b-f546d523aec6.gif)

利用した言語・ライブラリのバージョン・依存関係は以下の通りです。
```
python = ">=3.11,<3.12"
numpy = "^1.24.3"
pulp = "^2.7.0"
streamlit = "^1.29.0"
pandas = "^2.1.3"
```
+ Pythonは3.11.4を利用
+ 画面はstreamlitを利用
+ 最適化計算はモデリングツールをPuLP、ソルバーはデフォルトのCBCを利用
+ データ操作にPandasやNumPyを利用

実装したプログラムは以下のリポジトリに格納しています。

https://github.com/nukipei/social_gathering/tree/main

具体的なインプット（入力データ）とアウトプット（計算結果）は以下の通りです。

* インプット
  * 社員数
  * チーム数 
  * 各社員ごとの情報（年齢層, 所属チーム）
  * 1グループあたりの人数
* アウトプット
  * グループ分けの結果（CSVダウンロードも可）
  * グループごとの年齢層・チームの内訳を示したグラフ
  * チーム被り状況を示した表

具体的な、インプット・アウトプットの詳細イメージは本記事の最後に説明していますので、興味のある方は是非ご覧ください。

:::note
本記事では、実装の詳細や、具体的な定式化の説明は行いません。興味のある方は、↑のGitHubを見ていただければと思います。
:::

# 最適化のポイント
「部署の懇親会のグループ分け」の要件について、最適化計算に関係のある部分を再掲すると、以下の通りです。


- 部署全体の人数は **100人程度**、またその部署内に**いくつかのチーム**（今回は7チームほど）が存在する。
- **当日はいくつかのグループ**（今回は7 or 8人）に分かれる。
- グループごとに、**若手の人数はなるべく均等**にしたい。
- 各グループ内の社員の**所属チームはなるべくばらける**ようにしたい。

細かい定式化の説明は長くなってしまうので割愛し、その代わりに**グループ分けを最適化問題に落とし込んだ際のポイント**をいくつか紹介します。

## ポイント①：「ばらばら」「均等」を数式で表現する。

今回扱う懇親会グループ分けでは、「所属チームはなるべくばらけるようにしたい」「若手の人数はなるべく均等にしたい」とあるように、**社員の属性を分散させたい**というのが主旨ということがわかると思います。しかし、素直に「分散をそのまま最小化する問題」としてしまうと、分散が非線形であるため、解きづらくなってしまいます。

そこで、今回は他の記事に倣い[^3]、 **「各グループの社員の属性被りの数の、最大と最小の差を最小にする問題」** として解いています。

例えば、簡単のために部署内に2チームしか存在しないとして、各グループのチーム被りの数を均等にしたいというケースを考えます。この時、以下を最小にすることで、均等を表現します。

```math
max(各グループのチーム1の人数)-min(各グループのチーム1の人数)
```

以下の図にて、直観的な理解を示します。チーム1の人数の最大値と最小値の差が小さい、グループ分け案②のほうが、各グループの所属チームが均等になっていることがわかると思います。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/c317c19f-3ee6-f6ef-ad05-7ab2a74342f4.png)

## ポイント②：条件の優先度を考慮して、計算する。

ポイント①の方法で、チームと年齢層ができるだけ分散するようなグループ分けを求め、妻に見せたところ・・・

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/de113b4e-ce31-b56a-b443-70f8d43881a4.png)

このように「うーん」という顔をされました。どうやら、チーム数の都合上、どうしてもグループ内でチーム被りが発生してしまうのですが、その際 **「若手のチーム被りを優先して、発生させないようにしたい」** とのことでした。この時の実装は、若手もベテランも平等にチーム被りが発生する状況となっており、そこが微妙ということらしいです（厳しい・・）。

そこで、最後の要件である **「各グループ内の社員の所属チームはなるべくばらけるようにしたい。」** について、より詳細に整理したところ、以下のように、**同じばらばらでも優先度**が存在することがわかりました。

  - 同じグループの人はすべて別チームがベスト（ほとんど無いケースなので、今回は考えません。）
  - もしチーム被りが発生する場合は、以下の優先度順でばらけさせたいとのこと。
    - 第一優先：各グループ内で、**若手同士のチーム被り**ができるだけ発生しないようにする。
    - 第二優先：各グループ内で、**若手全員がベテランとできるだけチームが被らない**ようにする。
    - 第三優先：各グループ内で**ベテラン同士のチーム被り**ができるだけ発生しないようにする。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/f425627c-acfc-ae48-2d69-724d084d4fdc.png)



そこで、東京海洋大学の久保先生がX[^4]で紹介した、**優先順位付きの多目的最適化に対するアプローチ**を適用してみました。

本記事での具体的なアプローチは以下の通りです。

1. まず最初に、**各グループ内の「若手のチーム被り」ができるだけ発生しない**ように、目的関数を設定し、それを最小にするようなグループ分けを求める。
2. 次に、**「各若手と同じグループのベテランのチーム被り」ができるだけ発生しない**ように、目的関数を設定し、それを最小にするようなグループ分けを求める。この時、**「1の目的関数 ≦ 1で求めた最適値」** という制約を加える。
3. 最後に、**各グループ内の「ベテランのチーム被り」ができるだけ発生しない**ように、目的関数を設定し、それを最小にするようなグループ分けを求める。この時、**「1の目的関数 ≦ 1で求めた最適値」** と、**「2の目的関数 ≦ 2で求めた最適値」** という制約を加える。

注目すべきは、より優先順位が高いものから考慮に入れて最適化計算を行い、**その解を制約として後続の計算に追加**している点です。これにより、優先順位通りのグループ分けを実現することができます。

このアプローチを取って、再度グループ分けを計算し、見せたところ、「いいね」と納得してもらえました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/7a2cdef4-61a4-4281-304f-22241d41cadf.png)

あっさり説明で恐縮ですが、本記事はここまでにしたいと思います。（より細かい定式化の話は、どこかのタイミングで別記事でしたいと思います。）

# まとめ

妻が担当した雑務である「部署の懇親会のグループ分け」の簡易アプリをPythonで実装し、その概要やポイントを紹介しました。

何か、コメント、指摘がある方は是非お願いします！特に最適化計算については、個人的にほかに良いアプローチがある気もしているので、より効率的なアプローチをご存じの方、また思いついた方は、ぜひご指摘いただけると嬉しいです。

# （最後に）画面のイメージ

最後に、作成したグループ分けアプリのインプット・アウトプットのイメージをいくつか紹介します。~~無駄に~~様々な情報を可視化していますので、ここで供養させてください。

## インプットデータの設定
### 社員数の設定

部署全体の社員数を数値で設定します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/edf4ca24-8585-26e6-4fab-14c40c481ea0.png)

### チーム数の設定

部署内のチーム数を数値で設定します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/a3aab329-fddc-ddde-5b03-a134f16ee649.png)

### 各社員がどのチーム、どの年齢層なのかを設定

csvファイルで各社員がどのチーム、どの年齢層なのかを設定します。
現状は、ランダムに生成したデータと、サーバーに直接配置した手動設定データのみを設定できます。（そのうち、アップロードできるようにするかもです。。）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/5151e608-644d-a791-031c-502928931c22.png)

各社員のチーム、年齢層は「データを表示」を押下することで、確認できます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/e07989d8-a2a6-0ee0-9d76-f470ce096d7c.png)

## 計算の実行

「グループ分け実行」を押下すると、計算を実行します。計算中は以下のように、「計算中」と表示されます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/82214fa5-011a-d7ba-d50b-e485ae712056.png)


## アウトプットの確認

### グループごとの社員一覧の確認

グループごとの社員一覧を確認できます。また、社員のチームや年齢層ごとに色を分けて表示することも可能です（図はチームごとに色分けをした例。）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/30d60206-b08b-cdcd-ade8-87a5fa190aad.png)

ちなみに、★マークは若手の社員であることを示しています。

### グループごとの年齢層・チームの内訳

記事冒頭のGIF画像で紹介できなかった機能ですが、グループごとの社員の年齢層とチームの内訳をグラフで確認できます。図は年齢層の内訳を示していますが、年齢層が均等になっていることがわかるかと思います。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/b967ff5d-6ec6-df12-c2eb-a9f6b861cf37.png)

### チーム被り状況の確認

こちらもGIF画像にはない機能で、グループごと、チームごとのチーム被りの状況を確認できます。セレクトボックスで選択したチーム（図ではチームA）の年齢層ごとの被り数や、各グループの分散具合を確認できます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/4a14f0b8-114e-1447-4902-81d8c56d0408.png)

### 結果をCSV形式でダウンロード

おまけ機能ですが、以下の画像のように、ボタンを押下することで、グループ分けの結果をCSV形式でダウンロードできます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/455822/15cf75e7-649e-c997-0e0c-6f0ef6c959d7.png)


[^1]: https://qiita.com/matsulib/items/898873b73d584c7dcb8b 等
[^2]: https://www.ohmsha.co.jp/book/9784274227356/
[^3]: https://qiita.com/SaitoTsutomu/items/f4478dfbc3c1cf6425e3
[^4]: https://x.com/MickeyKubo/status/1700297528376279055