Filtering Algorithms Based on the Word-RAM Model
Abstract
The Word-RAM is a model of computation that takes into account the capacity of a computer to manipulate a word of w bits with a single instruction. Many modern constraint solvers use a bitset data structure to encode the values contained in the variable domains. Using the algorithmic techniques developed for the Word-RAM, we propose new filtering algorithms that can prune Opwq values from a domain in a single instruction. Experiments show that on a processor with w = 64, the new filtering algorithms that enforce domain consis- tency on the constraints A + B = C, |A - B| = C and ALL-DIFFERENT can offer a speed up of a factor 10.
Cite
Text
Van Kessel and Quimper. "Filtering Algorithms Based on the Word-RAM Model." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8145Markdown
[Van Kessel and Quimper. "Filtering Algorithms Based on the Word-RAM Model." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/kessel2012aaai-filtering/) doi:10.1609/AAAI.V26I1.8145BibTeX
@inproceedings{kessel2012aaai-filtering,
title = {{Filtering Algorithms Based on the Word-RAM Model}},
author = {Van Kessel, Philippe and Quimper, Claude-Guy},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {577-583},
doi = {10.1609/AAAI.V26I1.8145},
url = {https://mlanthology.org/aaai/2012/kessel2012aaai-filtering/}
}