Adaptive Parameterized Consistency for Non-Binary CSPs by Counting Supports

Robert J. Woodward 1 Anthony Schneider 1 Berthe Y. Choueiry 1 Christian Bessière 2
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Determining the appropriate level of local consistency to en- force on a given instance of a Constraint Satisfaction Problem (CSP) is not an easy task. However, selecting the right level may determine our ability to solve the problem. Adaptive parameterized consistency was recently proposed for binary CSPs as a strategy to dynamically select one of two local consistencies (i.e., AC and maxRPC). In this paper, we propose a similar strategy for non-binary table constraints to select between enforcing GAC and pairwise consistency. While the former strategy approximates the supports by their rank and requires that the variablesndomains be ordered, our technique removes those limitations. We empirically evaluate our approach on benchmark problems to establish its advantages.
Type de document :
Communication dans un congrès
CP: Principles and Practice of Constraint Programming, Sep 2014, Lyon, France. 20th International Conference on Principles and Practice of Constraint Programming, LNCS (8656), pp.755-764, 2014, 〈http://cp2014.a4cp.org/〉. 〈10.1007/978-3-319-10428-7_54〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01067342
Contributeur : Joël Quinqueton <>
Soumis le : mardi 23 septembre 2014 - 13:54:44
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

Collections

Citation

Robert J. Woodward, Anthony Schneider, Berthe Y. Choueiry, Christian Bessière. Adaptive Parameterized Consistency for Non-Binary CSPs by Counting Supports. CP: Principles and Practice of Constraint Programming, Sep 2014, Lyon, France. 20th International Conference on Principles and Practice of Constraint Programming, LNCS (8656), pp.755-764, 2014, 〈http://cp2014.a4cp.org/〉. 〈10.1007/978-3-319-10428-7_54〉. 〈lirmm-01067342〉

Partager

Métriques

Consultations de la notice

90