
[full paper] 
Marti Sanchez, Pedro Meseguer
Adaptive consistency is a solving algorithm for constraint networks. Its basic step is variable elimination: it takes a network as input, and produces an equivalent network with one less variable and one new constraint (the join of the variable bucket). This process is iterated until every variable is eliminated, and then all solutions can be computed without backtracking. A direct, naive implementation of variable elimination uses more space than needed, which renders this algorithm unapplicable in many cases. We present a more sophisticated implementation, based on the projection with memory of constraints. When a variable is projected out from a constraint, we keep the supports that that variable gave to the remaining tuples. Using this data structure, we compute a set of new constraints equivalent to the new constraint computed as the join of the variable bucket, but using less space on the average. This is especially relevant for problems where the elimination of the first variables generate very large constraints. We provide experimental evidence of the benefits of our approach.
Keywords: constraint satisfaction, constraint inference, adaptive consistency
Citation: Marti Sanchez, Pedro Meseguer: Implementing Variable Elimination. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.216220.