Solving Cardinality Constraints in (Constraint) Logic Programming

Dietmar Seipel and Ulrich Geske

In Proc. of the International Workshop on Functional and (Constraint) Logic Programming (WFLP 2001) , Report No. 2017, University of Kiel


We investigate sets of {\em cardinality constraints\/} of the form $\ccons{M}{\Theta}{K}$, where $\Theta \in \{=,\leq,\geq\}$. Such a constraint $C$ requires that a model of $C$ has to contain ``(exactly, at most, at least) $K$ elements out of the set $M$''. Applications dealing with {\em cardinality constraints\/} may for instance arise in assignment problems, such as {\em course planning\/}, or in {\em games\/}: E.g.\ there may be rules like ``every student has to take $3$ of the courses in a given set $M$''. We present a {\em calculus\/} represented by a definite logic program, which allows for very efficiently reasoning with sets of cardinality constraints, where $\Theta$ is ``$=$''. We have implemented the calculus in {\sc Swi}--\prolog\ and we have compared it to other methods that we have encoded in constraint logic programming.