Tech Report CS-06-02

Length-Lex Ordering for Set CSPs

Carmen Gervet and Pascal Van Henteryck

March 06


Combinatorial design problems arise in many application areas, are naturally modelled in terms of set variables and set constraints. Traditionally, the domain of a set variable is specified 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 important in combinatorial design. This paper takes a dual view of set variables. It proposes a representation that encodes directly cardinality and lexicographic information, by totally ordering a set domain with a length-lex ordering. Moreover, the solver can enforce bound-consistency on all unary constraints, including inclusion and disjointness, in time ~O(k) where k is the set size. In analogy with finite-domain solvers, non-unary constraints can be viewed as inference rules generating new unary constraints. The resulting set solver achieves a pruning (at least) comparable to the hybrid domain of Sadler and Gervet at a fraction of the computational cost.

(complete text in pdf or gzipped postscript)