Improving solution times for stable matching problems through preprocessing

•Preprocessing stable matching problems reduces time to find solutions.•New theory presented to identify more preprocessing opportunities.•Preprocessing extended to HRT with two-sided ties.•New polynomial-time algorithms to detect preprocessing.•Greater than 50% runtime reduction to find largest sta...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2021-04, Vol.128, p.105128, Article 105128
Main Authors: Pettersson, William, Delorme, Maxence, García, Sergio, Gondzio, Jacek, Kalcsics, Joerg, Manlove, David
Format: Article
Language:English
Subjects:
Hospital/Residents problem
Preprocessing
Stable Marriage problem
Ties and Incomplete Lists
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•Preprocessing stable matching problems reduces time to find solutions.•New theory presented to identify more preprocessing opportunities.•Preprocessing extended to HRT with two-sided ties.•New polynomial-time algorithms to detect preprocessing.•Greater than 50% runtime reduction to find largest stable matching. We present new theory, heuristics, and algorithms for preprocessing instances of the Stable Marriage problem with Ties and Incomplete lists (SMTI) and the Hospitals/Residents problem with Ties (HRT). Instances of these problems can be preprocessed by removing from the preference lists of some agents entries such that the set of stable matchings is not affected. Removing such entries reduces the problem size, creating smaller models that can be more easily solved by integer programming (IP) solvers. The new theorems are the first to describe when preference list entries can be removed from instances of HRT when ties are present on both sides, and also extend existing results on preprocessing instances of SMTI. A number of heuristics, as well as an IP model and a graph-based algorithm, are presented to find and perform this preprocessing. Experimental results show that our new graph-based algorithm achieves a 44% reduction in the average running time to find a maximum weight stable matching in real-world instances of SMTI compared to existing preprocessing techniques, and 80% compared to not using preprocessing. We also show that, when solving MAX-HRT instances with ties on both sides, our new techniques can reduce runtimes by up to 55%.
ISSN:0305-0548
1873-765X
DOI:10.1016/j.cor.2020.105128