Extending modern SAT solvers for models enumeration
- 1 August 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 803-810
Abstract
In this paper, we address the problem of enumerating all models of a Boolean formula in conjunctive normal form (CNF). We propose an extension of Conflict Driven Clause Learning (CDCL) based SAT solvers to deal with this fundamental problem. Then, we provide an experimental evaluation of our proposed SAT model enumeration algorithms on both satisfiable SAT instances taken from the last SAT challenge and on instances from the SAT-based encoding of sequence mining problems.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Itemset mining: A constraint programming perspectiveArtificial Intelligence, 2011
- Enumerating All Solutions of a Boolean CSP by Non-decreasing WeightLecture Notes in Computer Science, 2011
- Constraint Programming for Data Mining and Machine LearningProceedings of the AAAI Conference on Artificial Intelligence, 2010
- ASIG: An all-solution SAT solver for CNF formulas2009
- Conflict-Driven Answer Set Enumeration2007
- An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequenceJournal of Combinatorial Optimization, 2006
- Efficient Conflict Analysis for Finding All Satisfying Assignments of a Boolean Circuit2005
- ASSAT: computing answer sets of a logic program by SAT solversArtificial Intelligence, 2004
- GRASP-A new search algorithm for satisfiability2002
- A machine program for theorem-provingCommunications of the ACM, 1962