Improving Relational Consistency Algorithms Using Dynamic Relation Partitioning - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2014

Improving Relational Consistency Algorithms Using Dynamic Relation Partitioning

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.
Fichier principal
Vignette du fichier
cp14-partition.pdf (947.03 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01067437 , version 1 (10-10-2019)

Identifiers

Cite

Anthony Schneider, Robert J. Woodward, Berthe Y. Choueiry, Christian Bessiere. 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⟩
135 View
123 Download

Altmetric

Share

More