Improving Relational Consistency Algorithms Using Dynamic Relation Partitioning

Anthony Schneider 1 Robert J. Woodward 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 : Relational consistency algorithms are instrumental for solving difficult instances of Constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing relational consistency by exploiting the property that the constraints of the dual encoding of a CSP are piecewise functional. This property allows us to partition a CSP relation into blocks of equivalent tuples at varying levels of granularity. Our new algorithm dynamically exploits those partitions. Our experiments show a significant improvement of the processing time for enforcing relational consistency.
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.688-704, 2014, 〈http://cp2014.a4cp.org/〉. 〈10.1007/978-3-319-10428-7_50〉
Liste complète des métadonnées

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

Identifiants

Collections

Citation

Anthony Schneider, Robert J. Woodward, Berthe Y. Choueiry, Christian Bessière. Improving Relational Consistency Algorithms Using Dynamic Relation Partitioning. CP: Principles and Practice of Constraint Programming, Sep 2014, Lyon, France. 20th International Conference on Principles and Practice of Constraint Programming, LNCS (8656), pp.688-704, 2014, 〈http://cp2014.a4cp.org/〉. 〈10.1007/978-3-319-10428-7_50〉. 〈lirmm-01067437〉

Partager

Métriques

Consultations de la notice

100