English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We present an approach to propagation-based SAT encoding of combinatorialproblems, Boolean equi-propagation, where constraints are modeled as Booleanfunctions which propagate information about equalities between Booleanliterals. This information is then applied to simplify the CNF encoding of theconstraints. A key factor is that considering only a small fragment of aconstraint model at one time enables us to apply stronger, and even complete,reasoning to detect equivalent literals in that fragment. Once detected,equivalences apply to simplify the entire constraint model and facilitatefurther reasoning on other fragments. Equi-propagation in combination withpartial evaluation and constraint simplification provide the foundation for apowerful approach to SAT-based finite domain constraint solving. We introduce atool called BEE (Ben-Gurion Equi-propagation Encoder) based on these ideas anddemonstrate for a variety of benchmarks that our approach leads to aconsiderable reduction in the size of CNF encodings and subsequent speed-ups inSAT solving times.

Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems