Domain filtering consistencies for non-binary constraints

Christian Bessière 1 Kostas Stergiou 2 Toby Walsh 3
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In non-binary constraint satisfaction problems, the study of local consistencies that only prune values from domains has so far been largely limited to generalized arc consistency or weaker local consistency properties. This is in contrast with binary constraints where numerous such domain filtering consistencies have been proposed. In this paper we present a detailed theoretical, algorithmic and empirical study of domain filtering consistencies for non-binary problems. We study three domain filtering consistencies that are inspired by corresponding variable based domain filtering consistencies for binary problems. These consistencies are stronger than generalized arc consistency, but weaker than pairwise consistency, which is a strong consistency that removes tuples from constraint relations. Among other theoretical results, and contrary to expectations, we prove that these new consistencies do not reduce to the variable based definitions of their counterparts on binary constraints. We propose a number of algorithms to achieve the three consistencies. One of these algorithms has a time complexity comparable to that for generalized arc consistency despite performing more pruning. Experiments demonstrate that our new consistencies are promising as they can be more efficient than generalized arc consistency on certain non-binary problems.
Type de document :
Article dans une revue
Artificial Intelligence, Elsevier, 2008, 172 (6-7), pp.800-822. 〈10.1016/j.artint.2007.10.016〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00250086
Contributeur : Christian Bessiere <>
Soumis le : samedi 9 février 2008 - 17:11:58
Dernière modification le : mercredi 14 février 2018 - 11:46:01

Lien texte intégral

Identifiants

Collections

Citation

Christian Bessière, Kostas Stergiou, Toby Walsh. Domain filtering consistencies for non-binary constraints. Artificial Intelligence, Elsevier, 2008, 172 (6-7), pp.800-822. 〈10.1016/j.artint.2007.10.016〉. 〈lirmm-00250086〉

Partager

Métriques

Consultations de la notice

81