中学校の委員分け

これなに

生徒の希望を元に「クラスの委員を割り当てる問題」を組合せ最適化で解きます。
中学校の委員分けを最小費用流で最適化してみた話のPython版です。

方針

• 生徒の委員の希望を1レコードとしたpandas.DataFrameを作成します。
  • 第1希望のコストを10、第2希望のコストを30とします。
• DataFrameを使って数理最適化モデル（コスト最小化）を作成します。
• 数理最適化モデルをソルバーで解いて割り当てを出します。

数理最適化モデル

• 変数：DataFrameの列として作成（1行1変数）。
• 目的関数：希望コストの総和最小化
• 制約条件
  • 生徒がなれる委員は1つまで
  • 委員は定数を満たす

入力

DataFrameを作成します。

import pandas as pd
from pulp import lpDot, lpSum
from ortoolpy import model_min, addbinvars, addvals

lst = [['タプリス', '風紀委員', 10], ['青葉', '学級代表', 10], ['かぐや', '風紀委員', 10],
       ['チノ', '学級代表', 10], ['ミラ', '風紀委員', 10],
       ['タプリス', '学級代表', 30], ['青葉', '図書委員', 30], ['かぐや', '図書委員', 30],
       ['チノ', '風紀委員', 30], ['ミラ', '学級代表', 30]]
need = {"学級代表": 1, "図書委員": 2, "風紀委員": 2}
df = pd.DataFrame(lst, columns=['Name', 'Committee', 'Cost'])
addbinvars(df)

print(df)

	Name	Committee	Cost	Var
0	タプリス	風紀委員	10	v000001
1	青葉	学級代表	10	v000002
2	かぐや	風紀委員	10	v000003
3	チノ	学級代表	10	v000004
4	ミラ	風紀委員	10	v000005
5	タプリス	学級代表	30	v000006
6	青葉	図書委員	30	v000007
7	かぐや	図書委員	30	v000008
8	チノ	風紀委員	30	v000009
9	ミラ	学級代表	30	v000010

Var列が変数（1:割り当てる、0:割り当てない）

モデル作成と求解

m = model_min()
m += lpDot(df.Cost, df.Var)  # 希望コストの総和
for _, gr in df.groupby('Name'):
    m += lpSum(gr.Var) <= 1  # 生徒がなれる委員は1つまで
for k, gr in df.groupby('Committee'):
    m += lpSum(gr.Var) == need[k]  # 委員は定数を満たす
m.solve()
addvals(df)

結果

print(df[df.Val > 0])

	Name	Committee	Cost	Var	Val
0	タプリス	風紀委員	10	v000001	1
3	チノ	学級代表	10	v000004	1
4	ミラ	風紀委員	10	v000005	1
6	青葉	図書委員	30	v000007	1
7	かぐや	図書委員	30	v000008	1

補足

元記事では最小費用流問題にしてます。その場合、NetworkXのmin_cost_flowが使えます。

ただし、モデルを改造するのであれば、本記事のように数理最適化モデルの方が対応しやすいでしょう。数理最適化の計算時間も十分速いです。