Importing MiniSat2 070721 into trunk

4 files changed, 1287 insertions, 0 deletions

diff --git a/src/prop/minisat/simp/Main.C b/src/prop/minisat/simp/Main.C
new file mode 100644
index 000000000..b6d194631
--- /dev/null
+++ b/src/prop/minisat/simp/Main.C
@@ -0,0 +1,415 @@
+/******************************************************************************************[Main.C]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#include <ctime>
+#include <cstring>
+#include <stdint.h>
+#include <errno.h>
+
+#include <signal.h>
+#include <zlib.h>
+
+#include "SimpSolver.h"
+
+/*************************************************************************************/
+#ifdef _MSC_VER
+#include <ctime>
+
+static inline double cpuTime(void) {
+    return (double)clock() / CLOCKS_PER_SEC; }
+#else
+
+#include <sys/time.h>
+#include <sys/resource.h>
+#include <unistd.h>
+
+static inline double cpuTime(void) {
+    struct rusage ru;
+    getrusage(RUSAGE_SELF, &ru);
+    return (double)ru.ru_utime.tv_sec + (double)ru.ru_utime.tv_usec / 1000000; }
+#endif
+
+
+#if defined(__linux__)
+static inline int memReadStat(int field)
+{
+    char    name[256];
+    pid_t pid = getpid();
+    sprintf(name, "/proc/%d/statm", pid);
+    FILE*   in = fopen(name, "rb");
+    if (in == NULL) return 0;
+    int     value;
+    for (; field >= 0; field--)
+        fscanf(in, "%d", &value);
+    fclose(in);
+    return value;
+}
+static inline uint64_t memUsed() { return (uint64_t)memReadStat(0) * (uint64_t)getpagesize(); }
+
+
+#elif defined(__FreeBSD__)
+static inline uint64_t memUsed(void) {
+    struct rusage ru;
+    getrusage(RUSAGE_SELF, &ru);
+    return ru.ru_maxrss*1024; }
+
+
+#else
+static inline uint64_t memUsed() { return 0; }
+#endif
+
+#if defined(__linux__)
+#include <fpu_control.h>
+#endif
+
+
+//=================================================================================================
+// DIMACS Parser:
+
+#define CHUNK_LIMIT 1048576
+
+class StreamBuffer {
+    gzFile  in;
+    char    buf[CHUNK_LIMIT];
+    int     pos;
+    int     size;
+
+    void assureLookahead() {
+        if (pos >= size) {
+            pos  = 0;
+            size = gzread(in, buf, sizeof(buf)); } }
+
+public:
+    StreamBuffer(gzFile i) : in(i), pos(0), size(0) {
+        assureLookahead(); }
+
+    int  operator *  () { return (pos >= size) ? EOF : buf[pos]; }
+    void operator ++ () { pos++; assureLookahead(); }
+};
+
+//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+
+template<class B>
+static void skipWhitespace(B& in) {
+    while ((*in >= 9 && *in <= 13) || *in == 32)
+        ++in; }
+
+template<class B>
+static void skipLine(B& in) {
+    for (;;){
+        if (*in == EOF || *in == '\0') return;
+        if (*in == '\n') { ++in; return; }
+        ++in; } }
+
+template<class B>
+static int parseInt(B& in) {
+    int     val = 0;
+    bool    neg = false;
+    skipWhitespace(in);
+    if      (*in == '-') neg = true, ++in;
+    else if (*in == '+') ++in;
+    if (*in < '0' || *in > '9') reportf("PARSE ERROR! Unexpected char: %c\n", *in), exit(3);
+    while (*in >= '0' && *in <= '9')
+        val = val*10 + (*in - '0'),
+        ++in;
+    return neg ? -val : val; }
+
+template<class B>
+static void readClause(B& in, SimpSolver& S, vec<Lit>& lits) {
+    int     parsed_lit, var;
+    lits.clear();
+    for (;;){
+        parsed_lit = parseInt(in);
+        if (parsed_lit == 0) break;
+        var = abs(parsed_lit)-1;
+        while (var >= S.nVars()) S.newVar();
+        lits.push( (parsed_lit > 0) ? Lit(var) : ~Lit(var) );
+    }
+}
+
+template<class B>
+static bool match(B& in, char* str) {
+    for (; *str != 0; ++str, ++in)
+        if (*str != *in)
+            return false;
+    return true;
+}
+
+
+template<class B>
+static void parse_DIMACS_main(B& in, SimpSolver& S) {
+    vec<Lit> lits;
+    for (;;){
+        skipWhitespace(in);
+        if (*in == EOF) break;
+        else if (*in == 'p'){
+            if (match(in, "p cnf")){
+                int vars    = parseInt(in);
+                int clauses = parseInt(in);
+                reportf("|  Number of variables:  %-12d                                         |\n", vars);
+                reportf("|  Number of clauses:    %-12d                                         |\n", clauses);
+
+                // SATRACE'06 hack
+                if (clauses > 4000000)
+                    S.eliminate(true);
+            }else{
+                reportf("PARSE ERROR! Unexpected char: %c\n", *in), exit(3);
+            }
+        } else if (*in == 'c' || *in == 'p')
+            skipLine(in);
+        else{
+            readClause(in, S, lits);
+            S.addClause(lits); }
+    }
+}
+
+// Inserts problem into solver.
+//
+static void parse_DIMACS(gzFile input_stream, SimpSolver& S) {
+    StreamBuffer in(input_stream);
+    parse_DIMACS_main(in, S); }
+
+
+//=================================================================================================
+
+
+void printStats(Solver& S)
+{
+    double   cpu_time = cpuTime();
+    uint64_t mem_used = memUsed();
+    reportf("restarts              : %lld\n", S.starts);
+    reportf("conflicts             : %-12lld   (%.0f /sec)\n", S.conflicts   , S.conflicts   /cpu_time);
+    reportf("decisions             : %-12lld   (%4.2f %% random) (%.0f /sec)\n", S.decisions, (float)S.rnd_decisions*100 / (float)S.decisions, S.decisions   /cpu_time);
+    reportf("propagations          : %-12lld   (%.0f /sec)\n", S.propagations, S.propagations/cpu_time);
+    reportf("conflict literals     : %-12lld   (%4.2f %% deleted)\n", S.tot_literals, (S.max_literals - S.tot_literals)*100 / (double)S.max_literals);
+    if (mem_used != 0) reportf("Memory used           : %.2f MB\n", mem_used / 1048576.0);
+    reportf("CPU time              : %g s\n", cpu_time);
+}
+
+SimpSolver* solver;
+static void SIGINT_handler(int signum) {
+    reportf("\n"); reportf("*** INTERRUPTED ***\n");
+    printStats(*solver);
+    reportf("\n"); reportf("*** INTERRUPTED ***\n");
+    exit(1); }
+
+
+//=================================================================================================
+// Main:
+
+void printUsage(char** argv)
+{
+    reportf("USAGE: %s [options] <input-file> <result-output-file>\n\n  where input may be either in plain or gzipped DIMACS.\n\n", argv[0]);
+    reportf("OPTIONS:\n\n");
+    reportf("  -pre           = {none,once}\n");
+    reportf("  -asymm\n");
+    reportf("  -rcheck\n");
+    reportf("  -grow          = <num> [ >0 ]\n");
+    reportf("  -polarity-mode = {true,false,rnd}\n");
+    reportf("  -decay         = <num> [ 0 - 1 ]\n");
+    reportf("  -rnd-freq      = <num> [ 0 - 1 ]\n");
+    reportf("  -dimacs        = <output-file>\n");
+    reportf("  -verbosity     = {0,1,2}\n");
+    reportf("\n");
+}
+
+typedef enum { pre_none, pre_once, pre_repeat } preprocessMode;
+
+const char* hasPrefix(const char* str, const char* prefix)
+{
+    int len = strlen(prefix);
+    if (strncmp(str, prefix, len) == 0)
+        return str + len;
+    else
+        return NULL;
+}
+
+
+int main(int argc, char** argv)
+{
+    reportf("This is MiniSat 2.0 beta\n");
+#if defined(__linux__)
+    fpu_control_t oldcw, newcw;
+    _FPU_GETCW(oldcw); newcw = (oldcw & ~_FPU_EXTENDED) | _FPU_DOUBLE; _FPU_SETCW(newcw);
+    reportf("WARNING: for repeatability, setting FPU to use double precision\n");
+#endif
+    preprocessMode pre    = pre_once;
+    const char*    dimacs = NULL;
+    const char*    freeze = NULL;
+    SimpSolver     S;
+    S.verbosity = 1;
+
+    // This just grew and grew, and I didn't have time to do sensible argument parsing yet :)
+    //
+    int         i, j;
+    const char* value;
+    for (i = j = 0; i < argc; i++){
+        if ((value = hasPrefix(argv[i], "-polarity-mode="))){
+            if (strcmp(value, "true") == 0)
+                S.polarity_mode = Solver::polarity_true;
+            else if (strcmp(value, "false") == 0)
+                S.polarity_mode = Solver::polarity_false;
+            else if (strcmp(value, "rnd") == 0)
+                S.polarity_mode = Solver::polarity_rnd;
+            else{
+                reportf("ERROR! unknown polarity-mode %s\n", value);
+                exit(0); }
+
+        }else if ((value = hasPrefix(argv[i], "-rnd-freq="))){
+            double rnd;
+            if (sscanf(value, "%lf", &rnd) <= 0 || rnd < 0 || rnd > 1){
+                reportf("ERROR! illegal rnd-freq constant %s\n", value);
+                exit(0); }
+            S.random_var_freq = rnd;
+
+        }else if ((value = hasPrefix(argv[i], "-decay="))){
+            double decay;
+            if (sscanf(value, "%lf", &decay) <= 0 || decay <= 0 || decay > 1){
+                reportf("ERROR! illegal decay constant %s\n", value);
+                exit(0); }
+            S.var_decay = 1 / decay;
+
+        }else if ((value = hasPrefix(argv[i], "-verbosity="))){
+            int verbosity = (int)strtol(value, NULL, 10);
+            if (verbosity == 0 && errno == EINVAL){
+                reportf("ERROR! illegal verbosity level %s\n", value);
+                exit(0); }
+            S.verbosity = verbosity;
+
+        }else if ((value = hasPrefix(argv[i], "-pre="))){
+            if (strcmp(value, "none") == 0)
+                pre = pre_none;
+            else if (strcmp(value, "once") == 0)
+                pre = pre_once;
+            else if (strcmp(value, "repeat") == 0){
+                pre = pre_repeat;
+                reportf("ERROR! preprocessing mode \"repeat\" is not supported at the moment.\n");
+                exit(0);
+            }else{
+                reportf("ERROR! unknown preprocessing mode %s\n", value);
+                exit(0); }
+        }else if (strcmp(argv[i], "-asymm") == 0){
+            S.asymm_mode = true;
+        }else if (strcmp(argv[i], "-rcheck") == 0){
+            S.redundancy_check = true;
+        }else if ((value = hasPrefix(argv[i], "-grow="))){
+            int grow = (int)strtol(value, NULL, 10);
+            if (grow == 0 && errno == EINVAL){
+                reportf("ERROR! illegal grow constant %s\n", &argv[i][6]);
+                exit(0); }
+            S.grow = grow;
+        }else if ((value = hasPrefix(argv[i], "-dimacs="))){
+            dimacs = value;
+        }else if ((value = hasPrefix(argv[i], "-freeze="))){
+            freeze = value;
+        }else if (strcmp(argv[i], "-h") == 0 || strcmp(argv[i], "-help") == 0){
+            printUsage(argv);
+            exit(0);
+        }else if (strncmp(argv[i], "-", 1) == 0){
+            reportf("ERROR! unknown flag %s\n", argv[i]);
+            exit(0);
+        }else
+            argv[j++] = argv[i];
+    }
+    argc = j;
+
+    double cpu_time = cpuTime();
+
+    if (pre == pre_none)
+        S.eliminate(true);
+
+    solver = &S;
+    signal(SIGINT,SIGINT_handler);
+    signal(SIGHUP,SIGINT_handler);
+
+    if (argc == 1)
+        reportf("Reading from standard input... Use '-h' or '--help' for help.\n");
+
+    gzFile in = (argc == 1) ? gzdopen(0, "rb") : gzopen(argv[1], "rb");
+    if (in == NULL)
+        reportf("ERROR! Could not open file: %s\n", argc == 1 ? "<stdin>" : argv[1]), exit(1);
+
+    reportf("============================[ Problem Statistics ]=============================\n");
+    reportf("|                                                                             |\n");
+
+    parse_DIMACS(in, S);
+    gzclose(in);
+    FILE* res = (argc >= 3) ? fopen(argv[2], "wb") : NULL;
+
+
+    double parse_time = cpuTime() - cpu_time;
+    reportf("|  Parsing time:         %-12.2f s                                       |\n", parse_time);
+
+    /*HACK: Freeze variables*/
+    if (freeze != NULL && pre != pre_none){
+        int   count = 0;
+        FILE* in = fopen(freeze, "rb");
+        for(;;){
+            Var x;
+            fscanf(in, "%d", &x);
+            if (x == 0) break;
+            x--;
+
+            /**/assert(S.n_occ[toInt(Lit(x))] + S.n_occ[toInt(~Lit(x))] != 0);
+            /**/assert(S.value(x) == l_Undef);
+            S.setFrozen(x, true);
+            count++;
+        }
+        fclose(in);
+        reportf("|  Frozen vars :         %-12.0f                                         |\n", (double)count);
+    }
+    /*END*/
+
+    if (!S.simplify()){
+        reportf("Solved by unit propagation\n");
+        if (res != NULL) fprintf(res, "UNSAT\n"), fclose(res);
+        printf("UNSATISFIABLE\n");
+        exit(20);
+    }
+
+    if (dimacs){
+        if (pre != pre_none)
+            S.eliminate(true);
+        reportf("==============================[ Writing DIMACS ]===============================\n");
+        S.toDimacs(dimacs);
+        printStats(S);
+        exit(0);
+    }else{
+        bool ret = S.solve(true, true);
+        printStats(S);
+        reportf("\n");
+
+        printf(ret ? "SATISFIABLE\n" : "UNSATISFIABLE\n");
+        if (res != NULL){
+            if (ret){
+                fprintf(res, "SAT\n");
+                for (int i = 0; i < S.nVars(); i++)
+                    if (S.model[i] != l_Undef)
+                        fprintf(res, "%s%s%d", (i==0)?"":" ", (S.model[i]==l_True)?"":"-", i+1);
+                fprintf(res, " 0\n");
+            }else
+                fprintf(res, "UNSAT\n");
+            fclose(res);
+        }
+#ifdef NDEBUG
+        exit(ret ? 10 : 20);     // (faster than "return", which will invoke the destructor for 'Solver')
+#endif
+    }
+
+}
diff --git a/src/prop/minisat/simp/Makefile b/src/prop/minisat/simp/Makefile
new file mode 100644
index 000000000..a1db4951b
--- /dev/null
+++ b/src/prop/minisat/simp/Makefile
@@ -0,0 +1,11 @@
+MTL       = ../mtl
+CORE      = ../core
+CHDRS     = $(wildcard *.h) $(wildcard $(MTL)/*.h)
+EXEC      = minisat
+CFLAGS    = -I$(MTL) -I$(CORE) -Wall -ffloat-store
+LFLAGS    = -lz
+
+CSRCS     = $(wildcard *.C)
+COBJS     = $(addsuffix .o, $(basename $(CSRCS))) $(CORE)/Solver.o
+
+include ../mtl/template.mk
diff --git a/src/prop/minisat/simp/SimpSolver.C b/src/prop/minisat/simp/SimpSolver.C
new file mode 100644
index 000000000..22121c31e
--- /dev/null
+++ b/src/prop/minisat/simp/SimpSolver.C
@@ -0,0 +1,700 @@
+/************************************************************************************[SimpSolver.C]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#include "Sort.h"
+#include "SimpSolver.h"
+
+
+//=================================================================================================
+// Constructor/Destructor:
+
+
+SimpSolver::SimpSolver() :
+    grow               (0)
+  , asymm_mode         (false)
+  , redundancy_check   (false)
+  , merges             (0)
+  , asymm_lits         (0)
+  , remembered_clauses (0)
+  , elimorder          (1)
+  , use_simplification (true)
+  , elim_heap          (ElimLt(n_occ))
+  , bwdsub_assigns     (0)
+{
+    vec<Lit> dummy(1,lit_Undef);
+    bwdsub_tmpunit   = Clause_new(dummy);
+    remove_satisfied = false;
+}
+
+
+SimpSolver::~SimpSolver()
+{
+    free(bwdsub_tmpunit);
+
+    // NOTE: elimtable.size() might be lower than nVars() at the moment
+    for (int i = 0; i < elimtable.size(); i++)
+        for (int j = 0; j < elimtable[i].eliminated.size(); j++)
+            free(elimtable[i].eliminated[j]);
+}
+
+
+Var SimpSolver::newVar(bool sign, bool dvar) {
+    Var v = Solver::newVar(sign, dvar);
+
+    if (use_simplification){
+        n_occ    .push(0);
+        n_occ    .push(0);
+        occurs   .push();
+        frozen   .push((char)false);
+        touched  .push(0);
+        elim_heap.insert(v);
+        elimtable.push();
+    }
+    return v; }
+
+
+
+bool SimpSolver::solve(const vec<Lit>& assumps, bool do_simp, bool turn_off_simp) {
+    vec<Var> extra_frozen;
+    bool     result = true;
+
+    do_simp &= use_simplification;
+
+    if (do_simp){
+        // Assumptions must be temporarily frozen to run variable elimination:
+        for (int i = 0; i < assumps.size(); i++){
+            Var v = var(assumps[i]);
+
+            // If an assumption has been eliminated, remember it.
+            if (isEliminated(v))
+                remember(v);
+
+            if (!frozen[v]){
+                // Freeze and store.
+                setFrozen(v, true);
+                extra_frozen.push(v);
+            } }
+
+        result = eliminate(turn_off_simp);
+    }
+
+    if (result)
+        result = Solver::solve(assumps);
+
+    if (result) {
+        extendModel();
+#ifndef NDEBUG
+        verifyModel();
+#endif
+    }
+
+    if (do_simp)
+        // Unfreeze the assumptions that were frozen:
+        for (int i = 0; i < extra_frozen.size(); i++)
+            setFrozen(extra_frozen[i], false);
+
+    return result;
+}
+
+
+
+bool SimpSolver::addClause(vec<Lit>& ps)
+{
+    for (int i = 0; i < ps.size(); i++)
+        if (isEliminated(var(ps[i])))
+            remember(var(ps[i]));
+
+    int nclauses = clauses.size();
+
+    if (redundancy_check && implied(ps))
+        return true;
+
+    if (!Solver::addClause(ps))
+        return false;
+
+    if (use_simplification && clauses.size() == nclauses + 1){
+        Clause& c = *clauses.last();
+
+        subsumption_queue.insert(&c);
+
+        for (int i = 0; i < c.size(); i++){
+            assert(occurs.size() > var(c[i]));
+            assert(!find(occurs[var(c[i])], &c));
+
+            occurs[var(c[i])].push(&c);
+            n_occ[toInt(c[i])]++;
+            touched[var(c[i])] = 1;
+            assert(elimtable[var(c[i])].order == 0);
+            if (elim_heap.inHeap(var(c[i])))
+                elim_heap.increase_(var(c[i]));
+        }
+    }
+
+    return true;
+}
+
+
+void SimpSolver::removeClause(Clause& c)
+{
+    assert(!c.learnt());
+
+    if (use_simplification)
+        for (int i = 0; i < c.size(); i++){
+            n_occ[toInt(c[i])]--;
+            updateElimHeap(var(c[i]));
+        }
+
+    detachClause(c);
+    c.mark(1);
+}
+
+
+bool SimpSolver::strengthenClause(Clause& c, Lit l)
+{
+    assert(decisionLevel() == 0);
+    assert(c.mark() == 0);
+    assert(!c.learnt());
+    assert(find(watches[toInt(~c[0])], &c));
+    assert(find(watches[toInt(~c[1])], &c));
+
+    // FIX: this is too inefficient but would be nice to have (properly implemented)
+    // if (!find(subsumption_queue, &c))
+    subsumption_queue.insert(&c);
+
+    // If l is watched, delete it from watcher list and watch a new literal
+    if (c[0] == l || c[1] == l){
+        Lit other = c[0] == l ? c[1] : c[0];
+        if (c.size() == 2){
+            removeClause(c);
+            c.strengthen(l);
+        }else{
+            c.strengthen(l);
+            remove(watches[toInt(~l)], &c);
+
+            // Add a watch for the correct literal
+            watches[toInt(~(c[1] == other ? c[0] : c[1]))].push(&c);
+
+            // !! this version assumes that remove does not change the order !!
+            //watches[toInt(~c[1])].push(&c);
+            clauses_literals -= 1;
+        }
+    }
+    else{
+        c.strengthen(l);
+        clauses_literals -= 1;
+    }
+
+    // if subsumption-indexing is active perform the necessary updates
+    if (use_simplification){
+        remove(occurs[var(l)], &c);
+        n_occ[toInt(l)]--;
+        updateElimHeap(var(l));
+    }
+
+    return c.size() == 1 ? enqueue(c[0]) && propagate() == NULL : true;
+}
+
+
+// Returns FALSE if clause is always satisfied ('out_clause' should not be used).
+bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v, vec<Lit>& out_clause)
+{
+    merges++;
+    out_clause.clear();
+
+    bool  ps_smallest = _ps.size() < _qs.size();
+    const Clause& ps =  ps_smallest ? _qs : _ps;
+    const Clause& qs =  ps_smallest ? _ps : _qs;
+
+    for (int i = 0; i < qs.size(); i++){
+        if (var(qs[i]) != v){
+            for (int j = 0; j < ps.size(); j++)
+                if (var(ps[j]) == var(qs[i]))
+                    if (ps[j] == ~qs[i])
+                        return false;
+                    else
+                        goto next;
+            out_clause.push(qs[i]);
+        }
+        next:;
+    }
+
+    for (int i = 0; i < ps.size(); i++)
+        if (var(ps[i]) != v)
+            out_clause.push(ps[i]);
+
+    return true;
+}
+
+
+// Returns FALSE if clause is always satisfied.
+bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v)
+{
+    merges++;
+
+    bool  ps_smallest = _ps.size() < _qs.size();
+    const Clause& ps =  ps_smallest ? _qs : _ps;
+    const Clause& qs =  ps_smallest ? _ps : _qs;
+    const Lit* __ps = (const Lit*)ps;
+    const Lit* __qs = (const Lit*)qs;
+
+    for (int i = 0; i < qs.size(); i++){
+        if (var(__qs[i]) != v){
+            for (int j = 0; j < ps.size(); j++)
+                if (var(__ps[j]) == var(__qs[i]))
+                    if (__ps[j] == ~__qs[i])
+                        return false;
+                    else
+                        goto next;
+        }
+        next:;
+    }
+
+    return true;
+}
+
+
+void SimpSolver::gatherTouchedClauses()
+{
+    //fprintf(stderr, "Gathering clauses for backwards subsumption\n");
+    int ntouched = 0;
+    for (int i = 0; i < touched.size(); i++)
+        if (touched[i]){
+            const vec<Clause*>& cs = getOccurs(i);
+            ntouched++;
+            for (int j = 0; j < cs.size(); j++)
+                if (cs[j]->mark() == 0){
+                    subsumption_queue.insert(cs[j]);
+                    cs[j]->mark(2);
+                }
+            touched[i] = 0;
+        }
+
+    //fprintf(stderr, "Touched variables %d of %d yields %d clauses to check\n", ntouched, touched.size(), clauses.size());
+    for (int i = 0; i < subsumption_queue.size(); i++)
+        subsumption_queue[i]->mark(0);
+}
+
+
+bool SimpSolver::implied(const vec<Lit>& c)
+{
+    assert(decisionLevel() == 0);
+
+    trail_lim.push(trail.size());
+    for (int i = 0; i < c.size(); i++)
+        if (value(c[i]) == l_True){
+            cancelUntil(0);
+            return false;
+        }else if (value(c[i]) != l_False){
+            assert(value(c[i]) == l_Undef);
+            uncheckedEnqueue(~c[i]);
+        }
+
+    bool result = propagate() != NULL;
+    cancelUntil(0);
+    return result;
+}
+
+
+// Backward subsumption + backward subsumption resolution
+bool SimpSolver::backwardSubsumptionCheck(bool verbose)
+{
+    int cnt = 0;
+    int subsumed = 0;
+    int deleted_literals = 0;
+    assert(decisionLevel() == 0);
+
+    while (subsumption_queue.size() > 0 || bwdsub_assigns < trail.size()){
+
+        // Check top-level assignments by creating a dummy clause and placing it in the queue:
+        if (subsumption_queue.size() == 0 && bwdsub_assigns < trail.size()){
+            Lit l = trail[bwdsub_assigns++];
+            (*bwdsub_tmpunit)[0] = l;
+            bwdsub_tmpunit->calcAbstraction();
+            assert(bwdsub_tmpunit->mark() == 0);
+            subsumption_queue.insert(bwdsub_tmpunit); }
+
+        Clause&  c = *subsumption_queue.peek(); subsumption_queue.pop();
+
+        if (c.mark()) continue;
+
+        if (verbose && verbosity >= 2 && cnt++ % 1000 == 0)
+            reportf("subsumption left: %10d (%10d subsumed, %10d deleted literals)\r", subsumption_queue.size(), subsumed, deleted_literals);
+
+        assert(c.size() > 1 || value(c[0]) == l_True);    // Unit-clauses should have been propagated before this point.
+
+        // Find best variable to scan:
+        Var best = var(c[0]);
+        for (int i = 1; i < c.size(); i++)
+            if (occurs[var(c[i])].size() < occurs[best].size())
+                best = var(c[i]);
+
+        // Search all candidates:
+        vec<Clause*>& _cs = getOccurs(best);
+        Clause**       cs = (Clause**)_cs;
+
+        for (int j = 0; j < _cs.size(); j++)
+            if (c.mark())
+                break;
+            else if (!cs[j]->mark() && cs[j] != &c){
+                Lit l = c.subsumes(*cs[j]);
+
+                if (l == lit_Undef)
+                    subsumed++, removeClause(*cs[j]);
+                else if (l != lit_Error){
+                    deleted_literals++;
+
+                    if (!strengthenClause(*cs[j], ~l))
+                        return false;
+
+                    // Did current candidate get deleted from cs? Then check candidate at index j again:
+                    if (var(l) == best)
+                        j--;
+                }
+            }
+    }
+
+    return true;
+}
+
+
+bool SimpSolver::asymm(Var v, Clause& c)
+{
+    assert(decisionLevel() == 0);
+
+    if (c.mark() || satisfied(c)) return true;
+
+    trail_lim.push(trail.size());
+    Lit l = lit_Undef;
+    for (int i = 0; i < c.size(); i++)
+        if (var(c[i]) != v && value(c[i]) != l_False)
+            uncheckedEnqueue(~c[i]);
+        else
+            l = c[i];
+
+    if (propagate() != NULL){
+        cancelUntil(0);
+        asymm_lits++;
+        if (!strengthenClause(c, l))
+            return false;
+    }else
+        cancelUntil(0);
+
+    return true;
+}
+
+
+bool SimpSolver::asymmVar(Var v)
+{
+    assert(!frozen[v]);
+    assert(use_simplification);
+
+    vec<Clause*>  pos, neg;
+    const vec<Clause*>& cls = getOccurs(v);
+
+    if (value(v) != l_Undef || cls.size() == 0)
+        return true;
+
+    for (int i = 0; i < cls.size(); i++)
+        if (!asymm(v, *cls[i]))
+            return false;
+
+    return backwardSubsumptionCheck();
+}
+
+
+void SimpSolver::verifyModel()
+{
+    bool failed = false;
+    int  cnt    = 0;
+    // NOTE: elimtable.size() might be lower than nVars() at the moment
+    for (int i = 0; i < elimtable.size(); i++)
+        if (elimtable[i].order > 0)
+            for (int j = 0; j < elimtable[i].eliminated.size(); j++){
+                cnt++;
+                Clause& c = *elimtable[i].eliminated[j];
+                for (int k = 0; k < c.size(); k++)
+                    if (modelValue(c[k]) == l_True)
+                        goto next;
+
+                reportf("unsatisfied clause: ");
+                printClause(*elimtable[i].eliminated[j]);
+                reportf("\n");
+                failed = true;
+            next:;
+            }
+
+    assert(!failed);
+    reportf("Verified %d eliminated clauses.\n", cnt);
+}
+
+
+bool SimpSolver::eliminateVar(Var v, bool fail)
+{
+    if (!fail && asymm_mode && !asymmVar(v))    return false;
+
+    const vec<Clause*>& cls = getOccurs(v);
+
+//  if (value(v) != l_Undef || cls.size() == 0) return true;
+    if (value(v) != l_Undef) return true;
+
+    // Split the occurrences into positive and negative:
+    vec<Clause*>  pos, neg;
+    for (int i = 0; i < cls.size(); i++)
+        (find(*cls[i], Lit(v)) ? pos : neg).push(cls[i]);
+
+    // Check if number of clauses decreases:
+    int cnt = 0;
+    for (int i = 0; i < pos.size(); i++)
+        for (int j = 0; j < neg.size(); j++)
+            if (merge(*pos[i], *neg[j], v) && ++cnt > cls.size() + grow)
+                return true;
+
+    // Delete and store old clauses:
+    setDecisionVar(v, false);
+    elimtable[v].order = elimorder++;
+    assert(elimtable[v].eliminated.size() == 0);
+    for (int i = 0; i < cls.size(); i++){
+        elimtable[v].eliminated.push(Clause_new(*cls[i]));
+        removeClause(*cls[i]); }
+
+    // Produce clauses in cross product:
+    int top = clauses.size();
+    vec<Lit> resolvent;
+    for (int i = 0; i < pos.size(); i++)
+        for (int j = 0; j < neg.size(); j++)
+            if (merge(*pos[i], *neg[j], v, resolvent) && !addClause(resolvent))
+                return false;
+
+    // DEBUG: For checking that a clause set is saturated with respect to variable elimination.
+    //        If the clause set is expected to be saturated at this point, this constitutes an
+    //        error.
+    if (fail){
+        reportf("eliminated var %d, %d <= %d\n", v+1, cnt, cls.size());
+        reportf("previous clauses:\n");
+        for (int i = 0; i < cls.size(); i++){
+            printClause(*cls[i]); reportf("\n"); }
+        reportf("new clauses:\n");
+        for (int i = top; i < clauses.size(); i++){
+            printClause(*clauses[i]); reportf("\n"); }
+        assert(0); }
+
+    return backwardSubsumptionCheck();
+}
+
+
+void SimpSolver::remember(Var v)
+{
+    assert(decisionLevel() == 0);
+    assert(isEliminated(v));
+
+    vec<Lit> clause;
+
+    // Re-activate variable:
+    elimtable[v].order = 0;
+    setDecisionVar(v, true); // Not good if the variable wasn't a decision variable before. Not sure how to fix this right now.
+
+    if (use_simplification)
+        updateElimHeap(v);
+
+    // Reintroduce all old clauses which may implicitly remember other clauses:
+    for (int i = 0; i < elimtable[v].eliminated.size(); i++){
+        Clause& c = *elimtable[v].eliminated[i];
+        clause.clear();
+        for (int j = 0; j < c.size(); j++)
+            clause.push(c[j]);
+
+        remembered_clauses++;
+        check(addClause(clause));
+        free(&c);
+    }
+
+    elimtable[v].eliminated.clear();
+}
+
+
+void SimpSolver::extendModel()
+{
+    vec<Var> vs;
+
+    // NOTE: elimtable.size() might be lower than nVars() at the moment
+    for (int v = 0; v < elimtable.size(); v++)
+        if (elimtable[v].order > 0)
+            vs.push(v);
+
+    sort(vs, ElimOrderLt(elimtable));
+
+    for (int i = 0; i < vs.size(); i++){
+        Var v = vs[i];
+        Lit l = lit_Undef;
+
+        for (int j = 0; j < elimtable[v].eliminated.size(); j++){
+            Clause& c = *elimtable[v].eliminated[j];
+
+            for (int k = 0; k < c.size(); k++)
+                if (var(c[k]) == v)
+                    l = c[k];
+                else if (modelValue(c[k]) != l_False)
+                    goto next;
+
+            assert(l != lit_Undef);
+            model[v] = lbool(!sign(l));
+            break;
+
+        next:;
+        }
+
+        if (model[v] == l_Undef)
+            model[v] = l_True;
+    }
+}
+
+
+bool SimpSolver::eliminate(bool turn_off_elim)
+{
+    if (!ok || !use_simplification)
+        return ok;
+
+    // Main simplification loop:
+    //assert(subsumption_queue.size() == 0);
+    //gatherTouchedClauses();
+    while (subsumption_queue.size() > 0 || elim_heap.size() > 0){
+
+        //fprintf(stderr, "subsumption phase: (%d)\n", subsumption_queue.size());
+        if (!backwardSubsumptionCheck(true))
+            return false;
+
+        //fprintf(stderr, "elimination phase:\n (%d)", elim_heap.size());
+        for (int cnt = 0; !elim_heap.empty(); cnt++){
+            Var elim = elim_heap.removeMin();
+
+            if (verbosity >= 2 && cnt % 100 == 0)
+                reportf("elimination left: %10d\r", elim_heap.size());
+
+            if (!frozen[elim] && !eliminateVar(elim))
+                return false;
+        }
+
+        assert(subsumption_queue.size() == 0);
+        gatherTouchedClauses();
+    }
+
+    // Cleanup:
+    cleanUpClauses();
+    order_heap.filter(VarFilter(*this));
+
+#ifdef INVARIANTS
+    // Check that no more subsumption is possible:
+    reportf("Checking that no more subsumption is possible\n");
+    for (int i = 0; i < clauses.size(); i++){
+        if (i % 1000 == 0)
+            reportf("left %10d\r", clauses.size() - i);
+
+        assert(clauses[i]->mark() == 0);
+        for (int j = 0; j < i; j++)
+            assert(clauses[i]->subsumes(*clauses[j]) == lit_Error);
+    }
+    reportf("done.\n");
+
+    // Check that no more elimination is possible:
+    reportf("Checking that no more elimination is possible\n");
+    for (int i = 0; i < nVars(); i++)
+        if (!frozen[i]) eliminateVar(i, true);
+    reportf("done.\n");
+    checkLiteralCount();
+#endif
+
+    // If no more simplification is needed, free all simplification-related data structures:
+    if (turn_off_elim){
+        use_simplification = false;
+        touched.clear(true);
+        occurs.clear(true);
+        n_occ.clear(true);
+        subsumption_queue.clear(true);
+        elim_heap.clear(true);
+        remove_satisfied = true;
+    }
+
+
+    return true;
+}
+
+
+void SimpSolver::cleanUpClauses()
+{
+    int      i , j;
+    vec<Var> dirty;
+    for (i = 0; i < clauses.size(); i++)
+        if (clauses[i]->mark() == 1){
+            Clause& c = *clauses[i];
+            for (int k = 0; k < c.size(); k++)
+                if (!seen[var(c[k])]){
+                    seen[var(c[k])] = 1;
+                    dirty.push(var(c[k]));
+                } }
+
+    for (i = 0; i < dirty.size(); i++){
+        cleanOcc(dirty[i]);
+        seen[dirty[i]] = 0; }
+
+    for (i = j = 0; i < clauses.size(); i++)
+        if (clauses[i]->mark() == 1)
+            free(clauses[i]);
+        else
+            clauses[j++] = clauses[i];
+    clauses.shrink(i - j);
+}
+
+
+//=================================================================================================
+// Convert to DIMACS:
+
+
+void SimpSolver::toDimacs(FILE* f, Clause& c)
+{
+    if (satisfied(c)) return;
+
+    for (int i = 0; i < c.size(); i++)
+        if (value(c[i]) != l_False)
+            fprintf(f, "%s%d ", sign(c[i]) ? "-" : "", var(c[i])+1);
+    fprintf(f, "0\n");
+}
+
+
+void SimpSolver::toDimacs(const char* file)
+{
+    assert(decisionLevel() == 0);
+    FILE* f = fopen(file, "wr");
+    if (f != NULL){
+
+        // Cannot use removeClauses here because it is not safe
+        // to deallocate them at this point. Could be improved.
+        int cnt = 0;
+        for (int i = 0; i < clauses.size(); i++)
+            if (!satisfied(*clauses[i]))
+                cnt++;
+
+        fprintf(f, "p cnf %d %d\n", nVars(), cnt);
+
+        for (int i = 0; i < clauses.size(); i++)
+            toDimacs(f, *clauses[i]);
+
+        fprintf(stderr, "Wrote %d clauses...\n", clauses.size());
+    }else
+        fprintf(stderr, "could not open file %s\n", file);
+}
diff --git a/src/prop/minisat/simp/SimpSolver.h b/src/prop/minisat/simp/SimpSolver.h
new file mode 100644
index 000000000..f1bf88240
--- /dev/null
+++ b/src/prop/minisat/simp/SimpSolver.h
@@ -0,0 +1,161 @@
+/************************************************************************************[SimpSolver.h]
+MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
+associated documentation files (the "Software"), to deal in the Software without restriction,
+including without limitation the rights to use, copy, modify, merge, publish, distribute,
+sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or
+substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
+NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
+OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+**************************************************************************************************/
+
+#ifndef SimpSolver_h
+#define SimpSolver_h
+
+#include <cstdio>
+
+#include "Queue.h"
+#include "Solver.h"
+
+
+class SimpSolver : public Solver {
+ public:
+    // Constructor/Destructor:
+    //
+    SimpSolver();
+    ~SimpSolver();
+
+    // Problem specification:
+    //
+    Var     newVar    (bool polarity = true, bool dvar = true);
+    bool    addClause (vec<Lit>& ps);
+
+    // Variable mode:
+    // 
+    void    setFrozen (Var v, bool b); // If a variable is frozen it will not be eliminated.
+
+    // Solving:
+    //
+    bool    solve     (const vec<Lit>& assumps, bool do_simp = true, bool turn_off_simp = false);
+    bool    solve     (bool do_simp = true, bool turn_off_simp = false);
+    bool    eliminate (bool turn_off_elim = false);  // Perform variable elimination based simplification. 
+
+    // Generate a (possibly simplified) DIMACS file:
+    //
+    void    toDimacs  (const char* file);
+
+    // Mode of operation:
+    //
+    int     grow;             // Allow a variable elimination step to grow by a number of clauses (default to zero).
+    bool    asymm_mode;       // Shrink clauses by asymmetric branching.
+    bool    redundancy_check; // Check if a clause is already implied. Prett costly, and subsumes subsumptions :)
+
+    // Statistics:
+    //
+    int     merges;
+    int     asymm_lits;
+    int     remembered_clauses;
+
+// protected:
+  public:
+
+    // Helper structures:
+    //
+    struct ElimData {
+        int          order;      // 0 means not eliminated, >0 gives an index in the elimination order
+        vec<Clause*> eliminated;
+        ElimData() : order(0) {} };
+
+    struct ElimOrderLt {
+        const vec<ElimData>& elimtable;
+        ElimOrderLt(const vec<ElimData>& et) : elimtable(et) {}
+        bool operator()(Var x, Var y) { return elimtable[x].order > elimtable[y].order; } };
+
+    struct ElimLt {
+        const vec<int>& n_occ;
+        ElimLt(const vec<int>& no) : n_occ(no) {}
+        int  cost      (Var x)        const { return n_occ[toInt(Lit(x))] * n_occ[toInt(~Lit(x))]; }
+        bool operator()(Var x, Var y) const { return cost(x) < cost(y); } };
+
+
+    // Solver state:
+    //
+    int                 elimorder;
+    bool                use_simplification;
+    vec<ElimData>       elimtable;
+    vec<char>           touched;
+    vec<vec<Clause*> >  occurs;
+    vec<int>            n_occ;
+    Heap<ElimLt>        elim_heap;
+    Queue<Clause*>      subsumption_queue;
+    vec<char>           frozen;
+    int                 bwdsub_assigns;
+
+    // Temporaries:
+    //
+    Clause*             bwdsub_tmpunit;
+
+    // Main internal methods:
+    //
+    bool          asymm                    (Var v, Clause& c);
+    bool          asymmVar                 (Var v);
+    void          updateElimHeap           (Var v);
+    void          cleanOcc                 (Var v);
+    vec<Clause*>& getOccurs                (Var x);
+    void          gatherTouchedClauses     ();
+    bool          merge                    (const Clause& _ps, const Clause& _qs, Var v, vec<Lit>& out_clause);
+    bool          merge                    (const Clause& _ps, const Clause& _qs, Var v);
+    bool          backwardSubsumptionCheck (bool verbose = false);
+    bool          eliminateVar             (Var v, bool fail = false);
+    void          remember                 (Var v);
+    void          extendModel              ();
+    void          verifyModel              ();
+
+    void          removeClause             (Clause& c);
+    bool          strengthenClause         (Clause& c, Lit l);
+    void          cleanUpClauses           ();
+    bool          implied                  (const vec<Lit>& c);
+    void          toDimacs                 (FILE* f, Clause& c);
+    bool          isEliminated             (Var v) const;
+
+};
+
+
+//=================================================================================================
+// Implementation of inline methods:
+
+inline void SimpSolver::updateElimHeap(Var v) {
+    if (elimtable[v].order == 0)
+        elim_heap.update(v); }
+
+inline void SimpSolver::cleanOcc(Var v) {
+    assert(use_simplification);
+    Clause **begin = (Clause**)occurs[v];
+    Clause **end = begin + occurs[v].size();
+    Clause **i, **j;
+    for (i = begin, j = end; i < j; i++)
+        if ((*i)->mark() == 1){
+            *i = *(--j);
+            i--;
+        }
+    //occurs[v].shrink_(end - j);  // This seems slower. Why?!
+    occurs[v].shrink(end - j);
+}
+
+inline vec<Clause*>& SimpSolver::getOccurs(Var x) {
+    cleanOcc(x); return occurs[x]; }
+
+inline bool  SimpSolver::isEliminated (Var v) const { return v < elimtable.size() && elimtable[v].order != 0; }
+inline void  SimpSolver::setFrozen    (Var v, bool b) { frozen[v] = (char)b; if (b) { updateElimHeap(v); } }
+inline bool  SimpSolver::solve        (bool do_simp, bool turn_off_simp) { vec<Lit> tmp; return solve(tmp, do_simp, turn_off_simp); }
+
+//=================================================================================================
+#endif