Description: hospitals-residents problem with ties problem solved with ampl and highs
Description
The assignment problem is one of the most relevant problems in Operations Research. The Hospitals-Residents Problem (HR) and its variants is a particular case of the assignment problem, that focuses on the lists of preferences of the agents involved in the problem, and finding a stable matching between the agents.
In the HR Problem there are two different sets of agents: residents, who are applying to hospitals, and the hospitals which have to decide which residents to accept, and this decision is not arbitrary, each resident has a ranked list of the hospitals he prefers the most, and each hospital has a ranked list of the residents they like the most. The problem consists in finding a stable matching that is fair, in the sense that any resident and hospital that are not paired, would not prefer to be paired to each other.
It is a one-to-many assignment, as each hospital $j$ is assumed to have a quote of $Q_j$ residents, so it can match simultaneously to $Q_j$ residents, while each resident is matching one hospital at most.
Variants and complexity
The case where each hospital has $q_j=1$ is called the Stable Marriage Problem (D. Gale and L. S. Shapley, 1962), that is a one-to-one assignment problem with lists of preferences. If the lists do not contain ties, there exist greedy algorithms to solve the problem by finding the matching (Gale-Shapley algorithm).
When there are ties (a resident ranks in the same position more than one hospital, or a hospital ranks the same more than one resident), the problem is called Hospitals-Residents Problem with Ties (HRT), and in that case, the matching is not necessarily unique. Finding the maximum size matching in a HRT instance is called MAX-HRT, and is NP-hard (Manlove et al., 2002).
There are still extensions to the Gale-Shapley algorithm to find stable matchings within an instance, but not necessarily maximal.
In this notebook we are presenting a Mixed-Integer Programming solution for the HRT problem implemented by using AMPL.
MIP model
First we should formalize the notion of stable matching. If $r$ is a resident and $h$ a hospital, then $(r,h)$ will be an acceptable pair if $r$ is ranked by $h$ and viceversa (so it would make sense to assign $r$ to the hospital $h$).
We could think about a matching within the bipartite graph between the residents and the hospitals, as the subset of edges in the graph that determine the assignment. Then, a blocking pair $(r, h)$ is an acceptable pair within that matching that satisfies any of the following conditions:
$r$ and $h$ are not paired in the match, and $h$ has been assigned to less than $q_j$ residents (so they could be paired to make the matching more stable).
$r$ is not paired or it is paired to a hospital $h’$ worse ranked than $h$ inside the list of hospitals of $r$; and there exists $r’$ assigned to $h$ such that $r’$ is worse ranked than $r$ within the list of residents of $h$. In that case, it would be better to match $r$ and $h$ instead.
$h$ is not full or exists a resident $r’$ worse ranked than $r$ by $h$ list; and the pair of $r$ in the matching is worse wanked than $h$ by $r$. It would be better to match $r$ and $h$ instead.
With this definition, a stable matching is a matching that does not contain any blocking pair.
Sets:
R: set of residents
H: set of hospitals
Parameters:
In order to simplify the notation, we assume that lists of preferences are a matrices where the preference of each hospital/resident is ranked by their position in the list. For example, if Rose is applying to 3 hospitals and her preferences are:
meaning that her favourite hospital is H2, and she ranks the same H1 and H3. In this case, Rose’s list of preference would be:
And consequently the notation will be prefR{Rose,H1} = 2, prefR{Rose,H2} = 1, and prefR{Rose,H3} = 2, so the lower the preference the better ranked.
(more) Parameters:
prefR {R,H}: resident’s lists of preferences ranking hospitals
prefH {H,R}: hospital’s lists of preferences ranking residents
In order to model the stability we are going to introduce more sets that will be used in the model
{hh in H : prefR[r,hh] <= prefR[r,h]};
{rr in R : prefH[h,rr] <= prefH[h,r]}
$$\max \sum \limits_{(r, h) \in R \times H} x[r,h]$$
Each resident $r$ is matched to 1 hospital or is not matched:
$$\sum \limits_{h \in H} x[r,h] \leq 1$$
Each hospital $h$ does not allow more residents than its quote:
$$\sum \limits_{r \in R} x[r,h] \leq Q[j]$$
Stability conditions to ensure that there are no blocking pairs in the matching. For each acceptable pair $(r,h)$:
$$Q[h] \sum \limits_{h’ \in lesseq_H{H,R}} x[r,h’] + \sum \limits_{r’ \in lesseq_R{R,H}} x[r’,h] \geq Q[h]$$
If $r$ and $h$ are paired, the constraint is satisfied trivially. They are a blocking pair if and only if the first sum is going to be zero (so $r$ could have been matched to $h$) and the second must be less than $Q_j$ (so $h$ has enough quote to match with $r$). Otherwise the first sum must be 1 so $r$ is matched with a better hospital and the pair would be not blocking, or the first sum is $Q_j$ so $h$ is matched with $Q_j$ better residents than $r$. Notice that there is a quadratic number of stability constraints, and might be hard to deal with them. There are MIP formulations that try to solve this inconvenient.
Note: in AMPL we set the default preference to -1, in order to determine the acceptable pairs that should not be computed in the sum, as the variables $x$ make sense only if the resident and the hospital are an acceptable pair.
HiGHS 1.2.2: HiGHS 1.2.2: optimal solution; objective 7
0 branching nodes
x [*,*]
# $3 = 'Melbourne Medical Center'
: 'Hosp. East Boston' 'Madrid 12 Oct' $3 'Porto Hosp' :=
Bob 1 0 0 0
Christian 0 0 0 1
Gleb 0 1 0 0
Martin 1 0 0 0
Meg 0 0 0 1
Melinh 0 0 1 0
Nicolau 0 1 0 0
;
Christian is assigned to Porto Hosp
Meg is assigned to Porto Hosp
Nicolau is assigned to Madrid 12 Oct
Gleb is assigned to Madrid 12 Oct
Bob is assigned to Hosp. East Boston
Martin is assigned to Hosp. East Boston
Melinh is assigned to Melbourne Medical Center
Solution
Finally show the matching by using the AMPL API and the Networkx library