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

Posted at 2023-12-19

はじめに

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

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

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

具体的に・・・

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

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

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

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

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

実装した簡易アプリ

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

利用した言語・ライブラリのバージョン・依存関係は以下の通りです。

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を利用

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

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

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

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

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

最適化のポイント

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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