Optimization Online


Mathematical models for stable matching problems with ties and incomplete lists

Maxence Delorme (mdelorme***at***ed.ac.uk)
Sergio García (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: 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 solve all 22 instances within a mean runtime of 60 seconds. 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 the HRT case. For the real instances, we reduce the mean runtime from an average of 144 seconds when using state-of-the-art methods, to 3 seconds when using our new ILP-based algorithms. We also show that our models outperform considerably state-of-the-art models on larger randomly-generated instances of SMTI and HRT.

Keywords: Assignment, Stable Marriage problem, Hospitals / Residents problem, Ties and Incomplete lists, Exact algorithms.

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Citation: Technical report "ERGO-18-024", ERGO, University of Edinburgh, United Kingdom, October 2018.

Download: [PDF]

Entry Submitted: 10/05/2018
Entry Accepted: 10/05/2018
Entry Last Modified: 03/17/2019

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