Extending STR to a Higher-Order Consistency

Christophe Lecoutre, Anastasia Paparrizou, Kostas StergiouAAAI 2013 · DOI

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:

  1. Intersection Counters: For every pair of intersecting constraints ($C_i$ and $C_j$), the algorithm maintains counters for each shared "subtuple."
  2. 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.
  3. Interleaved Updates: Counter updates (decrementing when a tuple becomes invalid) are integrated directly into the standard STR filtering loop.
Data structures for eSTR, including intersection counters and indexing arrays for managing subtuple supports.

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-100 and Aim-200 problem classes, eSTR2 outperformed the standard STR2 by 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.
Performance comparison across problem classes, highlighting speedups (s) and node reductions (n) for eSTR variants.

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

BibTeX
@inproceedings{lecoutre2013extending,
  author = {Christophe Lecoutre and Anastasia Paparrizou and Kostas Stergiou},
  title = {{Extending STR to a Higher-Order Consistency}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8622},
}

Loading related content...

Figure