Making Simple Tabular ReductionWorks on Negative Table Constraints

Hongbo Li, Yanchun Liang, Jinsong Guo, Zhanshan LiAAAI 2013 · DOI

Abstract

Simple Tabular Reduction (STR) has proven to be a highly efficient technique for maintaining Generalized Arc Consistency (GAC) on positive table constraints. However, its application to negative table constraints—where disallowed tuples are explicitly listed—has remained unexplored. This paper introduces STR-Negative (STR-N) and its optimized variant, STR-Ni. By shifting the focus from finding valid supports to counting disallowed ones, these algorithms provide a robust mechanism for handling loose constraints efficiently. Experimental results demonstrate that STR-Ni significantly outperforms existing state-of-the-art GAC algorithms on both random and structured benchmark instances.

Introduction

In Constraint Satisfaction Problems (CSPs), table constraints are a fundamental way to define relationships between variables. While positive tables list allowed combinations, negative tables list forbidden ones. Negative tables are particularly space-efficient for "loose" constraints where the vast majority of combinations are valid. Maintaining Generalized Arc Consistency (GAC) is critical for solver performance, yet the highly effective STR family of algorithms was previously limited to positive constraints. This work bridges that gap by adapting STR logic to negative tables.

Methodology

The core challenge in negative tables is that a value is supported if there exists at least one combination not present in the table.

STR-Negative (STR-N)

STR-N employs a counting-based approach. For each value $(x, a)$, the algorithm calculates the total number of possible combinations based on current variable domains. It then iterates through the negative table, identifying disallowed tuples that are still "valid" (i.e., all participating values remain in their domains). For each such tuple, the count for the corresponding values is decremented. If the count remains above zero after processing the table, the value is supported; otherwise, it is pruned.

STR-Ni (Improved)

STR-Ni introduces a "Safety in Numbers" optimization. If the initial number of possible valid combinations for a value is significantly larger than the total number of tuples in the negative table, the algorithm can immediately conclude that support exists without scanning the table. This shortcut drastically reduces computation time for very loose constraints.

Experimental Evaluation

The proposed algorithms were compared against mddc (Multi-valued Decision Diagram based GAC) and GAC-v (GAC-valid) using two benchmark sets: Random Instances (Model RB) and structured benchmarks like Chessboard Coloration and Golomb Ruler problems.

Results on Benchmark Instances

As shown in Figure 1, STR-Ni consistently achieves the lowest runtimes across various structured instances. For the challenging ruler-44-10-a4 instance, STR-Ni required only 608.94 seconds, outperforming GAC-v (690.04s) and mddc (908.87s).

Performance comparison on benchmark instances including Chessboard Coloration and Golomb Ruler.

Results on Random Instances

The efficiency of the STR-N family is even more pronounced in high-arity random constraints. Figure 2 illustrates that as the complexity of the problem increases (e.g., arity 10), STR-Ni provides substantial speedups. In the most demanding configuration shown, STR-Ni (466.92s) is nearly three times faster than GAC-v (1330.53s) and five times faster than mddc (2312.29s).

Performance comparison on Random Instances (Model RB) across different arity and density configurations.

Conclusion

STR-N and STR-Ni successfully extend the benefits of Simple Tabular Reduction to negative table constraints. By leveraging a counting pivot and dynamic table maintenance, these algorithms offer a superior alternative to traditional GAC methods, particularly for loose, high-arity constraints. Future work will focus on integrating these techniques with advanced search heuristics and exploring their performance on large-scale industrial datasets.

Summary updated

BibTeX
@inproceedings{li2013making,
  author = {Hongbo Li and Yanchun Liang and Jinsong Guo and Zhanshan Li},
  title = {{Making Simple Tabular ReductionWorks on Negative Table Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8519},
}
Figure