組合せ最適化 - 典型問題 - 安定マッチング問題

典型問題と実行方法

##安定マッチング問題

男性のグループと女性のグループが与えられ、男性は女性の選好順序を、女性は男性の選好順序を持っている。男女でペアを作ったときブロッキングペアが存在しないマッチングを安定マッチングという。
ブロッキングペア(m,w)とは、ペアとなっていない男女で「wはmの現在のペアよりも好ましい」「mはwの現在のペア よりも好ましい」状態のペアをいう。

安定マッチング問題は、厳密には最適化問題ではないが、マッチングに関し重要な問題なので典型問題に含めている。ゲイル・シャプレーの解法により効率的に解くことができる。

##実行方法

usage

Signature: stable_matching(prefm, preff)
Docstring:
安定マッチング問題
入力
    prefm, preff: 選好
出力
    マッチング

python

from ortoolpy import stable_matching
print(stable_matching([[2,0,1],[2,1,0],[0,2,1]], [[0,1,2],[2,0,1],[2,1,0]]))

結果

{2: 2, 0: 0, 1: 1}

python

# pandas.DataFrame
from ortoolpy.optimization import StableMatching
StableMatching('data/stable.csv')

	male	female	pref_male	pref_female
0	0	0	1	0
4	1	1	1	2
8	2	2	1	0

##データ

• data/stable.csv