Proceedings of the AAAI Conference on Artificial Intelligence · 2021 · 17 citations · 23 references
ComputingComputer ScienceAlgorithmsKnowledge RepresentationOptimizationConstrained OptimizationConstraint SatisfactionBoolean SatisfiabilityBoolean Satisfiability ProblemCutting PlanesObjective Function FormulationSatisfiability
Core-guided techniques have revolutionized Boolean satisfiability approaches to optimization problems (MaxSAT), but the process at the heart of these methods, strengthening bounds on solutions by repeatedly adding cardinality constraints, remains a bottleneck. Cardinality constraints require significant work to be re-encoded to SAT, and SAT solvers are notoriously weak at cardinality reasoning. In this work, we lift core-guided search to pseudo-Boolean (PB) solvers, which deal with more general PB optimization problems and operate natively with cardinality constraints. The cutting planes method used in such solvers allows us to derive stronger cardinality constraints, which yield better updates to solution bounds, and the increased efficiency of objective function reformulation also makes it feasible to switch repeatedly between lower-bounding and upper- bounding search. A thorough evaluation on applied and crafted benchmarks shows that our core-guided PB solver significantly improves on the state of the art in pseudo-Boolean optimization.
23
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
The intractability of resolution
Armin Haken · Theoretical Computer Science · 1985 · 829 citations
Frontiers in Artificial Intelligence and Applications
Jaya Yadav, Shruti Shukla, Kanika Sharma et al. · 2022 · 661 citations
Using CSP look-back techniques to solve real-world SAT instances
Roberto J. Bayardo, Robert Schrag · 1997 · 598 citations