Exploiting Weak Dependencies in Tree-based Search

Abstract : In this work, our objective is to heuristically discover a simplified form of functional dependencies between variables called weak dependencies. Once discovered, these relations are used to rank the variables. Our method shows that these relations can be detected with some acceptable overhead during constraint propagation. More precisely, each time a variable y gets instantiated as a result of the instantiation of x, a weak dependency (x,y) is recorded. As a consequence, the weight of x is raised, and the variable becomes more likely to be selected by the variable ordering heuristic. Experiments on a large set of problems show that on the average, the search trees are reduced by a factor 3 while runtime is decreased by 31% when compared against dom-wdeg, one of the best dynamic variable ordering heuristic.
Type de document :
Communication dans un congrès
24th Annual ACM Symposium on Applied Computing, Mar 2009, Honolulu, United States. 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00344179
Contributeur : Alejandro Arbelaez <>
Soumis le : mercredi 3 décembre 2008 - 23:10:47
Dernière modification le : jeudi 4 décembre 2008 - 23:01:12
Document(s) archivé(s) le : jeudi 11 octobre 2012 - 12:31:17

Fichier

SAC-functdep.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00344179, version 1

Collections

Citation

Alejandro Arbelaez, Youssef Hamadi. Exploiting Weak Dependencies in Tree-based Search. 24th Annual ACM Symposium on Applied Computing, Mar 2009, Honolulu, United States. 2009. 〈inria-00344179〉

Partager

Métriques

Consultations de la notice

297

Téléchargements de fichiers

269