Try to solve the internship assignment problem with Python

Introduction

In 1962, D. Gale and L. S. Shapley raised the issue of stable marriage. Chaprey won the Nobel Prize in Economics in 2012 for this series of achievements.

The stable marriage problem is as follows. (From Wikipedia)

An example of a stable marriage problem consists of N men and N women, and each individual's wish list. The wish list is a list of all the opposite sexes arranged in total order based on each individual's preference. The solution to the stable marriage problem is stable matching. For the example of the stable marriage problem A pair that you like more than the other person you are currently pairing with (hereinafter referred to as a blocking pair) Matching that does not exist is called stable matching.

The stable marriage problem is a type of stable matching problem, and the stable matching problem is widely used, such as assigning residents to hospitals and university students to laboratories. Resident assignment has been used in the United States since around 1950, and has recently begun to be used in Japan.

Stable matching problems can be solved with stable_matching in Python's ortoolpy (http://qiita.com/Tsutomu-KKE@github/items/2ec5f7626054f4b4de63) can do. Let's try it out.

Solve with Python

Stable_matching of ortoolpy can only be solved if the number of residents and assignees is the same. Here, if the acceptable number of assignment destination A is 2, let's create a dummy of the assignment destination such as assignment destination A_0 and assignment destination A_1 and match them. We define a method stable_matching2 that solves such an extended stable matching problem.

python3


from itertools import accumulate
from ortoolpy import stable_matching
def stable_matching2(prefs, prefl, capa):
    """
Asymmetric matching
    prefs:Residents' preferences for their assignment
    prefl:Preference for residents(All assignments have the same preference)
    capa:Acceptable number of assignees
    """
    acca = list(accumulate([0] + capa[:-1])) #Cumulative acceptable number
    idx = [i for i, j in enumerate(capa) for _ in range(j)] #Dummy assignment destination → assignment destination conversion list
    prefs = [[j+acca[i] for i in pr for j in range(capa[i])] for pr in prefs] #Dummy selection
    res = stable_matching([prefl] * len(prefl), prefs)
    return{k:idx[v] for k, v in res.items()} #Return the dummy to the original

Create a question at random.

python3


lab_capa = [2, 3, 3, 2] #Acceptable number of assignees
ns, nl = sum(lab_capa), len(lab_capa) #Number of residents and assignments

import numpy as np
np.random.seed(1)
def shuffled(n):
    """0..n-Shuffle and return 1"""
    a = np.arange(n)
    np.random.shuffle(a)
    return a.tolist()
performance = shuffled(ns) #Preference for residents
preferences = [shuffled(nl) for i in range(ns)] #Preference for assignment

print(performance)
print(preferences)
>>>
[2, 9, 6, 4, 0, 3, 1, 7, 8, 5]
[[2, 0, 1, 3], [3, 0, 1, 2], [3, 1, 2, 0], [3, 1, 0, 2], [1, 3, 2, 0],
 [3, 0, 2, 1], [3, 2, 1, 0], [1, 0, 2, 3], [0, 3, 1, 2], [2, 0, 3, 1]]

Solve and display the result.

python3


res = stable_matching2(preferences, performance, lab_capa)
for k, v in res.items():
    print('medical intern%d ->Assigned to%d'%(k,v))
>>>
Resident 0->Assigned to 2
Resident 1->Assigned to 0
Resident 2->Assigned to 3
Resident 3->Assigned to 1
Resident 4->Assigned to 1
Resident 5->Assigned to 2
Resident 6->Assigned to 3
Resident 7->Assigned to 1
Resident 8->Assigned to 0
Resident 9->Assigned to 2

Relationship with combinatorial optimization

The stable matching problem is a problem that seeks matching without blocking pairs, and what we care about is the relative value of preference order. If the preference is an absolute value in the first place, it becomes a weight matching problem of the combinatorial optimization problem.

The absolute value is, for example, the commuting time from the trainee's home to the place of assignment. At this time, the problem of minimizing the total commuting time of all residents is a weight matching problem, which can be solved by the Edmonds method or the like.

The solution of the weight matching problem is stable matching, but the solution of the stable matching problem is not always the optimal solution of the weight matching problem.

After all, it looks like this:

You can think of probable weights → Weight matching problem The exact weight is unknown, but the order is known → Stable matching problem

reference Learn about romance while solving Haskell programming while solving stable marriage problems that's all

Recommended Posts