A New Method to Encode the At-Most-One Constraint into SAT
Lists
Only you see this
Abstract
One of the most widely used constraints during the process of translating a practical problem into a propositional satisfiability (SAT) instance is the at-most-one (AMO) constraint. This paper proposes a new encoding for the AMO constraint, the so-called AMO bimander encoding which can be easily extended to encode cardinality constraints, which are often used in constraint programming. Experimental results reveal that the new encoding is very competitive compared with all other state-of-the-art encodings. Furthermore, we will prove that the new encoding allows unit propagation to achieve arc consistency - an important technique in constraint programming. We also show that a special case of the AMO bimander encoding outperforms the AMO binary encoding, a widely used encoding, in all our experiments.
BibTeX
@inproceedings{nguyen2015new,
author = {Van-Hau Nguyen and Son Thai Mai},
title = {{A New Method to Encode the At-Most-One Constraint into SAT}},
booktitle = {SoICT},
year = {2015},
url = {https://openreview.net/forum?id=S3pdsdluuD},
}Loading related content...