Strong Local Consistency Algorithms for Table Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Constraints Year : 2016

Strong Local Consistency Algorithms for Table Constraints

Abstract

Table constraints are important in constraint programming as they are present in many real problems from areas such as configuration and databases. As a result, numerous specialized algorithms that achieve generalized arc consistency (GAC) on table constraints have been proposed. Since these algorithms achieve GAC, they operate on one constraint at a time. In this paper we propose new filtering algo- rithms for positive table constraints that achieve stronger local consistency proper- ties than GAC by exploiting intersections between constraints. The first algorithm, called maxRPWC+, is a domain filtering algorithm that is based on the local con- sistency maxRPWC and extends the GAC algorithm of Lecoutre and Szymanek [23]. The second algorithm extends the state-of-the-art STR-based algorithms to stronger relation filtering consistencies, i.e., consistencies that can remove tu- ples from constraints’ relations. Experimental results from benchmark problems demonstrate that the proposed algorithms are quite competitive with standard GAC algorithms like STR2 in some classes of problems with intersecting table con- straints, being orders of magnitude faster in some cases.
Fichier principal
Vignette du fichier
maxRPWC_cons15.pdf (462.71 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01276179 , version 1 (20-03-2019)

Identifiers

Cite

Anastasia Paparrizou, Kostas Stergiou. Strong Local Consistency Algorithms for Table Constraints. Constraints, 2016, 21 (2), pp.163-197. ⟨10.1007/s10601-014-9179-1⟩. ⟨lirmm-01276179⟩
293 View
146 Download

Altmetric

Share

More