Strong Bounds Consistencies and Their Application to Linear Constraints

Christian Bessière 1 Anastasia Paparrizou 1 Kostas Stergiou 2
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 University of Western Macedonia [Kozani]
Abstract : We propose two local consistencies that extend bounds consistency (BC) by simultaneously considering com- binations of constraints as opposed to single constraints. We prove that these two local consistencies are both stronger than BC, but are NP-hard to enforce even when constraints are linear. Hence, we propose two polynomial-time techniques to enforce approximations of these two consistencies on linear constraints. One is a reformulation of the constraints on which we enforce BC whereas the other is a polynomial time algorithm. Both achieve stronger pruning than BC. Our experi- ments show large differences in favor of our approaches.
Type de document :
Communication dans un congrès
AAAI Conference on Artificial Intelligence, 2015, Austin, Texas, United States. Twenty-Ninth AAAI Conference on Artificial Intelligence, pp.3717-3724, 2015
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01276177
Contributeur : Joël Quinqueton <>
Soumis le : jeudi 18 février 2016 - 21:13:55
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 00:06:06

Fichier

aaai15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01276177, version 1

Collections

LIRMM | COCONUT | MIPS | UNIV-MONTPELLIER

Citation

Christian Bessière, Anastasia Paparrizou, Kostas Stergiou. Strong Bounds Consistencies and Their Application to Linear Constraints. AAAI Conference on Artificial Intelligence, 2015, Austin, Texas, United States. Twenty-Ninth AAAI Conference on Artificial Intelligence, pp.3717-3724, 2015. 〈lirmm-01276177〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

141

Téléchargements de fichiers

120

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD