Skip to Main content Skip to Navigation
Conference papers

Solving Stable Matching Problems via Cooperative Parallel Local Search

Abstract : Stable matching problems and its variants have several practical applications, like the Hospital/Residents problem, stable roommates problem or bipartite market sharing. An important generalization problem is the SMTI which allows for incompleteness and ties in the user's preference lists. Finding a maximal size stable matching for SMTI is compu-tationally difficult. We developed a Local Search method to solve SMTI using the Adaptive Search algorithm and present experimental evidence that this approach is much more efficient than state-of-the-art exact and approximate methods (in terms of both computational effort required and quality of solution). We also tried a parallel version of our algorithm. For this we reused the Cooperative Parallel Local Search framework (CPLS) we designed. CPLS is a highly parametric framework for the execution in parallel of local search solvers allowing them to cooperate though communication. The cooperative parallel version of our local search algorithm improves performance so much that very large and hard instances can be solved quickly.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Danny Munera Connect in order to contact the contributor
Submitted on : Monday, September 7, 2015 - 8:59:05 PM
Last modification on : Tuesday, January 19, 2021 - 11:08:39 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 3:54:14 PM


Files produced by the author(s)


  • HAL Id : hal-01195525, version 1



Danny Munera. Solving Stable Matching Problems via Cooperative Parallel Local Search. 16ème conférence ROADEF Société Française de Recherche Opérationnelle et Aide à la Décision, Feb 2015, Marseille, France. ⟨hal-01195525⟩



Les métriques sont temporairement indisponibles