こんにちは、新卒1年目データサイエンティストのはだです。
この記事はBrainPad Advent Calendarの12日目の記事です。

はじめに

本記事では新卒研修のチーム決めを混合整数計画問題で定式化して解いてみた話をしたいと思います。
研修の空き時間に同期と雑談(ヒアリング？)しながらゼロからモデルを組み立てて、実際のチーム決めでも使われたのでとても良い経験になりました。
以下ではブレインパッドの新卒研修のざっくりした説明とチーム分けのモデルについて説明していきたいと思います。

研修について

ブレインパッドの新卒研修は4,5,6月の3ヶ月間あり、4月はビジネス系研修、5月は技術系研修、6月は実際のプロジェクトを想定した模擬案件研修(ミニプロジェクト)を行います。
新卒研修スケージュール
新卒研修の全体スケージュール (Platinum Data Blogより)

さらに詳しい内容は同期のインタビュー記事が公開されていますのでそちらを是非ご覧ください。

ミニプロカリキュラム
ミニプロジェクトカリキュラム (Platinum Data Blogより)

さて、本題の定式化を行なったのはこの6月にあるミニプロジェクト(通称ミニプロ^[1])のチーム分け^[2]です。
ミニプロでは実際の案件を想定してヒアリングから最終報告までを1ヶ月で行います。
私が所属するデータサイエンティスト職は同期が23人いるため6チームに分かれてチームごとに作業を行います。
1ヶ月もの間，苦楽を共にする仲間を決めるチーム分けは研修生にとって大きなイベントとなります。
そのため数理最適化の力を借りて全員が納得のいくようなチーム決めを行うことを目指します。
(と言いつつ乱数でｴｲって決めても誰も文句は言わないのですが、5月の最適化研修で混合整数計画問題の定式化の講義を受けたのでせっかくなので早速実践していこう気持ちです笑)

定式化

どんなチーム分けが良いかを研修の空き時間に同期で集まってワイワイ議論しました。
チーム分けとしては色々な方法^[3]が考えられますが、話し合いの結果、各チームに色々なバックグラウンドを持った人がいた方がよかろうということになりました。
そこで各チームを構成する人がなるべく多様になるように定式化します。
ここで使える各人の属性としては研究分野、博士号の有無などがあります。
これだけだと少し少ない気もするので、加えて4,5月での自習研修の進捗度合いによって3つのスキルの有無のフラグ変数も追加します(これは属性として妥当性が怪しくかなり苦しいですが…まあ笑)。
これらをまとめて以下のような入力データを作成します。

改めて、これらの属性(フラグ変数)がなるべくばらけるような定式化を行いたいです。
今回の最適化問題は特定の最大化ないし最小化したい目的関数があるわけではないので、基本的に制約を満たす実行可能解を見つける問題として定式化します。
一方で実行可能領域が空集合である場合を考慮して

絶対に守ってほしいハード制約
できれば守ってほしいソフト制約

の二つを考えて、ソフト制約のスラック変数の最小化問題として定式化します。
ここでスラック変数は各ソフト制約の違反量を表すものです。
(結局、最適値が0になってしまったので最初から全てハード制約にしても同じでしたが…)

考慮した制約

ハード制約

前述の通り同期のデータサイエンティスト23人を6チームに割り当てる必要があります。
すなわち3人チームが1チームできてそれ以外は4人チームという状況です。
これはチーム分けをする上で絶対になりたってほしい条件のためハード制約として考えます。

ソフト制約

考えている属性がなるべく偏りの無いようにします。
改めて考慮している属性は以下のようなものがあります。

学位
同期データサイエンティストには博士が4人いるので各チーム高々1人になるようにします。
(個人的には全員博士で固めたドリームチームも見てみたいですが、今回は固まらないようにします…)
大学時代の専攻
あまり粒度を細かく切りすぎても大変なので理学系、情報系、社会科学系の3カテゴリに分けてそれぞれがばらけるようにします。
これも境界の専攻やどれにも当てはまらない等ありますがとりあえず一番近そうなものに割り振ります。
(重複ありでも定式化上、問題はないのですが、今回は各人がいずれか一つの専門領域に属するものとします。)
自習研修の進捗
進捗度合いの中央値以上か未満かでSKILL1,2,3のフラグ変数を作ります。
かなりこじつけです笑

