Introduction
In the field of automated reasoning, symmetries often pose a significant computational hurdle. When a solver encounters problems with thousands of identical components—such as racks in a warehouse or pigeons in holes—it typically explores redundant permutations, leading to exponential search times. Traditional "symmetry breaking" techniques attempt to prune these redundant branches, but the solver still operates on the original, massive domain. This paper, presented at AAAI-24, introduces a "lifted" approach to satisfiability checking that compresses the domain itself by treating symmetric elements as a single representative with a specific multiplicity.
Methodology: Domain Compression and Lifting
The core of the proposed method is a two-step process that transforms a standard First-Order Logic problem into an equisatisfiable "lifted" version. Instead of individual variables for every element, the solver utilizes a multiplicity function ($mul$) to track how many concrete elements each lifted element represents.
Automatic Translation
The authors define a set of recursive rules to translate logic sentences, including aggregates like sums and counts, into a lifted vocabulary. A critical component of this translation is the use of the Least Common Multiple ($lcm$) of multiplicities, ensuring that constraints scale correctly when the compressed model is expanded back to the concrete domain. This formal transformation is detailed in the rules below:
Lifted Domain Growth
The solver identifies a "Backbone"—a subset of the domain containing one representative from each symmetric group (orbit). It then iteratively grows the lifted domain until a "lifted model" is found. By solving for the backbone and the multiplicities, the authors prove that the resulting compressed solution can always be expanded back into a full-scale valid solution.
Empirical Evaluation
The researchers benchmarked their lifted solver against standard methods using several high-symmetry problems, including the Pigeonhole Problem, Organized Monkey Village, and various Rack configuration problems.
As shown in the experimental results, the lifted method achieves dramatic performance gains. In the "Monkey 1" benchmark, the lifted solver found a solution in 0.28 seconds, while the original solver took over 184 seconds. Most notably, the complexity of the lifted version often depends on the number of types of elements rather than the total count. For instance, in the "Rack A1000" problem, the original domain of 2,250 elements was compressed into a lifted domain of just 4 elements, allowing for near-constant time scaling regardless of domain size.
Conclusion
By shifting the focus from search-tree pruning to domain compression, this research provides a powerful framework for solving massive, symmetric logic problems. While the current implementation excels at finding solutions (satisfiability), future work is needed to address the challenges of proving unsatisfiability, as the iterative growth of the lifted domain does not naturally terminate in the absence of a model. Nevertheless, the ability to solve complex configuration problems in fractions of a second represents a significant advancement in the scalability of automated reasoning.
Summary updated