33 files changed, 3238 insertions, 2205 deletions

diff --git a/src/prop/minisat/LICENSE b/src/prop/minisat/LICENSE
index c87a32731..22816ff39 100644
--- a/src/prop/minisat/LICENSE
+++ b/src/prop/minisat/LICENSE
@@ -1,4 +1,5 @@
 MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+           Copyright (c) 2007-2010  Niklas Sorensson
 
 Permission is hereby granted, free of charge, to any person obtaining a
 copy of this software and associated documentation files (the
diff --git a/src/prop/minisat/Makefile.am b/src/prop/minisat/Makefile.am
index 56f61adad..3d7bb08df 100644
--- a/src/prop/minisat/Makefile.am
+++ b/src/prop/minisat/Makefile.am
@@ -1,29 +1,41 @@
 AM_CPPFLAGS = \
 	-D__BUILDING_CVC4LIB \
-	-I@srcdir@/mtl -I@srcdir@/core -I@srcdir@/../.. -I@builddir@/../.. -I@srcdir@/../../include
-AM_CXXFLAGS = -Wall -Wno-unknown-pragmas $(FLAG_VISIBILITY_HIDDEN) -DNDEBUG
+	-D __STDC_LIMIT_MACROS \
+	-D __STDC_FORMAT_MACROS \               	
+	-I@srcdir@/ -I@srcdir@/../.. -I@builddir@/../.. -I@srcdir@/../../include
+AM_CXXFLAGS = -Wall -Wno-parentheses -Wno-unknown-pragmas $(FLAG_VISIBILITY_HIDDEN) -DNDEBUG
 
 noinst_LTLIBRARIES = libminisat.la
 libminisat_la_SOURCES = \
-	core/Solver.C \
+	core/Dimacs.h \
+	core/Solver.cc \
 	core/Solver.h \
 	core/SolverTypes.h \
-	simp/SimpSolver.C \
+	simp/SimpSolver.cc \
 	simp/SimpSolver.h \
 	mtl/Alg.h \
-	mtl/BasicHeap.h \
-	mtl/BoxedVec.h \
+	mtl/Alloc.h \
 	mtl/Heap.h \
+	mtl/IntTypes.h \
 	mtl/Map.h \
 	mtl/Queue.h \
 	mtl/Sort.h \
-	mtl/Vec.h
+	mtl/Vec.h \
+	mtl/Xalloc.h \
+	util/Options.h 
 
 EXTRA_DIST = \
-	core/Main.C \
+	core/Main.cc \
 	core/Makefile \
-	simp/Main.C \
+	doc/ReleaseNotes-2.2.0.txt \
+	simp/Main.cc \
 	simp/Makefile \
 	README \
 	LICENSE \
-	mtl/template.mk
+	mtl/config.mk \
+	mtl/template.mk \
+	utils/ParseUtils.h \
+	utils/System.h \
+	utils/System.cc \
+	Makefile
+
diff --git a/src/prop/minisat/README b/src/prop/minisat/README
index e1b79329b..e5e5617d8 100644
--- a/src/prop/minisat/README
+++ b/src/prop/minisat/README
@@ -1,19 +1,24 @@
-Directory overview:
-==================
+================================================================================
+DIRECTORY OVERVIEW:
 
 mtl/            Mini Template Library
+utils/          Generic helper code (I/O, Parsing, CPU-time, etc)
 core/           A core version of the solver
 simp/           An extended solver with simplification capabilities
 README
 LICENSE
 
-To build (release version: without assertions, statically linked, etc):
-======================================================================
+================================================================================
+BUILDING: (release version: without assertions, statically linked, etc)
 
+export MROOT=<minisat-dir>              (or setenv in cshell)
 cd { core | simp }
 gmake rs
+cp minisat_static <install-dir>/minisat
 
-Usage:
-======
+================================================================================
+EXAMPLES:
 
-TODO
+Run minisat with same heuristics as version 2.0:
+
+> minisat <cnf-file> -no-luby -rinc=1.5 -phase-saving=0 -rnd-freq=0.02
diff --git a/src/prop/minisat/core/Dimacs.h b/src/prop/minisat/core/Dimacs.h
new file mode 100644
index 000000000..a05e900c1
--- /dev/null
+++ b/src/prop/minisat/core/Dimacs.h
@@ -0,0 +1,89 @@
+/****************************************************************************************[Dimacs.h]
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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 Minisat_Dimacs_h
+#define Minisat_Dimacs_h
+
+#include <stdio.h>
+
+#include "utils/ParseUtils.h"
+#include "core/SolverTypes.h"
+
+namespace Minisat {
+
+//=================================================================================================
+// DIMACS Parser:
+
+template<class B, class Solver>
+static void readClause(B& in, Solver& 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) ? mkLit(var) : ~mkLit(var) );
+    }
+}
+
+template<class B, class Solver>
+static void parse_DIMACS_main(B& in, Solver& S) {
+    vec<Lit> lits;
+    int vars    = 0;
+    int clauses = 0;
+    int cnt     = 0;
+    for (;;){
+        skipWhitespace(in);
+        if (*in == EOF) break;
+        else if (*in == 'p'){
+            if (eagerMatch(in, "p cnf")){
+                vars    = parseInt(in);
+                clauses = parseInt(in);
+                // SATRACE'06 hack
+                // if (clauses > 4000000)
+                //     S.eliminate(true);
+            }else{
+                printf("PARSE ERROR! Unexpected char: %c\n", *in), exit(3);
+            }
+        } else if (*in == 'c' || *in == 'p')
+            skipLine(in);
+        else{
+            cnt++;
+            readClause(in, S, lits);
+            S.addClause_(lits); }
+    }
+    if (vars != S.nVars())
+        fprintf(stderr, "WARNING! DIMACS header mismatch: wrong number of variables.\n");
+    if (cnt  != clauses)
+        fprintf(stderr, "WARNING! DIMACS header mismatch: wrong number of clauses.\n");
+}
+
+// Inserts problem into solver.
+//
+template<class Solver>
+static void parse_DIMACS(gzFile input_stream, Solver& S) {
+    StreamBuffer in(input_stream);
+    parse_DIMACS_main(in, S); }
+
+//=================================================================================================
+}
+
+#endif
diff --git a/src/prop/minisat/core/Main.cc b/src/prop/minisat/core/Main.cc
index acef32cd5..4388c3e08 100644
--- a/src/prop/minisat/core/Main.cc
+++ b/src/prop/minisat/core/Main.cc
@@ -1,5 +1,6 @@
-/******************************************************************************************[Main.C]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+/*****************************************************************************************[Main.cc]
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,328 +18,175 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 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 "Solver.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, Solver& 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, Solver& 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);
-            }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, Solver& S) {
-    StreamBuffer in(input_stream);
-    parse_DIMACS_main(in, S); }
+#include "utils/System.h"
+#include "utils/ParseUtils.h"
+#include "utils/Options.h"
+#include "core/Dimacs.h"
+#include "core/Solver.h"
 
+using namespace Minisat;
 
 //=================================================================================================
 
 
 void printStats(Solver& solver)
 {
-    double   cpu_time = cpuTime();
-    uint64_t mem_used = memUsed();
-    reportf("restarts              : %lld\n", solver.starts);
-    reportf("conflicts             : %-12lld   (%.0f /sec)\n", solver.conflicts   , solver.conflicts   /cpu_time);
-    reportf("decisions             : %-12lld   (%4.2f %% random) (%.0f /sec)\n", solver.decisions, (float)solver.rnd_decisions*100 / (float)solver.decisions, solver.decisions   /cpu_time);
-    reportf("propagations          : %-12lld   (%.0f /sec)\n", solver.propagations, solver.propagations/cpu_time);
-    reportf("conflict literals     : %-12lld   (%4.2f %% deleted)\n", solver.tot_literals, (solver.max_literals - solver.tot_literals)*100 / (double)solver.max_literals);
-    if (mem_used != 0) reportf("Memory used           : %.2f MB\n", mem_used / 1048576.0);
-    reportf("CPU time              : %g s\n", cpu_time);
+    double cpu_time = cpuTime();
+    double mem_used = memUsedPeak();
+    printf("restarts              : %"PRIu64"\n", solver.starts);
+    printf("conflicts             : %-12"PRIu64"   (%.0f /sec)\n", solver.conflicts   , solver.conflicts   /cpu_time);
+    printf("decisions             : %-12"PRIu64"   (%4.2f %% random) (%.0f /sec)\n", solver.decisions, (float)solver.rnd_decisions*100 / (float)solver.decisions, solver.decisions   /cpu_time);
+    printf("propagations          : %-12"PRIu64"   (%.0f /sec)\n", solver.propagations, solver.propagations/cpu_time);
+    printf("conflict literals     : %-12"PRIu64"   (%4.2f %% deleted)\n", solver.tot_literals, (solver.max_literals - solver.tot_literals)*100 / (double)solver.max_literals);
+    if (mem_used != 0) printf("Memory used           : %.2f MB\n", mem_used);
+    printf("CPU time              : %g s\n", cpu_time);
 }
 
-Solver* solver;
-static void SIGINT_handler(int signum) {
-    reportf("\n"); reportf("*** INTERRUPTED ***\n");
-    printStats(*solver);
-    reportf("\n"); reportf("*** INTERRUPTED ***\n");
-    exit(1); }
-
 
-//=================================================================================================
-// Main:
+static Solver* solver;
+// Terminate by notifying the solver and back out gracefully. This is mainly to have a test-case
+// for this feature of the Solver as it may take longer than an immediate call to '_exit()'.
+static void SIGINT_interrupt(int signum) { solver->interrupt(); }
 
-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("  -polarity-mode = {true,false,rnd}\n");
-    reportf("  -decay         = <num> [ 0 - 1 ]\n");
-    reportf("  -rnd-freq      = <num> [ 0 - 1 ]\n");
-    reportf("  -verbosity     = {0,1,2}\n");
-    reportf("\n");
-}
+// Note that '_exit()' rather than 'exit()' has to be used. The reason is that 'exit()' calls
+// destructors and may cause deadlocks if a malloc/free function happens to be running (these
+// functions are guarded by locks for multithreaded use).
+static void SIGINT_exit(int signum) {
+    printf("\n"); printf("*** INTERRUPTED ***\n");
+    if (solver->verbosity > 0){
+        printStats(*solver);
+        printf("\n"); printf("*** INTERRUPTED ***\n"); }
+    _exit(1); }
 
 
-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;
-}
+//=================================================================================================
+// Main:
 
 
 int main(int argc, char** argv)
 {
-    Solver      S;
-    S.verbosity = 1;
-
-
-    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 (strcmp(argv[i], "-h") == 0 || strcmp(argv[i], "-help") == 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;
-
-
-    reportf("This is MiniSat 2.0 beta\n");
+    try {
+        setUsageHelp("USAGE: %s [options] <input-file> <result-output-file>\n\n  where input may be either in plain or gzipped DIMACS.\n");
+        // printf("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");
+        fpu_control_t oldcw, newcw;
+        _FPU_GETCW(oldcw); newcw = (oldcw & ~_FPU_EXTENDED) | _FPU_DOUBLE; _FPU_SETCW(newcw);
+        printf("WARNING: for repeatability, setting FPU to use double precision\n");
 #endif
-    double cpu_time = cpuTime();
-
-    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);
-
-    if (!S.simplify()){
-        reportf("Solved by unit propagation\n");
-        if (res != NULL) fprintf(res, "UNSAT\n"), fclose(res);
-        printf("UNSATISFIABLE\n");
-        exit(20);
-    }
-
-    bool ret = S.solve();
-    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);
-    }
-
+        // Extra options:
+        //
+        IntOption    verb   ("MAIN", "verb",   "Verbosity level (0=silent, 1=some, 2=more).", 1, IntRange(0, 2));
+        IntOption    cpu_lim("MAIN", "cpu-lim","Limit on CPU time allowed in seconds.\n", INT32_MAX, IntRange(0, INT32_MAX));
+        IntOption    mem_lim("MAIN", "mem-lim","Limit on memory usage in megabytes.\n", INT32_MAX, IntRange(0, INT32_MAX));
+        
+        parseOptions(argc, argv, true);
+
+        Solver S;
+        double initial_time = cpuTime();
+
+        S.verbosity = verb;
+        
+        solver = &S;
+        // Use signal handlers that forcibly quit until the solver will be able to respond to
+        // interrupts:
+        signal(SIGINT, SIGINT_exit);
+        signal(SIGXCPU,SIGINT_exit);
+
+        // Set limit on CPU-time:
+        if (cpu_lim != INT32_MAX){
+            rlimit rl;
+            getrlimit(RLIMIT_CPU, &rl);
+            if (rl.rlim_max == RLIM_INFINITY || (rlim_t)cpu_lim < rl.rlim_max){
+                rl.rlim_cur = cpu_lim;
+                if (setrlimit(RLIMIT_CPU, &rl) == -1)
+                    printf("WARNING! Could not set resource limit: CPU-time.\n");
+            } }
+
+        // Set limit on virtual memory:
+        if (mem_lim != INT32_MAX){
+            rlim_t new_mem_lim = (rlim_t)mem_lim * 1024*1024;
+            rlimit rl;
+            getrlimit(RLIMIT_AS, &rl);
+            if (rl.rlim_max == RLIM_INFINITY || new_mem_lim < rl.rlim_max){
+                rl.rlim_cur = new_mem_lim;
+                if (setrlimit(RLIMIT_AS, &rl) == -1)
+                    printf("WARNING! Could not set resource limit: Virtual memory.\n");
+            } }
+        
+        if (argc == 1)
+            printf("Reading from standard input... Use '--help' for help.\n");
+        
+        gzFile in = (argc == 1) ? gzdopen(0, "rb") : gzopen(argv[1], "rb");
+        if (in == NULL)
+            printf("ERROR! Could not open file: %s\n", argc == 1 ? "<stdin>" : argv[1]), exit(1);
+        
+        if (S.verbosity > 0){
+            printf("============================[ Problem Statistics ]=============================\n");
+            printf("|                                                                             |\n"); }
+        
+        parse_DIMACS(in, S);
+        gzclose(in);
+        FILE* res = (argc >= 3) ? fopen(argv[2], "wb") : NULL;
+        
+        if (S.verbosity > 0){
+            printf("|  Number of variables:  %12d                                         |\n", S.nVars());
+            printf("|  Number of clauses:    %12d                                         |\n", S.nClauses()); }
+        
+        double parsed_time = cpuTime();
+        if (S.verbosity > 0){
+            printf("|  Parse time:           %12.2f s                                       |\n", parsed_time - initial_time);
+            printf("|                                                                             |\n"); }
+ 
+        // Change to signal-handlers that will only notify the solver and allow it to terminate
+        // voluntarily:
+        signal(SIGINT, SIGINT_interrupt);
+        signal(SIGXCPU,SIGINT_interrupt);
+       
+        if (!S.simplify()){
+            if (res != NULL) fprintf(res, "UNSAT\n"), fclose(res);
+            if (S.verbosity > 0){
+                printf("===============================================================================\n");
+                printf("Solved by unit propagation\n");
+                printStats(S);
+                printf("\n"); }
+            printf("UNSATISFIABLE\n");
+            exit(20);
+        }
+        
+        vec<Lit> dummy;
+        lbool ret = S.solveLimited(dummy);
+        if (S.verbosity > 0){
+            printStats(S);
+            printf("\n"); }
+        printf(ret == l_True ? "SATISFIABLE\n" : ret == l_False ? "UNSATISFIABLE\n" : "INDETERMINATE\n");
+        if (res != NULL){
+            if (ret == l_True){
+                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 if (ret == l_False)
+                fprintf(res, "UNSAT\n");
+            else
+                fprintf(res, "INDET\n");
+            fclose(res);
+        }
+        
 #ifdef NDEBUG
-    exit(ret ? 10 : 20);     // (faster than "return", which will invoke the destructor for 'Solver')
+        exit(ret == l_True ? 10 : ret == l_False ? 20 : 0);     // (faster than "return", which will invoke the destructor for 'Solver')
+#else
+        return (ret == l_True ? 10 : ret == l_False ? 20 : 0);
 #endif
+    } catch (OutOfMemoryException&){
+        printf("===============================================================================\n");
+        printf("INDETERMINATE\n");
+        exit(0);
+    }
 }
diff --git a/src/prop/minisat/core/Makefile b/src/prop/minisat/core/Makefile
index 42128c6d6..5de1f7295 100644
--- a/src/prop/minisat/core/Makefile
+++ b/src/prop/minisat/core/Makefile
@@ -1,7 +1,4 @@
-MTL       = ../mtl
-CHDRS     = $(wildcard *.h) $(wildcard $(MTL)/*.h)
 EXEC      = minisat
-CFLAGS    = -I$(MTL) -Wall -ffloat-store
-LFLAGS    = -lz
+DEPDIR    = mtl utils
 
-include ../mtl/template.mk
+include $(MROOT)/mtl/template.mk
diff --git a/src/prop/minisat/core/Solver.cc b/src/prop/minisat/core/Solver.cc
index 1667af20d..0da9fc249 100644
--- a/src/prop/minisat/core/Solver.cc
+++ b/src/prop/minisat/core/Solver.cc
@@ -1,5 +1,6 @@
-/****************************************************************************************[Solver.C]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+/***************************************************************************************[Solver.cc]
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,78 +18,92 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
-#include "Solver.h"
-#include "Sort.h"
+#include <math.h>
+
+#include "mtl/Sort.h"
+#include "core/Solver.h"
 #include "prop/sat.h"
-#include <cmath>
+
+using namespace Minisat;
+using namespace CVC4;
+using namespace CVC4::prop;
 
 //=================================================================================================
-// Constructor/Destructor:
+// Options:
 
-namespace CVC4 {
-namespace prop {
-namespace minisat {
 
-Clause* Solver::lazy_reason = reinterpret_cast<Clause*>(1);
+static const char* _cat = "CORE";
+
+static DoubleOption  opt_var_decay         (_cat, "var-decay",   "The variable activity decay factor",            0.95,     DoubleRange(0, false, 1, false));
+static DoubleOption  opt_clause_decay      (_cat, "cla-decay",   "The clause activity decay factor",              0.999,    DoubleRange(0, false, 1, false));
+static DoubleOption  opt_random_var_freq   (_cat, "rnd-freq",    "The frequency with which the decision heuristic tries to choose a random variable", 0, DoubleRange(0, true, 1, true));
+static DoubleOption  opt_random_seed       (_cat, "rnd-seed",    "Used by the random variable selection",         91648253, DoubleRange(0, false, HUGE_VAL, false));
+static IntOption     opt_ccmin_mode        (_cat, "ccmin-mode",  "Controls conflict clause minimization (0=none, 1=basic, 2=deep)", 2, IntRange(0, 2));
+static IntOption     opt_phase_saving      (_cat, "phase-saving", "Controls the level of phase saving (0=none, 1=limited, 2=full)", 2, IntRange(0, 2));
+static BoolOption    opt_rnd_init_act      (_cat, "rnd-init",    "Randomize the initial activity", false);
+static BoolOption    opt_luby_restart      (_cat, "luby",        "Use the Luby restart sequence", true);
+static IntOption     opt_restart_first     (_cat, "rfirst",      "The base restart interval", 100, IntRange(1, INT32_MAX));
+static DoubleOption  opt_restart_inc       (_cat, "rinc",        "Restart interval increase factor", 2, DoubleRange(1, false, HUGE_VAL, false));
+static DoubleOption  opt_garbage_frac      (_cat, "gc-frac",     "The fraction of wasted memory allowed before a garbage collection is triggered",  0.20, DoubleRange(0, false, HUGE_VAL, false));
 
-Clause* Solver::getReason(Lit l)
-{
-    if (reason[var(l)] != lazy_reason) return reason[var(l)];
-    // Get the explanation from the theory
-    SatClause explanation;
-    if (value(l) == l_True) {
-      proxy->explainPropagation(l, explanation);
-      assert(explanation[0] == l);
-    } else {
-      proxy->explainPropagation(~l, explanation);
-      assert(explanation[0] == ~l);
-    }
-    Clause* real_reason = Clause_new(explanation, true);
-    reason[var(l)] = real_reason;
-    // Add it to the database
-    learnts.push(real_reason);
-    attachClause(*real_reason);
-    return real_reason;
-}
 
-Solver::Solver(SatSolver* proxy, context::Context* context) :
+//=================================================================================================
+// Constructor/Destructor:
 
-    // SMT stuff
+Solver::Solver(CVC4::prop::SatSolver* proxy, CVC4::context::Context* context) :
     proxy(proxy)
   , context(context)
-
-    // Parameters: (formerly in 'SearchParams')
-  , var_decay(1 / 0.95), clause_decay(1 / 0.999), random_var_freq(0.02)
-  , restart_first(100), restart_inc(1.5), learntsize_factor((double)1/(double)3), learntsize_inc(1.1)
-
-    // More parameters:
+    // Parameters (user settable):
     //
-  , expensive_ccmin  (true)
-  , polarity_mode    (polarity_false)
   , verbosity        (0)
+  , var_decay        (opt_var_decay)
+  , clause_decay     (opt_clause_decay)
+  , random_var_freq  (opt_random_var_freq)
+  , random_seed      (opt_random_seed)
+  , luby_restart     (opt_luby_restart)
+  , ccmin_mode       (opt_ccmin_mode)
+  , phase_saving     (opt_phase_saving)
+  , rnd_pol          (false)
+  , rnd_init_act     (opt_rnd_init_act)
+  , garbage_frac     (opt_garbage_frac)
+  , restart_first    (opt_restart_first)
+  , restart_inc      (opt_restart_inc)
+
+    // Parameters (the rest):
+    //
+  , learntsize_factor((double)1/(double)3), learntsize_inc(1.1)
+
+    // Parameters (experimental):
+    //
+  , learntsize_adjust_start_confl (100)
+  , learntsize_adjust_inc         (1.5)
 
     // Statistics: (formerly in 'SolverStats')
     //
-  , starts(0), decisions(0), rnd_decisions(0), propagations(0), conflicts(0)
-  , clauses_literals(0), learnts_literals(0), max_literals(0), tot_literals(0)
-
-  , ok               (true)
-  , cla_inc          (1)
-  , var_inc          (1)
-  , qhead            (0)
-  , simpDB_assigns   (-1)
-  , simpDB_props     (0)
-  , order_heap       (VarOrderLt(activity))
-  , random_seed      (91648253)
-  , progress_estimate(0)
-  , remove_satisfied (true)
+  , solves(0), starts(0), decisions(0), rnd_decisions(0), propagations(0), conflicts(0)
+  , dec_vars(0), clauses_literals(0), learnts_literals(0), max_literals(0), tot_literals(0)
+
+  , ok                 (true)
+  , cla_inc            (1)
+  , var_inc            (1)
+  , watches            (WatcherDeleted(ca))
+  , qhead              (0)
+  , simpDB_assigns     (-1)
+  , simpDB_props       (0)
+  , order_heap         (VarOrderLt(activity))
+  , progress_estimate  (0)
+  , remove_satisfied   (true)
+
+    // Resource constraints:
+    //
+  , conflict_budget    (-1)
+  , propagation_budget (-1)
+  , asynch_interrupt   (false)
 {}
 
 
 Solver::~Solver()
 {
-    for (int i = 0; i < learnts.size(); i++) free(learnts[i]);
-    for (int i = 0; i < clauses.size(); i++) free(clauses[i]);
 }
 
 
@@ -102,41 +117,59 @@ Solver::~Solver()
 Var Solver::newVar(bool sign, bool dvar, bool theoryAtom)
 {
     int v = nVars();
-    watches   .push();          // (list for positive literal)
-    watches   .push();          // (list for negative literal)
-    reason    .push(NULL);
-    assigns   .push(toInt(l_Undef));
-    level     .push(-1);
-    activity  .push(0);
-    seen      .push(0);
+    watches  .init(mkLit(v, false));
+    watches  .init(mkLit(v, true ));
+    assigns  .push(l_Undef);
+    vardata  .push(mkVarData(CRef_Undef, 0));
+    //activity .push(0);
+    activity .push(rnd_init_act ? drand(random_seed) * 0.00001 : 0);
+    seen     .push(0);
+    polarity .push(sign);
+    decision .push();
+    trail    .capacity(v+1);
+    setDecisionVar(v, dvar);
+	theory   .push(theoryAtom);
+    return v;
+}
 
-    theory    .push(theoryAtom);
 
-    polarity    .push((char)sign);
-    decision_var.push((char)dvar);
+CRef Solver::reason(Var x) const {
+    // If we already have a reaspon, just return it
+    if (vardata[x].reason != CRef_Lazy) return vardata[x].reason;
 
-    insertVarOrder(v);
-    return v;
-}
+    // What's the literal we are trying to explain
+    Lit l = mkLit(x, value(x) != l_True);
 
+    // Get the explanation from the theory
+    SatClause explanation;
+    proxy->explainPropagation(l, explanation);
+    assert(explanation[0] == l);
 
-bool Solver::addClause(vec<Lit>& ps, ClauseType type)
+    // We're actually changing the state, so we hack it into non-const
+    Solver* nonconst_this = const_cast<Solver*>(this);
+
+    // Construct the reason
+    CRef real_reason = nonconst_this->ca.alloc(explanation, true);
+    nonconst_this->vardata[x] = mkVarData(real_reason, level(x));
+    nonconst_this->learnts.push(real_reason);
+    nonconst_this->attachClause(real_reason);
+    return real_reason;
+}
+
+bool Solver::addClause_(vec<Lit>& ps, ClauseType type)
 {
     assert(decisionLevel() == 0);
+    if (!ok) return false;
 
-    if (!ok)
-        return false;
-    else{
-        // Check if clause is satisfied and remove false/duplicate literals:
-        sort(ps);
-        Lit p; int i, j;
-        for (i = j = 0, p = lit_Undef; i < ps.size(); i++)
-            if (value(ps[i]) == l_True || ps[i] == ~p)
-                return true;
-            else if (value(ps[i]) != l_False && ps[i] != p)
-                ps[j++] = p = ps[i];
-        ps.shrink(i - j);
-    }
+    // Check if clause is satisfied and remove false/duplicate literals:
+    sort(ps);
+    Lit p; int i, j;
+    for (i = j = 0, p = lit_Undef; i < ps.size(); i++)
+        if (value(ps[i]) == l_True || ps[i] == ~p)
+            return true;
+        else if (value(ps[i]) != l_False && ps[i] != p)
+            ps[j++] = p = ps[i];
+    ps.shrink(i - j);
 
     if (ps.size() == 0)
         return ok = false;
@@ -144,42 +177,53 @@ bool Solver::addClause(vec<Lit>& ps, ClauseType type)
         assert(type != CLAUSE_LEMMA);
         assert(value(ps[0]) == l_Undef);
         uncheckedEnqueue(ps[0]);
-        return ok = (propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) == NULL);
+        return ok = (propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) == CRef_Undef);
     }else{
-        Clause* c = Clause_new(ps, false);
-        clauses.push(c);
-        if (type == CLAUSE_LEMMA) lemmas.push(c);
-        attachClause(*c);
+        CRef cr = ca.alloc(ps, false);
+        clauses.push(cr);
+	if (type == CLAUSE_LEMMA) lemmas.push(cr);
+        attachClause(cr);
     }
 
     return true;
-
 }
 
 
-void Solver::attachClause(Clause& c) {
+void Solver::attachClause(CRef cr) {
+    const Clause& c = ca[cr];
     assert(c.size() > 1);
-    watches[toInt(~c[0])].push(&c);
-    watches[toInt(~c[1])].push(&c);
+    watches[~c[0]].push(Watcher(cr, c[1]));
+    watches[~c[1]].push(Watcher(cr, c[0]));
     if (c.learnt()) learnts_literals += c.size();
     else            clauses_literals += c.size(); }
 
 
-void Solver::detachClause(Clause& c) {
-    Debug("minisat") << "Solver::detachClause(" << c << ")" << std::endl;
+void Solver::detachClause(CRef cr, bool strict) {
+    const Clause& c = ca[cr];
+    CVC4::Debug("minisat") << "Solver::detachClause(" << c << ")" << std::endl;
     assert(c.size() > 1);
-    assert(find(watches[toInt(~c[0])], &c));
-    assert(find(watches[toInt(~c[1])], &c));
-    remove(watches[toInt(~c[0])], &c);
-    remove(watches[toInt(~c[1])], &c);
+    
+    if (strict){
+        remove(watches[~c[0]], Watcher(cr, c[1]));
+        remove(watches[~c[1]], Watcher(cr, c[0]));
+    }else{
+        // Lazy detaching: (NOTE! Must clean all watcher lists before garbage collecting this clause)
+        watches.smudge(~c[0]);
+        watches.smudge(~c[1]);
+    }
+
     if (c.learnt()) learnts_literals -= c.size();
     else            clauses_literals -= c.size(); }
 
 
-void Solver::removeClause(Clause& c) {
-    Debug("minisat") << "Solver::removeClause(" << c << ")" << std::endl;
-    detachClause(c);
-    free(&c);
+void Solver::removeClause(CRef cr) {
+    Clause& c = ca[cr];
+    CVC4::Debug("minisat") << "Solver::removeClause(" << c << ")" << std::endl;
+    detachClause(cr);
+    // Don't leave pointers to free'd memory!
+    if (locked(c)) vardata[var(c[0])].reason = CRef_Undef;
+    c.mark(1); 
+    ca.free(cr);
 }
 
 
@@ -197,12 +241,12 @@ void Solver::cancelUntil(int level) {
         // Pop the SMT context
         for (int l = trail_lim.size() - level; l > 0; --l)
           context->pop();
-        // Now the minisat stuff
-        for (int c = trail.size()-1; c >= trail_lim[level]; c--) {
-            Var     x  = var(trail[c]);
-            assigns[x] = toInt(l_Undef);
-            insertVarOrder(x);
-        }
+        for (int c = trail.size()-1; c >= trail_lim[level]; c--){
+            Var      x  = var(trail[c]);
+            assigns [x] = l_Undef;
+            if (phase_saving > 1 || (phase_saving == 1) && c > trail_lim.last())
+                polarity[x] = sign(trail[c]);
+            insertVarOrder(x); }
         qhead = trail_lim[level];
         trail.shrink(trail.size() - trail_lim[level]);
         trail_lim.shrink(trail_lim.size() - level);
@@ -220,33 +264,25 @@ void Solver::cancelUntil(int level) {
 // Major methods:
 
 
-Lit Solver::pickBranchLit(int polarity_mode, double random_var_freq)
+Lit Solver::pickBranchLit()
 {
     Var next = var_Undef;
 
     // Random decision:
     if (drand(random_seed) < random_var_freq && !order_heap.empty()){
         next = order_heap[irand(random_seed,order_heap.size())];
-        if (toLbool(assigns[next]) == l_Undef && decision_var[next])
+        if (value(next) == l_Undef && decision[next])
             rnd_decisions++; }
 
     // Activity based decision:
-    while (next == var_Undef || toLbool(assigns[next]) != l_Undef || !decision_var[next])
+    while (next == var_Undef || value(next) != l_Undef || !decision[next])
         if (order_heap.empty()){
             next = var_Undef;
             break;
         }else
             next = order_heap.removeMin();
 
-    bool sign = false;
-    switch (polarity_mode){
-    case polarity_true:  sign = false; break;
-    case polarity_false: sign = true;  break;
-    case polarity_user:  sign = polarity[next]; break;
-    case polarity_rnd:   sign = irand(random_seed, 2); break;
-    default: assert(false); }
-
-    return next == var_Undef ? lit_Undef : Lit(next, sign);
+    return next == var_Undef ? lit_Undef : mkLit(next, rnd_pol ? drand(random_seed) < 0.5 : polarity[next]);
 }
 
 
@@ -263,11 +299,11 @@ Lit Solver::pickBranchLit(int polarity_mode, double random_var_freq)
 |  
 |    Post-conditions:
 |      * 'out_learnt[0]' is the asserting literal at level 'out_btlevel'.
+|      * If out_learnt.size() > 1 then 'out_learnt[1]' has the greatest decision level of the 
+|        rest of literals. There may be others from the same level though.
 |  
-|  Effect:
-|    Will undo part of the trail, upto but not beyond the assumption of the current decision level.
 |________________________________________________________________________________________________@*/
-void Solver::analyze(Clause* confl, vec<Lit>& out_learnt, int& out_btlevel)
+void Solver::analyze(CRef confl, vec<Lit>& out_learnt, int& out_btlevel)
 {
     int pathC = 0;
     Lit p     = lit_Undef;
@@ -276,11 +312,10 @@ void Solver::analyze(Clause* confl, vec<Lit>& out_learnt, int& out_btlevel)
     //
     out_learnt.push();      // (leave room for the asserting literal)
     int index   = trail.size() - 1;
-    out_btlevel = 0;
 
     do{
-        assert(confl != NULL);          // (otherwise should be UIP)
-        Clause& c = *confl;
+        assert(confl != CRef_Undef); // (otherwise should be UIP)
+        Clause& c = ca[confl];
 
         if (c.learnt())
             claBumpActivity(c);
@@ -288,23 +323,20 @@ void Solver::analyze(Clause* confl, vec<Lit>& out_learnt, int& out_btlevel)
         for (int j = (p == lit_Undef) ? 0 : 1; j < c.size(); j++){
             Lit q = c[j];
 
-            if (!seen[var(q)] && level[var(q)] > 0){
+            if (!seen[var(q)] && level(var(q)) > 0){
                 varBumpActivity(var(q));
                 seen[var(q)] = 1;
-                if (level[var(q)] >= decisionLevel())
+                if (level(var(q)) >= decisionLevel())
                     pathC++;
-                else{
+                else
                     out_learnt.push(q);
-                    if (level[var(q)] > out_btlevel)
-                        out_btlevel = level[var(q)];
-                }
             }
         }
-
+        
         // Select next clause to look at:
         while (!seen[var(trail[index--])]);
         p     = trail[index+1];
-        confl = getReason(p);
+        confl = reason(var(p));
         seen[var(p)] = 0;
         pathC--;
 
@@ -314,25 +346,33 @@ void Solver::analyze(Clause* confl, vec<Lit>& out_learnt, int& out_btlevel)
     // Simplify conflict clause:
     //
     int i, j;
-    if (expensive_ccmin){
+    out_learnt.copyTo(analyze_toclear);
+    if (ccmin_mode == 2){
         uint32_t abstract_level = 0;
         for (i = 1; i < out_learnt.size(); i++)
             abstract_level |= abstractLevel(var(out_learnt[i])); // (maintain an abstraction of levels involved in conflict)
 
-        out_learnt.copyTo(analyze_toclear);
         for (i = j = 1; i < out_learnt.size(); i++)
-            if (getReason(out_learnt[i]) == NULL || !litRedundant(out_learnt[i], abstract_level))
+            if (reason(var(out_learnt[i])) == CRef_Undef || !litRedundant(out_learnt[i], abstract_level))
                 out_learnt[j++] = out_learnt[i];
-    }else{
-        out_learnt.copyTo(analyze_toclear);
+        
+    }else if (ccmin_mode == 1){
         for (i = j = 1; i < out_learnt.size(); i++){
-            Clause& c = *getReason(out_learnt[i]);
-            for (int k = 1; k < c.size(); k++)
-                if (!seen[var(c[k])] && level[var(c[k])] > 0){
-                    out_learnt[j++] = out_learnt[i];
-                    break; }
+            Var x = var(out_learnt[i]);
+
+            if (reason(x) == CRef_Undef)
+                out_learnt[j++] = out_learnt[i];
+            else{
+                Clause& c = ca[reason(var(out_learnt[i]))];
+                for (int k = 1; k < c.size(); k++)
+                    if (!seen[var(c[k])] && level(var(c[k])) > 0){
+                        out_learnt[j++] = out_learnt[i];
+                        break; }
+            }
         }
-    }
+    }else
+        i = j = out_learnt.size();
+
     max_literals += out_learnt.size();
     out_learnt.shrink(i - j);
     tot_literals += out_learnt.size();
@@ -343,16 +383,17 @@ void Solver::analyze(Clause* confl, vec<Lit>& out_learnt, int& out_btlevel)
         out_btlevel = 0;
     else{
         int max_i = 1;
+        // Find the first literal assigned at the next-highest level:
         for (int i = 2; i < out_learnt.size(); i++)
-            if (level[var(out_learnt[i])] > level[var(out_learnt[max_i])])
+            if (level(var(out_learnt[i])) > level(var(out_learnt[max_i])))
                 max_i = i;
+        // Swap-in this literal at index 1:
         Lit p             = out_learnt[max_i];
         out_learnt[max_i] = out_learnt[1];
         out_learnt[1]     = p;
-        out_btlevel       = level[var(p)];
+        out_btlevel       = level(var(p));
     }
 
-
     for (int j = 0; j < analyze_toclear.size(); j++) seen[var(analyze_toclear[j])] = 0;    // ('seen[]' is now cleared)
 }
 
@@ -364,13 +405,13 @@ bool Solver::litRedundant(Lit p, uint32_t abstract_levels)
     analyze_stack.clear(); analyze_stack.push(p);
     int top = analyze_toclear.size();
     while (analyze_stack.size() > 0){
-        assert(getReason(analyze_stack.last()) != NULL);
-        Clause& c = *reason[var(analyze_stack.last())]; analyze_stack.pop();
+        assert(reason(var(analyze_stack.last())) != CRef_Undef);
+        Clause& c = ca[reason(var(analyze_stack.last()))]; analyze_stack.pop();
 
         for (int i = 1; i < c.size(); i++){
             Lit p  = c[i];
-            if (!seen[var(p)] && level[var(p)] > 0){
-                if (getReason(p) != NULL && (abstractLevel(var(p)) & abstract_levels) != 0){
+            if (!seen[var(p)] && level(var(p)) > 0){
+                if (reason(var(p)) != CRef_Undef && (abstractLevel(var(p)) & abstract_levels) != 0){
                     seen[var(p)] = 1;
                     analyze_stack.push(p);
                     analyze_toclear.push(p);
@@ -410,13 +451,13 @@ void Solver::analyzeFinal(Lit p, vec<Lit>& out_conflict)
     for (int i = trail.size()-1; i >= trail_lim[0]; i--){
         Var x = var(trail[i]);
         if (seen[x]){
-            if (reason[x] == NULL){
-                assert(level[x] > 0);
+            if (reason(x) == CRef_Undef){
+                assert(level(x) > 0);
                 out_conflict.push(~trail[i]);
             }else{
-                Clause& c = *reason[x];
+                Clause& c = ca[reason(x)];
                 for (int j = 1; j < c.size(); j++)
-                    if (level[var(c[j])] > 0)
+                    if (level(var(c[j])) > 0)
                         seen[var(c[j])] = 1;
             }
             seen[x] = 0;
@@ -427,36 +468,32 @@ void Solver::analyzeFinal(Lit p, vec<Lit>& out_conflict)
 }
 
 
-void Solver::uncheckedEnqueue(Lit p, Clause* from)
+void Solver::uncheckedEnqueue(Lit p, CRef from)
 {
     assert(value(p) == l_Undef);
-    assigns  [var(p)] = toInt(lbool(!sign(p)));  // <<== abstract but not uttermost efficient
-    level    [var(p)] = decisionLevel();
-    reason   [var(p)] = from;
-    // Added for phase-caching
-    polarity [var(p)] = sign(p);
-    trail.push(p);
-
-    if (theory[var(p)] && from != lazy_reason) {
+    assigns[var(p)] = lbool(!sign(p));
+    vardata[var(p)] = mkVarData(from, decisionLevel());
+    trail.push_(p);
+    if (theory[var(p)] && from != CRef_Lazy) {
       // Enqueue to the theory
       proxy->enqueueTheoryLiteral(p);
     }
 }
 
 
-Clause* Solver::propagate(TheoryCheckType type)
+CRef Solver::propagate(TheoryCheckType type)
 {
-    Clause* confl = NULL;
+    CRef confl = CRef_Undef;
 
     // If this is the final check, no need for Boolean propagation and
     // theory propagation
     if (type == CHECK_WITHOUTH_PROPAGATION_FINAL) {
-      return theoryCheck(theory::Theory::FULL_EFFORT);
+      return theoryCheck(CVC4::theory::Theory::FULL_EFFORT);
     }
 
     // The effort we will be using to theory check
-    theory::Theory::Effort effort = type == CHECK_WITHOUTH_PROPAGATION_QUICK ?
-        theory::Theory::QUICK_CHECK : theory::Theory::STANDARD;
+    CVC4::theory::Theory::Effort effort = type == CHECK_WITHOUTH_PROPAGATION_QUICK ?
+        CVC4::theory::Theory::QUICK_CHECK : CVC4::theory::Theory::STANDARD;
 
     // Keep running until we have checked everything, we
     // have no conflict and no new literals have been asserted
@@ -465,12 +502,12 @@ Clause* Solver::propagate(TheoryCheckType type)
         new_assertions = false;
         while(qhead < trail.size()) {
             confl = propagateBool();
-            if (confl != NULL) break;
+            if (confl != CRef_Undef) break;
             confl = theoryCheck(effort);
-            if (confl != NULL) break;
+            if (confl != CRef_Undef) break;
         }
 
-        if (confl == NULL && type == CHECK_WITH_PROPAGATION_STANDARD) {
+        if (confl == CRef_Undef && type == CHECK_WITH_PROPAGATION_STANDARD) {
           new_assertions = propagateTheory();
           if (!new_assertions) break;
         }
@@ -484,7 +521,7 @@ bool Solver::propagateTheory() {
   proxy->theoryPropagate(propagatedLiterals);
   const unsigned i_end = propagatedLiterals.size();
   for (unsigned i = 0; i < i_end; ++ i) {
-    uncheckedEnqueue(propagatedLiterals[i], lazy_reason);
+    uncheckedEnqueue(propagatedLiterals[i], CRef_Lazy);
   }
   proxy->clearPropagatedLiterals();
   return propagatedLiterals.size() > 0;
@@ -500,9 +537,9 @@ bool Solver::propagateTheory() {
 |
 |    Note: the propagation queue might be NOT empty
 |________________________________________________________________________________________________@*/
-Clause* Solver::theoryCheck(theory::Theory::Effort effort)
+CRef Solver::theoryCheck(CVC4::theory::Theory::Effort effort)
 {
-  Clause* c = NULL;
+  CRef c = CRef_Undef;
   SatClause clause;
   proxy->theoryCheck(effort, clause);
   int clause_size = clause.size();
@@ -511,9 +548,9 @@ Clause* Solver::theoryCheck(theory::Theory::Effort effort)
     // Find the max level of the conflict
     int max_level = 0;
     for (int i = 0; i < clause_size; ++i) {
-      int current_level = level[var(clause[i])];
-      Debug("minisat") << "Literal: " << clause[i] << " with reason " << reason[var(clause[i])] << " at level " << current_level << std::endl;
-      Assert(toLbool(assigns[var(clause[i])]) != l_Undef, "Got an unassigned literal in conflict!");
+      int current_level = level(var(clause[i]));
+      Debug("minisat") << "Literal: " << clause[i] << " with reason " << reason(var(clause[i])) << " at level " << current_level << std::endl;
+      Assert(assigns[var(clause[i])] != l_Undef, "Got an unassigned literal in conflict!");
       if (current_level > max_level) max_level = current_level;
     }
     // If smaller than the decision level then pop back so we can analyse
@@ -524,9 +561,9 @@ Clause* Solver::theoryCheck(theory::Theory::Effort effort)
       cancelUntil(max_level);
     }
     // Create the new clause and attach all the information
-    c = Clause_new(clause, true);
+    c = ca.alloc(clause, true);
     learnts.push(c);
-    attachClause(*c);
+    attachClause(c);
   }
   return c;
 }
@@ -537,56 +574,63 @@ Clause* Solver::theoryCheck(theory::Theory::Effort effort)
 |  
 |  Description:
 |    Propagates all enqueued facts. If a conflict arises, the conflicting clause is returned,
-|    otherwise NULL.
+|    otherwise CRef_Undef.
 |  
 |    Post-conditions:
 |      * the propagation queue is empty, even if there was a conflict.
 |________________________________________________________________________________________________@*/
-Clause* Solver::propagateBool()
+CRef Solver::propagateBool()
 {
-    Clause* confl     = NULL;
+    CRef    confl     = CRef_Undef;
     int     num_props = 0;
+    watches.cleanAll();
 
     while (qhead < trail.size()){
         Lit            p   = trail[qhead++];     // 'p' is enqueued fact to propagate.
-        vec<Clause*>&  ws  = watches[toInt(p)];
-        Clause         **i, **j, **end;
+        vec<Watcher>&  ws  = watches[p];
+        Watcher        *i, *j, *end;
         num_props++;
 
-        for (i = j = (Clause**)ws, end = i + ws.size();  i != end;){
-            Clause& c = **i++;
+        for (i = j = (Watcher*)ws, end = i + ws.size();  i != end;){
+            // Try to avoid inspecting the clause:
+            Lit blocker = i->blocker;
+            if (value(blocker) == l_True){
+                *j++ = *i++; continue; }
 
             // Make sure the false literal is data[1]:
-            Lit false_lit = ~p;
+            CRef     cr        = i->cref;
+            Clause&  c         = ca[cr];
+            Lit      false_lit = ~p;
             if (c[0] == false_lit)
                 c[0] = c[1], c[1] = false_lit;
-
             assert(c[1] == false_lit);
+            i++;
 
             // If 0th watch is true, then clause is already satisfied.
-            Lit first = c[0];
-            if (value(first) == l_True){
-                *j++ = &c;
-            }else{
-                // Look for new watch:
-                for (int k = 2; k < c.size(); k++)
-                    if (value(c[k]) != l_False){
-                        c[1] = c[k]; c[k] = false_lit;
-                        watches[toInt(~c[1])].push(&c);
-                        goto FoundWatch; }
-
-                // Did not find watch -- clause is unit under assignment:
-                *j++ = &c;
-                if (value(first) == l_False){
-                    confl = &c;
-                    qhead = trail.size();
-                    // Copy the remaining watches:
-                    while (i < end)
-                        *j++ = *i++;
-                }else
-                    uncheckedEnqueue(first, &c);
-            }
-        FoundWatch:;
+            Lit     first = c[0];
+            Watcher w     = Watcher(cr, first);
+            if (first != blocker && value(first) == l_True){
+                *j++ = w; continue; }
+
+            // Look for new watch:
+            for (int k = 2; k < c.size(); k++)
+                if (value(c[k]) != l_False){
+                    c[1] = c[k]; c[k] = false_lit;
+                    watches[~c[1]].push(w);
+                    goto NextClause; }
+
+            // Did not find watch -- clause is unit under assignment:
+            *j++ = w;
+            if (value(first) == l_False){
+                confl = cr;
+                qhead = trail.size();
+                // Copy the remaining watches:
+                while (i < end)
+                    *j++ = *i++;
+            }else
+                uncheckedEnqueue(first, cr);
+
+        NextClause:;
         }
         ws.shrink(i - j);
     }
@@ -596,6 +640,7 @@ Clause* Solver::propagateBool()
     return confl;
 }
 
+
 /*_________________________________________________________________________________________________
 |
 |  reduceDB : ()  ->  [void]
@@ -604,35 +649,39 @@ Clause* Solver::propagateBool()
 |    Remove half of the learnt clauses, minus the clauses locked by the current assignment. Locked
 |    clauses are clauses that are reason to some assignment. Binary clauses are never removed.
 |________________________________________________________________________________________________@*/
-struct reduceDB_lt { bool operator () (Clause* x, Clause* y) { return x->size() > 2 && (y->size() == 2 || x->activity() < y->activity()); } };
+struct reduceDB_lt { 
+    ClauseAllocator& ca;
+    reduceDB_lt(ClauseAllocator& ca_) : ca(ca_) {}
+    bool operator () (CRef x, CRef y) { 
+        return ca[x].size() > 2 && (ca[y].size() == 2 || ca[x].activity() < ca[y].activity()); } 
+};
 void Solver::reduceDB()
 {
     int     i, j;
     double  extra_lim = cla_inc / learnts.size();    // Remove any clause below this activity
 
-    sort(learnts, reduceDB_lt());
-    for (i = j = 0; i < learnts.size() / 2; i++){
-        if (learnts[i]->size() > 2 && !locked(*learnts[i]))
-            removeClause(*learnts[i]);
-        else
-            learnts[j++] = learnts[i];
-    }
-    for (; i < learnts.size(); i++){
-        if (learnts[i]->size() > 2 && !locked(*learnts[i]) && learnts[i]->activity() < extra_lim)
-            removeClause(*learnts[i]);
+    sort(learnts, reduceDB_lt(ca));
+    // Don't delete binary or locked clauses. From the rest, delete clauses from the first half
+    // and clauses with activity smaller than 'extra_lim':
+    for (i = j = 0; i < learnts.size(); i++){
+        Clause& c = ca[learnts[i]];
+        if (c.size() > 2 && !locked(c) && (i < learnts.size() / 2 || c.activity() < extra_lim))
+            removeClause(learnts[i]);
         else
             learnts[j++] = learnts[i];
     }
     learnts.shrink(i - j);
+    checkGarbage();
 }
 
 
-void Solver::removeSatisfied(vec<Clause*>& cs)
+void Solver::removeSatisfied(vec<CRef>& cs)
 {
-    int i,j;
+    int i, j;
     for (i = j = 0; i < cs.size(); i++){
-        if (satisfied(*cs[i]))
-            removeClause(*cs[i]);
+        Clause& c = ca[cs[i]];
+        if (satisfied(c))
+            removeClause(cs[i]);
         else
             cs[j++] = cs[i];
     }
@@ -640,6 +689,16 @@ void Solver::removeSatisfied(vec<Clause*>& cs)
 }
 
 
+void Solver::rebuildOrderHeap()
+{
+    vec<Var> vs;
+    for (Var v = 0; v < nVars(); v++)
+        if (decision[v] && value(v) == l_Undef)
+            vs.push(v);
+    order_heap.build(vs);
+}
+
+
 /*_________________________________________________________________________________________________
 |
 |  simplify : [void]  ->  [bool]
@@ -652,7 +711,7 @@ bool Solver::simplify()
 {
     assert(decisionLevel() == 0);
 
-    if (!ok || propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) != NULL)
+    if (!ok || propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) != CRef_Undef)
         return ok = false;
 
     if (nAssigns() == simpDB_assigns || (simpDB_props > 0))
@@ -662,9 +721,8 @@ bool Solver::simplify()
     removeSatisfied(learnts);
     if (remove_satisfied)        // Can be turned off.
         removeSatisfied(clauses);
-
-    // Remove fixed variables from the variable heap:
-    order_heap.filter(VarFilter(*this));
+    checkGarbage();
+    rebuildOrderHeap();
 
     simpDB_assigns = nAssigns();
     simpDB_props   = clauses_literals + learnts_literals;   // (shouldn't depend on stats really, but it will do for now)
@@ -675,67 +733,72 @@ bool Solver::simplify()
 
 /*_________________________________________________________________________________________________
 |
-|  search : (nof_conflicts : int) (nof_learnts : int) (params : const SearchParams&)  ->  [lbool]
+|  search : (nof_conflicts : int) (params : const SearchParams&)  ->  [lbool]
 |  
 |  Description:
-|    Search for a model the specified number of conflicts, keeping the number of learnt clauses
-|    below the provided limit. NOTE! Use negative value for 'nof_conflicts' or 'nof_learnts' to
-|    indicate infinity.
+|    Search for a model the specified number of conflicts. 
+|    NOTE! Use negative value for 'nof_conflicts' indicate infinity.
 |  
 |  Output:
 |    'l_True' if a partial assigment that is consistent with respect to the clauseset is found. If
 |    all variables are decision variables, this means that the clause set is satisfiable. 'l_False'
 |    if the clause set is unsatisfiable. 'l_Undef' if the bound on number of conflicts is reached.
 |________________________________________________________________________________________________@*/
-lbool Solver::search(int nof_conflicts, int nof_learnts)
+lbool Solver::search(int nof_conflicts)
 {
     assert(ok);
     int         backtrack_level;
     int         conflictC = 0;
     vec<Lit>    learnt_clause;
-
     starts++;
 
-    bool first = true;
     TheoryCheckType check_type = CHECK_WITH_PROPAGATION_STANDARD;
     for (;;){
-        Clause* confl = propagate(check_type);
-        if (confl != NULL){
+        CRef confl = propagate(check_type);
+        if (confl != CRef_Undef){
             // CONFLICT
             conflicts++; conflictC++;
             if (decisionLevel() == 0) return l_False;
 
-            first = false;
-
             learnt_clause.clear();
             analyze(confl, learnt_clause, backtrack_level);
             cancelUntil(backtrack_level);
-            assert(value(learnt_clause[0]) == l_Undef);
 
             if (learnt_clause.size() == 1){
                 uncheckedEnqueue(learnt_clause[0]);
             }else{
-                Clause* c = Clause_new(learnt_clause, true);
-                learnts.push(c);
-                attachClause(*c);
-                claBumpActivity(*c);
-                uncheckedEnqueue(learnt_clause[0], c);
+                CRef cr = ca.alloc(learnt_clause, true);
+                learnts.push(cr);
+                attachClause(cr);
+                claBumpActivity(ca[cr]);
+                uncheckedEnqueue(learnt_clause[0], cr);
             }
 
             varDecayActivity();
             claDecayActivity();
 
-            // We have a conflict so, we are going back to standard checks
-            check_type = CHECK_WITH_PROPAGATION_STANDARD;
+            if (--learntsize_adjust_cnt == 0){
+                learntsize_adjust_confl *= learntsize_adjust_inc;
+                learntsize_adjust_cnt    = (int)learntsize_adjust_confl;
+                max_learnts             *= learntsize_inc;
+
+                if (verbosity >= 1)
+                    printf("| %9d | %7d %8d %8d | %8d %8d %6.0f | %6.3f %% |\n", 
+                           (int)conflicts, 
+                           (int)dec_vars - (trail_lim.size() == 0 ? trail.size() : trail_lim[0]), nClauses(), (int)clauses_literals, 
+                           (int)max_learnts, nLearnts(), (double)learnts_literals/nLearnts(), progressEstimate()*100);
+            }
 
+			// We have a conflict so, we are going back to standard checks
+            check_type = CHECK_WITH_PROPAGATION_STANDARD;
         }else{
             // NO CONFLICT
 
-            // If this was a final check, we are satisfiable
+			// If this was a final check, we are satisfiable
             if (check_type == CHECK_WITHOUTH_PROPAGATION_FINAL)
               return l_True;
 
-            if (nof_conflicts >= 0 && conflictC >= nof_conflicts){
+            if (nof_conflicts >= 0 && conflictC >= nof_conflicts || !withinBudget()){
                 // Reached bound on number of conflicts:
                 progress_estimate = progressEstimate();
                 cancelUntil(0);
@@ -745,7 +808,7 @@ lbool Solver::search(int nof_conflicts, int nof_learnts)
             if (decisionLevel() == 0 && !simplify())
                 return l_False;
 
-            if (nof_learnts >= 0 && learnts.size()-nAssigns() >= nof_learnts)
+            if (learnts.size()-nAssigns() >= max_learnts)
                 // Reduce the set of learnt clauses:
                 reduceDB();
 
@@ -768,7 +831,7 @@ lbool Solver::search(int nof_conflicts, int nof_learnts)
             if (next == lit_Undef){
                 // New variable decision:
                 decisions++;
-                next = pickBranchLit(polarity_mode, random_var_freq);
+                next = pickBranchLit();
 
                 if (next == lit_Undef) {
                     // We need to do a full theory check to confirm
@@ -778,7 +841,6 @@ lbool Solver::search(int nof_conflicts, int nof_learnts)
             }
 
             // Increase decision level and enqueue 'next'
-            assert(value(next) == l_Undef);
             newDecisionLevel();
             uncheckedEnqueue(next);
         }
@@ -800,100 +862,205 @@ double Solver::progressEstimate() const
     return progress / nVars();
 }
 
+/*
+  Finite subsequences of the Luby-sequence:
+
+  0: 1
+  1: 1 1 2
+  2: 1 1 2 1 1 2 4
+  3: 1 1 2 1 1 2 4 1 1 2 1 1 2 4 8
+  ...
+
+
+ */
+
+static double luby(double y, int x){
+
+    // Find the finite subsequence that contains index 'x', and the
+    // size of that subsequence:
+    int size, seq;
+    for (size = 1, seq = 0; size < x+1; seq++, size = 2*size+1);
+
+    while (size-1 != x){
+        size = (size-1)>>1;
+        seq--;
+        x = x % size;
+    }
 
-bool Solver::solve(const vec<Lit>& assumps)
+    return pow(y, seq);
+}
+
+// NOTE: assumptions passed in member-variable 'assumptions'.
+lbool Solver::solve_()
 {
     model.clear();
     conflict.clear();
+    if (!ok) return l_False;
 
-    if (!ok) return false;
-
-    assumps.copyTo(assumptions);
+    solves++;
 
-    double  nof_conflicts = restart_first;
-    double  nof_learnts   = nClauses() * learntsize_factor;
-    lbool   status        = l_Undef;
+    max_learnts               = nClauses() * learntsize_factor;
+    learntsize_adjust_confl   = learntsize_adjust_start_confl;
+    learntsize_adjust_cnt     = (int)learntsize_adjust_confl;
+    lbool   status            = l_Undef;
 
     if (verbosity >= 1){
-        reportf("============================[ Search Statistics ]==============================\n");
-        reportf("| Conflicts |          ORIGINAL         |          LEARNT          | Progress |\n");
-        reportf("|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |\n");
-        reportf("===============================================================================\n");
+        printf("============================[ Search Statistics ]==============================\n");
+        printf("| Conflicts |          ORIGINAL         |          LEARNT          | Progress |\n");
+        printf("|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |\n");
+        printf("===============================================================================\n");
     }
 
     // Search:
+    int curr_restarts = 0;
     while (status == l_Undef){
-        if (verbosity >= 1)
-            reportf("| %9d | %7d %8d %8d | %8d %8d %6.0f | %6.3f %% |\n", (int)conflicts, order_heap.size(), nClauses(), (int)clauses_literals, (int)nof_learnts, nLearnts(), (double)learnts_literals/nLearnts(), progress_estimate*100), fflush(stdout);
-        status = search((int)nof_conflicts, (int)nof_learnts);
-        nof_conflicts *= restart_inc;
-        nof_learnts   *= learntsize_inc;
+        double rest_base = luby_restart ? luby(restart_inc, curr_restarts) : pow(restart_inc, curr_restarts);
+        status = search(rest_base * restart_first);
+        if (!withinBudget()) break;
+        curr_restarts++;
     }
 
     if (verbosity >= 1)
-        reportf("===============================================================================\n");
+        printf("===============================================================================\n");
 
 
     if (status == l_True){
         // Extend & copy model:
         model.growTo(nVars());
         for (int i = 0; i < nVars(); i++) model[i] = value(i);
-#ifndef NDEBUG
-        verifyModel();
-#endif
-    }else{
-        assert(status == l_False);
-        if (conflict.size() == 0)
-            ok = false;
-    }
+    }else if (status == l_False && conflict.size() == 0)
+        ok = false;
 
     cancelUntil(0);
-    return status == l_True;
+    return status;
 }
 
 //=================================================================================================
-// Debug methods:
-
+// Writing CNF to DIMACS:
+// 
+// FIXME: this needs to be rewritten completely.
 
-void Solver::verifyModel()
+static Var mapVar(Var x, vec<Var>& map, Var& max)
 {
-    bool failed = false;
-    for (int i = 0; i < clauses.size(); i++){
-        assert(clauses[i]->mark() == 0);
-        Clause& c = *clauses[i];
-        for (int j = 0; j < c.size(); j++)
-            if (modelValue(c[j]) == l_True)
-                goto next;
-
-        reportf("unsatisfied clause: ");
-        printClause(*clauses[i]);
-        reportf("\n");
-        failed = true;
-    next:;
+    if (map.size() <= x || map[x] == -1){
+        map.growTo(x+1, -1);
+        map[x] = max++;
     }
+    return map[x];
+}
+
+
+void Solver::toDimacs(FILE* f, Clause& c, vec<Var>& map, Var& max)
+{
+    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]) ? "-" : "", mapVar(var(c[i]), map, max)+1);
+    fprintf(f, "0\n");
+}
 
-    assert(!failed);
 
-    if(verbosity >= 1)
-        reportf("Verified %d original clauses.\n", clauses.size());
+void Solver::toDimacs(const char *file, const vec<Lit>& assumps)
+{
+    FILE* f = fopen(file, "wr");
+    if (f == NULL)
+        fprintf(stderr, "could not open file %s\n", file), exit(1);
+    toDimacs(f, assumps);
+    fclose(f);
 }
 
 
-void Solver::checkLiteralCount()
+void Solver::toDimacs(FILE* f, const vec<Lit>& assumps)
 {
-    // Check that sizes are calculated correctly:
+    // Handle case when solver is in contradictory state:
+    if (!ok){
+        fprintf(f, "p cnf 1 2\n1 0\n-1 0\n");
+        return; }
+
+    vec<Var> map; Var max = 0;
+
+    // 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 (clauses[i]->mark() == 0)
-            cnt += clauses[i]->size();
+        if (!satisfied(ca[clauses[i]]))
+            cnt++;
+        
+    for (int i = 0; i < clauses.size(); i++)
+        if (!satisfied(ca[clauses[i]])){
+            Clause& c = ca[clauses[i]];
+            for (int j = 0; j < c.size(); j++)
+                if (value(c[j]) != l_False)
+                    mapVar(var(c[j]), map, max);
+        }
+
+    // Assumptions are added as unit clauses:
+    cnt += assumptions.size();
 
-    if ((int)clauses_literals != cnt){
-        fprintf(stderr, "literal count: %d, real value = %d\n", (int)clauses_literals, cnt);
-        assert((int)clauses_literals == cnt);
+    fprintf(f, "p cnf %d %d\n", max, cnt);
+
+    for (int i = 0; i < assumptions.size(); i++){
+        assert(value(assumptions[i]) != l_False);
+        fprintf(f, "%s%d 0\n", sign(assumptions[i]) ? "-" : "", mapVar(var(assumptions[i]), map, max)+1);
     }
+
+    for (int i = 0; i < clauses.size(); i++)
+        toDimacs(f, ca[clauses[i]], map, max);
+
+    if (verbosity > 0)
+        printf("Wrote %d clauses with %d variables.\n", cnt, max);
 }
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
 
+//=================================================================================================
+// Garbage Collection methods:
+
+void Solver::relocAll(ClauseAllocator& to)
+{
+    // All watchers:
+    //
+    // for (int i = 0; i < watches.size(); i++)
+    watches.cleanAll();
+    for (int v = 0; v < nVars(); v++)
+        for (int s = 0; s < 2; s++){
+            Lit p = mkLit(v, s);
+            // printf(" >>> RELOCING: %s%d\n", sign(p)?"-":"", var(p)+1);
+            vec<Watcher>& ws = watches[p];
+            for (int j = 0; j < ws.size(); j++)
+                ca.reloc(ws[j].cref, to);
+        }
+
+    // All reasons:
+    //
+    for (int i = 0; i < trail.size(); i++){
+        Var v = var(trail[i]);
+
+        if (reason(v) != CRef_Undef && (ca[reason(v)].reloced() || locked(ca[reason(v)])))
+            ca.reloc(vardata[v].reason, to);
+    }
+
+    // All learnt:
+    //
+    for (int i = 0; i < learnts.size(); i++)
+        ca.reloc(learnts[i], to);
+
+    // All original:
+    //
+    for (int i = 0; i < clauses.size(); i++)
+        ca.reloc(clauses[i], to);
+}
+
+
+void Solver::garbageCollect()
+{
+    // Initialize the next region to a size corresponding to the estimated utilization degree. This
+    // is not precise but should avoid some unnecessary reallocations for the new region:
+    ClauseAllocator to(ca.size() - ca.wasted()); 
+
+    relocAll(to);
+    if (verbosity >= 2)
+        printf("|  Garbage collection:   %12d bytes => %12d bytes             |\n", 
+               ca.size()*ClauseAllocator::Unit_Size, to.size()*ClauseAllocator::Unit_Size);
+    to.moveTo(ca);
+}
diff --git a/src/prop/minisat/core/Solver.h b/src/prop/minisat/core/Solver.h
index 2e44803e9..a47e865a1 100644
--- a/src/prop/minisat/core/Solver.h
+++ b/src/prop/minisat/core/Solver.h
@@ -1,5 +1,6 @@
 /****************************************************************************************[Solver.h]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,32 +18,30 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
+#ifndef Minisat_Solver_h
+#define Minisat_Solver_h
+
 #include "cvc4_private.h"
 
-#ifndef __CVC4__PROP__MINISAT__SOLVER_H
-#define __CVC4__PROP__MINISAT__SOLVER_H
+#include "mtl/Vec.h"
+#include "mtl/Heap.h"
+#include "mtl/Alg.h"
+#include "utils/Options.h"
+#include "core/SolverTypes.h"
 
 #include "context/context.h"
 #include "theory/theory.h"
 
-#include <cstdio>
-#include <cassert>
-
-#include "../mtl/Vec.h"
-#include "../mtl/Heap.h"
-#include "../mtl/Alg.h"
-
-#include "SolverTypes.h"
-
-//=================================================================================================
-// Solver -- the main class:
-
 namespace CVC4 {
 namespace prop {
+  class SatSolver;
+}
+}
 
-class SatSolver;
+namespace Minisat {
 
-namespace minisat {
+//=================================================================================================
+// Solver -- the main class:
 
 class Solver {
 
@@ -52,23 +51,23 @@ class Solver {
 protected:
 
   /** The pointer to the proxy that provides interfaces to the SMT engine */
-  SatSolver* proxy;
+  CVC4::prop::SatSolver* proxy;
 
   /** The context from the SMT solver */
-  context::Context* context;
+  CVC4::context::Context* context;
 
 public:
 
     // Constructor/Destructor:
     //
-    Solver(SatSolver* proxy, context::Context* context);
+    Solver(CVC4::prop::SatSolver* proxy, CVC4::context::Context* context);
     CVC4_PUBLIC ~Solver();
 
     // Problem specification:
     //
     Var     newVar    (bool polarity = true, bool dvar = true, bool theoryAtom = false); // Add a new variable with parameters specifying variable mode.
 
-    // Types of clauses
+	// Types of clauses
     enum ClauseType {
       // Clauses defined by the problem
       CLAUSE_PROBLEM,
@@ -78,17 +77,37 @@ public:
       CLAUSE_CONFLICT
     };
 
-    bool    addClause (vec<Lit>& ps, ClauseType type);                           // Add a clause to the solver. NOTE! 'ps' may be shrunk by this method!
+    bool    addClause (const vec<Lit>& ps, ClauseType type);                     // Add a clause to the solver. 
+    bool    addEmptyClause(ClauseType type);                                     // Add the empty clause, making the solver contradictory.
+    bool    addClause (Lit p, ClauseType type);                                  // Add a unit clause to the solver. 
+    bool    addClause (Lit p, Lit q, ClauseType type);                           // Add a binary clause to the solver. 
+    bool    addClause (Lit p, Lit q, Lit r, ClauseType type);                    // Add a ternary clause to the solver. 
+    bool    addClause_(      vec<Lit>& ps, ClauseType type);                     // Add a clause to the solver without making superflous internal copy. Will
+                                                                                 // change the passed vector 'ps'.
 
     // Solving:
     //
     bool    simplify     ();                        // Removes already satisfied clauses.
     bool    solve        (const vec<Lit>& assumps); // Search for a model that respects a given set of assumptions.
+    lbool   solveLimited (const vec<Lit>& assumps); // Search for a model that respects a given set of assumptions (With resource constraints).
     bool    solve        ();                        // Search without assumptions.
+    bool    solve        (Lit p);                   // Search for a model that respects a single assumption.
+    bool    solve        (Lit p, Lit q);            // Search for a model that respects two assumptions.
+    bool    solve        (Lit p, Lit q, Lit r);     // Search for a model that respects three assumptions.
     bool    okay         () const;                  // FALSE means solver is in a conflicting state
 
+    void    toDimacs     (FILE* f, const vec<Lit>& assumps);            // Write CNF to file in DIMACS-format.
+    void    toDimacs     (const char *file, const vec<Lit>& assumps);
+    void    toDimacs     (FILE* f, Clause& c, vec<Var>& map, Var& max);
+
+    // Convenience versions of 'toDimacs()':
+    void    toDimacs     (const char* file);
+    void    toDimacs     (const char* file, Lit p);
+    void    toDimacs     (const char* file, Lit p, Lit q);
+    void    toDimacs     (const char* file, Lit p, Lit q, Lit r);
+    
     // Variable mode:
-    //
+    // 
     void    setPolarity    (Var v, bool b); // Declare which polarity the decision heuristic should use for a variable. Requires mode 'polarity_user'.
     void    setDecisionVar (Var v, bool b); // Declare if a variable should be eligible for selection in the decision heuristic.
 
@@ -96,11 +115,27 @@ public:
     //
     lbool   value      (Var x) const;       // The current value of a variable.
     lbool   value      (Lit p) const;       // The current value of a literal.
+    lbool   modelValue (Var x) const;       // The value of a variable in the last model. The last call to solve must have been satisfiable.
     lbool   modelValue (Lit p) const;       // The value of a literal in the last model. The last call to solve must have been satisfiable.
     int     nAssigns   ()      const;       // The current number of assigned literals.
     int     nClauses   ()      const;       // The current number of original clauses.
     int     nLearnts   ()      const;       // The current number of learnt clauses.
     int     nVars      ()      const;       // The current number of variables.
+    int     nFreeVars  ()      const;
+
+    // Resource contraints:
+    //
+    void    setConfBudget(int64_t x);
+    void    setPropBudget(int64_t x);
+    void    budgetOff();
+    void    interrupt();          // Trigger a (potentially asynchronous) interruption of the solver.
+    void    clearInterrupt();     // Clear interrupt indicator flag.
+
+    // Memory managment:
+    //
+    virtual void garbageCollect();
+    void    checkGarbage(double gf);
+    void    checkGarbage();
 
     // Extra results: (read-only member variable)
     //
@@ -110,81 +145,89 @@ public:
 
     // Mode of operation:
     //
-    double    var_decay;          // Inverse of the variable activity decay factor.                                            (default 1 / 0.95)
-    double    clause_decay;       // Inverse of the clause activity decay factor.                                              (1 / 0.999)
-    double    random_var_freq;    // The frequency with which the decision heuristic tries to choose a random variable.        (default 0.02)
+    int       verbosity;
+    double    var_decay;
+    double    clause_decay;
+    double    random_var_freq;
+    double    random_seed;
+    bool      luby_restart;
+    int       ccmin_mode;         // Controls conflict clause minimization (0=none, 1=basic, 2=deep).
+    int       phase_saving;       // Controls the level of phase saving (0=none, 1=limited, 2=full).
+    bool      rnd_pol;            // Use random polarities for branching heuristics.
+    bool      rnd_init_act;       // Initialize variable activities with a small random value.
+    double    garbage_frac;       // The fraction of wasted memory allowed before a garbage collection is triggered.
+
     int       restart_first;      // The initial restart limit.                                                                (default 100)
     double    restart_inc;        // The factor with which the restart limit is multiplied in each restart.                    (default 1.5)
     double    learntsize_factor;  // The intitial limit for learnt clauses is a factor of the original clauses.                (default 1 / 3)
     double    learntsize_inc;     // The limit for learnt clauses is multiplied with this factor each restart.                 (default 1.1)
-    bool      expensive_ccmin;    // Controls conflict clause minimization.                                                    (default TRUE)
-    int       polarity_mode;      // Controls which polarity the decision heuristic chooses. See enum below for allowed modes. (default polarity_false)
-    int       verbosity;          // Verbosity level. 0=silent, 1=some progress report                                         (default 0)
 
-    enum { polarity_true = 0, polarity_false = 1, polarity_user = 2, polarity_rnd = 3 };
+    int       learntsize_adjust_start_confl;
+    double    learntsize_adjust_inc;
 
     // Statistics: (read-only member variable)
     //
-    uint64_t starts, decisions, rnd_decisions, propagations, conflicts;
-    uint64_t clauses_literals, learnts_literals, max_literals, tot_literals;
+    uint64_t solves, starts, decisions, rnd_decisions, propagations, conflicts;
+    uint64_t dec_vars, clauses_literals, learnts_literals, max_literals, tot_literals;
 
 protected:
 
     // Helper structures:
     //
+    struct VarData { CRef reason; int level; };
+    static inline VarData mkVarData(CRef cr, int l){ VarData d = {cr, l}; return d; }
+
+    struct Watcher {
+        CRef cref;
+        Lit  blocker;
+        Watcher(CRef cr, Lit p) : cref(cr), blocker(p) {}
+        bool operator==(const Watcher& w) const { return cref == w.cref; }
+        bool operator!=(const Watcher& w) const { return cref != w.cref; }
+    };
+
+    struct WatcherDeleted
+    {
+        const ClauseAllocator& ca;
+        WatcherDeleted(const ClauseAllocator& _ca) : ca(_ca) {}
+        bool operator()(const Watcher& w) const { return ca[w.cref].mark() == 1; }
+    };
+
     struct VarOrderLt {
         const vec<double>&  activity;
         bool operator () (Var x, Var y) const { return activity[x] > activity[y]; }
         VarOrderLt(const vec<double>&  act) : activity(act) { }
     };
 
-    friend class VarFilter;
-    struct VarFilter {
-        const Solver& s;
-        VarFilter(const Solver& _s) : s(_s) {}
-        bool operator()(Var v) const { return toLbool(s.assigns[v]) == l_Undef && s.decision_var[v]; }
-    };
-
     // Solver state:
     //
     bool                ok;               // If FALSE, the constraints are already unsatisfiable. No part of the solver state may be used!
-    vec<Clause*>        clauses;          // List of problem clauses.
-    vec<Clause*>        learnts;          // List of learnt clauses.
+    vec<CRef>           clauses;          // List of problem clauses.
+    vec<CRef>           learnts;          // List of learnt clauses.
     double              cla_inc;          // Amount to bump next clause with.
     vec<double>         activity;         // A heuristic measurement of the activity of a variable.
     double              var_inc;          // Amount to bump next variable with.
-    vec<vec<Clause*> >  watches;          // 'watches[lit]' is a list of constraints watching 'lit' (will go there if literal becomes true).
-    vec<char>           assigns;          // The current assignments (lbool:s stored as char:s).
+    OccLists<Lit, vec<Watcher>, WatcherDeleted>
+                        watches;          // 'watches[lit]' is a list of constraints watching 'lit' (will go there if literal becomes true).
+    vec<lbool>          assigns;          // The current assignments.
     vec<char>           polarity;         // The preferred polarity of each variable.
-    vec<bool>           theory;           // Is the variable representing a theory atom
-    vec<char>           decision_var;     // Declares if a variable is eligible for selection in the decision heuristic.
+    vec<char>           decision;         // Declares if a variable is eligible for selection in the decision heuristic.
     vec<Lit>            trail;            // Assignment stack; stores all assigments made in the order they were made.
     vec<int>            trail_lim;        // Separator indices for different decision levels in 'trail'.
-    vec<Clause*>        lemmas;           // List of lemmas we added (context dependent)
-    vec<int>            lemmas_lim;       // Separator indices for different decision levels in 'lemmas'.
-    static Clause*      lazy_reason;      // The mark when we need to ask the theory engine for a reason
-    vec<Clause*>        reason;           // 'reason[var]' is the clause that implied the variables current value, lazy_reason if theory propagated, or 'NULL' if none.
-
-    Clause* getReason(Lit l);             // Returns the reason, or asks the theory for an explanation
-
-    vec<int>            level;            // 'level[var]' contains the level at which the assignment was made.
+    vec<VarData>        vardata;          // Stores reason and level for each variable.
     int                 qhead;            // Head of queue (as index into the trail -- no more explicit propagation queue in MiniSat).
-    int                 lhead;            // Head of the lemma stack (for backtracking)
     int                 simpDB_assigns;   // Number of top-level assignments since last execution of 'simplify()'.
     int64_t             simpDB_props;     // Remaining number of propagations that must be made before next execution of 'simplify()'.
     vec<Lit>            assumptions;      // Current set of assumptions provided to solve by the user.
     Heap<VarOrderLt>    order_heap;       // A priority queue of variables ordered with respect to the variable activity.
-    double              random_seed;      // Used by the random variable selection.
     double              progress_estimate;// Set by 'search()'.
     bool                remove_satisfied; // Indicates whether possibly inefficient linear scan for satisfied clauses should be performed in 'simplify'.
 
-    // Temporaries (to reduce allocation overhead). Each variable is prefixed by the method in which it is
-    // used, exept 'seen' wich is used in several places.
-    //
-    vec<char>           seen;
-    vec<Lit>            analyze_stack;
-    vec<Lit>            analyze_toclear;
-    vec<Lit>            add_tmp;
+    ClauseAllocator     ca;
+
+	// CVC4 Stuff
+    vec<bool>           theory;           // Is the variable representing a theory atom
+    vec<CRef>           lemmas;           // List of lemmas we added (context dependent)
+    vec<int>            lemmas_lim;       // Separator indices for different decision levels in 'lemmas'.
 
     enum TheoryCheckType {
       // Quick check, but don't perform theory propagation
@@ -195,52 +238,71 @@ protected:
       CHECK_WITHOUTH_PROPAGATION_FINAL
     };
 
+    // Temporaries (to reduce allocation overhead). Each variable is prefixed by the method in which it is
+    // used, exept 'seen' wich is used in several places.
+    //
+    vec<char>           seen;
+    vec<Lit>            analyze_stack;
+    vec<Lit>            analyze_toclear;
+    vec<Lit>            add_tmp;
+
+    double              max_learnts;
+    double              learntsize_adjust_confl;
+    int                 learntsize_adjust_cnt;
+
+    // Resource contraints:
+    //
+    int64_t             conflict_budget;    // -1 means no budget.
+    int64_t             propagation_budget; // -1 means no budget.
+    bool                asynch_interrupt;
+
     // Main internal methods:
     //
     void     insertVarOrder   (Var x);                                                 // Insert a variable in the decision order priority queue.
-    Lit      pickBranchLit    (int polarity_mode, double random_var_freq);             // Return the next decision variable.
+    Lit      pickBranchLit    ();                                                      // Return the next decision variable.
     void     newDecisionLevel ();                                                      // Begins a new decision level.
-    void     uncheckedEnqueue (Lit p, Clause* from = NULL);                            // Enqueue a literal. Assumes value of literal is undefined.
-    bool     enqueue          (Lit p, Clause* from = NULL);                            // Test if fact 'p' contradicts current state, enqueue otherwise.
-    Clause*  propagate        (TheoryCheckType type);                                  // Perform Boolean and Theory. Returns possibly conflicting clause.
-    Clause*  propagateBool    ();                                                      // Perform Boolean propagation. Returns possibly conflicting clause.
+    void     uncheckedEnqueue (Lit p, CRef from = CRef_Undef);                         // Enqueue a literal. Assumes value of literal is undefined.
+    bool     enqueue          (Lit p, CRef from = CRef_Undef);                         // Test if fact 'p' contradicts current state, enqueue otherwise.
+    CRef     propagate        (TheoryCheckType type);                                  // Perform Boolean and Theory. Returns possibly conflicting clause.
+    CRef     propagateBool    ();                                                      // Perform Boolean propagation. Returns possibly conflicting clause.
     bool     propagateTheory  ();                                                      // Perform Theory propagation. Return true if any literals were asserted.
-    Clause*  theoryCheck      (theory::Theory::Effort effort);                         // Perform a theory satisfiability check. Returns possibly conflicting clause.
+    CRef     theoryCheck      (CVC4::theory::Theory::Effort effort);                   // Perform a theory satisfiability check. Returns possibly conflicting clause.
     void     cancelUntil      (int level);                                             // Backtrack until a certain level.
-    void     analyze          (Clause* confl, vec<Lit>& out_learnt, int& out_btlevel); // (bt = backtrack)
+    void     analyze          (CRef confl, vec<Lit>& out_learnt, int& out_btlevel);    // (bt = backtrack)
     void     analyzeFinal     (Lit p, vec<Lit>& out_conflict);                         // COULD THIS BE IMPLEMENTED BY THE ORDINARIY "analyze" BY SOME REASONABLE GENERALIZATION?
     bool     litRedundant     (Lit p, uint32_t abstract_levels);                       // (helper method for 'analyze()')
-    lbool    search           (int nof_conflicts, int nof_learnts);                    // Search for a given number of conflicts.
+    lbool    search           (int nof_conflicts);                                     // Search for a given number of conflicts.
+    lbool    solve_           ();                                                      // Main solve method (assumptions given in 'assumptions').
     void     reduceDB         ();                                                      // Reduce the set of learnt clauses.
-    void     removeSatisfied  (vec<Clause*>& cs);                                      // Shrink 'cs' to contain only non-satisfied clauses.
+    void     removeSatisfied  (vec<CRef>& cs);                                         // Shrink 'cs' to contain only non-satisfied clauses.
+    void     rebuildOrderHeap ();
 
     // Maintaining Variable/Clause activity:
     //
     void     varDecayActivity ();                      // Decay all variables with the specified factor. Implemented by increasing the 'bump' value instead.
+    void     varBumpActivity  (Var v, double inc);     // Increase a variable with the current 'bump' value.
     void     varBumpActivity  (Var v);                 // Increase a variable with the current 'bump' value.
     void     claDecayActivity ();                      // Decay all clauses with the specified factor. Implemented by increasing the 'bump' value instead.
     void     claBumpActivity  (Clause& c);             // Increase a clause with the current 'bump' value.
 
     // Operations on clauses:
     //
-    void     attachClause     (Clause& c);             // Attach a clause to watcher lists.
-    void     detachClause     (Clause& c);             // Detach a clause to watcher lists.
-    void     removeClause     (Clause& c);             // Detach and free a clause.
+    void     attachClause     (CRef cr);               // Attach a clause to watcher lists.
+    void     detachClause     (CRef cr, bool strict = false); // Detach a clause to watcher lists.
+    void     removeClause     (CRef cr);               // Detach and free a clause.
     bool     locked           (const Clause& c) const; // Returns TRUE if a clause is a reason for some implication in the current state.
     bool     satisfied        (const Clause& c) const; // Returns TRUE if a clause is satisfied in the current state.
 
+    void     relocAll         (ClauseAllocator& to);
+
     // Misc:
     //
-    int      decisionLevel    ()      const; // Gives the current decision level.
+    int      decisionLevel    ()      const; // Gives the current decisionlevel.
     uint32_t abstractLevel    (Var x) const; // Used to represent an abstraction of sets of decision levels.
+    CRef     reason           (Var x) const;
+    int      level            (Var x) const;
     double   progressEstimate ()      const; // DELETE THIS ?? IT'S NOT VERY USEFUL ...
-
-    // Debug:
-    void     printLit         (Lit l);
-    template<class C>
-    void     printClause      (const C& c);
-    void     verifyModel      ();
-    void     checkLiteralCount();
+    bool     withinBudget     ()      const;
 
     // Static helpers:
     //
@@ -257,15 +319,19 @@ protected:
         return (int)(drand(seed) * size); }
 };
 
+
 //=================================================================================================
 // Implementation of inline methods:
 
+inline int  Solver::level (Var x) const { return vardata[x].level; }
+
 inline void Solver::insertVarOrder(Var x) {
-    if (!order_heap.inHeap(x) && decision_var[x]) order_heap.insert(x); }
+    if (!order_heap.inHeap(x) && decision[x]) order_heap.insert(x); }
 
-inline void Solver::varDecayActivity() { var_inc *= var_decay; }
-inline void Solver::varBumpActivity(Var v) {
-    if ( (activity[v] += var_inc) > 1e100 ) {
+inline void Solver::varDecayActivity() { var_inc *= (1 / var_decay); }
+inline void Solver::varBumpActivity(Var v) { varBumpActivity(v, var_inc); }
+inline void Solver::varBumpActivity(Var v, double inc) {
+    if ( (activity[v] += inc) > 1e100 ) {
         // Rescale:
         for (int i = 0; i < nVars(); i++)
             activity[i] *= 1e-100;
@@ -275,84 +341,81 @@ inline void Solver::varBumpActivity(Var v) {
     if (order_heap.inHeap(v))
         order_heap.decrease(v); }
 
-inline void Solver::claDecayActivity() { cla_inc *= clause_decay; }
+inline void Solver::claDecayActivity() { cla_inc *= (1 / clause_decay); }
 inline void Solver::claBumpActivity (Clause& c) {
         if ( (c.activity() += cla_inc) > 1e20 ) {
             // Rescale:
             for (int i = 0; i < learnts.size(); i++)
-                learnts[i]->activity() *= 1e-20;
+                ca[learnts[i]].activity() *= 1e-20;
             cla_inc *= 1e-20; } }
 
-inline bool     Solver::enqueue         (Lit p, Clause* from)   { return value(p) != l_Undef ? value(p) != l_False : (uncheckedEnqueue(p, from), true); }
-inline bool     Solver::locked          (const Clause& c) const { return reason[var(c[0])] == &c && value(c[0]) == l_True; }
+inline void Solver::checkGarbage(void){ return checkGarbage(garbage_frac); }
+inline void Solver::checkGarbage(double gf){
+    if (ca.wasted() > ca.size() * gf)
+        garbageCollect(); }
+
+// NOTE: enqueue does not set the ok flag! (only public methods do)
+inline bool     Solver::enqueue         (Lit p, CRef from)      { return value(p) != l_Undef ? value(p) != l_False : (uncheckedEnqueue(p, from), true); }
+inline bool     Solver::addClause       (const vec<Lit>& ps, ClauseType type)    { ps.copyTo(add_tmp); return addClause_(add_tmp, type); }
+inline bool     Solver::addEmptyClause  (ClauseType type)                        { add_tmp.clear(); return addClause_(add_tmp, type); }
+inline bool     Solver::addClause       (Lit p, ClauseType type)                 { add_tmp.clear(); add_tmp.push(p); return addClause_(add_tmp, type); }
+inline bool     Solver::addClause       (Lit p, Lit q, ClauseType type)          { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); return addClause_(add_tmp, type); }
+inline bool     Solver::addClause       (Lit p, Lit q, Lit r, ClauseType type)   { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); add_tmp.push(r); return addClause_(add_tmp, type); }
+inline bool     Solver::locked          (const Clause& c) const { return value(c[0]) == l_True && reason(var(c[0])) != CRef_Undef && ca.lea(reason(var(c[0]))) == &c; }
 inline void     Solver::newDecisionLevel()                      { trail_lim.push(trail.size()); lemmas_lim.push(lemmas.size()); context->push(); }
 
 inline int      Solver::decisionLevel ()      const   { return trail_lim.size(); }
-inline uint32_t Solver::abstractLevel (Var x) const   { return 1 << (level[x] & 31); }
-inline lbool    Solver::value         (Var x) const   { return toLbool(assigns[x]); }
-inline lbool    Solver::value         (Lit p) const   { return toLbool(assigns[var(p)]) ^ sign(p); }
+inline uint32_t Solver::abstractLevel (Var x) const   { return 1 << (level(x) & 31); }
+inline lbool    Solver::value         (Var x) const   { return assigns[x]; }
+inline lbool    Solver::value         (Lit p) const   { return assigns[var(p)] ^ sign(p); }
+inline lbool    Solver::modelValue    (Var x) const   { return model[x]; }
 inline lbool    Solver::modelValue    (Lit p) const   { return model[var(p)] ^ sign(p); }
 inline int      Solver::nAssigns      ()      const   { return trail.size(); }
 inline int      Solver::nClauses      ()      const   { return clauses.size(); }
 inline int      Solver::nLearnts      ()      const   { return learnts.size(); }
-inline int      Solver::nVars         ()      const   { return assigns.size(); }
-inline void     Solver::setPolarity   (Var v, bool b) { polarity    [v] = (char)b; }
-inline void     Solver::setDecisionVar(Var v, bool b) { decision_var[v] = (char)b; if (b) { insertVarOrder(v); } }
-inline bool     Solver::solve         ()              { vec<Lit> tmp; return solve(tmp); }
+inline int      Solver::nVars         ()      const   { return vardata.size(); }
+inline int      Solver::nFreeVars     ()      const   { return (int)dec_vars - (trail_lim.size() == 0 ? trail.size() : trail_lim[0]); }
+inline void     Solver::setPolarity   (Var v, bool b) { polarity[v] = b; }
+inline void     Solver::setDecisionVar(Var v, bool b) 
+{ 
+    if      ( b && !decision[v]) dec_vars++;
+    else if (!b &&  decision[v]) dec_vars--;
+
+    decision[v] = b;
+    insertVarOrder(v);
+}
+inline void     Solver::setConfBudget(int64_t x){ conflict_budget    = conflicts    + x; }
+inline void     Solver::setPropBudget(int64_t x){ propagation_budget = propagations + x; }
+inline void     Solver::interrupt(){ asynch_interrupt = true; }
+inline void     Solver::clearInterrupt(){ asynch_interrupt = false; }
+inline void     Solver::budgetOff(){ conflict_budget = propagation_budget = -1; }
+inline bool     Solver::withinBudget() const {
+    return !asynch_interrupt &&
+           (conflict_budget    < 0 || conflicts < (uint64_t)conflict_budget) &&
+           (propagation_budget < 0 || propagations < (uint64_t)propagation_budget); }
+
+// FIXME: after the introduction of asynchronous interrruptions the solve-versions that return a
+// pure bool do not give a safe interface. Either interrupts must be possible to turn off here, or
+// all calls to solve must return an 'lbool'. I'm not yet sure which I prefer.
+inline bool     Solver::solve         ()                    { budgetOff(); assumptions.clear(); return solve_() == l_True; }
+inline bool     Solver::solve         (Lit p)               { budgetOff(); assumptions.clear(); assumptions.push(p); return solve_() == l_True; }
+inline bool     Solver::solve         (Lit p, Lit q)        { budgetOff(); assumptions.clear(); assumptions.push(p); assumptions.push(q); return solve_() == l_True; }
+inline bool     Solver::solve         (Lit p, Lit q, Lit r) { budgetOff(); assumptions.clear(); assumptions.push(p); assumptions.push(q); assumptions.push(r); return solve_() == l_True; }
+inline bool     Solver::solve         (const vec<Lit>& assumps){ budgetOff(); assumps.copyTo(assumptions); return solve_() == l_True; }
+inline lbool    Solver::solveLimited  (const vec<Lit>& assumps){ assumps.copyTo(assumptions); return solve_(); }
 inline bool     Solver::okay          ()      const   { return ok; }
 
+inline void     Solver::toDimacs     (const char* file){ vec<Lit> as; toDimacs(file, as); }
+inline void     Solver::toDimacs     (const char* file, Lit p){ vec<Lit> as; as.push(p); toDimacs(file, as); }
+inline void     Solver::toDimacs     (const char* file, Lit p, Lit q){ vec<Lit> as; as.push(p); as.push(q); toDimacs(file, as); }
+inline void     Solver::toDimacs     (const char* file, Lit p, Lit q, Lit r){ vec<Lit> as; as.push(p); as.push(q); as.push(r); toDimacs(file, as); }
 
 
 //=================================================================================================
-// Debug + etc:
-
-
-#define reportf(format, args...) ( fflush(stdout), fprintf(stderr, format, ## args), fflush(stderr) )
-//#define reportf(format, args...) do {} while(0)
-
-static inline void logLit(FILE* f, Lit l)
-{
-    fprintf(f, "%sx%d", sign(l) ? "~" : "", var(l)+1);
-}
-
-static inline void logLits(FILE* f, const vec<Lit>& ls)
-{
-    fprintf(f, "[ ");
-    if (ls.size() > 0){
-        logLit(f, ls[0]);
-        for (int i = 1; i < ls.size(); i++){
-            fprintf(f, ", ");
-            logLit(f, ls[i]);
-        }
-    }
-    fprintf(f, "] ");
-}
-
-static inline const char* showBool(bool b) { return b ? "true" : "false"; }
+// Debug etc:
 
 
-// Just like 'assert()' but expression will be evaluated in the release version as well.
-static inline void check(bool expr) { assert(expr); }
-
-
-inline void Solver::printLit(Lit l)
-{
-    reportf("%s%d:%c", sign(l) ? "-" : "", var(l)+1, value(l) == l_True ? '1' : (value(l) == l_False ? '0' : 'X'));
-}
-
-
-template<class C>
-inline void Solver::printClause(const C& c)
-{
-    for (int i = 0; i < c.size(); i++){
-        printLit(c[i]);
-        fprintf(stderr, " ");
-    }
+//=================================================================================================
 }
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
-
-//=================================================================================================
-#endif /* __CVC4__PROP__MINISAT__SOLVER_H */
+#endif
diff --git a/src/prop/minisat/core/SolverTypes.h b/src/prop/minisat/core/SolverTypes.h
index fd6a78ab0..12a0fdb6b 100644
--- a/src/prop/minisat/core/SolverTypes.h
+++ b/src/prop/minisat/core/SolverTypes.h
@@ -1,5 +1,6 @@
 /***********************************************************************************[SolverTypes.h]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -19,15 +20,18 @@ OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWA
 
 #include "cvc4_private.h"
 
-#ifndef __CVC4__PROP__MINISAT__SOLVERTYPES_H
-#define __CVC4__PROP__MINISAT__SOLVERTYPES_H
+#ifndef Minisat_SolverTypes_h
+#define Minisat_SolverTypes_h
 
-#include <cassert>
-#include <stdint.h>
+#include <assert.h>
 
-namespace CVC4 {
-namespace prop {
-namespace minisat {
+#include "mtl/IntTypes.h"
+#include "mtl/Alg.h"
+#include "mtl/Vec.h"
+#include "mtl/Map.h"
+#include "mtl/Alloc.h"
+
+namespace Minisat {
 
 //=================================================================================================
 // Variables, literals, lifted booleans, clauses:
@@ -40,118 +44,315 @@ typedef int Var;
 #define var_Undef (-1)
 
 
-class Lit {
+struct Lit {
     int     x;
- public:
-    Lit() : x(2*var_Undef)                                              { }   // (lit_Undef)
-    explicit Lit(Var var, bool sign = false) : x((var+var) + (int)sign) { }
-
-    // Don't use these for constructing/deconstructing literals. Use the normal constructors instead.
-    friend int  toInt       (Lit p);  // Guarantees small, positive integers suitable for array indexing.
-    friend Lit  toLit       (int i);  // Inverse of 'toInt()'
-    friend Lit  operator   ~(Lit p);
-    friend bool sign        (Lit p);
-    friend int  var         (Lit p);
-    friend Lit  unsign      (Lit p);
-    friend Lit  id          (Lit p, bool sgn);
+
+    // Use this as a constructor:
+    friend Lit mkLit(Var var, bool sign = false);
 
     bool operator == (Lit p) const { return x == p.x; }
     bool operator != (Lit p) const { return x != p.x; }
-    bool operator <  (Lit p) const { return x < p.x;  } // '<' guarantees that p, ~p are adjacent in the ordering.
+    bool operator <  (Lit p) const { return x < p.x;  } // '<' makes p, ~p adjacent in the ordering.
 };
 
-inline  int  toInt       (Lit p)           { return p.x; }
-inline  Lit  toLit       (int i)           { Lit p; p.x = i; return p; }
-inline  Lit  operator   ~(Lit p)           { Lit q; q.x = p.x ^ 1; return q; }
-inline  bool sign        (Lit p)           { return p.x & 1; }
-inline  int  var         (Lit p)           { return p.x >> 1; }
-inline  Lit  unsign      (Lit p)           { Lit q; q.x = p.x & ~1; return q; }
-inline  Lit  id          (Lit p, bool sgn) { Lit q; q.x = p.x ^ (int)sgn; return q; }
 
-const Lit lit_Undef(var_Undef, false);  // }- Useful special constants.
-const Lit lit_Error(var_Undef, true );  // }
+inline  Lit  mkLit     (Var var, bool sign) { Lit p; p.x = var + var + (int)sign; return p; }
+inline  Lit  operator ~(Lit p)              { Lit q; q.x = p.x ^ 1; return q; }
+inline  Lit  operator ^(Lit p, bool b)      { Lit q; q.x = p.x ^ (unsigned int)b; return q; }
+inline  bool sign      (Lit p)              { return p.x & 1; }
+inline  int  var       (Lit p)              { return p.x >> 1; }
+
+// Mapping Literals to and from compact integers suitable for array indexing:
+inline  int  toInt     (Var v)              { return v; } 
+inline  int  toInt     (Lit p)              { return p.x; } 
+inline  Lit  toLit     (int i)              { Lit p; p.x = i; return p; } 
+
+//const Lit lit_Undef = mkLit(var_Undef, false);  // }- Useful special constants.
+//const Lit lit_Error = mkLit(var_Undef, true );  // }
+
+const Lit lit_Undef = { -2 };  // }- Useful special constants.
+const Lit lit_Error = { -1 };  // }
 
 
 //=================================================================================================
 // Lifted booleans:
+//
+// NOTE: this implementation is optimized for the case when comparisons between values are mostly
+//       between one variable and one constant. Some care had to be taken to make sure that gcc 
+//       does enough constant propagation to produce sensible code, and this appears to be somewhat
+//       fragile unfortunately.
 
+#define l_True  (Minisat::lbool((uint8_t)0)) // gcc does not do constant propagation if these are real constants.
+#define l_False (Minisat::lbool((uint8_t)1))
+#define l_Undef (Minisat::lbool((uint8_t)2))
 
 class lbool {
-    char     value;
-    explicit lbool(int v) : value(v) { }
+    uint8_t value;
 
 public:
+    explicit lbool(uint8_t v) : value(v) { }
+
     lbool()       : value(0) { }
-    lbool(bool x) : value((int)x*2-1) { }
-    int toInt(void) const { return value; }
+    explicit lbool(bool x) : value(!x) { }
+
+    bool  operator == (lbool b) const { return ((b.value&2) & (value&2)) | (!(b.value&2)&(value == b.value)); }
+    bool  operator != (lbool b) const { return !(*this == b); }
+    lbool operator ^  (bool  b) const { return lbool((uint8_t)(value^(uint8_t)b)); }
 
-    bool  operator == (lbool b) const { return value == b.value; }
-    bool  operator != (lbool b) const { return value != b.value; }
-    lbool operator ^ (bool b) const { return b ? lbool(-value) : lbool(value); }
+    lbool operator && (lbool b) const { 
+        uint8_t sel = (this->value << 1) | (b.value << 3);
+        uint8_t v   = (0xF7F755F4 >> sel) & 3;
+        return lbool(v); }
+
+    lbool operator || (lbool b) const {
+        uint8_t sel = (this->value << 1) | (b.value << 3);
+        uint8_t v   = (0xFCFCF400 >> sel) & 3;
+        return lbool(v); }
 
     friend int   toInt  (lbool l);
     friend lbool toLbool(int   v);
 };
-inline int   toInt  (lbool l) { return l.toInt(); }
-inline lbool toLbool(int   v) { return lbool(v);  }
-
-const lbool l_True  = toLbool( 1);
-const lbool l_False = toLbool(-1);
-const lbool l_Undef = toLbool( 0);
+inline int   toInt  (lbool l) { return l.value; }
+inline lbool toLbool(int   v) { return lbool((uint8_t)v);  }
 
 //=================================================================================================
 // Clause -- a simple class for representing a clause:
 
+class Clause;
+typedef RegionAllocator<uint32_t>::Ref CRef;
 
 class Clause {
-    uint32_t size_etc;
-    union { float act; uint32_t abst; } extra;
-    Lit     data[0];
+    struct {
+        unsigned mark      : 2;
+        unsigned learnt    : 1;
+        unsigned has_extra : 1;
+        unsigned reloced   : 1;
+        unsigned size      : 27; }                            header;
+    union { Lit lit; float act; uint32_t abs; CRef rel; } data[0];
+
+    friend class ClauseAllocator;
+
+    // NOTE: This constructor cannot be used directly (doesn't allocate enough memory).
+    template<class V>
+    Clause(const V& ps, bool use_extra, bool learnt) {
+        header.mark      = 0;
+        header.learnt    = learnt;
+        header.has_extra = use_extra;
+        header.reloced   = 0;
+        header.size      = ps.size();
+
+        for (int i = 0; i < ps.size(); i++) 
+            data[i].lit = ps[i];
+
+        if (header.has_extra){
+            if (header.learnt)
+                data[header.size].act = 0; 
+            else 
+                calcAbstraction(); }
+    }
 
 public:
     void calcAbstraction() {
+        assert(header.has_extra);
         uint32_t abstraction = 0;
         for (int i = 0; i < size(); i++)
-            abstraction |= 1 << (var(data[i]) & 31);
-        extra.abst = abstraction;  }
+            abstraction |= 1 << (var(data[i].lit) & 31);
+        data[header.size].abs = abstraction;  }
 
-    // NOTE: This constructor cannot be used directly (doesn't allocate enough memory).
-    template<class V>
-    Clause(const V& ps, bool learnt) {
-        size_etc = (ps.size() << 3) | (uint32_t)learnt;
-        for (int i = 0; i < ps.size(); i++) data[i] = ps[i];
-        if (learnt) extra.act = 0; else calcAbstraction(); }
 
-    // -- use this function instead:
-    template<class V>
-    friend Clause* Clause_new(const V& ps, bool learnt = false) {
-        assert(sizeof(Lit)      == sizeof(uint32_t));
-        assert(sizeof(float)    == sizeof(uint32_t));
-        void* mem = malloc(sizeof(Clause) + sizeof(uint32_t)*(ps.size()));
-        return new (mem) Clause(ps, learnt); }
-
-    int          size        ()      const   { return size_etc >> 3; }
-    void         shrink      (int i)         { assert(i <= size()); size_etc = (((size_etc >> 3) - i) << 3) | (size_etc & 7); }
+    int          size        ()      const   { return header.size; }
+    void         shrink      (int i)         { assert(i <= size()); if (header.has_extra) data[header.size-i] = data[header.size]; header.size -= i; }
     void         pop         ()              { shrink(1); }
-    bool         learnt      ()      const   { return size_etc & 1; }
-    uint32_t     mark        ()      const   { return (size_etc >> 1) & 3; }
-    void         mark        (uint32_t m)    { size_etc = (size_etc & ~6) | ((m & 3) << 1); }
-    const Lit&   last        ()      const   { return data[size()-1]; }
+    bool         learnt      ()      const   { return header.learnt; }
+    bool         has_extra   ()      const   { return header.has_extra; }
+    uint32_t     mark        ()      const   { return header.mark; }
+    void         mark        (uint32_t m)    { header.mark = m; }
+    const Lit&   last        ()      const   { return data[header.size-1].lit; }
+
+    bool         reloced     ()      const   { return header.reloced; }
+    CRef         relocation  ()      const   { return data[0].rel; }
+    void         relocate    (CRef c)        { header.reloced = 1; data[0].rel = c; }
 
     // NOTE: somewhat unsafe to change the clause in-place! Must manually call 'calcAbstraction' afterwards for
     //       subsumption operations to behave correctly.
-    Lit&         operator [] (int i)         { return data[i]; }
-    Lit          operator [] (int i) const   { return data[i]; }
-    operator const Lit* (void) const         { return data; }
+    Lit&         operator [] (int i)         { return data[i].lit; }
+    Lit          operator [] (int i) const   { return data[i].lit; }
+    operator const Lit* (void) const         { return (Lit*)data; }
 
-    float&       activity    ()              { return extra.act; }
-    uint32_t     abstraction () const { return extra.abst; }
+    float&       activity    ()              { assert(header.has_extra); return data[header.size].act; }
+    uint32_t     abstraction () const        { assert(header.has_extra); return data[header.size].abs; }
 
     Lit          subsumes    (const Clause& other) const;
     void         strengthen  (Lit p);
 };
 
 
+//=================================================================================================
+// ClauseAllocator -- a simple class for allocating memory for clauses:
+
+
+const CRef CRef_Undef = RegionAllocator<uint32_t>::Ref_Undef;
+const CRef CRef_Lazy  = RegionAllocator<uint32_t>::Ref_Undef - 1;
+class ClauseAllocator : public RegionAllocator<uint32_t>
+{
+    static int clauseWord32Size(int size, bool has_extra){
+        return (sizeof(Clause) + (sizeof(Lit) * (size + (int)has_extra))) / sizeof(uint32_t); }
+ public:
+    bool extra_clause_field;
+
+    ClauseAllocator(uint32_t start_cap) : RegionAllocator<uint32_t>(start_cap), extra_clause_field(false){}
+    ClauseAllocator() : extra_clause_field(false){}
+
+    void moveTo(ClauseAllocator& to){
+        to.extra_clause_field = extra_clause_field;
+        RegionAllocator<uint32_t>::moveTo(to); }
+
+    template<class Lits>
+    CRef alloc(const Lits& ps, bool learnt = false)
+    {
+        assert(sizeof(Lit)      == sizeof(uint32_t));
+        assert(sizeof(float)    == sizeof(uint32_t));
+        bool use_extra = learnt | extra_clause_field;
+
+        CRef cid = RegionAllocator<uint32_t>::alloc(clauseWord32Size(ps.size(), use_extra));
+        new (lea(cid)) Clause(ps, use_extra, learnt);
+
+        return cid;
+    }
+
+    // Deref, Load Effective Address (LEA), Inverse of LEA (AEL):
+    Clause&       operator[](Ref r)       { return (Clause&)RegionAllocator<uint32_t>::operator[](r); }
+    const Clause& operator[](Ref r) const { return (Clause&)RegionAllocator<uint32_t>::operator[](r); }
+    Clause*       lea       (Ref r)       { return (Clause*)RegionAllocator<uint32_t>::lea(r); }
+    const Clause* lea       (Ref r) const { return (Clause*)RegionAllocator<uint32_t>::lea(r); }
+    Ref           ael       (const Clause* t){ return RegionAllocator<uint32_t>::ael((uint32_t*)t); }
+
+    void free(CRef cid)
+    {
+        Clause& c = operator[](cid);
+        RegionAllocator<uint32_t>::free(clauseWord32Size(c.size(), c.has_extra()));
+    }
+
+    void reloc(CRef& cr, ClauseAllocator& to)
+    {
+        Clause& c = operator[](cr);
+        
+        if (c.reloced()) { cr = c.relocation(); return; }
+        
+        cr = to.alloc(c, c.learnt());
+        c.relocate(cr);
+        
+        // Copy extra data-fields: 
+        // (This could be cleaned-up. Generalize Clause-constructor to be applicable here instead?)
+        to[cr].mark(c.mark());
+        if (to[cr].learnt())         to[cr].activity() = c.activity();
+        else if (to[cr].has_extra()) to[cr].calcAbstraction();
+    }
+};
+
+
+//=================================================================================================
+// OccLists -- a class for maintaining occurence lists with lazy deletion:
+
+template<class Idx, class Vec, class Deleted>
+class OccLists
+{
+    vec<Vec>  occs;
+    vec<char> dirty;
+    vec<Idx>  dirties;
+    Deleted   deleted;
+
+ public:
+    OccLists(const Deleted& d) : deleted(d) {}
+    
+    void  init      (const Idx& idx){ occs.growTo(toInt(idx)+1); dirty.growTo(toInt(idx)+1, 0); }
+    // Vec&  operator[](const Idx& idx){ return occs[toInt(idx)]; }
+    Vec&  operator[](const Idx& idx){ return occs[toInt(idx)]; }
+    Vec&  lookup    (const Idx& idx){ if (dirty[toInt(idx)]) clean(idx); return occs[toInt(idx)]; }
+
+    void  cleanAll  ();
+    void  clean     (const Idx& idx);
+    void  smudge    (const Idx& idx){
+        if (dirty[toInt(idx)] == 0){
+            dirty[toInt(idx)] = 1;
+            dirties.push(idx);
+        }
+    }
+
+    void  clear(bool free = true){
+        occs   .clear(free);
+        dirty  .clear(free);
+        dirties.clear(free);
+    }
+};
+
+
+template<class Idx, class Vec, class Deleted>
+void OccLists<Idx,Vec,Deleted>::cleanAll()
+{
+    for (int i = 0; i < dirties.size(); i++)
+        // Dirties may contain duplicates so check here if a variable is already cleaned:
+        if (dirty[toInt(dirties[i])])
+            clean(dirties[i]);
+    dirties.clear();
+}
+
+
+template<class Idx, class Vec, class Deleted>
+void OccLists<Idx,Vec,Deleted>::clean(const Idx& idx)
+{
+    Vec& vec = occs[toInt(idx)];
+    int  i, j;
+    for (i = j = 0; i < vec.size(); i++)
+        if (!deleted(vec[i]))
+            vec[j++] = vec[i];
+    vec.shrink(i - j);
+    dirty[toInt(idx)] = 0;
+}
+
+
+//=================================================================================================
+// CMap -- a class for mapping clauses to values:
+
+
+template<class T>
+class CMap
+{
+    struct CRefHash {
+        uint32_t operator()(CRef cr) const { return (uint32_t)cr; } };
+
+    typedef Map<CRef, T, CRefHash> HashTable;
+    HashTable map;
+        
+ public:
+    // Size-operations:
+    void     clear       ()                           { map.clear(); }
+    int      size        ()                const      { return map.elems(); }
+
+    
+    // Insert/Remove/Test mapping:
+    void     insert      (CRef cr, const T& t){ map.insert(cr, t); }
+    void     growTo      (CRef cr, const T& t){ map.insert(cr, t); } // NOTE: for compatibility
+    void     remove      (CRef cr)            { map.remove(cr); }
+    bool     has         (CRef cr, T& t)      { return map.peek(cr, t); }
+
+    // Vector interface (the clause 'c' must already exist):
+    const T& operator [] (CRef cr) const      { return map[cr]; }
+    T&       operator [] (CRef cr)            { return map[cr]; }
+
+    // Iteration (not transparent at all at the moment):
+    int  bucket_count() const { return map.bucket_count(); }
+    const vec<typename HashTable::Pair>& bucket(int i) const { return map.bucket(i); }
+
+    // Move contents to other map:
+    void moveTo(CMap& other){ map.moveTo(other.map); }
+
+    // TMP debug:
+    void debug(){
+        printf(" --- size = %d, bucket_count = %d\n", size(), map.bucket_count()); }
+};
+
+
 /*_________________________________________________________________________________________________
 |
 |  subsumes : (other : const Clause&)  ->  Lit
@@ -167,16 +368,20 @@ public:
 |________________________________________________________________________________________________@*/
 inline Lit Clause::subsumes(const Clause& other) const
 {
-    if (other.size() < size() || (extra.abst & ~other.extra.abst) != 0)
+    //if (other.size() < size() || (extra.abst & ~other.extra.abst) != 0)
+    //if (other.size() < size() || (!learnt() && !other.learnt() && (extra.abst & ~other.extra.abst) != 0))
+    assert(!header.learnt);   assert(!other.header.learnt);
+    assert(header.has_extra); assert(other.header.has_extra);
+    if (other.header.size < header.size || (data[header.size].abs & ~other.data[other.header.size].abs) != 0)
         return lit_Error;
 
     Lit        ret = lit_Undef;
-    const Lit* c  = (const Lit*)(*this);
-    const Lit* d  = (const Lit*)other;
+    const Lit* c   = (const Lit*)(*this);
+    const Lit* d   = (const Lit*)other;
 
-    for (int i = 0; i < size(); i++) {
+    for (unsigned i = 0; i < header.size; i++) {
         // search for c[i] or ~c[i]
-        for (int j = 0; j < other.size(); j++)
+        for (unsigned j = 0; j < other.header.size; j++)
             if (c[i] == d[j])
                 goto ok;
             else if (ret == lit_Undef && c[i] == ~d[j]){
@@ -192,15 +397,13 @@ inline Lit Clause::subsumes(const Clause& other) const
     return ret;
 }
 
-
 inline void Clause::strengthen(Lit p)
 {
     remove(*this, p);
     calcAbstraction();
 }
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
+//=================================================================================================
+}
 
-#endif /* __CVC4__PROP__MINISAT__SOLVERTYPES_H */
+#endif
diff --git a/src/prop/minisat/doc/ReleaseNotes-2.2.0.txt b/src/prop/minisat/doc/ReleaseNotes-2.2.0.txt
new file mode 100644
index 000000000..7f084de2b
--- /dev/null
+++ b/src/prop/minisat/doc/ReleaseNotes-2.2.0.txt
@@ -0,0 +1,79 @@
+Release Notes for MiniSat 2.2.0
+===============================
+
+Changes since version 2.0:
+
+ * Started using a more standard release numbering.
+
+ * Includes some now well-known heuristics: phase-saving and luby
+   restarts. The old heuristics are still present and can be activated
+   if needed.
+
+ * Detection/Handling of out-of-memory and vector capacity
+   overflow. This is fairly new and relatively untested.
+
+ * Simple resource controls: CPU-time, memory, number of
+   conflicts/decisions.
+
+ * CPU-time limiting is implemented by a more general, but simple,
+   asynchronous interruption feature. This means that the solving
+   procedure can be interrupted from another thread or in a signal
+   handler.
+
+ * Improved portability with respect to building on Solaris and with
+   Visual Studio. This is not regularly tested and chances are that
+   this have been broken since, but should be fairly easy to fix if
+   so.
+
+ * Changed C++ file-extention to the less problematic ".cc".
+
+ * Source code is now namespace-protected
+
+ * Introducing a new Clause Memory Allocator that brings reduced
+   memory consumption on 64-bit architechtures and improved
+   performance (to some extent). The allocator uses a region-based
+   approach were all references to clauses are represented as a 32-bit
+   index into a global memory region that contains all clauses. To
+   free up and compact memory it uses a simple copying garbage
+   collector.
+
+ * Improved unit-propagation by Blocking Literals. For each entry in
+   the watcher lists, pair the pointer to a clause with some
+   (arbitrary) literal from the clause. The idea is that if the
+   literal is currently true (i.e. the clause is satisfied) the
+   watchers of the clause does not need to be altered. This can thus
+   be detected without touching the clause's memory at all. As often
+   as can be done cheaply, the blocking literal for entries to the
+   watcher list of a literal 'p' is set to the other literal watched
+   in the corresponding clause.
+
+ * Basic command-line/option handling system. Makes it easy to specify
+   options in the class that they affect, and whenever that class is
+   used in an executable, parsing of options and help messages are
+   brought in automatically.
+
+ * General clean-up and various minor bug-fixes.
+
+ * Changed implementation of variable-elimination/model-extension:
+    
+     - The interface is changed so that arbitrary remembering is no longer
+       possible. If you need to mention some variable again in the future,
+       this variable has to be frozen.
+    
+     - When eliminating a variable, only clauses that contain the variable
+       with one sign is necessary to store. Thereby making the other sign
+       a "default" value when extending models.
+    
+     - The memory consumption for eliminated clauses is further improved
+       by storing all eliminated clauses in a single contiguous vector.
+
+  * Some common utility code (I/O, Parsing, CPU-time, etc) is ripped
+    out and placed in a separate "utils" directory.
+
+  * The DIMACS parse is refactored so that it can be reused in other
+    applications (not very elegant, but at least possible).
+
+  * Some simple improvements to scalability of preprocessing, using
+    more lazy clause removal from data-structures and a couple of
+    ad-hoc limits (the longest clause that can be produced in variable
+    elimination, and the longest clause used in backward subsumption).
diff --git a/src/prop/minisat/mtl/Alg.h b/src/prop/minisat/mtl/Alg.h
index e636f2b87..bb1ee5ad2 100644
--- a/src/prop/minisat/mtl/Alg.h
+++ b/src/prop/minisat/mtl/Alg.h
@@ -1,5 +1,6 @@
 /*******************************************************************************************[Alg.h]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,22 +18,20 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
-#include "cvc4_private.h"
+#ifndef Minisat_Alg_h
+#define Minisat_Alg_h
 
-#ifndef CVC4_MiniSat_Alg_h
-#define CVC4_MiniSat_Alg_h
+#include "mtl/Vec.h"
 
-#include <cassert>
-
-namespace CVC4 {
-namespace prop {
-namespace minisat {
+namespace Minisat {
 
 //=================================================================================================
-// Useful functions on vectors
+// Useful functions on vector-like types:
 
+//=================================================================================================
+// Removing and searching for elements:
+//
 
-#if 1
 template<class V, class T>
 static inline void remove(V& ts, const T& t)
 {
@@ -42,17 +41,7 @@ static inline void remove(V& ts, const T& t)
     for (; j < ts.size()-1; j++) ts[j] = ts[j+1];
     ts.pop();
 }
-#else
-template<class V, class T>
-static inline void remove(V& ts, const T& t)
-{
-    int j = 0;
-    for (; j < ts.size() && ts[j] != t; j++);
-    assert(j < ts.size());
-    ts[j] = ts.last();
-    ts.pop();
-}
-#endif
+
 
 template<class V, class T>
 static inline bool find(V& ts, const T& t)
@@ -62,8 +51,34 @@ static inline bool find(V& ts, const T& t)
     return j < ts.size();
 }
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
 
-#endif /* CVC4_MiniSat_Alg_h */
+//=================================================================================================
+// Copying vectors with support for nested vector types:
+//
+
+// Base case:
+template<class T>
+static inline void copy(const T& from, T& to)
+{
+    to = from;
+}
+
+// Recursive case:
+template<class T>
+static inline void copy(const vec<T>& from, vec<T>& to, bool append = false)
+{
+    if (!append)
+        to.clear();
+    for (int i = 0; i < from.size(); i++){
+        to.push();
+        copy(from[i], to.last());
+    }
+}
+
+template<class T>
+static inline void append(const vec<T>& from, vec<T>& to){ copy(from, to, true); }
+
+//=================================================================================================
+}
+
+#endif
diff --git a/src/prop/minisat/mtl/Alloc.h b/src/prop/minisat/mtl/Alloc.h
new file mode 100644
index 000000000..76322b8b6
--- /dev/null
+++ b/src/prop/minisat/mtl/Alloc.h
@@ -0,0 +1,131 @@
+/*****************************************************************************************[Alloc.h]
+Copyright (c) 2008-2010, 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 Minisat_Alloc_h
+#define Minisat_Alloc_h
+
+#include "mtl/XAlloc.h"
+#include "mtl/Vec.h"
+
+namespace Minisat {
+
+//=================================================================================================
+// Simple Region-based memory allocator:
+
+template<class T>
+class RegionAllocator
+{
+    T*        memory;
+    uint32_t  sz;
+    uint32_t  cap;
+    uint32_t  wasted_;
+
+    void capacity(uint32_t min_cap);
+
+ public:
+    // TODO: make this a class for better type-checking?
+    typedef uint32_t Ref;
+    enum { Ref_Undef = UINT32_MAX };
+    enum { Unit_Size = sizeof(uint32_t) };
+
+    explicit RegionAllocator(uint32_t start_cap = 1024*1024) : memory(NULL), sz(0), cap(0), wasted_(0){ capacity(start_cap); }
+    ~RegionAllocator()
+    {
+        if (memory != NULL)
+            ::free(memory);
+    }
+
+
+    uint32_t size      () const      { return sz; }
+    uint32_t wasted    () const      { return wasted_; }
+
+    Ref      alloc     (int size); 
+    void     free      (int size)    { wasted_ += size; }
+
+    // Deref, Load Effective Address (LEA), Inverse of LEA (AEL):
+    T&       operator[](Ref r)       { assert(r >= 0 && r < sz); return memory[r]; }
+    const T& operator[](Ref r) const { assert(r >= 0 && r < sz); return memory[r]; }
+
+    T*       lea       (Ref r)       { assert(r >= 0 && r < sz); return &memory[r]; }
+    const T* lea       (Ref r) const { assert(r >= 0 && r < sz); return &memory[r]; }
+    Ref      ael       (const T* t)  { assert((void*)t >= (void*)&memory[0] && (void*)t < (void*)&memory[sz-1]);
+        return  (Ref)(t - &memory[0]); }
+
+    void     moveTo(RegionAllocator& to) {
+        if (to.memory != NULL) ::free(to.memory);
+        to.memory = memory;
+        to.sz = sz;
+        to.cap = cap;
+        to.wasted_ = wasted_;
+
+        memory = NULL;
+        sz = cap = wasted_ = 0;
+    }
+
+
+};
+
+template<class T>
+void RegionAllocator<T>::capacity(uint32_t min_cap)
+{
+    if (cap >= min_cap) return;
+
+    uint32_t prev_cap = cap;
+    while (cap < min_cap){
+        // NOTE: Multiply by a factor (13/8) without causing overflow, then add 2 and make the
+        // result even by clearing the least significant bit. The resulting sequence of capacities
+        // is carefully chosen to hit a maximum capacity that is close to the '2^32-1' limit when
+        // using 'uint32_t' as indices so that as much as possible of this space can be used.
+        uint32_t delta = ((cap >> 1) + (cap >> 3) + 2) & ~1;
+        cap += delta;
+
+        if (cap <= prev_cap)
+            throw OutOfMemoryException();
+    }
+    // printf(" .. (%p) cap = %u\n", this, cap);
+
+    assert(cap > 0);
+    memory = (T*)xrealloc(memory, sizeof(T)*cap);
+}
+
+
+template<class T>
+typename RegionAllocator<T>::Ref
+RegionAllocator<T>::alloc(int size)
+{ 
+    // printf("ALLOC called (this = %p, size = %d)\n", this, size); fflush(stdout);
+    assert(size > 0);
+    capacity(sz + size);
+
+    uint32_t prev_sz = sz;
+    sz += size;
+    
+    // Handle overflow:
+    if (sz < prev_sz)
+        throw OutOfMemoryException();
+
+    return prev_sz;
+}
+
+
+//=================================================================================================
+}
+
+#endif
diff --git a/src/prop/minisat/mtl/BasicHeap.h b/src/prop/minisat/mtl/BasicHeap.h
deleted file mode 100644
index cb6a7cbd8..000000000
--- a/src/prop/minisat/mtl/BasicHeap.h
+++ /dev/null
@@ -1,109 +0,0 @@
-/******************************************************************************************[Heap.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.
-**************************************************************************************************/
-
-#include "cvc4_private.h"
-
-#ifndef CVC4_MiniSat_BasicHeap_h
-#define CVC4_MiniSat_BasicHeap_h
-
-#include "Vec.h"
-
-namespace CVC4 {
-namespace prop {
-namespace minisat {
-
-//=================================================================================================
-// A heap implementation with support for decrease/increase key.
-
-
-template<class Comp>
-class BasicHeap {
-    Comp     lt;
-    vec<int> heap;     // heap of ints
-
-    // Index "traversal" functions
-    static inline int left  (int i) { return i*2+1; }
-    static inline int right (int i) { return (i+1)*2; }
-    static inline int parent(int i) { return (i-1) >> 1; }
-
-    inline void percolateUp(int i)
-    {
-        int x = heap[i];
-        while (i != 0 && lt(x, heap[parent(i)])){
-            heap[i]          = heap[parent(i)];
-            i                = parent(i);
-        }
-        heap   [i] = x;
-    }
-
-
-    inline void percolateDown(int i)
-    {
-        int x = heap[i];
-        while (left(i) < heap.size()){
-            int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i);
-            if (!lt(heap[child], x)) break;
-            heap[i]          = heap[child];
-            i                = child;
-        }
-        heap[i] = x;
-    }
-
-
-    bool heapProperty(int i) {
-        return i >= heap.size()
-            || ((i == 0 || !lt(heap[i], heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); }
-
-
-  public:
-    BasicHeap(const C& c) : comp(c) { }
-
-    int  size      ()                     const { return heap.size(); }
-    bool empty     ()                     const { return heap.size() == 0; }
-    int  operator[](int index)            const { return heap[index+1]; }
-    void clear     (bool dealloc = false)       { heap.clear(dealloc); }
-    void insert    (int n)                      { heap.push(n); percolateUp(heap.size()-1); }
-
-
-    int  removeMin() {
-        int r   = heap[0];
-        heap[0] = heap.last();
-        heap.pop();
-        if (heap.size() > 1) percolateDown(0);
-        return r; 
-    }
-
-
-    // DEBUG: consistency checking
-    bool heapProperty() {
-        return heapProperty(1); }
-
-
-    // COMPAT: should be removed
-    int  getmin    ()      { return removeMin(); }
-};
-
-
-//=================================================================================================
-
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
-
-#endif /* CVC4_MiniSat_BasicHeap_h */
diff --git a/src/prop/minisat/mtl/BoxedVec.h b/src/prop/minisat/mtl/BoxedVec.h
deleted file mode 100644
index 7cf5ba14f..000000000
--- a/src/prop/minisat/mtl/BoxedVec.h
+++ /dev/null
@@ -1,156 +0,0 @@
-/*******************************************************************************************[Vec.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.
-**************************************************************************************************/
-
-#include "cvc4_private.h"
-
-#ifndef CVC4_MiniSat_BoxedVec_h
-#define CVC4_MiniSat_BoxedVec_h
-
-#include <cstdlib>
-#include <cassert>
-#include <new>
-
-namespace CVC4 {
-namespace prop {
-namespace minisat {
-
-//=================================================================================================
-// Automatically resizable arrays
-//
-// NOTE! Don't use this vector on datatypes that cannot be re-located in memory (with realloc)
-
-template<class T>
-class bvec {
-
-    static inline int imin(int x, int y) {
-        int mask = (x-y) >> (sizeof(int)*8-1);
-        return (x&mask) + (y&(~mask)); }
-
-    static inline int imax(int x, int y) {
-        int mask = (y-x) >> (sizeof(int)*8-1);
-        return (x&mask) + (y&(~mask)); }
-
-    struct Vec_t {
-        int sz;
-        int cap;
-        T   data[0];
-
-        static Vec_t* alloc(Vec_t* x, int size){
-            x = (Vec_t*)realloc((void*)x, sizeof(Vec_t) + sizeof(T)*size);
-            x->cap = size;
-            return x;
-        }
-
-    };
-
-    Vec_t* ref;
-
-    static const int init_size = 2;
-    static int   nextSize (int current) { return (current * 3 + 1) >> 1; }
-    static int   fitSize  (int needed)  { int x; for (x = init_size; needed > x; x = nextSize(x)); return x; }
-
-    void fill (int size) {
-        assert(ref != NULL);
-        for (T* i = ref->data; i < ref->data + size; i++)
-            new (i) T();
-    }
-
-    void fill (int size, const T& pad) {
-        assert(ref != NULL);
-        for (T* i = ref->data; i < ref->data + size; i++)
-            new (i) T(pad);
-    }
-
-    // Don't allow copying (error prone):
-    altvec<T>&  operator = (altvec<T>& other) { assert(0); }
-    altvec (altvec<T>& other)                  { assert(0); }
-
-public:
-    void     clear  (bool dealloc = false) {
-        if (ref != NULL){
-            for (int i = 0; i < ref->sz; i++)
-                (*ref).data[i].~T();
-
-            if (dealloc) {
-                free(ref); ref = NULL;
-            }else
-                ref->sz = 0;
-        }
-    }
-
-    // Constructors:
-    altvec(void)                   : ref (NULL) { }
-    altvec(int size)               : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size);      ref->sz = size; }
-    altvec(int size, const T& pad) : ref (Vec_t::alloc(NULL, fitSize(size))) { fill(size, pad); ref->sz = size; }
-   ~altvec(void) { clear(true); }
-
-    // Ownership of underlying array:
-    operator T*       (void)           { return ref->data; }     // (unsafe but convenient)
-    operator const T* (void) const     { return ref->data; }
-
-    // Size operations:
-    int      size   (void) const       { return ref != NULL ? ref->sz : 0; }
-
-    void     pop    (void)             { assert(ref != NULL && ref->sz > 0); int last = --ref->sz; ref->data[last].~T(); }
-    void     push   (const T& elem) {
-        int size = ref != NULL ? ref->sz  : 0;
-        int cap  = ref != NULL ? ref->cap : 0;
-        if (size == cap){
-            cap = cap != 0 ? nextSize(cap) : init_size;
-            ref = Vec_t::alloc(ref, cap);
-        }
-        //new (&ref->data[size]) T(elem);
-        ref->data[size] = elem;
-        ref->sz = size+1;
-    }
-
-    void     push   () {
-        int size = ref != NULL ? ref->sz  : 0;
-        int cap  = ref != NULL ? ref->cap : 0;
-        if (size == cap){
-            cap = cap != 0 ? nextSize(cap) : init_size;
-            ref = Vec_t::alloc(ref, cap);
-        }
-        new (&ref->data[size]) T();
-        ref->sz = size+1;
-    }
-
-    void     shrink (int nelems)             { for (int i = 0; i < nelems; i++) pop(); }
-    void     shrink_(int nelems)             { for (int i = 0; i < nelems; i++) pop(); }
-    void     growTo (int size)               { while (this->size() < size) push(); }
-    void     growTo (int size, const T& pad) { while (this->size() < size) push(pad); }
-    void     capacity (int size)             { growTo(size); }
-
-    const T& last  (void) const              { return ref->data[ref->sz-1]; }
-    T&       last  (void)                    { return ref->data[ref->sz-1]; }
-
-    // Vector interface:
-    const T& operator [] (int index) const  { return ref->data[index]; }
-    T&       operator [] (int index)        { return ref->data[index]; }
-
-    void copyTo(altvec<T>& copy) const { copy.clear(); for (int i = 0; i < size(); i++) copy.push(ref->data[i]); }
-    void moveTo(altvec<T>& dest) { dest.clear(true); dest.ref = ref; ref = NULL; }
-
-};
-
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
-
-#endif /* CVC4_MiniSat_BoxedVec_h */
diff --git a/src/prop/minisat/mtl/Heap.h b/src/prop/minisat/mtl/Heap.h
index 20d379b1d..226407e77 100644
--- a/src/prop/minisat/mtl/Heap.h
+++ b/src/prop/minisat/mtl/Heap.h
@@ -1,5 +1,6 @@
 /******************************************************************************************[Heap.h]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,17 +18,12 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
-#include "cvc4_private.h"
+#ifndef Minisat_Heap_h
+#define Minisat_Heap_h
 
-#ifndef CVC4_MiniSat_Heap_h
-#define CVC4_MiniSat_Heap_h
+#include "mtl/Vec.h"
 
-#include "Vec.h"
-#include <cassert>
-
-namespace CVC4 {
-namespace prop {
-namespace minisat {
+namespace Minisat {
 
 //=================================================================================================
 // A heap implementation with support for decrease/increase key.
@@ -35,9 +31,9 @@ namespace minisat {
 
 template<class Comp>
 class Heap {
-    Comp     lt;
-    vec<int> heap;     // heap of ints
-    vec<int> indices;  // int -> index in heap
+    Comp     lt;       // The heap is a minimum-heap with respect to this comparator
+    vec<int> heap;     // Heap of integers
+    vec<int> indices;  // Each integers position (index) in the Heap
 
     // Index "traversal" functions
     static inline int left  (int i) { return i*2+1; }
@@ -45,20 +41,23 @@ class Heap {
     static inline int parent(int i) { return (i-1) >> 1; }
 
 
-    inline void percolateUp(int i)
+    void percolateUp(int i)
     {
-        int x = heap[i];
-        while (i != 0 && lt(x, heap[parent(i)])){
-            heap[i]          = heap[parent(i)];
-            indices[heap[i]] = i;
-            i                = parent(i);
+        int x  = heap[i];
+        int p  = parent(i);
+        
+        while (i != 0 && lt(x, heap[p])){
+            heap[i]          = heap[p];
+            indices[heap[p]] = i;
+            i                = p;
+            p                = parent(p);
         }
         heap   [i] = x;
         indices[x] = i;
     }
 
 
-    inline void percolateDown(int i)
+    void percolateDown(int i)
     {
         int x = heap[i];
         while (left(i) < heap.size()){
@@ -73,11 +72,6 @@ class Heap {
     }
 
 
-    bool heapProperty (int i) const {
-        return i >= heap.size()
-            || ((i == 0 || !lt(heap[i], heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); }
-
-
   public:
     Heap(const Comp& c) : lt(c) { }
 
@@ -86,10 +80,20 @@ class Heap {
     bool inHeap    (int n)     const { return n < indices.size() && indices[n] >= 0; }
     int  operator[](int index) const { assert(index < heap.size()); return heap[index]; }
 
-    void decrease  (int n) { assert(inHeap(n)); percolateUp(indices[n]); }
 
-    // RENAME WHEN THE DEPRECATED INCREASE IS REMOVED.
-    void increase_ (int n) { assert(inHeap(n)); percolateDown(indices[n]); }
+    void decrease  (int n) { assert(inHeap(n)); percolateUp  (indices[n]); }
+    void increase  (int n) { assert(inHeap(n)); percolateDown(indices[n]); }
+
+
+    // Safe variant of insert/decrease/increase:
+    void update(int n)
+    {
+        if (!inHeap(n))
+            insert(n);
+        else {
+            percolateUp(indices[n]);
+            percolateDown(indices[n]); }
+    }
 
 
     void insert(int n)
@@ -99,7 +103,7 @@ class Heap {
 
         indices[n] = heap.size();
         heap.push(n);
-        percolateUp(indices[n]);
+        percolateUp(indices[n]); 
     }
 
 
@@ -111,69 +115,34 @@ class Heap {
         indices[x]       = -1;
         heap.pop();
         if (heap.size() > 1) percolateDown(0);
-        return x;
+        return x; 
     }
 
 
-    void clear(bool dealloc = false)
-    {
+    // Rebuild the heap from scratch, using the elements in 'ns':
+    void build(vec<int>& ns) {
         for (int i = 0; i < heap.size(); i++)
             indices[heap[i]] = -1;
-#ifdef NDEBUG
-        for (int i = 0; i < indices.size(); i++)
-            assert(indices[i] == -1);
-#endif
-        heap.clear(dealloc);
-    }
-
-
-    // Fool proof variant of insert/decrease/increase
-    void update (int n)
-    {
-        if (!inHeap(n))
-            insert(n);
-        else {
-            percolateUp(indices[n]);
-            percolateDown(indices[n]);
-        }
-    }
+        heap.clear();
 
+        for (int i = 0; i < ns.size(); i++){
+            indices[ns[i]] = i;
+            heap.push(ns[i]); }
 
-    // Delete elements from the heap using a given filter function (-object).
-    // *** this could probaly be replaced with a more general "buildHeap(vec<int>&)" method ***
-    template <class F>
-    void filter(const F& filt) {
-        int i,j;
-        for (i = j = 0; i < heap.size(); i++)
-            if (filt(heap[i])){
-                heap[j]          = heap[i];
-                indices[heap[i]] = j++;
-            }else
-                indices[heap[i]] = -1;
-
-        heap.shrink(i - j);
         for (int i = heap.size() / 2 - 1; i >= 0; i--)
             percolateDown(i);
-
-        assert(heapProperty());
     }
 
-
-    // DEBUG: consistency checking
-    bool heapProperty() const {
-        return heapProperty(1); }
-
-
-    // COMPAT: should be removed
-    void setBounds (int n) { }
-    void increase  (int n) { decrease(n); }
-    int  getmin    ()      { return removeMin(); }
-
+    void clear(bool dealloc = false) 
+    { 
+        for (int i = 0; i < heap.size(); i++)
+            indices[heap[i]] = -1;
+        heap.clear(dealloc); 
+    }
 };
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
 
 //=================================================================================================
-#endif /* CVC4_MiniSat_Heap_h */
+}
+
+#endif
diff --git a/src/prop/minisat/mtl/IntTypes.h b/src/prop/minisat/mtl/IntTypes.h
new file mode 100644
index 000000000..c48816284
--- /dev/null
+++ b/src/prop/minisat/mtl/IntTypes.h
@@ -0,0 +1,42 @@
+/**************************************************************************************[IntTypes.h]
+Copyright (c) 2009-2010, 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 Minisat_IntTypes_h
+#define Minisat_IntTypes_h
+
+#ifdef __sun
+    // Not sure if there are newer versions that support C99 headers. The
+    // needed features are implemented in the headers below though:
+
+#   include <sys/int_types.h>
+#   include <sys/int_fmtio.h>
+#   include <sys/int_limits.h>
+
+#else
+
+#   include <stdint.h>
+#   include <inttypes.h>
+
+#endif
+
+#include <limits.h>
+
+//=================================================================================================
+
+#endif
diff --git a/src/prop/minisat/mtl/Map.h b/src/prop/minisat/mtl/Map.h
index 715b84da4..8a82d0e28 100644
--- a/src/prop/minisat/mtl/Map.h
+++ b/src/prop/minisat/mtl/Map.h
@@ -1,5 +1,5 @@
 /*******************************************************************************************[Map.h]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2006-2010, 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,
@@ -17,18 +17,13 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
-#include "cvc4_private.h"
+#ifndef Minisat_Map_h
+#define Minisat_Map_h
 
-#ifndef CVC4_MiniSat_Map_h
-#define CVC4_MiniSat_Map_h
+#include "mtl/IntTypes.h"
+#include "mtl/Vec.h"
 
-#include <stdint.h>
-
-#include "Vec.h"
-
-namespace CVC4 {
-namespace prop {
-namespace minisat {
+namespace Minisat {
 
 //=================================================================================================
 // Default hash/equals functions
@@ -40,6 +35,12 @@ template<class K> struct Equal { bool     operator()(const K& k1, const K& k2) c
 template<class K> struct DeepHash  { uint32_t operator()(const K* k)               const { return hash(*k);  } };
 template<class K> struct DeepEqual { bool     operator()(const K* k1, const K* k2) const { return *k1 == *k2; } };
 
+static inline uint32_t hash(uint32_t x){ return x; }
+static inline uint32_t hash(uint64_t x){ return (uint32_t)x; }
+static inline uint32_t hash(int32_t x) { return (uint32_t)x; }
+static inline uint32_t hash(int64_t x) { return (uint32_t)x; }
+
+
 //=================================================================================================
 // Some primes
 //
@@ -53,8 +54,10 @@ static const int primes [nprimes] = { 31, 73, 151, 313, 643, 1291, 2593, 5233, 1
 
 template<class K, class D, class H = Hash<K>, class E = Equal<K> >
 class Map {
+ public:
     struct Pair { K key; D data; };
 
+ private:
     H          hash;
     E          equals;
 
@@ -66,45 +69,89 @@ class Map {
     Map<K,D,H,E>&  operator = (Map<K,D,H,E>& other) { assert(0); }
                    Map        (Map<K,D,H,E>& other) { assert(0); }
 
+    bool    checkCap(int new_size) const { return new_size > cap; }
+
     int32_t index  (const K& k) const { return hash(k) % cap; }
-    void   _insert (const K& k, const D& d) { table[index(k)].push(); table[index(k)].last().key = k; table[index(k)].last().data = d; }
+    void   _insert (const K& k, const D& d) { 
+        vec<Pair>& ps = table[index(k)];
+        ps.push(); ps.last().key = k; ps.last().data = d; }
+
     void    rehash () {
         const vec<Pair>* old = table;
 
+        int old_cap = cap;
         int newsize = primes[0];
         for (int i = 1; newsize <= cap && i < nprimes; i++)
            newsize = primes[i];
 
         table = new vec<Pair>[newsize];
+        cap   = newsize;
 
-        for (int i = 0; i < cap; i++){
+        for (int i = 0; i < old_cap; i++){
             for (int j = 0; j < old[i].size(); j++){
                 _insert(old[i][j].key, old[i][j].data); }}
 
         delete [] old;
 
-        cap = newsize;
+        // printf(" --- rehashing, old-cap=%d, new-cap=%d\n", cap, newsize);
     }
 
+    
+ public:
 
-    public:
-
-     Map () : table(NULL), cap(0), size(0) {}
-     Map (const H& h, const E& e) : Map(), hash(h), equals(e) {}
+    Map () : table(NULL), cap(0), size(0) {}
+    Map (const H& h, const E& e) : hash(h), equals(e), table(NULL), cap(0), size(0){}
     ~Map () { delete [] table; }
 
-    void insert (const K& k, const D& d) { if (size+1 > cap / 2) rehash(); _insert(k, d); size++; }
-    bool peek   (const K& k, D& d) {
+    // PRECONDITION: the key must already exist in the map.
+    const D& operator [] (const K& k) const
+    {
+        assert(size != 0);
+        const D*         res = NULL;
+        const vec<Pair>& ps  = table[index(k)];
+        for (int i = 0; i < ps.size(); i++)
+            if (equals(ps[i].key, k))
+                res = &ps[i].data;
+        assert(res != NULL);
+        return *res;
+    }
+
+    // PRECONDITION: the key must already exist in the map.
+    D& operator [] (const K& k)
+    {
+        assert(size != 0);
+        D*         res = NULL;
+        vec<Pair>& ps  = table[index(k)];
+        for (int i = 0; i < ps.size(); i++)
+            if (equals(ps[i].key, k))
+                res = &ps[i].data;
+        assert(res != NULL);
+        return *res;
+    }
+
+    // PRECONDITION: the key must *NOT* exist in the map.
+    void insert (const K& k, const D& d) { if (checkCap(size+1)) rehash(); _insert(k, d); size++; }
+    bool peek   (const K& k, D& d) const {
         if (size == 0) return false;
         const vec<Pair>& ps = table[index(k)];
         for (int i = 0; i < ps.size(); i++)
             if (equals(ps[i].key, k)){
                 d = ps[i].data;
-                return true; }
+                return true; } 
         return false;
     }
 
-    void remove (const K& k) {
+    bool has   (const K& k) const {
+        if (size == 0) return false;
+        const vec<Pair>& ps = table[index(k)];
+        for (int i = 0; i < ps.size(); i++)
+            if (equals(ps[i].key, k))
+                return true;
+        return false;
+    }
+
+    // PRECONDITION: the key must exist in the map.
+    void remove(const K& k) {
         assert(table != NULL);
         vec<Pair>& ps = table[index(k)];
         int j = 0;
@@ -112,6 +159,7 @@ class Map {
         assert(j < ps.size());
         ps[j] = ps.last();
         ps.pop();
+        size--;
     }
 
     void clear  () {
@@ -119,10 +167,27 @@ class Map {
         delete [] table;
         table = NULL;
     }
+
+    int  elems() const { return size; }
+    int  bucket_count() const { return cap; }
+
+    // NOTE: the hash and equality objects are not moved by this method:
+    void moveTo(Map& other){
+        delete [] other.table;
+
+        other.table = table;
+        other.cap   = cap;
+        other.size  = size;
+
+        table = NULL;
+        size = cap = 0;
+    }
+
+    // NOTE: given a bit more time, I could make a more C++-style iterator out of this:
+    const vec<Pair>& bucket(int i) const { return table[i]; }
 };
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
+//=================================================================================================
+}
 
-#endif /* CVC4_MiniSat_Map_h */
+#endif
diff --git a/src/prop/minisat/mtl/Queue.h b/src/prop/minisat/mtl/Queue.h
index 291a1f2e3..17567d694 100644
--- a/src/prop/minisat/mtl/Queue.h
+++ b/src/prop/minisat/mtl/Queue.h
@@ -1,5 +1,6 @@
 /*****************************************************************************************[Queue.h]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,77 +18,52 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
-#include "cvc4_private.h"
+#ifndef Minisat_Queue_h
+#define Minisat_Queue_h
 
-#ifndef CVC4_MiniSat_Queue_h
-#define CVC4_MiniSat_Queue_h
+#include "mtl/Vec.h"
 
-#include "Vec.h"
-
-namespace CVC4 {
-namespace prop {
-namespace minisat {
+namespace Minisat {
 
 //=================================================================================================
 
-
-template <class T>
+template<class T>
 class Queue {
-    vec<T>  elems;
+    vec<T>  buf;
     int     first;
+    int     end;
 
 public:
-    Queue(void) : first(0) { }
-
-    void insert(T x)   { elems.push(x); }
-    T    peek  () const { return elems[first]; }
-    void pop   () { first++; }
-
-    void clear(bool dealloc = false)   { elems.clear(dealloc); first = 0; }
-    int  size(void)    { return elems.size() - first; }
-
-    //bool has(T x) { for (int i = first; i < elems.size(); i++) if (elems[i] == x) return true; return false; }
-
-    const T& operator [] (int index) const  { return elems[first + index]; }
-
+    typedef T Key;
+
+    Queue() : buf(1), first(0), end(0) {}
+
+    void clear (bool dealloc = false) { buf.clear(dealloc); buf.growTo(1); first = end = 0; }
+    int  size  () const { return (end >= first) ? end - first : end - first + buf.size(); }
+
+    const T& operator [] (int index) const  { assert(index >= 0); assert(index < size()); return buf[(first + index) % buf.size()]; }
+    T&       operator [] (int index)        { assert(index >= 0); assert(index < size()); return buf[(first + index) % buf.size()]; }
+
+    T    peek  () const { assert(first != end); return buf[first]; }
+    void pop   () { assert(first != end); first++; if (first == buf.size()) first = 0; }
+    void insert(T elem) {   // INVARIANT: buf[end] is always unused
+        buf[end++] = elem;
+        if (end == buf.size()) end = 0;
+        if (first == end){  // Resize:
+            vec<T>  tmp((buf.size()*3 + 1) >> 1);
+            //**/printf("queue alloc: %d elems (%.1f MB)\n", tmp.size(), tmp.size() * sizeof(T) / 1000000.0);
+            int     i = 0;
+            for (int j = first; j < buf.size(); j++) tmp[i++] = buf[j];
+            for (int j = 0    ; j < end       ; j++) tmp[i++] = buf[j];
+            first = 0;
+            end   = buf.size();
+            tmp.moveTo(buf);
+        }
+    }
 };
 
-//template<class T>
-//class Queue {
-//    vec<T>  buf;
-//    int     first;
-//    int     end;
-//
-//public:
-//    typedef T Key;
-//
-//    Queue() : buf(1), first(0), end(0) {}
-//
-//    void clear () { buf.shrinkTo(1); first = end = 0; }
-//    int  size  () { return (end >= first) ? end - first : end - first + buf.size(); }
-//
-//    T    peek  () { assert(first != end); return buf[first]; }
-//    void pop   () { assert(first != end); first++; if (first == buf.size()) first = 0; }
-//    void insert(T elem) {   // INVARIANT: buf[end] is always unused
-//        buf[end++] = elem;
-//        if (end == buf.size()) end = 0;
-//        if (first == end){  // Resize:
-//            vec<T>  tmp((buf.size()*3 + 1) >> 1);
-//            //**/printf("queue alloc: %d elems (%.1f MB)\n", tmp.size(), tmp.size() * sizeof(T) / 1000000.0);
-//            int     i = 0;
-//            for (int j = first; j < buf.size(); j++) tmp[i++] = buf[j];
-//            for (int j = 0    ; j < end       ; j++) tmp[i++] = buf[j];
-//            first = 0;
-//            end   = buf.size();
-//            tmp.moveTo(buf);
-//        }
-//    }
-//};
 
 //=================================================================================================
+}
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
-
-#endif /* CVC4_MiniSat_Queue_h */
+#endif
diff --git a/src/prop/minisat/mtl/Sort.h b/src/prop/minisat/mtl/Sort.h
index 19e89803b..e9313ef86 100644
--- a/src/prop/minisat/mtl/Sort.h
+++ b/src/prop/minisat/mtl/Sort.h
@@ -1,5 +1,6 @@
 /******************************************************************************************[Sort.h]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2003-2007, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,21 +18,17 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
-#include "cvc4_private.h"
+#ifndef Minisat_Sort_h
+#define Minisat_Sort_h
 
-#ifndef CVC4_MiniSat_Sort_h
-#define CVC4_MiniSat_Sort_h
-
-#include "Vec.h"
-
-namespace CVC4 {
-namespace prop {
-namespace minisat {
+#include "mtl/Vec.h"
 
 //=================================================================================================
 // Some sorting algorithms for vec's
 
 
+namespace Minisat {
+
 template<class T>
 struct LessThan_default {
     bool operator () (T x, T y) { return x < y; }
@@ -96,9 +93,6 @@ template <class T> void sort(vec<T>& v) {
 
 
 //=================================================================================================
+}
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
-
-#endif /* CVC4_MiniSat_Sort_h */
+#endif
diff --git a/src/prop/minisat/mtl/Vec.h b/src/prop/minisat/mtl/Vec.h
index 364991aa9..9e220852e 100644
--- a/src/prop/minisat/mtl/Vec.h
+++ b/src/prop/minisat/mtl/Vec.h
@@ -1,5 +1,6 @@
 /*******************************************************************************************[Vec.h]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2003-2007, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,18 +18,16 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
-#include "cvc4_private.h"
+#ifndef Minisat_Vec_h
+#define Minisat_Vec_h
 
-#ifndef CVC4_MiniSat_Vec_h
-#define CVC4_MiniSat_Vec_h
-
-#include <cstdlib>
-#include <cassert>
+#include <assert.h>
 #include <new>
 
-namespace CVC4 {
-namespace prop {
-namespace minisat {
+#include "mtl/IntTypes.h"
+#include "mtl/XAlloc.h"
+
+namespace Minisat {
 
 //=================================================================================================
 // Automatically resizable arrays
@@ -41,93 +40,83 @@ class vec {
     int sz;
     int cap;
 
-    void     init(int size, const T& pad);
-    void     grow(int min_cap);
-
     // Don't allow copying (error prone):
     vec<T>&  operator = (vec<T>& other) { assert(0); return *this; }
              vec        (vec<T>& other) { assert(0); }
-
-    static inline int imin(int x, int y) {
-        int mask = (x-y) >> (sizeof(int)*8-1);
-        return (x&mask) + (y&(~mask)); }
-
-    static inline int imax(int x, int y) {
-        int mask = (y-x) >> (sizeof(int)*8-1);
-        return (x&mask) + (y&(~mask)); }
+             
+    // Helpers for calculating next capacity:
+    static inline int  imax   (int x, int y) { int mask = (y-x) >> (sizeof(int)*8-1); return (x&mask) + (y&(~mask)); }
+    //static inline void nextCap(int& cap){ cap += ((cap >> 1) + 2) & ~1; }
+    static inline void nextCap(int& cap){ cap += ((cap >> 1) + 2) & ~1; }
 
 public:
-    // Types:
-    typedef int Key;
-    typedef T   Datum;
-
     // Constructors:
-    vec(void)                   : data(NULL) , sz(0)   , cap(0)    { }
-    vec(int size)               : data(NULL) , sz(0)   , cap(0)    { growTo(size); }
+    vec()                       : data(NULL) , sz(0)   , cap(0)    { }
+    explicit vec(int size)      : data(NULL) , sz(0)   , cap(0)    { growTo(size); }
     vec(int size, const T& pad) : data(NULL) , sz(0)   , cap(0)    { growTo(size, pad); }
-    vec(T* array, int size)     : data(array), sz(size), cap(size) { }      // (takes ownership of array -- will be deallocated with 'free()')
-   ~vec(void)                                                      { clear(true); }
+   ~vec()                                                          { clear(true); }
 
-    // Ownership of underlying array:
-    T*       release  (void)           { T* ret = data; data = NULL; sz = 0; cap = 0; return ret; }
-    operator T*       (void)           { return data; }     // (unsafe but convenient)
-    operator const T* (void) const     { return data; }
+    // Pointer to first element:
+    operator T*       (void)           { return data; }
 
     // Size operations:
-    int      size   (void) const       { return sz; }
-    void     shrink (int nelems)       { assert(nelems <= sz); for (int i = 0; i < nelems; i++) sz--, data[sz].~T(); }
-    void     shrink_(int nelems)       { assert(nelems <= sz); sz -= nelems; }
-    void     pop    (void)             { sz--, data[sz].~T(); }
-    void     growTo (int size);
-    void     growTo (int size, const T& pad);
-    void     clear  (bool dealloc = false);
-    void     capacity (int size) { grow(size); }
+    int      size     (void) const     { return sz; }
+    void     shrink   (int nelems)     { assert(nelems <= sz); for (int i = 0; i < nelems; i++) sz--, data[sz].~T(); }
+    void     shrink_  (int nelems)     { assert(nelems <= sz); sz -= nelems; }
+    int      capacity (void) const     { return cap; }
+    void     capacity (int min_cap);
+    void     growTo   (int size);
+    void     growTo   (int size, const T& pad);
+    void     clear    (bool dealloc = false);
 
     // Stack interface:
-#if 1
-    void     push  (void)              { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } new (&data[sz]) T(); sz++; }
-    //void     push  (const T& elem)     { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } new (&data[sz]) T(elem); sz++; }
-    void     push  (const T& elem)     { if (sz == cap) { cap = imax(2, (cap*3+1)>>1); data = (T*)realloc(data, cap * sizeof(T)); } data[sz++] = elem; }
+    void     push  (void)              { if (sz == cap) capacity(sz+1); new (&data[sz]) T(); sz++; }
+    void     push  (const T& elem)     { if (sz == cap) capacity(sz+1); data[sz++] = elem; }
     void     push_ (const T& elem)     { assert(sz < cap); data[sz++] = elem; }
-#else
-    void     push  (void)              { if (sz == cap) grow(sz+1); new (&data[sz]) T()    ; sz++; }
-    void     push  (const T& elem)     { if (sz == cap) grow(sz+1); new (&data[sz]) T(elem); sz++; }
-#endif
+    void     pop   (void)              { assert(sz > 0); sz--, data[sz].~T(); }
+    // NOTE: it seems possible that overflow can happen in the 'sz+1' expression of 'push()', but
+    // in fact it can not since it requires that 'cap' is equal to INT_MAX. This in turn can not
+    // happen given the way capacities are calculated (below). Essentially, all capacities are
+    // even, but INT_MAX is odd.
 
     const T& last  (void) const        { return data[sz-1]; }
     T&       last  (void)              { return data[sz-1]; }
 
     // Vector interface:
-    const T& operator [] (int index) const  { return data[index]; }
-    T&       operator [] (int index)        { return data[index]; }
-
+    const T& operator [] (int index) const { return data[index]; }
+    T&       operator [] (int index)       { return data[index]; }
 
     // Duplicatation (preferred instead):
-    void copyTo(vec<T>& copy) const { copy.clear(); copy.growTo(sz); for (int i = 0; i < sz; i++) new (&copy[i]) T(data[i]); }
+    void copyTo(vec<T>& copy) const { copy.clear(); copy.growTo(sz); for (int i = 0; i < sz; i++) copy[i] = data[i]; }
     void moveTo(vec<T>& dest) { dest.clear(true); dest.data = data; dest.sz = sz; dest.cap = cap; data = NULL; sz = 0; cap = 0; }
 };
 
+
 template<class T>
-void vec<T>::grow(int min_cap) {
-    if (min_cap <= cap) return;
-    if (cap == 0) cap = (min_cap >= 2) ? min_cap : 2;
-    else          do cap = (cap*3+1) >> 1; while (cap < min_cap);
-    data = (T*)realloc(data, cap * sizeof(T)); }
+void vec<T>::capacity(int min_cap) {
+    if (cap >= min_cap) return;
+    int add = imax((min_cap - cap + 1) & ~1, ((cap >> 1) + 2) & ~1);   // NOTE: grow by approximately 3/2
+    if (add > INT_MAX - cap || ((data = (T*)::realloc(data, (cap += add) * sizeof(T))) == NULL) && errno == ENOMEM)
+        throw OutOfMemoryException();
+ }
+
 
 template<class T>
 void vec<T>::growTo(int size, const T& pad) {
     if (sz >= size) return;
-    grow(size);
-    for (int i = sz; i < size; i++) new (&data[i]) T(pad);
+    capacity(size);
+    for (int i = sz; i < size; i++) data[i] = pad;
     sz = size; }
 
+
 template<class T>
 void vec<T>::growTo(int size) {
     if (sz >= size) return;
-    grow(size);
+    capacity(size);
     for (int i = sz; i < size; i++) new (&data[i]) T();
     sz = size; }
 
+
 template<class T>
 void vec<T>::clear(bool dealloc) {
     if (data != NULL){
@@ -135,8 +124,7 @@ void vec<T>::clear(bool dealloc) {
         sz = 0;
         if (dealloc) free(data), data = NULL, cap = 0; } }
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
+//=================================================================================================
+}
 
-#endif /* CVC4_MiniSat_Vec_h */
+#endif
diff --git a/src/prop/minisat/mtl/XAlloc.h b/src/prop/minisat/mtl/XAlloc.h
new file mode 100644
index 000000000..1da176028
--- /dev/null
+++ b/src/prop/minisat/mtl/XAlloc.h
@@ -0,0 +1,45 @@
+/****************************************************************************************[XAlloc.h]
+Copyright (c) 2009-2010, 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 Minisat_XAlloc_h
+#define Minisat_XAlloc_h
+
+#include <errno.h>
+#include <stdlib.h>
+
+namespace Minisat {
+
+//=================================================================================================
+// Simple layer on top of malloc/realloc to catch out-of-memory situtaions and provide some typing:
+
+class OutOfMemoryException{};
+static inline void* xrealloc(void *ptr, size_t size)
+{
+    void* mem = realloc(ptr, size);
+    if (mem == NULL && errno == ENOMEM){
+        throw OutOfMemoryException();
+    }else
+        return mem;
+}
+
+//=================================================================================================
+}
+
+#endif
diff --git a/src/prop/minisat/mtl/config.mk b/src/prop/minisat/mtl/config.mk
new file mode 100644
index 000000000..b5c36fc6b
--- /dev/null
+++ b/src/prop/minisat/mtl/config.mk
@@ -0,0 +1,6 @@
+##
+##  This file is for system specific configurations. For instance, on
+##  some systems the path to zlib needs to be added. Example:
+##
+##  CFLAGS += -I/usr/local/include
+##  LFLAGS += -L/usr/local/lib
diff --git a/src/prop/minisat/mtl/template.mk b/src/prop/minisat/mtl/template.mk
index 15f023fb3..3f443fc38 100644
--- a/src/prop/minisat/mtl/template.mk
+++ b/src/prop/minisat/mtl/template.mk
@@ -5,45 +5,53 @@
 ##        "make d"  for a debug version (no optimizations).
 ##        "make"    for the standard version (optimized, but with debug information and assertions active)
 
-CSRCS     ?= $(wildcard *.C)
-CHDRS     ?= $(wildcard *.h)
-COBJS     ?= $(addsuffix .o, $(basename $(CSRCS)))
+PWD        = $(shell pwd)
+EXEC      ?= $(notdir $(PWD))
+
+CSRCS      = $(wildcard $(PWD)/*.cc) 
+DSRCS      = $(foreach dir, $(DEPDIR), $(filter-out $(MROOT)/$(dir)/Main.cc, $(wildcard $(MROOT)/$(dir)/*.cc)))
+CHDRS      = $(wildcard $(PWD)/*.h)
+COBJS      = $(CSRCS:.cc=.o) $(DSRCS:.cc=.o)
 
 PCOBJS     = $(addsuffix p,  $(COBJS))
 DCOBJS     = $(addsuffix d,  $(COBJS))
 RCOBJS     = $(addsuffix r,  $(COBJS))
 
-EXEC      ?= $(notdir $(shell pwd))
-LIB       ?= $(EXEC)
 
 CXX       ?= g++
-CFLAGS    ?= -Wall
+CFLAGS    ?= -Wall -Wno-parentheses
 LFLAGS    ?= -Wall
 
 COPTIMIZE ?= -O3
 
-.PHONY : s p d r rs lib libd clean 
+CFLAGS    += -I$(MROOT) -D __STDC_LIMIT_MACROS -D __STDC_FORMAT_MACROS
+LFLAGS    += -lz
+
+.PHONY : s p d r rs clean 
 
 s:	$(EXEC)
 p:	$(EXEC)_profile
 d:	$(EXEC)_debug
 r:	$(EXEC)_release
 rs:	$(EXEC)_static
-lib:	lib$(LIB).a
-libd:	lib$(LIB)d.a
+
+libs:	lib$(LIB)_standard.a
+libp:	lib$(LIB)_profile.a
+libd:	lib$(LIB)_debug.a
+libr:	lib$(LIB)_release.a
 
 ## Compile options
-%.o:			CFLAGS +=$(COPTIMIZE) -ggdb -D DEBUG
-%.op:			CFLAGS +=$(COPTIMIZE) -pg -ggdb -D NDEBUG
-%.od:			CFLAGS +=-O0 -ggdb -D DEBUG # -D INVARIANTS
-%.or:			CFLAGS +=$(COPTIMIZE) -D NDEBUG
+%.o:			CFLAGS +=$(COPTIMIZE) -g -D DEBUG
+%.op:			CFLAGS +=$(COPTIMIZE) -pg -g -D NDEBUG
+%.od:			CFLAGS +=-O0 -g -D DEBUG
+%.or:			CFLAGS +=$(COPTIMIZE) -g -D NDEBUG
 
 ## Link options
-$(EXEC):		LFLAGS := -ggdb $(LFLAGS)
-$(EXEC)_profile:	LFLAGS := -ggdb -pg $(LFLAGS)
-$(EXEC)_debug:		LFLAGS := -ggdb $(LFLAGS)
-$(EXEC)_release:	LFLAGS := $(LFLAGS)
-$(EXEC)_static:		LFLAGS := --static $(LFLAGS)
+$(EXEC):		LFLAGS += -g
+$(EXEC)_profile:	LFLAGS += -g -pg
+$(EXEC)_debug:		LFLAGS += -g
+#$(EXEC)_release:	LFLAGS += ...
+$(EXEC)_static:		LFLAGS += --static
 
 ## Dependencies
 $(EXEC):		$(COBJS)
@@ -52,39 +60,48 @@ $(EXEC)_debug:		$(DCOBJS)
 $(EXEC)_release:	$(RCOBJS)
 $(EXEC)_static:		$(RCOBJS)
 
-lib$(LIB).a:	$(filter-out Main.or, $(RCOBJS))
-lib$(LIB)d.a:	$(filter-out Main.od, $(DCOBJS))
+lib$(LIB)_standard.a:	$(filter-out */Main.o,  $(COBJS))
+lib$(LIB)_profile.a:	$(filter-out */Main.op, $(PCOBJS))
+lib$(LIB)_debug.a:	$(filter-out */Main.od, $(DCOBJS))
+lib$(LIB)_release.a:	$(filter-out */Main.or, $(RCOBJS))
 
 
 ## Build rule
-%.o %.op %.od %.or:	%.C
-	@echo Compiling: "$@ ( $< )"
+%.o %.op %.od %.or:	%.cc
+	@echo Compiling: $(subst $(MROOT)/,,$@)
 	@$(CXX) $(CFLAGS) -c -o $@ $<
 
 ## Linking rules (standard/profile/debug/release)
 $(EXEC) $(EXEC)_profile $(EXEC)_debug $(EXEC)_release $(EXEC)_static:
-	@echo Linking: "$@ ( $^ )"
+	@echo Linking: "$@ ( $(foreach f,$^,$(subst $(MROOT)/,,$f)) )"
 	@$(CXX) $^ $(LFLAGS) -o $@
 
-## Library rule
-lib$(LIB).a lib$(LIB)d.a:
-	@echo Library: "$@ ( $^ )"
-	@rm -f $@
-	@ar cq $@ $^
+## Library rules (standard/profile/debug/release)
+lib$(LIB)_standard.a lib$(LIB)_profile.a lib$(LIB)_release.a lib$(LIB)_debug.a:
+	@echo Making library: "$@ ( $(foreach f,$^,$(subst $(MROOT)/,,$f)) )"
+	@$(AR) -rcsv $@ $^
+
+## Library Soft Link rule:
+libs libp libd libr:
+	@echo "Making Soft Link: $^ -> lib$(LIB).a"
+	@ln -sf $^ lib$(LIB).a
 
 ## Clean rule
 clean:
 	@rm -f $(EXEC) $(EXEC)_profile $(EXEC)_debug $(EXEC)_release $(EXEC)_static \
-	  $(COBJS) $(PCOBJS) $(DCOBJS) $(RCOBJS) *.core depend.mak lib$(LIB).a lib$(LIB)d.a
+	  $(COBJS) $(PCOBJS) $(DCOBJS) $(RCOBJS) *.core depend.mk 
 
 ## Make dependencies
 depend.mk: $(CSRCS) $(CHDRS)
-	@echo Making dependencies ...
-	@$(CXX) $(CFLAGS) -MM $(CSRCS) > depend.mk
-	@cp depend.mk /tmp/depend.mk.tmp
-	@sed "s/o:/op:/" /tmp/depend.mk.tmp >> depend.mk
-	@sed "s/o:/od:/" /tmp/depend.mk.tmp >> depend.mk
-	@sed "s/o:/or:/" /tmp/depend.mk.tmp >> depend.mk
-	@rm /tmp/depend.mk.tmp
-
+	@echo Making dependencies
+	@$(CXX) $(CFLAGS) -I$(MROOT) \
+	   $(CSRCS) -MM | sed 's|\(.*\):|$(PWD)/\1 $(PWD)/\1r $(PWD)/\1d $(PWD)/\1p:|' > depend.mk
+	@for dir in $(DEPDIR); do \
+	      if [ -r $(MROOT)/$${dir}/depend.mk ]; then \
+		  echo Depends on: $${dir}; \
+		  cat $(MROOT)/$${dir}/depend.mk >> depend.mk; \
+	      fi; \
+	  done
+
+-include $(MROOT)/mtl/config.mk
 -include depend.mk
diff --git a/src/prop/minisat/simp/Main.cc b/src/prop/minisat/simp/Main.cc
index b6d194631..e59d73be0 100644
--- a/src/prop/minisat/simp/Main.cc
+++ b/src/prop/minisat/simp/Main.cc
@@ -1,5 +1,6 @@
-/******************************************************************************************[Main.C]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+/*****************************************************************************************[Main.cc]
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007,      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,
@@ -17,399 +18,194 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 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
+#include "utils/System.h"
+#include "utils/ParseUtils.h"
+#include "utils/Options.h"
+#include "core/Dimacs.h"
+#include "simp/SimpSolver.h"
 
+using namespace Minisat;
 
 //=================================================================================================
-// 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;
+void printStats(Solver& solver)
+{
+    double cpu_time = cpuTime();
+    double mem_used = memUsedPeak();
+    printf("restarts              : %"PRIu64"\n", solver.starts);
+    printf("conflicts             : %-12"PRIu64"   (%.0f /sec)\n", solver.conflicts   , solver.conflicts   /cpu_time);
+    printf("decisions             : %-12"PRIu64"   (%4.2f %% random) (%.0f /sec)\n", solver.decisions, (float)solver.rnd_decisions*100 / (float)solver.decisions, solver.decisions   /cpu_time);
+    printf("propagations          : %-12"PRIu64"   (%.0f /sec)\n", solver.propagations, solver.propagations/cpu_time);
+    printf("conflict literals     : %-12"PRIu64"   (%4.2f %% deleted)\n", solver.tot_literals, (solver.max_literals - solver.tot_literals)*100 / (double)solver.max_literals);
+    if (mem_used != 0) printf("Memory used           : %.2f MB\n", mem_used);
+    printf("CPU time              : %g s\n", cpu_time);
 }
 
 
-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); }
-    }
-}
+static Solver* solver;
+// Terminate by notifying the solver and back out gracefully. This is mainly to have a test-case
+// for this feature of the Solver as it may take longer than an immediate call to '_exit()'.
+static void SIGINT_interrupt(int signum) { solver->interrupt(); }
 
-// 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); }
+// Note that '_exit()' rather than 'exit()' has to be used. The reason is that 'exit()' calls
+// destructors and may cause deadlocks if a malloc/free function happens to be running (these
+// functions are guarded by locks for multithreaded use).
+static void SIGINT_exit(int signum) {
+    printf("\n"); printf("*** INTERRUPTED ***\n");
+    if (solver->verbosity > 0){
+        printStats(*solver);
+        printf("\n"); printf("*** 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");
+    try {
+        setUsageHelp("USAGE: %s [options] <input-file> <result-output-file>\n\n  where input may be either in plain or gzipped DIMACS.\n");
+        // printf("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");
+        fpu_control_t oldcw, newcw;
+        _FPU_GETCW(oldcw); newcw = (oldcw & ~_FPU_EXTENDED) | _FPU_DOUBLE; _FPU_SETCW(newcw);
+        printf("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();
+        // Extra options:
+        //
+        IntOption    verb   ("MAIN", "verb",   "Verbosity level (0=silent, 1=some, 2=more).", 1, IntRange(0, 2));
+        BoolOption   pre    ("MAIN", "pre",    "Completely turn on/off any preprocessing.", true);
+        StringOption dimacs ("MAIN", "dimacs", "If given, stop after preprocessing and write the result to this file.");
+        IntOption    cpu_lim("MAIN", "cpu-lim","Limit on CPU time allowed in seconds.\n", INT32_MAX, IntRange(0, INT32_MAX));
+        IntOption    mem_lim("MAIN", "mem-lim","Limit on memory usage in megabytes.\n", INT32_MAX, IntRange(0, INT32_MAX));
+
+        parseOptions(argc, argv, true);
+        
+        SimpSolver  S;
+        double      initial_time = cpuTime();
+
+        if (!pre) S.eliminate(true);
+
+        S.verbosity = verb;
+        
+        solver = &S;
+        // Use signal handlers that forcibly quit until the solver will be able to respond to
+        // interrupts:
+        signal(SIGINT, SIGINT_exit);
+        signal(SIGXCPU,SIGINT_exit);
+
+        // Set limit on CPU-time:
+        if (cpu_lim != INT32_MAX){
+            rlimit rl;
+            getrlimit(RLIMIT_CPU, &rl);
+            if (rl.rlim_max == RLIM_INFINITY || (rlim_t)cpu_lim < rl.rlim_max){
+                rl.rlim_cur = cpu_lim;
+                if (setrlimit(RLIMIT_CPU, &rl) == -1)
+                    printf("WARNING! Could not set resource limit: CPU-time.\n");
+            } }
+
+        // Set limit on virtual memory:
+        if (mem_lim != INT32_MAX){
+            rlim_t new_mem_lim = (rlim_t)mem_lim * 1024*1024;
+            rlimit rl;
+            getrlimit(RLIMIT_AS, &rl);
+            if (rl.rlim_max == RLIM_INFINITY || new_mem_lim < rl.rlim_max){
+                rl.rlim_cur = new_mem_lim;
+                if (setrlimit(RLIMIT_AS, &rl) == -1)
+                    printf("WARNING! Could not set resource limit: Virtual memory.\n");
+            } }
+        
+        if (argc == 1)
+            printf("Reading from standard input... Use '--help' for help.\n");
+
+        gzFile in = (argc == 1) ? gzdopen(0, "rb") : gzopen(argv[1], "rb");
+        if (in == NULL)
+            printf("ERROR! Could not open file: %s\n", argc == 1 ? "<stdin>" : argv[1]), exit(1);
+        
+        if (S.verbosity > 0){
+            printf("============================[ Problem Statistics ]=============================\n");
+            printf("|                                                                             |\n"); }
+        
+        parse_DIMACS(in, S);
+        gzclose(in);
+        FILE* res = (argc >= 3) ? fopen(argv[2], "wb") : NULL;
+
+        if (S.verbosity > 0){
+            printf("|  Number of variables:  %12d                                         |\n", S.nVars());
+            printf("|  Number of clauses:    %12d                                         |\n", S.nClauses()); }
+        
+        double parsed_time = cpuTime();
+        if (S.verbosity > 0)
+            printf("|  Parse time:           %12.2f s                                       |\n", parsed_time - initial_time);
+
+        // Change to signal-handlers that will only notify the solver and allow it to terminate
+        // voluntarily:
+        signal(SIGINT, SIGINT_interrupt);
+        signal(SIGXCPU,SIGINT_interrupt);
 
-    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++;
+        double simplified_time = cpuTime();
+        if (S.verbosity > 0){
+            printf("|  Simplification time:  %12.2f s                                       |\n", simplified_time - parsed_time);
+            printf("|                                                                             |\n"); }
+
+        if (!S.okay()){
+            if (res != NULL) fprintf(res, "UNSAT\n"), fclose(res);
+            if (S.verbosity > 0){
+                printf("===============================================================================\n");
+                printf("Solved by simplification\n");
+                printStats(S);
+                printf("\n"); }
+            printf("UNSATISFIABLE\n");
+            exit(20);
         }
-        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");
+        if (dimacs){
+            if (S.verbosity > 0)
+                printf("==============================[ Writing DIMACS ]===============================\n");
+            S.toDimacs((const char*)dimacs);
+            if (S.verbosity > 0)
+                printStats(S);
+            exit(0);
+        }
 
-        printf(ret ? "SATISFIABLE\n" : "UNSATISFIABLE\n");
+        vec<Lit> dummy;
+        lbool ret = S.solveLimited(dummy);
+        
+        if (S.verbosity > 0){
+            printStats(S);
+            printf("\n"); }
+        printf(ret == l_True ? "SATISFIABLE\n" : ret == l_False ? "UNSATISFIABLE\n" : "INDETERMINATE\n");
         if (res != NULL){
-            if (ret){
+            if (ret == l_True){
                 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
+            }else if (ret == l_False)
                 fprintf(res, "UNSAT\n");
+            else
+                fprintf(res, "INDET\n");
             fclose(res);
         }
+
 #ifdef NDEBUG
-        exit(ret ? 10 : 20);     // (faster than "return", which will invoke the destructor for 'Solver')
+        exit(ret == l_True ? 10 : ret == l_False ? 20 : 0);     // (faster than "return", which will invoke the destructor for 'Solver')
+#else
+        return (ret == l_True ? 10 : ret == l_False ? 20 : 0);
 #endif
+    } catch (OutOfMemoryException&){
+        printf("===============================================================================\n");
+        printf("INDETERMINATE\n");
+        exit(0);
     }
-
 }
diff --git a/src/prop/minisat/simp/Makefile b/src/prop/minisat/simp/Makefile
index a1db4951b..27b45f493 100644
--- a/src/prop/minisat/simp/Makefile
+++ b/src/prop/minisat/simp/Makefile
@@ -1,11 +1,4 @@
-MTL       = ../mtl
-CORE      = ../core
-CHDRS     = $(wildcard *.h) $(wildcard $(MTL)/*.h)
 EXEC      = minisat
-CFLAGS    = -I$(MTL) -I$(CORE) -Wall -ffloat-store
-LFLAGS    = -lz
+DEPDIR    = mtl utils core
 
-CSRCS     = $(wildcard *.C)
-COBJS     = $(addsuffix .o, $(basename $(CSRCS))) $(CORE)/Solver.o
-
-include ../mtl/template.mk
+include $(MROOT)/mtl/template.mk
diff --git a/src/prop/minisat/simp/SimpSolver.cc b/src/prop/minisat/simp/SimpSolver.cc
index 00f93402f..32ac223d6 100644
--- a/src/prop/minisat/simp/SimpSolver.cc
+++ b/src/prop/minisat/simp/SimpSolver.cc
@@ -1,5 +1,6 @@
-/************************************************************************************[SimpSolver.C]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+/***********************************************************************************[SimpSolver.cc]
+Copyright (c) 2006,      Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,77 +18,94 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
-#include "Sort.h"
-#include "SimpSolver.h"
+#include "mtl/Sort.h"
+#include "simp/SimpSolver.h"
+#include "utils/System.h"
+
+using namespace Minisat;
+using namespace CVC4;
+
+//=================================================================================================
+// Options:
+
+
+static const char* _cat = "SIMP";
+
+static BoolOption   opt_use_asymm        (_cat, "asymm",        "Shrink clauses by asymmetric branching.", false);
+static BoolOption   opt_use_rcheck       (_cat, "rcheck",       "Check if a clause is already implied. (costly)", false);
+static BoolOption   opt_use_elim         (_cat, "elim",         "Perform variable elimination.", true);
+static IntOption    opt_grow             (_cat, "grow",         "Allow a variable elimination step to grow by a number of clauses.", 0);
+static IntOption    opt_clause_lim       (_cat, "cl-lim",       "Variables are not eliminated if it produces a resolvent with a length above this limit. -1 means no limit", 20,   IntRange(-1, INT32_MAX));
+static IntOption    opt_subsumption_lim  (_cat, "sub-lim",      "Do not check if subsumption against a clause larger than this. -1 means no limit.", 1000, IntRange(-1, INT32_MAX));
+static DoubleOption opt_simp_garbage_frac(_cat, "simp-gc-frac", "The fraction of wasted memory allowed before a garbage collection is triggered during simplification.",  0.5, DoubleRange(0, false, HUGE_VAL, false));
 
 
 //=================================================================================================
 // Constructor/Destructor:
 
-namespace CVC4 {
-namespace prop {
-namespace minisat {
 
-SimpSolver::SimpSolver(SatSolver* proxy, context::Context* context) :
+SimpSolver::SimpSolver(CVC4::prop::SatSolver* proxy, CVC4::context::Context* context) :
     Solver(proxy, context)
-  , grow               (0)
-  , asymm_mode         (false)
-  , redundancy_check   (false)
+  , grow               (opt_grow)
+  , clause_lim         (opt_clause_lim)
+  , subsumption_lim    (opt_subsumption_lim)
+  , simp_garbage_frac  (opt_simp_garbage_frac)
+  , use_asymm          (opt_use_asymm)
+  , use_rcheck         (opt_use_rcheck)
+  , use_elim           (opt_use_elim)
   , merges             (0)
   , asymm_lits         (0)
-  , remembered_clauses (0)
+  , eliminated_vars    (0)
   , elimorder          (1)
   , use_simplification (true)
+  , occurs             (ClauseDeleted(ca))
   , elim_heap          (ElimLt(n_occ))
   , bwdsub_assigns     (0)
+  , n_touched          (0)
 {
     vec<Lit> dummy(1,lit_Undef);
-    bwdsub_tmpunit   = Clause_new(dummy);
-    remove_satisfied = false;
+    ca.extra_clause_field = true; // NOTE: must happen before allocating the dummy clause below.
+    bwdsub_tmpunit        = ca.alloc(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, bool theoryAtom) {
     Var v = Solver::newVar(sign, dvar,theoryAtom);
 
+    frozen    .push((char)theoryAtom);
+    eliminated.push((char)false);
+
     if (use_simplification){
-        n_occ    .push(0);
-        n_occ    .push(0);
-        occurs   .push();
-        frozen   .push((char)theoryAtom);
-        touched  .push(0);
-        elim_heap.insert(v);
-        elimtable.push();
+        n_occ     .push(0);
+        n_occ     .push(0);
+        occurs    .init(v);
+        touched   .push(0);
+        elim_heap .insert(v);
     }
     return v; }
 
 
 
-bool SimpSolver::solve(const vec<Lit>& assumps, bool do_simp, bool turn_off_simp) {
+lbool SimpSolver::solve_(bool do_simp, bool turn_off_simp)
+{
     vec<Var> extra_frozen;
-    bool     result = true;
+    lbool    result = l_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]);
+        for (int i = 0; i < assumptions.size(); i++){
+            Var v = var(assumptions[i]);
 
             // If an assumption has been eliminated, remember it.
-            if (isEliminated(v))
-                remember(v);
+            assert(!isEliminated(v));
 
             if (!frozen[v]){
                 // Freeze and store.
@@ -95,18 +113,16 @@ bool SimpSolver::solve(const vec<Lit>& assumps, bool do_simp, bool turn_off_simp
                 extra_frozen.push(v);
             } }
 
-        result = eliminate(turn_off_simp);
+        result = lbool(eliminate(turn_off_simp));
     }
 
-    if (result)
-        result = Solver::solve(assumps);
+    if (result == l_True)
+        result = Solver::solve_();
+    else if (verbosity >= 1)
+        printf("===============================================================================\n");
 
-    if (result) {
+    if (result == l_True)
         extendModel();
-#ifndef NDEBUG
-        verifyModel();
-#endif
-    }
 
     if (do_simp)
         // Unfreeze the assumptions that were frozen:
@@ -118,35 +134,39 @@ bool SimpSolver::solve(const vec<Lit>& assumps, bool do_simp, bool turn_off_simp
 
 
 
-bool SimpSolver::addClause(vec<Lit>& ps, ClauseType type)
+bool SimpSolver::addClause_(vec<Lit>& ps, ClauseType type)
 {
+#ifndef NDEBUG
     for (int i = 0; i < ps.size(); i++)
-        if (isEliminated(var(ps[i])))
-            remember(var(ps[i]));
+        assert(!isEliminated(var(ps[i])));
+#endif
 
     int nclauses = clauses.size();
 
-    if (redundancy_check && implied(ps))
+    if (use_rcheck && implied(ps))
         return true;
 
-    if (!Solver::addClause(ps, type))
+    if (!Solver::addClause_(ps, type))
         return false;
 
     if (use_simplification && clauses.size() == nclauses + 1){
-        Clause& c = *clauses.last();
-
-        subsumption_queue.insert(&c);
-
+        CRef          cr = clauses.last();
+        const Clause& c  = ca[cr];
+
+        // NOTE: the clause is added to the queue immediately and then
+        // again during 'gatherTouchedClauses()'. If nothing happens
+        // in between, it will only be checked once. Otherwise, it may
+        // be checked twice unnecessarily. This is an unfortunate
+        // consequence of how backward subsumption is used to mimic
+        // forward subsumption.
+        subsumption_queue.insert(cr);
         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);
+            occurs[var(c[i])].push(cr);
             n_occ[toInt(c[i])]++;
             touched[var(c[i])] = 1;
-            assert(elimtable[var(c[i])].order == 0);
+            n_touched++;
             if (elim_heap.inHeap(var(c[i])))
-                elim_heap.increase_(var(c[i]));
+                elim_heap.increase(var(c[i]));
         }
     }
 
@@ -154,65 +174,45 @@ bool SimpSolver::addClause(vec<Lit>& ps, ClauseType type)
 }
 
 
-void SimpSolver::removeClause(Clause& c)
+void SimpSolver::removeClause(CRef cr)
 {
+    const Clause& c = ca[cr];
     Debug("minisat") << "SimpSolver::removeClause(" << c << ")" << std::endl;
-    assert(!c.learnt());
 
     if (use_simplification)
         for (int i = 0; i < c.size(); i++){
             n_occ[toInt(c[i])]--;
             updateElimHeap(var(c[i]));
+            occurs.smudge(var(c[i]));
         }
 
-    detachClause(c);
-    c.mark(1);
+    Solver::removeClause(cr);
 }
 
 
-bool SimpSolver::strengthenClause(Clause& c, Lit l)
+bool SimpSolver::strengthenClause(CRef cr, Lit l)
 {
+    Clause& c = ca[cr];
     assert(decisionLevel() == 0);
-    assert(c.mark() == 0);
-    assert(!c.learnt());
-    assert(find(watches[toInt(~c[0])], &c));
-    assert(find(watches[toInt(~c[1])], &c));
+    assert(use_simplification);
 
     // 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;
-    }
+    subsumption_queue.insert(cr);
 
-    // if subsumption-indexing is active perform the necessary updates
-    if (use_simplification){
-        remove(occurs[var(l)], &c);
+    if (c.size() == 2){
+        removeClause(cr);
+        c.strengthen(l);
+    }else{
+        detachClause(cr, true);
+        c.strengthen(l);
+        attachClause(cr);
+        remove(occurs[var(l)], cr);
         n_occ[toInt(l)]--;
         updateElimHeap(var(l));
     }
 
-    return c.size() == 1 ? enqueue(c[0]) && propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) == NULL : true;
+    return c.size() == 1 ? enqueue(c[0]) && propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) == CRef_Undef : true;
 }
 
 
@@ -223,18 +223,17 @@ bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v, vec<Lit>& ou
     out_clause.clear();
 
     bool  ps_smallest = _ps.size() < _qs.size();
-    const Clause& ps =  ps_smallest ? _qs : _ps;
-    const Clause& qs =  ps_smallest ? _ps : _qs;
+    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 (var(ps[j]) == var(qs[i]))
                     if (ps[j] == ~qs[i])
                         return false;
                     else
                         goto next;
-                }
             out_clause.push(qs[i]);
         }
         next:;
@@ -249,25 +248,27 @@ bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v, vec<Lit>& ou
 
 
 // Returns FALSE if clause is always satisfied.
-bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v)
+bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v, int& size)
 {
     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;
+    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;
+
+    size = ps.size()-1;
 
     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 (var(__ps[j]) == var(__qs[i]))
                     if (__ps[j] == ~__qs[i])
                         return false;
                     else
                         goto next;
-                }
+            size++;
         }
         next:;
     }
@@ -278,23 +279,29 @@ bool SimpSolver::merge(const Clause& _ps, const Clause& _qs, Var v)
 
 void SimpSolver::gatherTouchedClauses()
 {
-    //fprintf(stderr, "Gathering clauses for backwards subsumption\n");
-    int ntouched = 0;
-    for (int i = 0; i < touched.size(); i++)
+    if (n_touched == 0) return;
+
+    int i,j;
+    for (i = j = 0; i < subsumption_queue.size(); i++)
+        if (ca[subsumption_queue[i]].mark() == 0)
+            ca[subsumption_queue[i]].mark(2);
+
+    for (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){
+            const vec<CRef>& cs = occurs.lookup(i);
+            for (j = 0; j < cs.size(); j++)
+                if (ca[cs[j]].mark() == 0){
                     subsumption_queue.insert(cs[j]);
-                    cs[j]->mark(2);
+                    ca[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);
+    for (i = 0; i < subsumption_queue.size(); i++)
+        if (ca[subsumption_queue[i]].mark() == 2)
+            ca[subsumption_queue[i]].mark(0);
+
+    n_touched = 0;
 }
 
 
@@ -312,7 +319,7 @@ bool SimpSolver::implied(const vec<Lit>& c)
             uncheckedEnqueue(~c[i]);
         }
 
-    bool result = propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) != NULL;
+    bool result = propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) != CRef_Undef;
     cancelUntil(0);
     return result;
 }
@@ -328,20 +335,26 @@ bool SimpSolver::backwardSubsumptionCheck(bool verbose)
 
     while (subsumption_queue.size() > 0 || bwdsub_assigns < trail.size()){
 
+        // Empty subsumption queue and return immediately on user-interrupt:
+        if (asynch_interrupt){
+            subsumption_queue.clear();
+            bwdsub_assigns = trail.size();
+            break; }
+
         // 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);
+            ca[bwdsub_tmpunit][0] = l;
+            ca[bwdsub_tmpunit].calcAbstraction();
             subsumption_queue.insert(bwdsub_tmpunit); }
 
-        Clause&  c = *subsumption_queue.peek(); subsumption_queue.pop();
+        CRef    cr = subsumption_queue.peek(); subsumption_queue.pop();
+        Clause& c  = ca[cr];
 
         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);
+            printf("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.
 
@@ -352,21 +365,21 @@ bool SimpSolver::backwardSubsumptionCheck(bool verbose)
                 best = var(c[i]);
 
         // Search all candidates:
-        vec<Clause*>& _cs = getOccurs(best);
-        Clause**       cs = (Clause**)_cs;
+        vec<CRef>& _cs = occurs.lookup(best);
+        CRef*       cs = (CRef*)_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]);
+            else if (!ca[cs[j]].mark() &&  cs[j] != cr && (subsumption_lim == -1 || ca[cs[j]].size() < subsumption_lim)){
+                Lit l = c.subsumes(ca[cs[j]]);
 
                 if (l == lit_Undef)
-                    subsumed++, removeClause(*cs[j]);
+                    subsumed++, removeClause(cs[j]);
                 else if (l != lit_Error){
                     deleted_literals++;
 
-                    if (!strengthenClause(*cs[j], ~l))
+                    if (!strengthenClause(cs[j], ~l))
                         return false;
 
                     // Did current candidate get deleted from cs? Then check candidate at index j again:
@@ -380,8 +393,9 @@ bool SimpSolver::backwardSubsumptionCheck(bool verbose)
 }
 
 
-bool SimpSolver::asymm(Var v, Clause& c)
+bool SimpSolver::asymm(Var v, CRef cr)
 {
+    Clause& c = ca[cr];
     assert(decisionLevel() == 0);
 
     if (c.mark() || satisfied(c)) return true;
@@ -394,10 +408,10 @@ bool SimpSolver::asymm(Var v, Clause& c)
         else
             l = c[i];
 
-    if (propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) != NULL){
+    if (propagate(CHECK_WITHOUTH_PROPAGATION_QUICK) != CRef_Undef){
         cancelUntil(0);
         asymm_lits++;
-        if (!strengthenClause(c, l))
+        if (!strengthenClause(cr, l))
             return false;
     }else
         cancelUntil(0);
@@ -408,304 +422,299 @@ bool SimpSolver::asymm(Var v, Clause& c)
 
 bool SimpSolver::asymmVar(Var v)
 {
-    assert(!frozen[v]);
     assert(use_simplification);
 
-    vec<Clause*>  pos, neg;
-    const vec<Clause*>& cls = getOccurs(v);
+    const vec<CRef>& cls = occurs.lookup(v);
 
     if (value(v) != l_Undef || cls.size() == 0)
         return true;
 
     for (int i = 0; i < cls.size(); i++)
-        if (!asymm(v, *cls[i]))
+        if (!asymm(v, cls[i]))
             return false;
 
     return backwardSubsumptionCheck();
 }
 
 
-void SimpSolver::verifyModel()
+static void mkElimClause(vec<uint32_t>& elimclauses, Lit x)
 {
-    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);
+    elimclauses.push(toInt(x));
+    elimclauses.push(1);
 }
 
 
-bool SimpSolver::eliminateVar(Var v, bool fail)
+static void mkElimClause(vec<uint32_t>& elimclauses, Var v, Clause& c)
 {
-    if (!fail && asymm_mode && !asymmVar(v))    return false;
+    int first = elimclauses.size();
+    int v_pos = -1;
+
+    // Copy clause to elimclauses-vector. Remember position where the
+    // variable 'v' occurs:
+    for (int i = 0; i < c.size(); i++){
+        elimclauses.push(toInt(c[i]));
+        if (var(c[i]) == v)
+            v_pos = i + first;
+    }
+    assert(v_pos != -1);
+
+    // Swap the first literal with the 'v' literal, so that the literal
+    // containing 'v' will occur first in the clause:
+    uint32_t tmp = elimclauses[v_pos];
+    elimclauses[v_pos] = elimclauses[first];
+    elimclauses[first] = tmp;
+
+    // Store the length of the clause last:
+    elimclauses.push(c.size());
+}
+
 
-    const vec<Clause*>& cls = getOccurs(v);
 
-//  if (value(v) != l_Undef || cls.size() == 0) return true;
-    if (value(v) != l_Undef) return true;
+bool SimpSolver::eliminateVar(Var v)
+{
+    assert(!frozen[v]);
+    assert(!isEliminated(v));
+    assert(value(v) == l_Undef);
 
     // Split the occurrences into positive and negative:
-    vec<Clause*>  pos, neg;
+    //
+    const vec<CRef>& cls = occurs.lookup(v);
+    vec<CRef>        pos, neg;
     for (int i = 0; i < cls.size(); i++)
-        (find(*cls[i], Lit(v)) ? pos : neg).push(cls[i]);
+        (find(ca[cls[i]], mkLit(v)) ? pos : neg).push(cls[i]);
+
+    // Check wether the increase in number of clauses stays within the allowed ('grow'). Moreover, no
+    // clause must exceed the limit on the maximal clause size (if it is set):
+    //
+    int cnt         = 0;
+    int clause_size = 0;
 
-    // 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)
+            if (merge(ca[pos[i]], ca[neg[j]], v, clause_size) && 
+                (++cnt > cls.size() + grow || (clause_lim != -1 && clause_size > clause_lim)))
                 return true;
 
     // Delete and store old clauses:
+    eliminated[v] = true;
     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]); }
+    eliminated_vars++;
+
+    if (pos.size() > neg.size()){
+        for (int i = 0; i < neg.size(); i++)
+            mkElimClause(elimclauses, v, ca[neg[i]]);
+        mkElimClause(elimclauses, mkLit(v));
+    }else{
+        for (int i = 0; i < pos.size(); i++)
+            mkElimClause(elimclauses, v, ca[pos[i]]);
+        mkElimClause(elimclauses, ~mkLit(v));
+    }
+
+    for (int i = 0; i < cls.size(); i++)
+        removeClause(cls[i]); 
 
     // Produce clauses in cross product:
-    int top = clauses.size();
-    vec<Lit> resolvent;
+    vec<Lit>& resolvent = add_tmp;
     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, CLAUSE_CONFLICT))
+            if (merge(ca[pos[i]], ca[neg[j]], v, resolvent) && !addClause_(resolvent, CLAUSE_CONFLICT))
                 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); }
+    // Free occurs list for this variable:
+    occurs[v].clear(true);
+    
+    // Free watchers lists for this variable, if possible:
+    if (watches[ mkLit(v)].size() == 0) watches[ mkLit(v)].clear(true);
+    if (watches[~mkLit(v)].size() == 0) watches[~mkLit(v)].clear(true);
 
     return backwardSubsumptionCheck();
 }
 
 
-void SimpSolver::remember(Var v)
+bool SimpSolver::substitute(Var v, Lit x)
 {
-    assert(decisionLevel() == 0);
-    assert(isEliminated(v));
+    assert(!frozen[v]);
+    assert(!isEliminated(v));
+    assert(value(v) == l_Undef);
 
-    vec<Lit> clause;
+    if (!ok) return false;
 
-    // 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.
+    eliminated[v] = true;
+    setDecisionVar(v, false);
+    const vec<CRef>& cls = occurs.lookup(v);
+    
+    vec<Lit>& subst_clause = add_tmp;
+    for (int i = 0; i < cls.size(); i++){
+        Clause& c = ca[cls[i]];
 
-    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, CLAUSE_PROBLEM));
-        free(&c);
+        subst_clause.clear();
+        for (int j = 0; j < c.size(); j++){
+            Lit p = c[j];
+            subst_clause.push(var(p) == v ? x ^ sign(p) : p);
+        }
+
+        removeClause(cls[i]);
+
+        if (!addClause_(subst_clause, CLAUSE_PROBLEM))
+            return ok = false;
     }
 
-    elimtable[v].eliminated.clear();
+    return true;
 }
 
 
 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));
+    int i, j;
+    Lit x;
 
-    for (int i = 0; i < vs.size(); i++){
-        Var v = vs[i];
-        Lit l = lit_Undef;
+    for (i = elimclauses.size()-1; i > 0; i -= j){
+        for (j = elimclauses[i--]; j > 1; j--, i--)
+            if (modelValue(toLit(elimclauses[i])) != l_False)
+                goto next;
 
-        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;
+        x = toLit(elimclauses[i]);
+        model[var(x)] = lbool(!sign(x));
+    next:;
     }
 }
 
 
 bool SimpSolver::eliminate(bool turn_off_elim)
 {
-    if (!ok || !use_simplification)
-        return ok;
+    if (!simplify())
+        return false;
+    else if (!use_simplification)
+        return true;
 
     // 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;
+    //
+    while (n_touched > 0 || bwdsub_assigns < trail.size() || elim_heap.size() > 0){
 
-        //fprintf(stderr, "elimination phase:\n (%d)", elim_heap.size());
+        gatherTouchedClauses();
+        // printf("  ## (time = %6.2f s) BWD-SUB: queue = %d, trail = %d\n", cpuTime(), subsumption_queue.size(), trail.size() - bwdsub_assigns);
+        if ((subsumption_queue.size() > 0 || bwdsub_assigns < trail.size()) && 
+            !backwardSubsumptionCheck(true)){
+            ok = false; goto cleanup; }
+
+        // Empty elim_heap and return immediately on user-interrupt:
+        if (asynch_interrupt){
+            assert(bwdsub_assigns == trail.size());
+            assert(subsumption_queue.size() == 0);
+            assert(n_touched == 0);
+            elim_heap.clear();
+            goto cleanup; }
+
+        // printf("  ## (time = %6.2f s) ELIM: vars = %d\n", cpuTime(), elim_heap.size());
         for (int cnt = 0; !elim_heap.empty(); cnt++){
             Var elim = elim_heap.removeMin();
+            
+            if (asynch_interrupt) break;
 
-            if (verbosity >= 2 && cnt % 100 == 0)
-                reportf("elimination left: %10d\r", elim_heap.size());
+            if (isEliminated(elim) || value(elim) != l_Undef) continue;
 
-            if (!frozen[elim] && !eliminateVar(elim))
-                return false;
+            if (verbosity >= 2 && cnt % 100 == 0)
+                printf("elimination left: %10d\r", elim_heap.size());
+
+            if (use_asymm){
+                // Temporarily freeze variable. Otherwise, it would immediately end up on the queue again:
+                bool was_frozen = frozen[elim];
+                frozen[elim] = true;
+                if (!asymmVar(elim)){
+                    ok = false; goto cleanup; }
+                frozen[elim] = was_frozen; }
+
+            // At this point, the variable may have been set by assymetric branching, so check it
+            // again. Also, don't eliminate frozen variables:
+            if (use_elim && value(elim) == l_Undef && !frozen[elim] && !eliminateVar(elim)){
+                ok = false; goto cleanup; }
+
+            checkGarbage(simp_garbage_frac);
         }
 
         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
+ cleanup:
 
     // 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);
+        touched  .clear(true);
+        occurs   .clear(true);
+        n_occ    .clear(true);
         elim_heap.clear(true);
-        remove_satisfied = true;
+        subsumption_queue.clear(true);
+
+        use_simplification    = false;
+        remove_satisfied      = true;
+        ca.extra_clause_field = false;
+
+        // Force full cleanup (this is safe and desirable since it only happens once):
+        rebuildOrderHeap();
+        garbageCollect();
+    }else{
+        // Cheaper cleanup:
+        cleanUpClauses(); // TODO: can we make 'cleanUpClauses()' not be linear in the problem size somehow?
+        checkGarbage();
     }
 
+    if (verbosity >= 1 && elimclauses.size() > 0)
+        printf("|  Eliminated clauses:     %10.2f Mb                                      |\n", 
+               double(elimclauses.size() * sizeof(uint32_t)) / (1024*1024));
 
-    return true;
+    return ok;
 }
 
 
 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; }
-
+    occurs.cleanAll();
+    int i,j;
     for (i = j = 0; i < clauses.size(); i++)
-        if (clauses[i]->mark() == 1)
-            free(clauses[i]);
-        else
+        if (ca[clauses[i]].mark() == 0)
             clauses[j++] = clauses[i];
     clauses.shrink(i - j);
 }
 
 
 //=================================================================================================
-// Convert to DIMACS:
+// Garbage Collection methods:
 
 
-void SimpSolver::toDimacs(FILE* f, Clause& c)
+void SimpSolver::relocAll(ClauseAllocator& to)
 {
-    if (satisfied(c)) return;
+    if (!use_simplification) return;
+
+    // All occurs lists:
+    //
+    for (int i = 0; i < nVars(); i++){
+        vec<CRef>& cs = occurs[i];
+        for (int j = 0; j < cs.size(); j++)
+            ca.reloc(cs[j], to);
+    }
 
-    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");
+    // Subsumption queue:
+    //
+    for (int i = 0; i < subsumption_queue.size(); i++)
+        ca.reloc(subsumption_queue[i], to);
+
+    // Temporary clause:
+    //
+    ca.reloc(bwdsub_tmpunit, to);
 }
 
 
-void SimpSolver::toDimacs(const char* file)
+void SimpSolver::garbageCollect()
 {
-    assert(decisionLevel() == 0);
-    FILE* f = fopen(file, "wr");
-    if (f != NULL){
+    // Initialize the next region to a size corresponding to the estimated utilization degree. This
+    // is not precise but should avoid some unnecessary reallocations for the new region:
+    ClauseAllocator to(ca.size() - ca.wasted()); 
 
-        // 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);
+    cleanUpClauses();
+    to.extra_clause_field = ca.extra_clause_field; // NOTE: this is important to keep (or lose) the extra fields.
+    relocAll(to);
+    Solver::relocAll(to);
+    if (verbosity >= 2)
+        printf("|  Garbage collection:   %12d bytes => %12d bytes             |\n", 
+               ca.size()*ClauseAllocator::Unit_Size, to.size()*ClauseAllocator::Unit_Size);
+    to.moveTo(ca);
 }
-
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
diff --git a/src/prop/minisat/simp/SimpSolver.h b/src/prop/minisat/simp/SimpSolver.h
index 3da574f6c..977da46e5 100644
--- a/src/prop/minisat/simp/SimpSolver.h
+++ b/src/prop/minisat/simp/SimpSolver.h
@@ -1,5 +1,6 @@
 /************************************************************************************[SimpSolver.h]
-MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2006,      Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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,
@@ -17,158 +18,187 @@ DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 **************************************************************************************************/
 
-#include "cvc4_private.h"
+#ifndef Minisat_SimpSolver_h
+#define Minisat_SimpSolver_h
 
-#ifndef __CVC4__PROP__MINISAT__SIMP_SOLVER_H
-#define __CVC4__PROP__MINISAT__SIMP_SOLVER_H
+#include "cvc4_private.h"
 
-#include <cstdio>
-#include <cassert>
+#include "mtl/Queue.h"
+#include "core/Solver.h"
 
-#include "../mtl/Queue.h"
-#include "../core/Solver.h"
 
 namespace CVC4 {
 namespace prop {
+  class SatSolver;
+}
+}
 
-class SatSolver;
+namespace Minisat {
 
-namespace minisat {
+//=================================================================================================
 
 class SimpSolver : public Solver {
  public:
     // Constructor/Destructor:
     //
-    SimpSolver(SatSolver* proxy, context::Context* context);
+    SimpSolver(CVC4::prop::SatSolver* proxy, CVC4::context::Context* context);
     CVC4_PUBLIC ~SimpSolver();
 
     // Problem specification:
     //
     Var     newVar    (bool polarity = true, bool dvar = true, bool theoryAtom = false);
-    bool    addClause (vec<Lit>& ps, ClauseType type);
+    bool    addClause (const vec<Lit>& ps, ClauseType type);
+    bool    addEmptyClause(ClauseType type);                  // Add the empty clause to the solver.
+    bool    addClause (Lit p, ClauseType type);               // Add a unit clause to the solver.
+    bool    addClause (Lit p, Lit q, ClauseType type);        // Add a binary clause to the solver.
+    bool    addClause (Lit p, Lit q, Lit r, ClauseType type); // Add a ternary clause to the solver.
+    bool    addClause_(      vec<Lit>& ps, ClauseType type);
+    bool    substitute(Var v, Lit x);  // Replace all occurences of v with x (may cause a contradiction).
 
     // Variable mode:
     // 
     void    setFrozen (Var v, bool b); // If a variable is frozen it will not be eliminated.
+    bool    isEliminated(Var v) const;
 
     // 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. 
+    bool    solve       (const vec<Lit>& assumps, bool do_simp = true, bool turn_off_simp = false);
+    lbool   solveLimited(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    solve       (Lit p       ,        bool do_simp = true, bool turn_off_simp = false);       
+    bool    solve       (Lit p, Lit q,        bool do_simp = true, bool turn_off_simp = false);
+    bool    solve       (Lit p, Lit q, Lit r, bool do_simp = true, bool turn_off_simp = false);
+    bool    eliminate   (bool turn_off_elim = false);  // Perform variable elimination based simplification. 
+
+    // Memory managment:
+    //
+    virtual void garbageCollect();
+
 
     // Generate a (possibly simplified) DIMACS file:
     //
+#if 0
+    void    toDimacs  (const char* file, const vec<Lit>& assumps);
     void    toDimacs  (const char* file);
+    void    toDimacs  (const char* file, Lit p);
+    void    toDimacs  (const char* file, Lit p, Lit q);
+    void    toDimacs  (const char* file, Lit p, Lit q, Lit r);
+#endif
 
     // 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 :)
+    int     grow;              // Allow a variable elimination step to grow by a number of clauses (default to zero).
+    int     clause_lim;        // Variables are not eliminated if it produces a resolvent with a length above this limit.
+                               // -1 means no limit.
+    int     subsumption_lim;   // Do not check if subsumption against a clause larger than this. -1 means no limit.
+    double  simp_garbage_frac; // A different limit for when to issue a GC during simplification (Also see 'garbage_frac').
+
+    bool    use_asymm;         // Shrink clauses by asymmetric branching.
+    bool    use_rcheck;        // Check if a clause is already implied. Prett costly, and subsumes subsumptions :)
+    bool    use_elim;          // Perform variable elimination.
 
     // Statistics:
     //
     int     merges;
     int     asymm_lits;
-    int     remembered_clauses;
+    int     eliminated_vars;
 
-// protected:
-  public:
+ protected:
 
     // 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); } };
-
+        explicit ElimLt(const vec<int>& no) : n_occ(no) {}
+
+        // TODO: are 64-bit operations here noticably bad on 32-bit platforms? Could use a saturating
+        // 32-bit implementation instead then, but this will have to do for now.
+        uint64_t cost  (Var x)        const { return (uint64_t)n_occ[toInt(mkLit(x))] * (uint64_t)n_occ[toInt(~mkLit(x))]; }
+        bool operator()(Var x, Var y) const { return cost(x) < cost(y); }
+        
+        // TODO: investigate this order alternative more.
+        // bool operator()(Var x, Var y) const { 
+        //     int c_x = cost(x);
+        //     int c_y = cost(y);
+        //     return c_x < c_y || c_x == c_y && x < y; }
+    };
+
+    struct ClauseDeleted {
+        const ClauseAllocator& ca;
+        explicit ClauseDeleted(const ClauseAllocator& _ca) : ca(_ca) {}
+        bool operator()(const CRef& cr) const { return ca[cr].mark() == 1; } };
 
     // Solver state:
     //
     int                 elimorder;
     bool                use_simplification;
-    vec<ElimData>       elimtable;
+    vec<uint32_t>       elimclauses;
     vec<char>           touched;
-    vec<vec<Clause*> >  occurs;
+    OccLists<Var, vec<CRef>, ClauseDeleted>
+                        occurs;
     vec<int>            n_occ;
     Heap<ElimLt>        elim_heap;
-    Queue<Clause*>      subsumption_queue;
+    Queue<CRef>         subsumption_queue;
     vec<char>           frozen;
+    vec<char>           eliminated;
     int                 bwdsub_assigns;
+    int                 n_touched;
 
     // Temporaries:
     //
-    Clause*             bwdsub_tmpunit;
+    CRef                bwdsub_tmpunit;
 
     // Main internal methods:
     //
-    bool          asymm                    (Var v, Clause& c);
+    lbool         solve_                   (bool do_simp = true, bool turn_off_simp = false);
+    bool          asymm                    (Var v, CRef cr);
     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          merge                    (const Clause& _ps, const Clause& _qs, Var v, int& size);
     bool          backwardSubsumptionCheck (bool verbose = false);
-    bool          eliminateVar             (Var v, bool fail = false);
-    void          remember                 (Var v);
+    bool          eliminateVar             (Var v);
     void          extendModel              ();
-    void          verifyModel              ();
 
-    void          removeClause             (Clause& c);
-    bool          strengthenClause         (Clause& c, Lit l);
+    void          removeClause             (CRef cr);
+    bool          strengthenClause         (CRef cr, Lit l);
     void          cleanUpClauses           ();
     bool          implied                  (const vec<Lit>& c);
-    void          toDimacs                 (FILE* f, Clause& c);
-    bool          isEliminated             (Var v) const;
-
+    void          relocAll                 (ClauseAllocator& to);
 };
 
 
 //=================================================================================================
 // Implementation of inline methods:
 
+
+inline bool SimpSolver::isEliminated (Var v) const { return eliminated[v]; }
 inline void SimpSolver::updateElimHeap(Var v) {
-    if (elimtable[v].order == 0)
+    assert(use_simplification);
+    // if (!frozen[v] && !isEliminated(v) && value(v) == l_Undef)
+    if (elim_heap.inHeap(v) || (!frozen[v] && !isEliminated(v) && value(v) == l_Undef))
         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::addClause    (const vec<Lit>& ps, ClauseType type)    { ps.copyTo(add_tmp); return addClause_(add_tmp, type); }
+inline bool SimpSolver::addEmptyClause(ClauseType type)                       { add_tmp.clear(); return addClause_(add_tmp, type); }
+inline bool SimpSolver::addClause    (Lit p, ClauseType type)                 { add_tmp.clear(); add_tmp.push(p); return addClause_(add_tmp, type); }
+inline bool SimpSolver::addClause    (Lit p, Lit q, ClauseType type)          { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); return addClause_(add_tmp, type); }
+inline bool SimpSolver::addClause    (Lit p, Lit q, Lit r, ClauseType type)   { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); add_tmp.push(r); return addClause_(add_tmp, type); }
+inline void SimpSolver::setFrozen    (Var v, bool b) { frozen[v] = (char)b; if (use_simplification && !b) { updateElimHeap(v); } }
 
-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); }
+inline bool SimpSolver::solve        (                     bool do_simp, bool turn_off_simp)  { budgetOff(); assumptions.clear(); return solve_(do_simp, turn_off_simp) == l_True; }
+inline bool SimpSolver::solve        (Lit p       ,        bool do_simp, bool turn_off_simp)  { budgetOff(); assumptions.clear(); assumptions.push(p); return solve_(do_simp, turn_off_simp) == l_True; }
+inline bool SimpSolver::solve        (Lit p, Lit q,        bool do_simp, bool turn_off_simp)  { budgetOff(); assumptions.clear(); assumptions.push(p); assumptions.push(q); return solve_(do_simp, turn_off_simp) == l_True; }
+inline bool SimpSolver::solve        (Lit p, Lit q, Lit r, bool do_simp, bool turn_off_simp)  { budgetOff(); assumptions.clear(); assumptions.push(p); assumptions.push(q); assumptions.push(r); return solve_(do_simp, turn_off_simp) == l_True; }
+inline bool SimpSolver::solve        (const vec<Lit>& assumps, bool do_simp, bool turn_off_simp){ 
+    budgetOff(); assumps.copyTo(assumptions); return solve_(do_simp, turn_off_simp) == l_True; }
 
-}/* CVC4::prop::minisat namespace */
-}/* CVC4::prop namespace */
-}/* CVC4 namespace */
+inline lbool SimpSolver::solveLimited (const vec<Lit>& assumps, bool do_simp, bool turn_off_simp){ 
+    assumps.copyTo(assumptions); return solve_(do_simp, turn_off_simp); }
 
 //=================================================================================================
-#endif /* __CVC4__PROP__MINISAT__SIMP_SOLVER_H */
+}
+
+#endif
diff --git a/src/prop/minisat/utils/Makefile b/src/prop/minisat/utils/Makefile
new file mode 100644
index 000000000..204cea541
--- /dev/null
+++ b/src/prop/minisat/utils/Makefile
@@ -0,0 +1,4 @@
+EXEC      = system_test
+DEPDIR    = mtl
+
+include $(MROOT)/mtl/template.mk
diff --git a/src/prop/minisat/utils/Options.cc b/src/prop/minisat/utils/Options.cc
new file mode 100644
index 000000000..ec5a6e930
--- /dev/null
+++ b/src/prop/minisat/utils/Options.cc
@@ -0,0 +1,91 @@
+/**************************************************************************************[Options.cc]
+Copyright (c) 2008-2010, 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 "mtl/Sort.h"
+#include "utils/Options.h"
+#include "utils/ParseUtils.h"
+
+using namespace Minisat;
+
+void Minisat::parseOptions(int& argc, char** argv, bool strict)
+{
+    int i, j;
+    for (i = j = 1; i < argc; i++){
+        const char* str = argv[i];
+        if (match(str, "--") && match(str, Option::getHelpPrefixString()) && match(str, "help")){
+            if (*str == '\0')
+                printUsageAndExit(argc, argv);
+            else if (match(str, "-verb"))
+                printUsageAndExit(argc, argv, true);
+        } else {
+            bool parsed_ok = false;
+        
+            for (int k = 0; !parsed_ok && k < Option::getOptionList().size(); k++){
+                parsed_ok = Option::getOptionList()[k]->parse(argv[i]);
+
+                // fprintf(stderr, "checking %d: %s against flag <%s> (%s)\n", i, argv[i], Option::getOptionList()[k]->name, parsed_ok ? "ok" : "skip");
+            }
+
+            if (!parsed_ok)
+                if (strict && match(argv[i], "-"))
+                    fprintf(stderr, "ERROR! Unknown flag \"%s\". Use '--%shelp' for help.\n", argv[i], Option::getHelpPrefixString()), exit(1);
+                else
+                    argv[j++] = argv[i];
+        }
+    }
+
+    argc -= (i - j);
+}
+
+
+void Minisat::setUsageHelp      (const char* str){ Option::getUsageString() = str; }
+void Minisat::setHelpPrefixStr  (const char* str){ Option::getHelpPrefixString() = str; }
+void Minisat::printUsageAndExit (int argc, char** argv, bool verbose)
+{
+    const char* usage = Option::getUsageString();
+    if (usage != NULL)
+        fprintf(stderr, usage, argv[0]);
+
+    sort(Option::getOptionList(), Option::OptionLt());
+
+    const char* prev_cat  = NULL;
+    const char* prev_type = NULL;
+
+    for (int i = 0; i < Option::getOptionList().size(); i++){
+        const char* cat  = Option::getOptionList()[i]->category;
+        const char* type = Option::getOptionList()[i]->type_name;
+
+        if (cat != prev_cat)
+            fprintf(stderr, "\n%s OPTIONS:\n\n", cat);
+        else if (type != prev_type)
+            fprintf(stderr, "\n");
+
+        Option::getOptionList()[i]->help(verbose);
+
+        prev_cat  = Option::getOptionList()[i]->category;
+        prev_type = Option::getOptionList()[i]->type_name;
+    }
+
+    fprintf(stderr, "\nHELP OPTIONS:\n\n");
+    fprintf(stderr, "  --%shelp        Print help message.\n", Option::getHelpPrefixString());
+    fprintf(stderr, "  --%shelp-verb   Print verbose help message.\n", Option::getHelpPrefixString());
+    fprintf(stderr, "\n");
+    exit(0);
+}
+
diff --git a/src/prop/minisat/utils/Options.h b/src/prop/minisat/utils/Options.h
new file mode 100644
index 000000000..9c1f40699
--- /dev/null
+++ b/src/prop/minisat/utils/Options.h
@@ -0,0 +1,386 @@
+/***************************************************************************************[Options.h]
+Copyright (c) 2008-2010, 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 Minisat_Options_h
+#define Minisat_Options_h
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <string.h>
+
+#include "mtl/IntTypes.h"
+#include "mtl/Vec.h"
+#include "utils/ParseUtils.h"
+
+namespace Minisat {
+
+//==================================================================================================
+// Top-level option parse/help functions:
+
+
+extern void parseOptions     (int& argc, char** argv, bool strict = false);
+extern void printUsageAndExit(int  argc, char** argv, bool verbose = false);
+extern void setUsageHelp     (const char* str);
+extern void setHelpPrefixStr (const char* str);
+
+
+//==================================================================================================
+// Options is an abstract class that gives the interface for all types options:
+
+
+class Option
+{
+ protected:
+    const char* name;
+    const char* description;
+    const char* category;
+    const char* type_name;
+
+    static vec<Option*>& getOptionList () { static vec<Option*> options; return options; }
+    static const char*&  getUsageString() { static const char* usage_str; return usage_str; }
+    static const char*&  getHelpPrefixString() { static const char* help_prefix_str = ""; return help_prefix_str; }
+
+    struct OptionLt {
+        bool operator()(const Option* x, const Option* y) {
+            int test1 = strcmp(x->category, y->category);
+            return test1 < 0 || test1 == 0 && strcmp(x->type_name, y->type_name) < 0;
+        }
+    };
+
+    Option(const char* name_, 
+           const char* desc_,
+           const char* cate_,
+           const char* type_) : 
+      name       (name_)
+    , description(desc_)
+    , category   (cate_)
+    , type_name  (type_)
+    { 
+        getOptionList().push(this); 
+    }
+
+ public:
+    virtual ~Option() {}
+
+    virtual bool parse             (const char* str)      = 0;
+    virtual void help              (bool verbose = false) = 0;
+
+    friend  void parseOptions      (int& argc, char** argv, bool strict);
+    friend  void printUsageAndExit (int  argc, char** argv, bool verbose);
+    friend  void setUsageHelp      (const char* str);
+    friend  void setHelpPrefixStr  (const char* str);
+};
+
+
+//==================================================================================================
+// Range classes with specialization for floating types:
+
+
+struct IntRange {
+    int begin;
+    int end;
+    IntRange(int b, int e) : begin(b), end(e) {}
+};
+
+struct Int64Range {
+    int64_t begin;
+    int64_t end;
+    Int64Range(int64_t b, int64_t e) : begin(b), end(e) {}
+};
+
+struct DoubleRange {
+    double begin;
+    double end;
+    bool  begin_inclusive;
+    bool  end_inclusive;
+    DoubleRange(double b, bool binc, double e, bool einc) : begin(b), end(e), begin_inclusive(binc), end_inclusive(einc) {}
+};
+
+
+//==================================================================================================
+// Double options:
+
+
+class DoubleOption : public Option
+{
+ protected:
+    DoubleRange range;
+    double      value;
+
+ public:
+    DoubleOption(const char* c, const char* n, const char* d, double def = double(), DoubleRange r = DoubleRange(-HUGE_VAL, false, HUGE_VAL, false))
+        : Option(n, d, c, "<double>"), range(r), value(def) {
+        // FIXME: set LC_NUMERIC to "C" to make sure that strtof/strtod parses decimal point correctly.
+    }
+
+    operator      double   (void) const { return value; }
+    operator      double&  (void)       { return value; }
+    DoubleOption& operator=(double x)   { value = x; return *this; }
+
+    virtual bool parse(const char* str){
+        const char* span = str; 
+
+        if (!match(span, "-") || !match(span, name) || !match(span, "="))
+            return false;
+
+        char*  end;
+        double tmp = strtod(span, &end);
+
+        if (end == NULL) 
+            return false;
+        else if (tmp >= range.end && (!range.end_inclusive || tmp != range.end)){
+            fprintf(stderr, "ERROR! value <%s> is too large for option \"%s\".\n", span, name);
+            exit(1);
+        }else if (tmp <= range.begin && (!range.begin_inclusive || tmp != range.begin)){
+            fprintf(stderr, "ERROR! value <%s> is too small for option \"%s\".\n", span, name);
+            exit(1); }
+
+        value = tmp;
+        // fprintf(stderr, "READ VALUE: %g\n", value);
+
+        return true;
+    }
+
+    virtual void help (bool verbose = false){
+        fprintf(stderr, "  -%-12s = %-8s %c%4.2g .. %4.2g%c (default: %g)\n", 
+                name, type_name, 
+                range.begin_inclusive ? '[' : '(', 
+                range.begin,
+                range.end,
+                range.end_inclusive ? ']' : ')', 
+                value);
+        if (verbose){
+            fprintf(stderr, "\n        %s\n", description);
+            fprintf(stderr, "\n");
+        }
+    }
+};
+
+
+//==================================================================================================
+// Int options:
+
+
+class IntOption : public Option
+{
+ protected:
+    IntRange range;
+    int32_t  value;
+
+ public:
+    IntOption(const char* c, const char* n, const char* d, int32_t def = int32_t(), IntRange r = IntRange(INT32_MIN, INT32_MAX))
+        : Option(n, d, c, "<int32>"), range(r), value(def) {}
+ 
+    operator   int32_t   (void) const { return value; }
+    operator   int32_t&  (void)       { return value; }
+    IntOption& operator= (int32_t x)  { value = x; return *this; }
+
+    virtual bool parse(const char* str){
+        const char* span = str; 
+
+        if (!match(span, "-") || !match(span, name) || !match(span, "="))
+            return false;
+
+        char*   end;
+        int32_t tmp = strtol(span, &end, 10);
+
+        if (end == NULL) 
+            return false;
+        else if (tmp > range.end){
+            fprintf(stderr, "ERROR! value <%s> is too large for option \"%s\".\n", span, name);
+            exit(1);
+        }else if (tmp < range.begin){
+            fprintf(stderr, "ERROR! value <%s> is too small for option \"%s\".\n", span, name);
+            exit(1); }
+
+        value = tmp;
+
+        return true;
+    }
+
+    virtual void help (bool verbose = false){
+        fprintf(stderr, "  -%-12s = %-8s [", name, type_name);
+        if (range.begin == INT32_MIN)
+            fprintf(stderr, "imin");
+        else
+            fprintf(stderr, "%4d", range.begin);
+
+        fprintf(stderr, " .. ");
+        if (range.end == INT32_MAX)
+            fprintf(stderr, "imax");
+        else
+            fprintf(stderr, "%4d", range.end);
+
+        fprintf(stderr, "] (default: %d)\n", value);
+        if (verbose){
+            fprintf(stderr, "\n        %s\n", description);
+            fprintf(stderr, "\n");
+        }
+    }
+};
+
+
+// Leave this out for visual C++ until Microsoft implements C99 and gets support for strtoll.
+#ifndef _MSC_VER
+
+class Int64Option : public Option
+{
+ protected:
+    Int64Range range;
+    int64_t  value;
+
+ public:
+    Int64Option(const char* c, const char* n, const char* d, int64_t def = int64_t(), Int64Range r = Int64Range(INT64_MIN, INT64_MAX))
+        : Option(n, d, c, "<int64>"), range(r), value(def) {}
+ 
+    operator     int64_t   (void) const { return value; }
+    operator     int64_t&  (void)       { return value; }
+    Int64Option& operator= (int64_t x)  { value = x; return *this; }
+
+    virtual bool parse(const char* str){
+        const char* span = str; 
+
+        if (!match(span, "-") || !match(span, name) || !match(span, "="))
+            return false;
+
+        char*   end;
+        int64_t tmp = strtoll(span, &end, 10);
+
+        if (end == NULL) 
+            return false;
+        else if (tmp > range.end){
+            fprintf(stderr, "ERROR! value <%s> is too large for option \"%s\".\n", span, name);
+            exit(1);
+        }else if (tmp < range.begin){
+            fprintf(stderr, "ERROR! value <%s> is too small for option \"%s\".\n", span, name);
+            exit(1); }
+
+        value = tmp;
+
+        return true;
+    }
+
+    virtual void help (bool verbose = false){
+        fprintf(stderr, "  -%-12s = %-8s [", name, type_name);
+        if (range.begin == INT64_MIN)
+            fprintf(stderr, "imin");
+        else
+            fprintf(stderr, "%4"PRIi64, range.begin);
+
+        fprintf(stderr, " .. ");
+        if (range.end == INT64_MAX)
+            fprintf(stderr, "imax");
+        else
+            fprintf(stderr, "%4"PRIi64, range.end);
+
+        fprintf(stderr, "] (default: %"PRIi64")\n", value);
+        if (verbose){
+            fprintf(stderr, "\n        %s\n", description);
+            fprintf(stderr, "\n");
+        }
+    }
+};
+#endif
+
+//==================================================================================================
+// String option:
+
+
+class StringOption : public Option
+{
+    const char* value;
+ public:
+    StringOption(const char* c, const char* n, const char* d, const char* def = NULL) 
+        : Option(n, d, c, "<string>"), value(def) {}
+
+    operator      const char*  (void) const     { return value; }
+    operator      const char*& (void)           { return value; }
+    StringOption& operator=    (const char* x)  { value = x; return *this; }
+
+    virtual bool parse(const char* str){
+        const char* span = str; 
+
+        if (!match(span, "-") || !match(span, name) || !match(span, "="))
+            return false;
+
+        value = span;
+        return true;
+    }
+
+    virtual void help (bool verbose = false){
+        fprintf(stderr, "  -%-10s = %8s\n", name, type_name);
+        if (verbose){
+            fprintf(stderr, "\n        %s\n", description);
+            fprintf(stderr, "\n");
+        }
+    }    
+};
+
+
+//==================================================================================================
+// Bool option:
+
+
+class BoolOption : public Option
+{
+    bool value;
+
+ public:
+    BoolOption(const char* c, const char* n, const char* d, bool v) 
+        : Option(n, d, c, "<bool>"), value(v) {}
+
+    operator    bool     (void) const { return value; }
+    operator    bool&    (void)       { return value; }
+    BoolOption& operator=(bool b)     { value = b; return *this; }
+
+    virtual bool parse(const char* str){
+        const char* span = str; 
+        
+        if (match(span, "-")){
+            bool b = !match(span, "no-");
+
+            if (strcmp(span, name) == 0){
+                value = b;
+                return true; }
+        }
+
+        return false;
+    }
+
+    virtual void help (bool verbose = false){
+
+        fprintf(stderr, "  -%s, -no-%s", name, name);
+
+        for (uint32_t i = 0; i < 32 - strlen(name)*2; i++)
+            fprintf(stderr, " ");
+
+        fprintf(stderr, " ");
+        fprintf(stderr, "(default: %s)\n", value ? "on" : "off");
+        if (verbose){
+            fprintf(stderr, "\n        %s\n", description);
+            fprintf(stderr, "\n");
+        }
+    }
+};
+
+//=================================================================================================
+}
+
+#endif
diff --git a/src/prop/minisat/utils/ParseUtils.h b/src/prop/minisat/utils/ParseUtils.h
new file mode 100644
index 000000000..d3071649d
--- /dev/null
+++ b/src/prop/minisat/utils/ParseUtils.h
@@ -0,0 +1,122 @@
+/************************************************************************************[ParseUtils.h]
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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 Minisat_ParseUtils_h
+#define Minisat_ParseUtils_h
+
+#include <stdlib.h>
+#include <stdio.h>
+
+#include <zlib.h>
+
+namespace Minisat {
+
+//-------------------------------------------------------------------------------------------------
+// A simple buffered character stream class:
+
+static const int buffer_size = 1048576;
+
+
+class StreamBuffer {
+    gzFile        in;
+    unsigned char buf[buffer_size];
+    int           pos;
+    int           size;
+
+    void assureLookahead() {
+        if (pos >= size) {
+            pos  = 0;
+            size = gzread(in, buf, sizeof(buf)); } }
+
+public:
+    explicit StreamBuffer(gzFile i) : in(i), pos(0), size(0) { assureLookahead(); }
+
+    int  operator *  () const { return (pos >= size) ? EOF : buf[pos]; }
+    void operator ++ ()       { pos++; assureLookahead(); }
+    int  position    () const { return pos; }
+};
+
+
+//-------------------------------------------------------------------------------------------------
+// End-of-file detection functions for StreamBuffer and char*:
+
+
+static inline bool isEof(StreamBuffer& in) { return *in == EOF;  }
+static inline bool isEof(const char*   in) { return *in == '\0'; }
+
+//-------------------------------------------------------------------------------------------------
+// Generic parse functions parametrized over the input-stream type.
+
+
+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 (isEof(in)) 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') fprintf(stderr, "PARSE ERROR! Unexpected char: %c\n", *in), exit(3);
+    while (*in >= '0' && *in <= '9')
+        val = val*10 + (*in - '0'),
+        ++in;
+    return neg ? -val : val; }
+
+
+// String matching: in case of a match the input iterator will be advanced the corresponding
+// number of characters.
+template<class B>
+static bool match(B& in, const char* str) {
+    int i;
+    for (i = 0; str[i] != '\0'; i++)
+        if (in[i] != str[i])
+            return false;
+
+    in += i;
+
+    return true; 
+}
+
+// String matching: consumes characters eagerly, but does not require random access iterator.
+template<class B>
+static bool eagerMatch(B& in, const char* str) {
+    for (; *str != '\0'; ++str, ++in)
+        if (*str != *in)
+            return false;
+    return true; }
+
+
+//=================================================================================================
+}
+
+#endif
diff --git a/src/prop/minisat/utils/System.cc b/src/prop/minisat/utils/System.cc
new file mode 100644
index 000000000..a7cf53f55
--- /dev/null
+++ b/src/prop/minisat/utils/System.cc
@@ -0,0 +1,95 @@
+/***************************************************************************************[System.cc]
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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 "utils/System.h"
+
+#if defined(__linux__)
+
+#include <stdio.h>
+#include <stdlib.h>
+
+using namespace Minisat;
+
+// TODO: split the memory reading functions into two: one for reading high-watermark of RSS, and
+// one for reading the current virtual memory size.
+
+static inline int memReadStat(int field)
+{
+    char  name[256];
+    pid_t pid = getpid();
+    int   value;
+
+    sprintf(name, "/proc/%d/statm", pid);
+    FILE* in = fopen(name, "rb");
+    if (in == NULL) return 0;
+
+    for (; field >= 0; field--)
+        if (fscanf(in, "%d", &value) != 1)
+            printf("ERROR! Failed to parse memory statistics from \"/proc\".\n"), exit(1);
+    fclose(in);
+    return value;
+}
+
+
+static inline int memReadPeak(void)
+{
+    char  name[256];
+    pid_t pid = getpid();
+
+    sprintf(name, "/proc/%d/status", pid);
+    FILE* in = fopen(name, "rb");
+    if (in == NULL) return 0;
+
+    // Find the correct line, beginning with "VmPeak:":
+    int peak_kb = 0;
+    while (!feof(in) && fscanf(in, "VmPeak: %d kB", &peak_kb) != 1)
+        while (!feof(in) && fgetc(in) != '\n')
+            ;
+    fclose(in);
+
+    return peak_kb;
+}
+
+double Minisat::memUsed() { return (double)memReadStat(0) * (double)getpagesize() / (1024*1024); }
+double Minisat::memUsedPeak() { 
+    double peak = memReadPeak() / 1024;
+    return peak == 0 ? memUsed() : peak; }
+
+#elif defined(__FreeBSD__)
+
+double Minisat::memUsed(void) {
+    struct rusage ru;
+    getrusage(RUSAGE_SELF, &ru);
+    return (double)ru.ru_maxrss / 1024; }
+double MiniSat::memUsedPeak(void) { return memUsed(); }
+
+
+#elif defined(__APPLE__)
+#include <malloc/malloc.h>
+
+double Minisat::memUsed(void) {
+    malloc_statistics_t t;
+    malloc_zone_statistics(NULL, &t);
+    return (double)t.max_size_in_use / (1024*1024); }
+
+#else
+double Minisat::memUsed() { 
+    return 0; }
+#endif
diff --git a/src/prop/minisat/utils/System.h b/src/prop/minisat/utils/System.h
new file mode 100644
index 000000000..17581927a
--- /dev/null
+++ b/src/prop/minisat/utils/System.h
@@ -0,0 +1,60 @@
+/****************************************************************************************[System.h]
+Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
+Copyright (c) 2007-2010, 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 Minisat_System_h
+#define Minisat_System_h
+
+#if defined(__linux__)
+#include <fpu_control.h>
+#endif
+
+#include "mtl/IntTypes.h"
+
+//-------------------------------------------------------------------------------------------------
+
+namespace Minisat {
+
+static inline double cpuTime(void); // CPU-time in seconds.
+extern double memUsed();            // Memory in mega bytes (returns 0 for unsupported architectures).
+extern double memUsedPeak();        // Peak-memory in mega bytes (returns 0 for unsupported architectures).
+
+}
+
+//-------------------------------------------------------------------------------------------------
+// Implementation of inline functions:
+
+#if defined(_MSC_VER) || defined(__MINGW32__)
+#include <time.h>
+
+static inline double Minisat::cpuTime(void) { return (double)clock() / CLOCKS_PER_SEC; }
+
+#else
+#include <sys/time.h>
+#include <sys/resource.h>
+#include <unistd.h>
+
+static inline double Minisat::cpuTime(void) {
+    struct rusage ru;
+    getrusage(RUSAGE_SELF, &ru);
+    return (double)ru.ru_utime.tv_sec + (double)ru.ru_utime.tv_usec / 1000000; }
+
+#endif
+
+#endif