This review considers how LCG has been refined and expanded over the years since its invention, and how it is used in all most performant CP solvers.
Abstract
Lazy clause generation (LCG) is an approach to building constraint programming (CP) solvers that uses ideas from Boolean Satisfiability (SAT) solvers. Propagation in the CP solver is extended to
explain
itself, lazily creating explanation clauses. This allows SAT style conflict analysis to be used to create clausal nogoods that record the reason for failure, and avoid the same failure in the future. LCG has proven to be a highly effective architecture, used in all most performant CP solvers. In this review we consider how LCG has been refined and expanded over the years since its invention.
Optional variables have for a long time been identified as a crucial component of state-of-the-art scheduling solvers and play an important role in the efficiency of such solvers by enabling a stronger inference in a constraint propagation engine.
Arthur Bit-Monnot· International Conference on...· 0 citations
This work presents the first systematic analysis of how leading LCG solvers maintain their SAT encodings, based on source-code inspection and developer correspondence, and proposes a native CDCL framework for CP, replacing SAT literals with atomic constraints, enabling conflict analysis, nogood learning, and nogood pro...
This system description reports on how Kissat’s award-winning techniques were adapted to the full-featured incremental SAT solver CaDiCaL, including clausal congruence closure, clausal equivalence sweeping, and bounded variable addition, to support efficient linear proof production with hints.
Florian Pollitt, Mathias Fleury, Katalin Fazekas et al.· 0 citations
This workshop paper presents a simplified version of the proposed loop operator approach, applied to a logic with loops restricted to atomic roles and their transitive closures.
B. Bednarczyk, Mikołaj Swoboda· Digital library· 0 citations
An account of the design and implementation of OpenSolver, an abstract branch-and-propagate tree search engine that supports a wide range of relevant solver configurations, and of many experiments that were performed to evaluate the approach.
P. Zoeteweij· 79 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
