Optimizing Simple Tabular Reduction with a Bitwise Representation
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.
@inproceedings{ijcai2016p117,
title = {Optimizing Simple Tabular Reduction with a Bitwise Representation},
author = {Wang, Ruiwei and Xia, Wei and Yap, Roland H.C. and Li, Zhanshan},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {787--794},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/117},
}
TY - CPAPER TI - Optimizing Simple Tabular Reduction with a Bitwise Representation AU - Wang, Ruiwei AU - Xia, Wei AU - Yap, Roland H.C. AU - Li, Zhanshan T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 787 EP - 794 UR - https://ijcai.org/proceedings/2016/117 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
