1 #include "internal.hpp"
2
3 namespace CaDiCaL {
4
5 /*------------------------------------------------------------------------*/
6
7 // Implements a variant of bounded variable elimination as originally
8 // described in our SAT'05 paper introducing 'SATeLite'. This is an
9 // inprocessing version, i.e., it is interleaved with search and triggers
10 // blocked clause elimination, subsumption and strengthening rounds during
11 // elimination rounds. It focuses only those variables which occurred in
12 // removed irredundant clauses since the last time an elimination round
13 // was run. By bounding the maximum resolvent size we can run each
14 // elimination round until completion. See the code of 'elim' for how
15 // elimination rounds are interleaved with blocked clause elimination and
16 // subsumption (which in turn also calls vivification and transitive
17 // reduction of the binary implication graph).
18
19 /*------------------------------------------------------------------------*/
20
compute_elim_score(unsigned lit)21 inline double Internal::compute_elim_score (unsigned lit) {
22 assert (1 <= lit), assert (lit <= (unsigned) max_var);
23 const unsigned uidx = 2*lit;
24 const double pos = internal->ntab [uidx];
25 const double neg = internal->ntab [uidx + 1];
26 if (!pos) return -neg;
27 if (!neg) return -pos;
28 double sum = pos + neg, prod = 0;
29 if (opts.elimprod) prod = opts.elimprod * pos * neg;
30 return prod + sum;
31 }
32
33 /*------------------------------------------------------------------------*/
34
operator ()(unsigned a,unsigned b)35 inline bool elim_more::operator () (unsigned a, unsigned b) {
36 const auto s = internal->compute_elim_score (a);
37 const auto t = internal->compute_elim_score (b);
38 if (s > t) return true;
39 if (s < t) return false;
40 return a > b;
41 }
42
43 /*------------------------------------------------------------------------*/
44
45 // Note that the new fast subsumption algorithm implemented in 'subsume'
46 // does not distinguish between irredundant and redundant clauses and is
47 // also run during search to strengthen and remove 'sticky' redundant
48 // clauses but also irredundant ones. So beside learned units during search
49 // or as consequence of other preprocessors, these subsumption rounds during
50 // search can remove (irredundant) clauses (and literals), which in turn
51 // might make new bounded variable elimination possible. This is tested
52 // in the 'bool eliminating ()' guard.
53
eliminating()54 bool Internal::eliminating () {
55
56 if (!opts.simplify) return false;
57 if (!opts.elim) return false;
58 if (!preprocessing && !opts.inprocessing) return false;
59 if (preprocessing) assert (lim.preprocessing);
60
61 // Respect (increasing) conflict limit.
62 //
63 if (lim.elim >= stats.conflicts) return false;
64
65 // Wait until there are new units or new removed variables
66 // (in removed or shrunken irredundant clauses and thus marked).
67 //
68 if (last.elim.fixed < stats.all.fixed) return true;
69 if (last.elim.marked < stats.mark.elim) return true;
70
71 return false;
72 }
73
74 /*------------------------------------------------------------------------*/
75
76 // Update the global elimination schedule after adding or removing a clause.
77
78 void
elim_update_added_clause(Eliminator & eliminator,Clause * c)79 Internal::elim_update_added_clause (Eliminator & eliminator, Clause * c) {
80 assert (!c->redundant);
81 ElimSchedule & schedule = eliminator.schedule;
82 for (const auto & lit : *c) {
83 if (!active (lit)) continue;
84 occs (lit).push_back (c);
85 if (frozen (lit)) continue;
86 noccs (lit)++;
87 const int idx = abs (lit);
88 if (schedule.contains (idx)) schedule.update (idx);
89 }
90 }
91
elim_update_removed_lit(Eliminator & eliminator,int lit)92 void Internal::elim_update_removed_lit (Eliminator & eliminator, int lit) {
93 if (!active (lit)) return;
94 if (frozen (lit)) return;
95 int64_t & score = noccs (lit);
96 assert (score > 0);
97 score--;
98 const int idx = abs (lit);
99 ElimSchedule & schedule = eliminator.schedule;
100 if (schedule.contains (idx)) schedule.update (idx);
101 else {
102 LOG ("rescheduling %d for elimination after removing clause", idx);
103 schedule.push_back (idx);
104 }
105 }
106
107 void
elim_update_removed_clause(Eliminator & eliminator,Clause * c,int except)108 Internal::elim_update_removed_clause (Eliminator & eliminator,
109 Clause * c, int except)
110 {
111 assert (!c->redundant);
112 for (const auto & lit : *c) {
113 if (lit == except) continue;
114 assert (lit != -except);
115 elim_update_removed_lit (eliminator, lit);
116 }
117 }
118
119 /*------------------------------------------------------------------------*/
120
121 // Since we do not have watches we have to do our own unit propagation
122 // during elimination as soon we find a unit clause. This finds new units
123 // and also marks clauses satisfied by those units as garbage immediately.
124
elim_propagate(Eliminator & eliminator,int root)125 void Internal::elim_propagate (Eliminator & eliminator, int root) {
126 assert (val (root) > 0);
127 vector<int> work;
128 size_t i = 0;
129 work.push_back (root);
130 while (i < work.size ()) {
131 int lit = work[i++];
132 LOG ("elimination propagation of %d", lit);
133 assert (val (lit) > 0);
134 const Occs & ns = occs (-lit);
135 for (const auto & c : ns) {
136 if (c->garbage) continue;
137 int unit = 0, satisfied = 0;
138 for (const auto & other : *c) {
139 const int tmp = val (other);
140 if (tmp < 0) continue;
141 if (tmp > 0) { satisfied = other; break; }
142 if (unit) unit = INT_MIN;
143 else unit = other;
144 }
145 if (satisfied) {
146 LOG (c, "elimination propagation of %d finds %d satisfied",
147 lit, satisfied);
148 elim_update_removed_clause (eliminator, c, satisfied);
149 mark_garbage (c);
150 } else if (!unit) {
151 LOG ("empty clause during elimination propagation of %d", lit);
152 learn_empty_clause ();
153 break;
154 } else if (unit != INT_MIN) {
155 LOG ("new unit %d during elimination propagation of %d", unit, lit);
156 assign_unit (unit);
157 work.push_back (unit);
158 }
159 }
160 if (unsat) break;
161 const Occs & ps = occs (lit);
162 for (const auto & c : ps) {
163 if (c->garbage) continue;
164 LOG (c, "elimination propagation of %d produces satisfied", lit);
165 elim_update_removed_clause (eliminator, c, lit);
166 mark_garbage (c);
167 }
168 }
169 }
170
171 /*------------------------------------------------------------------------*/
172
173 // On-the-fly self-subsuming resolution during variable elimination is due
174 // to HyoJung Han, Fabio Somenzi, SAT'09. Basically while resolving two
175 // clauses we test the resolvent to be smaller than one of the antecedents.
176 // If this is the case the pivot can be removed from the antecedent
177 // on-the-fly and the resolution can be skipped during elimination.
178
elim_on_the_fly_self_subsumption(Eliminator & eliminator,Clause * c,int pivot)179 void Internal::elim_on_the_fly_self_subsumption (Eliminator & eliminator,
180 Clause * c, int pivot)
181 {
182 LOG (c, "pivot %d on-the-fly self-subsuming resolution", pivot);
183 stats.elimotfstr++;
184 stats.strengthened++;
185 assert (clause.empty ());
186 for (const auto & lit : *c) {
187 if (lit == pivot) continue;
188 const int tmp = val (lit);
189 assert (tmp <= 0);
190 if (tmp < 0) continue;
191 clause.push_back (lit);
192 }
193 Clause * r = new_resolved_irredundant_clause ();
194 elim_update_added_clause (eliminator, r);
195 clause.clear ();
196 elim_update_removed_clause (eliminator, c, pivot);
197 mark_garbage (c);
198 }
199
200 /*------------------------------------------------------------------------*/
201
202 // Resolve two clauses on the pivot literal 'pivot', which is assumed to
203 // occur in opposite phases in 'c' and 'd'. The actual resolvent is stored
204 // in the temporary global 'clause' if it is not redundant. It is
205 // considered redundant if one of the clauses is already marked as garbage
206 // it is root level satisfied, the resolvent is empty, a unit, or produces a
207 // self-subsuming resolution, which results in the pivot to be removed from
208 // at least one of the antecedents.
209
210 // Note that current root level assignments are taken into account, i.e., by
211 // removing root level falsified literals. The function returns true if the
212 // resolvent is not redundant and for instance has to be taken into account
213 // during bounded variable elimination.
214
215 // Detected units are immediately assigned but not propagated yet.
216
resolve_clauses(Eliminator & eliminator,Clause * c,int pivot,Clause * d)217 bool Internal::resolve_clauses (Eliminator & eliminator,
218 Clause * c, int pivot, Clause * d) {
219
220 assert (!c->redundant);
221 assert (!d->redundant);
222
223 stats.elimres++;
224
225 if (c->garbage || d->garbage) return false;
226 if (c->size > d->size) { pivot = -pivot; swap (c, d); }
227
228 assert (!level);
229 assert (clause.empty ());
230
231 int satisfied = 0; // Contains this satisfying literal.
232 int tautological = 0; // Clashing literal if tautological.
233
234 int s = 0; // Actual literals from 'c'.
235 int t = 0; // Actual literals from 'd'.
236
237 // First determine whether the first antecedent is satisfied, add its
238 // literals to 'clause' and mark them (except for 'pivot').
239 //
240 for (const auto & lit : *c) {
241 if (lit == pivot) { s++; continue; }
242 assert (lit != -pivot);
243 const int tmp = val (lit);
244 if (tmp > 0) { satisfied = lit; break; }
245 else if (tmp < 0) continue;
246 else mark (lit), clause.push_back (lit), s++;
247 }
248 if (satisfied) {
249 LOG (c, "satisfied by %d antecedent", satisfied);
250 elim_update_removed_clause (eliminator, c, satisfied);
251 mark_garbage (c);
252 clause.clear ();
253 unmark (c);
254 return false;
255 }
256
257 // Then determine whether the second antecedent is satisfied, add its
258 // literal to 'clause' and check whether a clashing literal is found, such
259 // that the resolvent would be tautological.
260 //
261 for (const auto & lit : *d) {
262 if (lit == -pivot) { t++; continue; }
263 assert (lit != pivot);
264 int tmp = val (lit);
265 if (tmp > 0) { satisfied = lit; break; }
266 else if (tmp < 0) continue;
267 else if ((tmp = marked (lit)) < 0) { tautological = lit; break; }
268 else if (!tmp) clause.push_back (lit), t++;
269 else assert (tmp > 0), t++;
270 }
271
272 unmark (c);
273 const int64_t size = clause.size ();
274
275 if (satisfied) {
276 LOG (d, "satisfied by %d antecedent", satisfied);
277 elim_update_removed_clause (eliminator, d, satisfied);
278 mark_garbage (d);
279 clause.clear ();
280 return false;
281 }
282
283 LOG (c, "first antecedent");
284 LOG (d, "second antecedent");
285
286 if (tautological) {
287 clause.clear ();
288 LOG ("resolvent tautological on %d", tautological);
289 return false;
290 }
291
292 if (!size) {
293 clause.clear ();
294 LOG ("empty resolvent");
295 learn_empty_clause ();
296 return false;
297 }
298
299 if (size == 1) {
300 int unit = clause[0];
301 LOG ("unit resolvent %d", unit);
302 clause.clear ();
303 assign_unit (unit);
304 elim_propagate (eliminator, unit);
305 return false;
306 }
307
308 LOG (clause, "resolvent");
309
310 // Double self-subsuming resolution. The clauses 'c' and 'd' are
311 // identical except for the pivot which occurs in different phase. The
312 // resolvent subsumes both antecedents.
313
314 if (s > size && t > size) {
315 assert (s == size + 1);
316 assert (t == size + 1);
317 clause.clear ();
318 elim_on_the_fly_self_subsumption (eliminator, c, pivot);
319 LOG (d, "double pivot %d on-the-fly self-subsuming resolution", -pivot);
320 stats.elimotfsub++;
321 stats.subsumed++;
322 elim_update_removed_clause (eliminator, d, -pivot);
323 mark_garbage (d);
324 return false;
325 }
326
327 // Single self-subsuming resolution: The pivot can be removed from 'c',
328 // which is implemented by adding a clause which is the same as 'c' but
329 // with 'pivot' removed and then marking 'c' as garbage.
330
331 if (s > size) {
332 assert (s == size + 1);
333 clause.clear ();
334 elim_on_the_fly_self_subsumption (eliminator, c, pivot);
335 return false;
336 }
337
338 // Same single self-subsuming resolution situation, but only for 'd'.
339
340 if (t > size) {
341 assert (t == size + 1);
342 clause.clear ();
343 elim_on_the_fly_self_subsumption (eliminator, d, -pivot);
344 return false;
345 }
346
347 return true;
348 }
349
350 /*------------------------------------------------------------------------*/
351
352 // Check whether the number of non-tautological resolvents on 'pivot' is
353 // smaller or equal to the number of clauses with 'pivot' or '-pivot'. This
354 // is the main criteria of bounded variable elimination. As a side effect
355 // it flushes garbage clauses with that variable, sorts its occurrence lists
356 // (smallest clauses first) and also negates pivot if it has more positive
357 // than negative occurrences.
358
359 bool
elim_resolvents_are_bounded(Eliminator & eliminator,int pivot)360 Internal::elim_resolvents_are_bounded (Eliminator & eliminator, int pivot)
361 {
362 const bool substitute = !eliminator.gates.empty ();
363 if (substitute) LOG ("trying to substitute %d", pivot);
364
365 stats.elimtried++;
366
367 assert (!unsat);
368 assert (active (pivot));
369
370 const Occs & ps = occs (pivot);
371 const Occs & ns = occs (-pivot);
372 const int64_t pos = ps.size ();
373 const int64_t neg = ns.size ();
374 if (!pos || !neg) return lim.elimbound >= 0;
375 const int64_t bound = pos + neg + lim.elimbound;
376
377 LOG ("checking number resolvents on %d bounded by %" PRId64 " = %" PRId64 " + %" PRId64 " + %d",
378 pivot, bound, pos, neg, lim.elimbound);
379
380 // Try all resolutions between a positive occurrence (outer loop) of
381 // 'pivot' and a negative occurrence of 'pivot' (inner loop) as long the
382 // bound on non-tautological resolvents is not hit and the size of the
383 // generated resolvents does not exceed the resolvent clause size limit.
384
385 int64_t resolvents = 0; // Non-tautological resolvents.
386
387 for (const auto & c : ps) {
388 assert (!c->redundant);
389 if (c->garbage) continue;
390 for (const auto & d : ns) {
391 assert (!d->redundant);
392 if (d->garbage) continue;
393 if (substitute && c->gate == d->gate) continue;
394 stats.elimrestried++;
395 if (resolve_clauses (eliminator, c, pivot, d)) {
396 resolvents++;
397 int size = clause.size ();
398 clause.clear ();
399 LOG ("now at least %" PRId64 " non-tautological resolvents on pivot %d",
400 resolvents, pivot);
401 if (size > opts.elimclslim) {
402 LOG ("resolvent size %d too big after %" PRId64 " resolvents on %d",
403 size, resolvents, pivot);
404 return false;
405 }
406 if (resolvents > bound) {
407 LOG ("too many non-tautological resolvents on %d", pivot);
408 return false;
409 }
410 } else if (unsat) return false;
411 else if (val (pivot)) return false;
412 }
413 }
414
415 LOG ("need %" PRId64 " <= %" PRId64 " non-tautological resolvents", resolvents, bound);
416
417 return true;
418 }
419
420 /*------------------------------------------------------------------------*/
421 // Add all resolvents on 'pivot' and connect them.
422
423 inline void
elim_add_resolvents(Eliminator & eliminator,int pivot)424 Internal::elim_add_resolvents (Eliminator & eliminator, int pivot) {
425
426 const bool substitute = !eliminator.gates.empty ();
427 if (substitute) {
428 LOG ("substituting pivot %d by resolving with %zd gate clauses",
429 pivot, eliminator.gates.size ());
430 stats.elimsubst++;
431 }
432
433 LOG ("adding all resolvents on %d", pivot);
434
435 assert (!val (pivot));
436 assert (!flags (pivot).eliminated ());
437
438 const Occs & ps = occs (pivot);
439 const Occs & ns = occs (-pivot);
440
441 int64_t resolvents = 0;
442
443 for (auto & c : ps) {
444 if (unsat) break;
445 if (c->garbage) continue;
446 for (auto & d : ns) {
447 if (unsat) break;
448 if (d->garbage) continue;
449 if (substitute && c->gate == d->gate) continue;
450 if (!resolve_clauses (eliminator, c, pivot, d)) continue;
451 assert (clause.size () <= (size_t) opts.elimclslim);
452 Clause * r = new_resolved_irredundant_clause ();
453 elim_update_added_clause (eliminator, r);
454 eliminator.enqueue (r);
455 clause.clear ();
456 resolvents++;
457
458 }
459 }
460
461 LOG ("added %" PRId64 " resolvents to eliminate %d", resolvents, pivot);
462 }
463
464 /*------------------------------------------------------------------------*/
465
466 // Remove clauses with 'pivot' and '-pivot' by marking them as garbage and
467 // push them on the extension stack.
468
469 void
mark_eliminated_clauses_as_garbage(Eliminator & eliminator,int pivot)470 Internal::mark_eliminated_clauses_as_garbage (Eliminator & eliminator,
471 int pivot)
472 {
473 assert (!unsat);
474
475 LOG ("marking irredundant clauses with %d as garbage", pivot);
476
477 const int64_t substitute = eliminator.gates.size ();
478 if (substitute)
479 LOG ("pushing %" PRId64 " gate clauses on extension stack", substitute);
480
481 int64_t pushed = 0;
482
483 Occs & ps = occs (pivot);
484 for (const auto & c : ps) {
485 if (c->garbage) continue;
486 mark_garbage (c);
487 assert (!c->redundant);
488 if (!substitute || c->gate) {
489 external->push_clause_on_extension_stack (c, pivot);
490 pushed++;
491 }
492 elim_update_removed_clause (eliminator, c, pivot);
493 }
494 erase_occs (ps);
495
496 LOG ("marking irredundant clauses with %d as garbage", -pivot);
497
498 Occs & ns = occs (-pivot);
499 for (const auto & d : ns) {
500 if (d->garbage) continue;
501 mark_garbage (d);
502 assert (!d->redundant);
503 if (!substitute || d->gate) {
504 external->push_clause_on_extension_stack (d, -pivot);
505 pushed++;
506 }
507 elim_update_removed_clause (eliminator, d, -pivot);
508 }
509 erase_occs (ns);
510
511 if (substitute) assert (pushed <= substitute);
512
513 // Unfortunately, we can not use the trick by Niklas Soerensson anymore,
514 // which avoids saving all clauses on the extension stack. This would
515 // break our new incremental 'restore' logic.
516 }
517
518 /*------------------------------------------------------------------------*/
519
520 // Try to eliminate 'pivot' by bounded variable elimination.
521
522 void
try_to_eliminate_variable(Eliminator & eliminator,int pivot)523 Internal::try_to_eliminate_variable (Eliminator & eliminator, int pivot) {
524
525 if (!active (pivot)) return;
526 assert (!frozen (pivot));
527
528 // First flush garbage clauses.
529 //
530 int64_t pos = flush_occs (pivot);
531 int64_t neg = flush_occs (-pivot);
532
533 if (pos > neg) { pivot = -pivot; swap (pos, neg); }
534 LOG ("pivot %d occurs positively %" PRId64 " times and negatively %" PRId64 " times",
535 pivot, pos, neg);
536 assert (!eliminator.schedule.contains (abs (pivot)));
537 assert (pos <= neg);
538
539 if (pos && neg > opts.elimocclim) {
540 LOG ("too many occurrences thus not eliminated %d", pivot);
541 assert (!eliminator.schedule.contains (abs (pivot)));
542 return;
543 }
544
545 LOG ("trying to eliminate %d", pivot);
546 assert (!flags (pivot).eliminated ());
547
548 // Sort occurrence lists, such that shorter clauses come first.
549 Occs & ps = occs (pivot);
550 stable_sort (ps.begin (), ps.end (), clause_smaller_size ());
551 Occs & ns = occs (-pivot);
552 stable_sort (ns.begin (), ns.end (), clause_smaller_size ());
553
554 if (pos) find_gate_clauses (eliminator, pivot);
555
556 if (!unsat && !val (pivot)) {
557 if (elim_resolvents_are_bounded (eliminator, pivot)) {
558 LOG ("number of resolvents on %d are bounded", pivot);
559 elim_add_resolvents (eliminator, pivot);
560 if (!unsat) mark_eliminated_clauses_as_garbage (eliminator, pivot);
561 if (active (pivot)) mark_eliminated (pivot);
562 } else LOG ("too many resolvents on %d so not eliminated", pivot);
563 }
564
565 unmark_gate_clauses (eliminator);
566 elim_backward_clauses (eliminator);
567 }
568
569 /*------------------------------------------------------------------------*/
570
571 void
mark_redundant_clauses_with_eliminated_variables_as_garbage()572 Internal::mark_redundant_clauses_with_eliminated_variables_as_garbage () {
573 for (const auto & c : clauses) {
574 if (c->garbage || !c->redundant) continue;
575 bool clean = true;
576 for (const auto & lit : *c) {
577 Flags & f = flags (lit);
578 if (f.eliminated ()) { clean = false; break; }
579 if (f.pure ()) { clean = false; break; }
580 }
581 if (!clean) mark_garbage (c);
582 }
583 }
584
585 /*------------------------------------------------------------------------*/
586
587 // Perform one round of bounded variable elimination and return 'false' if
588 // no variable was eliminated even though elimination ran to completion.
589 // Thus the result is 'false' iff elimination completed for this
590 // particular elimination bound (which will trigger its increase) and it is
591 // 'true' if at least one variable was eliminated or the resolution limit
592 // was hit and elimination did not run to completion.
593
elim_round()594 bool Internal::elim_round () {
595
596 assert (opts.elim);
597 assert (!unsat);
598
599 START_SIMPLIFIER (elim, ELIM);
600 stats.elimrounds++;
601
602 last.elim.marked = stats.mark.elim;
603 assert (!level);
604
605 int64_t resolution_limit;
606
607 if (opts.elimlimited) {
608 int64_t delta = stats.propagations.search;
609 delta *= 1e-3 * opts.elimreleff;
610 if (delta < opts.elimineff) delta = opts.elimineff;
611 if (delta > opts.elimaxeff) delta = opts.elimaxeff;
612 delta = max (delta, (int64_t) 2l * active ());
613
614 PHASE ("elim-round", stats.elimrounds,
615 "limit of %" PRId64 " resolutions", delta);
616
617 resolution_limit = stats.elimres + delta;
618 } else {
619 PHASE ("elim-round", stats.elimrounds,
620 "resolutions unlimited");
621 resolution_limit = LONG_MAX;
622 }
623
624 init_noccs ();
625
626 // First compute the number of occurrences of each literal and at the same
627 // time mark satisfied clauses and update 'elim' flags of variables in
628 // clauses with root level assigned literals (both false and true).
629 //
630 for (const auto & c : clauses) {
631 if (c->garbage || c->redundant) continue;
632 bool satisfied = false, falsified = false;
633 for (const auto & lit : *c) {
634 const int tmp = val (lit);
635 if (tmp > 0) satisfied = true;
636 else if (tmp < 0) falsified = true;
637 else assert (active (lit));
638 }
639 if (satisfied) mark_garbage (c); // more precise counts
640 else {
641 for (const auto & lit : *c) {
642 if (!active (lit)) continue;
643 if (falsified) mark_elim (lit); // simulate unit propagation
644 noccs (lit)++;
645 }
646 }
647 }
648
649 init_occs ();
650 Eliminator eliminator (this);
651 ElimSchedule & schedule = eliminator.schedule;
652
653 // Now find elimination candidates with small number of occurrences, which
654 // do not occur in too large clauses but do occur in clauses which have
655 // been removed since the last time we ran bounded variable elimination,
656 // which in turned triggered their 'elim' bit to be set.
657 //
658 for (int idx = 1; idx <= max_var; idx++) {
659 if (!active (idx)) continue;
660 if (frozen (idx)) continue;
661 if (!flags (idx).elim) continue;
662 flags (idx).elim = false;
663 LOG ("scheduling %d for elimination initially", idx);
664 schedule.push_back (idx);
665 }
666
667 schedule.shrink ();
668
669 #ifndef QUIET
670 int64_t scheduled = schedule.size ();
671 #endif
672
673 PHASE ("elim-round", stats.elimrounds,
674 "scheduled %" PRId64 " variables %.0f%% for elimination",
675 scheduled, percent (scheduled, active ()));
676
677 // Connect irredundant clauses.
678 //
679 for (const auto & c : clauses)
680 if (!c->garbage && !c->redundant)
681 for (const auto & lit : *c)
682 if (active (lit))
683 occs (lit).push_back (c);
684
685 #ifndef QUIET
686 const int64_t old_resolutions = stats.elimres;
687 #endif
688 const int old_eliminated = stats.all.eliminated;
689 const int old_fixed = stats.all.fixed;
690
691 // Limit on garbage bytes during variable elimination. If the limit is hit
692 // a garbage collection is performed.
693 //
694 const int64_t garbage_limit = (2*stats.irrbytes/3) + (1<<20);
695
696 // Try eliminating variables according to the schedule.
697 //
698 #ifndef QUIET
699 int64_t tried = 0;
700 #endif
701 while (!unsat &&
702 !terminating () &&
703 stats.elimres <= resolution_limit &&
704 !schedule.empty ()) {
705 int idx = schedule.front ();
706 schedule.pop_front ();
707 flags (idx).elim = false;
708 try_to_eliminate_variable (eliminator, idx);
709 #ifndef QUIET
710 tried++;
711 #endif
712 if (stats.garbage <= garbage_limit) continue;
713 mark_redundant_clauses_with_eliminated_variables_as_garbage ();
714 garbage_collection ();
715 }
716
717 const int64_t remain = schedule.size ();
718 const bool completed = !remain;
719
720 PHASE ("elim-round", stats.elimrounds,
721 "tried to eliminate %" PRId64 " variables %.0f%% (%" PRId64 " remain)",
722 tried, percent (tried, scheduled), remain);
723
724 schedule.erase ();
725
726 // Collect potential literal clause instantiation pairs, which needs full
727 // occurrence lists and thus we have it here before resetting them.
728 //
729 Instantiator instantiator;
730 if (!unsat &&
731 !terminating () &&
732 opts.instantiate)
733 collect_instantiation_candidates (instantiator);
734
735 reset_occs ();
736 reset_noccs ();
737
738 // Mark all redundant clauses with eliminated variables as garbage.
739 //
740 if (!unsat)
741 mark_redundant_clauses_with_eliminated_variables_as_garbage ();
742
743 int eliminated = stats.all.eliminated - old_eliminated;
744 #ifndef QUIET
745 int64_t resolutions = stats.elimres - old_resolutions;
746 PHASE ("elim-round", stats.elimrounds,
747 "eliminated %" PRId64 " variables %.0f%% in %" PRId64 " resolutions",
748 eliminated, percent (eliminated, scheduled), resolutions);
749 #endif
750
751 last.elim.subsumephases = stats.subsumephases;
752 const int units = stats.all.fixed - old_fixed;
753 report ('e', !opts.reportall && !(eliminated + units));
754 STOP_SIMPLIFIER (elim, ELIM);
755
756 if (!unsat &&
757 !terminating () &&
758 instantiator) // Do we have candidate pairs?
759 instantiate (instantiator);
760
761 return !completed || eliminated;
762 }
763
764 /*------------------------------------------------------------------------*/
765
766 // Increase elimination bound (additional clauses allowed during variable
767 // elimination), which is triggered if elimination with last bound completed
768 // (including no new subsumptions).
769
increase_elimination_bound()770 void Internal::increase_elimination_bound () {
771
772 if (lim.elimbound >= opts.elimboundmax) return;
773
774 if (lim.elimbound < 0) lim.elimbound = 0;
775 else if (!lim.elimbound) lim.elimbound = 1;
776 else lim.elimbound *= 2;
777
778 if (lim.elimbound > opts.elimboundmax)
779 lim.elimbound = opts.elimboundmax;
780
781 PHASE ("elim-phase", stats.elimphases,
782 "new elimination bound %" PRId64 "", lim.elimbound);
783
784 // Now reschedule all active variables for elimination again.
785 //
786 int count = 0;
787 for (int idx = 1; idx <= max_var; idx++) {
788 if (!active (idx)) continue;
789 if (flags (idx).elim) continue;
790 mark_elim (idx);
791 count++;
792 }
793 LOG ("marked %d variables as elimination candidates", count);
794 }
795
796 /*------------------------------------------------------------------------*/
797
elim(bool update_limits)798 void Internal::elim (bool update_limits) {
799
800 if (unsat) return;
801 if (level) backtrack ();
802 if (!propagate ()) { learn_empty_clause (); return; }
803
804 stats.elimphases++;
805
806 #ifndef QUIET
807 int old_eliminated = stats.all.eliminated;
808 int old_active_variables = active ();
809 #endif
810
811 // Make sure there was a complete subsumption phase since last
812 // elimination including vivification etc.
813 //
814 if (last.elim.subsumephases == stats.subsumephases)
815 subsume (update_limits);
816
817 reset_watches (); // saves lots of memory
818
819 // Alternate blocked clause elimination, variable elimination and
820 // subsumption, blocked and covered clause elimination until nothing
821 // changes or the round limit is hit.
822 //
823 bool completed = false, blocked = false, covered = false;
824 int round = 1;
825
826 while (!unsat && !terminating ()) {
827
828 if (elim_round ()) { // Elimination successful or limit hit.
829
830 blocked = covered = false; // Enable again.
831
832 if (round++ >= opts.elimrounds) break;
833
834 if (subsume_round ()) continue; // New elimination candidates.
835
836 } else { // Completed but nothing eliminated.
837
838 completed = true; // Triggers elimination bound increase.
839
840 if (round++ >= opts.elimrounds) break;
841 }
842
843 if (!blocked) {
844 blocked = true; // Only once per failed elimination
845 if (block ()) continue; // At least one blocked clause.
846 }
847
848 if (!covered) {
849 covered = true; // Only once per failed elimination
850 if (cover ()) continue; // At least one covered clause.
851 }
852
853 // Was not able to generate new variable elimination candidates after
854 // variable elimination round, neither through subsumption, nor blocked,
855 // nor covered clause elimination.
856 //
857 break;
858 }
859
860 if (completed) {
861 stats.elimcompleted++;
862 PHASE ("elim-phase", stats.elimphases,
863 "fully completed elimination %" PRId64 " at elimination bound %" PRId64 "",
864 stats.elimcompleted, lim.elimbound);
865 } else {
866 PHASE ("elim-phase", stats.elimphases,
867 "incomplete elimination %" PRId64 " at elimination bound %" PRId64 "",
868 stats.elimcompleted + 1, lim.elimbound);
869 }
870
871 init_watches ();
872 connect_watches ();
873
874 if (unsat) LOG ("elimination derived empty clause");
875 else if (propagated < trail.size ()) {
876 LOG ("elimination produced %" PRId64 " units", trail.size () - propagated);
877 if (!propagate ()) {
878 LOG ("propagating units after elimination results in empty clause");
879 learn_empty_clause ();
880 }
881 }
882
883 #ifndef QUIET
884 int eliminated = stats.all.eliminated - old_eliminated;
885 PHASE ("elim-phase", stats.elimphases,
886 "eliminated %d variables %.2f%%",
887 eliminated, percent (eliminated, old_active_variables));
888 #endif
889
890 if (completed) increase_elimination_bound ();
891
892 if (!update_limits) return;
893
894 int64_t delta = scale (opts.elimint * (stats.elimphases + 1));
895 lim.elim = stats.conflicts + delta;
896
897 PHASE ("elim-phase", stats.elimphases,
898 "new limit at %" PRId64 " conflicts after %" PRId64 " conflicts", lim.elim, delta);
899
900 last.elim.fixed = stats.all.fixed;
901 }
902
903 }
904