MOVES Seminar 23 Sep 2010, 14:00

 Yoav Fekete

 

Optimizing SAT encodings - cardinality constraints case study

 

Abstract:
SAT encoding is all about finding a good knowledge representation of a
given problem. But what is a "good" SAT encoding, and how can we
evaluate one? In this talk we will review different encodings of
cardinality constraints and see how the use of mixed radix bases
enables us to improve the "quality" of the encoding.