中学校の委員分け（NetworkX版）

問題

生徒の希望を元に「クラスの委員を割り当てる問題」をマッチング問題として解きます。

参考

• 元記事「中学校の委員分けを最小費用流で最適化してみた話」：最小費用流問題として求解
• 前記事「中学校の委員分け」：混合整数最適化として求解

方針

今回は、マッチング問題として解きます。
そのためには、委員の必要数がn人のときに、その委員のノードをn個に増やす必要があります。
また、最大重み最大マッチング問題にするので、重みwを「40 - w」に変換します。

解いてみよう

import networkx as nx

lst = [['タプリス', '風紀委員', 10], ['青葉', '学級代表', 10], ['かぐや', '風紀委員', 10],
       ['チノ', '学級代表', 10], ['ミラ', '風紀委員', 10],
       ['タプリス', '学級代表', 30], ['青葉', '図書委員', 30], ['かぐや', '図書委員', 30],
       ['チノ', '風紀委員', 30], ['ミラ', '学級代表', 30]]
need = {"学級代表": 1, "図書委員": 2, "風紀委員": 2}
g = nx.Graph()
lst2 = [(s, f'{c}{i}', 40 - w) for s, c, w in lst for i in range(need[c])]
g.add_weighted_edges_from(lst2)
print(nx.max_weight_matching(g, maxcardinality=True))

出力

{('かぐや', '図書委員1'),
 ('チノ', '学級代表0'),
 ('図書委員0', '青葉'),
 ('風紀委員0', 'ミラ'),
 ('風紀委員1', 'タプリス')}

元記事や前記事と同じ解が出ました。

補足

マッチングは社会の色々なところで使われます。たとえば、下記のマッチングを研究している先生のサイトに紹介されています（今回利用した重みマッチングではなく安定マッチングですが）。

参考：https://www.nii.ac.jp/faculty/informatics/yokoi_yu/

今回、networkx.max_weight_matching（エドモンズ法）で解きましたが、現実問題を解くときは、数理最適化モデルの方が柔軟にモデルを作成できますし、高速に計算できるでしょう。