blob: c3db42801c24172a2cffe80a2422e78c1fee890d [file] [edit]
#include "walk.hpp"
#include "internal.hpp"
#include "random.hpp"
namespace CaDiCaL {
/*------------------------------------------------------------------------*/
ClauseOrBinary::clause_or_binary::TaggedBinary::TaggedBinary (
Internal *internal, CaDiCaL::Clause *c, unsigned clit, int cother)
: first_literal (clit), other (cother)
#if defined(LOGGING) || !defined(NDEBUG)
,
d (c)
#endif
{
#ifdef LOGGING
assert (c->literals[0] == internal->u2i (clit) ||
c->literals[1] == internal->u2i (clit));
assert (c->literals[0] == cother || c->literals[1] == cother);
#endif
#if !defined(LOGGING) || defined(NDEBUG)
(void) c;
(void) internal;
#endif
}
ClauseOrBinary::ClauseOrBinary (Internal *internal, Clause *c) {
// Check if literals fit in 31 bits each
if (c->size == 2) {
unsigned lit1 = internal->vlit (c->literals[0]);
const unsigned limit =
#ifndef NDEBUG
1u << (internal->opts.walkbinarylimit);
#else
(1u << 31);
#endif
if (lit1 < limit) {
// If literals fit, store as TaggedBinary
tagged.b.binary = true;
#if defined(LOGGING) || !defined(NDEBUG)
tagged.b.d = c;
#endif
tagged.b.first_literal = lit1;
tagged.b.other = c->literals[1];
return;
}
unsigned lit2 = internal->vlit (c->literals[1]);
if (lit2 < limit) {
// If literals fit, store as TaggedBinary
tagged.b.binary = true;
#if defined(LOGGING) || !defined(NDEBUG)
tagged.b.d = c;
#endif
tagged.b.first_literal = lit2;
tagged.b.other = c->literals[0];
return;
}
}
#if ((ULONG_MAX) != (UINT_MAX))
assert ((reinterpret_cast<uintptr_t> (c) & ((uintptr_t) 1 << 63)) == 0);
#endif
tagged.clause.clause_ptr = reinterpret_cast<uintptr_t> (c);
tagged.b.binary = false;
#if !defined(LOGGING) && defined(NDEBUG)
static_assert (sizeof (ClauseOrBinary) == 8,
"ClauseOrBinary compression does not work");
#endif
}
ClauseOrBinary::ClauseOrBinary (Clause *c) {
#if ((ULONG_MAX) != (UINT_MAX))
assert ((reinterpret_cast<uintptr_t> (c) & ((uintptr_t) 1 << 63)) == 0);
#endif
assert (c->size != 2);
tagged.clause.clause_ptr = reinterpret_cast<uintptr_t> (c);
tagged.b.binary = false;
}
int ClauseOrBinary::clause_or_binary::TaggedBinary::lit (
Internal *internal) const {
return internal->u2i (first_literal);
}
ClauseOrBinary::ClauseOrBinary (Internal *internal, Clause *c, int lit,
int other) noexcept {
unsigned lit1 = internal->vlit (lit);
assert (lit != other);
assert (c->size == 2);
if (lit1 < (1u << 31)) {
// If literals fit, store as TaggedBinary
tagged.b.binary = true;
#if defined(LOGGING) || !defined(NDEBUG)
tagged.b.d = c;
#endif
tagged.b.first_literal = lit1;
tagged.b.other = other;
return;
}
unsigned lit2 = internal->vlit (other);
if (lit2 < (1u << 31)) {
// If literals fit, store as TaggedBinary
tagged.b.binary = true;
#if defined(LOGGING) || !defined(NDEBUG)
tagged.b.d = c;
#endif
tagged.b.first_literal = lit2;
tagged.b.other = lit;
return;
}
#if ((ULONG_MAX) != (UINT_MAX))
assert ((reinterpret_cast<uintptr_t> (c) & ((uintptr_t) 1 << 63)) == 0);
#endif
tagged.clause.clause_ptr = reinterpret_cast<uintptr_t> (c);
}
// Random walk local search based on 'ProbSAT' ideas.
// We (based on the Master project from Leah Hohl) tried to ticks
// local search similarly to the other parts of the solver with
// limited success however.
//
// On the problem `ncc_none_5047_6_3_3_3_0_435991723', the broken part
// of walk_flip is very cheap and should not be counted in ticks, but
// on various other problems `9pipe_k' it is very important to ticks
// this part too.
// using ClauseOrBinary = std::variant <Clause*, TaggedBinary>;
struct Walker {
Internal *internal;
Random random; // local random number generator
int64_t ticks; // ticks to approximate run time
int64_t limit; // limit on number of propagations
vector<ClauseOrBinary> broken; // currently unsatisfied clauses
double epsilon; // smallest considered score
vector<double> table; // break value to score table
vector<double> scores; // scores of candidate literals
std::vector<int>
flips; // remember the flips compared to the last best saved model
int best_trail_pos;
size_t minimum = (size_t) (-1);
std::vector<signed char> best_values; // best model stored so far
double score (unsigned); // compute score from break count
#ifndef NDEBUG
std::vector<signed char> current_best_model; // best model found so far
#endif
Walker (Internal *, int64_t limit);
void populate_table (double size);
// for efficiency, storing the model each time an improvement is
// found is too costly. Instead we store some of the flips since
// last time and the position of the best model found so far.
//
// Once that buffer is full, we save the last best assignment. This is
// particularly important at the beginning where every or nearly every
// flip improves the current assignment.
// Push the literal on the buffer of flipped literals
void push_flipped (int flipped);
// save the best assignment found so far, if any was found
void save_walker_trail (bool);
// export the best model from walk to the main solver
void save_final_minimum (size_t old_minimum);
};
// These are in essence the CB values from Adrian Balint's thesis. They
// denote the inverse 'cb' of the base 'b' of the (probability) weight
// 'b^-i' for picking a literal with the break value 'i' (first column is
// the 'size', second the 'CB' value).
static constexpr double cbvals[][2] = {
{0.0, 2.00}, {3.0, 2.50}, {4.0, 2.85}, {5.0, 3.70},
{6.0, 5.10}, {7.0, 7.40}, // Adrian has '5.4', but '7.4' looks better.
};
static const int ncbvals = sizeof cbvals / sizeof cbvals[0];
// We interpolate the CB values for uniform random SAT formula to the non
// integer situation of average clause size by piecewise linear functions.
//
// y2 - y1
// ------- * (x - x1) + y1
// x2 - x1
//
// where 'x' is the average size of clauses and 'y' the CB value.
inline static double fitcbval (double size) {
int i = 0;
while (i + 2 < ncbvals &&
(cbvals[i][0] > size || cbvals[i + 1][0] < size))
i++;
const double x2 = cbvals[i + 1][0], x1 = cbvals[i][0];
const double y2 = cbvals[i + 1][1], y1 = cbvals[i][1];
const double dx = x2 - x1, dy = y2 - y1;
assert (dx);
const double res = dy * (size - x1) / dx + y1;
assert (res > 0);
return res;
}
// Initialize the data structures for one local search round.
Walker::Walker (Internal *i, int64_t l)
: internal (i), random (internal->opts.seed), // global random seed
ticks (0), limit (l), epsilon (-1), best_trail_pos (-1) {
random += internal->stats.walk; // different seed every time
flips.reserve (i->max_var / 4);
best_values.resize (i->max_var + 1, 0);
#ifndef NDEBUG
current_best_model.resize (i->max_var + 1, 0);
#endif
}
void Walker::populate_table (double size) {
// This is the magic constant in ProbSAT (also called 'CB'), which we pick
// according to the average size every second invocation and otherwise
// just the default '2.0', which turns into the base '0.5'.
//
const bool use_size_based_cb = (internal->stats.walk & 1);
const double cb = use_size_based_cb ? fitcbval (size) : 2.0;
assert (cb);
const double base = 1 / cb; // scores are 'base^0,base^1,base^2,...
double next = 1;
for (epsilon = next; next; next = epsilon * base)
table.push_back (epsilon = next);
PHASE ("walk", internal->stats.walk,
"CB %.2f with inverse %.2f as base and table size %zd", cb, base,
table.size ());
}
// Add the literal to flip to the queue
void Walker::push_flipped (int flipped) {
LOG ("push literal %s on the flips", LOGLIT (flipped));
assert (flipped);
if (best_trail_pos < 0) {
LOG ("not pushing flipped %s to already invalid trail",
LOGLIT (flipped));
return;
}
const size_t size_trail = flips.size ();
const size_t limit = internal->max_var / 4 + 1;
if (size_trail < limit) {
flips.push_back (flipped);
LOG ("pushed flipped %s to trail which now has size %zd",
LOGLIT (flipped), size_trail + 1);
return;
}
if (best_trail_pos) {
LOG ("trail reached limit %zd but has best position %d", limit,
best_trail_pos);
save_walker_trail (true);
flips.push_back (flipped);
LOG ("pushed flipped %s to trail which now has size %zu",
LOGLIT (flipped), flips.size ());
return;
} else {
LOG ("trail reached limit %zd without best position", limit);
flips.clear ();
LOG ("not pushing %s to invalidated trail", LOGLIT (flipped));
best_trail_pos = -1;
LOG ("best trail position becomes invalid");
}
}
void Walker::save_walker_trail (bool keep) {
assert (best_trail_pos != -1);
assert ((size_t) best_trail_pos <= flips.size ());
// assert (!keep || best_trail_pos == flips.size());
#ifdef LOGGING
const size_t size_trail = flips.size ();
#endif
const int kept = flips.size () - best_trail_pos;
LOG ("saving %d values of flipped literals on trail of size %zd",
best_trail_pos, flips.size ());
const auto begin = flips.begin ();
const auto best = flips.begin () + best_trail_pos;
const auto end = flips.end ();
auto it = begin;
for (; it != best; ++it) {
const int lit = *it;
assert (lit);
const signed char value = sign (lit);
const int idx = std::abs (lit);
best_values[idx] = value;
}
if (!keep) {
LOG ("no need to shift and keep remaining %u literals", kept);
return;
}
#ifndef NDEBUG
for (auto v : internal->vars) {
if (internal->active (v))
assert (best_values[v] == current_best_model[v]);
}
#endif
LOG ("flushed %u literals %.0f%% from trail", best_trail_pos,
percent (best_trail_pos, size_trail));
assert (it == best);
auto jt = begin;
for (; it != end; ++it, ++jt) {
assert (jt <= it);
assert (it < end);
*jt = *it;
}
assert ((int) (end - jt) == best_trail_pos);
assert ((int) (jt - begin) == kept);
flips.resize (kept);
LOG ("keeping %u literals %.0f%% on trail", kept,
percent (kept, size_trail));
LOG ("reset best trail position to 0");
best_trail_pos = 0;
}
// finally export the final minimum
void Walker::save_final_minimum (size_t old_init_minimum) {
assert (minimum <= old_init_minimum);
if (minimum == old_init_minimum) {
LOG ("no improvement thus keeping saved clauses");
return;
}
if (!best_trail_pos || best_trail_pos == -1)
LOG ("minimum already saved");
else
save_walker_trail (false);
++internal->stats.walk_improved;
for (auto v : internal->vars) {
if (best_values[v])
internal->phases.saved[v] = best_values[v];
else
assert (!internal->active (v));
}
internal->copy_phases (internal->phases.best);
internal->copy_phases (internal->phases.prev);
}
// The scores are tabulated for faster computation (to avoid 'pow').
inline double Walker::score (unsigned i) {
const double res = (i < table.size () ? table[i] : epsilon);
LOG ("break %u mapped to score %g", i, res);
return res;
}
/*------------------------------------------------------------------------*/
ClauseOrBinary Internal::walk_pick_clause (Walker &walker) {
MODE_REQUIRE (WALK);
assert (!walker.broken.empty ());
size_t size = walker.broken.size ();
if (size > INT_MAX)
size = INT_MAX;
int pos = walker.random.pick_int (0, (int) size - 1);
ClauseOrBinary res = walker.broken[pos];
#ifdef LOGGING
Clause *c;
if (!res.is_binary ())
c = res.clause ();
else
c = res.tagged_binary ().d;
LOG (c, "picking random position %d", pos);
#endif
return res;
}
/*------------------------------------------------------------------------*/
// Compute the number of clauses which would be become unsatisfied if 'lit'
// is flipped and set to false. This is called the 'break-count' of 'lit'.
unsigned Internal::walk_break_value (int lit, int64_t &ticks) {
MODE_REQUIRE (WALK);
PROFILE_SCOPE (walkbreak);
assert (val (lit) > 0);
const int64_t oldticks = ticks;
int64_t local_ticks = oldticks;
unsigned res = 0; // The computed break-count of 'lit'.
local_ticks += (1 + cache_lines (watches (lit).size (), sizeof (Watch)));
for (auto &w : watches (lit)) {
assert (w.blit != lit);
if (val (w.blit) > 0)
continue;
if (w.binary ()) {
res++;
continue;
}
Clause *c = w.clause;
#ifdef LOGGING
assert (c != dummy_binary);
#endif
++local_ticks;
assert (lit == c->literals[0]);
// Now try to find a second satisfied literal starting at 'literals[1]'
// shifting all the traversed literals to right by one position in order
// to move such a second satisfying literal to 'literals[1]'. This move
// to front strategy improves the chances to find the second satisfying
// literal earlier in subsequent break-count computations.
//
auto begin = c->begin () + 1;
const auto end = c->end ();
auto i = begin;
int prev = 0;
while (i != end) {
const int other = *i;
*i++ = prev;
prev = other;
if (val (other) < 0)
continue;
// Found 'other' as second satisfying literal.
w.blit = other; // Update 'blit'
*begin = other; // and move to front.
break;
}
if (i != end)
continue; // Double satisfied!
// Otherwise restore literals (undo shift to the right).
//
while (i != begin) {
const int other = *--i;
*i = prev;
prev = other;
}
res++; // Literal 'lit' single satisfies clause 'c'.
}
stats.ticks_walk_break += (local_ticks - oldticks);
ticks += (local_ticks - oldticks);
return res;
}
/*------------------------------------------------------------------------*/
// Given an unsatisfied clause 'c', in which we want to flip a literal, we
// first determine the exponential score based on the break-count of its
// literals and then sample the literals based on these scores. The CB
// value is smaller than one and thus the score is exponentially decreasing
// with the break-count increasing. The sampling works as in 'ProbSAT' and
// 'YalSAT' by summing up the scores and then picking a random limit in the
// range of zero to the sum, then summing up the scores again and picking
// the first literal which reaches the limit. Note, that during incremental
// SAT solving we can not flip assumed variables. Those are assigned at
// decision level one, while the other variables are assigned at two.
int Internal::walk_pick_lit (Walker &walker, Clause *c) {
LOG ("picking literal by break-count");
assert (walker.scores.empty ());
const int64_t old = walker.ticks;
walker.ticks += 1;
double sum = 0;
for (const auto lit : *c) {
assert (active (lit));
if (var (lit).level == 1) {
LOG ("skipping assumption %d for scoring", -lit);
continue;
}
assert (active (lit));
unsigned tmp = walk_break_value (-lit, walker.ticks);
double score = walker.score (tmp);
LOG ("literal %d break-count %u score %g", lit, tmp, score);
walker.scores.push_back (score);
sum += score;
}
LOG ("scored %zd literals", walker.scores.size ());
assert (!walker.scores.empty ());
assert (walker.scores.size () <= (size_t) c->size);
const double lim = sum * walker.random.generate_double ();
LOG ("score sum %g limit %g", sum, lim);
const auto end = c->end ();
auto i = c->begin ();
auto j = walker.scores.begin ();
int res;
for (;;) {
assert (i != end);
res = *i++;
if (var (res).level > 1)
break;
LOG ("skipping assumption %d without score", -res);
}
sum = *j++;
while (sum <= lim && i != end) {
res = *i++;
if (var (res).level == 1) {
LOG ("skipping assumption %d without score", -res);
continue;
}
sum += *j++;
}
walker.scores.clear ();
LOG ("picking literal %d by break-count", res);
stats.ticks_walk_pick += walker.ticks - old;
return res;
}
int Internal::walk_pick_lit (Walker &walker, ClauseOrBinary c) {
if (c.is_binary ())
return walk_pick_lit (walker, c.tagged_binary ());
return walk_pick_lit (walker, c.clause ());
}
int Internal::walk_pick_lit (
Walker &walker,
const ClauseOrBinary::clause_or_binary::TaggedBinary c) {
LOG ("picking literal by break-count on binary clause [%" PRIu64 "]%s %s",
c.d->id, LOGLIT (c.lit (internal)), LOGLIT (c.other));
assert (walker.scores.empty ());
const int64_t old = walker.ticks;
double sum = 0;
const std::array<int, 2> clause = {c.lit (internal), c.other};
for (const auto lit : clause) {
assert (active (lit));
if (var (lit).level == 1) {
LOG ("skipping assumption %d for scoring", -lit);
continue;
}
assert (active (lit));
assert (val (lit) < 0);
unsigned tmp = walk_break_value (-lit, walker.ticks);
double score = walker.score (tmp);
LOG ("literal %d break-count %u score %g", lit, tmp, score);
walker.scores.push_back (score);
sum += score;
}
LOG ("scored %zd literals", walker.scores.size ());
assert (!walker.scores.empty ());
assert (walker.scores.size () <= (size_t) 2);
const double lim = sum * walker.random.generate_double ();
LOG ("score sum %g limit %g", sum, lim);
const auto end = clause.end ();
auto i = clause.begin ();
auto j = walker.scores.begin ();
int res = 0;
for (;;) {
assert (i != end);
res = *i++;
if (var (res).level > 1)
break;
LOG ("skipping assumption %d without score", -res);
}
sum = *j++;
while (sum <= lim && i != end) {
res = *i++;
if (var (res).level == 1) {
LOG ("skipping assumption %d without score", -res);
continue;
}
sum += *j++;
}
assert (res);
walker.scores.clear ();
LOG ("picking literal %d by break-count", res);
stats.ticks_walk_pick += walker.ticks - old;
return res;
}
/*------------------------------------------------------------------------*/
// flips a literal unless we run out of ticks.
bool Internal::walk_flip_lit (Walker &walker, int lit) {
MODE_REQUIRE (WALK);
PROFILE_SCOPE (walkflip);
const int64_t old = walker.ticks;
int64_t ticks = old;
LOG ("flipping assign %d", lit);
assert (val (lit) < 0);
// First flip the literal value.
//
const signed char tmp = sign (lit);
const int idx = abs (lit);
set_val (idx, tmp);
assert (val (lit) > 0);
const int neg_lit = -lit;
const int64_t limit = walker.limit;
// we are going to need it anyway and it probably still is in memory
const Watches &ws = watches (neg_lit);
if (!ws.empty ()) {
const Watch &w = ws[0];
__builtin_prefetch (&w, 0, 1);
}
// Then remove 'c' and all other now satisfied (made) clauses.
{
// Simply go over all unsatisfied (broken) clauses.
LOG ("trying to make %zd broken clauses", walker.broken.size ());
const size_t broken_size = walker.broken.size ();
ClauseOrBinary *const broken_begin = walker.broken.data ();
ClauseOrBinary *const broken_end =
broken_size ? broken_begin + broken_size : broken_begin;
ClauseOrBinary *j = broken_begin, *i = broken_begin;
// broken is in cache given how central it is... but not always (see the
// ncc problems). Value was heuristically determined to give reasonnable
// values.
ticks += 1 + cache_lines (broken_size, sizeof (*i));
#if defined(LOGGING) || !defined(NDEBUG)
int64_t made = 0;
#endif
while (i != broken_end) {
ClauseOrBinary tagged = *j++ = *i++;
if (tagged.is_binary ()) {
const ClauseOrBinary::clause_or_binary::TaggedBinary &b =
tagged.tagged_binary ();
const int clit = b.lit (internal);
const int other = b.other;
assert (val (clit) < 0 || val (other) < 0);
#if defined(LOGGING)
assert (b.d->literals[0] == clit || b.d->literals[1] == clit);
assert (b.d->literals[0] == other || b.d->literals[1] == other);
#endif
if (clit == lit || other == lit) {
LOG (b.d, "made");
const int second_lit = clit ^ lit ^ other;
#ifdef LOGGING
watch_binary_literal (lit, second_lit, b.d);
#else
// placeholder for the clause, does not matter
watch_binary_literal (lit, second_lit, dummy_binary);
#endif
++ticks;
#if defined(LOGGING) || !defined(NDEBUG)
made++;
#endif
j--;
} else {
LOG (b.d, "still broken");
assert (val (clit) < 0 && val (other) < 0);
}
continue;
}
// now the expansive part
Clause *d = tagged.clause ();
++ticks;
int *literals = d->literals;
LOG (d, "search for replacement");
int prev = 0;
// Find 'lit' in 'd'.
//
const int size = d->size;
for (int i = 0; i < size; i++) {
const int other = literals[i];
assert (active (other));
literals[i] = prev;
prev = other;
if (other == lit)
break;
assert (val (other) < 0);
}
// If 'lit' is in 'd' then move it to the front to watch it.
//
if (prev == lit) {
literals[0] = lit;
LOG (d, "made");
watch_literal (literals[0], literals[1], d);
++ticks;
#if defined(LOGGING) || !defined(NDEBUG)
made++;
#endif
j--;
} else { // Otherwise the clause is not satisfied, undo shift.
for (int i = size - 1; i >= 0; i--) {
int other = literals[i];
literals[i] = prev;
prev = other;
}
}
LOG (d, "clause after undoing shift");
}
assert ((int64_t) (j - broken_begin) + made == (int64_t) broken_size);
walker.broken.resize (j - broken_begin);
LOG ("made %" PRId64 " clauses by flipping %d, still %zu broken", made,
lit, walker.broken.size ());
#ifndef NDEBUG
for (auto d : walker.broken) {
if (d.is_binary ()) {
const ClauseOrBinary::clause_or_binary::TaggedBinary &b =
d.tagged_binary ();
assert (val (b.lit (internal)) < 0 && val (b.other) < 0);
} else {
for (auto lit : *d.clause ())
assert (val (lit) < 0);
}
}
#endif
if (ticks > limit) {
walker.ticks = ticks;
return false;
}
}
stats.ticks_walk_flip_broke += ticks - old;
const int64_t old_after_broken = ticks;
// Finally add all new unsatisfied (broken) clauses.
{
#ifdef LOGGING
int64_t broken = 0;
#endif
Watches &ws = watches (neg_lit);
// probably still in cache
const size_t ws_size = ws.size ();
ticks += 1 + cache_lines (ws_size, sizeof (Watch));
LOG ("trying to break %zd watched clauses", ws_size);
for (const auto &w : ws) {
Clause *d = w.clause;
const bool binary = w.binary ();
if (binary) {
const int other = w.blit;
assert (other != neg_lit);
const signed char other_val = val (other);
if (other_val > 0) {
LOG (d, "unwatch %d in", neg_lit);
watch_binary_literal (other, neg_lit, d);
++ticks;
continue;
}
LOG (d, "broken");
#ifdef LOGGING
assert (d != dummy_binary);
#endif
walker.broken.emplace_back (internal, d, neg_lit, other);
++ticks;
#ifdef LOGGING
broken++;
#endif
continue;
}
if (ticks > limit) {
walker.ticks = ticks;
return false;
}
// now the expansive part
assert (d->size != 2);
++ticks;
int *literals = d->literals, replacement = 0, prev = neg_lit;
assert (d->size == w.size);
const int size = d->size;
assert (literals[0] == neg_lit);
for (int i = 1; i < size; i++) {
const int other = literals[i];
assert (active (other));
literals[i] = prev; // shift all to right
prev = other;
const signed char other_val = val (other);
if (other_val < 0)
continue;
replacement = other; // satisfying literal
break;
}
if (replacement) {
assert (neg_lit != replacement);
literals[1] = neg_lit;
literals[0] = replacement;
watch_literal (replacement, neg_lit, d);
++ticks;
LOG (d, "found replacement");
} else {
for (int i = size - 1; i > 0; i--) { // undo shift
const int other = literals[i];
literals[i] = prev;
prev = other;
}
assert (literals[0] == neg_lit);
LOG (d, "broken");
walker.broken.emplace_back (d);
++ticks;
#ifdef LOGGING
broken++;
#endif
}
}
LOG ("broken %" PRId64 " clauses by flipping %d", broken, lit);
ws.clear ();
}
walker.ticks = ticks;
stats.ticks_walk_flip_wl += ticks - old_after_broken;
stats.ticks_walk_flip += ticks - old;
return true;
}
/*------------------------------------------------------------------------*/
// Check whether to save the current phases as new global minimum.
inline void Internal::walk_save_minimum (Walker &walker) {
size_t broken = walker.broken.size ();
if (broken >= walker.minimum)
return;
if (broken <= (unsigned) stats.walk_minimum) {
stats.walk_minimum = broken;
VERBOSE (3, "new global minimum %zd", broken);
} else {
VERBOSE (3, "new walk minimum %zd", broken);
}
walker.minimum = broken;
#ifndef NDEBUG
for (auto i : vars) {
const signed char tmp = vals[i];
if (tmp)
walker.current_best_model[i] = tmp;
}
if (walker.minimum == 0) {
for (auto c : clauses) {
if (c->garbage)
continue;
if (c->redundant)
continue;
int satisfied = 0;
for (const auto &lit : *c) {
const int tmp = internal->val (lit);
if (tmp > 0) {
LOG (c, "satisfied literal %d in", lit);
satisfied++;
}
}
assert (satisfied);
}
}
#endif
if (walker.best_trail_pos == -1) {
VERBOSE (3, "saving the new walk minimum %zd", broken);
for (auto i : vars) {
const signed char tmp = vals[i];
if (tmp) {
walker.best_values[i] = tmp;
#ifndef NDEBUG
assert (tmp == walker.current_best_model[i]);
#endif
} else {
assert (!active (i));
}
}
walker.best_trail_pos = 0;
} else {
walker.best_trail_pos = walker.flips.size ();
LOG ("new best trail position %u", walker.best_trail_pos);
}
}
/*------------------------------------------------------------------------*/
int Internal::walk_round (int64_t limit, bool prev) {
stats.walk++;
std::vector<int> propagated;
bool failed = false; // Inconsistent assumptions?
int res = decide_and_propagate_all_assumptions (propagated);
if (res) {
return res;
}
// Remove all fixed variables first (assigned at decision level zero).
//
if (last.collect.fixed < stats.vars_all_fixed)
garbage_collection ();
clear_watches ();
#ifndef QUIET
// We want to see more messages during initial local search.
//
if (localsearching) {
assert (!force_phase_messages);
force_phase_messages = true;
}
#endif
PHASE ("walk", stats.walk, "random walk limit of %" PRId64 " ticks",
limit);
// Instantiate data structures for this local search round.
//
Walker walker (internal, limit);
#ifndef QUIET
size_t old_global_minimum = stats.walk_minimum;
#endif
level = 1; // Assumed variables assigned at level 1.
if (assumptions.empty ()) {
LOG ("no assumptions so assigning all variables to decision phase");
} else {
LOG ("assigning assumptions to their forced phase first");
std::vector<int> propagated;
for (auto lit : trail)
propagated.push_back (lit);
for (const auto lit : propagated) {
signed char tmp = val (lit);
if (tmp > 0)
continue;
assert (tmp == 0);
if (!active (lit))
continue;
tmp = sign (lit);
const int idx = abs (lit);
LOG ("initial assign %d to assumption phase", tmp < 0 ? -idx : idx);
set_val (idx, tmp);
assert (level == 1);
var (idx).level = 1;
}
if (!failed)
LOG ("now assigning remaining variables to their decision phase");
}
level = 2; // All other non assumed variables assigned at level 2.
if (!failed) {
// warmup stores the result in phases, not in target
const bool target = opts.warmup ? false : stable || opts.target == 2;
for (auto idx : vars) {
if (!active (idx)) {
LOG ("skipping inactive variable %d", idx);
continue;
}
if (vals[idx]) {
assert (var (idx).level == 1);
LOG ("skipping assumed variable %d", idx);
continue;
}
int tmp = 0;
if (prev)
tmp = phases.prev[idx];
if (!tmp)
tmp = sign (decide_phase (idx, target));
assert (tmp == 1 || tmp == -1);
set_val (idx, tmp);
assert (level == 2);
var (idx).level = 2;
LOG ("initial assign %d to decision phase", tmp < 0 ? -idx : idx);
}
LOG ("watching satisfied and registering broken clauses");
#ifdef LOGGING
size_t watched = 0;
#endif
double size = 0;
int64_t n = 0;
for (const auto c : clauses) {
if (c->garbage)
continue;
if (c->redundant) {
if (opts.walkredundant == 1 && c->size == 2 && !c->hyper)
LOG (c, "importing binary clause");
else if (opts.walkredundant == 0)
continue;
if (!likely_to_be_kept_clause (c))
continue;
}
bool satisfiable = false; // contains not only assumptions
int satisfied = 0; // clause satisfied?
int *lits = c->literals;
size += c->size;
n++;
const int size = c->size;
// Move to front satisfied literals and determine whether there
// is at least one (non-assumed) literal that can be flipped.
//
for (int i = 0; satisfied < 2 && i < size; i++) {
const int lit = lits[i];
assert (active (lit)); // Due to garbage collection.
if (val (lit) > 0) {
swap (lits[satisfied], lits[i]);
if (!satisfied++)
LOG ("first satisfying literal %d", lit);
} else if (!satisfiable && var (lit).level > 1) {
LOG ("non-assumption potentially satisfying literal %d", lit);
satisfiable = true;
}
}
if (!satisfied && !satisfiable) {
LOG (c, "due to assumptions unsatisfiable");
LOG ("stopping local search since assumptions falsify a clause");
failed = true;
break;
}
if (satisfied) {
LOG (c, "pushing to satisfied");
if (c->size == 2)
watch_binary_literal (lits[0], lits[1], c);
else
watch_literal (lits[0], lits[1], c);
#ifdef LOGGING
watched++;
#endif
} else {
assert (satisfiable); // at least one non-assumed variable ...
LOG (c, "broken");
assert (c->size == size);
if (size == 2)
walker.broken.emplace_back (walker.internal, c);
else
walker.broken.emplace_back (c);
}
}
double average_size = relative (size, n);
walker.populate_table (average_size);
PHASE ("walk", stats.walk,
"%" PRId64 " clauses average size %.2f over %d variables", n,
average_size, active ());
#ifdef LOGGING
if (!failed) {
size_t broken = walker.broken.size ();
size_t total = watched + broken;
LOG ("watching %zd clauses %.0f%% "
"out of %zd (watched and broken)",
watched, percent (watched, total), total);
}
#endif
}
assert (failed || walker.table.size ());
if (!failed) {
size_t broken = walker.broken.size ();
size_t initial_minimum = broken;
PHASE ("walk", stats.walk,
"starting with %zd unsatisfied clauses "
"(%.0f%% out of %" PRId64 ")",
broken, percent (broken, stats.clauses_now_irr),
stats.clauses_now_irr);
walk_save_minimum (walker);
assert (stats.walk_minimum <= (int64_t) walker.minimum);
size_t minimum = broken;
#ifndef QUIET
int64_t flips = 0;
#endif
while (!terminated_asynchronously () && !walker.broken.empty () &&
walker.ticks < walker.limit) {
#ifndef QUIET
flips++;
#endif
stats.walk_flips++;
stats.walk_broken += (int64_t) broken;
ClauseOrBinary c = walk_pick_clause (walker);
const int lit = walk_pick_lit (walker, c);
bool finished = walk_flip_lit (walker, lit);
if (!finished)
break;
walker.push_flipped (lit);
broken = walker.broken.size ();
LOG ("now have %zd broken clauses in total", broken);
if (broken >= minimum)
continue;
minimum = broken;
VERBOSE (3, "new phase minimum %zd after %" PRId64 " flips", minimum,
flips);
walk_save_minimum (walker);
}
walker.save_final_minimum (initial_minimum);
#ifndef QUIET
if (minimum == initial_minimum) {
PHASE ("walk", internal->stats.walk,
"%sno improvement %zd%s in %" PRId64 " flips and "
"%" PRId64 " ticks",
tout.bright_yellow_code (), minimum, tout.normal_code (),
flips, walker.ticks);
} else if (minimum < old_global_minimum)
PHASE ("walk", stats.walk,
"%snew global minimum %zd%s in %" PRId64 " flips and "
"%" PRId64 " ticks",
tout.bright_yellow_code (), minimum, tout.normal_code (),
flips, walker.ticks);
else
PHASE ("walk", stats.walk,
"best phase minimum %zd in %" PRId64 " flips and "
"%" PRId64 " ticks",
minimum, flips, walker.ticks);
if (opts.profile >= 2) {
PHASE ("walk", stats.walk, "%.2f million ticks per second",
1e-6 *
relative (walker.ticks, time () - profiles.walk.started));
PHASE ("walk", stats.walk, "%.2f thousand flips per second",
relative (1e-3 * flips, time () - profiles.walk.started));
} else {
PHASE ("walk", stats.walk, "%.2f ticks", 1e-6 * walker.ticks);
PHASE ("walk", stats.walk, "%.2f thousand flips", 1e-3 * flips);
}
#endif
if (minimum > 0) {
LOG ("minimum %zd non-zero thus potentially continue", minimum);
res = 0;
} else {
LOG ("minimum is zero thus stop local search");
res = 10;
}
} else {
res = 20;
PHASE ("walk", stats.walk, "aborted due to inconsistent assumptions");
}
for (auto idx : vars)
if (active (idx))
set_val (idx, 0);
assert (level == 2);
level = 0;
clear_watches ();
connect_watches ();
#ifndef QUIET
if (localsearching) {
assert (force_phase_messages);
force_phase_messages = false;
}
#endif
stats.ticks_walk += walker.ticks;
stats.ticks += walker.ticks;
return res;
}
void Internal::walk () {
MODE_SCOPE_WALK (WALK);
PROFILE_SCOPE_WALK (walk);
backtrack ();
if (propagated < trail.size () && !propagate ()) {
LOG ("empty clause after root level propagation");
learn_empty_clause ();
return;
}
int res = 0;
if (opts.warmup)
res = warmup ();
if (res) {
LOG ("stopping walk due to warmup");
return;
}
const int64_t ticks =
stats.ticks_search_unstable + stats.ticks_search_stable;
int64_t limit = ticks - last.walk.ticks;
last.walk.ticks = ticks;
limit *= 1e-3 * opts.walkeffort;
if (limit < opts.walkmineff)
limit = opts.walkmineff;
// local search is very cache friendly, so we actually really go over a
// lot of ticks
if (limit > 1e3 * opts.walkmaxeff) {
MSG ("reached maximum efficiency %" PRId64, limit);
limit = 1e3 * opts.walkmaxeff;
}
VERBOSE (2,
"walk scheduling: last %" PRId64 " current %" PRId64
" delta %" PRId64,
last.walk.ticks, ticks, limit);
(void) walk_round (limit, false);
}
} // namespace CaDiCaL