Optimizing Simple Tabular Reduction with a Bitwise Representation
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. PDF
Cite
Text
Wang et al. "Optimizing Simple Tabular Reduction with a Bitwise Representation." International Joint Conference on Artificial Intelligence, 2016.Markdown
[Wang et al. "Optimizing Simple Tabular Reduction with a Bitwise Representation." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/wang2016ijcai-optimizing/)BibTeX
@inproceedings{wang2016ijcai-optimizing,
title = {{Optimizing Simple Tabular Reduction with a Bitwise Representation}},
author = {Wang, Ruiwei and Xia, Wei and Yap, Roland H. C. and Li, Zhanshan},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2016},
pages = {787-795},
url = {https://mlanthology.org/ijcai/2016/wang2016ijcai-optimizing/}
}