採用面接の最適化(組み合わせ最適化でスケジューリング)

初めに

環境としてJupyter Notebook上を想定している。
まずスケジューリング問題と組み合わせ最適化についてまとめる

・スケジューリング問題について

スケジューリング問題とは時間やコストを制約条件に、タスクをスケジューリングしていく問題です。今回は企業の採用面接での面接官と応募者のマッチングを行いながらスケジューリングを行っていきます。

・組み合わせ最適化による面接官と応募者のマッチング

採用面接において応募者の能力を理解するためには、面接官にもある程度同じ分野の知識が必要とされるはずです。そのため今回は事前アンケートなどでそれぞれの能力が数値化されていると仮定して、組み合わせ最適化を行っていく。

扱うデータについて

➀応募者と面接官のスキルデータ(applicants_df、interviewer_df)

スキルはそれぞれ0~10の整数で仮定、スキルの内容や個数、人数はデータに依存する。
例.

	機械学習	統計	開発	人間性	その他
応or面1	1	2	3	4	5
応or面2	6	7	8	9	10
:	:	:	:	:	:

➁面接官のスケジュール(calendar_df)

事前に予定されているスケジュール(予定ありの場合1が入力されている)
日付など日程はデータに依存する。人数は➀のinterviewer_dfと揃える必要がある。
例.

	4/7 10:00	4/7 17:00	4/10 10:00	4/10 15:00	4/11 10:00	4/11 17:00
面接官1	0	0	1	0	1	0
面接官2	1	1	0	0	0	0
:	:	:	:	:	:	:

コード

最後にclassによる実装も記述しているので解説など必要ない場合は飛ばしてください。

#スキルの差を計算
gap_df = pd.DataFrame()
for k in interviewer_df.index:    
    gap_list = []
    for j in applicants_df.index:
        list = []
        list = [interviewer_df.iloc[k][i] - applicants_df.iloc[j][i]
                if interviewer_df.iloc[k][i] > applicants_df.iloc[j][i] else (interviewer_df.iloc[k][i] - applicants_df.iloc[j][i])//2 
                for i in applicants_df.columns]
        gap_list.append(quicksum(np.square(list)))
    gap_df[k] = gap_list

はじめにスキルの差をDataframeにまとめる。
面接官のスキルが応募者を上回っていた場合は単純な差ではなく1/2の値を入力する。(面接官の能力的にカバーできるはずだが、能力が高い面接官に予定が集中するのを防ぐため)

model = Model()

#x_面接官_日程_応募者
x = {}
week = calendar_df.columns
for i in interviewer_df.index:
    x[i] = {}
    for j in week:
        x[i][j] = {}
        for k in range(applicants_df.shape[0]):
            x[i][j][k] = model.addVar(vtype="B",name=f"x_{i}_{j}_{k}")
            
model.update()

#制約条件
#面接官１人の面接する人数は時間帯につき1人以下
for i in interviewer_df.index:
    for j in week:
    model.addConstr(quicksum(x[i][j][k] for k in range(applicants_df.shape[0])) <= 1)
        
#応募者に対して面接回数は１回
for k in range(applicants_df.shape[0]):
    model.addConstr(quicksum(x[i][j][k] for i in interviewer_df.index for j in week) == 1)
        
#面接官の日程calendar_dfに予定あり(==1)の場合、面接を入れないようにする
for i in interviewer_df.index:
    for j in week:
        if calendar_df.iloc[i][j] == 1:
            for k in range(applicants_df.shape[0]):
                model.addConstr(x[i][j][k] == 0)

model.setObjective(quicksum(gap_df[i][k] * x[i][j][k] for i in interviewer_df.index for j in week for k in applicants_df.index)/applicants_df.shape[0],GRB.MINIMIZE)

model.optimize()

変数、制約条件、目的関数を定義している。変数については各面接官ごとに別の辞書を定義するなどすれば見やすくなると思うが、個人的に変数の文字はは一つにまとめたい思いがあったのでこのような形になった。

