Length-Lex Ordering for Set CSPs

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Constraint Satisfaction and Satisfiability

Combinatorial design problems arise in many application areas, including networking, sport scheduling, and coding. They are naturally modelled in terms of set variables and set contraints (membership, inclusion, disjointness, and cardinality) and typically exhibit many symmetries. Traditionally, the domain of for set variables is specified by two sets (R,P) and denotes all sets containing R and included in P. While this representation is appropriate for many constraints, it has inherent difficulties in handling cardinality and lexicographic constraints so important in configuration 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. With this representation, the solver can achieve bound-consistency of all unary constraints in time O(k) where k is the greatest set size. In analogy with finite-domain solvers, non-unary constraints can be viewed as inference rules generating new unary constraints, allowing them to interact in reducing the domains. 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.