Filtering Atmost1 on Pairs of Set Variables

Many combinatorial problems, such as bin packing, set covering, and combinatorial design, can be conveniently expressed using set variables and constraints over these variables [3]. In constraint programming such problems can be modeled directly in their natural form by means of set variables. This offers a great potential in exploiting the structure captured by set variables during the solution process, for example to break problem symmetry or to improve domain filtering. We present an efficient filtering algorithm, establishing bounds consistency, for the atmost1 constraint on pairs of set variables with fixed cardinality. Computational results on social golfer benchmark problems demonstrate that with this additional filtering, these problems can be solved up to 50 times faster.