We present new theory, heuristics and algorithms for preprocessing instances of the Stable Marriage with Ties and Incomplete lists (SMTI), the Hospitals/Residents with Ties (HRT), and the Worker-Firms with Ties (WFT) problems. We show that instances of these problems can be preprocessed by removing from the preference lists of some agents entries that correspond to pairs that will not occur in any stable matching. 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 in the literature to describe when preference list entries can be removed from instances of WFT, 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 maximum weight stable matching in real-world instances compared to existing preprocessing techniques, or 80% compared to not using preprocessing. We also show that preprocessing can be useful across a wide range of instance parameters, depending mostly on the lengths of preferences of the agents.
Citation
Under review with Computers and Operations Research (submitted 2020-02-08). University of Glasgow.
Article
View Improving solve times of stable matching problems through preprocessing