Combinatorial optimization-Typical problem-Stable matching problem

Typical problem and execution method

Stable matching problem

Given a group of men and a group of women, men have a preference order for women and women have a preference order for men. Matching in which no blocking pair exists when a pair is made by a man and a woman is called stable matching. A blocking pair (m, w) is a pair of unpaired men and women in a state where "w is preferable to the current pair of m" and "m is preferable to the current pair of w".

[Stable matching problem](https://ja.wikipedia.org/wiki/%E5%AE%89%E5%AE%9A%E7%B5%90%E5%A9%9A%E5%95%8F%E9 % A1% 8C) is not strictly an optimization problem, but it is included in the typical problem because it is an important problem related to matching. It can be solved efficiently by Gail Shapley's solution.

Execution method

usage

Signature: stable_matching(prefm, preff)
Docstring:
Stable matching problem
input
    prefm, preff:Preference
output
matching

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]]))

result

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

python

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

data

• data/stable.csv