Length-Lex Ordering for Set CSPs

Pascal Van Hentenryck, Carmen Gervet

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.

Subjects: 15. Problem Solving; 15.2 Constraint Satisfaction

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.