Solving Stable Matching Problems via Cooperative Parallel Local Search - Archive ouverte HAL Access content directly
Conference Papers Year :

Solving Stable Matching Problems via Cooperative Parallel Local Search

(1)
1

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.
Fichier principal
Vignette du fichier
ROADEF-2015.pdf (277.43 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01195525 , version 1 (07-09-2015)

Identifiers

  • HAL Id : hal-01195525 , version 1

Cite

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⟩

Collections

UNIV-PARIS1 CRI
81 View
110 Download

Share

Gmail Facebook Twitter LinkedIn More