schedule_df = pd.DataFrame([[[k for k in applicants_df.index if x[i][j][k].X == 1] for j in week] for i in interviewer_df.index],columns=calendar_df.columns)

日程表の出力部分、以下のようにスケジュールが得られる。

	4/7 10:00	4/7 17:00	4/10 10:00	4/10 15:00	4/11 10:00	4/11 17:00
面接官1	[応募者0]	[]	[]	[]	[応募者5]	[]
面接官2	[]	[応募者1]	[]	[応募者8]	[]	[]
:	:	:	:	:	:	:

クラスとして利用

SCO.py

import pandas as pd
import numpy as np
from gurobipy import Model, quicksum, GRB

class ScheduleOptimizetion:
    #面接官と応募者のスキルのギャップを算出
    def mk_gap_df(self, applicants_df, interviewer_df):
        gap_df = pd.DataFrame()
        for k in interviewer_df.index:    
            gap_list = []
            for j in applicants_df.index:
                list = [interviewer_df.iloc[k][i] - applicants_df.iloc[j][i] if interviewer_df.iloc[k][i] > applicants_df.iloc[j][i] else (interviewer_df.iloc[k][i] - applicants_df.iloc[j][i])//2 for i in applicants_df.columns]
                gap_list.append(quicksum(np.square(list)))
        
            gap_df[k] = gap_list
        
        return(gap_df)
    
    #最適化部分
    def solve(self, applicants_df, interviewer_df, calendar_df):
        gap_df = self.mk_gap_df(applicants_df,interviewer_df)
        model = Model()
        
        #変数定義
        #x_面接官_曜日_応募者
        x = {}
        week = calendar_df.columns
        for i in interviewer_df.index:
            x[i] = {}
            x[i]["score"] = interviewer_df.iloc[i]
            for j in week:
                x[i][j] = {}
                for k in range(applicants_df.shape[0]):
                    x[i][j][k] = model.addVar(vtype="B",name=f"x_{i}_{j}_{k}")
        
        model.update()
        
        #制約条件
        #面接官１人の面接する人数は時間帯につき1人以下
        for i in interviewer_df.index:
            for j in week:
                model.addConstr(quicksum(x[i][j][k] for k in range(applicants_df.shape[0])) <= 1)
        
        #応募者に対して面接回数は１回
        for k in range(applicants_df.shape[0]):
            model.addConstr(quicksum(x[i][j][k] for i in interviewer_df.index for j in week) == 1)
        
        #面接官の日程calendar_dfに予定あり(==1)の場合、面接を入れないようにする
        for i in interviewer_df.index:
            for j in week:
                if calendar_df.iloc[i][j] == 1:
                    for k in range(applicants_df.shape[0]):
                        model.addConstr(x[i][j][k] == 0)
        #目的関数
        model.setObjective(quicksum(gap_df[i][k] * x[i][j][k] for i in interviewer_df.index for j in week for k in applicants_df.index)/applicants_df.shape[0],GRB.MINIMIZE)
        
        #最適化
        model.optimize()
        
        #スケジュールをDataFrame化
        schedule_df = pd.DataFrame([[[k for k in applicants_df.index if x[i][j][k].X == 1] for j in week] for i in interviewer_df.index],columns=calendar_df.columns)
        
        #スケジュールを出力 目的変数の値が一定の値を超えた場合注意喚起しスケジュールを見直すことを促すよう設定
        if model.Status == 2:
            if model.ObjVal > 11:
                print("応募者とのスコアギャップが基準値を超えています。面接官の日程を調整するなど条件を緩和することを推奨します。")
                return schedule_df
            else:
                return schedule_df
            
        else:
            print("最適解が存在しません。データの見直しを行ってください。")

基本的に上のコードと同じだが出力の部分で、最適解が存在しない場合と目的関数の値が一定を超えた場合に警告を出すように改変している。
警告が出た場合面接官の事前スケジュールの見直しなどをして、制約を緩和することが推奨される。

参考

面接のマッチングのアイデアは以下の動画を参考にした。
https://www.youtube.com/watch?v=iOnLifIm3-k&list=LL&index=6