Strong Bounds Consistencies and Their Application to Linear Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

Strong Bounds Consistencies and Their Application to Linear Constraints

Résumé

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.
Fichier principal
Vignette du fichier
aaai15.pdf (257.56 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01276177 , version 1 (18-02-2016)

Identifiants

  • HAL Id : lirmm-01276177 , version 1

Citer

Christian Bessiere, Anastasia Paparrizou, Kostas Stergiou. Strong Bounds Consistencies and Their Application to Linear Constraints. AAAI Conference on Artificial Intelligence, Jan 2015, Austin, TX, United States. pp.3717-3724. ⟨lirmm-01276177⟩
392 Consultations
287 Téléchargements

Partager

Gmail Facebook X LinkedIn More