Abstract: This paper surveys the evolution of filtering algorithms for table constraints in Constraint Programming, covering four decades of progress from basic tuple-checking to modern bit-parallel and compressed representation techniques. We analyze how the field transitioned from simple iteration to hardware-aligned bitwise operations, resulting in orders of magnitude speedups on standard benchmarks.
Introduction
In Constraint Programming (CP), a table constraint is the most fundamental way to define a relationship between variables: it simply lists all allowed (or disallowed) combinations of values, known as tuples. While intuitive, these tables can become gargantuan, making it computationally expensive to "filter" the domains of variables—that is, to remove values that cannot possibly be part of a solution.
The gold standard for this filtering is Generalized Arc Consistency (GAC). An algorithm achieves GAC if it ensures that for every value in a variable's domain, there exists at least one valid tuple in the table that supports it. The challenge addressed by researchers over the last 40 years is the quest for the most efficient way to maintain this consistency during a search process where variable domains are constantly shrinking.
Evolution of Algorithmic Families
Decades of research have categorized filtering techniques into several key algorithmic families, moving from flat lists to complex structures:
- GAC-schemes: Early frameworks (like GAC-V and GAC-A) that iterate through tuples to find "supports" for values.
- Simple Tabular Reduction (STR): A breakthrough approach that dynamically shrinks the table during search, removing invalid tuples so they don't have to be checked again.
- Bitwise Representations: The current state-of-the-art (e.g., STRbit, Compact-table (CT)). These algorithms use bit-vectors and word-level CPU operations to check thousands of tuples simultaneously, exploiting hardware parallelism.
- Compressed Representations: Instead of flat tables, these use Multi-valued Decision Diagrams (MDDs), tries, or "c-tuples" (Cartesian products) to represent the same data in a fraction of the space.
Key Insights and Hardware Alignment
Modern performance gains are driven by two primary innovations: residues and bit-parallelism.
Residues act as a caching mechanism; if a tuple supports a value in one step of the search, it is likely to remain valid for many subsequent steps. Saving these "residues" allows algorithms to skip massive amounts of re-computation.
Bit-Parallelism aligns solver logic with modern CPU architecture. By representing tuple validity as bit-vectors, solvers can use a single CPU instruction to filter 64 or more tuples at once. This shift from mathematical optimization to hardware-aware implementation has been the defining characteristic of recent high-performance solvers.
Performance Results
The quantitative progress in the field is staggering. Evaluations using the XCSP3 benchmarks—a standard competitive suite for constraint solvers—highlight the dominance of modern methods. Newer algorithms like STRbit can be up to 25x faster than STR3 and 70x faster than STR2 on difficult instances.
On specific complex problems, such as crossword puzzles, older standard algorithms often time out completely. In contrast, the modern CT algorithm can finish in under 50 seconds, while the specialized HTAC algorithm can complete the same task in just over 20 seconds. Furthermore, dynamic reduction techniques like STR can reduce the effective table size by 1 to 3 orders of magnitude during the search process.
Future Directions
While filtering efficiency has reached new heights, several open challenges remain. The interaction between filtering algorithms and search heuristics—how the solver chooses which variable to branch on next—is still not fully understood. Additionally, researchers are looking for better ways to integrate these generic table GAC algorithms with specialized "global constraints" (like AllDifferent) and revisiting specialized algorithms for binary constraints, which are becoming surprisingly competitive again.
Summary updated