Introduction
In the field of Constraint Programming (CP), solvers tackle complex combinatorial problems—ranging from Sudoku and scheduling to hardware verification—by pruning the search space using "propagators." A common approach for general-purpose propagators is to use tables that explicitly list every valid combination of variable assignments, known as tuples. However, as problem complexity grows, these tables can expand astronomically, often exceeding available memory.
To address this, researchers have developed SHORTSTR2, an algorithm that leverages the concept of "short supports." A short support is a partial assignment of variables that satisfies a constraint regardless of the values assigned to the remaining variables. By focusing on these minimal subsets, SHORTSTR2 achieves significant compression and computational efficiency.
The SHORTSTR2 Framework
SHORTSTR2 builds upon the widely used "Simple Tabular Reduction" (STR2+) framework. It introduces two primary innovations:
1. Greedy Compression
Finding the absolute minimum set of short supports is an NP-complete problem. To make this practical, the authors developed Greedy-Compress. This heuristic takes a standard table of full-length tuples and iteratively collapses them into shorter versions by identifying variables that do not affect the constraint's satisfaction, replacing them with a wildcard symbol (*).
2. Efficient Propagation
The core SHORTSTR2 propagator maintains a set of "active" short supports during the search process. It utilizes two complementary data structures:
- Long Form: An array representation including wildcards that allows for $O(1)$ value lookups.
- Short Form: A compact list of variable-value pairs that enables the algorithm to iterate only through the variables essential to a specific support.
This dual-structure approach allows the solver to skip redundant checks on wildcard variables, drastically reducing the computational overhead during backtracking searches.
Experimental Evaluation
The algorithm was tested against several challenging benchmarks, including Quasigroup Existence (QG3), Rectangle Packing, and various "Oscillating Life" variants based on Conway’s Game of Life. It was also evaluated on standardized instances from the CSP Solver Competition.
Key Performance Results
The experiments demonstrated that SHORTSTR2 is particularly effective for constraints amenable to compression. In the "Quadlife" variant of the Game of Life, standard STR2+ failed due to memory limitations (exceeding 4GB), whereas SHORTSTR2 ran successfully.
In terms of raw speed, SHORTSTR2 often outperformed HAGGISGAC, a more complex state-of-the-art algorithm. For instance, on the "Vector Not-Equal" problem, SHORTSTR2 showed a performance advantage of up to a factor of two in several parameter configurations.
Insights and Future Work
The primary strength of SHORTSTR2 lies in its simplicity and "drop-in" compatibility with existing STR2+ implementations. While its performance gains are minimal on purely random, incompressible constraints, it offers exponential compression for many real-world structured constraints.
Future research aims to explore even more expressive grouping methods, such as "c-tuples" or tuple sequences, and to integrate SHORTSTR2 into a broader range of production-grade constraint solvers.
Summary updated