Filtering methods for symmetric cardinality constraint

Abstract

The symmetric cardinality constraint is described in terms of variables X = {x_1,...,x_k} which take values in the subset of values V={v_1,...,v_n}. It constraints the number of times a value can be assigned to a variable in X to be in an interval [l_{x_i},c_{x_i}] and at the same time it restricts the number of values in V which any variable can take to an interval [l_{v_j},c_{v_j}]. In this paper we introduce the symmetric cardinality constraint and define set constraint satisfaction problem as a framework for dealing with this type of constraints. Moreover, we present effective filtering methods for the symmetric cardinality constraint.