レバレジーズ データAIブログ

インハウスデータ組織のあたまのなか

Google OR-Toolsでマッチング問題を解く

はじめに

こんにちは！レバレジーズデータ戦略室、データサイエンティストのJacobです。

今回は、以下のような問題を考えてみましょう。

  • 5000人の求職者と500社の企業があります。
  • 各企業に対して、最適な候補者10名のリストを送りたいです。
  • 企業と求職者の組み合わせに対して、0.0（マッチしない）から1.0（非常に相性が良い）までのマッチングスコアを出力するスコアリング関数（機械学習モデルなど）があるとします。

単純なアプローチは、各企業ごとに全候補者のスコアを計算し、上位10名を選ぶ方法です。しかし、この方法には「特定の優秀な候補者に推薦が集中してしまう」という欠点があります。一人の求職者が実際に応募できる社数には限りがあるため、あまりに多くの企業に一人の候補者を推薦しても、一社あたりの採用成功確率は極めて低くなってしまいます。

この問題を、制約条件下で全体のマッチングスコアを最大化する「数理最適化問題」として再定義します。例えば、「同一の候補者を提案できるのは最大X社まで」といった制約を設けることで、紹介の偏りを防ぎます。

Googleが提供する最適化ライブラリ「OR-Tools」を使用して、解決策を実装してみましょう。

実装

まず、スコアを格納する行列を定義します。ここでは説明のため、ランダムな値を使用します。

import numpy as np

NUM_USERS = 5000
NUM_COMPANIES = 500

# score_matrix[i,j] は、ユーザー i と企業 j のマッチングスコアです
score_matrix = np.random.rand(NUM_USERS, NUM_COMPANIES)

最適化モデルとその変数を初期化します。

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# boolean型変数の行列を作成します。 
# 最適化中、モデルは候補者 i と企業 j をマッチングさせる場合に 
# assignment_matrix[i,j] を True に、そうでない場合は False に設定します。
assignment_matrix = np.empty((NUM_USERS, NUM_COMPANIES), dtype=object)
for i in range(NUM_USERS):
    for j in range(NUM_COMPANIES):
        assignment_matrix[i, j] = model.new_bool_var(f"{i}_to_{j}")

前述の制約条件を設定します。

MAX_COMPANIES_PER_USER = 10
MAX_USERS_PER_COMPANY = 10

# 制約: 各ユーザーが割り当てられる企業数は最大10社まで
for user_row in assignment_matrix:
    model.add(sum(user_row) <= MAX_COMPANIES_PER_USER)

# 制約: 各企業に割り当てられるユーザー数は最大10名まで
for company_col in assignment_matrix.T:
    model.add(sum(company_col) <= MAX_USERS_PER_COMPANY)

最大化したい目的関数を定義します。

# 選択されたすべてのマッチングスコアの合計を最大化する
score = sum(score_matrix.flatten() * assignment_matrix.flatten())
model.Maximize(score)

これで準備が整いました。ソルバーを実行して結果を取得します。

solver = cp_model.CpSolver()
status = solver.solve(model)

# 解が見つかったかを確認する
assert status in [cp_model.OPTIMAL, cp_model.FEASIBLE]

# モデルの割り当て結果を解析する
solved_assignment_matrix = np.empty((NUM_USERS, NUM_COMPANIES), dtype=bool)
for i in range(NUM_USERS):
    for j in range(NUM_COMPANIES):
        was_assigned = solver.value(assignment_matrix[i, j])
        solved_assignment_matrix[i, j] = was_assigned

今回はランダムなスコアを使用したため結果自体に深い意味はありませんが、制約が守られていることも確認できます。

assert solved_assignment_matrix.sum(axis=0).max() <= MAX_USERS_PER_COMPANY
assert solved_assignment_matrix.sum(axis=1).max() <= MAX_COMPANIES_PER_USER

念の為に一社目の企業のマッチングを確認しましょう。

company_idx = 0

assigned_users = np.where(solved_assignment_matrix[:, company_idx])[0]
scores = score_matrix[assigned_users, company_idx]

print(assigned_users)
# >> [ 971 1769 2437 2540 3604 3657 3700 3886 4335 4622]

with np.printoptions(precision=3):
print(scores)
# >> [1.    0.999 0.998 0.999 1.    0.998 0.998 0.998 0.999 1.   ]

見ての通り、マッチングスコアが高い求職者が提案されます。

補足

上記は最適化問題を解くための最小限の実装ですが、実運用に向けて解決策を改善するポイントがいくつかあります。

例えば、今回の目的関数は少し単純すぎます。ある企業には非常に良いマッチングが集中し、別の企業には質の低いマッチングばかりが割り振られる可能性があります。これを避けるために、「各企業の最低スコアを最大化する（底上げする）」といった別の目的関数を検討することも可能です。

また、スコア行列に関しても考慮すべき重要な点があります。 m x n の行列は mn 個ものバイナリ決定変数が生成され、モデルの探索空間が膨大になります。その結果、データ量が増加した際に計算時間が指数関数的に増大する（スケールしない）リスクがあります。実務的には、スコアが一定のしきい値（例：0.5）を下回るような『マッチングの可能性が極めて低い組み合わせ』については、変数自体を生成しない（スパースな形式にする）ことで、計算負荷を大幅に抑えるのが現実的です。

まとめ

このブログ記事では、Google OR-Toolsを使用してマッチング問題を解決する方法を紹介しました。このライブラリを複数のプロジェクトで使用してきましたが、他にも多種多様な最適化問題に活用できると思います。興味のある方はぜひ試してみてください！

© 2025 Leverages Co., Ltd.