An Integer Programming Model for the Hospitals/Residents Problem with Couples

Iain McBride () and David F. Manlove ()
Additional contact information
Iain McBride: University of Glasgow
David F. Manlove: University of Glasgow

A chapter in Operations Research Proceedings 2013, 2014, pp 293-299 from Springer

Abstract: Abstract The Hospitals/Residents problem with Couples (hrc) is a generalisation of the classical Hospitals/Residents problem (hr) that is important in practical applications because it models the case where couples submit joint preference lists over pairs of (typically geographically close) hospitals. In this paper we give a new NP-completeness result for the problem of deciding whether a stable matching exists, in highly restricted instances of hrc. Further, we present an Integer Programming (IP) model for hrc and extend it the case where preference lists can include ties. Further, we describe an empirical study of an IP model for HRC and its extension to the case where preference lists can include ties. This model was applied to randomly generated instances and also real-world instances arising from previous matching runs of the Scottish Foundation Allocation Scheme, used to allocate junior doctors to hospitals in Scotland.

Keywords: Scottish Foundation Allocation Scheme (SFAS); Preference List; Maximum Cardinality Stable Matching; National Resident Matching Program (NRMP); Linear Preference Order (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-07001-8_40

Ordering information: This item can be ordered from
http://www.springer.com/9783319070018

DOI: 10.1007/978-3-319-07001-8_40

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().