Strong Bounds Consistencies and Their Application to Linear Constraints
Abstract
We propose two local consistencies that extend bounds consistency (BC) by simultaneously considering combinations 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 experiments show large differences in favor of our approaches.
Cite
Text
Bessiere et al. "Strong Bounds Consistencies and Their Application to Linear Constraints." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9756Markdown
[Bessiere et al. "Strong Bounds Consistencies and Their Application to Linear Constraints." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/bessiere2015aaai-strong/) doi:10.1609/AAAI.V29I1.9756BibTeX
@inproceedings{bessiere2015aaai-strong,
title = {{Strong Bounds Consistencies and Their Application to Linear Constraints}},
author = {Bessiere, Christian and Paparrizou, Anastasia and Stergiou, Kostas},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {3717-3723},
doi = {10.1609/AAAI.V29I1.9756},
url = {https://mlanthology.org/aaai/2015/bessiere2015aaai-strong/}
}