はじめに
この記事はBrainpad Advent Calendar 2025の9日目になります。
株式会社ブレインパッドでデータサイエンティストをしている25新卒hiroeです。
新卒研修のチーム分けを数理最適化で行いました。
ブレインパッドでは毎年、新卒研修の一環として数理最適化を用いた「研修チーム分け」が恒例行事となっています。
25卒版として、今年は複数の目的関数に明確な優先順位をつけて最適化する、辞書式最適化を用いてチーム分けを行いました。
以降の内容は、以前白金工業Meetupで発表した内容の一部です。
この発表では数理最適化とは何か？から解説をしていますので、よければこちらもご覧ください。
研修の概要
ブレインパッドの新卒研修は大きく3つのフェーズに分かれています。
Phase 1 (4月)：自社理解・ビジネス基礎
Phase 2 (5月)：エンジニアリング・データサイエンス
Phase 3 (6月)：総合演習（ミニプロジェクト）
引用元
今回は、研修の総仕上げであるPhase 3「ミニプロジェクト」のチーム分けを新卒メンバーで最適化しました。
最適なチーム分けとは？
人事から提示された条件は以下の3つです。
- 対象人数 ($I$)：新卒データサイエンティスト11名
- チーム数 ($J$)：3チーム
- チームの人数は3人もしくは4人
この条件を守りながら、最適（理想的）なチーム分けとは何かをメンバーで議論しました。
色々案は出ましたが、最終的に用いた観点は以下の3つです。
- データ分析の経験がチーム間でなるべく均等である
- 研修Phase2の中で、kaggleのように予測モデルを作り、スコアを競い合う研修がありました
- そのスコアが均一になるようにすれば、この観点は達成できます
- 大学での専攻がそれぞればらけている
- アンケートで「学部卒」「修士卒」「博士卒」の人数を集計しました
- 結果、学部卒が2人、博士卒が2人となったため、それぞれ同じチームになっていなければ、この観点は達成できます
- チームメンバー同士の相性が良い
- 相性の良さとはどのように表現すればいいのか...
- 今回は、メンバーのMBTIをアンケートで答えてもらい、「分析家」「外交官」「番人」「探検家」のいずれかに分類
- それぞれの属性がなるべくバラバラに分散していれば、この観点は達成できます
- これが本当に、相性が良いことにつながるのかは不明ですが...
定式化
数理最適化で問題を解くには定式化を行う必要があります。
定式化とは
- 最適化によって何を決定したいかを表す「決定変数」
- どのような状態になっているのが理想的かを表す「目的関数」
- 解が絶対に守るべき条件を表す「制約条件」
の3つを数式で設計することです。
決定変数
今回の問題で決定したいのは「この人がどのチームに属すか」です。
よって以下のように決定変数を定めます。
$$
x_{i,j} = \begin{cases}
1 & \text{人} i \text{がチーム} j \text{に割り当てられる} \\
0 & \text{人} i \text{がチーム} j \text{に割り当てられない}
\end{cases}
$$
制約条件
制約条件をまとめると次の3つになります。
- 11名を3つのいずれかのチームに割り当てる
- チームの人数は3人か4人
- 学部卒、博士卒が同じチームになっていない
これらを数式で表現します。
11名を3つのいずれかのチームに割り当てる
メンバー$i$の属しているチーム数がちょうど1であれば、必ずどれか1つのチームに割り当てられていることになります。
$$
\sum_{j \in J} x_{i,j} = 1 \quad (\forall i \in I)
$$
チームの人数は3人か4人
チーム$j$に属している人の総和が3以上4以下であればOKです。
$$
3 \le \sum_{i \in I} x_{i,j} \le 4 \quad (\forall j \in J)
$$
学部卒、博士卒が同じチームになっていない
$Major_{i, \text{学部}}$は、メンバー$i$が学部卒だった時に、1になります。
つまり、$\sum_{i \in I} x_{i,j} \times Major_{i, \text{学部}}$はチームjのメンバーの学部卒の人数を表します。
これが1以下であれば、学部卒が同じチームではないことになります
博士卒も同じように定式化できます。
$$
\sum_{i \in I} x_{i,j} \times Major_{i, \text{学士}} \le 1 \quad (\forall j \in J)
$$
$$
\sum_{i \in I} x_{i,j} \times Major_{i, \text{博士}} \le 1 \quad (\forall j \in J)
$$
目的関数
目的関数は以下の2つになります。
- メンバーのMBTIがなるべくばらけている
- 分析演習スコアの平均が、チーム間でなるべく均等になっている
メンバーのMBTIがなるべくばらけている
最初に、MBTIに関する定数を用意します。
MBTIの結果は16タイプに分けられますが、3チームに対して16タイプをばらけさせるのは難しいため、16タイプを4タイプにまとめました
$$
M = \{ \text{分析家}, \text{外交官}, \text{番人}, \text{探検家} \}
$$
アンケートでメンバーのMBTIを調査し、その結果を定数に反映させます。
$$
MBTI_{i,m} = \begin{cases}
1 & \text{人} i \text{がMBTIのタイプ} m \text{である} \\
0 & \text{人} i \text{がMBTIのタイプ} m \text{でない}
\end{cases}
$$
これで目的関数を立式する準備ができました。
「ばらけている」を数式で表現することは、比較的複雑になるので順に解説します。
- チーム$j$に属する、MBTIタイプ$m$の総人数を計算する
$$
\sum_{i \in I} x_{i,j} \times MBTI_{i, \text{m}}
$$ - 最もMBTIがばらついている理想的な人数を計算する
$$
\lceil \frac{\sum_{i \in I} MBTI_{i,m}}{3} \rceil
$$
「タイプ$m$の総人数÷3チーム」人が各チームに居る状態が最もばらついている理想人数です。上式はこれを数式で表現しています。$\lceil \enspace \rceil$は小数点切り上げを表します。 - 理想状態からの逸脱具合を表現します
$$
\lceil \frac{\sum_{i \in I} MBTI_{i,m}}{3} \rceil + z_m
$$
$z_m$がタイプ$m$に関する逸脱人数を表します。このような役割をもつ変数をスラック変数と言います。 - 制約条件の形にする
$$
\sum_{i \in I} x_{i,j} \times MBTI_{i, \text{m}} \leq \lceil \frac{\sum_{i \in I} MBTI_{i,m}}{3} \rceil + z_m
$$
これでチーム$j$のタイプ$m$の人数は、理想人数から$z_m$人離れていることを数式で表現できました。
目的関数としてやりたかったことは、チーム$j$のタイプ$m$の人数を理想人数に近づける（ばらつかせる）ことでした。
つまり、目的関数は
$$
\text{minimize} \sum_{m \in M} z_m
$$
となります。
分析演習スコアの平均が、チーム間でなるべく均等になっている
幸いなことに、この目的関数のやりたいことは分析スコアをばらつかせたい、つまり先ほどのMBTIと同じです。
ということで、MBTIの目的関数と同じ要領で
$$
\sum_{i \in I} x_{i,j} \times Score_{i} \leq \text{Score_average} + Z_{j}
$$
この制約を追加し
$$
\text{minimize} \sum_{j \in J} z_j
$$
これが目的関数になります。
複数目的関数があるときの最適化
定式化によって2つの目的関数が出てきました。
目的関数が複数あると、1つの場合と同じ手法は使えません。
複数ある場合の手法はいくつかありますが、代表的なものを4つ紹介します。
- 各目的関数を別の問題として、それぞれで最適化を行う
- 重み付き和法
- 各目的関数に重みを掛けて足し合わせて、1つの目的関数とする
- 多目的最適化
- 各目的関数を同時に考慮しながら最適化を行う
- 辞書式最適化
- 優先度の高い目的関数から順に最適化する
各手法の詳細やメリデメは以下資料を参照ください。
今回の場合、「MBTIを目的関数に使う」ことが、伝統的に続いているチーム分け最適化の今年の独自ポイントだったので、これを優先的に反映させたいと考えました。その結果、目的関数に優先順を付けられるときに使える辞書式最適化を用いました。
辞書式最適化での実装
辞書式最適化では最初に最も優先度の高い目的関数のみで最適化を行います。
よって、目的関数は
$$
\text{minimize} \sum_{m \in M} z_m
$$
のみで最適化を実行します。
最適化が完了すると、$z_m$の最小値が分かります。
ここでは仮に$z_m=10$だったとします。
次は制約に$z_m=10$を入れつつ、分析演習スコアの目的関数で最適化することで、最も優先したいMBTIのばらつきは最適のまま、分析演習スコアのばらつきを最小化することができます。
以上の定式化をpulpでモデリングして最適化を実行します
import pulp
# 定数の設定
I = [i for i in range(len(question_df_dummy))]
J = [1, 2, 3]
MBTI = question_df_drop["MBTI"].unique()
Score_average = question_df_dummy['スコア_Z'].sum() / 3
def optimize_dict(seed):
cbc_solver = pulp.PULP_CBC_CMD(options= [f"RandomS {seed}"])
# 決定変数
x = pulp.LpVariable.dicts('x', [(i, j) for i in I for j in J], cat='Binary')
z_mbti = pulp.LpVariable.dicts('z_mbti', MBTI, cat='Continuous', lowBound=0)
z_score = pulp.LpVariable.dicts('z_score', J, cat='Continuous', lowBound=0)
model = pulp.LpProblem(name='team', sense=pulp.LpMinimize)
## 制約
# メンバーはいずれかのチームに属する
for i in I:
model += pulp.lpSum(x[i,j] for j in J) == 1
# チームの人数は3人か4人
for j in J:
model += pulp.lpSum(x[i,j] for i in I) >= 3
model += pulp.lpSum(x[i,j] for i in I) <= 4
# 学部卒、博士卒はそれぞれ同じチームにならない
for j in J:
model += pulp.lpSum(x[i,j]*question_df_dummy.iloc[i]["学歴_博士卒"] for i in I) <= 1
model += pulp.lpSum(x[i,j]*question_df_dummy.iloc[i]["学歴_学部卒"] for i in I) <= 1
# MBTIがチームでばらけるようにする
for j in J:
for m in MBTI:
model += pulp.lpSum(x[i,j]*question_df_dummy.iloc[i][f"MBTI_{m}"] for i in I) <= np.ceil(float(str(pulp.lpSum(question_df_dummy.iloc[i][f"MBTI_{m}"] for i in I)/3))) + z_mbti[m]
# 分析演習スコアがチームでばらけるようにする
for j in J:
model += pulp.lpSum(x[i,j]*question_df_dummy.iloc[i][f"スコア_Z"] for i in I) - Score_average <= z_score[j]
# 最適化1段階目
model_mbti = model.copy()
model_mbti += pulp.lpSum(z_mbti[m] for m in MBTI)
model_mbti.solve(cbc_solver)
# 最適化2段階目
# 1段階目の最適値を計算する
optimal_mbti = sum(z_mbti[m].varValue for m in MBTI)
# 結果を制約に加える
model += pulp.lpSum(z_mbti[m] for m in MBTI) == optimal_mbti
model_score = model.copy()
model_score += pulp.lpSum(z_score[j] for j in J)
model_score.solve(cbc_solver)
おわりに
チーム分けは、人員配置問題として最適化の中でもよく使われているテーマですが、どんなチームが最適なチームかを考えるのは中々難しいと感じました。
より複雑な人員配置では、各個人の経験や希望など様々な変数が絡むので、より丁寧な目的関数や制約条件の設計が必要になります。
研修の一環として、その練習になるものを経験できたのはよかったです。
最後までお読みいただきありがとうございました。