Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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 : Friday, April 29, 2022 - 10:12:49 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⟩



Record views


Files downloads