Tech Report CS-06-02

Length-Lex Ordering for Set CSPs

Carmen Gervet and Pascal Van Henteryck

March 06

Abstract:

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)