Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
verfasst von : Carsten Sinz
Erschienen in: Principles and Practice of Constraint Programming - CP 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the problem of encoding Boolean cardinality constraints in conjunctive normal form (CNF). Boolean cardinality constraints are formulae expressing that at most (resp. at least)
k
out of
n
propositional variables are true. We give two novel encodings that improve upon existing results, one which requires only 7
n
clauses and 2
n
auxiliary variables, and another one demanding
$\mathcal{O}(n \cdot k)$
clauses, but with the advantage that inconsistencies can be detected in linear time by unit propagation alone. Moreover, we prove a linear lower bound on the number of required clauses for any such encoding.