Computing at Glasgow University
Paper ID: 8551

A Constraint Programming Approach to the Hospitals / Residents Problem
Manlove,D.F. O'Malley,G. Prosser,P. Unsworth,C.

Publication Type: Conference Proceedings
Appeared in: 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
Page Numbers : 155-170
Publisher: Springer
Year: 2007

URL: This publication is available at this URL.


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. We provide additional motivation for our models by indicating how side constraints can be added easily in order to solve hard variants of HR.

Keywords: Stable matching; constraint satisfaction problem; specialised constraints; arc consistency; GS-lists

PDF Bibtex entry Endnote XML