The Symmetric Alldiff Constraint

Abstract

The symm etric alldiff constraint is a particular case of the alldiff constraint, a case in which variables and values are defined from the same set S. That is, every variable represents an element e of S and its values represent the el ements of S that are compatible with e. This constraint requires that all the values taken by the variables are different (similar to the classical alldiff constraint) and that if the variable representing the element i is assigned to the value representing the element j, then the variable representing the el ement j is assigned to the value representing the element i. This constraint is present in many real-world problems, such sports scheduling where it expresses matches between teams. In this paper, we show how to compute the arc consistency of this constraint in O(nm) (m =I:; ID(i)l), where n is the number of involved variables and D( i) the domain of the variable i. We also propose a filtering algorithm of less complexity (O(m)) .