<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>8551</REFNUM><AUTHORS><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>O'Malley,G.</AUTHOR><AUTHOR>Prosser,P.</AUTHOR><AUTHOR>Unsworth,C.</AUTHOR></AUTHORS><YEAR>2007</YEAR><TITLE>A Constraint Programming Approach to the Hospitals / Residents Problem</TITLE><PLACE_PUBLISHED>Proceedings of CP-AI-OR '07: the Fourth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, volume 4510 of Lecture Notes in Computer Science</PLACE_PUBLISHED><PUBLISHER>Springer</PUBLISHER><PAGES>155-170</PAGES><LABEL>Manlove:2007:8551</LABEL><KEYWORDS><KEYWORD>Stable matching; constraint satisfaction problem; specialised constraints; arc consistency; GS-lists</KEYWORD></KEYWORDS<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 <i>stable matching</i>, 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. We provide additional motivation for our models by indicating how side constraints can be added easily in order to solve hard variants of HR.</ABSTRACT><URL>http://dx.doi.org/10.1007/978-3-540-72397-4_12</URL></RECORD></RECORDS></XML>