---
title: "Optimizing Simple Tabular Reduction with a Bitwise Representation"
authors:
  - "Ruiwei Wang"
  - "Wei Xia"
  - "Roland H. C. Yap"
  - "Zhanshan Li"
doi: ""
url: "https://ijcai.org/proceedings/2016/117"
pdf: "https://ijcai.org/proceedings/2016/0117.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "787-794"
track: ""
keywords:
---

# Optimizing Simple Tabular Reduction with a Bitwise Representation

Ruiwei Wang, Wei Xia, Roland H. C. Yap, Zhanshan Li

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 787-794.

## Abstract

Maintaining Generalized Arc Consistency (GAC) during search is considered an efficient way to solve non-binary constraint satisfaction problems. Bit-based representations have been used effectively in Arc Consistency algorithms. We propose STRbit, a GAC algorithm, based on simple tabular reduction (STR) using an efficient bit vector support data structure. STRbit is extended to deal with compression of the underlying constraint with c-tuples. Experimental evaluation show our algorithms are faster than many algorithms (STR2, STR2-C, STR3, STR3-C and MDDc) across a variety of benchmarks except for problems with small tables where complex data structures do not payoff.