はじめに
新年度が始まり、弊社 Fixstars Amplify でも新しいメンバーを迎えました。グループ合同で行う新人研修では 17 名の新人が 10 題のコーディング課題に取り組みます。彼らの書いたコードは総勢 68 名の先輩レビュアが分担してレビューし、品質についての考え方やコーディング文化を伝えます。
昨年度までの新人研修では、レビュー担当者割り当てについて、次のような問題が発生しており、一部の参加者から不満の声が上がっていました。
- レビュア各々の得意分野が考慮されておらず、レビュアが本領を発揮できなかった。
- 特定の新人にコメント数の少ないレビュアばかり割り当たってしまい、気の毒だった。
- 同じチームの新人のレビューが割り当たらず、関係構築の機会がなく残念だった。
今年度はこれらの問題を解決すべく、どの問題・どの新人にどのレビュアを割り当てれば良いかを、弊社で開発している組合せ最適化プラットフォーム Amplify SDK & Amplify AE を使って最適化しました。結果としては、レビュア全員の希望・新人間での公平感・チーム内での関係構築すべてを考慮した割り当て結果を半日で得ることができました。
本記事では、最適化のための事前準備から、どのようにして定式化を行い、どのような結果を得たのかをコードを交えてご紹介します。最適化コードとその結果だけでなく、課題解決のための各ステップでの考え方についても触れますので、同様の課題に直面した際の参考になれば幸いです。
方針決定と情報収集
私たちの仕事は、新人研修の参加者リストが確定するよりも前の段階から始まりました。
さっそく最適化コードを書き始めたいところですが、その前に、まずはどのような割り当てが「最適」であるのかを定義する必要があります。新人研修事務局も交えて数度の話し合いを行い、事務局の意向や過去の新人研修での反省もふまえて方針を決定することにしました。
まず、レビュアは 1 人あたり 1 題を担当し、均等な数 (2 名または 3 名) の新人を担当することが事務局側により決定されていました。レビュアの負担としては 1 人につきレビュー 3 件程度が妥当であり、また、複数題を担当すると、それだけ問題把握のコストが増えるためです。
これは、組み合わせ最適化を行う上で、最も基礎的な制約条件の 1 つとなります。
次に、過去の反省点をふまえて、議論を行いました。過去の反省点は次の通りです。
- レビュアが存分に本領発揮できるよう、各々の得意分野を考慮して割り当てを行うべき
- 新人間で公平感のある割り当てとするため、新人がもらうコメント数をできるだけ均等にするべき
- チーム内の関係構築のため、同じチームでレビュアが新人をレビューする機会を設けるべき
「レビュアのモチベーション向上のため、自己申告制で担当したい問題と担当したくない問題を決めて、できるだけ希望通りに割り当てるのはどうか」「特定のレビュアが積極的にコメントする人であるかどうかを知るのは難しいのではないか」「同一チームレビュアを割り当てるのは互いを知る機会を増やすために有効な一方、同一チームのレビュアばかりを割り当ててしまうと技術的に偏りが出てしまう可能性があるのではないか」といった意見が出ました。結論としては、組み合わせ最適化への定式化のしやすさや、データ収集のしやすさを考慮し、以下のような方針を取ることにしました。
- レビュアにアンケートを送付し、それぞれの課題を担当したいかどうかを 3 段階で回答してもらう。希望度が最低の課題は割り当てないようにし、さらに希望度が高い課題を担当するレビュアの数を最大にするようにする。
- 新人間で、新人に割り当たる 10 人のレビュアの職位の分布ができるだけ均等になるようにする。シニアエンジニアを 1 点、リードエンジニア以上を 2 点、それ以外を 0 点として、職位の点数の合計のばらつきを最小化する。
- 各新人に対して、同一チームのレビュアをできるだけ多く割り当てるようにする。ただし、同一チームから割り当てるレビュアは 4 人までとする。
その後、新人とレビュアの情報を各部署から集めてきたり、アンケートを送付して結果を回収したりといった作業を経て、ようやく最適化の準備が整いました。3 月 17 日、新人研修開始 2 週間前のことでした。
Fixstars Amplify による定式化と求解
Fixstars Amplify SDK & Fixstars Amplify AE とは
Fixstars Amplify は、弊社が提供する組み合わせ最適化プラットフォームです。
Fixstars Amplify SDK を用いて、組合せ最適化問題を Python で簡単に定式化することができます。定式化した組み合わせ最適化問題は、GPU クラウドソルバーである Fixstars Amplify AE、あるいはその他の組み合わせ最適化ソルバーを呼び出して解くことができます。
Fixstars Amplify の詳細な使い方については、ドキュメント を参照してください。
問題の整理
最適化を始めた段階で、以下のような形式の 2 種類のデータが揃っていました。新人の情報と、レビュアの情報です。
| 新人 | 上長 |
|---|---|
| 田中 | 佐藤 |
| 吉田 | 鈴木 |
| ... | ... |
| レビュア | 上長 | 職位 | 課題1 | 課題2 | ... |
|---|---|---|---|---|---|
| 高橋 | 佐藤 | シニアエンジニア | 積極的に担当したい | 担当しても良い | ... |
| 加藤 | 鈴木 | エンジニア | 担当しても良い | 担当するのは難しい | ... |
| 渡辺 | 鈴木 | リードエンジニア | 担当しても良い | 担当しても良い | ... |
| ... | ... | ... | ... | ... | ... |
我々のゴールは、最適化を行って、以下のような表を作ることです。その際、上記で述べた要件をできるだけ満たすようにする必要があります。
| 新人 | 課題1 | 課題2 | ... |
|---|---|---|---|
| 田中 | 加藤 | 高橋 | ... |
| 吉田 | 加藤 | 渡辺 | ... |
| ... | ... | ... | ... |
Amplify SDK を使用して、要件を制約条件や目的関数の形で書き下し、その後、組合せ最適化ソルバーである Amplify AE を呼び出して解を求めることになります。
実装方針
「誰に何を割り当てるか」というタイプの問題とは異なり、今回は「どのレビュアに、どの新人の、どの課題を担当させるか」という、3 次元の割り当て問題になります。これを一気に最適化しようとすると、考えることが増えて面倒です。そこで、今回は以下のような 2 段階のアプローチを取ることにしました。
- ステップ1： どのレビュアがどの問題を担当するかを決定する
- ステップ2： どのレビュアがどの新人を担当するかを決定する
このようにすることで、変数の数およびモデルサイズも削減でき、ソルバーも良い解を高速に求めやすくなります。また、結果が 2 段階で出てくるので、今回は必要ありませんでしたが、細かなパラメータなどの調整もしやすくなります。さらに大事なことに、私が一度に考える量が少なくて済みます。
ステップ1： 誰がどの問題を担当するか
Python スクリプトを作成し、新人 17 人、レビュア 68 人、課題数 10 題であることを変数においておきます。
num_trainees = 17
num_reviewers = 68
num_problems = 10
前処理として、先述のレビュア CSV から、レビュアの希望度を数値化した NumPy 二次元配列 reviewer_problem_preference_scores を作成しました (コードについては割愛します)。以下は、レビュア 3 人、課題 10 題の例です。各行が各レビュア、各列が各課題に対応しています。配列の要素は、希望度が「積極的に担当したい」なら 0、「担当しても良い」なら 1、「担当するのは難しい」なら 2 としています。
>>> reviewer_problem_preference_scores
array([[0, 1, 1, 1, 0, 1, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
上記の例では、レビュア 0 は課題 0, 4, 7 を積極的に担当したいと回答していることが分かります。レビュア 2 は全ての課題を積極的に担当したいようです。
各問題について、その問題に何人のレビュアを割り当てるかは、事前に決めておきます。課題 1 と 2 は簡単な問題なので少なめに割り当てることにしました。
reviewers_per_problem = [6, 6, 7, 7, 7, 7, 7, 7, 7, 7]
組合せ最適化の時間です。レビュアが課題を担当するかどうかを表す二次元の 0-1 変数 q[i, j] を定義します。q[i, j] は 0 または 1 の値をとる決定変数で、レビュア i が課題 j を担当する場合は 1, そうでない場合は 0 となります。この変数の最適な値を求めることが、ステップ 1 の目的となります。
import amplify
import numpy as np
var_generator = amplify.VariableGenerator()
q = var_generator.array("Binary", shape=(num_reviewers, num_problems))
レビュアが「担当するのが難しい」と回答した課題に対応する変数の値を 0 に固定します。これにより、そのような課題はそのレビュアには割り当てられないようになります。
q *= np.where(reviewer_problem_preference_scores == 2, 0, 1)
制約条件、つまり最適化において必ず満たすべき条件は、
- 各レビュアは、ちょうど 1 問を担当する (各行にちょうど 1 つの 1 がある)
- 各問題には、あらかじめ決めた人数のレビュアが割り当てられる (各列の和が
reviewers_per_problemに等しい)
の 2 種類です。
# 各レビュアは、ちょうど 1 問を担当する制約条件 (q の各行にちょうど 1 つの 1 がある)
one_problem_per_reviewer_constr = amplify.one_hot(q, axis=1)
# 各問題には、あらかじめ決めた人数のレビュアが割り当てられる制約条件 (q の各列の和が reviewers_per_problem に等しい)
reviewers_per_problem_constr = amplify.sum(
amplify.equal_to(q[:, problem_idx], reviewers_per_problem[problem_idx])
for problem_idx in range(num_problems)
)
これらの制約条件を課すことにより、レビュアを問題に割り当てることができます。
この最適化の目的関数、つまり最小化したい関数は、レビュアの希望が満たされているほど小さな値を取るように設計します。レビュアが「積極的に担当したい」と回答している問題を担当した場合、1 回につき目的関数が -1 されるようにすることで、レビュアの希望を最大限に満たすことを狙います。
# レビュアが「積極的に担当したい」と回答している問題を担当した数の和の -1 倍を目的関数とする
preference_objective = (
q * np.where(reviewer_problem_preference_scores == 0, -1, 0)
).sum()
作成した目的関数と制約条件を組み合わせて組合せ最適化モデルを作成し、GPU クラウドソルバーである Amplify AE を呼び出して解を求めます。実行には、Fixstars Amplify のアカウント登録およびトークンの発行が必要です。
# 組合せ最適化モデルの作成
stage1_model = (
preference_objective
+ one_problem_per_reviewer_constr
+ reviewers_per_problem_constr
)
# Amplify AE のトークンとタイムアウト時間を設定して Amplify AE を呼び出す
stage1_client = amplify.AmplifyAEClient(token="AE/XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX")
stage1_client.parameters.time_limit_ms = 1000
stage1_result = amplify.solve(stage1_model, stage1_client)
# 解の取得
q_values = q.evaluate(stage1_result.best.values)
q_values は、決定変数 q の最適な値を表す二次元の NumPy 配列になります。q_values[i, j] が 1 であれば、レビュア i は課題 j を担当することになります。これにより、誰がどの問題を担当するかが決定されました。ここまでの成果を表にすると、以下のようになります。
| レビュア | 課題1 | 課題2 | ... |
|---|---|---|---|
| 高橋 | 0 (担当しない) | 1 (担当する) | ... |
| 加藤 | 1 (担当する) | 0 (担当しない) | ... |
| 渡辺 | 0 (担当しない) | 1 (担当する) | ... |
実際は、全員が希望通りに割り当たりました。つまり、「積極的に担当したい」と 1 つでも回答したレビュアは、そのような課題を担当することになりました。レビュアが多様な好みを持っていたこと、および、レビュアの数が十分に多かったことが、全員が希望通りに割り当たる要因の 1 つだったのではないかと思います。もちろん、いつもこのようにうまくいくとは限りません。
ステップ2： 誰がどの新人を担当するか
ステップ1の結果を踏まえて、次は「誰がどの新人を担当するか」を決定します。このステップで考慮する要件は以下の通りです。
- 各レビュアはできるだけ均等な数のレビューを担当するようにする。
- 新人間で、新人に割り当たる 10 人のレビュアの職位の分布ができるだけ均等になるようにする。シニアエンジニアを 1 点、リードエンジニア以上を 2 点、それ以外を 0 点として、職位の点数の合計のばらつきを最小化する。
- 各新人に対して、同一チームのレビュアをできるだけ多く割り当てるようにする。ただし、同一チームから割り当てるレビュアは 4 人までとする。
このステップでは、「どのレビュアがどの新人のどの課題を担当するか」の 3 項目を決定する必要があります。これらをバイナリ変数の 3 次元配列 x[r, t, p] で表します。レビュア r が新人 t の課題 p を担当する場合は 1, そうでない場合は 0 となります。ステップ 1 の結果から、「レビュア r が課題 p を担当しない」と確定している場合 (q_values[r, p] が 0 の場合) は、対応する変数 x[r, t, p] を 0 に固定し、レビュア r に課題 p を担当させないようにします。
# 変数の発行
x = amplify.VariableGenerator().array(
"Binary", shape=(num_reviewers, num_trainees, num_problems)
)
# 変数の固定
x *= q_values[
:, np.newaxis, :
]
制約条件は以下の通りです。すべて、決定変数 x のうちいくつかの要素の和が特定の値、あるいは特定の範囲内になる、という形で表すことができます。
- 各問題・新人にレビュアがちょうど 1 人割り当てられる
- 各レビュアは、ちょうど 2 件または 3 件のレビューを担当する
- 新人と同じチームからは、4 人以下のレビュアが割り当てられる
# 各問題・新人にレビュアがちょうど 1 人割り当てられる制約条件
one_reviewer_per_trainee_problem_constr = amplify.one_hot(x, axis=0) # (3 次元配列の垂直方向の列にちょうど 1 つの 1 がある)
# 各レビュアは、ちょうど 2 件または 3 件のレビューを担当する制約条件
equal_burden_constr = amplify.clamp(x, bounds=(2, 3), axis=(1, 2)) # (3 次元配列の各レイヤに現れる 1 の数が 2 または 3)
# 新人と同じチームのレビュアのインデックスのリストを返す関数
def same_team_reviewers(trainee_idx: int) -> list[int]:
...
# 新人と同じチームからは、4 人以下のレビュアが割り当てられる制約条件
same_team_constr = amplify.ConstraintList()
for trainee_idx in range(num_trainees):
same_team_constr += amplify.less_equal(x[:, trainee_idx, :].take(same_team_reviewers(trainee_idx), axis=0).sum(), 4)
目的関数は以下の 2 つの線形和となります。
- シニアエンジニアを 1 点、リードエンジニア以上を 2 点、それ以外を 0 点として、職位の点数の合計の分散 (この値が小さいほど、点数の合計ばらつきが小さいことになる)
- 各新人に対して、同一チームのレビュアが割り当てられた場合、-1 点を加点
reviewer_position_scores = ... # レビュアの職位の点数からなる 1 次元 NumPy 配列 (長さ num_reviewers)
# 職位の点数の合計の分散を計算
trainee_position_score_totals = (x * reviewer_position_scores[:, np.newaxis, np.newaxis]).sum(axis=(0, 2))
trainee_position_score_variance = (trainee_position_score_totals**2).sum() / num_trainees - (trainee_position_score_totals.sum() / num_trainees) ** 2
# 各新人に対して、同一チームのレビュアが割り当てられた場合、-1 点を加点
same_team_objective = amplify.Poly()
for t in range(num_trainees):
same_team_objective -= amplify.sum(x[r, t, :] for r in same_team_reviewers(t))
最終的な組合せ最適化問題は、目的関数と制約条件を組み合わせて作成します。
stage2_model = (
trainee_position_score_variance
+ same_team_objective
+ one_reviewer_per_trainee_problem_constr
+ equal_burden_constr
+ same_team_constr
)
この問題を求解すると、どのレビュアがどの新人のどの課題を担当するかが決定されます。これにより、最終的な割り当て表を作成することができました。
| 新人 | 課題1 | 課題2 | ... |
|---|---|---|---|
| 田中 | 加藤 | 高橋 | ... |
| 吉田 | 加藤 | 渡辺 | ... |
| ... | ... | ... | ... |
この割り当て表に基づいて、レビュアに担当する課題と新人を通知し、無事に新人研修を開始することができました。
まとめ
現実に存在するちょっとした組合せ最適化問題を、Fixstars Amplify SDK を使って定式化し、解いてみました。結果としては、計 3 つの目的関数に対して、以下のようになりました。
- レビュアの希望を最大限に満たすこと： 全員が希望通りに割り当たりました。つまり、「積極的に担当したい」と 1 つでも回答したレビュアは、そのような課題を担当することになりました。
- 新人間で、割り当たるレビュアの職位の分布ができるだけ均等になるようにすること： 新人は、「エンジニア 4 人、シニアエンジニア 6 人」か「エンジニア 5 人、シニアエンジニア 4 人、リードエンジニア 1 人」のどちらかが割り当てられることとなりました。職位の点数の決め方を考えると、これは完全に均等な分布であると言えます。
- 各新人に対して、できるだけ同一チームのレビュアを割り当てること：たとえば、Fixstars Amplify の 3 人の新人については、同一チームのレビュアがちょうど 4 人ずつ割り当てられることとなりました。ただし、2 段階最適化の性質上、同一チームのレビュア同士が同じ問題に割り当たってしまった場合は、この目的関数は最大化されないことになります。これは来年以降の宿題とすることにしました。
手動で適当に割り当てを行ったり、組合せ最適化ライブラリを使わずに自分でアルゴリズムを実装したりするのと比較して、以下のようなメリットがあると感じました。
- かかる時間が少なくて済んだ。コードを書き始めてから結果が出るまで半日程度だったと思います。
- 公平感のある割り当てとなった。手動で行うと恣意性を疑われる可能性がありますが、最適化を使うことで、客観的な基準に基づいて割り当てを行うことができました。
- さまざまな要件を考慮した割り当てができた。求解アルゴリズム部分は最適化ソルバーに任せることができるため、条件式を追加するだけで済みました。
今回定式化に使用した Amplify SDK は、さまざまな分野で活用されています。その中には、今回のような割り当ての最適化 (シフト最適化や生産計画最適化など) も含まれます。導入のハードルも低く、Python で簡単に定式化できるので、組合せ最適化に興味のある方は、ぜひ Amplify SDK を試してみてください。
Discussion