Solving the Kirkman's schoolgirl problem in a few seconds - ENAC - École nationale de l'aviation civile Accéder directement au contenu
Communication Dans Un Congrès Lecture Notes in Computer Science Année : 2002

Solving the Kirkman's schoolgirl problem in a few seconds

Résumé

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.
Fichier principal
Vignette du fichier
290.pdf (152.27 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00938024 , version 1 (17-04-2014)

Identifiants

Citer

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⟩
137 Consultations
1780 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More