21 #include "absl/container/flat_hash_map.h"
22 #include "absl/strings/str_cat.h"
23 #include "absl/strings/str_format.h"
36 ABSL_FLAG(
bool, cp_disable_expression_optimization,
false,
37 "Disable special optimization when creating expressions.");
39 "Share IntConst's with the same value.");
42 #pragma warning(disable : 4351 4355)
60 :
IntExpr(s), index_(s->GetNewIntVarIndex()) {
81 if (mi > 1 || ma < 0 || mi > ma) {
105 if (l <= 0 && u >= 1) {
129 return ((v == 0 &&
value_ != 1) || (v == 1 &&
value_ != 0));
133 if (constant > 1 || constant < 0) {
144 if (constant > 1 || constant < 0) {
157 }
else if (constant <= 0) {
167 }
else if (constant >= 1) {
176 const std::string& var_name =
name();
177 if (!var_name.empty()) {
178 out = var_name +
"(";
202 class DomainIntVar :
public IntVar {
210 ~BitSetIterator()
override {}
217 bool Ok()
const {
return current_ <= max_; }
224 bitset_,
current_ - omin_, max_ - omin_) +
229 std::string DebugString()
const override {
return "BitSetIterator"; }
238 class BitSet :
public BaseObject {
240 explicit BitSet(Solver*
const s) :
solver_(s), holes_stamp_(0) {}
241 ~BitSet()
override {}
245 virtual bool Contains(
int64 val)
const = 0;
246 virtual bool SetValue(
int64 val) = 0;
247 virtual bool RemoveValue(
int64 val) = 0;
248 virtual uint64 Size()
const = 0;
249 virtual void DelayRemoveValue(
int64 val) = 0;
250 virtual void ApplyRemovedValues(DomainIntVar*
var) = 0;
251 virtual void ClearRemovedValues() = 0;
253 virtual BitSetIterator* MakeIterator() = 0;
257 if (holes_stamp_ < current_stamp) {
259 holes_stamp_ = current_stamp;
263 virtual void ClearHoles() {
holes_.clear(); }
265 const std::vector<int64>& Holes() {
return holes_; }
269 int NumHoles()
const {
277 std::vector<int64>
holes_;
281 class QueueHandler :
public Demon {
283 explicit QueueHandler(DomainIntVar*
const var) : var_(
var) {}
284 ~QueueHandler()
override {}
285 void Run(Solver*
const s)
override {
286 s->GetPropagationMonitor()->StartProcessingIntegerVariable(var_);
288 s->GetPropagationMonitor()->EndProcessingIntegerVariable(var_);
293 std::string DebugString()
const override {
294 return absl::StrFormat(
"Handler(%s)", var_->DebugString());
298 DomainIntVar*
const var_;
309 RevIntPtrMap(Solver*
const solver,
int64 rmin,
int64 rmax)
310 :
solver_(solver), range_min_(rmin), start_(0) {}
314 bool Empty()
const {
return start_.
Value() == elements_.size(); }
316 void SortActive() { std::sort(elements_.begin(), elements_.end()); }
322 elements_.push_back(std::make_pair(
value, elem));
325 [
this,
value](Solver* s) { Uninsert(
value); },
false);
330 for (
int pos = start_.
Value(); pos < elements_.size(); ++pos) {
331 if (elements_[pos].first ==
value) {
332 if (position !=
nullptr) *position = pos;
333 return At(pos).second;
341 const int start = start_.
Value();
344 if (position > start) {
347 const std::pair<int64, T*> copy = elements_[start];
348 elements_[start] = elements_[position];
349 elements_[position] = copy;
354 const std::pair<int64, T*>& At(
int position)
const {
357 return elements_[position];
362 int start()
const {
return start_.
Value(); }
363 int end()
const {
return elements_.size(); }
365 int Size()
const {
return elements_.size() - start_.
Value(); }
369 for (
int pos = 0; pos < elements_.size(); ++pos) {
370 if (elements_[pos].first ==
value) {
372 const int last = elements_.size() - 1;
374 elements_[pos] = elements_.back();
376 elements_.pop_back();
380 LOG(
FATAL) <<
"The element should have been removed";
385 const int64 range_min_;
386 NumericalRev<int> start_;
387 std::vector<std::pair<int64, T*>> elements_;
391 class BaseValueWatcher :
public Constraint {
393 explicit BaseValueWatcher(Solver*
const solver) : Constraint(solver) {}
395 ~BaseValueWatcher()
override {}
397 virtual IntVar* GetOrMakeValueWatcher(
int64 value) = 0;
399 virtual void SetValueWatcher(IntVar*
const boolvar,
int64 value) = 0;
404 class ValueWatcher :
public BaseValueWatcher {
406 class WatchDemon :
public Demon {
408 WatchDemon(ValueWatcher*
const watcher,
int64 value, IntVar*
var)
409 : value_watcher_(watcher), value_(
value), var_(
var) {}
410 ~WatchDemon()
override {}
412 void Run(Solver*
const solver)
override {
413 value_watcher_->ProcessValueWatcher(value_, var_);
417 ValueWatcher*
const value_watcher_;
422 class VarDemon :
public Demon {
424 explicit VarDemon(ValueWatcher*
const watcher)
425 : value_watcher_(watcher) {}
427 ~VarDemon()
override {}
429 void Run(Solver*
const solver)
override { value_watcher_->ProcessVar(); }
432 ValueWatcher*
const value_watcher_;
435 ValueWatcher(Solver*
const solver, DomainIntVar*
const variable)
436 : BaseValueWatcher(solver),
438 hole_iterator_(variable_->MakeHoleIterator(true)),
440 watchers_(solver, variable->Min(), variable->Max()) {}
442 ~ValueWatcher()
override {}
444 IntVar* GetOrMakeValueWatcher(
int64 value)
override {
445 IntVar*
const watcher = watchers_.FindPtrOrNull(
value,
nullptr);
446 if (watcher !=
nullptr)
return watcher;
447 if (variable_->Contains(
value)) {
448 if (variable_->Bound()) {
449 return solver()->MakeIntConst(1);
451 const std::string vname = variable_->HasName()
453 : variable_->DebugString();
454 const std::string bname =
455 absl::StrFormat(
"Watch<%s == %d>", vname,
value);
456 IntVar*
const boolvar = solver()->MakeBoolVar(bname);
457 watchers_.UnsafeRevInsert(
value, boolvar);
458 if (posted_.Switched()) {
460 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
461 var_demon_->desinhibit(solver());
466 return variable_->solver()->MakeIntConst(0);
470 void SetValueWatcher(IntVar*
const boolvar,
int64 value)
override {
471 CHECK(watchers_.FindPtrOrNull(
value,
nullptr) ==
nullptr);
472 if (!boolvar->Bound()) {
473 watchers_.UnsafeRevInsert(
value, boolvar);
474 if (posted_.Switched() && !boolvar->Bound()) {
476 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
477 var_demon_->desinhibit(solver());
482 void Post()
override {
483 var_demon_ = solver()->RevAlloc(
new VarDemon(
this));
484 variable_->WhenDomain(var_demon_);
485 for (
int pos = watchers_.start(); pos < watchers_.end(); ++pos) {
486 const std::pair<int64, IntVar*>& w = watchers_.At(pos);
488 IntVar*
const boolvar = w.second;
489 if (!boolvar->Bound() && variable_->Contains(
value)) {
491 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
494 posted_.Switch(solver());
497 void InitialPropagate()
override {
498 if (variable_->Bound()) {
501 for (
int pos = watchers_.start(); pos < watchers_.end(); ++pos) {
502 const std::pair<int64, IntVar*>& w = watchers_.At(pos);
504 IntVar*
const boolvar = w.second;
505 if (!variable_->Contains(
value)) {
506 boolvar->SetValue(0);
507 watchers_.RemoveAt(pos);
509 if (boolvar->Bound()) {
510 ProcessValueWatcher(
value, boolvar);
511 watchers_.RemoveAt(pos);
519 void ProcessValueWatcher(
int64 value, IntVar* boolvar) {
520 if (boolvar->Min() == 0) {
521 if (variable_->Size() < 0xFFFFFF) {
522 variable_->RemoveValue(
value);
525 solver()->AddConstraint(solver()->MakeNonEquality(variable_,
value));
528 variable_->SetValue(
value);
533 const int kSmallList = 16;
534 if (variable_->Bound()) {
536 }
else if (watchers_.Size() <= kSmallList ||
537 variable_->Min() != variable_->OldMin() ||
538 variable_->Max() != variable_->OldMax()) {
548 BitSet*
const bitset = variable_->bitset();
549 if (bitset !=
nullptr && !watchers_.Empty()) {
550 if (bitset->NumHoles() * 2 < watchers_.Size()) {
551 for (
const int64 hole : InitAndGetValues(hole_iterator_)) {
553 IntVar*
const boolvar = watchers_.FindPtrOrNull(hole, &pos);
554 if (boolvar !=
nullptr) {
555 boolvar->SetValue(0);
556 watchers_.RemoveAt(pos);
568 void VariableBound() {
569 DCHECK(variable_->Bound());
571 for (
int pos = watchers_.start(); pos < watchers_.end(); ++pos) {
572 const std::pair<int64, IntVar*>& w = watchers_.At(pos);
573 w.second->SetValue(w.first ==
value);
575 watchers_.RemoveAll();
576 var_demon_->inhibit(solver());
580 void ScanWatchers() {
581 for (
int pos = watchers_.start(); pos < watchers_.end(); ++pos) {
582 const std::pair<int64, IntVar*>& w = watchers_.At(pos);
583 if (!variable_->Contains(w.first)) {
584 IntVar*
const boolvar = w.second;
585 boolvar->SetValue(0);
586 watchers_.RemoveAt(pos);
593 void CheckInhibit() {
594 if (watchers_.Empty()) {
595 var_demon_->inhibit(solver());
599 void Accept(ModelVisitor*
const visitor)
const override {
603 std::vector<int64> all_coefficients;
604 std::vector<IntVar*> all_bool_vars;
605 for (
int position = watchers_.start(); position < watchers_.end();
607 const std::pair<int64, IntVar*>& w = watchers_.At(position);
608 all_coefficients.push_back(w.first);
609 all_bool_vars.push_back(w.second);
618 std::string DebugString()
const override {
619 return absl::StrFormat(
"ValueWatcher(%s)", variable_->DebugString());
623 DomainIntVar*
const variable_;
624 IntVarIterator*
const hole_iterator_;
627 RevIntPtrMap<IntVar> watchers_;
631 class DenseValueWatcher :
public BaseValueWatcher {
633 class WatchDemon :
public Demon {
635 WatchDemon(DenseValueWatcher*
const watcher,
int64 value, IntVar*
var)
636 : value_watcher_(watcher), value_(
value), var_(
var) {}
637 ~WatchDemon()
override {}
639 void Run(Solver*
const solver)
override {
640 value_watcher_->ProcessValueWatcher(value_, var_);
644 DenseValueWatcher*
const value_watcher_;
649 class VarDemon :
public Demon {
651 explicit VarDemon(DenseValueWatcher*
const watcher)
652 : value_watcher_(watcher) {}
654 ~VarDemon()
override {}
656 void Run(Solver*
const solver)
override { value_watcher_->ProcessVar(); }
659 DenseValueWatcher*
const value_watcher_;
662 DenseValueWatcher(Solver*
const solver, DomainIntVar*
const variable)
663 : BaseValueWatcher(solver),
665 hole_iterator_(variable_->MakeHoleIterator(true)),
668 watchers_(variable->Max() - variable->Min() + 1, nullptr),
669 active_watchers_(0) {}
671 ~DenseValueWatcher()
override {}
673 IntVar* GetOrMakeValueWatcher(
int64 value)
override {
675 if (value < offset_ || value > var_max) {
676 return solver()->MakeIntConst(0);
679 IntVar*
const watcher = watchers_[
index];
680 if (watcher !=
nullptr)
return watcher;
681 if (variable_->Contains(
value)) {
682 if (variable_->Bound()) {
683 return solver()->MakeIntConst(1);
685 const std::string vname = variable_->HasName()
687 : variable_->DebugString();
688 const std::string bname =
689 absl::StrFormat(
"Watch<%s == %d>", vname,
value);
690 IntVar*
const boolvar = solver()->MakeBoolVar(bname);
691 RevInsert(
index, boolvar);
692 if (posted_.Switched()) {
694 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
695 var_demon_->desinhibit(solver());
700 return variable_->solver()->MakeIntConst(0);
704 void SetValueWatcher(IntVar*
const boolvar,
int64 value)
override {
707 if (!boolvar->Bound()) {
708 RevInsert(
index, boolvar);
709 if (posted_.Switched() && !boolvar->Bound()) {
711 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
712 var_demon_->desinhibit(solver());
717 void Post()
override {
718 var_demon_ = solver()->RevAlloc(
new VarDemon(
this));
719 variable_->WhenDomain(var_demon_);
720 for (
int pos = 0; pos < watchers_.size(); ++pos) {
722 IntVar*
const boolvar = watchers_[pos];
723 if (boolvar !=
nullptr && !boolvar->Bound() &&
724 variable_->Contains(
value)) {
726 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
729 posted_.Switch(solver());
732 void InitialPropagate()
override {
733 if (variable_->Bound()) {
736 for (
int pos = 0; pos < watchers_.size(); ++pos) {
737 IntVar*
const boolvar = watchers_[pos];
738 if (boolvar ==
nullptr)
continue;
740 if (!variable_->Contains(
value)) {
741 boolvar->SetValue(0);
743 }
else if (boolvar->Bound()) {
744 ProcessValueWatcher(
value, boolvar);
748 if (active_watchers_.
Value() == 0) {
749 var_demon_->inhibit(solver());
754 void ProcessValueWatcher(
int64 value, IntVar* boolvar) {
755 if (boolvar->Min() == 0) {
756 variable_->RemoveValue(
value);
758 variable_->SetValue(
value);
763 if (variable_->Bound()) {
768 if (active_watchers_.
Value() == 0) {
769 var_demon_->inhibit(solver());
775 void VariableBound() {
776 DCHECK(variable_->Bound());
778 for (
int pos = 0; pos < watchers_.size(); ++pos) {
779 IntVar*
const boolvar = watchers_[pos];
780 if (boolvar !=
nullptr) {
785 var_demon_->inhibit(solver());
789 void ScanWatchers() {
790 const int64 old_min_index = variable_->OldMin() -
offset_;
791 const int64 old_max_index = variable_->OldMax() -
offset_;
794 for (
int pos = old_min_index; pos < min_index; ++pos) {
795 IntVar*
const boolvar = watchers_[pos];
796 if (boolvar !=
nullptr) {
797 boolvar->SetValue(0);
801 for (
int pos = max_index + 1; pos <= old_max_index; ++pos) {
802 IntVar*
const boolvar = watchers_[pos];
803 if (boolvar !=
nullptr) {
804 boolvar->SetValue(0);
808 BitSet*
const bitset = variable_->bitset();
809 if (bitset !=
nullptr) {
810 if (bitset->NumHoles() * 2 < active_watchers_.
Value()) {
811 for (
const int64 hole : InitAndGetValues(hole_iterator_)) {
812 IntVar*
const boolvar = watchers_[hole -
offset_];
813 if (boolvar !=
nullptr) {
814 boolvar->SetValue(0);
819 for (
int pos = min_index + 1; pos < max_index; ++pos) {
820 IntVar*
const boolvar = watchers_[pos];
821 if (boolvar !=
nullptr && !variable_->Contains(
offset_ + pos)) {
822 boolvar->SetValue(0);
830 void RevRemove(
int pos) {
831 solver()->SaveValue(
reinterpret_cast<void**
>(&watchers_[pos]));
832 watchers_[pos] =
nullptr;
833 active_watchers_.
Decr(solver());
836 void RevInsert(
int pos, IntVar* boolvar) {
837 solver()->SaveValue(
reinterpret_cast<void**
>(&watchers_[pos]));
838 watchers_[pos] = boolvar;
839 active_watchers_.
Incr(solver());
842 void Accept(ModelVisitor*
const visitor)
const override {
846 std::vector<int64> all_coefficients;
847 std::vector<IntVar*> all_bool_vars;
848 for (
int position = 0; position < watchers_.size(); ++position) {
849 if (watchers_[position] !=
nullptr) {
850 all_coefficients.push_back(position +
offset_);
851 all_bool_vars.push_back(watchers_[position]);
861 std::string DebugString()
const override {
862 return absl::StrFormat(
"DenseValueWatcher(%s)", variable_->DebugString());
866 DomainIntVar*
const variable_;
867 IntVarIterator*
const hole_iterator_;
871 std::vector<IntVar*> watchers_;
872 NumericalRev<int> active_watchers_;
875 class BaseUpperBoundWatcher :
public Constraint {
877 explicit BaseUpperBoundWatcher(Solver*
const solver) : Constraint(solver) {}
879 ~BaseUpperBoundWatcher()
override {}
881 virtual IntVar* GetOrMakeUpperBoundWatcher(
int64 value) = 0;
883 virtual void SetUpperBoundWatcher(IntVar*
const boolvar,
int64 value) = 0;
889 class UpperBoundWatcher :
public BaseUpperBoundWatcher {
891 class WatchDemon :
public Demon {
893 WatchDemon(UpperBoundWatcher*
const watcher,
int64 index,
895 : value_watcher_(watcher), index_(
index), var_(
var) {}
896 ~WatchDemon()
override {}
898 void Run(Solver*
const solver)
override {
899 value_watcher_->ProcessUpperBoundWatcher(index_, var_);
903 UpperBoundWatcher*
const value_watcher_;
908 class VarDemon :
public Demon {
910 explicit VarDemon(UpperBoundWatcher*
const watcher)
911 : value_watcher_(watcher) {}
912 ~VarDemon()
override {}
914 void Run(Solver*
const solver)
override { value_watcher_->ProcessVar(); }
917 UpperBoundWatcher*
const value_watcher_;
920 UpperBoundWatcher(Solver*
const solver, DomainIntVar*
const variable)
921 : BaseUpperBoundWatcher(solver),
924 watchers_(solver, variable->Min(), variable->Max()),
929 ~UpperBoundWatcher()
override {}
931 IntVar* GetOrMakeUpperBoundWatcher(
int64 value)
override {
932 IntVar*
const watcher = watchers_.FindPtrOrNull(
value,
nullptr);
933 if (watcher !=
nullptr) {
936 if (variable_->Max() >=
value) {
937 if (variable_->Min() >=
value) {
938 return solver()->MakeIntConst(1);
940 const std::string vname = variable_->HasName()
942 : variable_->DebugString();
943 const std::string bname =
944 absl::StrFormat(
"Watch<%s >= %d>", vname,
value);
945 IntVar*
const boolvar = solver()->MakeBoolVar(bname);
946 watchers_.UnsafeRevInsert(
value, boolvar);
947 if (posted_.Switched()) {
949 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
950 var_demon_->desinhibit(solver());
956 return variable_->solver()->MakeIntConst(0);
960 void SetUpperBoundWatcher(IntVar*
const boolvar,
int64 value)
override {
961 CHECK(watchers_.FindPtrOrNull(
value,
nullptr) ==
nullptr);
962 watchers_.UnsafeRevInsert(
value, boolvar);
963 if (posted_.Switched() && !boolvar->Bound()) {
965 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
966 var_demon_->desinhibit(solver());
971 void Post()
override {
972 const int kTooSmallToSort = 8;
973 var_demon_ = solver()->RevAlloc(
new VarDemon(
this));
974 variable_->WhenRange(var_demon_);
976 if (watchers_.Size() > kTooSmallToSort) {
977 watchers_.SortActive();
979 start_.
SetValue(solver(), watchers_.start());
980 end_.
SetValue(solver(), watchers_.end() - 1);
983 for (
int pos = watchers_.start(); pos < watchers_.end(); ++pos) {
984 const std::pair<int64, IntVar*>& w = watchers_.At(pos);
985 IntVar*
const boolvar = w.second;
987 if (!boolvar->Bound() &&
value > variable_->Min() &&
988 value <= variable_->Max()) {
990 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
993 posted_.Switch(solver());
996 void InitialPropagate()
override {
997 const int64 var_min = variable_->Min();
998 const int64 var_max = variable_->Max();
1001 const std::pair<int64, IntVar*>& w = watchers_.At(start_.
Value());
1002 if (w.first <= var_min) {
1003 w.second->SetValue(1);
1004 start_.
Incr(solver());
1010 const std::pair<int64, IntVar*>& w = watchers_.At(end_.
Value());
1011 if (w.first > var_max) {
1012 w.second->SetValue(0);
1013 end_.
Decr(solver());
1018 for (
int i = start_.
Value(); i <= end_.
Value(); ++i) {
1019 const std::pair<int64, IntVar*>& w = watchers_.At(i);
1020 if (w.second->Bound()) {
1021 ProcessUpperBoundWatcher(w.first, w.second);
1025 var_demon_->inhibit(solver());
1028 for (
int pos = watchers_.start(); pos < watchers_.end(); ++pos) {
1029 const std::pair<int64, IntVar*>& w = watchers_.At(pos);
1031 IntVar*
const boolvar = w.second;
1033 if (
value <= var_min) {
1034 boolvar->SetValue(1);
1035 watchers_.RemoveAt(pos);
1036 }
else if (
value > var_max) {
1037 boolvar->SetValue(0);
1038 watchers_.RemoveAt(pos);
1039 }
else if (boolvar->Bound()) {
1040 ProcessUpperBoundWatcher(
value, boolvar);
1041 watchers_.RemoveAt(pos);
1047 void Accept(ModelVisitor*
const visitor)
const override {
1051 std::vector<int64> all_coefficients;
1052 std::vector<IntVar*> all_bool_vars;
1053 for (
int pos = watchers_.start(); pos < watchers_.end(); ++pos) {
1054 const std::pair<int64, IntVar*>& w = watchers_.At(pos);
1055 all_coefficients.push_back(w.first);
1056 all_bool_vars.push_back(w.second);
1065 std::string DebugString()
const override {
1066 return absl::StrFormat(
"UpperBoundWatcher(%s)", variable_->DebugString());
1070 void ProcessUpperBoundWatcher(
int64 value, IntVar*
const boolvar) {
1071 if (boolvar->Min() == 0) {
1072 variable_->SetMax(
value - 1);
1074 variable_->SetMin(
value);
1079 const int64 var_min = variable_->Min();
1080 const int64 var_max = variable_->Max();
1083 const std::pair<int64, IntVar*>& w = watchers_.At(start_.
Value());
1084 if (w.first <= var_min) {
1085 w.second->SetValue(1);
1086 start_.
Incr(solver());
1092 const std::pair<int64, IntVar*>& w = watchers_.At(end_.
Value());
1093 if (w.first > var_max) {
1094 w.second->SetValue(0);
1095 end_.
Decr(solver());
1101 var_demon_->inhibit(solver());
1104 for (
int pos = watchers_.start(); pos < watchers_.end(); ++pos) {
1105 const std::pair<int64, IntVar*>& w = watchers_.At(pos);
1107 IntVar*
const boolvar = w.second;
1109 if (
value <= var_min) {
1110 boolvar->SetValue(1);
1111 watchers_.RemoveAt(pos);
1112 }
else if (
value > var_max) {
1113 boolvar->SetValue(0);
1114 watchers_.RemoveAt(pos);
1117 if (watchers_.Empty()) {
1118 var_demon_->inhibit(solver());
1123 DomainIntVar*
const variable_;
1126 RevIntPtrMap<IntVar> watchers_;
1127 NumericalRev<int> start_;
1128 NumericalRev<int> end_;
1133 class DenseUpperBoundWatcher :
public BaseUpperBoundWatcher {
1135 class WatchDemon :
public Demon {
1137 WatchDemon(DenseUpperBoundWatcher*
const watcher,
int64 value,
1139 : value_watcher_(watcher), value_(
value), var_(
var) {}
1140 ~WatchDemon()
override {}
1142 void Run(Solver*
const solver)
override {
1143 value_watcher_->ProcessUpperBoundWatcher(value_, var_);
1147 DenseUpperBoundWatcher*
const value_watcher_;
1152 class VarDemon :
public Demon {
1154 explicit VarDemon(DenseUpperBoundWatcher*
const watcher)
1155 : value_watcher_(watcher) {}
1157 ~VarDemon()
override {}
1159 void Run(Solver*
const solver)
override { value_watcher_->ProcessVar(); }
1162 DenseUpperBoundWatcher*
const value_watcher_;
1165 DenseUpperBoundWatcher(Solver*
const solver, DomainIntVar*
const variable)
1166 : BaseUpperBoundWatcher(solver),
1167 variable_(variable),
1168 var_demon_(nullptr),
1170 watchers_(variable->Max() - variable->Min() + 1, nullptr),
1171 active_watchers_(0) {}
1173 ~DenseUpperBoundWatcher()
override {}
1175 IntVar* GetOrMakeUpperBoundWatcher(
int64 value)
override {
1176 if (variable_->Max() >=
value) {
1177 if (variable_->Min() >=
value) {
1178 return solver()->MakeIntConst(1);
1180 const std::string vname = variable_->HasName()
1182 : variable_->DebugString();
1183 const std::string bname =
1184 absl::StrFormat(
"Watch<%s >= %d>", vname,
value);
1185 IntVar*
const boolvar = solver()->MakeBoolVar(bname);
1187 if (posted_.Switched()) {
1189 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
1190 var_demon_->desinhibit(solver());
1195 return variable_->solver()->MakeIntConst(0);
1199 void SetUpperBoundWatcher(IntVar*
const boolvar,
int64 value)
override {
1202 if (!boolvar->Bound()) {
1203 RevInsert(
index, boolvar);
1204 if (posted_.Switched() && !boolvar->Bound()) {
1206 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
1207 var_demon_->desinhibit(solver());
1212 void Post()
override {
1213 var_demon_ = solver()->RevAlloc(
new VarDemon(
this));
1214 variable_->WhenRange(var_demon_);
1215 for (
int pos = 0; pos < watchers_.size(); ++pos) {
1217 IntVar*
const boolvar = watchers_[pos];
1218 if (boolvar !=
nullptr && !boolvar->Bound() &&
1219 value > variable_->Min() && value <= variable_->Max()) {
1221 solver()->RevAlloc(
new WatchDemon(
this,
value, boolvar)));
1224 posted_.Switch(solver());
1227 void InitialPropagate()
override {
1228 for (
int pos = 0; pos < watchers_.size(); ++pos) {
1229 IntVar*
const boolvar = watchers_[pos];
1230 if (boolvar ==
nullptr)
continue;
1232 if (value <= variable_->Min()) {
1233 boolvar->SetValue(1);
1235 }
else if (
value > variable_->Max()) {
1236 boolvar->SetValue(0);
1238 }
else if (boolvar->Bound()) {
1239 ProcessUpperBoundWatcher(
value, boolvar);
1243 if (active_watchers_.
Value() == 0) {
1244 var_demon_->inhibit(solver());
1248 void ProcessUpperBoundWatcher(
int64 value, IntVar* boolvar) {
1249 if (boolvar->Min() == 0) {
1250 variable_->SetMax(
value - 1);
1252 variable_->SetMin(
value);
1257 const int64 old_min_index = variable_->OldMin() -
offset_;
1258 const int64 old_max_index = variable_->OldMax() -
offset_;
1261 for (
int pos = old_min_index; pos <= min_index; ++pos) {
1262 IntVar*
const boolvar = watchers_[pos];
1263 if (boolvar !=
nullptr) {
1264 boolvar->SetValue(1);
1269 for (
int pos = max_index + 1; pos <= old_max_index; ++pos) {
1270 IntVar*
const boolvar = watchers_[pos];
1271 if (boolvar !=
nullptr) {
1272 boolvar->SetValue(0);
1276 if (active_watchers_.
Value() == 0) {
1277 var_demon_->inhibit(solver());
1281 void RevRemove(
int pos) {
1282 solver()->SaveValue(
reinterpret_cast<void**
>(&watchers_[pos]));
1283 watchers_[pos] =
nullptr;
1284 active_watchers_.
Decr(solver());
1287 void RevInsert(
int pos, IntVar* boolvar) {
1288 solver()->SaveValue(
reinterpret_cast<void**
>(&watchers_[pos]));
1289 watchers_[pos] = boolvar;
1290 active_watchers_.
Incr(solver());
1293 void Accept(ModelVisitor*
const visitor)
const override {
1297 std::vector<int64> all_coefficients;
1298 std::vector<IntVar*> all_bool_vars;
1299 for (
int position = 0; position < watchers_.size(); ++position) {
1300 if (watchers_[position] !=
nullptr) {
1301 all_coefficients.push_back(position +
offset_);
1302 all_bool_vars.push_back(watchers_[position]);
1312 std::string DebugString()
const override {
1313 return absl::StrFormat(
"DenseUpperBoundWatcher(%s)",
1314 variable_->DebugString());
1318 DomainIntVar*
const variable_;
1322 std::vector<IntVar*> watchers_;
1323 NumericalRev<int> active_watchers_;
1327 DomainIntVar(Solver*
const s,
int64 vmin,
int64 vmax,
1328 const std::string&
name);
1329 DomainIntVar(Solver*
const s,
const std::vector<int64>& sorted_values,
1330 const std::string&
name);
1331 ~DomainIntVar()
override;
1333 int64 Min()
const override {
return min_.Value(); }
1334 void SetMin(
int64 m)
override;
1335 int64 Max()
const override {
return max_.Value(); }
1336 void SetMax(
int64 m)
override;
1338 void SetValue(
int64 v)
override;
1339 bool Bound()
const override {
return (min_.Value() == max_.Value()); }
1341 CHECK_EQ(min_.Value(), max_.Value())
1342 <<
" variable " << DebugString() <<
" is not bound.";
1343 return min_.Value();
1345 void RemoveValue(
int64 v)
override;
1346 void RemoveInterval(
int64 l,
int64 u)
override;
1348 void WhenBound(Demon* d)
override {
1349 if (min_.Value() != max_.Value()) {
1351 delayed_bound_demons_.PushIfNotTop(solver(),
1354 bound_demons_.PushIfNotTop(solver(), solver()->
RegisterDemon(d));
1358 void WhenRange(Demon* d)
override {
1359 if (min_.Value() != max_.Value()) {
1361 delayed_range_demons_.PushIfNotTop(solver(),
1364 range_demons_.PushIfNotTop(solver(), solver()->
RegisterDemon(d));
1368 void WhenDomain(Demon* d)
override {
1369 if (min_.Value() != max_.Value()) {
1371 delayed_domain_demons_.PushIfNotTop(solver(),
1374 domain_demons_.PushIfNotTop(solver(), solver()->
RegisterDemon(d));
1379 IntVar* IsEqual(
int64 constant)
override {
1380 Solver*
const s = solver();
1381 if (constant == min_.Value() && value_watcher_ ==
nullptr) {
1382 return s->MakeIsLessOrEqualCstVar(
this, constant);
1384 if (constant == max_.Value() && value_watcher_ ==
nullptr) {
1385 return s->MakeIsGreaterOrEqualCstVar(
this, constant);
1387 if (!Contains(constant)) {
1388 return s->MakeIntConst(
int64{0});
1390 if (Bound() && min_.Value() == constant) {
1391 return s->MakeIntConst(
int64{1});
1393 IntExpr*
const cache = s->Cache()->FindExprConstantExpression(
1395 if (cache !=
nullptr) {
1396 return cache->Var();
1398 if (value_watcher_ ==
nullptr) {
1399 if (
CapSub(Max(), Min()) <= 256) {
1400 solver()->SaveAndSetValue(
1401 reinterpret_cast<void**
>(&value_watcher_),
1402 reinterpret_cast<void*
>(
1403 solver()->RevAlloc(
new DenseValueWatcher(solver(),
this))));
1406 solver()->SaveAndSetValue(
reinterpret_cast<void**
>(&value_watcher_),
1407 reinterpret_cast<void*
>(solver()->RevAlloc(
1408 new ValueWatcher(solver(),
this))));
1410 solver()->AddConstraint(value_watcher_);
1412 IntVar*
const boolvar = value_watcher_->GetOrMakeValueWatcher(constant);
1413 s->Cache()->InsertExprConstantExpression(
1419 Constraint*
SetIsEqual(
const std::vector<int64>& values,
1420 const std::vector<IntVar*>& vars) {
1421 if (value_watcher_ ==
nullptr) {
1422 solver()->SaveAndSetValue(
reinterpret_cast<void**
>(&value_watcher_),
1423 reinterpret_cast<void*
>(solver()->RevAlloc(
1424 new ValueWatcher(solver(),
this))));
1425 for (
int i = 0; i < vars.size(); ++i) {
1426 value_watcher_->SetValueWatcher(vars[i], values[i]);
1429 return value_watcher_;
1432 IntVar* IsDifferent(
int64 constant)
override {
1433 Solver*
const s = solver();
1434 if (constant == min_.Value() && value_watcher_ ==
nullptr) {
1435 return s->MakeIsGreaterOrEqualCstVar(
this, constant + 1);
1437 if (constant == max_.Value() && value_watcher_ ==
nullptr) {
1438 return s->MakeIsLessOrEqualCstVar(
this, constant - 1);
1440 if (!Contains(constant)) {
1441 return s->MakeIntConst(
int64{1});
1443 if (Bound() && min_.Value() == constant) {
1444 return s->MakeIntConst(
int64{0});
1446 IntExpr*
const cache = s->Cache()->FindExprConstantExpression(
1448 if (cache !=
nullptr) {
1449 return cache->Var();
1451 IntVar*
const boolvar = s->MakeDifference(1, IsEqual(constant))->Var();
1452 s->Cache()->InsertExprConstantExpression(
1458 IntVar* IsGreaterOrEqual(
int64 constant)
override {
1459 Solver*
const s = solver();
1460 if (max_.Value() < constant) {
1461 return s->MakeIntConst(
int64{0});
1463 if (min_.Value() >= constant) {
1464 return s->MakeIntConst(
int64{1});
1466 IntExpr*
const cache = s->Cache()->FindExprConstantExpression(
1468 if (cache !=
nullptr) {
1469 return cache->Var();
1471 if (bound_watcher_ ==
nullptr) {
1472 if (
CapSub(Max(), Min()) <= 256) {
1473 solver()->SaveAndSetValue(
1474 reinterpret_cast<void**
>(&bound_watcher_),
1475 reinterpret_cast<void*
>(solver()->RevAlloc(
1476 new DenseUpperBoundWatcher(solver(),
this))));
1477 solver()->AddConstraint(bound_watcher_);
1479 solver()->SaveAndSetValue(
1480 reinterpret_cast<void**
>(&bound_watcher_),
1481 reinterpret_cast<void*
>(
1482 solver()->RevAlloc(
new UpperBoundWatcher(solver(),
this))));
1483 solver()->AddConstraint(bound_watcher_);
1486 IntVar*
const boolvar =
1487 bound_watcher_->GetOrMakeUpperBoundWatcher(constant);
1488 s->Cache()->InsertExprConstantExpression(
1489 boolvar,
this, constant,
1496 const std::vector<IntVar*>& vars) {
1497 if (bound_watcher_ ==
nullptr) {
1498 if (
CapSub(Max(), Min()) <= 256) {
1499 solver()->SaveAndSetValue(
1500 reinterpret_cast<void**
>(&bound_watcher_),
1501 reinterpret_cast<void*
>(solver()->RevAlloc(
1502 new DenseUpperBoundWatcher(solver(),
this))));
1503 solver()->AddConstraint(bound_watcher_);
1505 solver()->SaveAndSetValue(
reinterpret_cast<void**
>(&bound_watcher_),
1506 reinterpret_cast<void*
>(solver()->RevAlloc(
1507 new UpperBoundWatcher(solver(),
this))));
1508 solver()->AddConstraint(bound_watcher_);
1510 for (
int i = 0; i < values.size(); ++i) {
1511 bound_watcher_->SetUpperBoundWatcher(vars[i], values[i]);
1514 return bound_watcher_;
1517 IntVar* IsLessOrEqual(
int64 constant)
override {
1518 Solver*
const s = solver();
1519 IntExpr*
const cache = s->Cache()->FindExprConstantExpression(
1521 if (cache !=
nullptr) {
1522 return cache->Var();
1524 IntVar*
const boolvar =
1525 s->MakeDifference(1, IsGreaterOrEqual(constant + 1))->Var();
1526 s->Cache()->InsertExprConstantExpression(
1534 void CleanInProcess();
1535 uint64 Size()
const override {
1536 if (bits_ !=
nullptr)
return bits_->Size();
1537 return (
static_cast<uint64>(max_.Value()) -
1538 static_cast<uint64>(min_.Value()) + 1);
1540 bool Contains(
int64 v)
const override {
1541 if (v < min_.Value() || v > max_.Value())
return false;
1542 return (bits_ ==
nullptr ?
true : bits_->Contains(v));
1544 IntVarIterator* MakeHoleIterator(
bool reversible)
const override;
1545 IntVarIterator* MakeDomainIterator(
bool reversible)
const override;
1546 int64 OldMin()
const override {
return std::min(old_min_, min_.Value()); }
1547 int64 OldMax()
const override {
return std::max(old_max_, max_.Value()); }
1549 std::string DebugString()
const override;
1550 BitSet* bitset()
const {
return bits_; }
1552 std::string BaseName()
const override {
return "IntegerVar"; }
1554 friend class PlusCstDomainIntVar;
1555 friend class LinkExprAndDomainIntVar;
1558 void CheckOldMin() {
1559 if (old_min_ > min_.Value()) {
1560 old_min_ = min_.Value();
1563 void CheckOldMax() {
1564 if (old_max_ < max_.Value()) {
1565 old_max_ = max_.Value();
1574 SimpleRevFIFO<Demon*> bound_demons_;
1575 SimpleRevFIFO<Demon*> range_demons_;
1576 SimpleRevFIFO<Demon*> domain_demons_;
1577 SimpleRevFIFO<Demon*> delayed_bound_demons_;
1578 SimpleRevFIFO<Demon*> delayed_range_demons_;
1579 SimpleRevFIFO<Demon*> delayed_domain_demons_;
1583 BaseValueWatcher* value_watcher_;
1584 BaseUpperBoundWatcher* bound_watcher_;
1603 class SimpleBitSet :
public DomainIntVar::BitSet {
1605 SimpleBitSet(Solver*
const s,
int64 vmin,
int64 vmax)
1611 size_(vmax - vmin + 1),
1613 CHECK(ClosedIntervalNoLargerThan(vmin, vmax, 0xFFFFFFFF))
1614 <<
"Bitset too large: [" << vmin <<
", " << vmax <<
"]";
1615 bits_ =
new uint64[bsize_];
1616 stamps_ =
new uint64[bsize_];
1617 for (
int i = 0; i < bsize_; ++i) {
1619 (i == size_.Value() - 1) ? 63 -
BitPos64(size_.Value()) : 0;
1621 stamps_[i] = s->stamp() - 1;
1625 SimpleBitSet(Solver*
const s,
const std::vector<int64>& sorted_values,
1632 size_(sorted_values.size()),
1634 CHECK(ClosedIntervalNoLargerThan(vmin, vmax, 0xFFFFFFFF))
1635 <<
"Bitset too large: [" << vmin <<
", " << vmax <<
"]";
1636 bits_ =
new uint64[bsize_];
1637 stamps_ =
new uint64[bsize_];
1638 for (
int i = 0; i < bsize_; ++i) {
1639 bits_[i] = uint64_t{0};
1640 stamps_[i] = s->stamp() - 1;
1642 for (
int i = 0; i < sorted_values.size(); ++i) {
1643 const int64 val = sorted_values[i];
1646 const int pos =
BitPos64(val - omin_);
1651 ~SimpleBitSet()
override {
1664 const int64 new_min =
1667 const uint64 removed_bits =
1669 size_.Add(
solver_, -removed_bits);
1679 const int64 new_max =
1682 const uint64 removed_bits =
1684 size_.Add(
solver_, -removed_bits);
1688 bool SetValue(
int64 val)
override {
1698 bool Contains(
int64 val)
const override {
1704 bool RemoveValue(
int64 val)
override {
1705 if (val < omin_ || val > omax_ || !bit(val)) {
1709 const int64 val_offset = val - omin_;
1712 if (stamps_[offset] < current_stamp) {
1713 stamps_[offset] = current_stamp;
1714 solver_->SaveValue(&bits_[offset]);
1716 const int pos =
BitPos64(val_offset);
1725 uint64 Size()
const override {
return size_.Value(); }
1727 std::string DebugString()
const override {
1729 absl::StrAppendFormat(&out,
"SimpleBitSet(%d..%d : ", omin_, omax_);
1730 for (
int i = 0; i < bsize_; ++i) {
1731 absl::StrAppendFormat(&out,
"%x", bits_[i]);
1737 void DelayRemoveValue(
int64 val)
override { removed_.push_back(val); }
1739 void ApplyRemovedValues(DomainIntVar*
var)
override {
1740 std::sort(removed_.begin(), removed_.end());
1741 for (std::vector<int64>::iterator it = removed_.begin();
1742 it != removed_.end(); ++it) {
1743 var->RemoveValue(*it);
1747 void ClearRemovedValues()
override { removed_.clear(); }
1764 if (v == start_cumul + 1) {
1765 absl::StrAppendFormat(&out,
"%d ", start_cumul);
1766 }
else if (v == start_cumul + 2) {
1767 absl::StrAppendFormat(&out,
"%d %d ", start_cumul, v - 1);
1769 absl::StrAppendFormat(&out,
"%d..%d ", start_cumul, v - 1);
1776 if (
max == start_cumul + 1) {
1777 absl::StrAppendFormat(&out,
"%d %d", start_cumul,
max);
1779 absl::StrAppendFormat(&out,
"%d..%d", start_cumul,
max);
1782 absl::StrAppendFormat(&out,
"%d",
max);
1785 absl::StrAppendFormat(&out,
"%d",
min);
1790 DomainIntVar::BitSetIterator* MakeIterator()
override {
1791 return new DomainIntVar::BitSetIterator(bits_, omin_);
1799 NumericalRev<int64> size_;
1801 std::vector<int64> removed_;
1807 class SmallBitSet :
public DomainIntVar::BitSet {
1809 SmallBitSet(Solver*
const s,
int64 vmin,
int64 vmax)
1815 size_(vmax - vmin + 1) {
1816 CHECK(ClosedIntervalNoLargerThan(vmin, vmax, 64)) << vmin <<
", " << vmax;
1820 SmallBitSet(Solver*
const s,
const std::vector<int64>& sorted_values,
1827 size_(sorted_values.size()) {
1828 CHECK(ClosedIntervalNoLargerThan(vmin, vmax, 64)) << vmin <<
", " << vmax;
1830 for (
int i = 0; i < sorted_values.size(); ++i) {
1831 const int64 val = sorted_values[i];
1839 ~SmallBitSet()
override {}
1841 bool bit(
int64 val)
const {
1844 return (bits_ &
OneBit64(val - omin_)) != 0;
1858 if (new_bits != uint64_t{0}) {
1882 if (new_bits != uint64_t{0}) {
1895 bool SetValue(
int64 val)
override {
1907 bool Contains(
int64 val)
const override {
1913 bool RemoveValue(
int64 val)
override {
1919 if (
stamp_ < current_stamp) {
1936 uint64 Size()
const override {
return size_.Value(); }
1938 std::string DebugString()
const override {
1939 return absl::StrFormat(
"SmallBitSet(%d..%d : %llx)", omin_, omax_, bits_);
1942 void DelayRemoveValue(
int64 val)
override {
1945 removed_.push_back(val);
1948 void ApplyRemovedValues(DomainIntVar*
var)
override {
1949 std::sort(removed_.begin(), removed_.end());
1950 for (std::vector<int64>::iterator it = removed_.begin();
1951 it != removed_.end(); ++it) {
1952 var->RemoveValue(*it);
1956 void ClearRemovedValues()
override { removed_.clear(); }
1973 if (v == start_cumul + 1) {
1974 absl::StrAppendFormat(&out,
"%d ", start_cumul);
1975 }
else if (v == start_cumul + 2) {
1976 absl::StrAppendFormat(&out,
"%d %d ", start_cumul, v - 1);
1978 absl::StrAppendFormat(&out,
"%d..%d ", start_cumul, v - 1);
1985 if (
max == start_cumul + 1) {
1986 absl::StrAppendFormat(&out,
"%d %d", start_cumul,
max);
1988 absl::StrAppendFormat(&out,
"%d..%d", start_cumul,
max);
1991 absl::StrAppendFormat(&out,
"%d",
max);
1994 absl::StrAppendFormat(&out,
"%d",
min);
1999 DomainIntVar::BitSetIterator* MakeIterator()
override {
2000 return new DomainIntVar::BitSetIterator(&bits_, omin_);
2008 NumericalRev<int64> size_;
2009 std::vector<int64> removed_;
2012 class EmptyIterator :
public IntVarIterator {
2014 ~EmptyIterator()
override {}
2015 void Init()
override {}
2016 bool Ok()
const override {
return false; }
2018 LOG(
FATAL) <<
"Should not be called";
2021 void Next()
override {}
2024 class RangeIterator :
public IntVarIterator {
2026 explicit RangeIterator(
const IntVar*
const var)
2029 ~RangeIterator()
override {}
2031 void Init()
override {
2037 bool Ok()
const override {
return current_ <= max_; }
2041 void Next()
override {
current_++; }
2044 const IntVar*
const var_;
2050 class DomainIntVarHoleIterator :
public IntVarIterator {
2052 explicit DomainIntVarHoleIterator(
const DomainIntVar*
const v)
2053 : var_(v), bits_(nullptr), values_(nullptr), size_(0), index_(0) {}
2055 ~DomainIntVarHoleIterator()
override {}
2057 void Init()
override {
2058 bits_ = var_->bitset();
2059 if (bits_ !=
nullptr) {
2061 values_ = bits_->Holes().data();
2062 size_ = bits_->Holes().size();
2070 bool Ok()
const override {
return index_ < size_; }
2073 DCHECK(bits_ !=
nullptr);
2075 return values_[index_];
2078 void Next()
override { index_++; }
2081 const DomainIntVar*
const var_;
2082 DomainIntVar::BitSet* bits_;
2083 const int64* values_;
2088 class DomainIntVarDomainIterator :
public IntVarIterator {
2090 explicit DomainIntVarDomainIterator(
const DomainIntVar*
const v,
2093 bitset_iterator_(nullptr),
2097 reversible_(reversible) {}
2099 ~DomainIntVarDomainIterator()
override {
2100 if (!reversible_ && bitset_iterator_) {
2101 delete bitset_iterator_;
2105 void Init()
override {
2106 if (var_->bitset() !=
nullptr && !var_->Bound()) {
2108 if (!bitset_iterator_) {
2109 Solver*
const solver = var_->solver();
2110 solver->SaveValue(
reinterpret_cast<void**
>(&bitset_iterator_));
2111 bitset_iterator_ = solver->RevAlloc(var_->bitset()->MakeIterator());
2114 if (bitset_iterator_) {
2115 delete bitset_iterator_;
2117 bitset_iterator_ = var_->bitset()->MakeIterator();
2119 bitset_iterator_->Init(var_->Min(), var_->Max());
2121 if (bitset_iterator_) {
2123 Solver*
const solver = var_->solver();
2124 solver->SaveValue(
reinterpret_cast<void**
>(&bitset_iterator_));
2126 delete bitset_iterator_;
2128 bitset_iterator_ =
nullptr;
2136 bool Ok()
const override {
2137 return bitset_iterator_ ? bitset_iterator_->Ok() : (
current_ <= max_);
2141 return bitset_iterator_ ? bitset_iterator_->Value() :
current_;
2144 void Next()
override {
2145 if (bitset_iterator_) {
2146 bitset_iterator_->Next();
2153 const DomainIntVar*
const var_;
2154 DomainIntVar::BitSetIterator* bitset_iterator_;
2158 const bool reversible_;
2161 class UnaryIterator :
public IntVarIterator {
2163 UnaryIterator(
const IntVar*
const v,
bool hole,
bool reversible)
2164 :
iterator_(hole ? v->MakeHoleIterator(reversible)
2165 : v->MakeDomainIterator(reversible)),
2166 reversible_(reversible) {}
2168 ~UnaryIterator()
override {
2174 void Init()
override {
iterator_->Init(); }
2176 bool Ok()
const override {
return iterator_->Ok(); }
2178 void Next()
override {
iterator_->Next(); }
2182 const bool reversible_;
2185 DomainIntVar::DomainIntVar(Solver*
const s,
int64 vmin,
int64 vmax,
2186 const std::string&
name)
2197 value_watcher_(nullptr),
2198 bound_watcher_(nullptr) {}
2200 DomainIntVar::DomainIntVar(Solver*
const s,
2201 const std::vector<int64>& sorted_values,
2202 const std::string&
name)
2213 value_watcher_(nullptr),
2214 bound_watcher_(nullptr) {
2217 const int64 vmin = sorted_values.front();
2218 const int64 vmax = sorted_values.back();
2219 const bool contiguous = vmax - vmin + 1 == sorted_values.size();
2221 min_.SetValue(solver(), vmin);
2224 max_.SetValue(solver(), vmax);
2229 if (vmax - vmin + 1 < 65) {
2230 bits_ = solver()->RevAlloc(
2231 new SmallBitSet(solver(), sorted_values, vmin, vmax));
2233 bits_ = solver()->RevAlloc(
2234 new SimpleBitSet(solver(), sorted_values, vmin, vmax));
2239 DomainIntVar::~DomainIntVar() {}
2241 void DomainIntVar::SetMin(
int64 m) {
2242 if (m <= min_.Value())
return;
2243 if (m > max_.Value()) solver()->Fail();
2247 if (new_min_ > new_max_) {
2253 const int64 new_min =
2256 : bits_->ComputeNewMin(m, min_.Value(), max_.Value()));
2257 min_.SetValue(solver(), new_min);
2258 if (min_.Value() > max_.Value()) {
2265 void DomainIntVar::SetMax(
int64 m) {
2266 if (m >= max_.Value())
return;
2267 if (m < min_.Value()) solver()->Fail();
2271 if (new_max_ < new_min_) {
2277 const int64 new_max =
2280 : bits_->ComputeNewMax(m, min_.Value(), max_.Value()));
2281 max_.SetValue(solver(), new_max);
2282 if (min_.Value() > max_.Value()) {
2289 void DomainIntVar::SetRange(
int64 mi,
int64 ma) {
2293 if (mi > ma || mi > max_.Value() || ma < min_.Value()) solver()->Fail();
2294 if (mi <= min_.Value() && ma >= max_.Value())
return;
2296 if (ma < new_max_) {
2299 if (mi > new_min_) {
2302 if (new_min_ > new_max_) {
2306 if (mi > min_.Value()) {
2308 const int64 new_min =
2311 : bits_->ComputeNewMin(mi, min_.Value(), max_.Value()));
2312 min_.SetValue(solver(), new_min);
2314 if (min_.Value() > ma) {
2317 if (ma < max_.Value()) {
2319 const int64 new_max =
2322 : bits_->ComputeNewMax(ma, min_.Value(), max_.Value()));
2323 max_.SetValue(solver(), new_max);
2325 if (min_.Value() > max_.Value()) {
2333 void DomainIntVar::SetValue(
int64 v) {
2334 if (v != min_.Value() || v != max_.Value()) {
2335 if (v < min_.Value() || v > max_.Value()) {
2339 if (v > new_max_ || v < new_min_) {
2345 if (bits_ && !bits_->SetValue(v)) {
2350 min_.SetValue(solver(), v);
2351 max_.SetValue(solver(), v);
2357 void DomainIntVar::RemoveValue(
int64 v) {
2358 if (v < min_.Value() || v > max_.Value())
return;
2359 if (v == min_.Value()) {
2361 }
else if (v == max_.Value()) {
2364 if (bits_ ==
nullptr) {
2368 if (v >= new_min_ && v <= new_max_ && bits_->Contains(v)) {
2369 bits_->DelayRemoveValue(v);
2372 if (bits_->RemoveValue(v)) {
2379 void DomainIntVar::RemoveInterval(
int64 l,
int64 u) {
2380 if (l <= min_.Value()) {
2382 }
else if (u >= max_.Value()) {
2385 for (
int64 v = l; v <= u; ++v) {
2391 void DomainIntVar::CreateBits() {
2392 solver()->SaveValue(
reinterpret_cast<void**
>(&bits_));
2393 if (max_.Value() - min_.Value() < 64) {
2394 bits_ = solver()->RevAlloc(
2395 new SmallBitSet(solver(), min_.Value(), max_.Value()));
2397 bits_ = solver()->RevAlloc(
2398 new SimpleBitSet(solver(), min_.Value(), max_.Value()));
2402 void DomainIntVar::CleanInProcess() {
2404 if (bits_ !=
nullptr) {
2405 bits_->ClearHoles();
2409 void DomainIntVar::Push() {
2415 void DomainIntVar::Process() {
2418 if (bits_ !=
nullptr) {
2419 bits_->ClearRemovedValues();
2421 set_variable_to_clean_on_fail(
this);
2422 new_min_ = min_.Value();
2423 new_max_ = max_.Value();
2424 const bool is_bound = min_.Value() == max_.Value();
2425 const bool range_changed =
2426 min_.Value() != OldMin() || max_.Value() != OldMax();
2429 ExecuteAll(bound_demons_);
2431 if (range_changed) {
2432 ExecuteAll(range_demons_);
2434 ExecuteAll(domain_demons_);
2438 EnqueueAll(delayed_bound_demons_);
2440 if (range_changed) {
2441 EnqueueAll(delayed_range_demons_);
2443 EnqueueAll(delayed_domain_demons_);
2446 set_variable_to_clean_on_fail(
nullptr);
2448 old_min_ = min_.Value();
2449 old_max_ = max_.Value();
2450 if (min_.Value() < new_min_) {
2453 if (max_.Value() > new_max_) {
2456 if (bits_ !=
nullptr) {
2457 bits_->ApplyRemovedValues(
this);
2461 #define COND_REV_ALLOC(rev, alloc) rev ? solver()->RevAlloc(alloc) : alloc;
2463 IntVarIterator* DomainIntVar::MakeHoleIterator(
bool reversible)
const {
2464 return COND_REV_ALLOC(reversible,
new DomainIntVarHoleIterator(
this));
2467 IntVarIterator* DomainIntVar::MakeDomainIterator(
bool reversible)
const {
2469 new DomainIntVarDomainIterator(
this, reversible));
2472 std::string DomainIntVar::DebugString()
const {
2474 const std::string& var_name =
name();
2475 if (!var_name.empty()) {
2476 out = var_name +
"(";
2478 out =
"DomainIntVar(";
2480 if (min_.Value() == max_.Value()) {
2481 absl::StrAppendFormat(&out,
"%d", min_.Value());
2482 }
else if (bits_ !=
nullptr) {
2483 out.append(bits_->pretty_DebugString(min_.Value(), max_.Value()));
2485 absl::StrAppendFormat(&out,
"%d..%d", min_.Value(), max_.Value());
2493 class ConcreteBooleanVar :
public BooleanVar {
2496 class Handler :
public Demon {
2498 explicit Handler(ConcreteBooleanVar*
const var) : Demon(), var_(
var) {}
2499 ~Handler()
override {}
2500 void Run(Solver*
const s)
override {
2501 s->GetPropagationMonitor()->StartProcessingIntegerVariable(var_);
2503 s->GetPropagationMonitor()->EndProcessingIntegerVariable(var_);
2505 Solver::DemonPriority priority()
const override {
2506 return Solver::VAR_PRIORITY;
2508 std::string DebugString()
const override {
2509 return absl::StrFormat(
"Handler(%s)", var_->DebugString());
2513 ConcreteBooleanVar*
const var_;
2516 ConcreteBooleanVar(Solver*
const s,
const std::string&
name)
2519 ~ConcreteBooleanVar()
override {}
2521 void SetValue(
int64 v)
override {
2522 if (value_ == kUnboundBooleanVarValue) {
2523 if ((v & 0xfffffffffffffffe) == 0) {
2525 value_ =
static_cast<int>(v);
2529 }
else if (v == value_) {
2536 DCHECK_NE(value_, kUnboundBooleanVarValue);
2537 ExecuteAll(bound_demons_);
2538 for (SimpleRevFIFO<Demon*>::Iterator it(&delayed_bound_demons_); it.ok();
2540 EnqueueDelayedDemon(*it);
2544 int64 OldMin()
const override {
return 0LL; }
2545 int64 OldMax()
const override {
return 1LL; }
2546 void RestoreValue()
override { value_ = kUnboundBooleanVarValue; }
2554 class IntConst :
public IntVar {
2556 IntConst(Solver*
const s,
int64 value,
const std::string&
name =
"")
2558 ~IntConst()
override {}
2560 int64 Min()
const override {
return value_; }
2561 void SetMin(
int64 m)
override {
2566 int64 Max()
const override {
return value_; }
2567 void SetMax(
int64 m)
override {
2573 if (l > value_ || u < value_) {
2577 void SetValue(
int64 v)
override {
2582 bool Bound()
const override {
return true; }
2583 int64 Value()
const override {
return value_; }
2584 void RemoveValue(
int64 v)
override {
2589 void RemoveInterval(
int64 l,
int64 u)
override {
2590 if (l <= value_ && value_ <= u) {
2594 void WhenBound(Demon* d)
override {}
2595 void WhenRange(Demon* d)
override {}
2596 void WhenDomain(Demon* d)
override {}
2597 uint64 Size()
const override {
return 1; }
2598 bool Contains(
int64 v)
const override {
return (v == value_); }
2599 IntVarIterator* MakeHoleIterator(
bool reversible)
const override {
2602 IntVarIterator* MakeDomainIterator(
bool reversible)
const override {
2605 int64 OldMin()
const override {
return value_; }
2606 int64 OldMax()
const override {
return value_; }
2607 std::string DebugString()
const override {
2609 if (solver()->HasName(
this)) {
2610 const std::string& var_name =
name();
2611 absl::StrAppendFormat(&out,
"%s(%d)", var_name, value_);
2613 absl::StrAppendFormat(&out,
"IntConst(%d)", value_);
2618 int VarType()
const override {
return CONST_VAR; }
2620 IntVar* IsEqual(
int64 constant)
override {
2621 if (constant == value_) {
2622 return solver()->MakeIntConst(1);
2624 return solver()->MakeIntConst(0);
2628 IntVar* IsDifferent(
int64 constant)
override {
2629 if (constant == value_) {
2630 return solver()->MakeIntConst(0);
2632 return solver()->MakeIntConst(1);
2636 IntVar* IsGreaterOrEqual(
int64 constant)
override {
2637 return solver()->MakeIntConst(value_ >= constant);
2640 IntVar* IsLessOrEqual(
int64 constant)
override {
2641 return solver()->MakeIntConst(value_ <= constant);
2644 std::string
name()
const override {
2645 if (solver()->HasName(
this)) {
2648 return absl::StrCat(value_);
2658 class PlusCstVar :
public IntVar {
2660 PlusCstVar(Solver*
const s, IntVar* v,
int64 c)
2661 : IntVar(s), var_(v),
cst_(c) {}
2663 ~PlusCstVar()
override {}
2665 void WhenRange(Demon* d)
override { var_->WhenRange(d); }
2667 void WhenBound(Demon* d)
override { var_->WhenBound(d); }
2669 void WhenDomain(Demon* d)
override { var_->WhenDomain(d); }
2671 int64 OldMin()
const override {
return CapAdd(var_->OldMin(),
cst_); }
2673 int64 OldMax()
const override {
return CapAdd(var_->OldMax(),
cst_); }
2675 std::string DebugString()
const override {
2677 return absl::StrFormat(
"%s(%s + %d)",
name(), var_->DebugString(),
cst_);
2679 return absl::StrFormat(
"(%s + %d)", var_->DebugString(),
cst_);
2683 int VarType()
const override {
return VAR_ADD_CST; }
2685 void Accept(ModelVisitor*
const visitor)
const override {
2686 visitor->VisitIntegerVariable(
this, ModelVisitor::kSumOperation,
cst_,
2690 IntVar* IsEqual(
int64 constant)
override {
2691 return var_->IsEqual(constant -
cst_);
2694 IntVar* IsDifferent(
int64 constant)
override {
2695 return var_->IsDifferent(constant -
cst_);
2698 IntVar* IsGreaterOrEqual(
int64 constant)
override {
2699 return var_->IsGreaterOrEqual(constant -
cst_);
2702 IntVar* IsLessOrEqual(
int64 constant)
override {
2703 return var_->IsLessOrEqual(constant -
cst_);
2706 IntVar* SubVar()
const {
return var_; }
2715 class PlusCstIntVar :
public PlusCstVar {
2717 class PlusCstIntVarIterator :
public UnaryIterator {
2719 PlusCstIntVarIterator(
const IntVar*
const v,
int64 c,
bool hole,
bool rev)
2720 : UnaryIterator(v, hole, rev),
cst_(c) {}
2722 ~PlusCstIntVarIterator()
override {}
2730 PlusCstIntVar(Solver*
const s, IntVar* v,
int64 c) : PlusCstVar(s, v, c) {}
2732 ~PlusCstIntVar()
override {}
2734 int64 Min()
const override {
return var_->Min() +
cst_; }
2738 int64 Max()
const override {
return var_->Max() +
cst_; }
2746 void SetValue(
int64 v)
override { var_->SetValue(v -
cst_); }
2750 bool Bound()
const override {
return var_->Bound(); }
2752 void RemoveValue(
int64 v)
override { var_->RemoveValue(v -
cst_); }
2754 void RemoveInterval(
int64 l,
int64 u)
override {
2755 var_->RemoveInterval(l -
cst_, u -
cst_);
2758 uint64 Size()
const override {
return var_->Size(); }
2760 bool Contains(
int64 v)
const override {
return var_->Contains(v -
cst_); }
2762 IntVarIterator* MakeHoleIterator(
bool reversible)
const override {
2764 reversible,
new PlusCstIntVarIterator(var_,
cst_,
true, reversible));
2766 IntVarIterator* MakeDomainIterator(
bool reversible)
const override {
2768 reversible,
new PlusCstIntVarIterator(var_,
cst_,
false, reversible));
2772 class PlusCstDomainIntVar :
public PlusCstVar {
2774 class PlusCstDomainIntVarIterator :
public UnaryIterator {
2776 PlusCstDomainIntVarIterator(
const IntVar*
const v,
int64 c,
bool hole,
2778 : UnaryIterator(v, hole, reversible),
cst_(c) {}
2780 ~PlusCstDomainIntVarIterator()
override {}
2788 PlusCstDomainIntVar(Solver*
const s, DomainIntVar* v,
int64 c)
2789 : PlusCstVar(s, v, c) {}
2791 ~PlusCstDomainIntVar()
override {}
2793 int64 Min()
const override;
2794 void SetMin(
int64 m)
override;
2795 int64 Max()
const override;
2796 void SetMax(
int64 m)
override;
2798 void SetValue(
int64 v)
override;
2799 bool Bound()
const override;
2801 void RemoveValue(
int64 v)
override;
2802 void RemoveInterval(
int64 l,
int64 u)
override;
2803 uint64 Size()
const override;
2804 bool Contains(
int64 v)
const override;
2806 DomainIntVar* domain_int_var()
const {
2807 return reinterpret_cast<DomainIntVar*
>(var_);
2810 IntVarIterator* MakeHoleIterator(
bool reversible)
const override {
2811 return COND_REV_ALLOC(reversible,
new PlusCstDomainIntVarIterator(
2812 var_,
cst_,
true, reversible));
2814 IntVarIterator* MakeDomainIterator(
bool reversible)
const override {
2815 return COND_REV_ALLOC(reversible,
new PlusCstDomainIntVarIterator(
2816 var_,
cst_,
false, reversible));
2820 int64 PlusCstDomainIntVar::Min()
const {
2821 return domain_int_var()->min_.Value() +
cst_;
2824 void PlusCstDomainIntVar::SetMin(
int64 m) {
2825 domain_int_var()->DomainIntVar::SetMin(m -
cst_);
2828 int64 PlusCstDomainIntVar::Max()
const {
2829 return domain_int_var()->max_.Value() +
cst_;
2832 void PlusCstDomainIntVar::SetMax(
int64 m) {
2833 domain_int_var()->DomainIntVar::SetMax(m -
cst_);
2836 void PlusCstDomainIntVar::SetRange(
int64 l,
int64 u) {
2837 domain_int_var()->DomainIntVar::SetRange(l -
cst_, u -
cst_);
2840 void PlusCstDomainIntVar::SetValue(
int64 v) {
2841 domain_int_var()->DomainIntVar::SetValue(v -
cst_);
2844 bool PlusCstDomainIntVar::Bound()
const {
2845 return domain_int_var()->min_.Value() == domain_int_var()->max_.Value();
2849 CHECK_EQ(domain_int_var()->min_.Value(), domain_int_var()->max_.Value())
2850 <<
" variable is not bound";
2851 return domain_int_var()->min_.Value() +
cst_;
2854 void PlusCstDomainIntVar::RemoveValue(
int64 v) {
2855 domain_int_var()->DomainIntVar::RemoveValue(v -
cst_);
2858 void PlusCstDomainIntVar::RemoveInterval(
int64 l,
int64 u) {
2859 domain_int_var()->DomainIntVar::RemoveInterval(l -
cst_, u -
cst_);
2862 uint64 PlusCstDomainIntVar::Size()
const {
2863 return domain_int_var()->DomainIntVar::Size();
2866 bool PlusCstDomainIntVar::Contains(
int64 v)
const {
2867 return domain_int_var()->DomainIntVar::Contains(v -
cst_);
2872 class SubCstIntVar :
public IntVar {
2874 class SubCstIntVarIterator :
public UnaryIterator {
2876 SubCstIntVarIterator(
const IntVar*
const v,
int64 c,
bool hole,
bool rev)
2877 : UnaryIterator(v, hole, rev),
cst_(c) {}
2878 ~SubCstIntVarIterator()
override {}
2886 SubCstIntVar(Solver*
const s, IntVar* v,
int64 c);
2887 ~SubCstIntVar()
override;
2889 int64 Min()
const override;
2890 void SetMin(
int64 m)
override;
2891 int64 Max()
const override;
2892 void SetMax(
int64 m)
override;
2894 void SetValue(
int64 v)
override;
2895 bool Bound()
const override;
2897 void RemoveValue(
int64 v)
override;
2898 void RemoveInterval(
int64 l,
int64 u)
override;
2899 uint64 Size()
const override;
2900 bool Contains(
int64 v)
const override;
2901 void WhenRange(Demon* d)
override;
2902 void WhenBound(Demon* d)
override;
2903 void WhenDomain(Demon* d)
override;
2904 IntVarIterator* MakeHoleIterator(
bool reversible)
const override {
2906 reversible,
new SubCstIntVarIterator(var_,
cst_,
true, reversible));
2908 IntVarIterator* MakeDomainIterator(
bool reversible)
const override {
2910 reversible,
new SubCstIntVarIterator(var_,
cst_,
false, reversible));
2912 int64 OldMin()
const override {
return CapSub(
cst_, var_->OldMax()); }
2913 int64 OldMax()
const override {
return CapSub(
cst_, var_->OldMin()); }
2914 std::string DebugString()
const override;
2915 std::string
name()
const override;
2916 int VarType()
const override {
return CST_SUB_VAR; }
2918 void Accept(ModelVisitor*
const visitor)
const override {
2919 visitor->VisitIntegerVariable(
this, ModelVisitor::kDifferenceOperation,
2923 IntVar* IsEqual(
int64 constant)
override {
2924 return var_->IsEqual(
cst_ - constant);
2927 IntVar* IsDifferent(
int64 constant)
override {
2928 return var_->IsDifferent(
cst_ - constant);
2931 IntVar* IsGreaterOrEqual(
int64 constant)
override {
2932 return var_->IsLessOrEqual(
cst_ - constant);
2935 IntVar* IsLessOrEqual(
int64 constant)
override {
2936 return var_->IsGreaterOrEqual(
cst_ - constant);
2939 IntVar* SubVar()
const {
return var_; }
2947 SubCstIntVar::SubCstIntVar(Solver*
const s, IntVar* v,
int64 c)
2948 : IntVar(s), var_(v),
cst_(c) {}
2950 SubCstIntVar::~SubCstIntVar() {}
2952 int64 SubCstIntVar::Min()
const {
return cst_ - var_->Max(); }
2956 int64 SubCstIntVar::Max()
const {
return cst_ - var_->Min(); }
2960 void SubCstIntVar::SetRange(
int64 l,
int64 u) {
2964 void SubCstIntVar::SetValue(
int64 v) { var_->SetValue(
cst_ - v); }
2966 bool SubCstIntVar::Bound()
const {
return var_->Bound(); }
2968 void SubCstIntVar::WhenRange(Demon* d) { var_->WhenRange(d); }
2972 void SubCstIntVar::RemoveValue(
int64 v) { var_->RemoveValue(
cst_ - v); }
2974 void SubCstIntVar::RemoveInterval(
int64 l,
int64 u) {
2975 var_->RemoveInterval(
cst_ - u,
cst_ - l);
2978 void SubCstIntVar::WhenBound(Demon* d) { var_->WhenBound(d); }
2980 void SubCstIntVar::WhenDomain(Demon* d) { var_->WhenDomain(d); }
2982 uint64 SubCstIntVar::Size()
const {
return var_->Size(); }
2984 bool SubCstIntVar::Contains(
int64 v)
const {
return var_->Contains(
cst_ - v); }
2986 std::string SubCstIntVar::DebugString()
const {
2988 return absl::StrFormat(
"Not(%s)", var_->DebugString());
2990 return absl::StrFormat(
"(%d - %s)",
cst_, var_->DebugString());
2995 if (solver()->HasName(
this)) {
2998 return absl::StrFormat(
"Not(%s)", var_->name());
3000 return absl::StrFormat(
"(%d - %s)",
cst_, var_->name());
3006 class OppIntVar :
public IntVar {
3008 class OppIntVarIterator :
public UnaryIterator {
3010 OppIntVarIterator(
const IntVar*
const v,
bool hole,
bool reversible)
3011 : UnaryIterator(v, hole, reversible) {}
3012 ~OppIntVarIterator()
override {}
3017 OppIntVar(Solver*
const s, IntVar* v);
3018 ~OppIntVar()
override;
3020 int64 Min()
const override;
3021 void SetMin(
int64 m)
override;
3022 int64 Max()
const override;
3023 void SetMax(
int64 m)
override;
3025 void SetValue(
int64 v)
override;
3026 bool Bound()
const override;
3028 void RemoveValue(
int64 v)
override;
3029 void RemoveInterval(
int64 l,
int64 u)
override;
3030 uint64 Size()
const override;
3031 bool Contains(
int64 v)
const override;
3032 void WhenRange(Demon* d)
override;
3033 void WhenBound(Demon* d)
override;
3034 void WhenDomain(Demon* d)
override;
3035 IntVarIterator* MakeHoleIterator(
bool reversible)
const override {
3037 new OppIntVarIterator(var_,
true, reversible));
3039 IntVarIterator* MakeDomainIterator(
bool reversible)
const override {
3041 new OppIntVarIterator(var_,
false, reversible));
3043 int64 OldMin()
const override {
return CapOpp(var_->OldMax()); }
3044 int64 OldMax()
const override {
return CapOpp(var_->OldMin()); }
3045 std::string DebugString()
const override;
3046 int VarType()
const override {
return OPP_VAR; }
3048 void Accept(ModelVisitor*
const visitor)
const override {
3049 visitor->VisitIntegerVariable(
this, ModelVisitor::kDifferenceOperation, 0,
3053 IntVar* IsEqual(
int64 constant)
override {
return var_->IsEqual(-constant); }
3055 IntVar* IsDifferent(
int64 constant)
override {
3056 return var_->IsDifferent(-constant);
3059 IntVar* IsGreaterOrEqual(
int64 constant)
override {
3060 return var_->IsLessOrEqual(-constant);
3063 IntVar* IsLessOrEqual(
int64 constant)
override {
3064 return var_->IsGreaterOrEqual(-constant);
3067 IntVar* SubVar()
const {
return var_; }
3073 OppIntVar::OppIntVar(Solver*
const s, IntVar* v) : IntVar(s), var_(v) {}
3075 OppIntVar::~OppIntVar() {}
3077 int64 OppIntVar::Min()
const {
return -var_->Max(); }
3079 void OppIntVar::SetMin(
int64 m) { var_->SetMax(
CapOpp(m)); }
3081 int64 OppIntVar::Max()
const {
return -var_->Min(); }
3083 void OppIntVar::SetMax(
int64 m) { var_->SetMin(
CapOpp(m)); }
3089 void OppIntVar::SetValue(
int64 v) { var_->SetValue(
CapOpp(v)); }
3091 bool OppIntVar::Bound()
const {
return var_->Bound(); }
3093 void OppIntVar::WhenRange(Demon* d) { var_->WhenRange(d); }
3097 void OppIntVar::RemoveValue(
int64 v) { var_->RemoveValue(-v); }
3099 void OppIntVar::RemoveInterval(
int64 l,
int64 u) {
3100 var_->RemoveInterval(-u, -l);
3103 void OppIntVar::WhenBound(Demon* d) { var_->WhenBound(d); }
3105 void OppIntVar::WhenDomain(Demon* d) { var_->WhenDomain(d); }
3107 uint64 OppIntVar::Size()
const {
return var_->Size(); }
3109 bool OppIntVar::Contains(
int64 v)
const {
return var_->Contains(-v); }
3111 std::string OppIntVar::DebugString()
const {
3112 return absl::StrFormat(
"-(%s)", var_->DebugString());
3119 class TimesCstIntVar :
public IntVar {
3121 TimesCstIntVar(Solver*
const s, IntVar* v,
int64 c)
3122 : IntVar(s), var_(v),
cst_(c) {}
3123 ~TimesCstIntVar()
override {}
3125 IntVar* SubVar()
const {
return var_; }
3128 void Accept(ModelVisitor*
const visitor)
const override {
3129 visitor->VisitIntegerVariable(
this, ModelVisitor::kProductOperation,
cst_,
3133 IntVar* IsEqual(
int64 constant)
override {
3134 if (constant %
cst_ == 0) {
3135 return var_->IsEqual(constant /
cst_);
3137 return solver()->MakeIntConst(0);
3141 IntVar* IsDifferent(
int64 constant)
override {
3142 if (constant %
cst_ == 0) {
3143 return var_->IsDifferent(constant /
cst_);
3145 return solver()->MakeIntConst(1);
3149 IntVar* IsGreaterOrEqual(
int64 constant)
override {
3157 IntVar* IsLessOrEqual(
int64 constant)
override {
3165 std::string DebugString()
const override {
3166 return absl::StrFormat(
"(%s * %d)", var_->DebugString(),
cst_);
3176 class TimesPosCstIntVar :
public TimesCstIntVar {
3178 class TimesPosCstIntVarIterator :
public UnaryIterator {
3180 TimesPosCstIntVarIterator(
const IntVar*
const v,
int64 c,
bool hole,
3182 : UnaryIterator(v, hole, reversible),
cst_(c) {}
3183 ~TimesPosCstIntVarIterator()
override {}
3191 TimesPosCstIntVar(Solver*
const s, IntVar* v,
int64 c);
3192 ~TimesPosCstIntVar()
override;
3194 int64 Min()
const override;
3195 void SetMin(
int64 m)
override;
3196 int64 Max()
const override;
3197 void SetMax(
int64 m)
override;
3199 void SetValue(
int64 v)
override;
3200 bool Bound()
const override;
3202 void RemoveValue(
int64 v)
override;
3203 void RemoveInterval(
int64 l,
int64 u)
override;
3204 uint64 Size()
const override;
3205 bool Contains(
int64 v)
const override;
3206 void WhenRange(Demon* d)
override;
3207 void WhenBound(Demon* d)
override;
3208 void WhenDomain(Demon* d)
override;
3209 IntVarIterator* MakeHoleIterator(
bool reversible)
const override {
3211 var_,
cst_,
true, reversible));
3213 IntVarIterator* MakeDomainIterator(
bool reversible)
const override {
3215 var_,
cst_,
false, reversible));
3223 TimesPosCstIntVar::TimesPosCstIntVar(Solver*
const s, IntVar* v,
int64 c)
3224 : TimesCstIntVar(s, v, c) {}
3226 TimesPosCstIntVar::~TimesPosCstIntVar() {}
3228 int64 TimesPosCstIntVar::Min()
const {
return CapProd(var_->Min(),
cst_); }
3230 void TimesPosCstIntVar::SetMin(
int64 m) {
3236 int64 TimesPosCstIntVar::Max()
const {
return CapProd(var_->Max(),
cst_); }
3238 void TimesPosCstIntVar::SetMax(
int64 m) {
3244 void TimesPosCstIntVar::SetRange(
int64 l,
int64 u) {
3248 void TimesPosCstIntVar::SetValue(
int64 v) {
3249 if (v %
cst_ != 0) {
3252 var_->SetValue(v /
cst_);
3255 bool TimesPosCstIntVar::Bound()
const {
return var_->Bound(); }
3257 void TimesPosCstIntVar::WhenRange(Demon* d) { var_->WhenRange(d); }
3261 void TimesPosCstIntVar::RemoveValue(
int64 v) {
3262 if (v %
cst_ == 0) {
3263 var_->RemoveValue(v /
cst_);
3267 void TimesPosCstIntVar::RemoveInterval(
int64 l,
int64 u) {
3268 for (
int64 v = l; v <= u; ++v) {
3274 void TimesPosCstIntVar::WhenBound(Demon* d) { var_->WhenBound(d); }
3276 void TimesPosCstIntVar::WhenDomain(Demon* d) { var_->WhenDomain(d); }
3278 uint64 TimesPosCstIntVar::Size()
const {
return var_->Size(); }
3280 bool TimesPosCstIntVar::Contains(
int64 v)
const {
3281 return (v %
cst_ == 0 && var_->Contains(v /
cst_));
3286 class TimesPosCstBoolVar :
public TimesCstIntVar {
3288 class TimesPosCstBoolVarIterator :
public UnaryIterator {
3291 TimesPosCstBoolVarIterator(
const IntVar*
const v,
int64 c,
bool hole,
3293 : UnaryIterator(v, hole, reversible),
cst_(c) {}
3294 ~TimesPosCstBoolVarIterator()
override {}
3302 TimesPosCstBoolVar(Solver*
const s, BooleanVar* v,
int64 c);
3303 ~TimesPosCstBoolVar()
override;
3305 int64 Min()
const override;
3306 void SetMin(
int64 m)
override;
3307 int64 Max()
const override;
3308 void SetMax(
int64 m)
override;
3310 void SetValue(
int64 v)
override;
3311 bool Bound()
const override;
3313 void RemoveValue(
int64 v)
override;
3314 void RemoveInterval(
int64 l,
int64 u)
override;
3315 uint64 Size()
const override;
3316 bool Contains(
int64 v)
const override;
3317 void WhenRange(Demon* d)
override;
3318 void WhenBound(Demon* d)
override;
3319 void WhenDomain(Demon* d)
override;
3320 IntVarIterator* MakeHoleIterator(
bool reversible)
const override {
3323 IntVarIterator* MakeDomainIterator(
bool reversible)
const override {
3326 new TimesPosCstBoolVarIterator(boolean_var(),
cst_,
false, reversible));
3328 int64 OldMin()
const override {
return 0; }
3329 int64 OldMax()
const override {
return cst_; }
3331 BooleanVar* boolean_var()
const {
3332 return reinterpret_cast<BooleanVar*
>(var_);
3338 TimesPosCstBoolVar::TimesPosCstBoolVar(Solver*
const s, BooleanVar* v,
int64 c)
3339 : TimesCstIntVar(s, v, c) {}
3341 TimesPosCstBoolVar::~TimesPosCstBoolVar() {}
3343 int64 TimesPosCstBoolVar::Min()
const {
3344 return (boolean_var()->RawValue() == 1) *
cst_;
3347 void TimesPosCstBoolVar::SetMin(
int64 m) {
3351 boolean_var()->SetMin(1);
3355 int64 TimesPosCstBoolVar::Max()
const {
3356 return (boolean_var()->RawValue() != 0) *
cst_;
3359 void TimesPosCstBoolVar::SetMax(
int64 m) {
3362 }
else if (m <
cst_) {
3363 boolean_var()->SetMax(0);
3367 void TimesPosCstBoolVar::SetRange(
int64 l,
int64 u) {
3368 if (u < 0 || l >
cst_ || l > u) {
3372 boolean_var()->SetMin(1);
3373 }
else if (u <
cst_) {
3374 boolean_var()->SetMax(0);
3378 void TimesPosCstBoolVar::SetValue(
int64 v) {
3380 boolean_var()->SetValue(0);
3381 }
else if (v ==
cst_) {
3382 boolean_var()->SetValue(1);
3388 bool TimesPosCstBoolVar::Bound()
const {
3389 return boolean_var()->RawValue() != BooleanVar::kUnboundBooleanVarValue;
3392 void TimesPosCstBoolVar::WhenRange(Demon* d) { boolean_var()->WhenRange(d); }
3395 CHECK_NE(boolean_var()->RawValue(), BooleanVar::kUnboundBooleanVarValue)
3396 <<
" variable is not bound";
3397 return boolean_var()->RawValue() *
cst_;
3400 void TimesPosCstBoolVar::RemoveValue(
int64 v) {
3402 boolean_var()->RemoveValue(0);
3403 }
else if (v ==
cst_) {
3404 boolean_var()->RemoveValue(1);
3408 void TimesPosCstBoolVar::RemoveInterval(
int64 l,
int64 u) {
3409 if (l <= 0 && u >= 0) {
3410 boolean_var()->RemoveValue(0);
3412 if (l <= cst_ && u >=
cst_) {
3413 boolean_var()->RemoveValue(1);
3417 void TimesPosCstBoolVar::WhenBound(Demon* d) { boolean_var()->WhenBound(d); }
3419 void TimesPosCstBoolVar::WhenDomain(Demon* d) { boolean_var()->WhenDomain(d); }
3421 uint64 TimesPosCstBoolVar::Size()
const {
3423 (boolean_var()->RawValue() == BooleanVar::kUnboundBooleanVarValue));
3426 bool TimesPosCstBoolVar::Contains(
int64 v)
const {
3428 return boolean_var()->RawValue() != 1;
3429 }
else if (v ==
cst_) {
3430 return boolean_var()->RawValue() != 0;
3437 class TimesNegCstIntVar :
public TimesCstIntVar {
3439 class TimesNegCstIntVarIterator :
public UnaryIterator {
3441 TimesNegCstIntVarIterator(
const IntVar*
const v,
int64 c,
bool hole,
3443 : UnaryIterator(v, hole, reversible),
cst_(c) {}
3444 ~TimesNegCstIntVarIterator()
override {}
3452 TimesNegCstIntVar(Solver*
const s, IntVar* v,
int64 c);
3453 ~TimesNegCstIntVar()
override;
3455 int64 Min()
const override;
3456 void SetMin(
int64 m)
override;
3457 int64 Max()
const override;
3458 void SetMax(
int64 m)
override;
3460 void SetValue(
int64 v)
override;
3461 bool Bound()
const override;
3463 void RemoveValue(
int64 v)
override;
3464 void RemoveInterval(
int64 l,
int64 u)
override;
3465 uint64 Size()
const override;
3466 bool Contains(
int64 v)
const override;
3467 void WhenRange(Demon* d)
override;
3468 void WhenBound(Demon* d)
override;
3469 void WhenDomain(Demon* d)
override;
3470 IntVarIterator* MakeHoleIterator(
bool reversible)
const override {
3472 var_,
cst_,
true, reversible));
3474 IntVarIterator* MakeDomainIterator(
bool reversible)
const override {
3476 var_,
cst_,
false, reversible));
3484 TimesNegCstIntVar::TimesNegCstIntVar(Solver*
const s, IntVar* v,
int64 c)
3485 : TimesCstIntVar(s, v, c) {}
3487 TimesNegCstIntVar::~TimesNegCstIntVar() {}
3489 int64 TimesNegCstIntVar::Min()
const {
return CapProd(var_->Max(),
cst_); }
3491 void TimesNegCstIntVar::SetMin(
int64 m) {
3497 int64 TimesNegCstIntVar::Max()
const {
return CapProd(var_->Min(),
cst_); }
3499 void TimesNegCstIntVar::SetMax(
int64 m) {
3505 void TimesNegCstIntVar::SetRange(
int64 l,
int64 u) {
3509 void TimesNegCstIntVar::SetValue(
int64 v) {
3510 if (v %
cst_ != 0) {
3513 var_->SetValue(v /
cst_);
3516 bool TimesNegCstIntVar::Bound()
const {
return var_->Bound(); }
3518 void TimesNegCstIntVar::WhenRange(Demon* d) { var_->WhenRange(d); }
3522 void TimesNegCstIntVar::RemoveValue(
int64 v) {
3523 if (v %
cst_ == 0) {
3524 var_->RemoveValue(v /
cst_);
3528 void TimesNegCstIntVar::RemoveInterval(
int64 l,
int64 u) {
3529 for (
int64 v = l; v <= u; ++v) {
3535 void TimesNegCstIntVar::WhenBound(Demon* d) { var_->WhenBound(d); }
3537 void TimesNegCstIntVar::WhenDomain(Demon* d) { var_->WhenDomain(d); }
3539 uint64 TimesNegCstIntVar::Size()
const {
return var_->Size(); }
3541 bool TimesNegCstIntVar::Contains(
int64 v)
const {
3542 return (v %
cst_ == 0 && var_->Contains(v /
cst_));
3549 class PlusIntExpr :
public BaseIntExpr {
3551 PlusIntExpr(Solver*
const s, IntExpr*
const l, IntExpr*
const r)
3552 : BaseIntExpr(s), left_(l), right_(r) {}
3554 ~PlusIntExpr()
override {}
3556 int64 Min()
const override {
return left_->Min() + right_->Min(); }
3558 void SetMin(
int64 m)
override {
3559 if (m > left_->Min() + right_->Min()) {
3560 left_->SetMin(m - right_->Max());
3561 right_->SetMin(m - left_->Max());
3566 const int64 left_min = left_->Min();
3567 const int64 right_min = right_->Min();
3568 const int64 left_max = left_->Max();
3569 const int64 right_max = right_->Max();
3570 if (l > left_min + right_min) {
3571 left_->SetMin(l - right_max);
3572 right_->SetMin(l - left_max);
3574 if (u < left_max + right_max) {
3575 left_->SetMax(u - right_min);
3576 right_->SetMax(u - left_min);
3580 int64 Max()
const override {
return left_->Max() + right_->Max(); }
3582 void SetMax(
int64 m)
override {
3583 if (m < left_->Max() + right_->Max()) {
3584 left_->SetMax(m - right_->Min());
3585 right_->SetMax(m - left_->Min());
3589 bool Bound()
const override {
return (left_->Bound() && right_->Bound()); }
3591 void Range(
int64*
const mi,
int64*
const ma)
override {
3592 *mi = left_->Min() + right_->Min();
3593 *ma = left_->Max() + right_->Max();
3596 std::string
name()
const override {
3597 return absl::StrFormat(
"(%s + %s)", left_->name(), right_->name());
3600 std::string DebugString()
const override {
3601 return absl::StrFormat(
"(%s + %s)", left_->DebugString(),
3602 right_->DebugString());
3605 void WhenRange(Demon* d)
override {
3606 left_->WhenRange(d);
3607 right_->WhenRange(d);
3610 void ExpandPlusIntExpr(IntExpr*
const expr, std::vector<IntExpr*>* subs) {
3611 PlusIntExpr*
const casted =
dynamic_cast<PlusIntExpr*
>(expr);
3612 if (casted !=
nullptr) {
3613 ExpandPlusIntExpr(casted->left_, subs);
3614 ExpandPlusIntExpr(casted->right_, subs);
3616 subs->push_back(expr);
3620 IntVar* CastToVar()
override {
3621 if (
dynamic_cast<PlusIntExpr*
>(left_) !=
nullptr ||
3622 dynamic_cast<PlusIntExpr*
>(right_) !=
nullptr) {
3623 std::vector<IntExpr*> sub_exprs;
3624 ExpandPlusIntExpr(left_, &sub_exprs);
3625 ExpandPlusIntExpr(right_, &sub_exprs);
3626 if (sub_exprs.size() >= 3) {
3627 std::vector<IntVar*> sub_vars(sub_exprs.size());
3628 for (
int i = 0; i < sub_exprs.size(); ++i) {
3629 sub_vars[i] = sub_exprs[i]->Var();
3631 return solver()->MakeSum(sub_vars)->Var();
3634 return BaseIntExpr::CastToVar();
3637 void Accept(ModelVisitor*
const visitor)
const override {
3638 visitor->BeginVisitIntegerExpression(ModelVisitor::kSum,
this);
3639 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
3640 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
3642 visitor->EndVisitIntegerExpression(ModelVisitor::kSum,
this);
3646 IntExpr*
const left_;
3647 IntExpr*
const right_;
3650 class SafePlusIntExpr :
public BaseIntExpr {
3652 SafePlusIntExpr(Solver*
const s, IntExpr*
const l, IntExpr*
const r)
3653 : BaseIntExpr(s), left_(l), right_(r) {}
3655 ~SafePlusIntExpr()
override {}
3657 int64 Min()
const override {
return CapAdd(left_->Min(), right_->Min()); }
3659 void SetMin(
int64 m)
override {
3660 left_->SetMin(
CapSub(m, right_->Max()));
3661 right_->SetMin(
CapSub(m, left_->Max()));
3665 const int64 left_min = left_->Min();
3666 const int64 right_min = right_->Min();
3667 const int64 left_max = left_->Max();
3668 const int64 right_max = right_->Max();
3669 if (l >
CapAdd(left_min, right_min)) {
3670 left_->SetMin(
CapSub(l, right_max));
3671 right_->SetMin(
CapSub(l, left_max));
3673 if (u <
CapAdd(left_max, right_max)) {
3674 left_->SetMax(
CapSub(u, right_min));
3675 right_->SetMax(
CapSub(u, left_min));
3679 int64 Max()
const override {
return CapAdd(left_->Max(), right_->Max()); }
3681 void SetMax(
int64 m)
override {
3682 left_->SetMax(
CapSub(m, right_->Min()));
3683 right_->SetMax(
CapSub(m, left_->Min()));
3686 bool Bound()
const override {
return (left_->Bound() && right_->Bound()); }
3688 std::string
name()
const override {
3689 return absl::StrFormat(
"(%s + %s)", left_->name(), right_->name());
3692 std::string DebugString()
const override {
3693 return absl::StrFormat(
"(%s + %s)", left_->DebugString(),
3694 right_->DebugString());
3697 void WhenRange(Demon* d)
override {
3698 left_->WhenRange(d);
3699 right_->WhenRange(d);
3702 void Accept(ModelVisitor*
const visitor)
const override {
3703 visitor->BeginVisitIntegerExpression(ModelVisitor::kSum,
this);
3704 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
3705 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
3707 visitor->EndVisitIntegerExpression(ModelVisitor::kSum,
this);
3711 IntExpr*
const left_;
3712 IntExpr*
const right_;
3717 class PlusIntCstExpr :
public BaseIntExpr {
3719 PlusIntCstExpr(Solver*
const s, IntExpr*
const e,
int64 v)
3720 : BaseIntExpr(s),
expr_(e), value_(v) {}
3721 ~PlusIntCstExpr()
override {}
3726 bool Bound()
const override {
return (
expr_->Bound()); }
3727 std::string
name()
const override {
3728 return absl::StrFormat(
"(%s + %d)",
expr_->name(), value_);
3730 std::string DebugString()
const override {
3731 return absl::StrFormat(
"(%s + %d)",
expr_->DebugString(), value_);
3733 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
3734 IntVar* CastToVar()
override;
3735 void Accept(ModelVisitor*
const visitor)
const override {
3736 visitor->BeginVisitIntegerExpression(ModelVisitor::kSum,
this);
3737 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
3739 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, value_);
3740 visitor->EndVisitIntegerExpression(ModelVisitor::kSum,
this);
3744 IntExpr*
const expr_;
3748 IntVar* PlusIntCstExpr::CastToVar() {
3749 Solver*
const s = solver();
3751 IntVar* cast =
nullptr;
3754 return BaseIntExpr::CastToVar();
3756 switch (
var->VarType()) {
3758 cast = s->RegisterIntVar(s->RevAlloc(
new PlusCstDomainIntVar(
3759 s,
reinterpret_cast<DomainIntVar*
>(
var), value_)));
3763 cast = s->RegisterIntVar(s->RevAlloc(
new PlusCstIntVar(s,
var, value_)));
3771 class SubIntExpr :
public BaseIntExpr {
3773 SubIntExpr(Solver*
const s, IntExpr*
const l, IntExpr*
const r)
3774 : BaseIntExpr(s), left_(l), right_(r) {}
3776 ~SubIntExpr()
override {}
3778 int64 Min()
const override {
return left_->Min() - right_->Max(); }
3780 void SetMin(
int64 m)
override {
3781 left_->SetMin(
CapAdd(m, right_->Min()));
3782 right_->SetMax(
CapSub(left_->Max(), m));
3785 int64 Max()
const override {
return left_->Max() - right_->Min(); }
3787 void SetMax(
int64 m)
override {
3788 left_->SetMax(
CapAdd(m, right_->Max()));
3789 right_->SetMin(
CapSub(left_->Min(), m));
3793 *mi = left_->Min() - right_->Max();
3794 *ma = left_->Max() - right_->Min();
3798 const int64 left_min = left_->Min();
3799 const int64 right_min = right_->Min();
3800 const int64 left_max = left_->Max();
3801 const int64 right_max = right_->Max();
3802 if (l > left_min - right_max) {
3803 left_->SetMin(
CapAdd(l, right_min));
3804 right_->SetMax(
CapSub(left_max, l));
3806 if (u < left_max - right_min) {
3807 left_->SetMax(
CapAdd(u, right_max));
3808 right_->SetMin(
CapSub(left_min, u));
3812 bool Bound()
const override {
return (left_->Bound() && right_->Bound()); }
3814 std::string
name()
const override {
3815 return absl::StrFormat(
"(%s - %s)", left_->name(), right_->name());
3818 std::string DebugString()
const override {
3819 return absl::StrFormat(
"(%s - %s)", left_->DebugString(),
3820 right_->DebugString());
3823 void WhenRange(Demon* d)
override {
3824 left_->WhenRange(d);
3825 right_->WhenRange(d);
3828 void Accept(ModelVisitor*
const visitor)
const override {
3829 visitor->BeginVisitIntegerExpression(ModelVisitor::kDifference,
this);
3830 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
3831 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
3833 visitor->EndVisitIntegerExpression(ModelVisitor::kDifference,
this);
3836 IntExpr* left()
const {
return left_; }
3837 IntExpr* right()
const {
return right_; }
3840 IntExpr*
const left_;
3841 IntExpr*
const right_;
3844 class SafeSubIntExpr :
public SubIntExpr {
3846 SafeSubIntExpr(Solver*
const s, IntExpr*
const l, IntExpr*
const r)
3847 : SubIntExpr(s, l, r) {}
3849 ~SafeSubIntExpr()
override {}
3851 int64 Min()
const override {
return CapSub(left_->Min(), right_->Max()); }
3853 void SetMin(
int64 m)
override {
3854 left_->SetMin(
CapAdd(m, right_->Min()));
3855 right_->SetMax(
CapSub(left_->Max(), m));
3859 const int64 left_min = left_->Min();
3860 const int64 right_min = right_->Min();
3861 const int64 left_max = left_->Max();
3862 const int64 right_max = right_->Max();
3863 if (l >
CapSub(left_min, right_max)) {
3864 left_->SetMin(
CapAdd(l, right_min));
3865 right_->SetMax(
CapSub(left_max, l));
3867 if (u <
CapSub(left_max, right_min)) {
3868 left_->SetMax(
CapAdd(u, right_max));
3869 right_->SetMin(
CapSub(left_min, u));
3874 *mi =
CapSub(left_->Min(), right_->Max());
3875 *ma =
CapSub(left_->Max(), right_->Min());
3878 int64 Max()
const override {
return CapSub(left_->Max(), right_->Min()); }
3880 void SetMax(
int64 m)
override {
3881 left_->SetMax(
CapAdd(m, right_->Max()));
3882 right_->SetMin(
CapSub(left_->Min(), m));
3890 class SubIntCstExpr :
public BaseIntExpr {
3892 SubIntCstExpr(Solver*
const s, IntExpr*
const e,
int64 v)
3893 : BaseIntExpr(s),
expr_(e), value_(v) {}
3894 ~SubIntCstExpr()
override {}
3899 bool Bound()
const override {
return (
expr_->Bound()); }
3900 std::string
name()
const override {
3901 return absl::StrFormat(
"(%d - %s)", value_,
expr_->name());
3903 std::string DebugString()
const override {
3904 return absl::StrFormat(
"(%d - %s)", value_,
expr_->DebugString());
3906 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
3907 IntVar* CastToVar()
override;
3909 void Accept(ModelVisitor*
const visitor)
const override {
3910 visitor->BeginVisitIntegerExpression(ModelVisitor::kDifference,
this);
3911 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, value_);
3912 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
3914 visitor->EndVisitIntegerExpression(ModelVisitor::kDifference,
this);
3918 IntExpr*
const expr_;
3922 IntVar* SubIntCstExpr::CastToVar() {
3925 return BaseIntExpr::CastToVar();
3927 Solver*
const s = solver();
3929 s->RegisterIntVar(s->RevAlloc(
new SubCstIntVar(s,
expr_->Var(), value_)));
3935 class OppIntExpr :
public BaseIntExpr {
3937 OppIntExpr(Solver*
const s, IntExpr*
const e) : BaseIntExpr(s),
expr_(e) {}
3938 ~OppIntExpr()
override {}
3939 int64 Min()
const override {
return (-
expr_->Max()); }
3940 void SetMin(
int64 m)
override {
expr_->SetMax(-m); }
3941 int64 Max()
const override {
return (-
expr_->Min()); }
3942 void SetMax(
int64 m)
override {
expr_->SetMin(-m); }
3943 bool Bound()
const override {
return (
expr_->Bound()); }
3944 std::string
name()
const override {
3945 return absl::StrFormat(
"(-%s)",
expr_->name());
3947 std::string DebugString()
const override {
3948 return absl::StrFormat(
"(-%s)",
expr_->DebugString());
3950 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
3951 IntVar* CastToVar()
override;
3953 void Accept(ModelVisitor*
const visitor)
const override {
3954 visitor->BeginVisitIntegerExpression(ModelVisitor::kOpposite,
this);
3955 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
3957 visitor->EndVisitIntegerExpression(ModelVisitor::kOpposite,
this);
3961 IntExpr*
const expr_;
3964 IntVar* OppIntExpr::CastToVar() {
3965 Solver*
const s = solver();
3967 s->RegisterIntVar(s->RevAlloc(
new OppIntVar(s,
expr_->Var())));
3973 class TimesIntCstExpr :
public BaseIntExpr {
3975 TimesIntCstExpr(Solver*
const s, IntExpr*
const e,
int64 v)
3976 : BaseIntExpr(s),
expr_(e), value_(v) {}
3978 ~TimesIntCstExpr()
override {}
3980 bool Bound()
const override {
return (
expr_->Bound()); }
3982 std::string
name()
const override {
3983 return absl::StrFormat(
"(%s * %d)",
expr_->name(), value_);
3986 std::string DebugString()
const override {
3987 return absl::StrFormat(
"(%s * %d)",
expr_->DebugString(), value_);
3990 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
3992 IntExpr* Expr()
const {
return expr_; }
3994 int64 Constant()
const {
return value_; }
3996 void Accept(ModelVisitor*
const visitor)
const override {
3997 visitor->BeginVisitIntegerExpression(ModelVisitor::kProduct,
this);
3998 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
4000 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, value_);
4001 visitor->EndVisitIntegerExpression(ModelVisitor::kProduct,
this);
4005 IntExpr*
const expr_;
4011 class TimesPosIntCstExpr :
public TimesIntCstExpr {
4013 TimesPosIntCstExpr(Solver*
const s, IntExpr*
const e,
int64 v)
4014 : TimesIntCstExpr(s, e, v) {
4018 ~TimesPosIntCstExpr()
override {}
4020 int64 Min()
const override {
return expr_->Min() * value_; }
4024 int64 Max()
const override {
return expr_->Max() * value_; }
4028 IntVar* CastToVar()
override {
4029 Solver*
const s = solver();
4030 IntVar*
var =
nullptr;
4031 if (
expr_->IsVar() &&
4033 var = s->RegisterIntVar(s->RevAlloc(
new TimesPosCstBoolVar(
4034 s,
reinterpret_cast<BooleanVar*
>(
expr_), value_)));
4036 var = s->RegisterIntVar(
4037 s->RevAlloc(
new TimesPosCstIntVar(s,
expr_->Var(), value_)));
4045 class SafeTimesPosIntCstExpr :
public TimesIntCstExpr {
4047 SafeTimesPosIntCstExpr(Solver*
const s, IntExpr*
const e,
int64 v)
4048 : TimesIntCstExpr(s, e, v) {
4052 ~SafeTimesPosIntCstExpr()
override {}
4056 void SetMin(
int64 m)
override {
4064 void SetMax(
int64 m)
override {
4070 IntVar* CastToVar()
override {
4071 Solver*
const s = solver();
4072 IntVar*
var =
nullptr;
4073 if (
expr_->IsVar() &&
4075 var = s->RegisterIntVar(s->RevAlloc(
new TimesPosCstBoolVar(
4076 s,
reinterpret_cast<BooleanVar*
>(
expr_), value_)));
4079 var = s->RegisterIntVar(
4080 s->RevAlloc(
new TimesPosCstIntVar(s,
expr_->Var(), value_)));
4088 class TimesIntNegCstExpr :
public TimesIntCstExpr {
4090 TimesIntNegCstExpr(Solver*
const s, IntExpr*
const e,
int64 v)
4091 : TimesIntCstExpr(s, e, v) {
4095 ~TimesIntNegCstExpr()
override {}
4099 void SetMin(
int64 m)
override {
4107 void SetMax(
int64 m)
override {
4113 IntVar* CastToVar()
override {
4114 Solver*
const s = solver();
4115 IntVar*
var =
nullptr;
4116 var = s->RegisterIntVar(
4117 s->RevAlloc(
new TimesNegCstIntVar(s,
expr_->Var(), value_)));
4125 void SetPosPosMinExpr(IntExpr*
const left, IntExpr*
const right,
int64 m) {
4128 const int64 lmax = left->Max();
4129 const int64 rmax = right->Max();
4130 if (m >
CapProd(lmax, rmax)) {
4131 left->solver()->Fail();
4133 if (m >
CapProd(left->Min(), right->Min())) {
4145 void SetPosPosMaxExpr(IntExpr*
const left, IntExpr*
const right,
int64 m) {
4148 const int64 lmin = left->Min();
4149 const int64 rmin = right->Min();
4150 if (m <
CapProd(lmin, rmin)) {
4151 left->solver()->Fail();
4153 if (m <
CapProd(left->Max(), right->Max())) {
4165 void SetPosGenMinExpr(IntExpr*
const left, IntExpr*
const right,
int64 m) {
4169 const int64 lmax = left->Max();
4170 const int64 rmax = right->Max();
4171 if (m >
CapProd(lmax, rmax)) {
4172 left->solver()->Fail();
4174 if (left->Max() == 0) {
4181 }
else if (m == 0) {
4182 const int64 lmin = left->Min();
4187 const int64 lmin = left->Min();
4196 void SetGenGenMinExpr(IntExpr*
const left, IntExpr*
const right,
int64 m) {
4201 const int64 lmin = left->Min();
4202 const int64 lmax = left->Max();
4203 const int64 rmin = right->Min();
4204 const int64 rmax = right->Max();
4206 left->solver()->Fail();
4208 if (m > lmin * rmin) {
4211 }
else if (m >
CapProd(lmax, rmax)) {
4217 void TimesSetMin(IntExpr*
const left, IntExpr*
const right,
4218 IntExpr*
const minus_left, IntExpr*
const minus_right,
4220 if (left->Min() >= 0) {
4221 if (right->Min() >= 0) {
4222 SetPosPosMinExpr(left, right, m);
4223 }
else if (right->Max() <= 0) {
4224 SetPosPosMaxExpr(left, minus_right, -m);
4226 SetPosGenMinExpr(left, right, m);
4228 }
else if (left->Max() <= 0) {
4229 if (right->Min() >= 0) {
4230 SetPosPosMaxExpr(right, minus_left, -m);
4231 }
else if (right->Max() <= 0) {
4232 SetPosPosMinExpr(minus_left, minus_right, m);
4234 SetPosGenMinExpr(minus_left, minus_right, m);
4236 }
else if (right->Min() >= 0) {
4237 SetPosGenMinExpr(right, left, m);
4238 }
else if (right->Max() <= 0) {
4239 SetPosGenMinExpr(minus_right, minus_left, m);
4242 SetGenGenMinExpr(left, right, m);
4246 class TimesIntExpr :
public BaseIntExpr {
4248 TimesIntExpr(Solver*
const s, IntExpr*
const l, IntExpr*
const r)
4252 minus_left_(s->MakeOpposite(left_)),
4253 minus_right_(s->MakeOpposite(right_)) {}
4254 ~TimesIntExpr()
override {}
4255 int64 Min()
const override {
4256 const int64 lmin = left_->Min();
4257 const int64 lmax = left_->Max();
4258 const int64 rmin = right_->Min();
4259 const int64 rmax = right_->Max();
4263 void SetMin(
int64 m)
override;
4264 int64 Max()
const override {
4265 const int64 lmin = left_->Min();
4266 const int64 lmax = left_->Max();
4267 const int64 rmin = right_->Min();
4268 const int64 rmax = right_->Max();
4272 void SetMax(
int64 m)
override;
4273 bool Bound()
const override;
4274 std::string
name()
const override {
4275 return absl::StrFormat(
"(%s * %s)", left_->name(), right_->name());
4277 std::string DebugString()
const override {
4278 return absl::StrFormat(
"(%s * %s)", left_->DebugString(),
4279 right_->DebugString());
4281 void WhenRange(Demon* d)
override {
4282 left_->WhenRange(d);
4283 right_->WhenRange(d);
4286 void Accept(ModelVisitor*
const visitor)
const override {
4287 visitor->BeginVisitIntegerExpression(ModelVisitor::kProduct,
this);
4288 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
4289 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
4291 visitor->EndVisitIntegerExpression(ModelVisitor::kProduct,
this);
4295 IntExpr*
const left_;
4296 IntExpr*
const right_;
4297 IntExpr*
const minus_left_;
4298 IntExpr*
const minus_right_;
4301 void TimesIntExpr::SetMin(
int64 m) {
4303 TimesSetMin(left_, right_, minus_left_, minus_right_, m);
4307 void TimesIntExpr::SetMax(
int64 m) {
4309 TimesSetMin(left_, minus_right_, minus_left_, right_, -m);
4313 bool TimesIntExpr::Bound()
const {
4314 const bool left_bound = left_->Bound();
4315 const bool right_bound = right_->Bound();
4316 return ((left_bound && left_->Max() == 0) ||
4317 (right_bound && right_->Max() == 0) || (left_bound && right_bound));
4322 class TimesPosIntExpr :
public BaseIntExpr {
4324 TimesPosIntExpr(Solver*
const s, IntExpr*
const l, IntExpr*
const r)
4325 : BaseIntExpr(s), left_(l), right_(r) {}
4326 ~TimesPosIntExpr()
override {}
4327 int64 Min()
const override {
return (left_->Min() * right_->Min()); }
4328 void SetMin(
int64 m)
override;
4329 int64 Max()
const override {
return (left_->Max() * right_->Max()); }
4330 void SetMax(
int64 m)
override;
4331 bool Bound()
const override;
4332 std::string
name()
const override {
4333 return absl::StrFormat(
"(%s * %s)", left_->name(), right_->name());
4335 std::string DebugString()
const override {
4336 return absl::StrFormat(
"(%s * %s)", left_->DebugString(),
4337 right_->DebugString());
4339 void WhenRange(Demon* d)
override {
4340 left_->WhenRange(d);
4341 right_->WhenRange(d);
4344 void Accept(ModelVisitor*
const visitor)
const override {
4345 visitor->BeginVisitIntegerExpression(ModelVisitor::kProduct,
this);
4346 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
4347 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
4349 visitor->EndVisitIntegerExpression(ModelVisitor::kProduct,
this);
4353 IntExpr*
const left_;
4354 IntExpr*
const right_;
4357 void TimesPosIntExpr::SetMin(
int64 m) { SetPosPosMinExpr(left_, right_, m); }
4359 void TimesPosIntExpr::SetMax(
int64 m) { SetPosPosMaxExpr(left_, right_, m); }
4361 bool TimesPosIntExpr::Bound()
const {
4362 return (left_->Max() == 0 || right_->Max() == 0 ||
4363 (left_->Bound() && right_->Bound()));
4368 class SafeTimesPosIntExpr :
public BaseIntExpr {
4370 SafeTimesPosIntExpr(Solver*
const s, IntExpr*
const l, IntExpr*
const r)
4371 : BaseIntExpr(s), left_(l), right_(r) {}
4372 ~SafeTimesPosIntExpr()
override {}
4373 int64 Min()
const override {
return CapProd(left_->Min(), right_->Min()); }
4374 void SetMin(
int64 m)
override {
4376 SetPosPosMinExpr(left_, right_, m);
4379 int64 Max()
const override {
return CapProd(left_->Max(), right_->Max()); }
4380 void SetMax(
int64 m)
override {
4382 SetPosPosMaxExpr(left_, right_, m);
4385 bool Bound()
const override {
4386 return (left_->Max() == 0 || right_->Max() == 0 ||
4387 (left_->Bound() && right_->Bound()));
4389 std::string
name()
const override {
4390 return absl::StrFormat(
"(%s * %s)", left_->name(), right_->name());
4392 std::string DebugString()
const override {
4393 return absl::StrFormat(
"(%s * %s)", left_->DebugString(),
4394 right_->DebugString());
4396 void WhenRange(Demon* d)
override {
4397 left_->WhenRange(d);
4398 right_->WhenRange(d);
4401 void Accept(ModelVisitor*
const visitor)
const override {
4402 visitor->BeginVisitIntegerExpression(ModelVisitor::kProduct,
this);
4403 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
4404 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
4406 visitor->EndVisitIntegerExpression(ModelVisitor::kProduct,
this);
4410 IntExpr*
const left_;
4411 IntExpr*
const right_;
4416 class TimesBooleanPosIntExpr :
public BaseIntExpr {
4418 TimesBooleanPosIntExpr(Solver*
const s, BooleanVar*
const b, IntExpr*
const e)
4419 : BaseIntExpr(s), boolvar_(
b),
expr_(e) {}
4420 ~TimesBooleanPosIntExpr()
override {}
4421 int64 Min()
const override {
4422 return (boolvar_->RawValue() == 1 ?
expr_->Min() : 0);
4424 void SetMin(
int64 m)
override;
4425 int64 Max()
const override {
4426 return (boolvar_->RawValue() == 0 ? 0 :
expr_->Max());
4428 void SetMax(
int64 m)
override;
4431 bool Bound()
const override;
4432 std::string
name()
const override {
4433 return absl::StrFormat(
"(%s * %s)", boolvar_->name(),
expr_->name());
4435 std::string DebugString()
const override {
4436 return absl::StrFormat(
"(%s * %s)", boolvar_->DebugString(),
4437 expr_->DebugString());
4439 void WhenRange(Demon* d)
override {
4440 boolvar_->WhenRange(d);
4441 expr_->WhenRange(d);
4444 void Accept(ModelVisitor*
const visitor)
const override {
4445 visitor->BeginVisitIntegerExpression(ModelVisitor::kProduct,
this);
4446 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument,
4448 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
4450 visitor->EndVisitIntegerExpression(ModelVisitor::kProduct,
this);
4454 BooleanVar*
const boolvar_;
4455 IntExpr*
const expr_;
4458 void TimesBooleanPosIntExpr::SetMin(
int64 m) {
4460 boolvar_->SetValue(1);
4465 void TimesBooleanPosIntExpr::SetMax(
int64 m) {
4469 if (m < expr_->Min()) {
4470 boolvar_->SetValue(0);
4472 if (boolvar_->RawValue() == 1) {
4477 void TimesBooleanPosIntExpr::Range(
int64* mi,
int64* ma) {
4478 const int value = boolvar_->RawValue();
4482 }
else if (
value == 1) {
4483 expr_->Range(mi, ma);
4490 void TimesBooleanPosIntExpr::SetRange(
int64 mi,
int64 ma) {
4491 if (ma < 0 || mi > ma) {
4495 boolvar_->SetValue(1);
4498 if (ma < expr_->Min()) {
4499 boolvar_->SetValue(0);
4501 if (boolvar_->RawValue() == 1) {
4506 bool TimesBooleanPosIntExpr::Bound()
const {
4507 return (boolvar_->RawValue() == 0 ||
expr_->Max() == 0 ||
4508 (boolvar_->RawValue() != BooleanVar::kUnboundBooleanVarValue &&
4514 class TimesBooleanIntExpr :
public BaseIntExpr {
4516 TimesBooleanIntExpr(Solver*
const s, BooleanVar*
const b, IntExpr*
const e)
4517 : BaseIntExpr(s), boolvar_(
b),
expr_(e) {}
4518 ~TimesBooleanIntExpr()
override {}
4519 int64 Min()
const override {
4520 switch (boolvar_->RawValue()) {
4525 return expr_->Min();
4528 DCHECK_EQ(BooleanVar::kUnboundBooleanVarValue, boolvar_->RawValue());
4533 void SetMin(
int64 m)
override;
4534 int64 Max()
const override {
4535 switch (boolvar_->RawValue()) {
4540 return expr_->Max();
4543 DCHECK_EQ(BooleanVar::kUnboundBooleanVarValue, boolvar_->RawValue());
4548 void SetMax(
int64 m)
override;
4551 bool Bound()
const override;
4552 std::string
name()
const override {
4553 return absl::StrFormat(
"(%s * %s)", boolvar_->name(),
expr_->name());
4555 std::string DebugString()
const override {
4556 return absl::StrFormat(
"(%s * %s)", boolvar_->DebugString(),
4557 expr_->DebugString());
4559 void WhenRange(Demon* d)
override {
4560 boolvar_->WhenRange(d);
4561 expr_->WhenRange(d);
4564 void Accept(ModelVisitor*
const visitor)
const override {
4565 visitor->BeginVisitIntegerExpression(ModelVisitor::kProduct,
this);
4566 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument,
4568 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
4570 visitor->EndVisitIntegerExpression(ModelVisitor::kProduct,
this);
4574 BooleanVar*
const boolvar_;
4575 IntExpr*
const expr_;
4578 void TimesBooleanIntExpr::SetMin(
int64 m) {
4579 switch (boolvar_->RawValue()) {
4591 DCHECK_EQ(BooleanVar::kUnboundBooleanVarValue, boolvar_->RawValue());
4593 boolvar_->SetValue(1);
4595 }
else if (m <= 0 && expr_->Max() < m) {
4596 boolvar_->SetValue(0);
4602 void TimesBooleanIntExpr::SetMax(
int64 m) {
4603 switch (boolvar_->RawValue()) {
4615 DCHECK_EQ(BooleanVar::kUnboundBooleanVarValue, boolvar_->RawValue());
4617 boolvar_->SetValue(1);
4619 }
else if (m >= 0 &&
expr_->Min() > m) {
4620 boolvar_->SetValue(0);
4626 void TimesBooleanIntExpr::Range(
int64* mi,
int64* ma) {
4627 switch (boolvar_->RawValue()) {
4639 DCHECK_EQ(BooleanVar::kUnboundBooleanVarValue, boolvar_->RawValue());
4647 void TimesBooleanIntExpr::SetRange(
int64 mi,
int64 ma) {
4651 switch (boolvar_->RawValue()) {
4653 if (mi > 0 || ma < 0) {
4659 expr_->SetRange(mi, ma);
4663 DCHECK_EQ(BooleanVar::kUnboundBooleanVarValue, boolvar_->RawValue());
4665 boolvar_->SetValue(1);
4667 }
else if (mi == 0 &&
expr_->Max() < 0) {
4668 boolvar_->SetValue(0);
4671 boolvar_->SetValue(1);
4673 }
else if (ma == 0 &&
expr_->Min() > 0) {
4674 boolvar_->SetValue(0);
4681 bool TimesBooleanIntExpr::Bound()
const {
4682 return (boolvar_->RawValue() == 0 ||
4684 (boolvar_->RawValue() != BooleanVar::kUnboundBooleanVarValue ||
4685 expr_->Max() == 0)));
4690 class DivPosIntCstExpr :
public BaseIntExpr {
4692 DivPosIntCstExpr(Solver*
const s, IntExpr*
const e,
int64 v)
4693 : BaseIntExpr(s),
expr_(e), value_(v) {
4696 ~DivPosIntCstExpr()
override {}
4698 int64 Min()
const override {
return expr_->Min() / value_; }
4700 void SetMin(
int64 m)
override {
4702 expr_->SetMin(m * value_);
4704 expr_->SetMin((m - 1) * value_ + 1);
4707 int64 Max()
const override {
return expr_->Max() / value_; }
4709 void SetMax(
int64 m)
override {
4711 expr_->SetMax((m + 1) * value_ - 1);
4713 expr_->SetMax(m * value_);
4717 std::string
name()
const override {
4718 return absl::StrFormat(
"(%s div %d)",
expr_->name(), value_);
4721 std::string DebugString()
const override {
4722 return absl::StrFormat(
"(%s div %d)",
expr_->DebugString(), value_);
4725 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
4727 void Accept(ModelVisitor*
const visitor)
const override {
4728 visitor->BeginVisitIntegerExpression(ModelVisitor::kDivide,
this);
4729 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
4731 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, value_);
4732 visitor->EndVisitIntegerExpression(ModelVisitor::kDivide,
this);
4736 IntExpr*
const expr_;
4742 class DivPosIntExpr :
public BaseIntExpr {
4744 DivPosIntExpr(Solver*
const s, IntExpr*
const num, IntExpr*
const denom)
4748 opp_num_(s->MakeOpposite(num)) {}
4750 ~DivPosIntExpr()
override {}
4752 int64 Min()
const override {
4753 return num_->Min() >= 0
4754 ? num_->Min() / denom_->Max()
4755 : (denom_->Min() == 0 ? num_->Min()
4756 : num_->Min() / denom_->Min());
4759 int64 Max()
const override {
4760 return num_->Max() >= 0 ? (denom_->Min() == 0 ? num_->Max()
4761 : num_->Max() / denom_->Min())
4762 : num_->Max() / denom_->Max();
4765 static void SetPosMin(IntExpr*
const num, IntExpr*
const denom,
int64 m) {
4766 num->SetMin(m * denom->Min());
4767 denom->SetMax(num->Max() / m);
4770 static void SetPosMax(IntExpr*
const num, IntExpr*
const denom,
int64 m) {
4771 num->SetMax((m + 1) * denom->Max() - 1);
4772 denom->SetMin(num->Min() / (m + 1) + 1);
4775 void SetMin(
int64 m)
override {
4777 SetPosMin(num_, denom_, m);
4779 SetPosMax(opp_num_, denom_, -m);
4783 void SetMax(
int64 m)
override {
4785 SetPosMax(num_, denom_, m);
4787 SetPosMin(opp_num_, denom_, -m);
4791 std::string
name()
const override {
4792 return absl::StrFormat(
"(%s div %s)", num_->name(), denom_->name());
4794 std::string DebugString()
const override {
4795 return absl::StrFormat(
"(%s div %s)", num_->DebugString(),
4796 denom_->DebugString());
4798 void WhenRange(Demon* d)
override {
4800 denom_->WhenRange(d);
4803 void Accept(ModelVisitor*
const visitor)
const override {
4804 visitor->BeginVisitIntegerExpression(ModelVisitor::kDivide,
this);
4805 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, num_);
4806 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
4808 visitor->EndVisitIntegerExpression(ModelVisitor::kDivide,
this);
4812 IntExpr*
const num_;
4813 IntExpr*
const denom_;
4814 IntExpr*
const opp_num_;
4817 class DivPosPosIntExpr :
public BaseIntExpr {
4819 DivPosPosIntExpr(Solver*
const s, IntExpr*
const num, IntExpr*
const denom)
4820 : BaseIntExpr(s), num_(num), denom_(denom) {}
4822 ~DivPosPosIntExpr()
override {}
4824 int64 Min()
const override {
4825 if (denom_->Max() == 0) {
4828 return num_->Min() / denom_->Max();
4831 int64 Max()
const override {
4832 if (denom_->Min() == 0) {
4835 return num_->Max() / denom_->Min();
4839 void SetMin(
int64 m)
override {
4841 num_->SetMin(m * denom_->Min());
4842 denom_->SetMax(num_->Max() / m);
4846 void SetMax(
int64 m)
override {
4848 num_->SetMax((m + 1) * denom_->Max() - 1);
4849 denom_->SetMin(num_->Min() / (m + 1) + 1);
4855 std::string
name()
const override {
4856 return absl::StrFormat(
"(%s div %s)", num_->name(), denom_->name());
4859 std::string DebugString()
const override {
4860 return absl::StrFormat(
"(%s div %s)", num_->DebugString(),
4861 denom_->DebugString());
4864 void WhenRange(Demon* d)
override {
4866 denom_->WhenRange(d);
4869 void Accept(ModelVisitor*
const visitor)
const override {
4870 visitor->BeginVisitIntegerExpression(ModelVisitor::kDivide,
this);
4871 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, num_);
4872 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
4874 visitor->EndVisitIntegerExpression(ModelVisitor::kDivide,
this);
4878 IntExpr*
const num_;
4879 IntExpr*
const denom_;
4884 class DivIntExpr :
public BaseIntExpr {
4886 DivIntExpr(Solver*
const s, IntExpr*
const num, IntExpr*
const denom)
4890 opp_num_(s->MakeOpposite(num)) {}
4892 ~DivIntExpr()
override {}
4894 int64 Min()
const override {
4895 const int64 num_min = num_->Min();
4896 const int64 num_max = num_->Max();
4897 const int64 denom_min = denom_->Min();
4898 const int64 denom_max = denom_->Max();
4900 if (denom_min == 0 && denom_max == 0) {
4904 if (denom_min >= 0) {
4906 const int64 adjusted_denom_min = denom_min == 0 ? 1 : denom_min;
4907 return num_min >= 0 ? num_min / denom_max : num_min / adjusted_denom_min;
4908 }
else if (denom_max <= 0) {
4910 const int64 adjusted_denom_max = denom_max == 0 ? -1 : denom_max;
4911 return num_max >= 0 ? num_max / adjusted_denom_max : num_max / denom_min;
4913 return std::min(num_min, -num_max);
4917 int64 Max()
const override {
4918 const int64 num_min = num_->Min();
4919 const int64 num_max = num_->Max();
4920 const int64 denom_min = denom_->Min();
4921 const int64 denom_max = denom_->Max();
4923 if (denom_min == 0 && denom_max == 0) {
4927 if (denom_min >= 0) {
4929 const int64 adjusted_denom_min = denom_min == 0 ? 1 : denom_min;
4930 return num_max >= 0 ? num_max / adjusted_denom_min : num_max / denom_max;
4931 }
else if (denom_max <= 0) {
4933 const int64 adjusted_denom_max = denom_max == 0 ? -1 : denom_max;
4934 return num_min >= 0 ? num_min / denom_min
4935 : -num_min / -adjusted_denom_max;
4937 return std::max(num_max, -num_min);
4941 void AdjustDenominator() {
4942 if (denom_->Min() == 0) {
4944 }
else if (denom_->Max() == 0) {
4950 static void SetPosMin(IntExpr*
const num, IntExpr*
const denom,
int64 m) {
4952 const int64 num_min = num->Min();
4953 const int64 num_max = num->Max();
4954 const int64 denom_min = denom->Min();
4955 const int64 denom_max = denom->Max();
4958 if (denom_min > 0) {
4959 num->SetMin(m * denom_min);
4960 denom->SetMax(num_max / m);
4961 }
else if (denom_max < 0) {
4962 num->SetMax(m * denom_max);
4963 denom->SetMin(num_min / m);
4967 denom->SetRange(1, num_max / m);
4968 }
else if (num_max <= 0) {
4970 denom->SetRange(num_min / m, -1);
4974 denom->SetRange(1, num_max / m);
4975 }
else if (m > num_max) {
4977 denom->SetRange(num_min / m, -1);
4979 denom->SetRange(num_min / m, num_max / m);
4986 static void SetPosMax(IntExpr*
const num, IntExpr*
const denom,
int64 m) {
4988 const int64 num_min = num->Min();
4989 const int64 num_max = num->Max();
4990 const int64 denom_min = denom->Min();
4991 const int64 denom_max = denom->Max();
4994 if (denom_min > 0) {
4995 num->SetMax((m + 1) * denom_max - 1);
4996 denom->SetMin((num_min / (m + 1)) + 1);
4997 }
else if (denom_max < 0) {
4998 num->SetMin((m + 1) * denom_min + 1);
4999 denom->SetMax(num_max / (m + 1) - 1);
5000 }
else if (num_min > (m + 1) * denom_max - 1) {
5002 }
else if (num_max < (m + 1) * denom_min + 1) {
5007 void SetMin(
int64 m)
override {
5008 AdjustDenominator();
5010 SetPosMin(num_, denom_, m);
5012 SetPosMax(opp_num_, denom_, -m);
5016 void SetMax(
int64 m)
override {
5017 AdjustDenominator();
5019 SetPosMax(num_, denom_, m);
5021 SetPosMin(opp_num_, denom_, -m);
5025 std::string
name()
const override {
5026 return absl::StrFormat(
"(%s div %s)", num_->name(), denom_->name());
5028 std::string DebugString()
const override {
5029 return absl::StrFormat(
"(%s div %s)", num_->DebugString(),
5030 denom_->DebugString());
5032 void WhenRange(Demon* d)
override {
5034 denom_->WhenRange(d);
5037 void Accept(ModelVisitor*
const visitor)
const override {
5038 visitor->BeginVisitIntegerExpression(ModelVisitor::kDivide,
this);
5039 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, num_);
5040 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
5042 visitor->EndVisitIntegerExpression(ModelVisitor::kDivide,
this);
5046 IntExpr*
const num_;
5047 IntExpr*
const denom_;
5048 IntExpr*
const opp_num_;
5053 class IntAbsConstraint :
public CastConstraint {
5055 IntAbsConstraint(Solver*
const s, IntVar*
const sub, IntVar*
const target)
5056 : CastConstraint(s, target), sub_(sub) {}
5058 ~IntAbsConstraint()
override {}
5060 void Post()
override {
5062 solver(),
this, &IntAbsConstraint::PropagateSub,
"PropagateSub");
5063 sub_->WhenRange(sub_demon);
5065 solver(),
this, &IntAbsConstraint::PropagateTarget,
"PropagateTarget");
5069 void InitialPropagate()
override {
5074 void PropagateSub() {
5075 const int64 smin = sub_->Min();
5076 const int64 smax = sub_->Max();
5079 }
else if (smin >= 0) {
5086 void PropagateTarget() {
5088 sub_->SetRange(-target_max, target_max);
5090 if (target_min > 0) {
5091 if (sub_->Min() > -target_min) {
5092 sub_->SetMin(target_min);
5093 }
else if (sub_->Max() < target_min) {
5094 sub_->SetMax(-target_min);
5099 std::string DebugString()
const override {
5100 return absl::StrFormat(
"IntAbsConstraint(%s, %s)", sub_->DebugString(),
5104 void Accept(ModelVisitor*
const visitor)
const override {
5105 visitor->BeginVisitConstraint(ModelVisitor::kAbsEqual,
this);
5106 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
5108 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
5110 visitor->EndVisitConstraint(ModelVisitor::kAbsEqual,
this);
5117 class IntAbs :
public BaseIntExpr {
5119 IntAbs(Solver*
const s, IntExpr*
const e) : BaseIntExpr(s),
expr_(e) {}
5121 ~IntAbs()
override {}
5123 int64 Min()
const override {
5126 expr_->Range(&emin, &emax);
5136 void SetMin(
int64 m)
override {
5140 expr_->Range(&emin, &emax);
5143 }
else if (emax < m) {
5149 int64 Max()
const override {
5152 expr_->Range(&emin, &emax);
5156 void SetMax(
int64 m)
override {
expr_->SetRange(-m, m); }
5159 expr_->SetRange(-ma, ma);
5163 expr_->Range(&emin, &emax);
5166 }
else if (emax < mi) {
5175 expr_->Range(&emin, &emax);
5179 }
else if (emax <= 0) {
5188 bool Bound()
const override {
return expr_->Bound(); }
5190 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
5192 std::string
name()
const override {
5193 return absl::StrFormat(
"IntAbs(%s)",
expr_->name());
5196 std::string DebugString()
const override {
5197 return absl::StrFormat(
"IntAbs(%s)",
expr_->DebugString());
5200 void Accept(ModelVisitor*
const visitor)
const override {
5201 visitor->BeginVisitIntegerExpression(ModelVisitor::kAbs,
this);
5202 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
5204 visitor->EndVisitIntegerExpression(ModelVisitor::kAbs,
this);
5207 IntVar* CastToVar()
override {
5208 int64 min_value = 0;
5209 int64 max_value = 0;
5210 Range(&min_value, &max_value);
5211 Solver*
const s = solver();
5212 const std::string
name = absl::StrFormat(
"AbsVar(%s)",
expr_->name());
5213 IntVar*
const target = s->MakeIntVar(min_value, max_value,
name);
5214 CastConstraint*
const ct =
5215 s->RevAlloc(
new IntAbsConstraint(s,
expr_->Var(), target));
5216 s->AddCastConstraint(
ct, target,
this);
5221 IntExpr*
const expr_;
5227 class IntSquare :
public BaseIntExpr {
5229 IntSquare(Solver*
const s, IntExpr*
const e) : BaseIntExpr(s),
expr_(e) {}
5230 ~IntSquare()
override {}
5232 int64 Min()
const override {
5243 void SetMin(
int64 m)
override {
5250 const int64 root =
static_cast<int64>(ceil(sqrt(
static_cast<double>(m))));
5252 expr_->SetMin(root);
5253 }
else if (emax <= 0) {
5254 expr_->SetMax(-root);
5255 }
else if (
expr_->IsVar()) {
5256 reinterpret_cast<IntVar*
>(
expr_)->RemoveInterval(-root + 1, root - 1);
5259 int64 Max()
const override {
5265 return std::max(emin * emin, emax * emax);
5267 void SetMax(
int64 m)
override {
5274 const int64 root =
static_cast<int64>(floor(sqrt(
static_cast<double>(m))));
5275 expr_->SetRange(-root, root);
5277 bool Bound()
const override {
return expr_->Bound(); }
5278 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
5279 std::string
name()
const override {
5280 return absl::StrFormat(
"IntSquare(%s)",
expr_->name());
5282 std::string DebugString()
const override {
5283 return absl::StrFormat(
"IntSquare(%s)",
expr_->DebugString());
5286 void Accept(ModelVisitor*
const visitor)
const override {
5287 visitor->BeginVisitIntegerExpression(ModelVisitor::kSquare,
this);
5288 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
5290 visitor->EndVisitIntegerExpression(ModelVisitor::kSquare,
this);
5293 IntExpr* expr()
const {
return expr_; }
5296 IntExpr*
const expr_;
5299 class PosIntSquare :
public IntSquare {
5301 PosIntSquare(Solver*
const s, IntExpr*
const e) : IntSquare(s, e) {}
5302 ~PosIntSquare()
override {}
5304 int64 Min()
const override {
5308 void SetMin(
int64 m)
override {
5312 const int64 root =
static_cast<int64>(ceil(sqrt(
static_cast<double>(m))));
5313 expr_->SetMin(root);
5315 int64 Max()
const override {
5319 void SetMax(
int64 m)
override {
5326 const int64 root =
static_cast<int64>(floor(sqrt(
static_cast<double>(m))));
5327 expr_->SetMax(root);
5336 for (
int i = 1; i < power; ++i) {
5343 return static_cast<int64>(
5344 floor(exp(log(
static_cast<double>(
kint64max)) / power)));
5347 class BasePower :
public BaseIntExpr {
5349 BasePower(Solver*
const s, IntExpr*
const e,
int64 n)
5354 ~BasePower()
override {}
5356 bool Bound()
const override {
return expr_->Bound(); }
5358 IntExpr* expr()
const {
return expr_; }
5362 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
5364 std::string
name()
const override {
5365 return absl::StrFormat(
"IntPower(%s, %d)",
expr_->name(),
pow_);
5368 std::string DebugString()
const override {
5369 return absl::StrFormat(
"IntPower(%s, %d)",
expr_->DebugString(),
pow_);
5372 void Accept(ModelVisitor*
const visitor)
const override {
5373 visitor->BeginVisitIntegerExpression(ModelVisitor::kPower,
this);
5374 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
5376 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument,
pow_);
5377 visitor->EndVisitIntegerExpression(ModelVisitor::kPower,
this);
5386 if (
pow_ % 2 == 0) {
5403 const double d_value =
static_cast<double>(
value);
5405 const double sq = exp(log(d_value) /
pow_);
5406 res =
static_cast<int64>(floor(sq));
5409 const double sq = exp(log(-d_value) /
pow_);
5410 res = -
static_cast<int64>(ceil(sq));
5412 const int64 pow_res = Pown(res + 1);
5413 if (pow_res <=
value) {
5428 const double d_value =
static_cast<double>(
value);
5430 const double sq = exp(log(d_value) /
pow_);
5431 res =
static_cast<int64>(ceil(sq));
5434 const double sq = exp(log(-d_value) /
pow_);
5435 res = -
static_cast<int64>(floor(sq));
5437 const int64 pow_res = Pown(res - 1);
5438 if (pow_res >=
value) {
5445 IntExpr*
const expr_;
5450 class IntEvenPower :
public BasePower {
5452 IntEvenPower(Solver*
const s, IntExpr*
const e,
int64 n)
5453 : BasePower(s, e, n) {
5457 ~IntEvenPower()
override {}
5459 int64 Min()
const override {
5462 expr_->Range(&emin, &emax);
5471 void SetMin(
int64 m)
override {
5477 expr_->Range(&emin, &emax);
5478 const int64 root = SqrnUp(m);
5480 expr_->SetMin(root);
5481 }
else if (emax < root) {
5482 expr_->SetMax(-root);
5483 }
else if (
expr_->IsVar()) {
5484 reinterpret_cast<IntVar*
>(
expr_)->RemoveInterval(-root + 1, root - 1);
5488 int64 Max()
const override {
5492 void SetMax(
int64 m)
override {
5499 const int64 root = SqrnDown(m);
5500 expr_->SetRange(-root, root);
5504 class PosIntEvenPower :
public BasePower {
5506 PosIntEvenPower(Solver*
const s, IntExpr*
const e,
int64 pow)
5507 : BasePower(s, e, pow) {
5511 ~PosIntEvenPower()
override {}
5513 int64 Min()
const override {
return Pown(
expr_->Min()); }
5515 void SetMin(
int64 m)
override {
5519 expr_->SetMin(SqrnUp(m));
5521 int64 Max()
const override {
return Pown(
expr_->Max()); }
5523 void SetMax(
int64 m)
override {
5530 expr_->SetMax(SqrnDown(m));
5534 class IntOddPower :
public BasePower {
5536 IntOddPower(Solver*
const s, IntExpr*
const e,
int64 n) : BasePower(s, e, n) {
5540 ~IntOddPower()
override {}
5542 int64 Min()
const override {
return Pown(
expr_->Min()); }
5544 void SetMin(
int64 m)
override {
expr_->SetMin(SqrnUp(m)); }
5546 int64 Max()
const override {
return Pown(
expr_->Max()); }
5548 void SetMax(
int64 m)
override {
expr_->SetMax(SqrnDown(m)); }
5553 class MinIntExpr :
public BaseIntExpr {
5555 MinIntExpr(Solver*
const s, IntExpr*
const l, IntExpr*
const r)
5556 : BaseIntExpr(s), left_(l), right_(r) {}
5557 ~MinIntExpr()
override {}
5558 int64 Min()
const override {
5559 const int64 lmin = left_->Min();
5560 const int64 rmin = right_->Min();
5563 void SetMin(
int64 m)
override {
5567 int64 Max()
const override {
5568 const int64 lmax = left_->Max();
5569 const int64 rmax = right_->Max();
5572 void SetMax(
int64 m)
override {
5573 if (left_->Min() > m) {
5576 if (right_->Min() > m) {
5580 std::string
name()
const override {
5581 return absl::StrFormat(
"MinIntExpr(%s, %s)", left_->name(), right_->name());
5583 std::string DebugString()
const override {
5584 return absl::StrFormat(
"MinIntExpr(%s, %s)", left_->DebugString(),
5585 right_->DebugString());
5587 void WhenRange(Demon* d)
override {
5588 left_->WhenRange(d);
5589 right_->WhenRange(d);
5592 void Accept(ModelVisitor*
const visitor)
const override {
5593 visitor->BeginVisitIntegerExpression(ModelVisitor::kMin,
this);
5594 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
5595 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
5597 visitor->EndVisitIntegerExpression(ModelVisitor::kMin,
this);
5601 IntExpr*
const left_;
5602 IntExpr*
const right_;
5607 class MinCstIntExpr :
public BaseIntExpr {
5609 MinCstIntExpr(Solver*
const s, IntExpr*
const e,
int64 v)
5610 : BaseIntExpr(s),
expr_(e), value_(v) {}
5612 ~MinCstIntExpr()
override {}
5616 void SetMin(
int64 m)
override {
5625 void SetMax(
int64 m)
override {
5631 bool Bound()
const override {
5632 return (
expr_->Bound() ||
expr_->Min() >= value_);
5635 std::string
name()
const override {
5636 return absl::StrFormat(
"MinCstIntExpr(%s, %d)",
expr_->name(), value_);
5639 std::string DebugString()
const override {
5640 return absl::StrFormat(
"MinCstIntExpr(%s, %d)",
expr_->DebugString(),
5644 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
5646 void Accept(ModelVisitor*
const visitor)
const override {
5647 visitor->BeginVisitIntegerExpression(ModelVisitor::kMin,
this);
5648 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
5650 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, value_);
5651 visitor->EndVisitIntegerExpression(ModelVisitor::kMin,
this);
5655 IntExpr*
const expr_;
5661 class MaxIntExpr :
public BaseIntExpr {
5663 MaxIntExpr(Solver*
const s, IntExpr*
const l, IntExpr*
const r)
5664 : BaseIntExpr(s), left_(l), right_(r) {}
5666 ~MaxIntExpr()
override {}
5668 int64 Min()
const override {
return std::max(left_->Min(), right_->Min()); }
5670 void SetMin(
int64 m)
override {
5671 if (left_->Max() < m) {
5674 if (right_->Max() < m) {
5680 int64 Max()
const override {
return std::max(left_->Max(), right_->Max()); }
5682 void SetMax(
int64 m)
override {
5687 std::string
name()
const override {
5688 return absl::StrFormat(
"MaxIntExpr(%s, %s)", left_->name(), right_->name());
5691 std::string DebugString()
const override {
5692 return absl::StrFormat(
"MaxIntExpr(%s, %s)", left_->DebugString(),
5693 right_->DebugString());
5696 void WhenRange(Demon* d)
override {
5697 left_->WhenRange(d);
5698 right_->WhenRange(d);
5701 void Accept(ModelVisitor*
const visitor)
const override {
5702 visitor->BeginVisitIntegerExpression(ModelVisitor::kMax,
this);
5703 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
5704 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
5706 visitor->EndVisitIntegerExpression(ModelVisitor::kMax,
this);
5710 IntExpr*
const left_;
5711 IntExpr*
const right_;
5716 class MaxCstIntExpr :
public BaseIntExpr {
5718 MaxCstIntExpr(Solver*
const s, IntExpr*
const e,
int64 v)
5719 : BaseIntExpr(s),
expr_(e), value_(v) {}
5721 ~MaxCstIntExpr()
override {}
5725 void SetMin(
int64 m)
override {
5733 void SetMax(
int64 m)
override {
5740 bool Bound()
const override {
5741 return (
expr_->Bound() ||
expr_->Max() <= value_);
5744 std::string
name()
const override {
5745 return absl::StrFormat(
"MaxCstIntExpr(%s, %d)",
expr_->name(), value_);
5748 std::string DebugString()
const override {
5749 return absl::StrFormat(
"MaxCstIntExpr(%s, %d)",
expr_->DebugString(),
5753 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
5755 void Accept(ModelVisitor*
const visitor)
const override {
5756 visitor->BeginVisitIntegerExpression(ModelVisitor::kMax,
this);
5757 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
5759 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, value_);
5760 visitor->EndVisitIntegerExpression(ModelVisitor::kMax,
this);
5764 IntExpr*
const expr_;
5776 class SimpleConvexPiecewiseExpr :
public BaseIntExpr {
5778 SimpleConvexPiecewiseExpr(Solver*
const s, IntExpr*
const e,
int64 ec,
5794 ~SimpleConvexPiecewiseExpr()
override {}
5796 int64 Min()
const override {
5799 if (vmin >= late_date_) {
5800 return (vmin - late_date_) * late_cost_;
5801 }
else if (vmax <= early_date_) {
5802 return (early_date_ - vmax) * early_cost_;
5808 void SetMin(
int64 m)
override {
5814 expr_->Range(&vmin, &vmax);
5817 (late_cost_ == 0 ? vmax : late_date_ +
PosIntDivUp(m, late_cost_) - 1);
5819 (early_cost_ == 0 ? vmin
5822 if (
expr_->IsVar()) {
5823 expr_->Var()->RemoveInterval(lb, rb);
5827 int64 Max()
const override {
5830 const int64 mr = vmax > late_date_ ? (vmax - late_date_) * late_cost_ : 0;
5832 vmin < early_date_ ? (early_date_ - vmin) * early_cost_ : 0;
5836 void SetMax(
int64 m)
override {
5840 if (late_cost_ != 0LL) {
5842 if (early_cost_ != 0LL) {
5844 expr_->SetRange(lb, rb);
5849 if (early_cost_ != 0LL) {
5856 std::string
name()
const override {
5857 return absl::StrFormat(
5858 "ConvexPiecewiseExpr(%s, ec = %d, ed = %d, ld = %d, lc = %d)",
5859 expr_->name(), early_cost_, early_date_, late_date_, late_cost_);
5862 std::string DebugString()
const override {
5863 return absl::StrFormat(
5864 "ConvexPiecewiseExpr(%s, ec = %d, ed = %d, ld = %d, lc = %d)",
5865 expr_->DebugString(), early_cost_, early_date_, late_date_, late_cost_);
5868 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
5870 void Accept(ModelVisitor*
const visitor)
const override {
5871 visitor->BeginVisitIntegerExpression(ModelVisitor::kConvexPiecewise,
this);
5872 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
5874 visitor->VisitIntegerArgument(ModelVisitor::kEarlyCostArgument,
5876 visitor->VisitIntegerArgument(ModelVisitor::kEarlyDateArgument,
5878 visitor->VisitIntegerArgument(ModelVisitor::kLateCostArgument, late_cost_);
5879 visitor->VisitIntegerArgument(ModelVisitor::kLateDateArgument, late_date_);
5880 visitor->EndVisitIntegerExpression(ModelVisitor::kConvexPiecewise,
this);
5884 IntExpr*
const expr_;
5885 const int64 early_cost_;
5886 const int64 early_date_;
5887 const int64 late_date_;
5888 const int64 late_cost_;
5893 class SemiContinuousExpr :
public BaseIntExpr {
5895 SemiContinuousExpr(Solver*
const s, IntExpr*
const e,
int64 fixed_charge,
5897 : BaseIntExpr(s),
expr_(e), fixed_charge_(fixed_charge),
step_(step) {
5902 ~SemiContinuousExpr()
override {}
5914 void SetMin(
int64 m)
override {
5925 void SetMax(
int64 m)
override {
5940 std::string
name()
const override {
5941 return absl::StrFormat(
"SemiContinuous(%s, fixed_charge = %d, step = %d)",
5945 std::string DebugString()
const override {
5946 return absl::StrFormat(
"SemiContinuous(%s, fixed_charge = %d, step = %d)",
5950 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
5952 void Accept(ModelVisitor*
const visitor)
const override {
5953 visitor->BeginVisitIntegerExpression(ModelVisitor::kSemiContinuous,
this);
5954 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
5956 visitor->VisitIntegerArgument(ModelVisitor::kFixedChargeArgument,
5958 visitor->VisitIntegerArgument(ModelVisitor::kStepArgument,
step_);
5959 visitor->EndVisitIntegerExpression(ModelVisitor::kSemiContinuous,
this);
5963 IntExpr*
const expr_;
5964 const int64 fixed_charge_;
5968 class SemiContinuousStepOneExpr :
public BaseIntExpr {
5970 SemiContinuousStepOneExpr(Solver*
const s, IntExpr*
const e,
5972 : BaseIntExpr(s),
expr_(e), fixed_charge_(fixed_charge) {
5976 ~SemiContinuousStepOneExpr()
override {}
5982 return fixed_charge_ + x;
5988 void SetMin(
int64 m)
override {
5989 if (m >= fixed_charge_ + 1) {
5990 expr_->SetMin(m - fixed_charge_);
5998 void SetMax(
int64 m)
override {
6002 if (m < fixed_charge_ + 1) {
6005 expr_->SetMax(m - fixed_charge_);
6009 std::string
name()
const override {
6010 return absl::StrFormat(
"SemiContinuousStepOne(%s, fixed_charge = %d)",
6011 expr_->name(), fixed_charge_);
6014 std::string DebugString()
const override {
6015 return absl::StrFormat(
"SemiContinuousStepOne(%s, fixed_charge = %d)",
6016 expr_->DebugString(), fixed_charge_);
6019 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
6021 void Accept(ModelVisitor*
const visitor)
const override {
6022 visitor->BeginVisitIntegerExpression(ModelVisitor::kSemiContinuous,
this);
6023 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
6025 visitor->VisitIntegerArgument(ModelVisitor::kFixedChargeArgument,
6027 visitor->VisitIntegerArgument(ModelVisitor::kStepArgument, 1);
6028 visitor->EndVisitIntegerExpression(ModelVisitor::kSemiContinuous,
this);
6032 IntExpr*
const expr_;
6033 const int64 fixed_charge_;
6036 class SemiContinuousStepZeroExpr :
public BaseIntExpr {
6038 SemiContinuousStepZeroExpr(Solver*
const s, IntExpr*
const e,
6040 : BaseIntExpr(s),
expr_(e), fixed_charge_(fixed_charge) {
6044 ~SemiContinuousStepZeroExpr()
override {}
6050 return fixed_charge_;
6056 void SetMin(
int64 m)
override {
6057 if (m >= fixed_charge_) {
6066 void SetMax(
int64 m)
override {
6070 if (m < fixed_charge_) {
6075 std::string
name()
const override {
6076 return absl::StrFormat(
"SemiContinuousStepZero(%s, fixed_charge = %d)",
6077 expr_->name(), fixed_charge_);
6080 std::string DebugString()
const override {
6081 return absl::StrFormat(
"SemiContinuousStepZero(%s, fixed_charge = %d)",
6082 expr_->DebugString(), fixed_charge_);
6085 void WhenRange(Demon* d)
override {
expr_->WhenRange(d); }
6087 void Accept(ModelVisitor*
const visitor)
const override {
6088 visitor->BeginVisitIntegerExpression(ModelVisitor::kSemiContinuous,
this);
6089 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
6091 visitor->VisitIntegerArgument(ModelVisitor::kFixedChargeArgument,
6093 visitor->VisitIntegerArgument(ModelVisitor::kStepArgument, 0);
6094 visitor->EndVisitIntegerExpression(ModelVisitor::kSemiContinuous,
this);
6098 IntExpr*
const expr_;
6099 const int64 fixed_charge_;
6103 class LinkExprAndVar :
public CastConstraint {
6105 LinkExprAndVar(Solver*
const s, IntExpr*
const expr, IntVar*
const var)
6106 : CastConstraint(s,
var),
expr_(expr) {}
6108 ~LinkExprAndVar()
override {}
6110 void Post()
override {
6111 Solver*
const s = solver();
6112 Demon* d = s->MakeConstraintInitialPropagateCallback(
this);
6113 expr_->WhenRange(d);
6117 void InitialPropagate()
override {
6120 expr_->Range(&l, &u);
6124 std::string DebugString()
const override {
6125 return absl::StrFormat(
"cast(%s, %s)",
expr_->DebugString(),
6129 void Accept(ModelVisitor*
const visitor)
const override {
6130 visitor->BeginVisitConstraint(ModelVisitor::kLinkExprVar,
this);
6131 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
6133 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
6135 visitor->EndVisitConstraint(ModelVisitor::kLinkExprVar,
this);
6139 IntExpr*
const expr_;
6144 class ExprWithEscapeValue :
public BaseIntExpr {
6146 ExprWithEscapeValue(Solver*
const s, IntVar*
const c, IntExpr*
const e,
6147 int64 unperformed_value)
6151 unperformed_value_(unperformed_value) {}
6153 ~ExprWithEscapeValue()
override {}
6155 int64 Min()
const override {
6156 if (condition_->Min() == 1) {
6157 return expression_->Min();
6158 }
else if (condition_->Max() == 1) {
6159 return std::min(unperformed_value_, expression_->Min());
6161 return unperformed_value_;
6165 void SetMin(
int64 m)
override {
6166 if (m > unperformed_value_) {
6167 condition_->SetValue(1);
6168 expression_->SetMin(m);
6169 }
else if (condition_->Min() == 1) {
6170 expression_->SetMin(m);
6171 }
else if (m > expression_->Max()) {
6172 condition_->SetValue(0);
6176 int64 Max()
const override {
6177 if (condition_->Min() == 1) {
6178 return expression_->Max();
6179 }
else if (condition_->Max() == 1) {
6180 return std::max(unperformed_value_, expression_->Max());
6182 return unperformed_value_;
6186 void SetMax(
int64 m)
override {
6187 if (m < unperformed_value_) {
6188 condition_->SetValue(1);
6189 expression_->SetMax(m);
6190 }
else if (condition_->Min() == 1) {
6191 expression_->SetMax(m);
6192 }
else if (m < expression_->Min()) {
6193 condition_->SetValue(0);
6198 if (ma < unperformed_value_ || mi > unperformed_value_) {
6199 condition_->SetValue(1);
6200 expression_->SetRange(mi, ma);
6201 }
else if (condition_->Min() == 1) {
6202 expression_->SetRange(mi, ma);
6203 }
else if (ma < expression_->Min() || mi > expression_->Max()) {
6204 condition_->SetValue(0);
6208 void SetValue(
int64 v)
override {
6209 if (v != unperformed_value_) {
6210 condition_->SetValue(1);
6211 expression_->SetValue(v);
6212 }
else if (condition_->Min() == 1) {
6213 expression_->SetValue(v);
6214 }
else if (v < expression_->Min() || v > expression_->Max()) {
6215 condition_->SetValue(0);
6219 bool Bound()
const override {
6220 return condition_->Max() == 0 || expression_->Bound();
6223 void WhenRange(Demon* d)
override {
6224 expression_->WhenRange(d);
6225 condition_->WhenBound(d);
6228 std::string DebugString()
const override {
6229 return absl::StrFormat(
"ConditionExpr(%s, %s, %d)",
6230 condition_->DebugString(),
6231 expression_->DebugString(), unperformed_value_);
6234 void Accept(ModelVisitor*
const visitor)
const override {
6235 visitor->BeginVisitIntegerExpression(ModelVisitor::kConditionalExpr,
this);
6236 visitor->VisitIntegerExpressionArgument(ModelVisitor::kVariableArgument,
6238 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
6240 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument,
6241 unperformed_value_);
6242 visitor->EndVisitIntegerExpression(ModelVisitor::kConditionalExpr,
this);
6246 IntVar*
const condition_;
6247 IntExpr*
const expression_;
6248 const int64 unperformed_value_;
6253 class LinkExprAndDomainIntVar :
public CastConstraint {
6255 LinkExprAndDomainIntVar(Solver*
const s, IntExpr*
const expr,
6256 DomainIntVar*
const var)
6257 : CastConstraint(s,
var),
6261 fail_stamp_(uint64_t{0}) {}
6263 ~LinkExprAndDomainIntVar()
override {}
6265 DomainIntVar*
var()
const {
6266 return reinterpret_cast<DomainIntVar*
>(
target_var_);
6269 void Post()
override {
6270 Solver*
const s = solver();
6271 Demon*
const d = s->MakeConstraintInitialPropagateCallback(
this);
6272 expr_->WhenRange(d);
6274 solver(),
this, &LinkExprAndDomainIntVar::Propagate,
"Propagate");
6278 void InitialPropagate()
override {
6279 expr_->SetRange(
var()->min_.Value(),
var()->max_.Value());
6280 expr_->Range(&cached_min_, &cached_max_);
6281 var()->DomainIntVar::SetRange(cached_min_, cached_max_);
6285 if (
var()->min_.Value() > cached_min_ ||
6286 var()->max_.Value() < cached_max_ ||
6287 solver()->fail_stamp() != fail_stamp_) {
6289 fail_stamp_ = solver()->fail_stamp();
6293 std::string DebugString()
const override {
6294 return absl::StrFormat(
"cast(%s, %s)",
expr_->DebugString(),
6298 void Accept(ModelVisitor*
const visitor)
const override {
6299 visitor->BeginVisitConstraint(ModelVisitor::kLinkExprVar,
this);
6300 visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
6302 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
6304 visitor->EndVisitConstraint(ModelVisitor::kLinkExprVar,
this);
6308 IntExpr*
const expr_;
6328 DomainIntVar*
const dvar =
reinterpret_cast<DomainIntVar*
>(
var);
6329 dvar->CleanInProcess();
6333 const std::vector<IntVar*>& vars) {
6334 DomainIntVar*
const dvar =
reinterpret_cast<DomainIntVar*
>(
var);
6335 CHECK(dvar !=
nullptr);
6336 return dvar->SetIsEqual(values, vars);
6340 const std::vector<int64>& values,
6341 const std::vector<IntVar*>& vars) {
6342 DomainIntVar*
const dvar =
reinterpret_cast<DomainIntVar*
>(
var);
6343 CHECK(dvar !=
nullptr);
6344 return dvar->SetIsGreaterOrEqual(values, vars);
6357 return MakeIntConst(
min,
name);
6359 if (
min == 0 &&
max == 1) {
6360 return RegisterIntVar(RevAlloc(
new ConcreteBooleanVar(
this,
name)));
6362 const std::string inner_name =
"inner_" +
name;
6363 return RegisterIntVar(
6364 MakeSum(RevAlloc(
new ConcreteBooleanVar(
this, inner_name)),
min)
6365 ->VarWithName(
name));
6367 return RegisterIntVar(RevAlloc(
new DomainIntVar(
this,
min,
max,
name)));
6372 return MakeIntVar(
min,
max,
"");
6376 return RegisterIntVar(RevAlloc(
new ConcreteBooleanVar(
this,
name)));
6380 return RegisterIntVar(RevAlloc(
new ConcreteBooleanVar(
this,
"")));
6383 IntVar* Solver::MakeIntVar(
const std::vector<int64>& values,
6384 const std::string&
name) {
6387 if (values.size() == 1)
return MakeIntConst(values[0],
name);
6389 std::vector<int64> unique_sorted_values = values;
6392 if (unique_sorted_values.size() == 1)
return MakeIntConst(values[0],
name);
6394 if (unique_sorted_values.size() ==
6395 unique_sorted_values.back() - unique_sorted_values.front() + 1) {
6396 return MakeIntVar(unique_sorted_values.front(), unique_sorted_values.back(),
6402 for (
const int64 v : unique_sorted_values) {
6406 gcd = MathUtil::GCD64(gcd, std::abs(v));
6411 return RegisterIntVar(
6412 RevAlloc(
new DomainIntVar(
this, unique_sorted_values,
name)));
6416 for (
int64& v : unique_sorted_values) {
6420 const std::string new_name =
name.empty() ?
"" :
"inner_" +
name;
6422 IntVar* inner_intvar =
nullptr;
6423 if (unique_sorted_values.size() ==
6424 unique_sorted_values.back() - unique_sorted_values.front() + 1) {
6425 inner_intvar = MakeIntVar(unique_sorted_values.front(),
6426 unique_sorted_values.back(), new_name);
6428 inner_intvar = RegisterIntVar(
6429 RevAlloc(
new DomainIntVar(
this, unique_sorted_values, new_name)));
6431 return MakeProd(inner_intvar, gcd)->Var();
6434 IntVar* Solver::MakeIntVar(
const std::vector<int64>& values) {
6435 return MakeIntVar(values,
"");
6438 IntVar* Solver::MakeIntVar(
const std::vector<int>& values,
6439 const std::string&
name) {
6443 IntVar* Solver::MakeIntVar(
const std::vector<int>& values) {
6444 return MakeIntVar(values,
"");
6451 if (absl::GetFlag(FLAGS_cp_share_int_consts) &&
name.empty() &&
6452 val >= MIN_CACHED_INT_CONST && val <= MAX_CACHED_INT_CONST) {
6453 return cached_constants_[val - MIN_CACHED_INT_CONST];
6455 return RevAlloc(
new IntConst(
this, val,
name));
6458 IntVar* Solver::MakeIntConst(
int64 val) {
return MakeIntConst(val,
""); }
6463 std::string IndexedName(
const std::string& prefix,
int index,
int max_index) {
6465 #if defined(_MSC_VER)
6466 const int digits = max_index > 0 ?
6467 static_cast<int>(log(1.0L * max_index) / log(10.0L)) + 1 :
6470 const int digits = max_index > 0 ?
static_cast<int>(log10(max_index)) + 1: 1;
6472 return absl::StrFormat(
"%s%0*d", prefix, digits,
index);
6474 return absl::StrCat(prefix,
index);
6479 void Solver::MakeIntVarArray(
int var_count,
int64 vmin,
int64 vmax,
6480 const std::string&
name,
6481 std::vector<IntVar*>* vars) {
6482 for (
int i = 0; i < var_count; ++i) {
6483 vars->push_back(MakeIntVar(vmin, vmax, IndexedName(
name, i, var_count)));
6487 void Solver::MakeIntVarArray(
int var_count,
int64 vmin,
int64 vmax,
6488 std::vector<IntVar*>* vars) {
6489 for (
int i = 0; i < var_count; ++i) {
6490 vars->push_back(MakeIntVar(vmin, vmax));
6495 const std::string&
name) {
6497 for (
int i = 0; i < var_count; ++i) {
6498 vars[i] = MakeIntVar(vmin, vmax, IndexedName(
name, i, var_count));
6503 void Solver::MakeBoolVarArray(
int var_count,
const std::string&
name,
6504 std::vector<IntVar*>* vars) {
6505 for (
int i = 0; i < var_count; ++i) {
6506 vars->push_back(MakeBoolVar(IndexedName(
name, i, var_count)));
6510 void Solver::MakeBoolVarArray(
int var_count, std::vector<IntVar*>* vars) {
6511 for (
int i = 0; i < var_count; ++i) {
6512 vars->push_back(MakeBoolVar());
6516 IntVar** Solver::MakeBoolVarArray(
int var_count,
const std::string&
name) {
6518 for (
int i = 0; i < var_count; ++i) {
6519 vars[i] = MakeBoolVar(IndexedName(
name, i, var_count));
6524 void Solver::InitCachedIntConstants() {
6525 for (
int i = MIN_CACHED_INT_CONST; i <= MAX_CACHED_INT_CONST; ++i) {
6526 cached_constants_[i - MIN_CACHED_INT_CONST] =
6527 RevAlloc(
new IntConst(
this, i,
""));
6534 if (right->
Bound()) {
6535 return MakeSum(left, right->
Min());
6537 if (left->
Bound()) {
6538 return MakeSum(right, left->
Min());
6540 if (left == right) {
6541 return MakeProd(left, 2);
6543 IntExpr* cache = model_cache_->FindExprExprExpression(
6544 left, right, ModelCache::EXPR_EXPR_SUM);
6545 if (cache ==
nullptr) {
6546 cache = model_cache_->FindExprExprExpression(right, left,
6547 ModelCache::EXPR_EXPR_SUM);
6549 if (cache !=
nullptr) {
6555 ? RegisterIntExpr(RevAlloc(
new SafePlusIntExpr(
this, left, right)))
6556 : RegisterIntExpr(RevAlloc(
new PlusIntExpr(
this, left, right)));
6557 model_cache_->InsertExprExprExpression(result, left, right,
6558 ModelCache::EXPR_EXPR_SUM);
6565 if (expr->
Bound()) {
6566 return MakeIntConst(expr->
Min() +
value);
6571 IntExpr* result = Cache()->FindExprConstantExpression(
6572 expr,
value, ModelCache::EXPR_CONSTANT_SUM);
6573 if (result ==
nullptr) {
6577 switch (
var->VarType()) {
6579 result = RegisterIntExpr(RevAlloc(
new PlusCstDomainIntVar(
6580 this,
reinterpret_cast<DomainIntVar*
>(
var),
value)));
6584 result = RegisterIntExpr(MakeIntConst(
var->Min() +
value));
6588 PlusCstVar*
const add_var =
reinterpret_cast<PlusCstVar*
>(
var);
6589 IntVar*
const sub_var = add_var->SubVar();
6590 const int64 new_constant =
value + add_var->Constant();
6591 if (new_constant == 0) {
6595 DomainIntVar*
const dvar =
6596 reinterpret_cast<DomainIntVar*
>(sub_var);
6597 result = RegisterIntExpr(
6598 RevAlloc(
new PlusCstDomainIntVar(
this, dvar, new_constant)));
6600 result = RegisterIntExpr(
6601 RevAlloc(
new PlusCstIntVar(
this, sub_var, new_constant)));
6607 SubCstIntVar*
const add_var =
reinterpret_cast<SubCstIntVar*
>(
var);
6608 IntVar*
const sub_var = add_var->SubVar();
6609 const int64 new_constant =
value + add_var->Constant();
6610 result = RegisterIntExpr(
6611 RevAlloc(
new SubCstIntVar(
this, sub_var, new_constant)));
6615 OppIntVar*
const add_var =
reinterpret_cast<OppIntVar*
>(
var);
6616 IntVar*
const sub_var = add_var->SubVar();
6618 RegisterIntExpr(RevAlloc(
new SubCstIntVar(
this, sub_var,
value)));
6623 RegisterIntExpr(RevAlloc(
new PlusCstIntVar(
this,
var,
value)));
6626 result = RegisterIntExpr(RevAlloc(
new PlusIntCstExpr(
this, expr,
value)));
6628 Cache()->InsertExprConstantExpression(result, expr,
value,
6629 ModelCache::EXPR_CONSTANT_SUM);
6637 if (left->
Bound()) {
6638 return MakeDifference(left->
Min(), right);
6640 if (right->
Bound()) {
6641 return MakeSum(left, -right->
Min());
6645 int64 left_coef = 1;
6646 int64 right_coef = 1;
6647 if (IsProduct(left, &sub_left, &left_coef) &&
6648 IsProduct(right, &sub_right, &right_coef)) {
6649 const int64 abs_gcd =
6650 MathUtil::GCD64(std::abs(left_coef), std::abs(right_coef));
6651 if (abs_gcd != 0 && abs_gcd != 1) {
6652 return MakeProd(MakeDifference(MakeProd(sub_left, left_coef / abs_gcd),
6653 MakeProd(sub_right, right_coef / abs_gcd)),
6658 IntExpr* result = Cache()->FindExprExprExpression(
6659 left, right, ModelCache::EXPR_EXPR_DIFFERENCE);
6660 if (result ==
nullptr) {
6663 result = RegisterIntExpr(RevAlloc(
new SubIntExpr(
this, left, right)));
6665 result = RegisterIntExpr(RevAlloc(
new SafeSubIntExpr(
this, left, right)));
6667 Cache()->InsertExprExprExpression(result, left, right,
6668 ModelCache::EXPR_EXPR_DIFFERENCE);
6676 if (expr->
Bound()) {
6677 return MakeIntConst(
value - expr->
Min());
6680 return MakeOpposite(expr);
6682 IntExpr* result = Cache()->FindExprConstantExpression(
6683 expr,
value, ModelCache::EXPR_CONSTANT_DIFFERENCE);
6684 if (result ==
nullptr) {
6689 switch (
var->VarType()) {
6691 PlusCstVar*
const add_var =
reinterpret_cast<PlusCstVar*
>(
var);
6692 IntVar*
const sub_var = add_var->SubVar();
6693 const int64 new_constant =
value - add_var->Constant();
6694 if (new_constant == 0) {
6697 result = RegisterIntExpr(
6698 RevAlloc(
new SubCstIntVar(
this, sub_var, new_constant)));
6703 SubCstIntVar*
const add_var =
reinterpret_cast<SubCstIntVar*
>(
var);
6704 IntVar*
const sub_var = add_var->SubVar();
6705 const int64 new_constant =
value - add_var->Constant();
6706 result = MakeSum(sub_var, new_constant);
6710 OppIntVar*
const add_var =
reinterpret_cast<OppIntVar*
>(
var);
6711 IntVar*
const sub_var = add_var->SubVar();
6712 result = MakeSum(sub_var,
value);
6717 RegisterIntExpr(RevAlloc(
new SubCstIntVar(
this,
var,
value)));
6720 result = RegisterIntExpr(RevAlloc(
new SubIntCstExpr(
this, expr,
value)));
6722 Cache()->InsertExprConstantExpression(result, expr,
value,
6723 ModelCache::EXPR_CONSTANT_DIFFERENCE);
6730 if (expr->
Bound()) {
6731 return MakeIntConst(-expr->
Min());
6734 Cache()->FindExprExpression(expr, ModelCache::EXPR_OPPOSITE);
6735 if (result ==
nullptr) {
6736 if (expr->
IsVar()) {
6737 result = RegisterIntVar(RevAlloc(
new OppIntExpr(
this, expr))->Var());
6739 result = RegisterIntExpr(RevAlloc(
new OppIntExpr(
this, expr)));
6741 Cache()->InsertExprExpression(result, expr, ModelCache::EXPR_OPPOSITE);
6748 IntExpr* result = Cache()->FindExprConstantExpression(
6749 expr,
value, ModelCache::EXPR_CONSTANT_PROD);
6750 if (result !=
nullptr) {
6761 if (m_expr->
Bound()) {
6766 return MakeOpposite(m_expr);
6770 result = RegisterIntExpr(
6771 RevAlloc(
new SafeTimesPosIntCstExpr(
this, m_expr,
coefficient)));
6773 result = RegisterIntExpr(
6774 RevAlloc(
new TimesPosIntCstExpr(
this, m_expr,
coefficient)));
6777 result = MakeIntConst(0);
6779 result = RegisterIntExpr(
6780 RevAlloc(
new TimesIntNegCstExpr(
this, m_expr,
coefficient)));
6782 if (m_expr->
IsVar() &&
6783 !absl::GetFlag(FLAGS_cp_disable_expression_optimization)) {
6784 result = result->
Var();
6786 Cache()->InsertExprConstantExpression(result, expr,
value,
6787 ModelCache::EXPR_CONSTANT_PROD);
6793 void ExtractPower(
IntExpr**
const expr,
int64*
const exponant) {
6794 if (
dynamic_cast<BasePower*
>(*expr) !=
nullptr) {
6795 BasePower*
const power =
dynamic_cast<BasePower*
>(*expr);
6796 *expr = power->expr();
6797 *exponant = power->exponant();
6799 if (
dynamic_cast<IntSquare*
>(*expr) !=
nullptr) {
6800 IntSquare*
const power =
dynamic_cast<IntSquare*
>(*expr);
6801 *expr = power->expr();
6804 if ((*expr)->IsVar()) {
6805 IntVar*
const var = (*expr)->Var();
6806 IntExpr*
const sub =
var->solver()->CastExpression(
var);
6807 if (sub !=
nullptr &&
dynamic_cast<BasePower*
>(sub) !=
nullptr) {
6808 BasePower*
const power =
dynamic_cast<BasePower*
>(sub);
6809 *expr = power->expr();
6810 *exponant = power->exponant();
6812 if (sub !=
nullptr &&
dynamic_cast<IntSquare*
>(sub) !=
nullptr) {
6813 IntSquare*
const power =
dynamic_cast<IntSquare*
>(sub);
6814 *expr = power->expr();
6822 if (
dynamic_cast<TimesCstIntVar*
>(*expr) !=
nullptr) {
6823 TimesCstIntVar*
const left_prod =
dynamic_cast<TimesCstIntVar*
>(*expr);
6825 *expr = left_prod->SubVar();
6827 }
else if (
dynamic_cast<TimesIntCstExpr*
>(*expr) !=
nullptr) {
6828 TimesIntCstExpr*
const left_prod =
dynamic_cast<TimesIntCstExpr*
>(*expr);
6830 *expr = left_prod->Expr();
6837 if (left->
Bound()) {
6838 return MakeProd(right, left->
Min());
6841 if (right->
Bound()) {
6842 return MakeProd(left, right->
Min());
6849 int64 left_exponant = 1;
6850 int64 right_exponant = 1;
6851 ExtractPower(&m_left, &left_exponant);
6852 ExtractPower(&m_right, &right_exponant);
6854 if (m_left == m_right) {
6855 return MakePower(m_left, left_exponant + right_exponant);
6863 bool modified =
false;
6866 ExtractProduct(&m_right, &
coefficient, &modified);
6868 return MakeProd(MakeProd(m_left, m_right),
coefficient);
6875 IntExpr* result = model_cache_->FindExprExprExpression(
6876 left, right, ModelCache::EXPR_EXPR_PROD);
6877 if (result ==
nullptr) {
6878 result = model_cache_->FindExprExprExpression(right, left,
6879 ModelCache::EXPR_EXPR_PROD);
6881 if (result !=
nullptr) {
6885 if (right->
Min() >= 0) {
6886 result = RegisterIntExpr(RevAlloc(
new TimesBooleanPosIntExpr(
6887 this,
reinterpret_cast<BooleanVar*
>(left), right)));
6889 result = RegisterIntExpr(RevAlloc(
new TimesBooleanIntExpr(
6890 this,
reinterpret_cast<BooleanVar*
>(left), right)));
6892 }
else if (right->
IsVar() &&
6894 if (left->
Min() >= 0) {
6895 result = RegisterIntExpr(RevAlloc(
new TimesBooleanPosIntExpr(
6896 this,
reinterpret_cast<BooleanVar*
>(right), left)));
6898 result = RegisterIntExpr(RevAlloc(
new TimesBooleanIntExpr(
6899 this,
reinterpret_cast<BooleanVar*
>(right), left)));
6901 }
else if (left->
Min() >= 0 && right->
Min() >= 0) {
6905 RegisterIntExpr(RevAlloc(
new SafeTimesPosIntExpr(
this, left, right)));
6908 RegisterIntExpr(RevAlloc(
new TimesPosIntExpr(
this, left, right)));
6911 result = RegisterIntExpr(RevAlloc(
new TimesIntExpr(
this, left, right)));
6913 model_cache_->InsertExprExprExpression(result, left, right,
6914 ModelCache::EXPR_EXPR_PROD);
6919 CHECK(numerator !=
nullptr);
6920 CHECK(denominator !=
nullptr);
6921 if (denominator->
Bound()) {
6922 return MakeDiv(numerator, denominator->
Min());
6924 IntExpr* result = model_cache_->FindExprExprExpression(
6925 numerator, denominator, ModelCache::EXPR_EXPR_DIV);
6926 if (result !=
nullptr) {
6930 if (denominator->
Min() <= 0 && denominator->
Max() >= 0) {
6931 AddConstraint(MakeNonEquality(denominator, 0));
6934 if (denominator->
Min() >= 0) {
6935 if (numerator->
Min() >= 0) {
6936 result = RevAlloc(
new DivPosPosIntExpr(
this, numerator, denominator));
6938 result = RevAlloc(
new DivPosIntExpr(
this, numerator, denominator));
6940 }
else if (denominator->
Max() <= 0) {
6941 if (numerator->
Max() <= 0) {
6942 result = RevAlloc(
new DivPosPosIntExpr(
this, MakeOpposite(numerator),
6943 MakeOpposite(denominator)));
6945 result = MakeOpposite(RevAlloc(
6946 new DivPosIntExpr(
this, numerator, MakeOpposite(denominator))));
6949 result = RevAlloc(
new DivIntExpr(
this, numerator, denominator));
6951 model_cache_->InsertExprExprExpression(result, numerator, denominator,
6952 ModelCache::EXPR_EXPR_DIV);
6957 CHECK(expr !=
nullptr);
6959 if (expr->
Bound()) {
6960 return MakeIntConst(expr->
Min() /
value);
6961 }
else if (
value == 1) {
6963 }
else if (
value == -1) {
6964 return MakeOpposite(expr);
6965 }
else if (
value > 0) {
6966 return RegisterIntExpr(RevAlloc(
new DivPosIntCstExpr(
this, expr,
value)));
6967 }
else if (
value == 0) {
6968 LOG(
FATAL) <<
"Cannot divide by 0";
6971 return RegisterIntExpr(
6972 MakeOpposite(RevAlloc(
new DivPosIntCstExpr(
this, expr, -
value))));
6978 if (Cache()->FindExprExpression(
var, ModelCache::EXPR_ABS) ==
nullptr) {
6979 Cache()->InsertExprExpression(abs_var,
var, ModelCache::EXPR_ABS);
6981 return RevAlloc(
new IntAbsConstraint(
this,
var, abs_var));
6986 if (e->
Min() >= 0) {
6988 }
else if (e->
Max() <= 0) {
6989 return MakeOpposite(e);
6991 IntExpr* result = Cache()->FindExprExpression(e, ModelCache::EXPR_ABS);
6992 if (result ==
nullptr) {
6996 result = MakeProd(MakeAbs(expr), std::abs(
coefficient));
6998 result = RegisterIntExpr(RevAlloc(
new IntAbs(
this, e)));
7000 Cache()->InsertExprExpression(result, e, ModelCache::EXPR_ABS);
7007 if (expr->
Bound()) {
7009 return MakeIntConst(v * v);
7011 IntExpr* result = Cache()->FindExprExpression(expr, ModelCache::EXPR_SQUARE);
7012 if (result ==
nullptr) {
7013 if (expr->
Min() >= 0) {
7014 result = RegisterIntExpr(RevAlloc(
new PosIntSquare(
this, expr)));
7016 result = RegisterIntExpr(RevAlloc(
new IntSquare(
this, expr)));
7018 Cache()->InsertExprExpression(result, expr, ModelCache::EXPR_SQUARE);
7026 if (expr->
Bound()) {
7028 if (v >= OverflowLimit(n)) {
7031 return MakeIntConst(IntPower(v, n));
7035 return MakeIntConst(1);
7039 return MakeSquare(expr);
7043 if (expr->
Min() >= 0) {
7045 RegisterIntExpr(RevAlloc(
new PosIntEvenPower(
this, expr, n)));
7047 result = RegisterIntExpr(RevAlloc(
new IntEvenPower(
this, expr, n)));
7050 result = RegisterIntExpr(RevAlloc(
new IntOddPower(
this, expr, n)));
7060 if (left->
Bound()) {
7061 return MakeMin(right, left->
Min());
7063 if (right->
Bound()) {
7064 return MakeMin(left, right->
Min());
7066 if (left->
Min() >= right->
Max()) {
7069 if (right->
Min() >= left->
Max()) {
7072 return RegisterIntExpr(RevAlloc(
new MinIntExpr(
this, left, right)));
7077 if (value <= expr->Min()) {
7078 return MakeIntConst(
value);
7080 if (expr->
Bound()) {
7086 return RegisterIntExpr(RevAlloc(
new MinCstIntExpr(
this, expr,
value)));
7090 return MakeMin(expr,
static_cast<int64>(
value));
7096 if (left->
Bound()) {
7097 return MakeMax(right, left->
Min());
7099 if (right->
Bound()) {
7100 return MakeMax(left, right->
Min());
7102 if (left->
Min() >= right->
Max()) {
7105 if (right->
Min() >= left->
Max()) {
7108 return RegisterIntExpr(RevAlloc(
new MaxIntExpr(
this, left, right)));
7113 if (expr->
Bound()) {
7116 if (value <= expr->Min()) {
7120 return MakeIntConst(
value);
7122 return RegisterIntExpr(RevAlloc(
new MaxCstIntExpr(
this, expr,
value)));
7126 return MakeMax(expr,
static_cast<int64>(
value));
7132 return RegisterIntExpr(RevAlloc(
new SimpleConvexPiecewiseExpr(
7133 this, expr, early_cost, early_date, late_date, late_cost)));
7139 if (fixed_charge == 0) {
7140 return MakeIntConst(
int64{0});
7142 return RegisterIntExpr(
7143 RevAlloc(
new SemiContinuousStepZeroExpr(
this, expr, fixed_charge)));
7145 }
else if (step == 1) {
7146 return RegisterIntExpr(
7147 RevAlloc(
new SemiContinuousStepOneExpr(
this, expr, fixed_charge)));
7149 return RegisterIntExpr(
7150 RevAlloc(
new SemiContinuousExpr(
this, expr, fixed_charge, step)));
7165 return f_.GetMinimum(
expr_->Min(),
expr_->Max());
7169 f_.GetSmallestRangeGreaterThanValue(
expr_->Min(),
expr_->Max(), m);
7170 expr_->SetRange(range.first, range.second);
7174 return f_.GetMaximum(
expr_->Min(),
expr_->Max());
7179 f_.GetSmallestRangeLessThanValue(
expr_->Min(),
expr_->Max(), m);
7180 expr_->SetRange(range.first, range.second);
7185 f_.GetSmallestRangeInValueRange(
expr_->Min(),
expr_->Max(), l, u);
7186 expr_->SetRange(range.first, range.second);
7188 std::string
name()
const override {
7189 return absl::StrFormat(
"PiecewiseLinear(%s, f = %s)",
expr_->name(),
7194 return absl::StrFormat(
"PiecewiseLinear(%s, f = %s)",
expr_->DebugString(),
7218 int64 unperformed_value) {
7219 if (condition->
Min() == 1) {
7221 }
else if (condition->
Max() == 0) {
7222 return MakeIntConst(unperformed_value);
7224 IntExpr* cache = Cache()->FindExprExprConstantExpression(
7225 condition, expr, unperformed_value,
7226 ModelCache::EXPR_EXPR_CONSTANT_CONDITIONAL);
7227 if (cache ==
nullptr) {
7229 new ExprWithEscapeValue(
this, condition, expr, unperformed_value));
7230 Cache()->InsertExprExprConstantExpression(
7231 cache, condition, expr, unperformed_value,
7232 ModelCache::EXPR_EXPR_CONSTANT_CONDITIONAL);
7242 MakeDifference(x, MakeProd(MakeDiv(x, mod), mod))->
Var();
7244 AddConstraint(MakeBetweenCt(result, 0, mod - 1));
7246 AddConstraint(MakeBetweenCt(result, mod + 1, 0));
7253 return MakeModulo(x, mod->
Min());
7256 MakeDifference(x, MakeProd(MakeDiv(x, mod), mod))->
Var();
7257 AddConstraint(MakeLess(result, MakeAbs(mod)));
7258 AddConstraint(MakeGreater(result, MakeOpposite(MakeAbs(mod))));
7266 void IntVar::RemoveValues(
const std::vector<int64>& values) {
7268 const int size = values.size();
7275 RemoveValue(values[0]);
7279 RemoveValue(values[0]);
7280 RemoveValue(values[1]);
7284 RemoveValue(values[0]);
7285 RemoveValue(values[1]);
7286 RemoveValue(values[2]);
7292 int start_index = 0;
7293 int64 new_min = Min();
7294 if (values[start_index] <= new_min) {
7295 while (start_index < size - 1 &&
7296 values[start_index + 1] == values[start_index] + 1) {
7297 new_min = values[start_index + 1] + 1;
7301 int end_index = size - 1;
7302 int64 new_max = Max();
7303 if (values[end_index] >= new_max) {
7304 while (end_index > start_index + 1 &&
7305 values[end_index - 1] == values[end_index] - 1) {
7306 new_max = values[end_index - 1] - 1;
7310 SetRange(new_min, new_max);
7311 for (
int i = start_index; i <= end_index; ++i) {
7312 RemoveValue(values[i]);
7319 IntExpr*
const casted = solver()->CastExpression(
this);
7323 void IntVar::SetValues(
const std::vector<int64>& values) {
7324 switch (values.size()) {
7330 SetValue(values.back());
7334 if (Contains(values[0])) {
7335 if (Contains(values[1])) {
7340 RemoveInterval(l + 1, u - 1);
7343 SetValue(values[0]);
7346 SetValue(values[1]);
7357 std::vector<int64>& tmp = solver()->tmp_vector_;
7359 tmp.insert(tmp.end(), values.begin(), values.end());
7360 std::sort(tmp.begin(), tmp.end());
7361 tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
7362 const int size = tmp.size();
7363 const int64 vmin = Min();
7364 const int64 vmax = Max();
7366 int last = size - 1;
7367 if (tmp.front() > vmax || tmp.back() < vmin) {
7371 while (tmp[first] < vmin || !Contains(tmp[first])) {
7373 if (first > last || tmp[first] > vmax) {
7377 while (last > first && (tmp[last] > vmax || !Contains(tmp[last]))) {
7382 SetRange(tmp[first], tmp[last]);
7383 while (first < last) {
7384 const int64 start = tmp[first] + 1;
7385 const int64 end = tmp[first + 1] - 1;
7387 RemoveInterval(start, end);
7397 if (!
var->Bound()) {
7399 DomainIntVar* dvar =
reinterpret_cast<DomainIntVar*
>(
var);
7401 s->
RevAlloc(
new LinkExprAndDomainIntVar(s, expr, dvar)), dvar, expr);
7410 if (var_ ==
nullptr) {
7411 solver()->SaveValue(
reinterpret_cast<void**
>(&var_));
7419 Range(&vmin, &vmax);
7420 IntVar*
const var = solver()->MakeIntVar(vmin, vmax);
7428 if (expr->
IsVar()) {
7430 expr = CastExpression(expr_var);
7434 SubIntExpr*
const sub_expr =
dynamic_cast<SubIntExpr*
>(expr);
7435 if (sub_expr !=
nullptr) {
7436 *left = sub_expr->left();
7437 *right = sub_expr->right();
7444 bool* is_negated)
const {
7446 *inner_var = expr->
Var();
7447 *is_negated =
false;
7450 SubCstIntVar*
const sub_var =
reinterpret_cast<SubCstIntVar*
>(expr);
7451 if (sub_var !=
nullptr && sub_var->Constant() == 1 &&
7454 *inner_var = sub_var->SubVar();
7463 if (
dynamic_cast<TimesCstIntVar*
>(expr) !=
nullptr) {
7464 TimesCstIntVar*
const var =
dynamic_cast<TimesCstIntVar*
>(expr);
7466 *inner_expr =
var->SubVar();
7468 }
else if (
dynamic_cast<TimesIntCstExpr*
>(expr) !=
nullptr) {
7469 TimesIntCstExpr*
const prod =
dynamic_cast<TimesIntCstExpr*
>(expr);
7471 *inner_expr = prod->Expr();
7479 #undef COND_REV_ALLOC
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_LT(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK_GE(val1, val2)
#define CHECK_NE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
This is the base class for all expressions that are not variables.
A BaseObject is the root of all reversibly allocated objects.
IntVar * IsDifferent(int64 constant) override
void RemoveInterval(int64 l, int64 u) override
This method removes the interval 'l' .
virtual void RestoreValue()=0
void SetMax(int64 m) override
IntVar * IsLessOrEqual(int64 constant) override
void WhenBound(Demon *d) override
This method attaches a demon that will be awakened when the variable is bound.
bool Contains(int64 v) const override
This method returns whether the value 'v' is in the domain of the variable.
SimpleRevFIFO< Demon * > delayed_bound_demons_
static const int kUnboundBooleanVarValue
void SetRange(int64 mi, int64 ma) override
This method sets both the min and the max of the expression.
void RemoveValue(int64 v) override
This method removes the value 'v' from the domain of the variable.
IntVar * IsEqual(int64 constant) override
IsEqual.
IntVar * IsGreaterOrEqual(int64 constant) override
SimpleRevFIFO< Demon * > bound_demons_
void SetMin(int64 m) override
std::string DebugString() const override
uint64 Size() const override
This method returns the number of values in the domain of the variable.
A constraint is the main modeling object.
A Demon is the base element of a propagation queue.
virtual Solver::DemonPriority priority() const
This method returns the priority of the demon.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual IntVar * Var()=0
Creates a variable from the expression.
virtual void SetValue(int64 v)
This method sets the value of the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual bool IsVar() const
Returns true if the expression is indeed a variable.
virtual int64 Max() const =0
IntVar * VarWithName(const std::string &name)
Creates a variable from the expression and set the name of the resulting var.
virtual int64 Min() const =0
The class IntVar is a subset of IntExpr.
IntVar * Var() override
Creates a variable from the expression.
virtual int VarType() const
The class Iterator has two direct subclasses.
@ EXPR_CONSTANT_IS_GREATER_OR_EQUAL
@ EXPR_CONSTANT_IS_NOT_EQUAL
@ EXPR_CONSTANT_IS_LESS_OR_EQUAL
virtual void VisitIntegerVariable(const IntVar *const variable, IntExpr *const delegate)
static const char kVarValueWatcher[]
static const char kVarsArgument[]
static const char kVarBoundWatcher[]
static const char kVariableArgument[]
static const char kValuesArgument[]
void Decr(Solver *const s)
void Incr(Solver *const s)
void SetMax(int64 m) override
void SetRange(int64 l, int64 u) override
This method sets both the min and the max of the expression.
PiecewiseLinearExpr(Solver *solver, IntExpr *expr, const PiecewiseLinearFunction &f)
void WhenRange(Demon *d) override
Attach a demon that will watch the min or the max of the expression.
int64 Min() const override
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
std::string name() const override
Object naming.
~PiecewiseLinearExpr() override
void SetMin(int64 m) override
std::string DebugString() const override
int64 Max() const override
virtual std::string name() const
Object naming.
void set_name(const std::string &name)
void SetValue(Solver *const s, const T &val)
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
@ OUTSIDE_SEARCH
Before search, after search.
IntExpr * MakeDifference(IntExpr *const left, IntExpr *const right)
left - right
T * RevAlloc(T *object)
Registers the given object as being reversible.
void AddCastConstraint(CastConstraint *const constraint, IntVar *const target_var, IntExpr *const expr)
Adds 'constraint' to the solver and marks it as a cast constraint, that is, a constraint created call...
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
IntVar * MakeIntConst(int64 val, const std::string &name)
IntConst will create a constant expression.
std::vector< IntVarIterator * > holes_
#define COND_REV_ALLOC(rev, alloc)
ABSL_FLAG(bool, cp_disable_expression_optimization, false, "Disable special optimization when creating expressions.")
IntVarIterator *const iterator_
static const int64 kint64max
static const int32 kint32max
static const int64 kint64min
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
int RemoveAt(RepeatedType *array, const IndexContainer &indices)
const Collection::value_type::second_type FindPtrOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
std::function< int64(const Model &)> Value(IntegerVariable v)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int LeastSignificantBitPosition64(uint64 n)
void InternalSaveBooleanVarValue(Solver *const solver, IntVar *const var)
uint32 BitPos64(uint64 pos)
int64 CapSub(int64 x, int64 y)
void CleanVariableOnFail(IntVar *const var)
int MostSignificantBitPosition64(uint64 n)
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
uint64 BitCount64(uint64 n)
int64 SubOverflows(int64 x, int64 y)
int64 PosIntDivUp(int64 e, int64 v)
int64 UnsafeLeastSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 BitOffset64(uint64 pos)
bool IsBitSet64(const uint64 *const bitset, uint64 pos)
Constraint * SetIsGreaterOrEqual(IntVar *const var, const std::vector< int64 > &values, const std::vector< IntVar * > &vars)
static const uint64 kAllBits64
int64 PosIntDivDown(int64 e, int64 v)
void RegisterDemon(Solver *const solver, Demon *const demon, DemonProfiler *const monitor)
int64 CapAdd(int64 x, int64 y)
void RestoreBoolValue(IntVar *const var)
uint64 OneRange64(uint64 s, uint64 e)
Constraint * SetIsEqual(IntVar *const var, const std::vector< int64 > &values, const std::vector< IntVar * > &vars)
int64 CapProd(int64 x, int64 y)
uint64 BitCountRange64(const uint64 *const bitset, uint64 start, uint64 end)
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
void LinkVarExpr(Solver *const s, IntExpr *const expr, IntVar *const var)
int64 UnsafeMostSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 BitLength64(uint64 size)
bool AddOverflows(int64 x, int64 y)
IntervalVar *const target_var_