blob: b973ac65b660294fca21559ee54acb828455b534 [file] [edit]
#include "internal.hpp"
namespace CaDiCaL {
/*------------------------------------------------------------------------*/
// Failed literal probing uses its own propagation and assignment
// functions. It further provides on-the-fly generation of hyper binary
// resolvents but only probes on roots of the binary implication graph. The
// search for failed literals is limited, but untried roots are kept until
// the next time 'probe' is called. Left over probes from the last attempt
// and new probes are tried until the limit is hit or all are tried.
/*------------------------------------------------------------------------*/
bool Internal::inprobing () {
if (!opts.inprobing)
return false;
if (!preprocessing && !opts.inprocessing)
return false;
if (preprocessing)
assert (lim.preprocessing);
if (opts.reduce && stats.inprobingphases &&
last.inprobe.reductions == stats.reductions)
return false;
return lim.inprobe <= stats.conflicts;
}
/*------------------------------------------------------------------------*/
inline int Internal::get_parent_reason_literal (int lit) {
const int idx = vidx (lit);
int res = parents[idx];
if (lit < 0)
res = -res;
return res;
}
inline void Internal::set_parent_reason_literal (int lit, int reason) {
const int idx = vidx (lit);
if (lit < 0)
reason = -reason;
parents[idx] = reason;
}
/*-----------------------------------------------------------------------*/
// for opts.probehbr=false we need to do a lot of extra work to remember the
// correct lrat_chains... This solution is also memory intensive I think
// all corresponding functions are guarded to only work with the right
// options so they can be called without checking for options
//
// call locally after failed_literal or backtracking
//
void Internal::clean_probehbr_lrat () {
if (!lrat || opts.probehbr)
return;
for (auto &field : probehbr_chains) {
for (auto &chain : field) {
chain.clear ();
}
}
}
// call globally before a probe round (or a lookahead round)
//
void Internal::init_probehbr_lrat () {
if (!lrat || opts.probehbr)
return;
const size_t size = 2 * (1 + (size_t) max_var);
probehbr_chains.resize (size);
for (size_t i = 0; i < size; i++) {
probehbr_chains[i].resize (size);
// commented because not needed... should be empty already
/*
for (size_t j = 0; j < size; j++) {
vector<int64_t> empty;
probehbr_chains[i][j] = empty;
}
*/
}
}
// sets lrat_chain to the stored chain in probehbr_chains.
// this leads to conflict with unit reason uip
//
void Internal::get_probehbr_lrat (int lit, int uip) {
if (!lrat || opts.probehbr)
return;
assert (lit);
assert (lrat_chain.empty ());
assert (val (uip) < 0);
lrat_chain = probehbr_chains[vlit (lit)][vlit (uip)];
int64_t id = unit_id (-uip);
lrat_chain.push_back (id);
}
// sets the corresponding probehbr_chain to what is currently stored in
// lrat_chain. also clears lrat_chain.
//
void Internal::set_probehbr_lrat (int lit, int uip) {
if (!lrat || opts.probehbr)
return;
assert (lit);
assert (lrat_chain.size ());
assert (probehbr_chains[vlit (lit)][vlit (uip)].empty ());
probehbr_chains[vlit (lit)][vlit (uip)] = lrat_chain;
lrat_chain.clear ();
}
// compute lrat_chain for the part of the tree from lit to dom
// use mini_chain because it needs to be reversed
//
void Internal::probe_dominator_lrat (int dom, Clause *reason) {
if (!lrat || !dom)
return;
LOG (reason, "probe dominator LRAT for %d from", dom);
for (const auto lit : *reason) {
if (val (lit) >= 0)
continue;
const auto other = -lit;
if (other == dom)
continue;
Flags &f = flags (other);
if (f.seen)
continue;
f.seen = true;
analyzed.push_back (other);
Var u = var (other);
if (u.level) {
if (!u.reason) {
LOG ("this may be a problem %d", other);
continue;
}
probe_dominator_lrat (dom, u.reason);
continue;
}
int64_t id = unit_id (other);
lrat_chain.push_back (id);
}
lrat_chain.push_back (reason->id);
}
/*------------------------------------------------------------------------*/
// On-the-fly (dynamic) hyper binary resolution on decision level one can
// make use of the fact that the implication graph is actually a tree.
// Compute a dominator of two literals in the binary implication tree.
int Internal::probe_dominator (int a, int b) {
MODE_REQUIRE (PROBE);
int l = a, k = b;
Var *u = &var (l), *v = &var (k);
assert (val (l) > 0), assert (val (k) > 0);
assert (u->level == 1), assert (v->level == 1);
while (l != k) {
if (u->trail > v->trail)
swap (l, k), swap (u, v);
if (!get_parent_reason_literal (l))
return l;
int parent = get_parent_reason_literal (k);
assert (parent), assert (val (parent) > 0);
v = &var (k = parent);
assert (v->level == 1);
}
LOG ("dominator %d of %d and %d", l, a, b);
assert (val (l) > 0);
return l;
}
// The idea of dynamic on-the-fly hyper-binary resolution came up in the
// PrecoSAT solver, where it originally was used on all decision levels.
// It turned out, that most of the hyper-binary resolvents were generated
// during probing on decision level one anyhow. Thus this version is
// specialized to decision level one, where actually all long (non-binary)
// forcing clauses can be resolved to become binary. So if we find a clause
// which would force a new assignment at decision level one during probing
// we resolve it (the 'reason' argument) to obtain a hyper binary resolvent.
// It consists of the still unassigned literal (the new unit) and the
// negation of the unique closest dominator of the negation of all (false)
// literals in the clause (which has to exist on decision level one).
// There are two special cases which should be mentioned:
//
// (A) The reason is already a binary clause in a certain sense, since all
// its unwatched literals are root level fixed to false. In this
// situation it would be better to shrink the clause immediately instead
// of adding a new clause consisting only of the watched literals.
// However, this would happen during the next garbage collection anyhow.
//
// (B) The resolvent subsumes the original reason clause. This is
// equivalent to the property that the negated dominator is contained in
// the original reason. Again one could in principle shrink the clause.
//
// Note that (A) is actually subsumed by (B). The possible optimization to
// shrink the clause on-the-fly is difficult (need to update 'blit' and
// 'binary' of the other watch at least) and also not really that important.
// For (B) we simply add the new binary resolvent and mark the old subsumed
// clause as garbage instead. And since in the situation of (A) the
// shrinking will be performed at the next garbage collection anyhow, we
// do not change clauses in (A).
// The hyper binary resolvent clause is redundant unless it subsumes the
// original reason and that one is irredundant.
// If the option 'opts.probehbr' is 'false', we actually do not add the new
// hyper binary resolvent, but simply pretend we would have added it and
// still return the dominator as new reason / parent for the new unit.
// Finally note that adding clauses changes the watches of the propagated
// literal and thus we can not use standard iterators during probing but
// need to fall back to indices. One watch for the hyper binary resolvent
// clause is added at the end of the currently propagated watches, but its
// watch is a binary watch and will be skipped during propagating long
// clauses anyhow.
inline int Internal::hyper_binary_resolve (Clause *reason) {
MODE_REQUIRE (PROBE);
assert (level == 1);
assert (reason->size > 2);
const const_literal_iterator end = reason->end ();
const int *lits = reason->literals;
const_literal_iterator k;
#ifndef NDEBUG
// First literal unassigned, all others false.
assert (!val (lits[0]));
for (k = lits + 1; k != end; k++)
assert (val (*k) < 0);
assert (var (lits[1]).level == 1);
#endif
LOG (reason, "hyper binary resolving");
stats.hbrs++;
stats.hbr_sizes += reason->size;
const int lit = lits[1];
int dom = -lit, non_root_level_literals = 0;
for (k = lits + 2; k != end; k++) {
const int other = -*k;
assert (val (other) > 0);
if (!var (other).level)
continue;
dom = probe_dominator (dom, other);
non_root_level_literals++;
}
probe_reason = reason;
if (non_root_level_literals && opts.probehbr) { // !(A)
bool contained = false;
for (k = lits + 1; !contained && k != end; k++)
contained = (*k == -dom);
const bool red = !contained || reason->redundant;
if (red)
stats.hbr_redundant++;
LOG ("new %s hyper binary resolvent %d %d",
(red ? "redundant" : "irredundant"), -dom, lits[0]);
assert (clause.empty ());
clause.push_back (-dom);
clause.push_back (lits[0]);
probe_dominator_lrat (dom, reason);
if (lrat)
clear_analyzed_literals ();
Clause *c = new_hyper_binary_resolved_clause (red, 2);
probe_reason = c;
if (red)
c->hyper = true;
clause.clear ();
lrat_chain.clear ();
if (contained) {
stats.hbr_subsuming++;
LOG (reason, "subsumed original");
mark_garbage (reason);
}
} else if (non_root_level_literals && lrat) {
// still calculate LRAT and remember for later
assert (!opts.probehbr);
probe_dominator_lrat (dom, reason);
clear_analyzed_literals ();
set_probehbr_lrat (dom, lits[0]);
}
return dom;
}
/*------------------------------------------------------------------------*/
// The following functions 'probe_assign' and 'probe_propagate' are used for
// propagating during failed literal probing in simplification mode, as
// replacement of the generic propagation routine 'propagate' and
// 'search_assign'.
// The code is mostly copied from 'propagate.cpp' and specialized. We only
// comment on the differences. More explanations are in 'propagate.cpp'.
inline void Internal::probe_assign (int lit, int parent) {
MODE_REQUIRE (PROBE);
int idx = vidx (lit);
assert (!val (idx));
assert (!flags (idx).eliminated () || !parent);
assert (!parent || val (parent) > 0);
Var &v = var (idx);
v.level = level;
v.trail = get_trail_size ();
assert ((int) num_assigned < max_var);
num_assigned++;
v.reason = level ? probe_reason : 0;
probe_reason = nullptr;
set_parent_reason_literal (lit, parent);
if (!level)
learn_unit_clause (lit);
else
assert (level == 1);
const signed char tmp = sign (lit);
set_val (idx, tmp);
assert (val (lit) > 0);
assert (val (-lit) < 0);
trail.push_back (lit);
// Do not save the current phase during inprocessing but remember the
// number of units on the trail of the last time this literal was
// assigned. This allows us to avoid some redundant failed literal
// probing attempts. Search for 'propfixed' in 'probe.cpp' for details.
//
if (level)
propfixed (lit) = stats.vars_all_fixed;
if (parent)
LOG ("probe assign %d parent %d", lit, parent);
else if (level)
LOG ("probe assign %d probe", lit);
else
LOG ("probe assign %d negated failed literal UIP", lit);
}
void Internal::probe_assign_decision (int lit) {
MODE_REQUIRE (PROBE);
assert (!level);
assert (propagated == trail.size ());
level++;
control.push_back (Level (lit, get_trail_size ()));
probe_assign (lit, 0);
}
void Internal::probe_assign_unit (int lit) {
MODE_REQUIRE (PROBE);
assert (!level);
assert (active (lit));
probe_assign (lit, 0);
}
/*------------------------------------------------------------------------*/
// same as in propagate but inlined here
//
inline void Internal::probe_lrat_for_units (int lit) {
if (!lrat)
return;
if (level)
return; // not decision level 0
LOG ("building chain for units");
assert (lrat_chain.empty ());
assert (probe_reason);
for (auto &reason_lit : *probe_reason) {
if (lit == reason_lit)
continue;
assert (val (reason_lit));
if (!val (reason_lit))
continue;
const int signed_reason_lit = val (reason_lit) * reason_lit;
int64_t id = unit_id (signed_reason_lit);
lrat_chain.push_back (id);
}
lrat_chain.push_back (probe_reason->id);
}
/*------------------------------------------------------------------------*/
// This is essentially the same as 'propagate' except that we prioritize and
// always propagate binary clauses first (see our CPAIOR'13 paper on tree
// based look ahead), then immediately stop at a conflict and of course use
// 'probe_assign' instead of 'search_assign'. The binary propagation part
// is factored out too. If a new unit on decision level one is found we
// perform hyper binary resolution and thus actually build an implication
// tree instead of a DAG. Statistics counters are also different.
inline void Internal::probe_propagate2 () {
MODE_REQUIRE (PROBE);
int64_t &ticks = stats.ticks_probe;
while (propagated2 != trail.size ()) {
const int lit = -trail[propagated2++];
LOG ("probe propagating %d over binary clauses", -lit);
Watches &ws = watches (lit);
ticks += 1 + cache_lines (ws.size (), sizeof (const_watch_iterator *));
for (const auto &w : ws) {
if (!w.binary ())
continue;
const signed char b = val (w.blit);
if (b > 0)
continue;
ticks++;
if (b < 0)
conflict = w.clause; // but continue
else {
assert (lrat_chain.empty ());
assert (!probe_reason);
probe_reason = w.clause;
probe_lrat_for_units (w.blit);
probe_assign (w.blit, -lit);
lrat_chain.clear ();
}
}
}
}
bool Internal::probe_propagate () {
MODE_REQUIRE (PROBE);
assert (!unsat);
PROFILE_SCOPE (propagate);
const size_t before = propagated2 = propagated;
int64_t &ticks = stats.ticks_probe;
while (!conflict) {
if (propagated2 != trail.size ())
probe_propagate2 ();
else if (propagated != trail.size ()) {
const int lit = -trail[propagated++];
LOG ("probe propagating %d over large clauses", -lit);
Watches &ws = watches (lit);
ticks +=
1 + cache_lines (ws.size (), sizeof (const_watch_iterator *));
size_t i = 0, j = 0;
while (i != ws.size ()) {
const Watch w = ws[j++] = ws[i++];
if (w.binary ())
continue;
const signed char b = val (w.blit);
if (b > 0)
continue;
ticks++;
if (w.clause->garbage)
continue;
const literal_iterator lits = w.clause->begin ();
const int other = lits[0] ^ lits[1] ^ lit;
// lits[0] = other, lits[1] = lit;
const signed char u = val (other);
if (u > 0)
ws[j - 1].blit = other;
else {
const int size = w.clause->size;
const const_literal_iterator end = lits + size;
const literal_iterator middle = lits + w.clause->pos;
literal_iterator k = middle;
int r = 0;
signed char v = -1;
while (k != end && (v = val (r = *k)) < 0)
k++;
if (v < 0) {
k = lits + 2;
assert (w.clause->pos <= size);
while (k != middle && (v = val (r = *k)) < 0)
k++;
}
w.clause->pos = k - lits;
assert (lits + 2 <= k), assert (k <= w.clause->end ());
if (v > 0)
ws[j - 1].blit = r;
else if (!v) {
ticks++;
LOG (w.clause, "unwatch %d in", r);
*k = lit;
lits[0] = other;
lits[1] = r;
watch_literal (r, lit, w.clause);
j--;
} else if (!u) {
ticks++;
if (level == 1) {
lits[0] = other, lits[1] = lit;
assert (lrat_chain.empty ());
assert (!probe_reason);
int dom = hyper_binary_resolve (w.clause);
probe_assign (other, dom);
} else {
ticks++;
assert (lrat_chain.empty ());
assert (!probe_reason);
probe_reason = w.clause;
probe_lrat_for_units (other);
probe_assign_unit (other);
lrat_chain.clear ();
}
probe_propagate2 ();
} else
conflict = w.clause;
}
}
if (j != i) {
while (i != ws.size ())
ws[j++] = ws[i++];
ws.resize (j);
}
} else
break;
}
int64_t delta = (int64_t) propagated2 - before;
stats.propagations_probe += delta;
stats.propagations += delta;
if (conflict)
LOG (conflict, "conflict");
return !conflict;
}
/*------------------------------------------------------------------------*/
// This a specialized instance of 'analyze'.
void Internal::failed_literal (int failed) {
LOG ("analyzing failed literal probe %d", failed);
stats.failed_literals++;
stats.probe_failed_literals++;
assert (!unsat);
assert (conflict);
assert (level == 1);
assert (analyzed.empty ());
assert (lrat_chain.empty ());
PROFILE_SCOPE (analyze);
LOG (conflict, "analyzing failed literal conflict");
int uip = 0;
for (const auto &lit : *conflict) {
const int other = -lit;
if (!var (other).level) {
assert (val (other) > 0);
continue;
}
uip = uip ? probe_dominator (uip, other) : other;
}
probe_dominator_lrat (uip, conflict);
if (lrat)
clear_analyzed_literals ();
LOG ("found probing UIP %d", uip);
assert (uip);
vector<int> work;
int parent = uip;
while (parent != failed) {
const int next = get_parent_reason_literal (parent);
parent = next;
assert (parent);
work.push_back (parent);
}
backtrack ();
conflict = 0;
assert (!val (uip));
probe_assign_unit (-uip);
lrat_chain.clear ();
if (!probe_propagate ())
learn_empty_clause ();
size_t j = 0;
while (!unsat && j < work.size ()) {
// assert (!opts.probehbr); assertion fails ...
const int parent = work[j++];
const signed char tmp = val (parent);
if (tmp > 0) {
assert (!opts.probehbr); // ... assertion should hold here
get_probehbr_lrat (parent, uip);
LOG ("clashing failed parent %d", parent);
learn_empty_clause ();
} else if (tmp == 0) {
assert (!opts.probehbr); // ... and here
LOG ("found unassigned failed parent %d", parent);
get_probehbr_lrat (parent, uip); // this is computed during
probe_assign_unit (-parent); // propagation and can include
lrat_chain.clear (); // multiple chains where only one
if (!probe_propagate ())
learn_empty_clause (); // is needed!
}
uip = parent;
}
work.clear ();
erase_vector (work);
assert (unsat || val (failed) < 0);
}
/*------------------------------------------------------------------------*/
bool Internal::is_binary_clause (Clause *c, int &a, int &b) {
assert (!level);
if (c->garbage)
return false;
int first = 0, second = 0;
for (const auto &lit : *c) {
const signed char tmp = val (lit);
if (tmp > 0)
return false;
if (tmp < 0)
continue;
if (second)
return false;
if (first)
second = lit;
else
first = lit;
}
if (!second)
return false;
a = first, b = second;
return true;
}
// We probe on literals first, which occur more often negated and thus we
// sort the 'probes' stack in such a way that literals which occur negated
// less frequently come first. Probes are taken from the back of the stack.
struct probe_negated_noccs_rank {
Internal *internal;
probe_negated_noccs_rank (Internal *i) : internal (i) {}
typedef size_t Type;
Type operator() (int a) const { return internal->noccs (-a); }
};
// Fill the 'probes' schedule.
void Internal::generate_probes () {
assert (probes.empty ());
int64_t &ticks = stats.ticks_probe;
// First determine all the literals which occur in binary clauses. It is
// way faster to go over the clauses once, instead of walking the watch
// lists for each literal.
//
init_noccs ();
ticks += 1 + cache_lines (clauses.size (), sizeof (Clause *));
for (const auto &c : clauses) {
int a, b;
ticks++;
if (!is_binary_clause (c, a, b))
continue;
noccs (a)++;
noccs (b)++;
}
for (auto idx : vars) {
// Then focus on roots of the binary implication graph, which are
// literals occurring negatively in a binary clause, but not positively.
// If neither 'idx' nor '-idx' is a root it makes less sense to probe
// this variable.
// This argument requires that equivalent literal substitution through
// 'decompose' is performed, because otherwise there might be 'cyclic
// roots' which are not tried, i.e., -1 2 0, 1 -2 0, 1 2 3 0, 1 2 -3 0.
ticks += 2;
const bool have_pos_bin_occs = noccs (idx) > 0;
const bool have_neg_bin_occs = noccs (-idx) > 0;
if (have_pos_bin_occs == have_neg_bin_occs)
continue;
int probe = have_neg_bin_occs ? idx : -idx;
// See the discussion where 'propfixed' is used below.
//
if (propfixed (probe) >= stats.vars_all_fixed)
continue;
LOG ("scheduling probe %d negated occs %" PRIu64 "", probe,
noccs (-probe));
probes.push_back (probe);
}
rsort (probes.begin (), probes.end (), probe_negated_noccs_rank (this));
reset_noccs ();
shrink_vector (probes);
PHASE ("probe-round", stats.probingrounds,
"scheduled %zd literals %.0f%%", probes.size (),
percent (probes.size (), 2u * max_var));
}
// Follow the ideas in 'generate_probes' but flush non root probes and
// reorder remaining probes.
void Internal::flush_probes () {
assert (!probes.empty ());
int64_t &ticks = stats.ticks_probe;
init_noccs ();
ticks += 1 + cache_lines (clauses.size (), sizeof (Clause *));
for (const auto &c : clauses) {
int a, b;
ticks++;
if (!is_binary_clause (c, a, b))
continue;
noccs (a)++;
noccs (b)++;
}
const auto eop = probes.end ();
auto j = probes.begin ();
for (auto i = j; i != eop; i++) {
int lit = *i;
if (!active (lit))
continue;
ticks += 2;
const bool have_pos_bin_occs = noccs (lit) > 0;
const bool have_neg_bin_occs = noccs (-lit) > 0;
if (have_pos_bin_occs == have_neg_bin_occs)
continue;
if (have_pos_bin_occs)
lit = -lit;
assert (!noccs (lit)), assert (noccs (-lit) > 0);
if (propfixed (lit) >= stats.vars_all_fixed)
continue;
LOG ("keeping probe %d negated occs %" PRId64 "", lit, noccs (-lit));
*j++ = lit;
}
size_t remain = j - probes.begin ();
#ifndef QUIET
size_t flushed = probes.size () - remain;
#endif
probes.resize (remain);
rsort (probes.begin (), probes.end (), probe_negated_noccs_rank (this));
reset_noccs ();
shrink_vector (probes);
PHASE ("probe-round", stats.probingrounds,
"flushed %zd literals %.0f%% remaining %zd", flushed,
percent (flushed, remain + flushed), remain);
}
int Internal::next_probe () {
int generated = 0;
for (;;) {
if (probes.empty ()) {
if (generated++)
return 0;
generate_probes ();
}
while (!probes.empty ()) {
int probe = probes.back ();
probes.pop_back ();
// Eliminated or assigned.
//
if (!active (probe))
continue;
// There is now new unit since the last time we propagated this probe,
// thus we propagated it before without obtaining a conflict and
// nothing changed since then. Thus there is no need to propagate it
// again. This observation was independently made by Partik Simons
// et.al. in the context of implementing 'smodels' (see for instance
// Alg. 4 in his JAIR article from 2002) and it has also been
// contributed to the thesis work of Yacine Boufkhad.
//
if (propfixed (probe) >= stats.vars_all_fixed)
continue;
return probe;
}
}
}
bool Internal::probe () {
if (!opts.probe)
return false;
if (unsat)
return false;
if (terminated_asynchronously ())
return false;
SET_EFFORT_LIMIT (limit, probe, true);
MODE_SCOPE_SIMPLIFY (PROBE);
PROFILE_SCOPE_SIMPLIFY (probe);
stats.probingrounds++;
// Probing is limited in terms of non-probing propagations
// 'stats.propagations'. We allow a certain percentage 'opts.probeeffort'
// (say %5) of probing propagations in each probing with a lower bound of
// 'opts.probmineff'.
//
PHASE ("probe-round", stats.probingrounds,
"probing limit of %" PRId64 " propagations ", limit);
int old_failed = stats.failed_literals;
#ifndef QUIET
int64_t old_probed = stats.probed;
#endif
int64_t old_hbrs = stats.hbrs;
struct {
int64_t ticks;
} before, after;
before.ticks = stats.ticks_probe;
if (!probes.empty ())
flush_probes ();
// We reset 'propfixed' since there was at least another conflict thus
// a new learned clause, which might produce new propagations (and hyper
// binary resolvents). During 'generate_probes' we keep the old value.
//
for (auto idx : vars)
propfixed (idx) = propfixed (-idx) = -1;
assert (unsat || propagated == trail.size ());
propagated = propagated2 = trail.size ();
int probe;
init_probehbr_lrat ();
while (!unsat && !terminated_asynchronously () &&
stats.ticks_probe < limit && (probe = next_probe ())) {
stats.probed++;
LOG ("probing %d", probe);
probe_assign_decision (probe);
if (probe_propagate ())
backtrack_without_updating_phases ();
else
failed_literal (probe);
clean_probehbr_lrat ();
}
if (unsat)
LOG ("probing derived empty clause");
else if (propagated < trail.size ()) {
LOG ("probing produced %zd units",
(size_t) (trail.size () - propagated));
if (!propagate ()) {
LOG ("propagating units after probing results in empty clause");
learn_empty_clause ();
} else
sort_watches ();
}
int failed = stats.failed_literals - old_failed;
#ifndef QUIET
int64_t probed = stats.probed - old_probed;
#endif
int64_t hbrs = stats.hbrs - old_hbrs;
after.ticks = stats.ticks_probe;
stats.ticks += after.ticks - before.ticks;
PHASE ("probe-round", stats.probingrounds,
"probed %" PRId64 " and found %d failed literals", probed, failed);
if (hbrs)
PHASE ("probe-round", stats.probingrounds,
"found %" PRId64 " hyper binary resolvents", hbrs);
report ('p', !opts.reportall && !(unsat + failed + hbrs));
return !unsat && failed;
}
/*------------------------------------------------------------------------*/
// This schedules a number of inprocessing techniques.
// These range from very cheap and beneficial (decompose) to
// more expensive and sometimes less beneficial. We want to limit
// expensive techniques to some fraction of total time or search time.
// this is done using 'ticks'.
// Generally, there are options for each of the techniques to set the
// efficiency, i.e., the fraction of ticks they are allowed as budget.
// Whenever e.g. vivify is called, the budget is calculated from the
// search ticks that have passed since the last vivify round and this
// efficiency.
// We want to be able to run inprocessing frequently, without it dominating
// runtime. This entire inprocessing scheme is scheduled after a certain
// amount of conflicts were found, the gap between two inprocessing rounds
// increasing by a constant number each time. In effect, the number of
// inprocessing rounds is always the square root of the number of conflicts
// with some constant factor.
// This factor can also be with the option 'inprobeint'
// Some of the techniques are not run always, for different reasons.
// 'factor' or BVA depends on certain structures of the irredundant clauses
// and as such will only be run when new irredundant clauses are derived or
// it was not able to finish with the entire search space.
// 'sweeping' is especially useful on certain classes of formulas, and uses
// a increasing or decreasing delay that depends on how useful it was.
// In cases where it is less useful, we obviously want to reset the budged,
// even if the routine was delayed.
// Additionally 'vivify', 'sweep' and 'factor' can also have a big initial
// overhead in setting up the datastructures. This has to be accounted for
// with the 'ticks', however, since inprocessing is done frequently, this
// overhead is too expensive to pay. So instead, we accumulate the budget
// of 'ticks' and delay the technique until it passes a certain threshold,
// which depends on the the cost of initialization. Note that in the case of
// sweeping, we have two different delays, one which resets the budget, and
// one which passes it to the next round. In this case the former takes
// precedent, until we would run sweeping once, at which point the focus
// switches to the latter delay until the budget is big enough, such that
// sweeping can be run. Then we switch back to the other delay.
void CaDiCaL::Internal::inprobe (bool update_limits) {
if (unsat)
return;
if (terminated_asynchronously ())
return;
if (level)
backtrack ();
if (!propagate ()) {
learn_empty_clause ();
return;
}
stats.inprobingphases++;
if (external_prop) {
assert (!level);
private_steps = true;
}
const int before = active ();
const int64_t before_extended = stats.variables_extension;
// schedule of inprobing techniques.
//
{
mark_duplicated_binary_clauses_as_garbage ();
decompose ();
if (ternary ())
decompose (); // If we derived a binary clause
if (probe ())
decompose ();
if (extract_gates (preprocessing))
decompose ();
binary_clauses_backbone ();
mark_duplicated_binary_clauses_as_garbage ();
if (sweep ()) // full occurrence list
decompose (); // ... and (ELS) afterwards.
(void) vivify (); // resets watches
transred (); // builds big.
binary_clauses_backbone ();
mark_duplicated_binary_clauses_as_garbage ();
factor (); // resets watches, partial occurrence list
}
if (external_prop) {
assert (!level);
private_steps = false;
}
if (!update_limits)
return;
const int after = active ();
const int64_t after_extended = stats.variables_extension;
const int64_t diff_extended = after_extended - before_extended;
assert (diff_extended >= 0);
const int64_t removed = before - after + diff_extended;
assert (removed >= 0);
if (removed) {
stats.inprobingsuccess++;
PHASE ("probe-phase", stats.inprobingphases,
"successfully removed %" PRId64 " active variables %.0f%%",
removed, percent (removed, before));
} else
PHASE ("probe-phase", stats.inprobingphases,
"could not remove any active variable");
const int64_t delta =
25 * (int64_t) opts.inprobeint * log10 (stats.inprobingphases + 9);
assert (delta > 0);
lim.inprobe = stats.conflicts + delta;
PHASE ("probe-phase", stats.inprobingphases,
"new limit at %" PRId64 " conflicts after %" PRId64 " conflicts",
lim.inprobe, delta);
last.inprobe.reductions = stats.reductions;
}
} // namespace CaDiCaL