Stable Marriage Problems with Ties and Incomplete Preferences: An Empirical Comparison of ASP, SAT, ILP, CP, and Local Search Methods
This work addresses matching problems in domains like resource allocation, but it is incremental as it focuses on empirical comparisons of existing methods without introducing new algorithms.
The paper tackled the Stable Marriage problem with Ties and Incomplete preferences (SMTI) by empirically comparing methods like Answer Set Programming, Constraint Programming, and Integer Linear Programming across optimization variants such as Max Cardinality, Sex-Equal, and Egalitarian, with results including performance evaluations but no specific numerical improvements reported.
We study a variation of the Stable Marriage problem, where every man and every woman express their preferences as preference lists which may be incomplete and contain ties. This problem is called the Stable Marriage problem with Ties and Incomplete preferences (SMTI). We consider three optimization variants of SMTI, Max Cardinality, Sex-Equal and Egalitarian, and empirically compare the following methods to solve them: Answer Set Programming, Constraint Programming, Integer Linear Programming. For Max Cardinality, we compare these methods with Local Search methods as well. We also empirically compare Answer Set Programming with Propositional Satisfiability, for SMTI instances. This paper is under consideration for acceptance in Theory and Practice of Logic Programming (TPLP).