UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 7941
DCS Tech Report Number: TR-2005-196

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

Publication Type: Tech Report (internal)
Appeared in: DCS Tech Report
Page Numbers :
Publisher: N/A
Year: 2005
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.


PDF Bibtex entry Endnote XML