Complexity results and integer programming models for hospitals / residents problem variants

QA Mathematics;QA75 Electronic computers. Computer science;QA76 Computer software

McBride, Iain ; Manlove, David F.

University:University of Glasgow

Department:School of Computing Science

关键词: Hospitalsresidents problem, matching with couples, stable matching, hospitals residents problem with couples, integer programming, stability, teachers allocation problem;   

Others  :  http://theses.gla.ac.uk/7027/7/2015mcbridephd.pdf

来源: University of Glasgow

【 摘 要 】

The classical Hospitals / Residents problem (HR) is a many-to-one bipartite matching problem involving preferences, motivated by centralised matching schemes arising in entry level labour markets, the assignment of pupils to schools and higher education admissions schemes, among its many applications. The particular requirements of these matching schemes may lead to generalisations of HR that involve additional inputs or constraints on an acceptable solution. In this thesis we study such variants of HR from an algorithmic and integer programming viewpoint.The Hospitals / Residents problem with Couples (HRC) is a variant of 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. It is known that an instance of HRC need not admit a stable matching. We show that deciding whether an instance of HRC admits a stable matching is NP-complete even under some very severe restrictions on the lengths and the structure of the participants’ preference lists. However, we show that under certain restrictions on the lengths of the agents’ preference lists, it is possible to find a maximum cardinality stable matching or report that none exists in polynomial time.Since an instance of HRC need not admit a stable matching, it is natural to seek the ‘most stable’ matching possible, i.e., a matching that admits the minimum number of blocking pairs. We use a gap-introducing reduction to establish an inapproximability bound for the problem of finding a matching in an instance of HRC that admits the minimum number of blocking pairs. Further, we show how this result might be generalised to prove that a number of minimisation problems based on matchings having NP-complete decision versions have the same inapproximability bound. We also show that this result holds for more general minimisation problems having NP-complete decisions versions that are not based on matching problems.Further, we present a full description of the first Integer Programming (IP) model for finding a maximum cardinality stable matching or reporting that none exists in an arbitrary instance of HRC. We present empirical results showing the average size of a maximum cardinality stable matching and the percentage of instances admitting stable matching taken over a number of randomly generated instances of HRC with varying properties. We also show how this model might be generalised to the variant of HRC in which ties are allowed in either the hospitals’ or the residents’ preference lists, the Hospitals / Residents problem with Couples and Ties (HRCT). We also describe and prove the correctness of the first IP model for finding a maximum cardinality ‘most stable’ matching in an arbitrary instance of HRC. We describe empirical results showing the average number of blocking pairs admitted by a most-stable matching as well as the average size of a maximum cardinality ‘most stable’ matching taken over a number of randomly generated instances of HRC with varying properties. Further, we examine the output when the IP model for HRCT is applied to real world instances arising from the process used to assign medical graduates to Foundation Programme places in Scotland in the years 2010-2012.The Hungarian Higher Education Allocation Scheme places a number of additional constraints on the feasibility of an allocation and this gives rise to various generalisations of HR. We show how a number of these additional requirements may be modelled using IP techniques by use of an appropriate combination of IP constraints. We present IP models for HR with Stable Score Limits and Ties, HR with Paired Applications, Ties and Stable Score limits, HR with Common Quotas, Ties and Stable Score Limits and also HR with Lower Quotas, Ties and Stable Score limits that model these generalisations of HR.The Teachers’ Allocation Problem (TAP) is a variant of HR that models the allocation of trainee teachers to supervised teaching positions in Slovakia. In TAP teachers express preference lists over pairs of subjects at individual schools. It is known that deciding whether an optimal matching exists that assigns all of the trainee teachers is NP-complete for a number of restricted cases. We describe IP models for finding a maximum cardinality matching in an arbitrary TAP instance and for finding a maximum cardinality stable matching, or reporting that none exists, in a TAP instance where schools also have preferences. We show the results when applying the first model to the real data arising from the allocation of trainee teachers to schools carried out at P.J. Safarik University in Kosice in 2013.