Optimizing Simple Tabular Reduction with a Bitwise Representation

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.

Authors

• Ruiwei Wang National University of Singapore
• Wei Xia www. imxwell. com
• Roland H. C. Yap National University of Singapore
• Zhanshan Li Jilin University

Keywords

No keywords are indexed for this paper.