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.
Type de document :
Article dans une revue
Constraints, Springer Verlag, 2016, 21 (2), pp.163-197
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01276179
Contributeur : Joël Quinqueton <>
Soumis le : jeudi 18 février 2016 - 21:25:22
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23

Identifiants

  • HAL Id : lirmm-01276179, version 1

Collections

Citation

Anastasia Paparrizou, Kostas Stergiou. Strong Local Consistency Algorithms for Table Constraints. Constraints, Springer Verlag, 2016, 21 (2), pp.163-197. 〈lirmm-01276179〉

Partager

Métriques

Consultations de la notice

28