Strong Bounds Consistencies and Their Application to Linear Constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
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⟩
404 Consultations
294 Téléchargements

Partager

More