Optimizing Simple Tabular Reduction with a Bitwise Representation

Ruiwei Wang, Wei Xia, Roland H. C. Yap, Zhanshan LiIJCAI 2016

Abstract

Maintaining Generalized Arc Consistency (GAC) is a critical task in solving Constraint Satisfaction Problems (CSPs). This paper introduces STRbit and STRbit-C, two algorithms that leverage bitwise parallelism to optimize the Simple Tabular Reduction (STR) approach. By representing table constraints as bit-vectors, these algorithms allow solvers to validate multiple tuples simultaneously using constant-time bitwise operations. Experimental results demonstrate speedups of up to 25x over the state-of-the-art STR3 algorithm.

Introduction

Constraint Satisfaction Problems (CSPs) are ubiquitous in real-world applications such as scheduling and configuration. Efficiently solving these problems requires effective propagation techniques to prune the search space, with Generalized Arc Consistency (GAC) being the standard. However, for constraints defined by large tables of allowed tuples, maintaining GAC often becomes a computational bottleneck. Existing algorithms in the Simple Tabular Reduction (STR) family, like STR2 and STR3, dynamically reduce these tables but typically process tuples sequentially. This paper addresses the challenge of exploiting modern CPU architectures to accelerate tabular reduction through bitwise parallelism.

Methods

The authors propose the Bit Table data structure and two algorithms: STRbit and STRbit-C. In a Bit Table, the original table is partitioned into sub-tables corresponding to the CPU word size (typically 64 bits). For each variable-value pair (literal), a bitmask is stored where each bit indicates whether a specific tuple in the sub-table supports that literal.

Comparison of standard c-table and bit c-table representations.

STRbit adapts the incremental approach of STR3 by maintaining a bit-vector (VAL) of valid tuples. When a domain value is deleted, bitwise AND and NOT operations update the validity of all affected tuples in a single step. STRbit-C extends this to compressed tables (c-tuples), which use Cartesian products for more compact representation. This approach transforms support checking from a linear scan into an $O(1)$ bitwise operation per block of 64 tuples.

Evaluation

The algorithms were implemented in the Abscon solver and evaluated on a diverse set of benchmarks from International Constraint Solver Competitions. These include:

  • Random Benchmarks: Testing performance on unstructured data.
  • Structured Benchmarks: Including Golomb ruler, crosswords, and word puzzles.
  • Compressed Benchmarks: Instances specifically designed to test Cartesian product compression.

Results

STRbit and STRbit-C consistently outperformed previous state-of-the-art methods. STRbit achieved speedups of up to 25x over STR3 and 70x over STR2 on specific random benchmarks. A key finding is that the performance gain is strongly correlated with the "compression ratio"—the ratio of the standard table size ($L_c$) to the bit table size ($L_{bitc}$).

Speedup of STRbit-C over STR3-C as a function of the compression ratio.

Across most benchmarks, STRbit effectively bridges the performance gap between STR2 and STR3, dominating in most scenarios where tables are large enough to justify the bitwise overhead.

Conclusion

This work demonstrates that bitwise parallelism can significantly enhance the efficiency of table constraint propagation. While simpler algorithms like MDDc remain competitive for very small tables (under 50 tuples), STRbit represents a major advancement for large-scale constraints. Future research directions include integrating bitwise representations with global consistency algorithms like GIC4.

Summary updated

BibTeX
@inproceedings{wang2016optimizing,
  author = {Ruiwei Wang and Wei Xia and Roland H. C. Yap and Zhanshan Li},
  title = {{Optimizing Simple Tabular Reduction with a Bitwise Representation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure