ECAI 2004 Conference Paper

[full paper]

Implementing Variable Elimination

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.216-220.