Length-Lex Ordering for Set CSPs

Abstract

Combinatorial design problems arise in many application ar-eas and are naturally modelled in terms of set variables and constraints. Traditionally, the domain of a set variable is spec-ified by two sets (R,E) and denotes all sets containing R and disjoint from E. This representation has inherent difficulties in handling cardinality and lexicographic constraints so im-portant in combinatorial design. This paper takes a dual view of set variables. It proposes a representation that encodes di-rectly cardinality and lexicographic information, by totally ordering a set domain with a length-lex ordering. The solver can then enforce bound-consistency on all unary constraints in time Õ(k) where k is the set cardinality. In analogy with finite-domain solvers, non-unary constraints can be viewed as inference rules generating new unary constraints. The re-sulting set solver achieves a pruning (at least) comparable to the hybrid domain of Sadler and Gervet at a fraction of the computational cost.