Strong Local Consistency Algorithms for Table Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Constraints Année : 2016

Strong Local Consistency Algorithms for Table Constraints

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
295 Consultations
147 Téléchargements

Altmetric

Partager

More