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.
Type de document :
Communication dans un congrès
16ème conférence ROADEF Société Française de Recherche Opérationnelle et Aide à la Décision, Feb 2015, Marseille, France
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal-paris1.archives-ouvertes.fr/hal-01195525
Contributeur : Danny Munera <>
Soumis le : lundi 7 septembre 2015 - 20:59:05
Dernière modification le : mercredi 9 septembre 2015 - 01:04:16
Document(s) archivé(s) le : mercredi 26 avril 2017 - 15:54:14

Fichier

ROADEF-2015.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

77

Téléchargements de fichiers

86