Introduction
Constraint Satisfaction Problems (CSPs) are a cornerstone of automated reasoning, used to find solutions that satisfy a predefined set of rules. While integer variables are standard, many real-world problems—such as scheduling, grouping, or configuration—are more naturally modeled using set variables. A set variable's value is a subset of a given universe, leading to a domain size of $2^n$ for $n$ elements.
In the context of Weighted CSPs (WCSPs), which incorporate "soft" constraints with associated violation costs, handling set variables has historically been difficult. Researchers typically resort to simulating sets using collections of 0-1 (Boolean) variables. However, this approach often obscures the high-level structure of the problem and hinders efficient constraint propagation. This paper presents a framework that integrates set variables directly into WCSPs by "micro-managing" individual set elements.
Methodology: The Micro-Management Approach
The core innovation of this work is the decomposition of complex set-level constraints into element-level cost functions. Instead of reasoning about the entire power set, the solver tracks the costs associated with the inclusion or exclusion of each individual element.
Set Bounds and Cost Functions
The authors represent set domains using set intervals, defined by a Lower Bound (elements that must be present) and an Upper Bound (elements that might be present). High-level constraints like union ($S_i \cup S_j = S_k$), intersection, and subset are mapped to equivalent cost functions that operate on the existence of elements across variables.
Consistency Notions
To prune the search space effectively, the authors introduce several levels of Weighted Set Bounds Consistency (WSBC):
- Element Node Consistency (ENC): Evaluates costs at the level of a single element within a single set variable.
- Element Arc/Hyper-arc Consistency (EAC/EHAC): Manages costs across binary or ternary relationships between elements of different sets.
- Weighted Cardinality Consistency (WCC): Specifically handles constraints on the size (cardinality) of sets, a common requirement in combinatorial problems.
These notions ensure that the solver can identify and prune inconsistent values early in the search process. The authors implemented these techniques in a prototype solver named TB-Set, built upon the existing ToolBar WCSP solver.
Experimental Evaluation
The framework was evaluated using two benchmarks from CSPLib: the Steiner Triple System (CSPLib044) and the Social Golfer Problem (CSPLib010). To test the "weighted" aspect, the researchers created three variants of each problem:
- Classical: Standard hard constraints where violations have infinite cost.
- Restricted: Random unary costs are added to elements to simulate preferences.
- Relaxed: Hard constraints are "softened" by replacing infinite penalties with large, finite costs, allowing for solutions that minimize total violation.
Key Results and Insights
The "micro-management" strategy proved highly effective. A key theoretical insight is that enforcing consistency at the element level automatically implies consistency at the set level, making the approach both sound and computationally tractable.
As shown in the results, TB-Set outperformed the commercial ILOG Solver 6.0 on classical Steiner Triple Systems. More significantly, on "softened" versions of the Social Golfer Problem, TB-Set achieved speedups of up to two orders of magnitude compared to the standard 0-1 variable simulation (TB-01). The 0-1 simulation often fails because it transforms simple set constraints into complex $n$-ary constraints that are difficult for general-purpose solvers to prune.
Conclusion and Future Directions
By treating set variables as first-class citizens in the WCSP framework, the authors have demonstrated that element-level reasoning provides superior pruning power and efficiency. Future work includes exploring more advanced data structures like Reduced Ordered Binary Decision Diagrams (ROBDDs) for stronger domain consistency and extending the framework to handle more complex global constraints.
Summary updated