A Family of Encodings for Translating Pseudo-Boolean Constraints into SAT

Details A Family of Encodings for Translating Pseudo-Boolean Constraints into SAT A Family of Encodings for Translating Pseudo-Boolean Constraints into SAT

2011-04-08

arxiv.org/abs/1104.1479v2

Computer Science

Logic in Computer Science

Submitted to SAT 2012

Scientific paper

A Pseudo-Boolean constraint is a linear constraint over Boolean variables. This kind of constraints has been widely used in expressing NP-complete problems. This paper introduces a new algorithm for translating Pseudo-Boolean constraints into CNF clauses. The CNF produced by the proposed encoding has small size, and we also characterize the constraints for which one can expect the SAT solvers to perform well on the produced CNF. We show that there are many constraints for which the proposed encoding has a good performance.

Affiliated with

Also associated with

No associations

Rating

A Family of Encodings for Translating Pseudo-Boolean Constraints into SAT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Family of Encodings for Translating Pseudo-Boolean Constraints into SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Family of Encodings for Translating Pseudo-Boolean Constraints into SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-353970