Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Solving the Kirkman's schoolgirl problem in a few seconds

Nicolas Barnier 1 Pascal Brisset 2
1 MAIA-OPTIM - ENAC Equipe MAIAA-OPTIM
MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
Abstract : The Social Golfer Problem has been extensively used by the constraint community in recent years as an example of a highly symmetric problem. It is an excellent problem for benchmarking symmetry breaking mechanisms such as SBDS or SBDD and for demonstrating the importance of the choice of the right model for one problem. We address in this paper a specific instance of the Golfer Problem well known as Kirkman's Schoolgirl Problem and list a collection of techniques and tricks to find efficiently all its unique solutions. In particular, we propose SBDD+, a generic improvement over SBDD which allows a deep pruning when a symmetry is detected during the search. Our implementation of the presented techniques improves previously published results by an order of magnitude for CPU time as well as for number of backtracks. It computes the seven unique solutions of Kirkman's problem in a few seconds.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

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

https://hal-enac.archives-ouvertes.fr/hal-00938024
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : jeudi 17 avril 2014 - 15:58:08
Dernière modification le : mardi 19 octobre 2021 - 11:02:56
Archivage à long terme le : : dimanche 9 avril 2017 - 02:19:59

Fichier

290.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Nicolas Barnier, Pascal Brisset. Solving the Kirkman's schoolgirl problem in a few seconds. CP 2002, 8th International Conference on Principles and Practice of Constraint Programming, Sep 2002, Ithaca, United States. pp 33-41, ⟨10.1007/3-540-46135-3⟩. ⟨hal-00938024⟩

Partager

Métriques

Consultations de la notice

111

Téléchargements de fichiers

1438