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 metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-paris1.archives-ouvertes.fr/hal-01195525
Contributor : Danny Munera <>
Submitted on : Monday, September 7, 2015 - 8:59:05 PM
Last modification on : Wednesday, September 9, 2015 - 1:04:16 AM
Long-term archiving on : Wednesday, April 26, 2017 - 3:54:14 PM

File

ROADEF-2015.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01195525, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

90

Files downloads

106