Filtering Algorithms Based on the Word-RAM Model

Authors

  • Philippe Van Kessel University of Laval
  • Claude-Guy Quimper University of Laval

DOI:

https://doi.org/10.1609/aaai.v26i1.8145

Keywords:

word-ram, all-different, sum

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.

Downloads

Published

2021-09-20

How to Cite

Van Kessel, P., & Quimper, C.-G. (2021). Filtering Algorithms Based on the Word-RAM Model. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 577-583. https://doi.org/10.1609/aaai.v26i1.8145

Issue

Section

Constraints, Satisfiability, and Search