Mathematical models for stable matching problems with ties and incomplete lists

Maxence Delorme*, Sergio García, Jacek Gondzio, Jörg Kalcsics, David Manlove, William Pettersson

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

8 Citations (Scopus)

Abstract

We present new integer linear programming (ILP) models for NP-hard optimisation problems in instances of the Stable Marriage problem with Ties and Incomplete lists (SMTI) and its many-to-one generalisation, the Hospitals/Residents problem with Ties (HRT). These models can be used to efficiently solve these optimisation problems when applied to (i) instances derived from real-world applications, and (ii) larger instances that are randomly-generated. In the case of SMTI, we consider instances arising from the pairing of children with adoptive families, where preferences are obtained from a quality measure of each possible pairing of child to family. In this case, we seek a maximum weight stable matching. We present new algorithms for preprocessing instances of SMTI with ties on both sides, as well as new ILP models. Algorithms based on existing state-of-the-art models only solve 6 of our 22 real-world instances within an hour per instance, and our new models incorporating dummy variables and constraint merging, together with preprocessing and a warm start, solve all 22 instances within a mean runtime of a minute. For HRT, we consider instances derived from the problem of assigning junior doctors to foundation posts in Scottish hospitals. Here, we seek a maximum size stable matching. We show how to extend our models for SMTI to HRT and reduce the average running time for real-world HRT instances by two orders of magnitude. We also show that our models outperform by a wide margin all known state-of-the-art models on larger randomly-generated instances of SMTI and HRT.

Original languageEnglish
Pages (from-to)426-441
Number of pages16
JournalEuropean Journal of Operational Research
Volume277
Issue number2
DOIs
Publication statusPublished - 1 Sep 2019
Externally publishedYes

Keywords

  • Assignment
  • Exact algorithms
  • Hospitals/Residents problem
  • Stable Marriage problem
  • Ties and Incomplete lists

Fingerprint Dive into the research topics of 'Mathematical models for stable matching problems with ties and incomplete lists'. Together they form a unique fingerprint.

Cite this