blob: 619b9e7e5e84c7899b4d4d2b53843f7054cb2ac1 [file] [edit]
#include "internal.hpp"
#include <algorithm>
#include <functional>
namespace CaDiCaL {
// It turns out that even in the competition there are formulas which are
// easy to satisfy by either setting all variables to the same truth value
// or by assigning variables to the same value and propagating it. In the
// latter situation this can be done either in the order of all variables
// (forward or backward) or in the order of all clauses. These lucky
// assignments can be tested initially in a kind of pre-solving step.
// We extended the search to do discrepency search to strengthen the
// original idea. We try both direction of a literal if it leads to a
// conflict. On top of that, as long as we are on level 1, we actually learn
// the unit, similarly to how probing is done.
// This function factors out clean up code common among the 'lucky'
// functions for backtracking and resetting a potential conflict. One could
// also use exceptions here, but there are two different reasons for
// aborting early. The first kind of aborting is due to asynchronous
// termination and the second kind due to a situation in which it is clear
// that a particular function will not be successful (for instance a
// completely negative clause is found). The latter situation returns zero
// and will just abort the particular lucky function, while the former will
// abort all (by returning '-1').
int Internal::unlucky (int res) {
if (level > 0)
backtrack_without_updating_phases ();
assert (propagated == trail.size ());
if (conflict)
conflict = nullptr;
return res;
}
inline void Internal::lucky_search_assign (int lit, Clause *reason) {
assert (searching_lucky_phases);
if (level)
MODE_REQUIRE (SEARCH);
assert (!flags (lit).unused ());
const int idx = vidx (lit);
assert (reason != external_reason);
assert (!val (idx));
assert (!flags (idx).eliminated () || reason == decision_reason ||
reason == external_reason);
Var &v = var (idx);
int lit_level;
assert (!lrat || level || reason == external_reason ||
reason == decision_reason || !lrat_chain.empty ());
// The following cases are explained in the two comments above before
// 'decision_reason' and 'assignment_level'.
//
// External decision reason means that the propagation was done by
// an external propagation and the reason clause not known (yet).
// In that case it is assumed that the propagation is NOT out of
// order (i.e. lit_level = level), because due to lazy explanation,
// we can not calculate the real assignment level.
// The function assignment_level () will also assign the current level
// to literals with external reason.
if (!reason)
lit_level = 0; // unit
else if (reason == decision_reason)
lit_level = level, reason = nullptr;
else
lit_level = level;
if (!lit_level)
reason = nullptr;
v.level = lit_level;
v.trail = get_trail_size ();
v.reason = reason;
assert ((int) num_assigned < max_var);
assert (num_assigned == trail.size ());
num_assigned++;
if (!lit_level)
learn_unit_clause (lit); // increases 'stats.fixed'
assert (lit_level);
const signed char tmp = sign (lit);
set_val (idx, tmp);
assert (val (lit) > 0); // Just a bit paranoid but useful.
assert (val (-lit) < 0); // Ditto.
trail.push_back (lit);
#ifdef LOGGING
if (!lit_level)
LOG ("root-level unit assign %d @ 0", lit);
else
LOG (reason, "search assign %d @ %d", lit, lit_level);
#endif
if (watching ()) {
const Watches &ws = watches (-lit);
if (!ws.empty ()) {
const Watch &w = ws[0];
__builtin_prefetch (&w, 0, 1);
}
}
lrat_chain.clear ();
}
void Internal::lucky_assume_decision (int lit) {
MODE_REQUIRE (SEARCH);
assert (propagated == trail.size ());
new_trail_level (lit);
LOG ("lucky decide %d", lit);
lucky_search_assign (lit, decision_reason);
}
int Internal::trivially_false_satisfiable (int64_t &ticks) {
if (terminated_asynchronously ())
return -1;
LOG ("checking that all clauses contain a negative literal");
assert (!level);
++stats.lucky_constant_zero;
int res = lucky_decide_assumptions ();
if (res)
return res;
ticks += 1 + cache_lines (clauses.size (), sizeof (clauses.begin ()));
for (const auto &c : clauses) {
++ticks;
if (terminated_asynchronously (100))
return unlucky (-1);
if (c->garbage)
continue;
if (c->redundant)
continue;
bool satisfied = false, found_negative_literal = false;
for (const auto &lit : *c) {
const signed char tmp = val (lit);
if (tmp > 0) {
satisfied = true;
break;
}
if (tmp < 0)
continue;
if (lit > 0)
continue;
found_negative_literal = true;
break;
}
if (satisfied || found_negative_literal)
continue;
LOG (c, "found purely positively");
return unlucky (0);
}
VERBOSE (1, "all clauses contain a negative literal");
for (auto idx : vars) {
if (terminated_asynchronously (10))
return unlucky (-1);
if (val (idx))
continue;
if (flags (idx).unused ())
continue;
lucky_assume_decision (-idx);
if (propagate ())
continue;
if (flags (idx).unused ())
continue;
assert (level > 0);
LOG ("propagation failed including redundant clauses");
return unlucky (0);
}
stats.lucky_constant_zero++;
return 10;
}
int Internal::trivially_true_satisfiable (int64_t &ticks) {
if (terminated_asynchronously ())
return -1;
LOG ("checking that all clauses contain a positive literal");
assert (!level);
++stats.lucky_constant_one;
int res = lucky_decide_assumptions ();
if (res)
return res;
ticks += 1 + cache_lines (clauses.size (), sizeof (clauses.begin ()));
for (const auto &c : clauses) {
++ticks;
if (terminated_asynchronously (100))
return unlucky (-1);
if (c->garbage)
continue;
if (c->redundant)
continue;
bool satisfied = false, found_positive_literal = false;
for (const auto &lit : *c) {
const signed char tmp = val (lit);
if (tmp > 0) {
satisfied = true;
break;
}
if (tmp < 0)
continue;
if (lit < 0)
continue;
found_positive_literal = true;
break;
}
if (satisfied || found_positive_literal)
continue;
LOG (c, "found purely negatively");
return unlucky (0);
}
VERBOSE (1, "all clauses contain a positive literal");
for (auto idx : vars) {
if (terminated_asynchronously (10))
return unlucky (-1);
if (val (idx))
continue;
if (flags (idx).unused ())
continue;
lucky_assume_decision (idx);
if (propagate ())
continue;
assert (level > 0);
LOG ("propagation failed including redundant clauses");
return unlucky (0);
}
return 10;
}
/*------------------------------------------------------------------------*/
inline bool Internal::lucky_propagate_discrepency (int dec) {
lucky_assume_decision (dec);
bool no_conflict = propagate ();
if (no_conflict)
return false;
if (level > 1) {
conflict = nullptr;
backtrack_without_updating_phases (level - 1);
lucky_assume_decision (-dec);
no_conflict = propagate ();
if (no_conflict)
return false;
return true;
} else {
analyze ();
assert (!level);
no_conflict = propagate ();
if (!no_conflict) {
analyze ();
LOG ("lucky inconsistency backward assigning to true");
return true;
}
}
return false;
}
template <class Iterator>
int Internal::lucky_fixed_test (Iterator begin, Iterator end,
signed char pol, std::string str) {
if (terminated_asynchronously ())
return -1;
LOG ("checking %s variable index %s assignment", str.c_str (),
pol == 1 ? "true" : "false");
#ifdef QUIET
(void) str;
#endif
assert (!unsat);
assert (!level);
if (pol == 1)
stats.lucky_forward_one++;
else
stats.lucky_forward_zero++;
int res = lucky_decide_assumptions ();
if (res)
return res;
for (auto it = begin; it != end; ++it) {
const int idx = *it;
if (flags (idx).unused ())
continue;
START:
int lit = idx * pol;
if (terminated_asynchronously (10))
return unlucky (-1);
if (val (idx))
continue;
if (lucky_propagate_discrepency (lit)) {
if (unsat)
return 20;
else
return unlucky (0);
} else
goto START;
}
VERBOSE (1, "%s assuming variables %s satisfies formula", str.c_str (),
pol == 1 ? "true" : "false");
assert (satisfied ());
return 10;
}
int Internal::forward_false_satisfiable () {
return lucky_fixed_test (vars.begin (), vars.end (), -1, "forward");
}
int Internal::forward_true_satisfiable () {
return lucky_fixed_test (vars.begin (), vars.end (), 1, "forward");
}
/*------------------------------------------------------------------------*/
int Internal::backward_false_satisfiable () {
if (terminated_asynchronously ())
return -1;
LOG ("checking decreasing variable index false assignment");
assert (!unsat);
assert (!level);
stats.lucky_backward_zero++;
int res = lucky_decide_assumptions ();
if (res)
return res;
for (auto it = vars.rbegin (); it != vars.rend (); ++it) {
int idx = *it;
if (flags (idx).unused ())
continue;
START:
if (terminated_asynchronously (10))
return unlucky (-1);
if (val (idx))
continue;
if (lucky_propagate_discrepency (-idx)) {
if (unsat)
return 20;
else
return unlucky (0);
} else
goto START;
}
VERBOSE (1, "backward assuming variables false satisfies formula");
assert (satisfied ());
return 10;
}
int Internal::backward_true_satisfiable () {
if (terminated_asynchronously ())
return -1;
LOG ("checking decreasing variable index true assignment");
assert (!unsat);
assert (!level);
stats.lucky_backward_one++;
int res = lucky_decide_assumptions ();
if (res)
return res;
for (auto it = vars.rbegin (); it != vars.rend (); ++it) {
int idx = *it;
if (flags (idx).unused ())
continue;
START:
if (terminated_asynchronously (10))
return unlucky (-1);
if (val (idx))
continue;
if (lucky_propagate_discrepency (idx)) {
if (unsat)
return 20;
else
return unlucky (0);
} else
goto START;
}
VERBOSE (1, "backward assuming variables true satisfies formula");
assert (satisfied ());
return 10;
}
/*------------------------------------------------------------------------*/
int Internal::lucky_decide_assumptions () {
assert (!level);
assert (!constraint.size ());
int res = 0;
while ((size_t) level < assumptions.size ()) {
res = decide ();
if (res == 20) {
marked_failed = false;
return 20;
}
if (!propagate ()) {
break;
}
}
if (conflict) {
// analyze and learn from the conflict.
LOG (conflict, "setting assumption lead to conflict");
analyze_wrapper ();
backtrack_without_updating_phases (0);
assert (!conflict);
int res = 0;
while (!res) {
assert ((size_t) level <= assumptions.size ());
if (unsat)
res = 20;
else if (!propagate ()) {
analyze_wrapper ();
} else {
res = decide_wrapper ();
}
}
assert (res == 20);
return 20;
}
return 0;
}
int Internal::random_lucky_assignment (signed char pol) {
if (!opts.luckyrandom)
return 0;
LOG ("checking random variable order %s assignment",
pol == 1 ? "true" : "false");
assert (!unsat);
assert (!level);
stats.lucky_random++;
// Shuffle the variables
std::vector<int> shuffle;
for (int idx = max_var; idx; idx--) {
if (val (idx))
continue;
if (flags (idx).unused ())
continue;
shuffle.push_back (idx);
}
Random random (opts.seed); // global seed
random += stats.lucky_random; // different every time
const int highest_var = (int) shuffle.size ();
for (int i = 0; i <= highest_var - 2; i++) {
const int j = random.pick_int (i, highest_var - 1);
swap (shuffle[i], shuffle[j]);
}
int res = lucky_decide_assumptions ();
if (res)
return res;
for (int idx : shuffle) {
START:
if (flags (idx).unused ())
continue;
if (val (idx))
continue;
if (terminated_asynchronously (10))
return unlucky (-1);
int lit = idx * pol;
if (lucky_propagate_discrepency (lit)) {
if (unsat)
return 20;
else
return unlucky (0);
} else {
goto START;
}
}
VERBOSE (1, "random %s assignment satisfies formula",
pol == 1 ? "true" : "false");
assert (satisfied ());
return 10;
}
/*------------------------------------------------------------------------*/
int Internal::lucky_phases (bool update_limit) {
assert (!level);
MODE_REQUIRE (SEARCH);
if (!opts.lucky)
return 0;
if (!opts.luckyassumptions && !assumptions.empty ())
return 0;
if (terminated_asynchronously ())
return 0;
// TODO: Some of the lucky assignments can also be found if there are
// constraint.
// External propagator assumes a CDCL loop, so lucky is not tried here.
if (!constraint.empty () || external_prop)
return 0;
if (unsat)
return 20;
if (!propagate ()) {
learn_empty_clause ();
return 20;
}
PROFILE_SCOPE2 (search, lucky);
LOG ("starting lucky");
assert (!searching_lucky_phases);
searching_lucky_phases = true;
stats.lucky_tried++;
int64_t units = 0;
int res = 0, rounds = 0;
#ifndef QUIET
const int64_t active_initially = stats.vars_active;
#endif
constexpr int schedule_size = 6;
std::array<std::function<int ()>, schedule_size> schedule;
int schedule_pos = 0;
// The idea of the code is to:
//
// 1. check for the trival solutions. The trivial solution are
// tested only once, because the forward/backward true/false would
// solve the same model too (which higher cost).
//
// 2. a. use the order provided by the user (by default, the decisions are
// largest first)
//
// b. then use first the phases proviveded by the user (by default '1')
if (opts.phase) {
if (!opts.varprioritizefirst) {
schedule[schedule_pos++] = [this] () {
return backward_true_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return backward_false_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return forward_true_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return forward_false_satisfiable ();
};
} else {
schedule[schedule_pos++] = [this] () {
return forward_true_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return forward_false_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return backward_true_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return backward_false_satisfiable ();
};
}
schedule[schedule_pos++] = [this] () {
return random_lucky_assignment (1);
};
schedule[schedule_pos++] = [this] () {
return random_lucky_assignment (-1);
};
} else {
if (!opts.varprioritizefirst) {
schedule[schedule_pos++] = [this] () {
return backward_false_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return backward_true_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return forward_false_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return forward_true_satisfiable ();
};
} else {
schedule[schedule_pos++] = [this] () {
return forward_false_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return forward_true_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return backward_false_satisfiable ();
};
schedule[schedule_pos++] = [this] () {
return backward_true_satisfiable ();
};
}
schedule[schedule_pos++] = [this] () {
return random_lucky_assignment (-1);
};
schedule[schedule_pos++] = [this] () {
return random_lucky_assignment (1);
};
}
assert (schedule_pos == schedule_size);
if (res < 0)
assert (termination_forced), res = 0;
if (res == 10)
stats.lucky++;
report ('l', !res);
assert (searching_lucky_phases);
assert (res || !level);
if (res != 20) {
if (!propagate ()) {
LOG ("propagating units after elimination results in empty clause");
learn_empty_clause ();
}
}
int64_t ticks = 0;
res = trivially_false_satisfiable (ticks);
if (!res)
res = trivially_true_satisfiable (ticks);
stats.ticks += ticks;
const int64_t old_active = stats.vars_active;
// abort the search if visit each clause too often
const int64_t limit =
stats.ticks + stats.clauses_now_irr * opts.luckylimitpercls;
if (!res)
do {
const int64_t active_before = stats.vars_active;
for (auto &luck : schedule) {
res = luck ();
if (res)
break;
if (stats.ticks >= limit)
break;
}
if (res < 0)
assert (termination_forced), res = 0;
if (res == 10)
stats.lucky++;
assert (searching_lucky_phases);
assert (res || !level);
assert (res || propagated == trail.size ());
units = active_before - stats.vars_active;
stats.lucky_units += units;
if (!res && units)
VERBOSE (3, "lucky-%" PRId64 " in round %d found %" PRId64 " units",
stats.lucky_tried, rounds, units);
} while (units && !res && ++rounds < opts.luckyrounds);
report ('l', !res && (old_active == stats.vars_active));
searching_lucky_phases = false;
PHASE ("lucky", stats.lucky_tried,
" produced %" PRId64 " units after %d rounds",
active_initially - stats.vars_active, rounds);
// Here we should reset lim.terminate.check since in a lucky run this
// may be set to up to 1000 (for terminateint=10).
// This then may lead to a high latency for external termination.
lim.terminate.check = opts.terminateint;
if (update_limit && !res && (old_active == stats.vars_active)) {
lim.lucky = stats.conflicts + opts.luckymininterval;
VERBOSE (
3, "lucky-%" PRId64 " scheduled to be next after conflict %" PRId64,
stats.lucky_tried, lim.lucky);
}
return res;
}
} // namespace CaDiCaL