Decomposition of the Factor Encoding for CSPs

Likitvivatanavong, Chavalit; Xia, Wei; Yap, Roland H.C.

Decomposition of the Factor Encoding for CSPs

Chavalit Likitvivatanavong, Wei Xia, Roland H. C. Yap

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 353-358.

Abstract

Generalized arc consistency (GAC) is one of the most fundamental properties for reducing the search space when solving constraint satisfaction problems (CSPs). Consistencies stronger than GAC have also been shown useful, but the challenge is to develop efficient and simple filtering algorithms. Several CSP transformations are proposed recently so that the GAC algorithms can be applied on the transformedCSP to enforce stronger consistencies. Among them, the factor encoding (FE) is shown to be promising with respect to recent higher-order consistency algorithms. Nonetheless, one potential drawback of the FE is the fact that it enlarges the table relations as it increases constraint arity. We propose a variation of the FE that aims at reducing redundant columns in the constraints of the FE while still preserving full pairwise consistency. Experiments show that the new approach is competitive over a variety of random and structured benchmarks.

Chavalit Likitvivatanavong, Wei Xia, and Roland H.C. Yap. 2015. Decomposition of the Factor Encoding for CSPs. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 353–358. https://ijcai.org/proceedings/2015/56

@inproceedings{ijcai2015p56,
  title     = {Decomposition of the Factor Encoding for CSPs},
  author    = {Likitvivatanavong, Chavalit and Xia, Wei and Yap, Roland H.C.},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {353--358},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/56},
}

TY  - CPAPER
TI  - Decomposition of the Factor Encoding for CSPs
AU  - Likitvivatanavong, Chavalit
AU  - Xia, Wei
AU  - Yap, Roland H.C.
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 353
EP  - 358
UR  - https://ijcai.org/proceedings/2015/56
ER  -