Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Thursday, October 10, 2019 - 1:47:51 PM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM


Files produced by the author(s)




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. pp.688-704, ⟨10.1007/978-3-319-10428-7_50⟩. ⟨lirmm-01067437⟩



Record views


Files downloads