Yet Another Comparison of SAT Encodings for the At-Most-K Constraint
Authors: Neng-Fa Zhou
Abstract: The at-most-k constraint is ubiquitous in combinatorial problems, and numerous SAT encodings are available for the constraint. Prior experiments have shown the competitiveness of the sequential-counter encoding for k $>$ 1, and have excluded the parallel-counter encoding, which is more compact that the binary-adder encoding, from consideration due to its incapability of enforcing arc consistency through unit propagation. This paper presents an experiment that shows astounding performance of the binary-adder encoding for the at-most-k constraint.
Explore the paper tree
Click on the tree nodes to be redirected to a given paper and access their summaries and virtual assistant
Look for similar papers (in beta version)
We compare the title and abstract with papers indexed in our database. For arXiv papers, we search within the same category; for DOI and other sources, we search across sources and subjects. You can rerun the search as our database grows.