An Integer Programming Approach to the Hospitals/Residents Problem with Ties

Augustine Kwanashie () and David F. Manlove ()
Additional contact information
Augustine Kwanashie: University of Glasgow
David F. Manlove: University of Glasgow

A chapter in Operations Research Proceedings 2013, 2014, pp 263-269 from Springer

Abstract: Abstract The classical Hospitals/Residents problem (HR) models the assignment of junior doctors to hospitals based on their preferences over one another. In an instance of this problem, a stable matching $$M$$ M is sought which ensures that no blocking pair can exist in which a resident $$r$$ r and hospital $$h$$ h can improve relative to $$M$$ M by becoming assigned to each other. Such a situation is undesirable as it could naturally lead to $$r$$ r and $$h$$ h forming a private arrangement outside of the matching. The original HR model assumes that preference lists are strictly ordered. However in practice, this may be an unreasonable assumption: an agent may find two or more agents equally acceptable, giving rise to ties in its preference list. We thus obtain the Hospitals/Residents problem with Ties (HRT). In such an instance, stable matchings may have different sizes and MAX HRT, the problem of finding a maximum cardinality stable matching, is NP-hard. In this paper we describe an Integer Programming (IP) model for MAX HRT. We also provide some details on the implementation of the model. Finally we present results obtained from an empirical evaluation of the IP model based on real-world and randomly generated problem instances.

Keywords: Stable Matching; Hospitals/Residents Problem (HR); Blocking Pair; Preference List; Maximum Cardinality Stable Matching (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (17)

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_36

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

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

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 ().