Skip to Main content Skip to Navigation
Journal articles

Strong Local Consistency Algorithms for Table Constraints

Anastasia Paparrizou 1 Kostas Stergiou 2 
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Wednesday, March 20, 2019 - 2:56:51 PM
Last modification on : Friday, August 5, 2022 - 3:02:57 PM
Long-term archiving on: : Friday, June 21, 2019 - 8:55:01 PM


Files produced by the author(s)




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



Record views


Files downloads