26#include "absl/container/flat_hash_map.h"
27#include "absl/container/inlined_vector.h"
28#include "absl/log/check.h"
29#include "absl/numeric/int128.h"
30#include "absl/strings/str_cat.h"
31#include "absl/types/span.h"
48 CHECK_GE(n, pos_.size());
50 tmp_positions_.resize(n, 0);
53 if (n + 1 < queue_.size())
return;
54 const int old_size = queue_.size();
55 queue_.resize(n + 1, 0);
56 queue_.resize(queue_.capacity(), 0);
60 const int diff = queue_.size() - old_size;
61 for (
int i = old_size - 1;
i >= left_; --
i) {
62 pos_[queue_[
i]] =
i + diff;
63 queue_[
i + diff] = queue_[
i];
71 const int id = queue_[left_];
74 if (left_ == queue_.size()) left_ = 0;
80 DCHECK_LE(
id, pos_.size());
85 if (right_ == queue_.size()) right_ = 0;
89 if (order.size() <= 1)
return;
91 const int capacity = queue_.size();
92 const int size = left_ < right_ ? right_ - left_ : left_ + capacity - right_;
93 if (order.size() > size / 8) {
98 for (
const int id : order) {
99 const int p = pos_[id];
101 tmp_positions_[
index++] = p >= left_ ? p : p + capacity;
103 std::sort(&tmp_positions_[0], &tmp_positions_[
index]);
104 DCHECK(std::unique(&tmp_positions_[0], &tmp_positions_[
index]) ==
105 &tmp_positions_[
index]);
108 for (
const int id : order) {
109 int p = tmp_positions_[
index++];
110 if (p >= capacity) p -= capacity;
117 for (
const int id : order) {
118 DCHECK_GE(pos_[
id], 0);
119 queue_[pos_[id]] = -1;
122 if (left_ <= right_) {
123 for (
int i = left_;
i < right_; ++
i) {
124 if (queue_[
i] == -1) {
125 queue_[
i] = order[order_index++];
130 const int size = queue_.size();
131 for (
int i = left_;
i < size; ++
i) {
132 if (queue_[
i] == -1) {
133 queue_[
i] = order[order_index++];
137 for (
int i = 0;
i < left_; ++
i) {
138 if (queue_[
i] == -1) {
139 queue_[
i] = order[order_index++];
144 DCHECK_EQ(order_index, order.size());
148 std::sort(elements.begin(), elements.end(),
149 [
this](
const int id1,
const int id2) {
150 const int p1 = pos_[id1];
151 const int p2 = pos_[id2];
153 if (p2 >= left_) return p1 < p2;
157 if (p2 < left_) return p1 < p2;
165 case EnforcementStatus::IS_FALSE:
168 case EnforcementStatus::CANNOT_PROPAGATE:
169 os <<
"CANNOT_PROPAGATE";
171 case EnforcementStatus::CAN_PROPAGATE:
172 os <<
"CAN_PROPAGATE";
174 case EnforcementStatus::IS_ENFORCED:
199 if (
literal.Index() >=
static_cast<int>(watcher_.
size()))
continue;
202 auto& watch_list = watcher_[
literal.Index()];
203 for (
const EnforcementId
id : watch_list) {
204 const LiteralIndex
index = ProcessIdOnTrue(
literal,
id);
207 watch_list[new_size++] = id;
214 watch_list.resize(new_size);
217 for (
const EnforcementId
id : watcher_[
literal.NegatedIndex()]) {
221 rev_stack_size_ =
static_cast<int>(untrail_stack_.size());
227 const int size =
static_cast<int>(untrail_stack_.size());
228 for (
int i = size - 1;
i >= rev_stack_size_; --
i) {
229 const auto [id,
status] = untrail_stack_[
i];
231 if (callbacks_[
id] !=
nullptr) callbacks_[id](
status);
233 untrail_stack_.resize(rev_stack_size_);
243 absl::Span<const Literal> enforcement,
247 bool is_always_false =
false;
248 temp_literals_.clear();
250 for (
const Literal l : enforcement) {
252 const int size = std::max(l.Index().value(), l.NegatedIndex().value()) + 1;
253 if (size >
static_cast<int>(watcher_.
size())) {
257 if (level == 0 || trail_.
Info(l.Variable()).
level == 0)
continue;
260 if (level == 0 || trail_.
Info(l.Variable()).
level == 0) {
261 is_always_false =
true;
266 temp_literals_.push_back(l);
271 if (is_always_false) {
273 return EnforcementId(-1);
275 if (temp_literals_.empty()) {
277 return EnforcementId(-1);
280 const EnforcementId id(
static_cast<int>(callbacks_.
size()));
283 CHECK(!temp_literals_.empty());
284 buffer_.insert(buffer_.end(), temp_literals_.begin(), temp_literals_.end());
288 statuses_.
push_back(temp_literals_.size() == 1
292 if (temp_literals_.size() == 1) {
293 watcher_[temp_literals_[0].Index()].
push_back(
id);
296 const auto span = GetSpan(
id);
297 int num_not_true = 0;
298 for (
int i = 0;
i < span.size(); ++
i) {
300 std::swap(span[num_not_true], span[
i]);
302 if (num_not_true == 2)
break;
306 if (num_not_true == 1) {
307 int max_level = trail_.
Info(span[1].Variable()).
level;
308 for (
int i = 2;
i < span.size(); ++
i) {
309 const int level = trail_.
Info(span[
i].Variable()).
level;
310 if (level > max_level) {
312 std::swap(span[1], span[
i]);
325 }
else if (num_true == temp_literals_.size()) {
327 }
else if (num_true + 1 == temp_literals_.size()) {
330 if (temp_literals_.size() == 1) {
331 if (callbacks_[
id] !=
nullptr) {
341 EnforcementId
id, std::vector<Literal>* reason)
const {
342 for (
const Literal l : GetSpan(
id)) {
343 reason->push_back(l.Negated());
350 EnforcementId
id, absl::Span<const Literal> literal_reason,
351 absl::Span<const IntegerLiteral> integer_reason) {
352 temp_reason_.clear();
354 for (
const Literal l : GetSpan(
id)) {
357 temp_reason_.push_back(l.Negated());
361 unique_unassigned = l.Index();
364 temp_reason_.insert(temp_reason_.end(), literal_reason.begin(),
365 literal_reason.end());
367 return integer_trail_->
ReportConflict(temp_reason_, integer_reason);
371 temp_reason_, integer_reason);
375absl::Span<Literal> EnforcementPropagator::GetSpan(EnforcementId
id) {
376 if (
id < 0)
return {};
377 DCHECK_LE(
id + 1, starts_.
size());
378 const int size = starts_[
id + 1] - starts_[id];
380 return absl::MakeSpan(&buffer_[starts_[
id]], size);
383absl::Span<const Literal> EnforcementPropagator::GetSpan(
384 EnforcementId
id)
const {
385 if (
id < 0)
return {};
386 DCHECK_LE(
id + 1, starts_.
size());
387 const int size = starts_[
id + 1] - starts_[id];
389 return absl::MakeSpan(&buffer_[starts_[
id]], size);
392LiteralIndex EnforcementPropagator::ProcessIdOnTrue(Literal watched,
397 const auto span = GetSpan(
id);
398 if (span.size() == 1) {
404 const int watched_pos = (span[0] == watched) ? 0 : 1;
405 CHECK_EQ(span[watched_pos], watched);
411 for (
int i = 2;
i < span.size(); ++
i) {
412 const Literal l = span[
i];
420 std::swap(span[watched_pos], span[
i]);
421 return span[watched_pos].Index();
438void EnforcementPropagator::ChangeStatus(EnforcementId
id,
441 if (old_status == new_status)
return;
443 untrail_stack_.push_back({id, old_status});
445 statuses_[id] = new_status;
446 if (callbacks_[
id] !=
nullptr) callbacks_[id](new_status);
453 for (
const Literal l : GetSpan(
id)) {
459 const int size = GetSpan(
id).size();
472 rev_integer_value_repository_(
475 watcher_id_(watcher_->Register(this)) {
487 if (!VLOG_IS_ON(1))
return;
488 if (shared_stats_ ==
nullptr)
return;
489 std::vector<std::pair<std::string, int64_t>>
stats;
490 stats.push_back({
"linear_propag/num_pushes", num_pushes_});
492 {
"linear_propag/num_enforcement_pushes", num_enforcement_pushes_});
493 stats.push_back({
"linear_propag/num_simple_cycles", num_simple_cycles_});
494 stats.push_back({
"linear_propag/num_complex_cycles", num_complex_cycles_});
495 stats.push_back({
"linear_propag/num_scanned", num_scanned_});
496 stats.push_back({
"linear_propag/num_extra_scan", num_extra_scans_});
497 stats.push_back({
"linear_propag/num_explored_in_disassemble",
498 num_explored_in_disassemble_});
499 stats.push_back({
"linear_propag/num_bool_aborts", num_bool_aborts_});
500 stats.push_back({
"linear_propag/num_ignored", num_ignored_});
501 stats.push_back({
"linear_propag/num_reordered", num_reordered_});
506 if (level < previous_level_) {
510 while (!propagation_queue_.
empty()) {
511 in_queue_[propagation_queue_.
Pop()] =
false;
513 for (
int i = rev_unenforced_size_;
i < unenforced_constraints_.size();
515 in_queue_[unenforced_constraints_[
i]] =
false;
517 unenforced_constraints_.resize(rev_unenforced_size_);
518 }
else if (level > previous_level_) {
519 rev_unenforced_size_ = unenforced_constraints_.size();
520 rev_int_repository_->
SaveState(&rev_unenforced_size_);
522 previous_level_ = level;
528 if (!propagation_queue_.
empty()) {
539 if (
var >= var_to_constraint_ids_.
size())
continue;
540 SetPropagatedBy(
var, -1);
541 AddWatchedToQueue(
var);
552 const int saved_index = trail_->
Index();
553 while (!propagation_queue_.
empty()) {
554 const int id = propagation_queue_.
Pop();
555 in_queue_[id] =
false;
556 if (!PropagateOneConstraint(
id)) {
561 if (trail_->
Index() > saved_index) {
574 absl::Span<const Literal> enforcement_literals,
575 absl::Span<const IntegerVariable> vars,
576 absl::Span<const IntegerValue> coeffs, IntegerValue
upper_bound) {
577 if (vars.empty())
return true;
579 for (
const Literal l : enforcement_literals) {
586 CHECK_LT(vars.size(), 1 << 29);
587 if (vars.size() > max_variations_.size()) {
588 max_variations_.resize(vars.size(), 0);
589 buffer_of_ones_.resize(vars.size(), IntegerValue(1));
593 CHECK_EQ(vars.size(), coeffs.size());
594 const int id = infos_.size();
597 info.all_coeffs_are_one =
false;
598 info.start = variables_buffer_.size();
599 info.initial_size = vars.size();
601 info.rev_size = vars.size();
602 infos_.push_back(std::move(info));
605 id_to_propagation_count_.push_back(0);
606 variables_buffer_.insert(variables_buffer_.end(), vars.begin(), vars.end());
607 coeffs_buffer_.insert(coeffs_buffer_.end(), coeffs.begin(), coeffs.end());
608 CanonicalizeConstraint(
id);
610 bool all_at_one =
true;
611 for (
const IntegerValue coeff : GetCoeffs(infos_.back())) {
620 infos_.back().all_coeffs_are_one =
true;
625 in_queue_.push_back(
false);
628 if (!enforcement_literals.empty()) {
629 infos_.back().enf_status =
631 infos_.back().enf_id = enforcement_propagator_->
Register(
633 infos_[id].enf_status =
static_cast<int>(
status);
639 AddToQueueIfNeeded(
id);
644 AddToQueueIfNeeded(
id);
645 infos_.back().enf_id = -1;
649 for (
const IntegerVariable
var : GetVariables(infos_[
id])) {
651 if (
var >= var_to_constraint_ids_.
size()) {
654 var_to_constraint_ids_.
resize(size);
655 propagated_by_.
resize(size, -1);
656 propagated_by_was_set_.
Resize(IntegerVariable(size));
657 is_watched_.
resize(size,
false);
667 if (!is_watched_[
var]) {
668 is_watched_[
var] =
true;
674 return PropagateOneConstraint(
id);
677absl::Span<IntegerValue> LinearPropagator::GetCoeffs(
678 const ConstraintInfo& info) {
679 if (info.all_coeffs_are_one) {
680 return absl::MakeSpan(&buffer_of_ones_[0], info.initial_size);
682 return absl::MakeSpan(&coeffs_buffer_[info.start], info.initial_size);
685absl::Span<IntegerVariable> LinearPropagator::GetVariables(
686 const ConstraintInfo& info) {
687 return absl::MakeSpan(&variables_buffer_[info.start], info.initial_size);
690void LinearPropagator::CanonicalizeConstraint(
int id) {
691 const ConstraintInfo& info = infos_[id];
692 auto coeffs = GetCoeffs(info);
693 auto vars = GetVariables(info);
694 for (
int i = 0;
i < vars.size(); ++
i) {
696 coeffs[
i] = -coeffs[
i];
703bool LinearPropagator::PropagateOneConstraint(
int id) {
708 if (id_scanned_at_least_once_[
id]) {
711 id_scanned_at_least_once_.
Set(
id);
716 ConstraintInfo& info = infos_[id];
718 DCHECK_EQ(enf_status, enforcement_propagator_->
DebugStatus(info.enf_id));
721 DCHECK(!in_queue_[
id]);
725 in_queue_[id] =
true;
726 unenforced_constraints_.push_back(
id);
734 IntegerValue implied_lb(0);
735 auto vars = GetVariables(info);
736 auto coeffs = GetCoeffs(info);
737 IntegerValue max_variation(0);
738 bool first_change =
true;
741 for (
int i = 0;
i < info.rev_size;) {
742 const IntegerVariable
var = vars[
i];
743 const IntegerValue coeff = coeffs[
i];
750 rev_int_repository_->
SaveState(&info.rev_size);
751 rev_integer_value_repository_->
SaveState(&info.rev_rhs);
752 first_change =
false;
755 std::swap(vars[
i], vars[info.rev_size]);
756 std::swap(coeffs[
i], coeffs[info.rev_size]);
757 info.rev_rhs -= coeff * lb;
759 implied_lb += coeff * lb;
760 max_variations_[
i] = (ub - lb) * coeff;
761 max_variation = std::max(max_variation, max_variations_[
i]);
765 const IntegerValue slack = info.rev_rhs - implied_lb;
768 if (max_variation <= slack)
return true;
771 integer_reason_.clear();
772 reason_coeffs_.clear();
773 for (
int i = 0;
i < info.initial_size; ++
i) {
774 const IntegerVariable
var = vars[
i];
777 reason_coeffs_.push_back(coeffs[
i]);
784 ++num_enforcement_pushes_;
797 for (
int i = 0;
i < info.rev_size; ++
i) {
798 if (max_variations_[
i] <= slack)
continue;
803 const IntegerVariable
var = vars[
i];
804 const IntegerValue coeff = coeffs[
i];
805 const IntegerValue div = slack / coeff;
806 const IntegerValue new_ub = integer_trail_->
LowerBound(
var) + div;
807 const IntegerValue propagation_slack = (div + 1) * coeff - slack - 1;
810 [
this, info, propagation_slack](
811 IntegerLiteral i_lit,
int trail_index,
812 std::vector<Literal>* literal_reason,
813 std::vector<int>* trail_indices_reason) {
814 literal_reason->clear();
815 trail_indices_reason->clear();
816 enforcement_propagator_->AddEnforcementReason(info.enf_id,
818 reason_coeffs_.clear();
820 auto coeffs = GetCoeffs(info);
821 auto vars = GetVariables(info);
822 for (int i = 0; i < info.initial_size; ++i) {
823 const IntegerVariable var = vars[i];
824 if (PositiveVariable(var) == PositiveVariable(i_lit.var)) {
828 integer_trail_->FindTrailIndexOfVarBefore(var, trail_index);
830 trail_indices_reason->push_back(index);
831 if (propagation_slack > 0) {
832 reason_coeffs_.push_back(coeffs[i]);
836 if (propagation_slack > 0) {
838 propagation_slack, reason_coeffs_, trail_indices_reason);
845 const IntegerValue actual_ub = integer_trail_->
UpperBound(
var);
847 if (actual_ub < new_ub) {
849 SetPropagatedBy(next_var, -1);
850 AddWatchedToQueue(next_var);
851 }
else if (actual_ub == new_ub) {
852 SetPropagatedBy(next_var,
id);
853 AddWatchedToQueue(next_var);
856 std::swap(vars[
i], vars[num_pushed]);
857 std::swap(coeffs[
i], coeffs[num_pushed]);
863 if (num_pushed > 0) {
864 if (!DisassembleSubtree(
id, num_pushed)) {
873std::string LinearPropagator::ConstraintDebugString(
int id) {
875 const ConstraintInfo& info = infos_[id];
876 auto coeffs = GetCoeffs(info);
877 auto vars = GetVariables(info);
878 IntegerValue implied_lb(0);
879 IntegerValue rhs_correction(0);
880 for (
int i = 0;
i < info.initial_size; ++
i) {
881 const IntegerValue term = coeffs[
i] * integer_trail_->LowerBound(vars[i]);
882 if (i >= info.rev_size) {
883 rhs_correction += term;
886 absl::StrAppend(&result,
" +", coeffs[i].
value(),
"*X", vars[i].
value());
888 const IntegerValue original_rhs = info.rev_rhs + rhs_correction;
889 absl::StrAppend(&result,
" <= ", original_rhs.value(),
890 " slack=", original_rhs.value() - implied_lb.value());
891 absl::StrAppend(&result,
" enf=", info.enf_status);
895bool LinearPropagator::ReportConflictingCycle() {
903 literal_reason_.clear();
904 integer_reason_.clear();
905 absl::int128 rhs_sum = 0;
906 absl::flat_hash_map<IntegerVariable, absl::int128> map_sum;
907 for (
const auto [
id, next_var] : disassemble_branch_) {
908 const ConstraintInfo& info = infos_[id];
909 enforcement_propagator_->AddEnforcementReason(info.enf_id,
911 auto coeffs = GetCoeffs(info);
912 auto vars = GetVariables(info);
913 IntegerValue rhs_correction(0);
914 for (
int i = 0;
i < info.initial_size; ++
i) {
915 if (i >= info.rev_size) {
916 rhs_correction += coeffs[
i] * integer_trail_->LowerBound(vars[i]);
919 map_sum[vars[
i]] += coeffs[
i].value();
924 rhs_sum += (info.rev_rhs + rhs_correction).
value();
929 absl::int128 implied_lb = 0;
930 for (
const auto [
var, coeff] : map_sum) {
932 if (!integer_trail_->VariableLowerBoundIsFromLevelZero(
var)) {
933 integer_reason_.push_back(integer_trail_->LowerBoundAsLiteral(
var));
936 coeff * absl::int128{integer_trail_->LowerBound(
var).value()};
937 }
else if (coeff < 0) {
938 if (!integer_trail_->VariableLowerBoundIsFromLevelZero(
940 integer_reason_.push_back(integer_trail_->UpperBoundAsLiteral(
var));
943 coeff * absl::int128{integer_trail_->UpperBound(
var).value()};
946 if (implied_lb > rhs_sum) {
948 std::sort(integer_reason_.begin(), integer_reason_.end(),
949 [](
const IntegerLiteral&
a,
const IntegerLiteral&
b) {
950 return a.var < b.var;
954 const absl::int128 limit{std::numeric_limits<int64_t>::max()};
955 const absl::int128 slack = implied_lb - rhs_sum;
957 reason_coeffs_.clear();
959 for (
const IntegerLiteral i_lit : integer_reason_) {
966 reason_coeffs_.push_back(
static_cast<int64_t
>(c));
969 const IntegerValue slack64(
970 static_cast<int64_t
>(std::min(limit, slack)));
971 integer_trail_->RelaxLinearReason(slack64 - 1, reason_coeffs_,
976 ++num_simple_cycles_;
977 VLOG(2) <<
"Simplified " << integer_reason_.size() <<
" slack "
978 << implied_lb - rhs_sum;
979 return integer_trail_->ReportConflict(literal_reason_, integer_reason_);
988 literal_reason_.clear();
989 integer_reason_.clear();
991 for (
const auto [
id, next_var] : disassemble_branch_) {
992 const ConstraintInfo& info = infos_[id];
993 enforcement_propagator_->AddEnforcementReason(info.enf_id,
995 for (
const IntegerVariable
var : GetVariables(infos_[id])) {
998 if (
var == previous_var)
continue;
1003 if (!integer_trail_->VariableLowerBoundIsFromLevelZero(
var)) {
1004 integer_reason_.push_back(integer_trail_->LowerBoundAsLiteral(
var));
1007 previous_var = next_var;
1009 VLOG(2) << next_var <<
" [" << integer_trail_->LowerBound(next_var) <<
","
1010 << integer_trail_->UpperBound(next_var)
1011 <<
"] : " << ConstraintDebugString(
id);
1013 ++num_complex_cycles_;
1014 return integer_trail_->ReportConflict(literal_reason_, integer_reason_);
1023bool LinearPropagator::DisassembleSubtree(
int root_id,
int num_pushed) {
1024 disassemble_to_reorder_.ClearAndResize(in_queue_.size());
1025 disassemble_reverse_topo_order_.clear();
1032 disassemble_queue_.clear();
1033 disassemble_branch_.clear();
1035 const ConstraintInfo& info = infos_[root_id];
1036 auto vars = GetVariables(info);
1037 for (
int i = 0;
i < num_pushed; ++
i) {
1038 disassemble_queue_.push_back({root_id,
NegationOf(vars[i])});
1044 while (!disassemble_queue_.empty()) {
1045 const auto [prev_id,
var] = disassemble_queue_.back();
1046 if (!disassemble_branch_.empty() &&
1047 disassemble_branch_.back().first == prev_id &&
1048 disassemble_branch_.back().second ==
var) {
1049 disassemble_branch_.pop_back();
1050 disassemble_reverse_topo_order_.push_back(prev_id);
1051 disassemble_queue_.pop_back();
1055 disassemble_branch_.push_back({prev_id,
var});
1056 time_limit_->AdvanceDeterministicTime(
1057 static_cast<double>(var_to_constraint_ids_[
var].size()) * 1e-9);
1058 for (
const int id : var_to_constraint_ids_[
var]) {
1059 if (prev_id == root_id) {
1062 DCHECK_NE(
id, root_id);
1063 if (disassemble_to_reorder_[
id])
continue;
1064 disassemble_to_reorder_.Set(
id);
1065 }
else if (
id == root_id) {
1069 CHECK(!disassemble_branch_.empty());
1072 const IntegerVariable root_var = disassemble_branch_[0].second;
1073 CHECK_EQ(disassemble_branch_[0].first, root_id);
1074 CHECK_NE(
var, root_var);
1083 const ConstraintInfo& info = infos_[id];
1084 auto coeffs = GetCoeffs(info);
1085 auto vars = GetVariables(info);
1086 IntegerValue root_coeff(0);
1087 IntegerValue var_coeff(0);
1088 for (
int i = 0;
i < info.initial_size; ++
i) {
1089 if (vars[i] ==
var) var_coeff = coeffs[
i];
1090 if (vars[i] ==
NegationOf(root_var)) root_coeff = coeffs[
i];
1092 CHECK_NE(root_coeff, 0);
1093 CHECK_NE(var_coeff, 0);
1094 if (var_coeff >= root_coeff) {
1095 return ReportConflictingCycle();
1102 if (id_to_propagation_count_[
id] == 0)
continue;
1103 disassemble_to_reorder_.Set(
id);
1108 const ConstraintInfo& info = infos_[id];
1109 auto coeffs = GetCoeffs(info);
1110 auto vars = GetVariables(info);
1111 IntegerValue var_coeff(0);
1112 disassemble_candidates_.clear();
1113 ++num_explored_in_disassemble_;
1114 time_limit_->AdvanceDeterministicTime(
static_cast<double>(info.rev_size) *
1116 for (
int i = 0;
i < info.rev_size; ++
i) {
1117 if (vars[i] ==
var) {
1118 var_coeff = coeffs[
i];
1121 const IntegerVariable next_var =
NegationOf(vars[i]);
1122 if (propagated_by_[next_var] ==
id) {
1123 disassemble_candidates_.push_back({next_var, coeffs[
i]});
1126 propagated_by_[next_var] = -1;
1127 id_to_propagation_count_[id]--;
1130 for (
const auto [next_var, coeff] : disassemble_candidates_) {
1131 if (coeff <= var_coeff) {
1137 disassemble_queue_.push_back({id, next_var});
1143 CHECK(!disassemble_to_reorder_[root_id]);
1144 tmp_to_reorder_.clear();
1145 std::reverse(disassemble_reverse_topo_order_.begin(),
1146 disassemble_reverse_topo_order_.end());
1147 for (
const int id : disassemble_reverse_topo_order_) {
1148 if (!disassemble_to_reorder_[
id])
continue;
1149 disassemble_to_reorder_.Clear(
id);
1150 AddToQueueIfNeeded(
id);
1151 if (!propagation_queue_.Contains(
id))
continue;
1152 tmp_to_reorder_.push_back(
id);
1158 if (tmp_to_reorder_.empty())
return true;
1159 const int important_size =
static_cast<int>(tmp_to_reorder_.size());
1161 for (
const int id : disassemble_to_reorder_.PositionsSetAtLeastOnce()) {
1162 if (!disassemble_to_reorder_[
id])
continue;
1163 disassemble_to_reorder_.Clear(
id);
1164 if (!propagation_queue_.Contains(
id))
continue;
1165 tmp_to_reorder_.push_back(
id);
1167 disassemble_to_reorder_.NotifyAllClear();
1171 if (important_size < tmp_to_reorder_.size()) {
1172 propagation_queue_.SortByPos(
1173 absl::MakeSpan(&tmp_to_reorder_[important_size],
1174 tmp_to_reorder_.size() - important_size));
1177 num_reordered_ += tmp_to_reorder_.size();
1178 propagation_queue_.Reorder(tmp_to_reorder_);
1182void LinearPropagator::AddToQueueIfNeeded(
int id) {
1183 DCHECK_LT(
id, in_queue_.size());
1184 DCHECK_LT(
id, infos_.size());
1186 if (in_queue_[
id])
return;
1187 in_queue_[id] =
true;
1188 propagation_queue_.Push(
id);
1191void LinearPropagator::AddWatchedToQueue(IntegerVariable
var) {
1192 if (
var >=
static_cast<int>(var_to_constraint_ids_.size()))
return;
1193 time_limit_->AdvanceDeterministicTime(
1194 static_cast<double>(var_to_constraint_ids_[
var].size()) * 1e-9);
1195 for (
const int id : var_to_constraint_ids_[
var]) {
1196 AddToQueueIfNeeded(
id);
1200void LinearPropagator::SetPropagatedBy(IntegerVariable
var,
int id) {
1201 int& ref_id = propagated_by_[
var];
1202 if (ref_id ==
id)
return;
1204 propagated_by_was_set_.Set(
var);
1207 DCHECK_LT(
var, propagated_by_.size());
1209 DCHECK_GE(ref_id, 0);
1210 DCHECK_LT(ref_id, id_to_propagation_count_.size());
1211 id_to_propagation_count_[ref_id]--;
1214 if (
id != -1) id_to_propagation_count_[id]++;
1217void LinearPropagator::ClearPropagatedBy() {
1220 for (
const IntegerVariable
var :
1221 propagated_by_was_set_.PositionsSetAtLeastOnce()) {
1222 int&
id = propagated_by_[
var];
1223 if (
id != -1) --id_to_propagation_count_[id];
1224 propagated_by_[
var] = -1;
1226 propagated_by_was_set_.ClearAndResize(propagated_by_was_set_.size());
1227 DCHECK(std::all_of(propagated_by_.begin(), propagated_by_.end(),
1228 [](
int id) { return id == -1; }));
1229 DCHECK(std::all_of(id_to_propagation_count_.begin(),
1230 id_to_propagation_count_.end(),
1231 [](
int count) { return count == 0; }));
void push_back(const value_type &x)
void resize(size_type new_size)
void SaveStateWithStamp(T *object, int64_t *stamp)
void SaveState(T *object)
void ClearAndResize(IntegerType size)
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
void Set(IntegerType index)
void Resize(IntegerType size)
void AdvanceDeterministicTime(double deterministic_duration)
bool Contains(int id) const
void SortByPos(absl::Span< int > elements)
void ReorderDense(absl::Span< const int > order)
void Reorder(absl::Span< const int > order)
This is meant as an helper to deal with enforcement for any constraint.
bool Propagate(Trail *trail) final
SatPropagator interface.
void AddEnforcementReason(EnforcementId id, std::vector< Literal > *reason) const
Add the enforcement reason to the given vector.
ABSL_MUST_USE_RESULT bool PropagateWhenFalse(EnforcementId id, absl::Span< const Literal > literal_reason, absl::Span< const IntegerLiteral > integer_reason)
void Untrail(const Trail &trail, int trail_index) final
EnforcementStatus DebugStatus(EnforcementId id)
EnforcementId Register(absl::Span< const Literal > enforcement, std::function< void(EnforcementStatus)> callback=nullptr)
void WatchLowerBound(IntegerVariable var, int id, int watch_index=-1)
void SetPropagatorPriority(int id, int priority)
void CallOnNextPropagate(int id)
Add the given propagator to its queue.
IntegerValue LowerBound(IntegerVariable i) const
Returns the current lower/upper bound of the given integer variable.
bool VariableLowerBoundIsFromLevelZero(IntegerVariable var) const
Returns true if the variable lower bound is still the one from level zero.
void RegisterWatcher(SparseBitset< IntegerVariable > *p)
void RelaxLinearReason(IntegerValue slack, absl::Span< const IntegerValue > coeffs, std::vector< IntegerLiteral > *reason) const
IntegerValue UpperBound(IntegerVariable i) const
IntegerLiteral LowerBoundAsLiteral(IntegerVariable i) const
void RegisterReversibleClass(ReversibleInterface *rev)
bool ReportConflict(absl::Span< const Literal > literal_reason, absl::Span< const IntegerLiteral > integer_reason)
IntegerVariable NumIntegerVariables() const
ABSL_MUST_USE_RESULT bool Enqueue(IntegerLiteral i_lit, absl::Span< const Literal > literal_reason, absl::Span< const IntegerLiteral > integer_reason)
void EnqueueLiteral(Literal literal, absl::Span< const Literal > literal_reason, absl::Span< const IntegerLiteral > integer_reason)
LinearPropagator(Model *model)
~LinearPropagator() override
void SetLevel(int level) final
bool AddConstraint(absl::Span< const Literal > enforcement_literals, absl::Span< const IntegerVariable > vars, absl::Span< const IntegerValue > coeffs, IntegerValue upper_bound)
Adds a new constraint to the propagator.
Base class for all the SAT constraints.
int propagation_trail_index_
Simple class to add statistics by name and print them at the end.
void AddStats(absl::Span< const std::pair< std::string, int64_t > > stats)
Adds a bunch of stats, adding count for the same key together.
int CurrentDecisionLevel() const
const AssignmentInfo & Info(BooleanVariable var) const
const VariablesAssignment & Assignment() const
bool LiteralIsAssigned(Literal literal) const
bool LiteralIsFalse(Literal literal) const
bool LiteralIsTrue(Literal literal) const
SharedStatistics *const stats
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
const LiteralIndex kNoLiteralIndex(-1)
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
Returns the vector of the negated variables.
const IntegerVariable kNoIntegerVariable(-1)
IntegerVariable PositiveVariable(IntegerVariable i)
@ IS_ENFORCED
All enforcement literals are true.
@ CANNOT_PROPAGATE
More than two literals are unassigned.
@ IS_FALSE
One enforcement literal is false.
@ CAN_PROPAGATE
All enforcement literals are true but one.
bool VariableIsPositive(IntegerVariable i)
In SWIG mode, we don't want anything besides these top-level includes.
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
static IntegerLiteral LowerOrEqual(IntegerVariable i, IntegerValue bound)