Introduction
In Constraint Programming (CP), table constraints—which explicitly list allowed or forbidden combinations of values (tuples)—are fundamental for modeling real-world applications like configuration and database management. Most modern solvers rely on Generalized Arc Consistency (GAC) to filter impossible values. However, GAC is a "first-order" consistency that treats constraints independently, often missing "higher-order" inconsistencies that only emerge when examining the intersection of multiple constraints.
While stronger consistencies like Pairwise Consistency (PWC) have existed theoretically, they have historically been too computationally expensive for practical use. This paper introduces FPWC-STR (implemented as eSTR2), a novel algorithm that bridges this gap by extending Simple Tabular Reduction (STR) to achieve Full Pairwise Consistency efficiently.
Methodology: The eSTR Framework
The authors build upon the Simple Tabular Reduction (STR) algorithm, which dynamically maintains a list of valid tuples during search. The new approach, eSTR (extended STR), introduces specialized data structures to track intersections between constraints without significant overhead:
- Intersection Counters: For every pair of intersecting constraints ($C_i$ and $C_j$), the algorithm maintains counters for each shared "subtuple."
- Constant-Time Checks: These counters track how many valid tuples in one constraint support a specific combination of values in another, turning pairwise support checks into simple $O(1)$ look-ups.
- Interleaved Updates: Counter updates (decrementing when a tuple becomes invalid) are integrated directly into the standard STR filtering loop.
The paper presents two main versions: eSTR2, which enforces full pairwise consistency plus GAC, and a "weak" variant, eSTR2$^w$, which optimizes performance by reducing the frequency of constraint re-propagation.
Experimental Evaluation
The researchers evaluated their algorithms using benchmarks from the CSP Solver Competition, focusing on problems with non-trivial constraint intersections. These included synthetic benchmarks (Random and Forced Random), hard instances (Aim-100, Aim-200), classic consistency tests (Dubois), and high-arity constraints (BDD).
Key Results and Performance
The experimental data demonstrates that the extra pruning power of FPWC translates into significant real-world performance gains:
- Search Speedups: On the
Aim-100andAim-200problem classes,eSTR2outperformed the standardSTR2by one to two orders of magnitude in search time. - Node Reduction: Higher-order consistency often reduced the number of nodes visited in the search tree by a factor of 10 or more compared to GAC.
- Competitive Efficiency: Even on simpler problems where GAC is typically sufficient (e.g.,
Random), the overhead of maintaining counters was low enough that the algorithm remained competitive with state-of-the-art GAC solvers.
Insights and Limitations
A key insight of this work is that STR provides the ideal foundation for higher-order consistency; because it already iterates over valid tuples, adding a counting step for intersections adds relatively little overhead to the inner loop. The authors proved that FPWC is strictly stronger than GAC and the previously proposed maxRPWC consistency.
However, the primary limitation is memory consumption. Storing counters for every intersection can be intensive. In the BDD benchmark, which features constraints intersecting on 16 variables, the algorithm exhausted available RAM. Future work aims to mitigate this by using hash functions to map tuples to counters, potentially eliminating the need for large index arrays and significantly reducing the memory footprint.
Summary updated