Enforcing Arc Consistency using Bitwise Operations
Christophe Lecoutre, Julien Vion · 2007
Editor: M.R.C. van Dongen In this paper, we propose to exploit bitwise operations to speed up some important computations such as looking for a support of a value in a constraint, or determining if a value is substitutable by another one. Considering a computer equipped with a x-bit CPU, one can then expect an increase of the performance by a coefficient up to x (which may be important, since x is equal to 32 or 64 in many current central units). To show the interest of enforcing arc consistency using bitwise operations, we introduce a new variant of AC3, denoted by AC3 bit, which can be used when constraints are (or can be) represented in extension. This new algorithm when embedded in MAC, is approximately two times more efficient than AC3 rm. Note that AC3 rm is a variant of AC3 which exploits the concept of residual supports and has been shown to be faster than AC2001.