ここで記号の定義をしておきます。
まず、
$I=\{1,2,...,23\}:$ 人の集合
$J=\{1,2,...,6\}:$ チームの集合
$K=\{\text{Science}, \text{Information}, \text{Social}\}:$ 専攻の種別
$P=\{1,2,3\}:$ スキルの種別

さらに入力データから定まる定数を以下のように表します。
$D_i \in \{0,1\}:$ 人 $i$ が博士号を持っているかどうか
$S_{i,k}\in \{0,1\}\ i\in I, k\in K:$ 人 $i$ が専攻 $k$ 出身かどうか
$C_{i,p}\in \{0,1\}\ i\in I, p\in P:$ 人 $i$ がスキル $p$ を持っているかどうか

最後に決定変数について以下のように定めます。
$x_{i,j} \in \{0,1\}\ i\in I, j\in J:$ 人 $i$ がチーム $j$ に割り当てられるかどうか
$z_{\text{doc}} \in R_{\ge 0}:$ 博士号制約に対する違反量を表すスラック変数
$z_{\text{spe},k} \in R_{\ge 0}, k\in K:$ 専攻 $k$ の制約に対する違反量を表すスラック変数
$z_{\text{skill},p} \in R_{\ge 0}, p\in P:$ スキル $p$ の制約に対する違反量を表すスラック変数

この設定のもとで以下のような定式化を行います。

\begin{aligned} &\text{minimize} & &z_{\text{doc}} + \sum_{k\in K}z_{\text{spe},k} + \sum_{p\in P}z_{\text{skill},p} \\ &\text{subject to} & &\sum_{i\in I} x_{i,0} = 3, \\ & & &\sum_{i\in I} x_{i,j} = 4, & j \in J\setminus \{0\}, \\ & & &\sum_{j\in J} x_{i,j} = 1, & i \in I, \\ & & &\sum_{i\in I} D_i x_{i,j} \le \left \lfloor \frac{\sum_{i\in I}D_i}{6} +1 \right \rfloor + z_{\text{doc}}, & j \in J\setminus \{0\}, \\ & & &\sum_{i\in I} S_{i,k} x_{i,j} \le \left \lfloor \frac{\sum_{i\in I}S_{i,k}}{6} +1 \right \rfloor + z_{\text{spec},k}, & j \in J\setminus \{0\},\ k\in K, \\ & & &\sum_{i\in I} C_{i,p} x_{i,j} \le \left \lfloor \frac{\sum_{i\in I}C_{i,p}}{6} +1 \right \rfloor + z_{\text{spec},p}, & j \in J\setminus \{0\},\ p\in P. \\ \end{aligned}

制約式の1,2行目はハード制約の各チーム3人か4人の制約となっています。
ここで0番目チームが3人チームという固定を行なっています。
3行目は各人がいずれかのチームに割り振られるという制約となっており、4行目以降は各チームを構成するメンバー属性がばらけるような多様性制約です。
(今思い返すとこの制約の右辺は $\lceil \cdot /6 \rceil$ にする方が自然ですね)
ここで3人チームに関して多様性制約を外した意図としては、3人チームは4人チームに比べて人手が足りないのでスキルが高い人や博士が偏っても良いだろうという気持ちを表しています。
以下は実際にpulpでモデリングしたコードです。

# 集合
I = list(range(len(df)))
J =list(range(6))
IJ = [(i,j) for i in I for j in J]
K = {'IS_SCI', 'IS_INFO', 'IS_SOCIAL'}
P = {1,2,3}

# 問題定義
prob = pulp.LpProblem('TeamAssignmentProblem', pulp.LpMinimize)

