Adaptive Singleton-based Consistencies

Abstract : Singleton-based consistencies have been shown to dra- matically improve the performance of constraint solvers on some difficult instances. However, they are in gen- eral too expensive to be applied exhaustively during the whole search. In this paper, we focus on partition-one- AC, a singleton-based consistency which, as opposed to singleton arc consistency, is able to prune values on all variables when it performs singleton tests on one of them. We propose adaptive variants of partition-one- AC that do not necessarily run until having proved the fixpoint. The pruning can be weaker than the full ver- sion but the computational effort can be significantly reduced. Our experiments show that adaptive Partition- one-AC can obtain significant speed-ups over arc con- sistency and over the full version of partition-one-AC.
Type de document :
Communication dans un congrès
AAAI Conference on Artificial Intelligence, Jul 2014, Québec City, Canada. Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14), pp.2601-2607, 2014, 〈http://www.aaai.org/ocs/index.php/AAAI/AAAI14〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01067213
Contributeur : Joël Quinqueton <>
Soumis le : mardi 14 février 2017 - 17:15:16
Dernière modification le : lundi 16 juillet 2018 - 15:42:03
Document(s) archivé(s) le : lundi 15 mai 2017 - 17:51:56

Fichier

apoac_aaai_2014.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : lirmm-01067213, version 1

Collections

Citation

Amine Balafrej, Christian Bessière, Gilles Trombettoni, El Houssine Bouyakhf. Adaptive Singleton-based Consistencies. AAAI Conference on Artificial Intelligence, Jul 2014, Québec City, Canada. Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14), pp.2601-2607, 2014, 〈http://www.aaai.org/ocs/index.php/AAAI/AAAI14〉. 〈lirmm-01067213〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

126