Design, Automation, and Test in Europe · 2005 · 45 citations · 20 references
ComputingComputer ScienceAlgorithmsDesign AutomationOptimizationConstraint SatisfactionHeuristic OptimizationHeuristic SearchSearching AlgorithmsBoolean SatisfiabilityBoolean Satisfiability ProblemSearch Priority SettingSearch StrategiesSequential SearchState Variables
A sequential SAT solver, Satori, was recently proposed (Iyer, M.K. et al., Proc. IEEE/ACM Int. Conf. on Computer-Aided Design, 2003) as an alternative to combinational SAT in verification applications. This paper describes the design of Seq-SAT, an efficient sequential SAT solver with improved search strategies over Satori. The major improvements include: (1) a new and better heuristic for minimizing the set of assignments to state variables; (2) a new priority-based search strategy and a flexible sequential search framework which integrates different search strategies; (3) a decision variable selection heuristic more suitable for solving the sequential problems. We present experimental results to demonstrate that our sequential SAT solver can achieve orders-of-magnitude speedup over Satori. We plan to release the source code of Seq-SAT.
20
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations
Symbolic model checking using SAT procedures instead of BDDs
Armin Biere, Alessandro Cimatti, E. M. Clarke et al. · 1999 · 697 citations
Efficient Conflict Driven Learning in a Boolean Satisfiability Solver
2001 · 666 citations