Adaptive Parameterized Consistency

Abstract : State-of-the-art constraint solvers uniformly maintain the same level of local consistency (usually arc consistency) on all the instances. We propose parameterized local consistency, an original approach to adjust the level of consistency depending on the instance and on which part of the instance we propagate. We do not use as parameter one of the features of the instance, as done for instance in portfolios of solvers. We use as parameter the stability of values, which is a feature based on the state of the arc consistency algorithm during its execution. Parameterized local consistencies choose to enforce arc consistency or a higher level of local consistency on a value depending on whether the stability of the value is above or below a given threshold. We also propose a way to dynamically adapt the parameter, and thus the level of local consistency, during search. This approach allows us to get a good trade-off between the number of values pruned and the computational cost. We validate our approach on various problems from the CSP competition.
Type de document :
Communication dans un congrès
CP: Principles and Practice of Constraint Programming, Sep 2013, Uppsala, Sweden. 19th International Conference on Principles and Practice of Constraint Programming, LNCS (8124), pp.143-158, 2013, 〈10.1007/978-3-642-40627-0_14〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00839025
Contributeur : Joël Quinqueton <>
Soumis le : mardi 23 janvier 2018 - 15:53:11
Dernière modification le : jeudi 25 janvier 2018 - 01:12:25

Fichier

cp13-p-maxrpc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Amine Balafrej, Christian Bessière, Remi Coletta, El Houssine Bouyakhf. Adaptive Parameterized Consistency. CP: Principles and Practice of Constraint Programming, Sep 2013, Uppsala, Sweden. 19th International Conference on Principles and Practice of Constraint Programming, LNCS (8124), pp.143-158, 2013, 〈10.1007/978-3-642-40627-0_14〉. 〈lirmm-00839025〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

21