M. Delorme, S. Garcia, J. Gondzio, J. Kalcsics, D. Manlove, and W. Pettersson
Abstract
In the well-known Hospitals/Residents problem (HR), the objective
is to find a stable matching of doctors (or residents) to hospitals
based on their preference lists. In this paper, we study HRCT,
the extension of HR in which doctors are allowed to apply in couples,
and in which doctors and hospitals can include ties in their preference
lists. We first review three stability definitions that have been
proposed in the literature for HRC (the restriction of HRCT where
ties are not allowed) and we extend them to HRCT. We show that such
extensions might bring some unwanted behaviour and we introduce a new
stability definition specifically designed for HRCT. We then introduce
unified Integer Linear Programming (ILP) models for each stability
definition, where only minor changes are required to switch from one
definition to the other. We propose some improvements to decrease
the average solution time of each ILP model based on preprocessing,
dummy variables, and valid inequalities. We show that these improvements
reduce the solution time of the models by several orders of magnitude.
In addition, we also show that the stability criterion chosen has
a minor impact on the solution quality (average matching size) and
time required to obtain the solution, but for a specific set of instances,
stable matchings are significantly less likely to exist for one
particular criterion compared to the other criteria. We also provide
meaningful insights about how certain parameters such as the tie
density, the number of couples, and the difference between the number
of positions available in the hospitals and the number of doctors,
might affect the average matching size.
Key words: Hospitals / Residents problem with Couples, Ties and incomplete lists, Stable matching, Exact algorithms.