An n-ary Constraint for the Stable Marriage Problem
This work addresses a computational efficiency problem for constraint programming researchers, though it appears incremental as it builds on prior encodings.
The paper tackles the stable marriage problem by introducing an n-ary constraint that enforces stability and prevents bigamy, resulting in optimal O(n^2) complexity for arc-consistency and showing significantly faster and more space-efficient performance compared to existing encodings.
We present an n-ary constraint for the stable marriage problem. This constraint acts between two sets of integer variables where the domains of those variables represent preferences. Our constraint enforces stability and disallows bigamy. For a stable marriage instance with $n$ men and $n$ women we require only one of these constraints, and the complexity of enforcing arc-consistency is $O(n^2)$ which is optimal in the size of input. Our computational studies show that our n-ary constraint is significantly faster and more space efficient than the encodings presented in \cite{cp01}. We also introduce a new problem to the constraint community, the sex-equal stable marriage problem.