A constraint programming approach to the hospitals/residents problem

Manlove, D.F.;O'Malley, G.;Prosser, P.;Unsworth, C.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • Manlove, D.F.
    Author
  • O'Malley, G.
    Author
  • Prosser, P.
    Author
  • Unsworth, C.
    Author
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. We provide additional motivation for our models by indicating how side constraints can be added easily in order to solve hard variants of HR.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Manlove, D. F., O’Malley, G., Prosser, P., & Unsworth, C. (2007). A constraint programming approach to the hospitals/residents problem. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 155-170). Springer-verlag. https://hdl.handle.net/2078.5/218810