Efficient CNF encoding of boolean cardinality constraints
O Bailleux, Y Boufkhad - … conference on principles and practice of …, 2003 - Springer
International conference on principles and practice of constraint programming, 2003•Springer
In this paper, we address the encoding into CNF clauses of Boolean cardinality constraints
that arise in many practical applications. The proposed encoding is efficient with respect to
unit propagation, which is implemented in almost all complete CNF satisfiability solvers. We
prove the practical efficiency of this encoding on some problems arising in discrete
tomography that involve many cardinality constraints. This encoding is also used together
with a trivial variable elimination in order to re-encode parity learning benchmarks so that a …
that arise in many practical applications. The proposed encoding is efficient with respect to
unit propagation, which is implemented in almost all complete CNF satisfiability solvers. We
prove the practical efficiency of this encoding on some problems arising in discrete
tomography that involve many cardinality constraints. This encoding is also used together
with a trivial variable elimination in order to re-encode parity learning benchmarks so that a …
Abstract
In this paper, we address the encoding into CNF clauses of Boolean cardinality constraints that arise in many practical applications. The proposed encoding is efficient with respect to unit propagation, which is implemented in almost all complete CNF satisfiability solvers. We prove the practical efficiency of this encoding on some problems arising in discrete tomography that involve many cardinality constraints. This encoding is also used together with a trivial variable elimination in order to re-encode parity learning benchmarks so that a simple Davis and Putnam procedure can solve them.
Springer