UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 7924
DCS Tech Report Number: TR-2005-192

Modelling and solving the stable marriage problem using constraint programming
Manlove,D.F. O'Malley,G.

Publication Type: Tech Report (internal)
Appeared in: DCS Tech Report
Page Numbers :
Publisher: N/A
Year: 2005
Abstract:

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 [6], establishing a greater level of structure.


PDF Bibtex entry Endnote XML