<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>8067</REFNUM><AUTHORS><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>O'Malley,G.</AUTHOR><AUTHOR>Prosser,P.</AUTHOR><AUTHOR>Unsworth,C.</AUTHOR></AUTHORS><YEAR>2005</YEAR><TITLE>A Constraint Programming Approach to the Hospitals / Residents Problem</TITLE><PLACE_PUBLISHED>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)</PLACE_PUBLISHED><PUBLISHER>N/A</PUBLISHER><PAGES>28-43</PAGES><LABEL>Manlove:2005:8067</LABEL><ABSTRACT>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.</ABSTRACT></RECORD></RECORDS></XML>