Paper ID: 7981
Modelling and solving the stable marriage problem using constraint programming
Proceedings of the Fifth Workshop on Modelling and Solving Problems with Constraints, held at the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)
Page Numbers : 10-17
We study the Stable Marriage problem (SM), which is a combinatorial problem that arises in many practical applications. We present two new models of an instance I of SM with n men and n women as an instance J of a Constraint Satisfaction Problem. We prove that establishing arc consistency in J yields the same structure as given by the established Extended Gale/Shapley algorithm for SM as applied to I. Consequently, a solution (stable matching) of I can be derived without search. Furthermore we show that, in both encodings, all stable matchings in I may be enumerated in a failure-free manner. Our first encoding is of O(n^3) complexity and is very natural, whilst our second model, of O(n^2) complexity (which is optimal), is a development of the Boolean encoding in , establishing a greater level of structure.