aiqbench analysis
This paper provides an empirical benchmark of optimization solvers—ASP, SAT, ILP, and CP—for the Stable Marriage problem with ties and incomplete preferences, a combinatorial challenge relevant to resource allocation and matching systems in AI applications. While the core mathematical formulation is classical, the comparative analysis of these computational methods offers direct insights for researchers developing algorithms for complex matching tasks within machine learning pipelines or constraint satisfaction frameworks.
Stable Marriage Problems with Ties and Incomplete Preferences: An Empirical Comparison of ASP, SAT, ILP, CP, and Local Search Methods
arXiv:2108.05165v3 Announce Type: replace Abstract: 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.
Abstract: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.
Artificial Intelligence (cs.AI)
arXiv:2108.05165 [cs.AI]
(or arXiv:2108.05165v3 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2108.05165 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 189 words
