| /****************************************************************************************[Solver.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_Solver_h |
| #define Minisat_Solver_h |
| |
| #include "Vec.h" |
| #include "Heap.h" |
| #include "Alg.h" |
| #include "IntMap.h" |
| #include "Options.h" |
| #include "SolverTypes.h" |
| |
| |
| namespace Minisat { |
| |
| //================================================================================================= |
| // Solver -- the main class: |
| |
| class Solver { |
| public: |
| |
| // Constructor/Destructor: |
| // |
| Solver(); |
| virtual ~Solver(); |
| |
| // Problem specification: |
| // |
| Var newVar (lbool upol = l_Undef, bool dvar = true); // Add a new variable with parameters specifying variable mode. |
| void releaseVar(Lit l); // Make literal true and promise to never refer to variable again. |
| |
| bool addClause (const vec<Lit>& ps); // Add a clause to the solver. |
| bool addEmptyClause(); // Add the empty clause, making the solver contradictory. |
| bool addClause (Lit p); // Add a unit clause to the solver. |
| bool addClause (Lit p, Lit q); // Add a binary clause to the solver. |
| bool addClause (Lit p, Lit q, Lit r); // Add a ternary clause to the solver. |
| bool addClause (Lit p, Lit q, Lit r, Lit s); // Add a quaternary clause to the solver. |
| bool addClause_( vec<Lit>& ps); // 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 |
| |
| bool implies (const vec<Lit>& assumps, vec<Lit>& out); |
| |
| // Iterate over clauses and top-level assignments: |
| ClauseIterator clausesBegin() const; |
| ClauseIterator clausesEnd() const; |
| TrailIterator trailBegin() const; |
| TrailIterator trailEnd () const; |
| |
| 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, lbool 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. |
| |
| // Read state: |
| // |
| 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; |
| void printStats () const; // Print some current statistics to standard output. |
| |
| // Resource constraints: |
| // |
| 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) |
| // |
| vec<lbool> model; // If problem is satisfiable, this vector contains the model (if any). |
| LSet conflict; // If problem is unsatisfiable (possibly under assumptions), |
| // this vector represent the final conflict clause expressed in the assumptions. |
| |
| // Mode of operation: |
| // |
| 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 min_learnts_lim; // Minimum number to set the learnts limit to. |
| |
| 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) |
| |
| int learntsize_adjust_start_confl; |
| double learntsize_adjust_inc; |
| |
| // Statistics: (read-only member variable) |
| // |
| uint64_t solves, starts, decisions, rnd_decisions, propagations, conflicts; |
| uint64_t dec_vars, num_clauses, num_learnts, 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 IntMap<Var, double>& activity; |
| bool operator () (Var x, Var y) const { return activity[x] > activity[y]; } |
| VarOrderLt(const IntMap<Var, double>& act) : activity(act) { } |
| }; |
| |
| struct ShrinkStackElem { |
| uint32_t i; |
| Lit l; |
| ShrinkStackElem(uint32_t _i, Lit _l) : i(_i), l(_l){} |
| }; |
| |
| // Solver state: |
| // |
| vec<CRef> clauses; // List of problem clauses. |
| vec<CRef> learnts; // List of learnt clauses. |
| 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<Lit> assumptions; // Current set of assumptions provided to solve by the user. |
| |
| VMap<double> activity; // A heuristic measurement of the activity of a variable. |
| VMap<lbool> assigns; // The current assignments. |
| VMap<char> polarity; // The preferred polarity of each variable. |
| VMap<lbool> user_pol; // The users preferred polarity of each variable. |
| VMap<char> decision; // Declares if a variable is eligible for selection in the decision heuristic. |
| VMap<VarData> vardata; // Stores reason and level for each variable. |
| OccLists<Lit, vec<Watcher>, WatcherDeleted, MkIndexLit> |
| watches; // 'watches[lit]' is a list of constraints watching 'lit' (will go there if literal becomes true). |
| |
| Heap<Var,VarOrderLt>order_heap; // A priority queue of variables ordered with respect to the variable activity. |
| |
| bool ok; // If FALSE, the constraints are already unsatisfiable. No part of the solver state may be used! |
| double cla_inc; // Amount to bump next clause with. |
| double var_inc; // Amount to bump next variable with. |
| int qhead; // Head of queue (as index into the trail -- no more explicit propagation queue in MiniSat). |
| 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()'. |
| double progress_estimate;// Set by 'search()'. |
| bool remove_satisfied; // Indicates whether possibly inefficient linear scan for satisfied clauses should be performed in 'simplify'. |
| Var next_var; // Next variable to be created. |
| ClauseAllocator ca; |
| |
| vec<Var> released_vars; |
| vec<Var> free_vars; |
| |
| // 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. |
| // |
| VMap<char> seen; |
| vec<ShrinkStackElem>analyze_stack; |
| vec<Lit> analyze_toclear; |
| vec<Lit> add_tmp; |
| |
| double max_learnts; |
| double learntsize_adjust_confl; |
| int learntsize_adjust_cnt; |
| |
| // Resource constraints: |
| // |
| 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 (); // Return the next decision variable. |
| void newDecisionLevel (); // Begins a new decision level. |
| 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 (); // Perform unit propagation. Returns possibly conflicting clause. |
| void cancelUntil (int level); // Backtrack until a certain level. |
| void analyze (CRef confl, vec<Lit>& out_learnt, int& out_btlevel); // (bt = backtrack) |
| void analyzeFinal (Lit p, LSet& out_conflict); // COULD THIS BE IMPLEMENTED BY THE ORDINARIY "analyze" BY SOME REASONABLE GENERALIZATION? |
| bool litRedundant (Lit p); // (helper method for 'analyze()') |
| 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<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 (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 isRemoved (CRef cr) const; // Test if a clause has been removed. |
| 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. |
| |
| // Misc: |
| // |
| 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 ... |
| bool withinBudget () const; |
| void relocAll (ClauseAllocator& to); |
| |
| // Static helpers: |
| // |
| |
| // Returns a random float 0 <= x < 1. Seed must never be 0. |
| static inline double drand(double& seed) { |
| seed *= 1389796; |
| int q = (int)(seed / 2147483647); |
| seed -= (double)q * 2147483647; |
| return seed / 2147483647; } |
| |
| // Returns a random integer 0 <= x < size. Seed must never be 0. |
| static inline int irand(double& seed, int size) { |
| return (int)(drand(seed) * size); } |
| }; |
| |
| |
| //================================================================================================= |
| // Implementation of inline methods: |
| |
| inline CRef Solver::reason(Var x) const { return vardata[x].reason; } |
| inline int Solver::level (Var x) const { return vardata[x].level; } |
| |
| inline void Solver::insertVarOrder(Var x) { |
| if (!order_heap.inHeap(x) && decision[x]) order_heap.insert(x); } |
| |
| 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; |
| var_inc *= 1e-100; } |
| |
| // Update order_heap with respect to new activity: |
| if (order_heap.inHeap(v)) |
| order_heap.decrease(v); } |
| |
| 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++) |
| ca[learnts[i]].activity() *= 1e-20; |
| cla_inc *= 1e-20; } } |
| |
| 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) { ps.copyTo(add_tmp); return addClause_(add_tmp); } |
| inline bool Solver::addEmptyClause () { add_tmp.clear(); return addClause_(add_tmp); } |
| inline bool Solver::addClause (Lit p) { add_tmp.clear(); add_tmp.push(p); return addClause_(add_tmp); } |
| inline bool Solver::addClause (Lit p, Lit q) { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); return addClause_(add_tmp); } |
| inline bool Solver::addClause (Lit p, Lit q, Lit r) { add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); add_tmp.push(r); return addClause_(add_tmp); } |
| inline bool Solver::addClause (Lit p, Lit q, Lit r, Lit s){ add_tmp.clear(); add_tmp.push(p); add_tmp.push(q); add_tmp.push(r); add_tmp.push(s); return addClause_(add_tmp); } |
| |
| inline bool Solver::isRemoved (CRef cr) const { return ca[cr].mark() == 1; } |
| 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()); } |
| |
| 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 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 num_clauses; } |
| inline int Solver::nLearnts () const { return num_learnts; } |
| inline int Solver::nVars () const { return next_var; } |
| // TODO: nFreeVars() is not quite correct, try to calculate right instead of adapting it like below: |
| inline int Solver::nFreeVars () const { return (int)dec_vars - (trail_lim.size() == 0 ? trail.size() : trail_lim[0]); } |
| inline void Solver::setPolarity (Var v, lbool b){ user_pol[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 ClauseIterator Solver::clausesBegin() const { return ClauseIterator(ca, &clauses[0]); } |
| inline ClauseIterator Solver::clausesEnd () const { return ClauseIterator(ca, &clauses[clauses.size()]); } |
| inline TrailIterator Solver::trailBegin () const { return TrailIterator(&trail[0]); } |
| inline TrailIterator Solver::trailEnd () const { |
| return TrailIterator(&trail[decisionLevel() == 0 ? trail.size() : trail_lim[0]]); } |
| |
| 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: |
| |
| |
| //================================================================================================= |
| } |
| |
| #endif |
