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
Abstract
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.