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 metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01067437
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 10, 2019 - 1:47:51 PM
Last modification on : Saturday, October 12, 2019 - 1:13:16 AM

File

cp14-partition.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

160

Files downloads

20