Two Set-Constraints for Modeling and Efficiency

Set variables provide convenient modeling shorthands for many combinatorial problems. However, it is often challenging to efficiently handle set constraints when solving the problem. We present efficient filtering algorithms, establishing bounds consistency, for two such constraints: the sum-free constraint, and the atmost1 constraint on pairs of set variables with known cardinality. The filtering algorithm for the sum-free constraint achieves the same pruning as the corresponding collection of constraints on the binary representation, but it does so more efficiently and without running into memory bottlenecks. For the atmost1 constraint on pairs of set variables, the additional time spent on pruning more values pays off well in terms of overall efficiency. Our results show that set constraints can not only ease modeling the problem, they can also decrease the solution time and memory requirements.