25#include "absl/algorithm/container.h"
26#include "absl/container/flat_hash_map.h"
27#include "absl/container/flat_hash_set.h"
28#include "absl/log/check.h"
29#include "absl/types/span.h"
34#include "ortools/sat/cp_model.pb.h"
46int64_t ExprValue(
const LinearExpressionProto& expr,
47 absl::Span<const int64_t>
solution) {
48 int64_t result = expr.offset();
49 for (
int i = 0;
i < expr.vars_size(); ++
i) {
50 result +=
solution[expr.vars(
i)] * expr.coeffs(
i);
55LinearExpressionProto ExprDiff(
const LinearExpressionProto& a,
56 const LinearExpressionProto&
b) {
57 LinearExpressionProto result;
58 result.set_offset(a.offset() -
b.offset());
59 result.mutable_vars()->Reserve(a.vars().size() +
b.vars().size());
60 result.mutable_coeffs()->Reserve(a.vars().size() +
b.vars().size());
61 for (
int i = 0;
i < a.vars().size(); ++
i) {
62 result.add_vars(a.vars(
i));
63 result.add_coeffs(a.coeffs(
i));
65 for (
int i = 0;
i <
b.vars().size(); ++
i) {
66 result.add_vars(
b.vars(
i));
67 result.add_coeffs(-
b.coeffs(
i));
72LinearExpressionProto LinearExprSum(LinearExpressionProto a,
73 LinearExpressionProto
b) {
74 LinearExpressionProto result;
75 result.set_offset(a.offset() +
b.offset());
76 result.mutable_vars()->Reserve(a.vars().size() +
b.vars().size());
77 result.mutable_coeffs()->Reserve(a.vars().size() +
b.vars().size());
78 for (
const LinearExpressionProto& p : {a,
b}) {
79 for (
int i = 0;
i < p.vars().size(); ++
i) {
80 result.add_vars(p.vars(
i));
81 result.add_coeffs(p.coeffs(
i));
87LinearExpressionProto NegatedLinearExpression(LinearExpressionProto a) {
88 LinearExpressionProto result = a;
89 result.set_offset(-a.offset());
90 for (int64_t& coeff : *result.mutable_coeffs()) {
96int64_t ExprMin(
const LinearExpressionProto& expr,
const CpModelProto& model) {
97 int64_t result = expr.offset();
98 for (
int i = 0;
i < expr.vars_size(); ++
i) {
99 const IntegerVariableProto& var_proto = model.variables(expr.vars(
i));
100 if (expr.coeffs(
i) > 0) {
101 result += expr.coeffs(
i) * var_proto.domain(0);
103 result += expr.coeffs(
i) * var_proto.domain(var_proto.domain_size() - 1);
109int64_t ExprMax(
const LinearExpressionProto& expr,
const CpModelProto& model) {
110 int64_t result = expr.offset();
111 for (
int i = 0;
i < expr.vars_size(); ++
i) {
112 const IntegerVariableProto& var_proto = model.variables(expr.vars(
i));
113 if (expr.coeffs(
i) > 0) {
114 result += expr.coeffs(
i) * var_proto.domain(var_proto.domain_size() - 1);
116 result += expr.coeffs(
i) * var_proto.domain(0);
122bool LiteralValue(
int lit, absl::Span<const int64_t>
solution) {
135 DCHECK(creation_phase_);
136 domains_.push_back(domain);
137 offsets_.push_back(0);
138 activities_.push_back(0);
139 num_false_enforcement_.push_back(0);
140 distances_.push_back(0);
141 is_violated_.push_back(
false);
142 return num_constraints_++;
146 DCHECK(creation_phase_);
148 if (literal_entries_.size() <= var) {
149 literal_entries_.resize(var + 1);
151 literal_entries_[var].push_back(
157 DCHECK(creation_phase_);
159 AddTerm(ct_index, lit, coeff, 0);
167 DCHECK(creation_phase_);
169 if (coeff == 0)
return;
171 if (var_entries_.size() <= var) {
172 var_entries_.resize(var + 1);
174 if (!var_entries_[var].empty() &&
175 var_entries_[var].back().ct_index == ct_index) {
176 var_entries_[var].back().coefficient += coeff;
177 if (var_entries_[var].back().coefficient == 0) {
178 var_entries_[var].pop_back();
181 var_entries_[var].push_back({.ct_index = ct_index, .coefficient = coeff});
188 DCHECK(creation_phase_);
189 offsets_[ct_index] += offset;
193 int ct_index,
const LinearExpressionProto& expr, int64_t multiplier) {
194 DCHECK(creation_phase_);
195 AddOffset(ct_index, expr.offset() * multiplier);
196 for (
int i = 0;
i < expr.vars_size(); ++
i) {
197 if (expr.coeffs(
i) * multiplier == 0)
continue;
198 AddTerm(ct_index, expr.vars(
i), expr.coeffs(
i) * multiplier);
203 if (var_entries_.size() <= var)
return true;
205 absl::flat_hash_set<int> visited;
206 for (
const Entry& entry : var_entries_[var]) {
207 if (!visited.insert(entry.ct_index).second)
return false;
213 absl::Span<const int64_t>
solution) {
214 DCHECK(!creation_phase_);
217 activities_ = offsets_;
218 in_last_affected_variables_.resize(columns_.size(),
false);
219 num_false_enforcement_.assign(num_constraints_, 0);
222 const int num_vars = columns_.size();
223 for (
int var = 0; var < num_vars; ++var) {
224 const SpanData& data = columns_[var];
225 const int64_t value =
solution[var];
227 if (value == 0 && data.num_pos_literal > 0) {
228 const int* ct_indices = &ct_buffer_[data.start];
229 for (
int k = 0; k < data.num_pos_literal; ++k) {
230 num_false_enforcement_[ct_indices[k]]++;
234 if (value == 1 && data.num_neg_literal > 0) {
235 const int* ct_indices = &ct_buffer_[data.start + data.num_pos_literal];
236 for (
int k = 0; k < data.num_neg_literal; ++k) {
237 num_false_enforcement_[ct_indices[k]]++;
241 if (value != 0 && data.num_linear_entries > 0) {
242 const int* ct_indices =
243 &ct_buffer_[data.start + data.num_pos_literal + data.num_neg_literal];
244 const int64_t* coeffs = &coeff_buffer_[data.linear_start];
245 for (
int k = 0; k < data.num_linear_entries; ++k) {
246 activities_[ct_indices[k]] += coeffs[k] * value;
252 for (
int c = 0; c < num_constraints_; ++c) {
253 distances_[c] = domains_[c].Distance(activities_[c]);
259 if (10 * last_affected_variables_.size() < columns_.size()) {
261 in_last_affected_variables_.resize(columns_.size(),
false);
262 for (
const int var : last_affected_variables_) {
263 in_last_affected_variables_[var] =
false;
267 in_last_affected_variables_.assign(columns_.size(),
false);
269 last_affected_variables_.clear();
270 DCHECK(std::all_of(in_last_affected_variables_.begin(),
271 in_last_affected_variables_.end(),
272 [](
bool b) { return !b; }));
279 int c, absl::Span<const int64_t> jump_deltas,
280 absl::Span<double> var_to_score_change) {
281 if (c >= rows_.size())
return;
283 DCHECK_EQ(num_false_enforcement_[c], 0);
284 const SpanData& data = rows_[c];
289 const double enforcement_change =
static_cast<double>(-distances_[c]);
290 if (enforcement_change != 0.0) {
292 const int end = data.num_pos_literal + data.num_neg_literal;
294 for (
int k = 0; k < end; ++k, ++
i) {
295 const int var = row_var_buffer_[
i];
296 if (!in_last_affected_variables_[var]) {
297 var_to_score_change[var] = enforcement_change;
298 in_last_affected_variables_[var] =
true;
299 last_affected_variables_.push_back(var);
301 var_to_score_change[var] += enforcement_change;
307 if (data.num_linear_entries > 0) {
308 const int* row_vars = &row_var_buffer_[data.start + data.num_pos_literal +
309 data.num_neg_literal];
310 const int64_t* row_coeffs = &row_coeff_buffer_[data.linear_start];
311 num_ops_ += 2 * data.num_linear_entries;
316 const Domain& rhs = domains_[c];
317 const int64_t rhs_min = rhs.
Min();
318 const int64_t rhs_max = rhs.
Max();
320 const auto violation = [&rhs, rhs_min, rhs_max, is_simple](int64_t v) {
323 }
else if (v <= rhs_min) {
326 return is_simple ? int64_t{0} : rhs.
Distance(v);
330 const int64_t old_distance = distances_[c];
331 const int64_t activity = activities_[c];
332 for (
int k = 0; k < data.num_linear_entries; ++k) {
333 const int var = row_vars[k];
334 const int64_t coeff = row_coeffs[k];
336 violation(activity + coeff * jump_deltas[var]) - old_distance;
337 if (!in_last_affected_variables_[var]) {
338 var_to_score_change[var] =
static_cast<double>(diff);
339 in_last_affected_variables_[var] =
true;
340 last_affected_variables_.push_back(var);
342 var_to_score_change[var] +=
static_cast<double>(diff);
348void LinearIncrementalEvaluator::UpdateScoreOnNewlyEnforced(
349 int c,
double weight, absl::Span<const int64_t> jump_deltas,
350 absl::Span<double> jump_scores) {
351 const SpanData& data = rows_[c];
355 const double weight_time_violation =
356 weight *
static_cast<double>(distances_[c]);
357 if (weight_time_violation > 0.0) {
359 const int end = data.num_pos_literal + data.num_neg_literal;
361 for (
int k = 0; k < end; ++k, ++
i) {
362 const int var = row_var_buffer_[
i];
363 jump_scores[var] -= weight_time_violation;
364 if (!in_last_affected_variables_[var]) {
365 in_last_affected_variables_[var] =
true;
373 int i = data.start + data.num_pos_literal + data.num_neg_literal;
374 int j = data.linear_start;
375 num_ops_ += 2 * data.num_linear_entries;
376 const int64_t old_distance = distances_[
c];
377 for (
int k = 0; k < data.num_linear_entries; ++k, ++
i, ++j) {
378 const int var = row_var_buffer_[
i];
379 const int64_t coeff = row_coeff_buffer_[j];
380 const int64_t new_distance =
381 domains_[
c].Distance(activities_[c] + coeff * jump_deltas[var]);
383 weight *
static_cast<double>(new_distance - old_distance);
384 if (!in_last_affected_variables_[var]) {
385 in_last_affected_variables_[var] =
true;
386 last_affected_variables_.push_back(var);
392void LinearIncrementalEvaluator::UpdateScoreOnNewlyUnenforced(
393 int c,
double weight, absl::Span<const int64_t> jump_deltas,
394 absl::Span<double> jump_scores) {
395 const SpanData& data = rows_[
c];
400 const double weight_time_violation =
401 weight *
static_cast<double>(distances_[
c]);
402 if (weight_time_violation > 0.0) {
404 const int end = data.num_pos_literal + data.num_neg_literal;
406 for (
int k = 0; k < end; ++k, ++
i) {
407 const int var = row_var_buffer_[
i];
408 jump_scores[var] += weight_time_violation;
414 int i = data.start + data.num_pos_literal + data.num_neg_literal;
415 int j = data.linear_start;
416 num_ops_ += 2 * data.num_linear_entries;
417 const int64_t old_distance = distances_[
c];
418 for (
int k = 0; k < data.num_linear_entries; ++k, ++
i, ++j) {
419 const int var = row_var_buffer_[
i];
420 const int64_t coeff = row_coeff_buffer_[j];
421 const int64_t new_distance =
422 domains_[
c].Distance(activities_[c] + coeff * jump_deltas[var]);
424 weight *
static_cast<double>(new_distance - old_distance);
425 if (!in_last_affected_variables_[var]) {
426 in_last_affected_variables_[var] =
true;
427 last_affected_variables_.push_back(var);
435void LinearIncrementalEvaluator::UpdateScoreOfEnforcementIncrease(
436 int c,
double score_change, absl::Span<const int64_t> jump_deltas,
437 absl::Span<double> jump_scores) {
438 if (score_change == 0.0)
return;
440 const SpanData& data = rows_[
c];
442 num_ops_ += data.num_pos_literal;
443 for (
int k = 0; k < data.num_pos_literal; ++k, ++
i) {
444 const int var = row_var_buffer_[
i];
445 if (jump_deltas[var] == 1) {
446 jump_scores[var] += score_change;
447 if (score_change < 0.0 && !in_last_affected_variables_[var]) {
448 in_last_affected_variables_[var] =
true;
449 last_affected_variables_.push_back(var);
453 num_ops_ += data.num_neg_literal;
454 for (
int k = 0; k < data.num_neg_literal; ++k, ++
i) {
455 const int var = row_var_buffer_[
i];
456 if (jump_deltas[var] == -1) {
457 jump_scores[var] += score_change;
458 if (score_change < 0.0 && !in_last_affected_variables_[var]) {
459 in_last_affected_variables_[var] =
true;
460 last_affected_variables_.push_back(var);
466void LinearIncrementalEvaluator::UpdateScoreOnActivityChange(
467 int c,
double weight, int64_t activity_delta,
468 absl::Span<const int64_t> jump_deltas, absl::Span<double> jump_scores) {
469 if (activity_delta == 0)
return;
470 const SpanData& data = rows_[
c];
481 const int64_t old_activity = activities_[
c];
482 const int64_t new_activity = old_activity + activity_delta;
485 if (new_activity > old_activity) {
486 min_range = old_activity - row_max_variations_[
c];
487 max_range = new_activity + row_max_variations_[
c];
489 min_range = new_activity - row_max_variations_[
c];
490 max_range = old_activity + row_max_variations_[
c];
494 if (Domain(min_range, max_range).IsIncludedIn(domains_[c]))
return;
500 static_cast<double>(domains_[
c].Distance(new_activity) - distances_[c]);
503 const int end = data.num_pos_literal + data.num_neg_literal;
505 for (
int k = 0; k < end; ++k, ++
i) {
506 const int var = row_var_buffer_[
i];
507 jump_scores[var] += delta;
508 if (delta < 0.0 && !in_last_affected_variables_[var]) {
509 in_last_affected_variables_[var] =
true;
510 last_affected_variables_.push_back(var);
518 if (min_range >= domains_[c].Max() || max_range <= domains_[c].Min())
return;
521 if (data.num_linear_entries > 0) {
522 const int* row_vars = &row_var_buffer_[data.start + data.num_pos_literal +
523 data.num_neg_literal];
524 const int64_t* row_coeffs = &row_coeff_buffer_[data.linear_start];
525 num_ops_ += 2 * data.num_linear_entries;
530 const Domain& rhs = domains_[
c];
531 const int64_t rhs_min = rhs.
Min();
532 const int64_t rhs_max = rhs.
Max();
533 const bool is_simple = rhs.NumIntervals() == 2;
534 const auto violation = [&rhs, rhs_min, rhs_max, is_simple](int64_t v) {
537 }
else if (v <= rhs_min) {
540 return is_simple ? int64_t{0} : rhs.Distance(v);
544 const int64_t old_a_minus_new_a =
545 distances_[
c] - domains_[
c].Distance(new_activity);
546 for (
int k = 0; k < data.num_linear_entries; ++k) {
547 const int var = row_vars[k];
548 const int64_t impact = row_coeffs[k] * jump_deltas[var];
549 const int64_t old_b = violation(old_activity + impact);
550 const int64_t new_b = violation(new_activity + impact);
557 const int64_t diff = old_a_minus_new_a + new_b - old_b;
562 jump_scores[var] += weight *
static_cast<double>(diff);
563 if (!in_last_affected_variables_[var]) {
564 in_last_affected_variables_[var] =
true;
565 last_affected_variables_.push_back(var);
573 int var, int64_t delta, absl::Span<const double> weights,
574 absl::Span<const int64_t> jump_deltas, absl::Span<double> jump_scores,
575 std::vector<int>* constraints_with_changed_violation) {
576 DCHECK(!creation_phase_);
578 if (var >= columns_.size())
return;
580 const SpanData& data = columns_[var];
582 num_ops_ += data.num_pos_literal;
583 for (
int k = 0; k < data.num_pos_literal; ++k, ++
i) {
584 const int c = ct_buffer_[
i];
587 num_false_enforcement_[c]--;
588 DCHECK_GE(num_false_enforcement_[c], 0);
589 if (num_false_enforcement_[c] == 0) {
590 UpdateScoreOnNewlyEnforced(c, weights[c], jump_deltas, jump_scores);
591 }
else if (num_false_enforcement_[c] == 1) {
592 const double enforcement_change =
593 weights[c] *
static_cast<double>(distances_[c]);
594 UpdateScoreOfEnforcementIncrease(c, enforcement_change, jump_deltas,
598 num_false_enforcement_[c]++;
599 if (num_false_enforcement_[c] == 1) {
600 UpdateScoreOnNewlyUnenforced(c, weights[c], jump_deltas, jump_scores);
601 }
else if (num_false_enforcement_[c] == 2) {
602 const double enforcement_change =
603 weights[c] *
static_cast<double>(distances_[c]);
604 UpdateScoreOfEnforcementIncrease(c, -enforcement_change, jump_deltas,
609 is_violated_[c] = v1 > 0;
611 constraints_with_changed_violation->push_back(c);
614 num_ops_ += data.num_neg_literal;
615 for (
int k = 0; k < data.num_neg_literal; ++k, ++
i) {
616 const int c = ct_buffer_[
i];
619 num_false_enforcement_[c]--;
620 DCHECK_GE(num_false_enforcement_[c], 0);
621 if (num_false_enforcement_[c] == 0) {
622 UpdateScoreOnNewlyEnforced(c, weights[c], jump_deltas, jump_scores);
623 }
else if (num_false_enforcement_[c] == 1) {
624 const double enforcement_change =
625 weights[c] *
static_cast<double>(distances_[c]);
626 UpdateScoreOfEnforcementIncrease(c, enforcement_change, jump_deltas,
630 num_false_enforcement_[c]++;
631 if (num_false_enforcement_[c] == 1) {
632 UpdateScoreOnNewlyUnenforced(c, weights[c], jump_deltas, jump_scores);
633 }
else if (num_false_enforcement_[c] == 2) {
634 const double enforcement_change =
635 weights[c] *
static_cast<double>(distances_[c]);
636 UpdateScoreOfEnforcementIncrease(c, -enforcement_change, jump_deltas,
641 is_violated_[c] = v1 > 0;
643 constraints_with_changed_violation->push_back(c);
646 int j = data.linear_start;
647 num_ops_ += 2 * data.num_linear_entries;
648 for (
int k = 0; k < data.num_linear_entries; ++k, ++
i, ++j) {
649 const int c = ct_buffer_[
i];
651 const int64_t coeff = coeff_buffer_[j];
653 if (num_false_enforcement_[c] == 1) {
657 const int64_t new_distance =
658 domains_[c].Distance(activities_[c] + coeff * delta);
659 if (new_distance != distances_[c]) {
660 UpdateScoreOfEnforcementIncrease(
661 c, -weights[c] *
static_cast<double>(distances_[c] - new_distance),
662 jump_deltas, jump_scores);
664 }
else if (num_false_enforcement_[c] == 0) {
665 UpdateScoreOnActivityChange(c, weights[c], coeff * delta, jump_deltas,
669 activities_[c] += coeff * delta;
670 distances_[c] = domains_[c].Distance(activities_[c]);
672 is_violated_[c] = v1 > 0;
674 constraints_with_changed_violation->push_back(c);
680 return activities_[c];
684 return num_false_enforcement_[c] > 0 ? 0 : distances_[c];
688 DCHECK_EQ(is_violated_[c],
Violation(c) > 0);
689 return is_violated_[c];
693 if (domains_[c].Min() >= lb && domains_[c].Max() <= ub)
return false;
694 domains_[c] = domains_[c].IntersectionWith(
Domain(lb, ub));
695 distances_[c] = domains_[c].Distance(activities_[c]);
700 absl::Span<const double> weights)
const {
702 DCHECK_GE(weights.size(), num_constraints_);
703 for (
int c = 0; c < num_constraints_; ++c) {
704 if (num_false_enforcement_[c] > 0)
continue;
705 result += weights[c] *
static_cast<double>(distances_[c]);
716 absl::Span<const double> weights,
int var, int64_t delta)
const {
718 if (var >= columns_.size())
return 0.0;
719 const SpanData& data = columns_[var];
723 num_ops_ += data.num_pos_literal;
724 for (
int k = 0; k < data.num_pos_literal; ++k, ++
i) {
725 const int c = ct_buffer_[
i];
726 if (num_false_enforcement_[c] == 0) {
728 DCHECK_EQ(delta, -1);
729 result -= weights[c] *
static_cast<double>(distances_[c]);
731 if (delta == 1 && num_false_enforcement_[c] == 1) {
732 result += weights[c] *
static_cast<double>(distances_[c]);
737 num_ops_ += data.num_neg_literal;
738 for (
int k = 0; k < data.num_neg_literal; ++k, ++
i) {
739 const int c = ct_buffer_[
i];
740 if (num_false_enforcement_[c] == 0) {
743 result -= weights[c] *
static_cast<double>(distances_[c]);
745 if (delta == -1 && num_false_enforcement_[c] == 1) {
746 result += weights[c] *
static_cast<double>(distances_[c]);
751 int j = data.linear_start;
752 num_ops_ += 2 * data.num_linear_entries;
753 for (
int k = 0; k < data.num_linear_entries; ++k, ++
i, ++j) {
754 const int c = ct_buffer_[
i];
755 if (num_false_enforcement_[c] > 0)
continue;
756 const int64_t coeff = coeff_buffer_[j];
757 const int64_t old_distance = distances_[c];
758 const int64_t new_distance =
759 domains_[c].Distance(activities_[c] + coeff * delta);
760 result += weights[c] *
static_cast<double>(new_distance - old_distance);
767 if (var >= columns_.size())
return false;
768 for (
const int c : VarToConstraints(var)) {
775 int var, int64_t current_value,
const Domain& var_domain)
const {
777 if (var_domain.
Size() <= 2 || var >= columns_.size())
return result;
779 const SpanData& data = columns_[var];
780 int i = data.start + data.num_pos_literal + data.num_neg_literal;
781 int j = data.linear_start;
782 for (
int k = 0; k < data.num_linear_entries; ++k, ++
i, ++j) {
783 const int c = ct_buffer_[
i];
784 if (num_false_enforcement_[c] > 0)
continue;
789 const int64_t coeff = coeff_buffer_[j];
790 const int64_t activity = activities_[c] - current_value * coeff;
792 const int64_t slack_min =
CapSub(domains_[c].Min(), activity);
793 const int64_t slack_max =
CapSub(domains_[c].Max(), activity);
794 if (slack_min != std::numeric_limits<int64_t>::min()) {
796 if (ceil_bp != result.back() && var_domain.
Contains(ceil_bp)) {
797 result.push_back(ceil_bp);
800 if (floor_bp != result.back() && var_domain.
Contains(floor_bp)) {
801 result.push_back(floor_bp);
804 if (slack_min != slack_max &&
805 slack_max != std::numeric_limits<int64_t>::min()) {
807 if (ceil_bp != result.back() && var_domain.
Contains(ceil_bp)) {
808 result.push_back(ceil_bp);
811 if (floor_bp != result.back() && var_domain.
Contains(floor_bp)) {
812 result.push_back(floor_bp);
822 absl::Span<const int64_t> var_max_variation) {
823 creation_phase_ =
false;
824 if (num_constraints_ == 0)
return;
829 int total_linear_size = 0;
830 tmp_row_sizes_.assign(num_constraints_, 0);
831 tmp_row_num_positive_literals_.assign(num_constraints_, 0);
832 tmp_row_num_negative_literals_.assign(num_constraints_, 0);
833 tmp_row_num_linear_entries_.assign(num_constraints_, 0);
834 for (
const auto& column : literal_entries_) {
835 total_size += column.size();
836 for (
const auto [c, is_positive] : column) {
839 tmp_row_num_positive_literals_[c]++;
841 tmp_row_num_negative_literals_[c]++;
846 row_max_variations_.assign(num_constraints_, 0);
847 for (
int var = 0; var < var_entries_.size(); ++var) {
848 const int64_t range = var_max_variation[var];
849 const auto& column = var_entries_[var];
850 total_size += column.size();
851 total_linear_size += column.size();
852 for (
const auto [c, coeff] : column) {
854 tmp_row_num_linear_entries_[c]++;
855 row_max_variations_[c] =
856 std::max(row_max_variations_[c], range * std::abs(coeff));
861 ct_buffer_.reserve(total_size);
862 coeff_buffer_.reserve(total_linear_size);
863 columns_.resize(std::max(literal_entries_.size(), var_entries_.size()));
864 for (
int var = 0; var < columns_.size(); ++var) {
865 columns_[var].start =
static_cast<int>(ct_buffer_.size());
866 columns_[var].linear_start =
static_cast<int>(coeff_buffer_.size());
867 if (var < literal_entries_.size()) {
868 for (
const auto [c, is_positive] : literal_entries_[var]) {
870 columns_[var].num_pos_literal++;
871 ct_buffer_.push_back(c);
874 for (
const auto [c, is_positive] : literal_entries_[var]) {
876 columns_[var].num_neg_literal++;
877 ct_buffer_.push_back(c);
881 if (var < var_entries_.size()) {
882 for (
const auto [c, coeff] : var_entries_[var]) {
883 columns_[var].num_linear_entries++;
884 ct_buffer_.push_back(c);
885 coeff_buffer_.push_back(coeff);
901 int linear_offset = 0;
902 rows_.resize(num_constraints_);
903 for (
int c = 0; c < num_constraints_; ++c) {
904 rows_[c].num_pos_literal = tmp_row_num_positive_literals_[c];
905 rows_[c].num_neg_literal = tmp_row_num_negative_literals_[c];
906 rows_[c].num_linear_entries = tmp_row_num_linear_entries_[c];
908 rows_[c].start = offset;
909 offset += tmp_row_sizes_[c];
910 tmp_row_sizes_[c] = rows_[c].start;
912 rows_[c].linear_start = linear_offset;
913 linear_offset += tmp_row_num_linear_entries_[c];
914 tmp_row_num_linear_entries_[c] = rows_[c].linear_start;
916 DCHECK_EQ(offset, total_size);
917 DCHECK_EQ(linear_offset, total_linear_size);
920 row_var_buffer_.resize(total_size);
921 row_coeff_buffer_.resize(total_linear_size);
922 for (
int var = 0; var < columns_.size(); ++var) {
923 const SpanData& data = columns_[var];
925 for (
int k = 0; k < data.num_pos_literal; ++
i, ++k) {
926 const int c = ct_buffer_[
i];
927 row_var_buffer_[tmp_row_sizes_[c]++] = var;
930 for (
int var = 0; var < columns_.size(); ++var) {
931 const SpanData& data = columns_[var];
932 int i = data.start + data.num_pos_literal;
933 for (
int k = 0; k < data.num_neg_literal; ++
i, ++k) {
934 const int c = ct_buffer_[
i];
935 row_var_buffer_[tmp_row_sizes_[c]++] = var;
938 for (
int var = 0; var < columns_.size(); ++var) {
939 const SpanData& data = columns_[var];
940 int i = data.start + data.num_pos_literal + data.num_neg_literal;
941 int j = data.linear_start;
942 for (
int k = 0; k < data.num_linear_entries; ++
i, ++j, ++k) {
943 const int c = ct_buffer_[
i];
944 row_var_buffer_[tmp_row_sizes_[c]++] = var;
945 row_coeff_buffer_[tmp_row_num_linear_entries_[c]++] = coeff_buffer_[j];
949 cached_deltas_.assign(columns_.size(), 0);
950 cached_scores_.assign(columns_.size(), 0);
951 last_affected_variables_.ClearAndReserve(columns_.size());
955 for (
const int c : VarToConstraints(var)) {
956 if (domains_[c].NumIntervals() > 2)
return false;
964 absl::Span<const int64_t>
solution) {
969 int var, int64_t old_value,
970 absl::Span<const int64_t> solution_with_new_value) {
975 absl::Span<const int64_t>
solution) {
986 const CpModelProto& model_proto)
const {
989 const ConstraintProto& interval_proto = model_proto.constraints(i_var);
991 result.push_back(var);
995 result.shrink_to_fit();
1006 absl::Span<const int64_t>
solution) {
1007 int64_t sum_of_literals = 0;
1008 for (
const int lit :
ct_proto().bool_xor().literals()) {
1009 sum_of_literals += LiteralValue(lit,
solution);
1011 return 1 - (sum_of_literals % 2);
1016 absl::Span<const int64_t> ) {
1027 absl::Span<const int64_t>
solution) {
1028 const int64_t target_value =
1030 int64_t max_of_expressions = std::numeric_limits<int64_t>::min();
1031 for (
const LinearExpressionProto& expr :
ct_proto().lin_max().exprs()) {
1032 const int64_t expr_value = ExprValue(expr,
solution);
1033 max_of_expressions = std::max(max_of_expressions, expr_value);
1035 return std::max(target_value - max_of_expressions, int64_t{0});
1045 absl::Span<const int64_t>
solution) {
1046 const int64_t target_value =
1048 int64_t prod_value = 1;
1049 for (
const LinearExpressionProto& expr :
ct_proto().int_prod().exprs()) {
1050 prod_value *= ExprValue(expr,
solution);
1052 return std::abs(target_value - prod_value);
1062 absl::Span<const int64_t>
solution) {
1063 const int64_t target_value =
1065 DCHECK_EQ(
ct_proto().int_div().exprs_size(), 2);
1066 const int64_t div_value = ExprValue(
ct_proto().int_div().exprs(0),
solution) /
1068 return std::abs(target_value - div_value);
1078 absl::Span<const int64_t>
solution) {
1079 const int64_t target_value =
1081 DCHECK_EQ(
ct_proto().int_mod().exprs_size(), 2);
1083 const int64_t expr_value = ExprValue(
ct_proto().int_mod().exprs(0),
solution);
1084 const int64_t mod_value = ExprValue(
ct_proto().int_mod().exprs(1),
solution);
1085 const int64_t rhs = expr_value % mod_value;
1086 if ((expr_value >= 0 && target_value >= 0) ||
1087 (expr_value <= 0 && target_value <= 0)) {
1089 return std::min({std::abs(target_value - rhs),
1090 std::abs(target_value) + std::abs(mod_value - rhs),
1091 std::abs(rhs) + std::abs(mod_value - target_value)});
1096 return std::abs(target_value) + std::abs(expr_value);
1107 absl::Span<const int64_t>
solution) {
1109 for (
const LinearExpressionProto& expr :
ct_proto().all_diff().exprs()) {
1110 values_.push_back(ExprValue(expr,
solution));
1112 std::sort(values_.begin(), values_.end());
1114 int64_t value = values_[0];
1117 for (
int i = 1;
i < values_.size(); ++
i) {
1118 const int64_t new_value = values_[
i];
1119 if (new_value == value) {
1122 violation += counter * (counter - 1) / 2;
1127 violation += counter * (counter - 1) / 2;
1134 int interval_0,
int interval_1,
const CpModelProto& cp_model) {
1135 const ConstraintProto& ct0 = cp_model.constraints(interval_0);
1136 const ConstraintProto& ct1 = cp_model.constraints(interval_1);
1140 ct0.enforcement_literal().size() + ct1.enforcement_literal().size();
1141 if (num_enforcements_ > 0) {
1142 enforcements_.reset(
new int[num_enforcements_]);
1144 for (
const int lit : ct0.enforcement_literal()) enforcements_[
i++] = lit;
1145 for (
const int lit : ct1.enforcement_literal()) enforcements_[
i++] = lit;
1150 end_minus_start_1_ =
1151 ExprDiff(LinearExprSum(ct0.interval().start(), ct0.interval().size()),
1152 ct1.interval().start());
1153 end_minus_start_2_ =
1154 ExprDiff(LinearExprSum(ct1.interval().start(), ct1.interval().size()),
1155 ct0.interval().start());
1159int64_t NoOverlapBetweenTwoIntervals::ComputeViolationInternal(
1160 absl::Span<const int64_t>
solution) {
1161 for (
int i = 0;
i < num_enforcements_; ++
i) {
1162 if (!LiteralValue(enforcements_[
i],
solution))
return 0;
1164 const int64_t diff1 = ExprValue(end_minus_start_1_,
solution);
1165 const int64_t diff2 = ExprValue(end_minus_start_2_,
solution);
1166 return std::max(std::min(diff1, diff2), int64_t{0});
1170 const CpModelProto& )
const {
1171 std::vector<int> result;
1172 for (
int i = 0;
i < num_enforcements_; ++
i) {
1175 for (
const int var : end_minus_start_1_.vars()) {
1178 for (
const int var : end_minus_start_2_.vars()) {
1182 result.shrink_to_fit();
1189 const ConstraintProto& interval2,
1190 absl::Span<const int64_t>
solution) {
1191 for (
const int lit : interval1.enforcement_literal()) {
1192 if (!LiteralValue(lit,
solution))
return 0;
1194 for (
const int lit : interval2.enforcement_literal()) {
1195 if (!LiteralValue(lit,
solution))
return 0;
1198 const int64_t start1 = ExprValue(interval1.interval().start(),
solution);
1199 const int64_t end1 = ExprValue(interval1.interval().end(),
solution);
1201 const int64_t start2 = ExprValue(interval2.interval().start(),
solution);
1202 const int64_t end2 = ExprValue(interval2.interval().end(),
solution);
1204 if (start1 >= end2 || start2 >= end1)
return 0;
1208 return std::max(std::min(std::min(end2 - start2, end1 - start1),
1209 std::min(end2 - start1, end1 - start2)),
1214 const ConstraintProto& interval2,
1215 absl::Span<const int64_t>
solution) {
1216 for (
const int lit : interval1.enforcement_literal()) {
1217 if (!LiteralValue(lit,
solution))
return 0;
1219 for (
const int lit : interval2.enforcement_literal()) {
1220 if (!LiteralValue(lit,
solution))
return 0;
1223 const int64_t start1 = ExprValue(interval1.interval().start(),
solution);
1224 const int64_t end1 = ExprValue(interval1.interval().end(),
solution);
1226 const int64_t start2 = ExprValue(interval2.interval().start(),
solution);
1227 const int64_t end2 = ExprValue(interval2.interval().end(),
solution);
1229 return std::max(std::min(end2 - start1, end1 - start2), int64_t{0});
1233 const ConstraintProto&
ct_proto,
const CpModelProto& cp_model)
1237 absl::Span<const int64_t>
solution) {
1238 DCHECK_GE(
ct_proto().no_overlap_2d().x_intervals_size(), 2);
1239 const int size =
ct_proto().no_overlap_2d().x_intervals_size();
1242 for (
int i = 0;
i + 1 < size; ++
i) {
1243 const ConstraintProto& x_i =
1244 cp_model_.constraints(
ct_proto().no_overlap_2d().x_intervals(
i));
1245 const ConstraintProto& y_i =
1246 cp_model_.constraints(
ct_proto().no_overlap_2d().y_intervals(
i));
1247 for (
int j =
i + 1; j < size; ++j) {
1248 const ConstraintProto& x_j =
1249 cp_model_.constraints(
ct_proto().no_overlap_2d().x_intervals(j));
1250 const ConstraintProto& y_j =
1251 cp_model_.constraints(
ct_proto().no_overlap_2d().y_intervals(j));
1289 absl::Span<const int64_t> new_solution)
override;
1291 int var, int64_t old_value,
1292 absl::Span<const int64_t> solution_with_new_value)
override;
1296 void emplace_back(
const int* start,
const int* end);
1297 void reset(
int num_nodes);
1299 int num_components = 0;
1300 std::vector<bool> skipped;
1301 std::vector<int> root;
1303 void InitGraph(absl::Span<const int64_t>
solution);
1304 bool UpdateGraph(
int var, int64_t value);
1305 int64_t ViolationForCurrentGraph();
1307 absl::flat_hash_map<int, std::vector<int>> arcs_by_lit_;
1308 absl::Span<const int> literals_;
1309 absl::Span<const int> tails_;
1310 absl::Span<const int> heads_;
1312 std::vector<DenseSet<int>> graph_;
1314 SccOutput committed_sccs_;
1315 std::vector<bool> has_in_arc_;
1320void CompiledCircuitConstraint::SccOutput::emplace_back(
int const* start,
1322 const int root_node = *start;
1323 const int size = end - start;
1327 for (; start != end; ++start) {
1328 root[*start] = root_node;
1329 skipped[*start] = (size == 1);
1332void CompiledCircuitConstraint::SccOutput::reset(
int num_nodes) {
1335 root.resize(num_nodes);
1337 skipped.resize(num_nodes);
1343 const bool routes =
ct_proto.has_routes();
1345 heads_ = absl::MakeConstSpan(routes ?
ct_proto.routes().heads()
1347 literals_ = absl::MakeConstSpan(routes ?
ct_proto.routes().literals()
1349 graph_.resize(*absl::c_max_element(tails_) + 1);
1350 for (
int i = 0;
i < literals_.size(); ++
i) {
1351 arcs_by_lit_[literals_[
i]].push_back(
i);
1355void CompiledCircuitConstraint::InitGraph(absl::Span<const int64_t>
solution) {
1359 for (
int i = 0;
i < tails_.size(); ++
i) {
1360 if (!LiteralValue(literals_[
i],
solution))
continue;
1361 graph_[tails_[
i]].
insert(heads_[
i]);
1365bool CompiledCircuitConstraint::UpdateGraph(
int var, int64_t value) {
1366 bool needs_update =
false;
1367 const int enabled_lit =
1369 const int disabled_lit =
NegatedRef(enabled_lit);
1370 for (
const int arc : arcs_by_lit_[disabled_lit]) {
1371 const int tail = tails_[arc];
1372 const int head = heads_[arc];
1374 needs_update = needs_update || tail != head;
1375 graph_[tails_[arc]].erase(heads_[arc]);
1377 for (
const int arc : arcs_by_lit_[enabled_lit]) {
1378 const int tail = tails_[arc];
1379 const int head = heads_[arc];
1381 needs_update = needs_update ||
1382 committed_sccs_.root[tail] != committed_sccs_.root[head];
1383 graph_[tails_[arc]].insert(heads_[arc]);
1385 return needs_update;
1389 int var, int64_t, absl::Span<const int64_t> new_solution) {
1390 UpdateGraph(var, new_solution[var]);
1392 std::swap(committed_sccs_, sccs_);
1396 absl::Span<const int64_t>
solution) {
1398 int64_t result = ViolationForCurrentGraph();
1399 std::swap(committed_sccs_, sccs_);
1404 int var, int64_t old_value,
1405 absl::Span<const int64_t> solution_with_new_value) {
1407 if (UpdateGraph(var, solution_with_new_value[var])) {
1408 result = ViolationForCurrentGraph() -
violation_;
1410 UpdateGraph(var, old_value);
1414int64_t CompiledCircuitConstraint::ViolationForCurrentGraph() {
1415 const int num_nodes = graph_.
size();
1416 sccs_.reset(num_nodes);
1417 scc_finder_.FindStronglyConnectedComponents(num_nodes, graph_, &sccs_);
1420 if (sccs_.num_components == 0)
return 0;
1423 int num_half_connected_components = 0;
1424 has_in_arc_.clear();
1425 has_in_arc_.resize(num_nodes,
false);
1426 for (
int tail = 0; tail < graph_.
size(); ++tail) {
1427 if (sccs_.skipped[tail])
continue;
1428 for (
const int head : graph_[tail]) {
1429 const int head_root = sccs_.root[head];
1430 if (sccs_.root[tail] == head_root)
continue;
1431 if (has_in_arc_[head_root])
continue;
1432 if (sccs_.skipped[head_root])
continue;
1433 has_in_arc_[head_root] =
true;
1434 ++num_half_connected_components;
1437 const int64_t
violation = sccs_.num_components - 1 + sccs_.num_components -
1438 num_half_connected_components - 1 +
1439 (
ct_proto().has_routes() ? sccs_.skipped[0] : 0);
1440 VLOG(2) <<
"#SCCs=" << sccs_.num_components <<
" #nodes=" << num_nodes
1441 <<
" #half_connected_components=" << num_half_connected_components
1447 const ConstraintProto& ct_proto) {
1448 const bool routes = ct_proto.has_routes();
1449 auto heads = routes ? ct_proto.routes().heads() : ct_proto.circuit().heads();
1450 auto tails = routes ? ct_proto.routes().tails() : ct_proto.circuit().tails();
1452 routes ? ct_proto.routes().literals() : ct_proto.circuit().literals();
1454 std::vector<std::vector<int>> inflow_lits;
1455 std::vector<std::vector<int>> outflow_lits;
1456 for (
int i = 0;
i < heads.size(); ++
i) {
1457 if (heads[
i] >= inflow_lits.size()) {
1458 inflow_lits.resize(heads[
i] + 1);
1460 inflow_lits[heads[
i]].push_back(literals[
i]);
1461 if (tails[
i] >= outflow_lits.size()) {
1462 outflow_lits.resize(tails[
i] + 1);
1464 outflow_lits[tails[
i]].push_back(literals[
i]);
1467 const int depot_net_flow = linear_evaluator.
NewConstraint({0, 0});
1468 for (
const int lit : inflow_lits[0]) {
1469 linear_evaluator.
AddLiteral(depot_net_flow, lit, 1);
1471 for (
const int lit : outflow_lits[0]) {
1472 linear_evaluator.
AddLiteral(depot_net_flow, lit, -1);
1475 for (
int i = routes ? 1 : 0;
i < inflow_lits.size(); ++
i) {
1476 const int inflow_ct = linear_evaluator.
NewConstraint({1, 1});
1477 for (
const int lit : inflow_lits[
i]) {
1481 for (
int i = routes ? 1 : 0;
i < outflow_lits.size(); ++
i) {
1482 const int outflow_ct = linear_evaluator.
NewConstraint({1, 1});
1483 for (
const int lit : outflow_lits[
i]) {
1484 linear_evaluator.
AddLiteral(outflow_ct, lit);
1492 const SatParameters& params)
1493 : cp_model_(cp_model), params_(params) {
1494 var_to_constraints_.resize(cp_model_.variables_size());
1495 jump_value_optimal_.resize(cp_model_.variables_size(),
true);
1496 num_violated_constraint_per_var_ignoring_objective_.assign(
1497 cp_model_.variables_size(), 0);
1499 std::vector<bool> ignored_constraints(cp_model_.constraints_size(),
false);
1500 std::vector<ConstraintProto> additional_constraints;
1501 CompileConstraintsAndObjective(ignored_constraints, additional_constraints);
1502 BuildVarConstraintGraph();
1507 const CpModelProto& cp_model,
const SatParameters& params,
1508 const std::vector<bool>& ignored_constraints,
1509 const std::vector<ConstraintProto>& additional_constraints)
1510 : cp_model_(cp_model), params_(params) {
1511 var_to_constraints_.resize(cp_model_.variables_size());
1512 jump_value_optimal_.resize(cp_model_.variables_size(),
true);
1513 num_violated_constraint_per_var_ignoring_objective_.assign(
1514 cp_model_.variables_size(), 0);
1515 CompileConstraintsAndObjective(ignored_constraints, additional_constraints);
1516 BuildVarConstraintGraph();
1520void LsEvaluator::BuildVarConstraintGraph() {
1522 for (std::vector<int>& ct_indices : var_to_constraints_) ct_indices.clear();
1523 constraint_to_vars_.resize(constraints_.size());
1526 for (
int ct_index = 0; ct_index < constraints_.size(); ++ct_index) {
1527 constraint_to_vars_[ct_index] =
1528 constraints_[ct_index]->UsedVariables(cp_model_);
1529 for (
const int var : constraint_to_vars_[ct_index]) {
1530 var_to_constraints_[var].push_back(ct_index);
1535 for (std::vector<int>& constraints : var_to_constraints_) {
1538 for (std::vector<int>& vars : constraint_to_vars_) {
1543 jump_value_optimal_.resize(cp_model_.variables_size());
1544 for (
int i = 0;
i < cp_model_.variables_size(); ++
i) {
1545 if (!var_to_constraints_[
i].empty()) {
1546 jump_value_optimal_[
i] =
false;
1550 const IntegerVariableProto& var_proto = cp_model_.variables(
i);
1551 if (var_proto.domain_size() == 2 && var_proto.domain(0) == 0 &&
1552 var_proto.domain(1) == 1) {
1554 jump_value_optimal_[
i] =
true;
1558 jump_value_optimal_[
i] = linear_evaluator_.ViolationChangeIsConvex(
i);
1562void LsEvaluator::CompileOneConstraint(
const ConstraintProto& ct) {
1563 switch (ct.constraint_case()) {
1564 case ConstraintProto::ConstraintCase::kBoolOr: {
1566 const int ct_index = linear_evaluator_.NewConstraint(Domain(1, 1));
1567 for (
const int lit : ct.enforcement_literal()) {
1568 linear_evaluator_.AddEnforcementLiteral(ct_index, lit);
1570 for (
const int lit : ct.bool_or().literals()) {
1571 linear_evaluator_.AddEnforcementLiteral(ct_index,
NegatedRef(lit));
1575 case ConstraintProto::ConstraintCase::kBoolAnd: {
1576 const int num_literals = ct.bool_and().literals_size();
1577 const int ct_index =
1578 linear_evaluator_.NewConstraint(Domain(num_literals));
1579 for (
const int lit : ct.enforcement_literal()) {
1580 linear_evaluator_.AddEnforcementLiteral(ct_index, lit);
1582 for (
const int lit : ct.bool_and().literals()) {
1583 linear_evaluator_.AddLiteral(ct_index, lit);
1587 case ConstraintProto::ConstraintCase::kAtMostOne: {
1588 DCHECK(ct.enforcement_literal().empty());
1589 const int ct_index = linear_evaluator_.NewConstraint({0, 1});
1590 for (
const int lit : ct.at_most_one().literals()) {
1591 linear_evaluator_.AddLiteral(ct_index, lit);
1595 case ConstraintProto::ConstraintCase::kExactlyOne: {
1596 DCHECK(ct.enforcement_literal().empty());
1597 const int ct_index = linear_evaluator_.NewConstraint({1, 1});
1598 for (
const int lit : ct.exactly_one().literals()) {
1599 linear_evaluator_.AddLiteral(ct_index, lit);
1603 case ConstraintProto::ConstraintCase::kBoolXor: {
1604 constraints_.emplace_back(
new CompiledBoolXorConstraint(ct));
1607 case ConstraintProto::ConstraintCase::kAllDiff: {
1608 constraints_.emplace_back(
new CompiledAllDiffConstraint(ct));
1611 case ConstraintProto::ConstraintCase::kLinMax: {
1614 const LinearExpressionProto& target = ct.lin_max().target();
1615 for (
const LinearExpressionProto& expr : ct.lin_max().exprs()) {
1616 const int64_t max_value =
1617 ExprMax(target, cp_model_) - ExprMin(expr, cp_model_);
1618 const int precedence_index =
1619 linear_evaluator_.NewConstraint({0, max_value});
1620 linear_evaluator_.AddLinearExpression(precedence_index, target, 1);
1621 linear_evaluator_.AddLinearExpression(precedence_index, expr, -1);
1625 constraints_.emplace_back(
new CompiledLinMaxConstraint(ct));
1628 case ConstraintProto::ConstraintCase::kIntProd: {
1629 constraints_.emplace_back(
new CompiledIntProdConstraint(ct));
1632 case ConstraintProto::ConstraintCase::kIntDiv: {
1633 constraints_.emplace_back(
new CompiledIntDivConstraint(ct));
1636 case ConstraintProto::ConstraintCase::kIntMod: {
1637 DCHECK_EQ(ExprMin(ct.int_mod().exprs(1), cp_model_),
1638 ExprMax(ct.int_mod().exprs(1), cp_model_));
1639 constraints_.emplace_back(
new CompiledIntModConstraint(ct));
1642 case ConstraintProto::ConstraintCase::kLinear: {
1644 const int ct_index = linear_evaluator_.NewConstraint(domain);
1645 for (
const int lit : ct.enforcement_literal()) {
1646 linear_evaluator_.AddEnforcementLiteral(ct_index, lit);
1648 for (
int i = 0;
i < ct.linear().vars_size(); ++
i) {
1649 const int var = ct.linear().vars(
i);
1650 const int64_t coeff = ct.linear().coeffs(
i);
1651 linear_evaluator_.AddTerm(ct_index, var, coeff);
1655 case ConstraintProto::ConstraintCase::kNoOverlap: {
1656 const int size = ct.no_overlap().intervals_size();
1657 if (size <= 1)
break;
1658 if (size > params_.feasibility_jump_max_expanded_constraint_size()) {
1661 LinearExpressionProto one;
1663 std::vector<std::optional<int>> is_active;
1664 std::vector<LinearExpressionProto> times;
1665 std::vector<LinearExpressionProto> demands;
1666 const int num_intervals = ct.no_overlap().intervals().size();
1667 for (
int i = 0;
i < num_intervals; ++
i) {
1668 const ConstraintProto& interval_ct =
1669 cp_model_.constraints(ct.no_overlap().intervals(
i));
1670 if (interval_ct.enforcement_literal().empty()) {
1671 is_active.push_back(std::nullopt);
1672 is_active.push_back(std::nullopt);
1674 CHECK_EQ(interval_ct.enforcement_literal().size(), 1);
1675 is_active.push_back(interval_ct.enforcement_literal(0));
1676 is_active.push_back(interval_ct.enforcement_literal(0));
1679 times.push_back(interval_ct.interval().start());
1680 times.push_back(LinearExprSum(interval_ct.interval().start(),
1681 interval_ct.interval().size()));
1682 demands.push_back(one);
1683 demands.push_back(NegatedLinearExpression(one));
1685 constraints_.emplace_back(
new CompiledReservoirConstraint(
1686 std::move(one), std::move(is_active), std::move(times),
1687 std::move(demands)));
1691 for (
int i = 0;
i + 1 < size; ++
i) {
1692 const IntervalConstraintProto& interval_i =
1693 cp_model_.constraints(ct.no_overlap().intervals(
i)).interval();
1694 const int64_t min_start_i = ExprMin(interval_i.start(), cp_model_);
1695 const int64_t max_end_i = ExprMax(interval_i.end(), cp_model_);
1696 for (
int j =
i + 1; j < size; ++j) {
1697 const IntervalConstraintProto& interval_j =
1698 cp_model_.constraints(ct.no_overlap().intervals(j)).interval();
1699 const int64_t min_start_j = ExprMin(interval_j.start(), cp_model_);
1700 const int64_t max_end_j = ExprMax(interval_j.end(), cp_model_);
1701 if (min_start_i >= max_end_j || min_start_j >= max_end_i)
continue;
1703 constraints_.emplace_back(
new NoOverlapBetweenTwoIntervals(
1704 ct.no_overlap().intervals(
i), ct.no_overlap().intervals(j),
1711 case ConstraintProto::ConstraintCase::kCumulative: {
1712 LinearExpressionProto capacity = ct.cumulative().capacity();
1713 std::vector<std::optional<int>> is_active;
1714 std::vector<LinearExpressionProto> times;
1715 std::vector<LinearExpressionProto> demands;
1716 const int num_intervals = ct.cumulative().intervals().size();
1717 for (
int i = 0;
i < num_intervals; ++
i) {
1718 const ConstraintProto& interval_ct =
1719 cp_model_.constraints(ct.cumulative().intervals(
i));
1720 if (interval_ct.enforcement_literal().empty()) {
1721 is_active.push_back(std::nullopt);
1722 is_active.push_back(std::nullopt);
1724 CHECK_EQ(interval_ct.enforcement_literal().size(), 1);
1725 is_active.push_back(interval_ct.enforcement_literal(0));
1726 is_active.push_back(interval_ct.enforcement_literal(0));
1730 times.push_back(interval_ct.interval().start());
1731 demands.push_back(ct.cumulative().demands(
i));
1741 times.push_back(LinearExprSum(interval_ct.interval().start(),
1742 interval_ct.interval().size()));
1743 demands.push_back(NegatedLinearExpression(ct.cumulative().demands(
i)));
1746 constraints_.emplace_back(
new CompiledReservoirConstraint(
1747 std::move(capacity), std::move(is_active), std::move(times),
1748 std::move(demands)));
1751 case ConstraintProto::ConstraintCase::kNoOverlap2D: {
1752 const auto& x_intervals = ct.no_overlap_2d().x_intervals();
1753 const auto& y_intervals = ct.no_overlap_2d().y_intervals();
1754 const int size = x_intervals.size();
1755 if (size <= 1)
break;
1757 size > params_.feasibility_jump_max_expanded_constraint_size()) {
1758 CompiledNoOverlap2dConstraint* no_overlap_2d =
1759 new CompiledNoOverlap2dConstraint(ct, cp_model_);
1760 constraints_.emplace_back(no_overlap_2d);
1764 for (
int i = 0;
i + 1 < size; ++
i) {
1765 const IntervalConstraintProto& x_interval_i =
1766 cp_model_.constraints(x_intervals[
i]).interval();
1767 const int64_t x_min_start_i = ExprMin(x_interval_i.start(), cp_model_);
1768 const int64_t x_max_end_i = ExprMax(x_interval_i.end(), cp_model_);
1769 const IntervalConstraintProto& y_interval_i =
1770 cp_model_.constraints(y_intervals[
i]).interval();
1771 const int64_t y_min_start_i = ExprMin(y_interval_i.start(), cp_model_);
1772 const int64_t y_max_end_i = ExprMax(y_interval_i.end(), cp_model_);
1773 for (
int j =
i + 1; j < size; ++j) {
1774 const IntervalConstraintProto& x_interval_j =
1775 cp_model_.constraints(x_intervals[j]).interval();
1776 const int64_t x_min_start_j =
1777 ExprMin(x_interval_j.start(), cp_model_);
1778 const int64_t x_max_end_j = ExprMax(x_interval_j.end(), cp_model_);
1779 const IntervalConstraintProto& y_interval_j =
1780 cp_model_.constraints(y_intervals[j]).interval();
1781 const int64_t y_min_start_j =
1782 ExprMin(y_interval_j.start(), cp_model_);
1783 const int64_t y_max_end_j = ExprMax(y_interval_j.end(), cp_model_);
1784 if (x_min_start_i >= x_max_end_j || x_min_start_j >= x_max_end_i ||
1785 y_min_start_i >= y_max_end_j || y_min_start_j >= y_max_end_i) {
1788 ConstraintProto* diffn = expanded_constraints_.add_constraints();
1789 diffn->mutable_no_overlap_2d()->add_x_intervals(x_intervals[
i]);
1790 diffn->mutable_no_overlap_2d()->add_x_intervals(x_intervals[j]);
1791 diffn->mutable_no_overlap_2d()->add_y_intervals(y_intervals[
i]);
1792 diffn->mutable_no_overlap_2d()->add_y_intervals(y_intervals[j]);
1793 CompiledNoOverlap2dConstraint* no_overlap_2d =
1794 new CompiledNoOverlap2dConstraint(*diffn, cp_model_);
1795 constraints_.emplace_back(no_overlap_2d);
1800 case ConstraintProto::ConstraintCase::kCircuit:
1801 case ConstraintProto::ConstraintCase::kRoutes:
1802 constraints_.emplace_back(
new CompiledCircuitConstraint(ct));
1806 VLOG(1) <<
"Not implemented: " << ct.constraint_case();
1811void LsEvaluator::CompileConstraintsAndObjective(
1812 const std::vector<bool>& ignored_constraints,
1813 const std::vector<ConstraintProto>& additional_constraints) {
1814 constraints_.clear();
1817 if (cp_model_.has_objective()) {
1818 const int ct_index = linear_evaluator_.NewConstraint(
1819 cp_model_.objective().domain().empty()
1822 DCHECK_EQ(0, ct_index);
1823 for (
int i = 0;
i < cp_model_.objective().vars_size(); ++
i) {
1824 const int var = cp_model_.objective().vars(
i);
1825 const int64_t coeff = cp_model_.objective().coeffs(
i);
1826 linear_evaluator_.AddTerm(ct_index, var, coeff);
1830 for (
int c = 0;
c < cp_model_.constraints_size(); ++
c) {
1831 if (ignored_constraints[c])
continue;
1832 CompileOneConstraint(cp_model_.constraints(c));
1835 for (
const ConstraintProto& ct : additional_constraints) {
1836 CompileOneConstraint(ct);
1840 std::vector<int64_t> var_max_variations(cp_model_.variables().size());
1841 for (
int var = 0; var < cp_model_.variables().size(); ++var) {
1842 const auto& domain = cp_model_.variables(var).domain();
1843 var_max_variations[var] = domain[domain.size() - 1] - domain[0];
1845 linear_evaluator_.PrecomputeCompactView(var_max_variations);
1849 if (!cp_model_.has_objective())
return false;
1850 if (linear_evaluator_.ReduceBounds(0, lb, ub)) {
1859 linear_evaluator_.ComputeInitialActivities(
solution);
1862 for (
const auto& ct : constraints_) {
1870 absl::Span<const int64_t>
solution) {
1872 for (
const auto& ct : constraints_) {
1878 int var, int64_t old_value, absl::Span<const int64_t> new_solution) {
1879 for (
const int general_ct_index : var_to_constraints_[var]) {
1880 const int c = general_ct_index + linear_evaluator_.num_constraints();
1881 const int64_t v0 = constraints_[general_ct_index]->violation();
1882 constraints_[general_ct_index]->PerformMove(var, old_value, new_solution);
1883 const int64_t violation_delta =
1884 constraints_[general_ct_index]->violation() - v0;
1885 if (violation_delta != 0) {
1886 last_update_violation_changes_.push_back(c);
1893 absl::Span<const double> weights,
1894 absl::Span<const int64_t> jump_deltas,
1895 absl::Span<double> jump_scores) {
1897 if (old_value == new_value)
return;
1898 last_update_violation_changes_.clear();
1899 linear_evaluator_.ClearAffectedVariables();
1900 linear_evaluator_.UpdateVariableAndScores(var, new_value - old_value, weights,
1901 jump_deltas, jump_scores,
1902 &last_update_violation_changes_);
1907 dtime_ += 1e-8 * last_update_violation_changes_.size();
1908 for (
const int c : last_update_violation_changes_) {
1914 int64_t evaluation = 0;
1917 for (
int i = 0;
i < linear_evaluator_.num_constraints(); ++
i) {
1918 evaluation += linear_evaluator_.Violation(
i);
1919 DCHECK_GE(linear_evaluator_.Violation(
i), 0);
1923 for (
const auto& ct : constraints_) {
1924 evaluation += ct->violation();
1925 DCHECK_GE(ct->violation(), 0);
1931 DCHECK(cp_model_.has_objective());
1932 return linear_evaluator_.Activity(0);
1936 return linear_evaluator_.num_constraints();
1940 return static_cast<int>(constraints_.size());
1944 return linear_evaluator_.num_constraints() +
1945 static_cast<int>(constraints_.size());
1950 for (
int c = 0; c < linear_evaluator_.num_constraints(); ++c) {
1951 if (linear_evaluator_.Violation(c) > 0) {
1955 for (
const auto& constraint : constraints_) {
1956 if (constraint->violation() > 0) {
1964 if (c < linear_evaluator_.num_constraints()) {
1965 return linear_evaluator_.Violation(c);
1967 return constraints_[c - linear_evaluator_.num_constraints()]->violation();
1972 if (c < linear_evaluator_.num_constraints()) {
1973 return linear_evaluator_.IsViolated(c);
1975 return constraints_[c - linear_evaluator_.num_constraints()]->violation() >
1982 double result = linear_evaluator_.WeightedViolation(weights);
1984 const int num_linear_constraints = linear_evaluator_.num_constraints();
1985 for (
int c = 0; c < constraints_.size(); ++c) {
1986 result +=
static_cast<double>(constraints_[c]->violation()) *
1987 weights[num_linear_constraints + c];
1993 bool linear_only, absl::Span<const double> weights,
int var, int64_t delta,
1994 absl::Span<int64_t> mutable_solution)
const {
1995 double result = linear_evaluator_.WeightedViolationDelta(weights, var, delta);
1996 if (linear_only)
return result;
1999 const int64_t old_value = mutable_solution[var];
2000 mutable_solution[var] += delta;
2002 const int num_linear_constraints = linear_evaluator_.num_constraints();
2003 for (
const int ct_index : var_to_constraints_[var]) {
2006 dtime_ += 1e-8 *
static_cast<double>(constraint_to_vars_[ct_index].size());
2008 DCHECK_LT(ct_index, constraints_.size());
2009 const int64_t ct_delta = constraints_[ct_index]->ViolationDelta(
2010 var, old_value, mutable_solution);
2011 result +=
static_cast<double>(ct_delta) *
2012 weights[ct_index + num_linear_constraints];
2016 mutable_solution[var] = old_value;
2022 return jump_value_optimal_[var];
2026 num_violated_constraint_per_var_ignoring_objective_.assign(
2027 cp_model_.variables_size(), 0);
2028 violated_constraints_.clear();
2029 const int num_constraints =
2031 for (
int c = 0; c < num_constraints; ++c) {
2038 auto [it, inserted] = violated_constraints_.insert(c);
2040 if (!inserted)
return;
2044 num_violated_constraint_per_var_ignoring_objective_[v] += 1;
2048 if (violated_constraints_.erase(c) == 1) {
2052 num_violated_constraint_per_var_ignoring_objective_[v] -= 1;
2057int64_t CompiledReservoirConstraint::BuildProfileAndReturnViolation(
2058 absl::Span<const int64_t>
solution) {
2060 capacity_value_ = ExprValue(capacity_,
solution);
2061 const int num_events = time_values_.size();
2063 for (
int i = 0;
i < num_events; ++
i) {
2064 time_values_[
i] = ExprValue(times_[
i],
solution);
2065 if (is_active_[
i] != std::nullopt &&
2066 LiteralValue(*is_active_[
i],
solution) == 0) {
2067 demand_values_[
i] = 0;
2069 demand_values_[
i] = ExprValue(demands_[
i],
solution);
2070 if (demand_values_[
i] != 0) {
2071 profile_.push_back({time_values_[
i], demand_values_[
i]});
2076 if (profile_.empty())
return 0;
2077 absl::c_sort(profile_);
2082 for (
int i = 1;
i < profile_.size(); ++
i) {
2083 if (profile_[
i].time == profile_[p].time) {
2084 profile_[p].demand += profile_[
i].demand;
2086 profile_[++p] = profile_[
i];
2089 profile_.resize(p + 1);
2092 int64_t overload = 0;
2093 int64_t current_load = 0;
2094 int64_t previous_time = std::numeric_limits<int64_t>::min();
2095 for (
int i = 0;
i < profile_.size(); ++
i) {
2097 const int64_t time = profile_[
i].time;
2098 if (current_load > capacity_value_) {
2099 overload =
CapAdd(overload,
CapProd(current_load - capacity_value_,
2100 time - previous_time));
2103 current_load += profile_[
i].demand;
2104 previous_time = time;
2109int64_t CompiledReservoirConstraint::IncrementalViolation(
2110 int var, absl::Span<const int64_t>
solution) {
2111 const int64_t capacity = ExprValue(capacity_,
solution);
2112 profile_delta_.clear();
2114 for (
const int i : dense_index_to_events_[var_to_dense_index_.at(var)]) {
2115 const int64_t time = ExprValue(times_[
i],
solution);
2117 if (is_active_[
i] == std::nullopt ||
2118 LiteralValue(*is_active_[
i],
solution) == 1) {
2119 demand = ExprValue(demands_[
i],
solution);
2122 if (time == time_values_[
i]) {
2123 if (demand != demand_values_[
i]) {
2125 profile_delta_.push_back({time, demand - demand_values_[
i]});
2129 if (demand_values_[
i] != 0) {
2130 profile_delta_.push_back({time_values_[
i], -demand_values_[
i]});
2134 profile_delta_.push_back({time, demand});
2142 if (capacity == capacity_value_ && profile_delta_.empty()) {
2145 absl::c_sort(profile_delta_);
2148 int64_t overload = 0;
2149 int64_t current_load = 0;
2150 int64_t previous_time = std::numeric_limits<int64_t>::min();
2158 const absl::Span<const Event> i_profile(profile_);
2159 const absl::Span<const Event> j_profile(profile_delta_);
2162 if (
i < i_profile.size() && j < j_profile.size()) {
2163 time = std::min(i_profile[
i].time, j_profile[j].time);
2164 }
else if (
i < i_profile.size()) {
2165 time = i_profile[
i].time;
2166 }
else if (j < j_profile.size()) {
2167 time = j_profile[j].time;
2175 if (current_load > capacity) {
2176 overload =
CapAdd(overload,
2177 CapProd(current_load - capacity, time - previous_time));
2181 while (
i < i_profile.size() && i_profile[
i].time == time) {
2182 current_load += i_profile[
i].demand;
2187 while (j < j_profile.size() && j_profile[j].time == time) {
2188 current_load += j_profile[j].demand;
2192 previous_time = time;
2197void CompiledReservoirConstraint::AppendVariablesForEvent(
2198 int i, std::vector<int>* result)
const {
2199 if (is_active_[
i] != std::nullopt) {
2202 for (
const int var : times_[
i].vars()) {
2205 for (
const int var : demands_[
i].vars()) {
2210void CompiledReservoirConstraint::InitializeDenseIndexToEvents() {
2213 CpModelProto unused;
2214 int num_dense_indices = 0;
2216 var_to_dense_index_[var] = num_dense_indices++;
2219 CompactVectorVector<int, int> event_to_dense_indices;
2220 event_to_dense_indices.reserve(times_.size());
2221 const int num_events = times_.size();
2222 std::vector<int> result;
2223 for (
int i = 0;
i < num_events; ++
i) {
2225 AppendVariablesForEvent(
i, &result);
2228 for (
int& var : result) {
2229 var = var_to_dense_index_.at(var);
2232 event_to_dense_indices.Add(result);
2237 dense_index_to_events_.ResetFromTranspose(event_to_dense_indices,
2242 const CpModelProto& )
const {
2243 std::vector<int> result;
2244 const int num_events = times_.size();
2245 for (
int i = 0;
i < num_events; ++
i) {
2246 AppendVariablesForEvent(
i, &result);
2248 for (
const int var : capacity_.vars()) {
2252 result.shrink_to_fit();
std::pair< iterator, bool > insert(T value)
std::vector< int64_t > FlattenedIntervals() const
bool Contains(int64_t value) const
int64_t Distance(int64_t value) const
static Domain AllValues()
static IntegralType CeilOfRatio(IntegralType numerator, IntegralType denominator)
static IntegralType FloorOfRatio(IntegralType numerator, IntegralType denominator)
int64_t ComputeViolation(absl::Span< const int64_t > solution) override
CompiledAllDiffConstraint(const ConstraintProto &ct_proto)
--— CompiledAllDiffConstraint --—
CompiledBoolXorConstraint(const ConstraintProto &ct_proto)
--— CompiledBoolXorConstraint --—
int64_t ViolationDelta(int, int64_t, absl::Span< const int64_t > solution_with_new_value) override
Returns the delta if var changes from old_value to solution[var].
int64_t ComputeViolation(absl::Span< const int64_t > solution) override
void PerformMove(int var, int64_t old_value, absl::Span< const int64_t > new_solution) override
Updates the violation with the new value.
int64_t ComputeViolation(absl::Span< const int64_t > solution) override
~CompiledCircuitConstraint() override=default
int64_t ViolationDelta(int var, int64_t old_value, absl::Span< const int64_t > solution_with_new_value) override
Returns the delta if var changes from old_value to solution[var].
CompiledCircuitConstraint(const ConstraintProto &ct_proto)
CompiledConstraintWithProto(const ConstraintProto &ct_proto)
--— CompiledConstraintWithProto --—
std::vector< int > UsedVariables(const CpModelProto &model_proto) const final
This just returns the variables used by the stored ct_proto_.
const ConstraintProto & ct_proto() const
int64_t violation() const
The cached violation of this constraint.
virtual void PerformMove(int var, int64_t old_value, absl::Span< const int64_t > solution_with_new_value)
Updates the violation with the new value.
virtual int64_t ComputeViolation(absl::Span< const int64_t > solution)=0
void InitializeViolation(absl::Span< const int64_t > solution)
Recomputes the violation of the constraint from scratch.
virtual int64_t ViolationDelta(int var, int64_t old_value, absl::Span< const int64_t > solution_with_new_value)
Returns the delta if var changes from old_value to solution[var].
CompiledIntDivConstraint(const ConstraintProto &ct_proto)
--— CompiledIntDivConstraint --—
int64_t ComputeViolation(absl::Span< const int64_t > solution) override
int64_t ComputeViolation(absl::Span< const int64_t > solution) override
CompiledIntModConstraint(const ConstraintProto &ct_proto)
--— CompiledIntModConstraint --—
CompiledIntProdConstraint(const ConstraintProto &ct_proto)
--— CompiledIntProdConstraint --—
int64_t ComputeViolation(absl::Span< const int64_t > solution) override
int64_t ComputeViolation(absl::Span< const int64_t > solution) override
CompiledLinMaxConstraint(const ConstraintProto &ct_proto)
--— CompiledLinMaxConstraint --—
int64_t ComputeViolation(absl::Span< const int64_t > solution) override
CompiledNoOverlap2dConstraint(const ConstraintProto &ct_proto, const CpModelProto &cp_model)
std::vector< int > UsedVariables(const CpModelProto &model_proto) const final
void UpdateScoreOnWeightUpdate(int c, absl::Span< const int64_t > jump_deltas, absl::Span< double > var_to_score_change)
Also for feasibility jump.
void AddOffset(int ct_index, int64_t offset)
double WeightedViolationDelta(absl::Span< const double > weights, int var, int64_t delta) const
bool IsViolated(int c) const
void ComputeInitialActivities(absl::Span< const int64_t > solution)
Compute activities.
void AddLiteral(int ct_index, int lit, int64_t coeff=1)
int NewConstraint(Domain domain)
Returns the index of the new constraint.
double WeightedViolation(absl::Span< const double > weights) const
bool ReduceBounds(int c, int64_t lb, int64_t ub)
bool VarIsConsistent(int var) const
Used to DCHECK the state of the evaluator.
void ClearAffectedVariables()
int64_t Activity(int c) const
Query violation.
void UpdateVariableAndScores(int var, int64_t delta, absl::Span< const double > weights, absl::Span< const int64_t > jump_deltas, absl::Span< double > jump_scores, std::vector< int > *constraints_with_changed_violations)
bool AppearsInViolatedConstraints(int var) const
void AddLinearExpression(int ct_index, const LinearExpressionProto &expr, int64_t multiplier)
void PrecomputeCompactView(absl::Span< const int64_t > var_max_variation)
int64_t Violation(int c) const
void AddEnforcementLiteral(int ct_index, int lit)
bool ViolationChangeIsConvex(int var) const
Checks if the jump value of a variable is always optimal.
std::vector< int64_t > SlopeBreakpoints(int var, int64_t current_value, const Domain &var_domain) const
void AddTerm(int ct_index, int var, int64_t coeff, int64_t offset=0)
double WeightedViolation(absl::Span< const double > weights) const
void ComputeAllNonLinearViolations(absl::Span< const int64_t > solution)
void UpdateLinearScores(int var, int64_t old_value, int64_t new_value, absl::Span< const double > weights, absl::Span< const int64_t > jump_deltas, absl::Span< double > jump_scores)
Function specific to the linear only feasibility jump.
bool VariableOnlyInLinearConstraintWithConvexViolationChange(int var) const
Indicates if the computed jump value is always the best choice.
void ComputeAllViolations(absl::Span< const int64_t > solution)
Recomputes the violations of all constraints (resp only non-linear one).
void UpdateNonLinearViolations(int var, int64_t old_value, absl::Span< const int64_t > new_solution)
Recomputes the violations of all impacted non linear constraints.
bool ReduceObjectiveBounds(int64_t lb, int64_t ub)
int64_t SumOfViolations()
Simple summation metric for the constraint and objective violations.
int64_t ObjectiveActivity() const
Returns the objective activity in the current state.
bool IsViolated(int c) const
int64_t Violation(int c) const
void UpdateViolatedList()
absl::Span< const int > ConstraintToVars(int c) const
int NumNonLinearConstraints() const
LsEvaluator(const CpModelProto &cp_model, const SatParameters ¶ms)
The cp_model must outlive this class.
int NumInfeasibleConstraints() const
double WeightedViolationDelta(bool linear_only, absl::Span< const double > weights, int var, int64_t delta, absl::Span< int64_t > mutable_solution) const
void RecomputeViolatedList(bool linear_only)
bool IsObjectiveConstraint(int c) const
int NumLinearConstraints() const
int NumEvaluatorConstraints() const
std::vector< int > UsedVariables(const CpModelProto &model_proto) const final
NoOverlapBetweenTwoIntervals(int interval_0, int interval_1, const CpModelProto &cp_model)
--— NoOverlapBetweenTwoIntervals --—
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
void STLClearObject(T *obj)
void AddCircuitFlowConstraints(LinearIncrementalEvaluator &linear_evaluator, const ConstraintProto &ct_proto)
bool RefIsPositive(int ref)
int64_t OverlapOfTwoIntervals(const ConstraintProto &interval1, const ConstraintProto &interval2, absl::Span< const int64_t > solution)
--— CompiledNoOverlap2dConstraint --—
std::vector< int > UsedVariables(const ConstraintProto &ct)
std::vector< int > UsedIntervals(const ConstraintProto &ct)
Returns the sorted list of interval used by a constraint.
int64_t NoOverlapMinRepairDistance(const ConstraintProto &interval1, const ConstraintProto &interval2, absl::Span< const int64_t > solution)
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
Reads a Domain from the domain field of a proto.
int NegatedRef(int ref)
Small utility functions to deal with negative variable/literal references.
In SWIG mode, we don't want anything besides these top-level includes.
int64_t CapAdd(int64_t x, int64_t y)
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
int64_t CapSub(int64_t x, int64_t y)
int64_t CapProd(int64_t x, int64_t y)
int64_t Max() const
Returns the max of the domain.
int64_t Min() const
Returns the min of the domain.