# 決定変数
x = pulp.LpVariable.dicts('x', IJ, cat='Binary')
z_doc = pulp.LpVariable('z_doc', lowBound = 0, cat='Continuous')
z_spe = pulp.LpVariable.dicts('z_spe', K, lowBound = 0, cat='Continuous')
z_sk = pulp.LpVariable.dicts('z_sk', P, lowBound = 0, cat='Continuous')

## ハード制約
# 各グループには3人か4人割り当てられる (グループ0: 3人、　グループ1,..,5: 4人)
for j in J:
    if j == 0:
        prob += pulp.lpSum([x[i,j] for i in I])  ==3
    else :
        prob += pulp.lpSum([x[i,j] for i in I])  ==4

# 各人がいずれかのグループに割り当てられる
for i in I:
    prob += pulp.lpSum([x[i,j] for j in J])  == 1

# 3人グループの専攻毎の偏りをなくす
for k in K:  
    prob += pulp.lpSum([df[k][i] * x[i,0] for i in I]) == 1

## ソフト制約
# 各グループに博士は高々1人
for j in J:
    prob += pulp.lpSum([df['IS_DOCTOR'][i] * x[i,j] for i in I]) <= (df['IS_DOCTOR'].sum() // 6 + 1) + z_doc

# 専攻毎の偏りをなくす
for k in K:    
    for j in J:
        if j == 0:
             continue
        prob += pulp.lpSum([df[k][i] * x[i,j] for i in I]) <= (df[k].sum() //6 + 1) + z_spe[k]



# スキルの偏りをなくす
for p in P:
    for j in J:
        if j == 0:
             continue
        prob += pulp.lpSum([df[f'SKILL{p}'][i] * x[i,j] for i in I]) <= (df[f'SKILL{p}'].sum() //6 + 1) + z_sk[p]

# 目的関数
prob += z_doc + pulp.lpSum(z_spe) + pulp.lpSum(z_sk)
prob.solve()

チーム決め当日

実際にミニプロ研修初日にチーム決めを上のモデルを使って行いました！
上で少し述べた通り、今回のインスタンスに対しては最適値は0となって複数の最適解が存在することが事前に分かっていました(ソルバーに渡すseed値によって実行するたびに解が変わる)^[4]。
そこでチーム決めの際は同期に適当に好きな数字を言ってもらってソルバーに渡すseed値を決めてチーム決めを行いました。
ちなみに選ばれたseed値は97421でした笑。

以下に得られた解のチーム編成ごとに属性の合計値を集計した表を示します。
表より全体的に満遍なんく属性がばらけていることが見て取れます。
特に3人チームにはスキルが高い人が集まっているので意図通りの挙動をしてくれていそうです^[5]。

おわりに

モデルとしてはそこまで複雑なものではないですが、同期と話し合いながらモデルを作って実際にそれを使ってチーム決めをするという貴重な経験ができて良かったです。
また、一人ずつseed値を言っていくみたいなパフォーマンスも楽しかったので良い思い出になりました^[6]。
最後までお読みいただきありがとうございました。

脚注

ミニプロで扱った小売店のデータ分析というお題は今年のデータサイエンティストサマーインターンでも使われており、それに関してラジオ(白金鉱業.FM)で詳しく話していただいてるのでそちらも是非お聞きください ↩︎
今回行ったのはデータサイエンティストのミニプロチームのみです ↩︎
雑談の中で各人が選好を申告してマッチングとして定式化するみたいなことも言ったりしてましたが不和が生じそうなので却下になりました笑 ↩︎
全部でいくつの最適解があるのか知りたくもなったので制約プログラミングソルバーでモデリングした方が良かったかもなとも思っています、MILPソルバーでもこの定式化ならPuLPのドキュメントにあるような方法で最適解の列挙ができそうです ↩︎
実際、この3人チームは他チームより人手が1人少ないにも関わらず、どのチームよりも重実装な分析を行なっていて凄かったです ↩︎
後で「実は乱数仕組んでただろ」と同期に疑われましたが笑 ↩︎

Discussion