Paper ID: 8067
A Constraint Programming Approach to the Hospitals / Residents Problem
In Proceedings of the Fourth Workshop on Modelling and Reformulating Constraint Satisfaction Problems, held at the 11th International Conference on Principles and Practice of Constraint Programming (CP 2005)
Page Numbers : 28-43
An instance I of the Hospitals / Residents problem (HR) involves a set of residents (graduating medical students) and a set of hospitals, where each hospital has a given capacity. The residents have preferences for the hospitals, as do hospitals for residents. A solution of I is a stable matching, which is an assignment of residents to hospitals that respects the capacity conditions and preference lists in a precise way. In this paper we present constraint encodings for HR that give rise to important structural properties. We also present a computational study using both randomly-generated and real-world instances. Our study suggests that Constraint Programming is indeed an applicable technology for solving this problem, in terms of both theory and practice.