blob: 2bc27d9fb4d00b832f0efdc57aa90915d8b29e80 [file] [edit]
#include "internal.hpp"
namespace CaDiCaL {
// As observed by Chanseok Oh and implemented in MapleSAT solvers too,
// various mostly satisfiable instances benefit from long quiet phases
// with less or almost no restarts. We implement this idea by prohibiting
// the Glucose style restart scheme in a geometric fashion, which is very
// similar to how originally restarts were scheduled in MiniSAT and earlier
// solvers. We start with say 1e3 = 1000 (opts.stabilizeinit) conflicts of
// Glucose restarts. Then in a "stabilizing" phase we disable these
// until 1e4 = 2000 conflicts (if 'opts.stabilizefactor' is '200' percent)
// have passed. After that we switch back to regular Glucose style restarts
// until again 2 times more conflicts than the previous limit are reached.
// Actually, in the latest version we still restarts during stabilization
// but only in a reluctant doubling scheme with a rather high interval.
bool Internal::stabilizing () {
if (!opts.stabilize)
return false;
if (stable && opts.stabilizeonly)
return true;
if (!inc.stabilize) {
assert (!stable);
if (stats.conflicts <= lim.stabilize)
return false;
} else if ((stable && stats.ticks_search_stable <= lim.stabilize) ||
(!stable && stats.ticks_search_unstable <= lim.stabilize))
return stable;
report (stable ? ']' : '}');
PROFILE_SCOPE_SEARCH_STABILIZE ();
assert (last.stabilize.ticks >= 0);
assert (last.stabilize.conflicts >= 0 &&
last.stabilize.conflicts <= stats.conflicts);
const int64_t delta_ticks =
stable ? stats.ticks_search_stable - last.stabilize.ticks
: stats.ticks_search_unstable - last.stabilize.ticks;
assert (delta_ticks >= 0);
#ifndef QUIET
const int64_t delta_conflicts =
stats.conflicts - last.stabilize.conflicts;
const char *current_mode = stable ? "stable" : "unstable";
const char *next_mode = stable ? "unstable" : "stable";
#endif
PHASE ("stabilizing", stats.stable_phases_total,
"reached %s stabilization limit %" PRId64 " after %" PRId64
" conflicts and %" PRId64 " ticks at %" PRId64
" conflicts and %" PRId64 " ticks",
current_mode, lim.stabilize, delta_conflicts, delta_ticks,
stats.conflicts,
stable ? stats.ticks_search_stable : stats.ticks_search_unstable);
if (!inc.stabilize)
inc.stabilize = delta_ticks;
if (!inc.stabilize) // rare occurence in incremental calls requiring no
// ticks
inc.stabilize = 1;
int64_t next_delta_ticks = inc.stabilize;
int64_t stabphases = stats.stable_phases_current + 1;
next_delta_ticks *= stabphases * stabphases;
lim.stabilize = next_delta_ticks;
if (lim.stabilize < 1)
lim.stabilize = 1;
lim.stabilize +=
!stable ? stats.ticks_search_stable : stats.ticks_search_unstable;
last.stabilize.ticks =
!stable ? stats.ticks_search_stable : stats.ticks_search_unstable;
PHASE ("stabilizing", stats.stable_phases_total,
"next %s stabilization limit %" PRId64
" at ticks interval %" PRId64,
next_mode, lim.stabilize, next_delta_ticks);
stable = !stable; // Switch!!!!!
if (stable)
++stats.stable_phases_total, ++stats.stable_phases_current;
swap_averages ();
report (stable ? '[' : '{');
return stable;
}
// Restarts are scheduled by a variant of the Glucose scheme as presented
// in our POS'15 paper using exponential moving averages. There is a slow
// moving average of the average recent glucose level of learned clauses
// as well as a fast moving average of those glues. If the end of a base
// restart conflict interval has passed and the fast moving average is
// above a certain margin over the slow moving average then we restart.
bool Internal::restarting () {
if (!opts.restart)
return false;
if ((size_t) level < assumptions.size () + 2)
return false;
if (stabilizing () && opts.reluctant)
return reluctant;
if (stats.conflicts <= lim.restart)
return false;
double f = averages.current.glue.fast;
int p = stable ? opts.restartmarginstable : opts.restartmarginfocused;
double m = (100.0 + p) / 100.0;
double s = averages.current.glue.slow;
double l = m * s;
#ifndef QUIET
char c = l > f ? '>' : l < f ? '<' : '=';
VERBOSE (3,
"restart glue limit "
"%g = %.2f * %g (slow glue) %c %g (fast glue)",
l, m, s, c, f);
#endif
return l <= f;
}
// This is Marijn's reuse trail idea. Instead of always backtracking to
// the top we figure out which decisions will be made again anyhow and
// only backtrack to the level of the last such decision or to the top if
// no such decision exists top (in which case we do not reuse any level).
int Internal::reuse_trail () {
const int trivial_decisions =
assumptions.size ()
// Plus 1 if the constraint is satisfied via implications of
// assumptions and a pseudo-decision level was introduced.
+ !control[assumptions.size () + 1].decision;
if (!opts.restartreusetrail)
return trivial_decisions;
int next_decision = next_decision_variable ();
assert (1 <= next_decision);
int res = trivial_decisions;
if (use_scores ()) {
while (res < level) {
int decision = control[res + 1].decision;
if (decision && score_smaller (this) (abs (decision), next_decision))
break;
res++;
}
} else {
int64_t limit = bumped (next_decision);
while (res < level) {
int decision = control[res + 1].decision;
if (decision && bumped (decision) < limit)
break;
res++;
}
}
int reused = res - trivial_decisions;
if (reused > 0) {
stats.reused++;
stats.reused_levels += reused;
if (stable)
stats.reused_stable++;
}
return res;
}
void Internal::restart () {
PROFILE_SCOPE (restart);
stats.restart++;
stats.restart_levels += level;
if (stable)
stats.restart_stable++;
LOG ("restart %" PRId64 "", stats.restart);
backtrack (reuse_trail ());
lim.restart = stats.conflicts + opts.restartint;
LOG ("new restart limit at %" PRId64 " conflicts", lim.restart);
report ('R', 2);
}
} // namespace CaDiCaL