HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

L' élargissement aléatoire progressif

Résumé : Nous présentons un algorithme qui permet de résoudre efficacement les problèmes de complétion de quasi-groupes. Il se greffe sur un algorithme de Forward- Checking. Il élargit progressivement le nombre de valeurs à explorer. Pour un nombre donné de valeurs à explorer, et pour chaque variable, il choisit aléatoirement entre le nombre de valeurs à explorer et ce nombre moins un. La probabilité de choisir le nombre de valeurs à explorer est elle aussi augmentée progressivement. Sur 9900 problèmes de complétion de quasi-groupes d'ordre 20 et pour une bonne heuristique d'ordonnancement des valeurs utilisant une modélisation duale, notre algorithme donne de meilleurs résultats que le Forward-Checking, que les recommencements rapides aléatoires (Rapid Randomized Restarts), que l'élargissement itératif (Iterative Broadening) et que la recherche avec déviations limitées (Limited Discrepancy Search).
Document type :
Conference papers
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151220
Contributor : Sylvain Soliman Connect in order to contact the contributor
Submitted on : Friday, June 1, 2007 - 6:13:01 PM
Last modification on : Wednesday, April 28, 2021 - 6:44:21 PM
Long-term archiving on: : Thursday, April 8, 2010 - 5:06:30 PM

File

49.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00151220, version 1

Citation

Tristan Cazenave. L' élargissement aléatoire progressif. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France. ⟨inria-00151220⟩

Share

Metrics

Record views

62

Files downloads

49