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
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01276177
Contributor : Joël Quinqueton <>
Submitted on : Thursday, February 18, 2016 - 9:13:55 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Long-term archiving on : Sunday, November 13, 2016 - 12:06:06 AM

File

aaai15.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01276177, version 1

Collections

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. pp.3717-3724. ⟨lirmm-01276177⟩

Share

Metrics

Record views

300

Files downloads

238