Optimization Online


Stability in the the Hospitals / Residents problem with Couples and Ties: Mathematical models and computational studies

Maxence Delorme(mdelorme***at***ed.qc.uk)
Sergio Garcia(sergio.garcia-quiles***at***ed.ac.uk)
Jacek Gondzio(j.gondzio***at***ed.ac.uk)
Joerg Kalcsics(joerg.kalcsics***at***ed.ac.uk)
David Manlove(david.manlove***at***glasgow.ac.uk)
William Pettersson(william.pettersson***at***glasgow.ac.uk)

Abstract: In the well-known Hospitals/Residents problem (HR), the objective is to find a stable matching of doctors (or residents) to hospitals based on their preference lists. In this paper, we study HRCT, the extension of HR in which doctors are allowed to apply in couples, and in which doctors and hospitals can include ties in their preference lists. We first review three stability definitions that have been proposed in the literature for HRC (the restriction of HRCT where ties are not allowed) and we extend them to HRCT. We show that such extensions might bring some unwanted behaviour and we introduce a new stability definition specifically designed for HRCT. We then introduce unified Integer Linear Programming (ILP) models for each stability definition, where only minor changes are required to switch from one definition to the other. We propose some improvements to decrease the average solution time of each ILP model based on preprocessing, dummy variables, and valid inequalities. We show that these improvements reduce the solution time of the models by several orders of magnitude. In addition, we also show that the stability criterion chosen has a minor impact on the solution quality (average matching size) and time required to obtain the solution, but for a specific set of instances, stable matchings are significantly less likely to exist for one particular criterion compared to the other criteria. We also provide meaningful insights about how certain parameters such as the tie density, the number of couples, and the difference between the number of positions available in the hospitals and the number of doctors, might affect the average matching size.

Keywords: Hospitals / Residents problem with Couples, Ties and incomplete lists, Stable matching, Exact algorithms.

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization

Category 3: Integer Programming

Citation: Research report ERGO-20-003, The University of Edinburgh, 2020 (submitted for publication)

Download: [PDF]

Entry Submitted: 03/26/2020
Entry Accepted: 03/26/2020
Entry Last Modified: 03/26/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society