22 #include "absl/strings/str_format.h"
23 #include "absl/strings/str_join.h"
36 class TreeArrayConstraint :
public CastConstraint {
38 TreeArrayConstraint(Solver*
const solver,
const std::vector<IntVar*>& vars,
39 IntVar*
const sum_var)
40 : CastConstraint(solver, sum_var),
42 block_size_(solver->
parameters().array_split_size()) {
43 std::vector<int> lengths;
44 lengths.push_back(
vars_.size());
45 while (lengths.back() > 1) {
46 const int current = lengths.back();
47 lengths.push_back((current + block_size_ - 1) / block_size_);
49 tree_.resize(lengths.size());
50 for (
int i = 0; i < lengths.size(); ++i) {
51 tree_[i].resize(lengths[lengths.size() - i - 1]);
55 root_node_ = &tree_[0][0];
58 std::string DebugStringInternal(
const std::string&
name)
const {
59 return absl::StrFormat(
"%s(%s) == %s",
name,
64 void AcceptInternal(
const std::string&
name,
65 ModelVisitor*
const visitor)
const {
66 visitor->BeginVisitConstraint(
name,
this);
71 visitor->EndVisitConstraint(
name,
this);
75 void ReduceRange(
int depth,
int position,
int64 delta_min,
int64 delta_max) {
76 NodeInfo*
const info = &tree_[depth][position];
78 info->node_min.SetValue(solver(),
79 CapAdd(info->node_min.Value(), delta_min));
82 info->node_max.SetValue(solver(),
83 CapSub(info->node_max.Value(), delta_max));
88 void SetRange(
int depth,
int position,
int64 new_min,
int64 new_max) {
89 NodeInfo*
const info = &tree_[depth][position];
90 if (new_min > info->node_min.Value()) {
91 info->node_min.SetValue(solver(), new_min);
93 if (new_max < info->
node_max.Value()) {
94 info->node_max.SetValue(solver(), new_max);
98 void InitLeaf(
int position,
int64 var_min,
int64 var_max) {
99 InitNode(MaxDepth(), position, var_min, var_max);
103 tree_[depth][position].node_min.SetValue(solver(),
node_min);
104 tree_[depth][position].node_max.SetValue(solver(),
node_max);
107 int64 Min(
int depth,
int position)
const {
108 return tree_[depth][position].node_min.Value();
111 int64 Max(
int depth,
int position)
const {
112 return tree_[depth][position].node_max.Value();
115 int64 RootMin()
const {
return root_node_->node_min.Value(); }
117 int64 RootMax()
const {
return root_node_->node_max.Value(); }
119 int Parent(
int position)
const {
return position / block_size_; }
121 int ChildStart(
int position)
const {
return position * block_size_; }
123 int ChildEnd(
int depth,
int position)
const {
125 return std::min((position + 1) * block_size_ - 1, Width(depth + 1) - 1);
128 bool IsLeaf(
int depth)
const {
return depth == MaxDepth(); }
130 int MaxDepth()
const {
return tree_.size() - 1; }
132 int Width(
int depth)
const {
return tree_[depth].size(); }
144 std::vector<std::vector<NodeInfo> > tree_;
145 const int block_size_;
146 NodeInfo* root_node_;
161 class SumConstraint :
public TreeArrayConstraint {
163 SumConstraint(Solver*
const solver,
const std::vector<IntVar*>& vars,
164 IntVar*
const sum_var)
165 : TreeArrayConstraint(solver, vars, sum_var), sum_demon_(
nullptr) {}
167 ~SumConstraint()
override {}
169 void Post()
override {
170 for (
int i = 0; i <
vars_.size(); ++i) {
172 solver(),
this, &SumConstraint::LeafChanged,
"LeafChanged", i);
173 vars_[i]->WhenRange(demon);
176 solver(),
this, &SumConstraint::SumChanged,
"SumChanged"));
180 void InitialPropagate()
override {
182 for (
int i = 0; i <
vars_.size(); ++i) {
183 InitLeaf(i,
vars_[i]->Min(),
vars_[i]->Max());
186 for (
int i = MaxDepth() - 1; i >= 0; --i) {
187 for (
int j = 0; j < Width(i); ++j) {
190 const int block_start = ChildStart(j);
191 const int block_end = ChildEnd(i, j);
192 for (
int k = block_start; k <= block_end; ++k) {
193 sum_min =
CapAdd(sum_min, Min(i + 1, k));
194 sum_max =
CapAdd(sum_max, Max(i + 1, k));
196 InitNode(i, j, sum_min, sum_max);
209 for (
int i = 0; i <
vars_.size(); ++i) {
215 for (
int i = 0; i <
vars_.size(); ++i) {
223 void PushDown(
int depth,
int position,
int64 new_min,
int64 new_max) {
225 if (new_min <= Min(depth, position) && new_max >= Max(depth, position)) {
231 vars_[position]->SetRange(new_min, new_max);
239 const int64 sum_min = Min(depth, position);
240 const int64 sum_max = Max(depth, position);
243 new_max =
std::min(sum_max, new_max);
244 new_min =
std::max(sum_min, new_min);
247 if (new_max < sum_min || new_min > sum_max) {
252 const int block_start = ChildStart(position);
253 const int block_end = ChildEnd(depth, position);
254 for (
int i = block_start; i <= block_end; ++i) {
255 const int64 target_var_min = Min(depth + 1, i);
256 const int64 target_var_max = Max(depth + 1, i);
257 const int64 residual_min =
CapSub(sum_min, target_var_min);
258 const int64 residual_max =
CapSub(sum_max, target_var_max);
259 PushDown(depth + 1, i,
CapSub(new_min, residual_max),
260 CapSub(new_max, residual_min));
266 void LeafChanged(
int term_index) {
267 IntVar*
const var =
vars_[term_index];
270 EnqueueDelayedDemon(sum_demon_);
273 void PushUp(
int position,
int64 delta_min,
int64 delta_max) {
277 for (
int depth = MaxDepth(); depth >= 0; --depth) {
278 ReduceRange(depth, position, delta_min, delta_max);
279 position = Parent(position);
285 std::string DebugString()
const override {
286 return DebugStringInternal(
"Sum");
289 void Accept(ModelVisitor*
const visitor)
const override {
298 class SmallSumConstraint :
public Constraint {
300 SmallSumConstraint(Solver*
const solver,
const std::vector<IntVar*>& vars,
301 IntVar*
const target_var)
302 : Constraint(solver),
307 sum_demon_(nullptr) {}
309 ~SmallSumConstraint()
override {}
311 void Post()
override {
312 for (
int i = 0; i <
vars_.size(); ++i) {
313 if (!
vars_[i]->Bound()) {
315 solver(),
this, &SmallSumConstraint::VarChanged,
"VarChanged",
317 vars_[i]->WhenRange(demon);
321 solver(),
this, &SmallSumConstraint::SumChanged,
"SumChanged"));
325 void InitialPropagate()
override {
335 computed_min_.SetValue(solver(), sum_min);
336 computed_max_.SetValue(solver(), sum_max);
346 const int64 sum_min = computed_min_.Value();
347 const int64 sum_max = computed_max_.Value();
348 if (new_max == sum_min && new_max !=
kint64max) {
350 for (
int i = 0; i <
vars_.size(); ++i) {
353 }
else if (new_min == sum_max && new_min !=
kint64min) {
355 for (
int i = 0; i <
vars_.size(); ++i) {
359 if (new_min > sum_min || new_max < sum_max) {
361 new_max =
std::min(sum_max, new_max);
362 new_min =
std::max(sum_min, new_min);
365 if (new_max < sum_min || new_min > sum_max) {
373 const int64 residual_min =
CapSub(sum_min, var_min);
374 const int64 residual_max =
CapSub(sum_max, var_max);
375 var->SetRange(
CapSub(new_min, residual_max),
376 CapSub(new_max, residual_min));
382 void VarChanged(IntVar*
var) {
385 computed_min_.Add(solver(), delta_min);
386 computed_max_.Add(solver(), -delta_max);
389 target_var_->SetRange(computed_min_.Value(), computed_max_.Value());
391 EnqueueDelayedDemon(sum_demon_);
395 std::string DebugString()
const override {
396 return absl::StrFormat(
"SmallSum(%s) == %s",
401 void Accept(ModelVisitor*
const visitor)
const override {
411 const std::vector<IntVar*>
vars_;
413 NumericalRev<int64> computed_min_;
414 NumericalRev<int64> computed_max_;
419 bool DetectSumOverflow(
const std::vector<IntVar*>& vars) {
422 for (
int i = 0; i < vars.size(); ++i) {
423 sum_min =
CapAdd(sum_min, vars[i]->Min());
424 sum_max =
CapAdd(sum_max, vars[i]->Max());
433 class SafeSumConstraint :
public TreeArrayConstraint {
435 SafeSumConstraint(Solver*
const solver,
const std::vector<IntVar*>& vars,
436 IntVar*
const sum_var)
437 : TreeArrayConstraint(solver, vars, sum_var), sum_demon_(nullptr) {}
439 ~SafeSumConstraint()
override {}
441 void Post()
override {
442 for (
int i = 0; i <
vars_.size(); ++i) {
444 solver(),
this, &SafeSumConstraint::LeafChanged,
"LeafChanged", i);
445 vars_[i]->WhenRange(demon);
448 solver(),
this, &SafeSumConstraint::SumChanged,
"SumChanged"));
452 void SafeComputeNode(
int depth,
int position,
int64*
const sum_min,
453 int64*
const sum_max) {
455 const int block_start = ChildStart(position);
456 const int block_end = ChildEnd(depth, position);
457 for (
int k = block_start; k <= block_end; ++k) {
459 *sum_min =
CapAdd(*sum_min, Min(depth + 1, k));
462 *sum_max =
CapAdd(*sum_max, Max(depth + 1, k));
470 void InitialPropagate()
override {
472 for (
int i = 0; i <
vars_.size(); ++i) {
473 InitLeaf(i,
vars_[i]->Min(),
vars_[i]->Max());
476 for (
int i = MaxDepth() - 1; i >= 0; --i) {
477 for (
int j = 0; j < Width(i); ++j) {
480 SafeComputeNode(i, j, &sum_min, &sum_max);
481 InitNode(i, j, sum_min, sum_max);
492 DCHECK(CheckInternalState());
495 for (
int i = 0; i <
vars_.size(); ++i) {
500 for (
int i = 0; i <
vars_.size(); ++i) {
508 void PushDown(
int depth,
int position,
int64 new_min,
int64 new_max) {
510 if (new_min <= Min(depth, position) && new_max >= Max(depth, position)) {
516 vars_[position]->SetRange(new_min, new_max);
524 const int64 sum_min = Min(depth, position);
525 const int64 sum_max = Max(depth, position);
528 new_max =
std::min(sum_max, new_max);
529 new_min =
std::max(sum_min, new_min);
532 if (new_max < sum_min || new_min > sum_max) {
537 const int block_start = ChildStart(position);
538 const int block_end = ChildEnd(depth, position);
539 for (
int pos = block_start; pos <= block_end; ++pos) {
540 const int64 target_var_min = Min(depth + 1, pos);
541 const int64 residual_min =
543 const int64 target_var_max = Max(depth + 1, pos);
544 const int64 residual_max =
546 PushDown(depth + 1, pos,
548 :
CapSub(new_min, residual_max)),
550 :
CapSub(new_max, residual_min)));
556 void LeafChanged(
int term_index) {
557 IntVar*
const var =
vars_[term_index];
560 EnqueueDelayedDemon(sum_demon_);
563 void PushUp(
int position,
int64 delta_min,
int64 delta_max) {
566 if (
CapAdd(delta_min, delta_max) == 0) {
571 bool delta_corrupted =
false;
572 for (
int depth = MaxDepth(); depth >= 0; --depth) {
575 delta_max !=
kint64max && !delta_corrupted) {
576 ReduceRange(depth, position, delta_min, delta_max);
577 }
else if (depth == MaxDepth()) {
578 SetRange(depth, position,
vars_[position]->Min(),
579 vars_[position]->Max());
580 delta_corrupted =
true;
584 SafeComputeNode(depth, position, &sum_min, &sum_max);
588 SetRange(depth, position, sum_min, sum_max);
589 delta_corrupted =
true;
591 position = Parent(position);
597 std::string DebugString()
const override {
598 return DebugStringInternal(
"Sum");
601 void Accept(ModelVisitor*
const visitor)
const override {
606 bool CheckInternalState() {
607 for (
int i = 0; i <
vars_.size(); ++i) {
608 CheckLeaf(i,
vars_[i]->Min(),
vars_[i]->Max());
611 for (
int i = MaxDepth() - 1; i >= 0; --i) {
612 for (
int j = 0; j < Width(i); ++j) {
615 SafeComputeNode(i, j, &sum_min, &sum_max);
616 CheckNode(i, j, sum_min, sum_max);
622 void CheckLeaf(
int position,
int64 var_min,
int64 var_max) {
623 CheckNode(MaxDepth(), position, var_min, var_max);
637 class MinConstraint :
public TreeArrayConstraint {
639 MinConstraint(Solver*
const solver,
const std::vector<IntVar*>& vars,
640 IntVar*
const min_var)
641 : TreeArrayConstraint(solver, vars, min_var), min_demon_(nullptr) {}
643 ~MinConstraint()
override {}
645 void Post()
override {
646 for (
int i = 0; i <
vars_.size(); ++i) {
648 solver(),
this, &MinConstraint::LeafChanged,
"LeafChanged", i);
649 vars_[i]->WhenRange(demon);
652 solver(),
this, &MinConstraint::MinVarChanged,
"MinVarChanged"));
656 void InitialPropagate()
override {
658 for (
int i = 0; i <
vars_.size(); ++i) {
659 InitLeaf(i,
vars_[i]->Min(),
vars_[i]->Max());
663 for (
int i = MaxDepth() - 1; i >= 0; --i) {
664 for (
int j = 0; j < Width(i); ++j) {
667 const int block_start = ChildStart(j);
668 const int block_end = ChildEnd(i, j);
669 for (
int k = block_start; k <= block_end; ++k) {
670 min_min =
std::min(min_min, Min(i + 1, k));
671 min_max =
std::min(min_max, Max(i + 1, k));
673 InitNode(i, j, min_min, min_max);
683 void MinVarChanged() {
687 void PushDown(
int depth,
int position,
int64 new_min,
int64 new_max) {
689 if (new_min <= Min(depth, position) && new_max >= Max(depth, position)) {
695 vars_[position]->SetRange(new_min, new_max);
704 const int block_start = ChildStart(position);
705 const int block_end = ChildEnd(depth, position);
709 for (
int i = block_start; i <= block_end; ++i) {
710 if (Min(depth + 1, i) <= new_max) {
723 for (
int i = block_start; i <= block_end; ++i) {
724 if (i == candidate && active == 1) {
725 PushDown(depth + 1, i, new_min, new_max);
727 PushDown(depth + 1, i, new_min, Max(depth + 1, i));
730 }
else if (active == 1) {
731 PushDown(depth + 1, candidate, Min(depth + 1, candidate), new_max);
736 void LeafChanged(
int term_index) {
737 IntVar*
const var =
vars_[term_index];
738 SetRange(MaxDepth(), term_index,
var->Min(),
var->Max());
739 const int parent_depth = MaxDepth() - 1;
740 const int parent = Parent(term_index);
741 const int64 old_min =
var->OldMin();
744 if ((old_min == Min(parent_depth, parent) && old_min != var_min) ||
745 var_max < Max(parent_depth, parent)) {
751 void PushUp(
int position) {
752 int depth = MaxDepth();
754 const int parent = Parent(position);
755 const int parent_depth = depth - 1;
758 const int block_start = ChildStart(parent);
759 const int block_end = ChildEnd(parent_depth, parent);
760 for (
int k = block_start; k <= block_end; ++k) {
761 min_min =
std::min(min_min, Min(depth, k));
762 min_max =
std::min(min_max, Max(depth, k));
764 if (min_min > Min(parent_depth, parent) ||
765 min_max < Max(parent_depth, parent)) {
766 SetRange(parent_depth, parent, min_min, min_max);
770 depth = parent_depth;
779 std::string DebugString()
const override {
780 return DebugStringInternal(
"Min");
783 void Accept(ModelVisitor*
const visitor)
const override {
791 class SmallMinConstraint :
public Constraint {
793 SmallMinConstraint(Solver*
const solver,
const std::vector<IntVar*>& vars,
794 IntVar*
const target_var)
795 : Constraint(solver),
801 ~SmallMinConstraint()
override {}
803 void Post()
override {
804 for (
int i = 0; i <
vars_.size(); ++i) {
805 if (!
vars_[i]->Bound()) {
807 solver(),
this, &SmallMinConstraint::VarChanged,
"VarChanged",
809 vars_[i]->WhenRange(demon);
813 solver(),
this, &SmallMinConstraint::MinVarChanged,
"MinVarChanged"));
817 void InitialPropagate()
override {
824 computed_min_.SetValue(solver(), min_min);
825 computed_max_.SetValue(solver(), min_max);
833 std::string DebugString()
const override {
834 return absl::StrFormat(
"SmallMin(%s) == %s",
839 void Accept(ModelVisitor*
const visitor)
const override {
849 void VarChanged(IntVar*
var) {
850 const int64 old_min =
var->OldMin();
853 if ((old_min == computed_min_.Value() && old_min != var_min) ||
854 var_max < computed_max_.Value()) {
862 if (min_min > computed_min_.Value() || min_max < computed_max_.Value()) {
863 computed_min_.SetValue(solver(), min_min);
864 computed_max_.SetValue(solver(), min_max);
865 target_var_->SetRange(computed_min_.Value(), computed_max_.Value());
871 void MinVarChanged() {
875 if (new_min <= computed_min_.Value() && new_max >= computed_max_.Value()) {
879 IntVar* candidate =
nullptr;
882 if (new_max < computed_max_.Value()) {
885 if (
var->Min() <= new_max) {
896 if (computed_min_.Value() < new_min) {
898 candidate->SetRange(new_min, new_max);
901 var->SetMin(new_min);
904 }
else if (active == 1) {
905 candidate->SetMax(new_max);
909 std::vector<IntVar*>
vars_;
911 Rev<int64> computed_min_;
912 Rev<int64> computed_max_;
918 class MaxConstraint :
public TreeArrayConstraint {
920 MaxConstraint(Solver*
const solver,
const std::vector<IntVar*>& vars,
921 IntVar*
const max_var)
922 : TreeArrayConstraint(solver, vars, max_var), max_demon_(nullptr) {}
924 ~MaxConstraint()
override {}
926 void Post()
override {
927 for (
int i = 0; i <
vars_.size(); ++i) {
929 solver(),
this, &MaxConstraint::LeafChanged,
"LeafChanged", i);
930 vars_[i]->WhenRange(demon);
933 solver(),
this, &MaxConstraint::MaxVarChanged,
"MaxVarChanged"));
937 void InitialPropagate()
override {
939 for (
int i = 0; i <
vars_.size(); ++i) {
940 InitLeaf(i,
vars_[i]->Min(),
vars_[i]->Max());
944 for (
int i = MaxDepth() - 1; i >= 0; --i) {
945 for (
int j = 0; j < Width(i); ++j) {
948 const int block_start = ChildStart(j);
949 const int block_end = ChildEnd(i, j);
950 for (
int k = block_start; k <= block_end; ++k) {
951 max_min =
std::max(max_min, Min(i + 1, k));
952 max_max =
std::max(max_max, Max(i + 1, k));
954 InitNode(i, j, max_min, max_max);
964 void MaxVarChanged() {
968 void PushDown(
int depth,
int position,
int64 new_min,
int64 new_max) {
970 if (new_min <= Min(depth, position) && new_max >= Max(depth, position)) {
976 vars_[position]->SetRange(new_min, new_max);
985 const int block_start = ChildStart(position);
986 const int block_end = ChildEnd(depth, position);
990 for (
int i = block_start; i <= block_end; ++i) {
991 if (Max(depth + 1, i) >= new_min) {
1004 for (
int i = block_start; i <= block_end; ++i) {
1005 if (i == candidate && active == 1) {
1006 PushDown(depth + 1, i, new_min, new_max);
1008 PushDown(depth + 1, i, Min(depth + 1, i), new_max);
1011 }
else if (active == 1) {
1012 PushDown(depth + 1, candidate, new_min, Max(depth + 1, candidate));
1016 void LeafChanged(
int term_index) {
1017 IntVar*
const var =
vars_[term_index];
1018 SetRange(MaxDepth(), term_index,
var->Min(),
var->Max());
1019 const int parent_depth = MaxDepth() - 1;
1020 const int parent = Parent(term_index);
1021 const int64 old_max =
var->OldMax();
1024 if ((old_max == Max(parent_depth, parent) && old_max != var_max) ||
1025 var_min > Min(parent_depth, parent)) {
1031 void PushUp(
int position) {
1032 int depth = MaxDepth();
1034 const int parent = Parent(position);
1035 const int parent_depth = depth - 1;
1038 const int block_start = ChildStart(parent);
1039 const int block_end = ChildEnd(parent_depth, parent);
1040 for (
int k = block_start; k <= block_end; ++k) {
1041 max_min =
std::max(max_min, Min(depth, k));
1042 max_max =
std::max(max_max, Max(depth, k));
1044 if (max_min > Min(parent_depth, parent) ||
1045 max_max < Max(parent_depth, parent)) {
1046 SetRange(parent_depth, parent, max_min, max_max);
1050 depth = parent_depth;
1059 std::string DebugString()
const override {
1060 return DebugStringInternal(
"Max");
1063 void Accept(ModelVisitor*
const visitor)
const override {
1071 class SmallMaxConstraint :
public Constraint {
1073 SmallMaxConstraint(Solver*
const solver,
const std::vector<IntVar*>& vars,
1074 IntVar*
const target_var)
1075 : Constraint(solver),
1081 ~SmallMaxConstraint()
override {}
1083 void Post()
override {
1084 for (
int i = 0; i <
vars_.size(); ++i) {
1085 if (!
vars_[i]->Bound()) {
1087 solver(),
this, &SmallMaxConstraint::VarChanged,
"VarChanged",
1089 vars_[i]->WhenRange(demon);
1093 solver(),
this, &SmallMaxConstraint::MaxVarChanged,
"MinVarChanged"));
1097 void InitialPropagate()
override {
1104 computed_min_.SetValue(solver(), max_min);
1105 computed_max_.SetValue(solver(), max_max);
1113 std::string DebugString()
const override {
1114 return absl::StrFormat(
"SmallMax(%s) == %s",
1119 void Accept(ModelVisitor*
const visitor)
const override {
1129 void VarChanged(IntVar*
var) {
1130 const int64 old_max =
var->OldMax();
1133 if ((old_max == computed_max_.Value() && old_max != var_max) ||
1134 var_min > computed_min_.Value()) {
1142 if (max_min > computed_min_.Value() || max_max < computed_max_.Value()) {
1143 computed_min_.SetValue(solver(), max_min);
1144 computed_max_.SetValue(solver(), max_max);
1145 target_var_->SetRange(computed_min_.Value(), computed_max_.Value());
1151 void MaxVarChanged() {
1155 if (new_min <= computed_min_.Value() && new_max >= computed_max_.Value()) {
1159 IntVar* candidate =
nullptr;
1162 if (new_min > computed_min_.Value()) {
1165 if (
var->Max() >= new_min) {
1166 if (active++ >= 1) {
1176 if (computed_max_.Value() > new_max) {
1178 candidate->SetRange(new_min, new_max);
1181 var->SetMax(new_max);
1184 }
else if (active == 1) {
1185 candidate->SetMin(new_min);
1189 std::vector<IntVar*>
vars_;
1191 Rev<int64> computed_min_;
1192 Rev<int64> computed_max_;
1197 class ArrayBoolAndEq :
public CastConstraint {
1199 ArrayBoolAndEq(Solver*
const s,
const std::vector<IntVar*>& vars,
1200 IntVar*
const target)
1201 : CastConstraint(s, target),
1203 demons_(vars.size()),
1206 ~ArrayBoolAndEq()
override {}
1208 void Post()
override {
1209 for (
int i = 0; i <
vars_.size(); ++i) {
1210 if (!
vars_[i]->Bound()) {
1213 "PropagateVar",
vars_[i]);
1214 vars_[i]->WhenBound(demons_[i]);
1219 solver(),
this, &ArrayBoolAndEq::PropagateTarget,
"PropagateTarget");
1224 void InitialPropagate()
override {
1227 for (
int i = 0; i <
vars_.size(); ++i) {
1228 vars_[i]->SetMin(1);
1231 int possible_zero = -1;
1234 for (
int i = 0; i <
vars_.size(); ++i) {
1235 if (!
vars_[i]->Bound()) {
1238 }
else if (
vars_[i]->Max() == 0) {
1247 if (unbounded == 0) {
1249 }
else if (
target_var_->Max() == 0 && unbounded == 1) {
1251 vars_[possible_zero]->SetMax(0);
1253 unbounded_.
SetValue(solver(), unbounded);
1258 void PropagateVar(IntVar*
var) {
1259 if (
var->Min() == 1) {
1260 unbounded_.
Decr(solver());
1261 if (unbounded_.
Value() == 0 && !decided_.Switched()) {
1263 decided_.Switch(solver());
1265 !decided_.Switched()) {
1274 void PropagateTarget() {
1276 for (
int i = 0; i <
vars_.size(); ++i) {
1277 vars_[i]->SetMin(1);
1280 if (unbounded_.
Value() == 1 && !decided_.Switched()) {
1286 std::string DebugString()
const override {
1291 void Accept(ModelVisitor*
const visitor)
const override {
1302 for (
int i = 0; i < demons_.size(); ++i) {
1303 if (demons_[i] !=
nullptr) {
1304 demons_[i]->inhibit(solver());
1309 void ForceToZero() {
1310 for (
int i = 0; i <
vars_.size(); ++i) {
1311 if (
vars_[i]->Min() == 0) {
1312 vars_[i]->SetValue(0);
1313 decided_.Switch(solver());
1320 const std::vector<IntVar*>
vars_;
1321 std::vector<Demon*> demons_;
1322 NumericalRev<int> unbounded_;
1326 class ArrayBoolOrEq :
public CastConstraint {
1328 ArrayBoolOrEq(Solver*
const s,
const std::vector<IntVar*>& vars,
1329 IntVar*
const target)
1330 : CastConstraint(s, target),
1332 demons_(vars.size()),
1335 ~ArrayBoolOrEq()
override {}
1337 void Post()
override {
1338 for (
int i = 0; i <
vars_.size(); ++i) {
1339 if (!
vars_[i]->Bound()) {
1342 "PropagateVar",
vars_[i]);
1343 vars_[i]->WhenBound(demons_[i]);
1348 solver(),
this, &ArrayBoolOrEq::PropagateTarget,
"PropagateTarget");
1353 void InitialPropagate()
override {
1356 for (
int i = 0; i <
vars_.size(); ++i) {
1357 vars_[i]->SetMax(0);
1361 int possible_one = -1;
1363 for (
int i = 0; i <
vars_.size(); ++i) {
1364 if (!
vars_[i]->Bound()) {
1367 }
else if (
vars_[i]->Min() == 1) {
1376 if (unbounded == 0) {
1378 }
else if (
target_var_->Min() == 1 && unbounded == 1) {
1380 vars_[possible_one]->SetMin(1);
1382 unbounded_.
SetValue(solver(), unbounded);
1387 void PropagateVar(IntVar*
var) {
1388 if (
var->Min() == 0) {
1389 unbounded_.
Decr(solver());
1390 if (unbounded_.
Value() == 0 && !decided_.Switched()) {
1392 decided_.Switch(solver());
1395 !decided_.Switched()) {
1404 void PropagateTarget() {
1406 for (
int i = 0; i <
vars_.size(); ++i) {
1407 vars_[i]->SetMax(0);
1410 if (unbounded_.
Value() == 1 && !decided_.Switched()) {
1416 std::string DebugString()
const override {
1421 void Accept(ModelVisitor*
const visitor)
const override {
1432 for (
int i = 0; i < demons_.size(); ++i) {
1433 if (demons_[i] !=
nullptr) {
1434 demons_[i]->inhibit(solver());
1440 for (
int i = 0; i <
vars_.size(); ++i) {
1441 if (
vars_[i]->Max() == 1) {
1442 vars_[i]->SetValue(1);
1443 decided_.Switch(solver());
1450 const std::vector<IntVar*>
vars_;
1451 std::vector<Demon*> demons_;
1452 NumericalRev<int> unbounded_;
1458 class BaseSumBooleanConstraint :
public Constraint {
1460 BaseSumBooleanConstraint(Solver*
const s,
const std::vector<IntVar*>& vars)
1461 : Constraint(s),
vars_(vars) {}
1463 ~BaseSumBooleanConstraint()
override {}
1466 std::string DebugStringInternal(
const std::string&
name)
const {
1470 const std::vector<IntVar*>
vars_;
1476 class SumBooleanLessOrEqualToOne :
public BaseSumBooleanConstraint {
1478 SumBooleanLessOrEqualToOne(Solver*
const s,
const std::vector<IntVar*>& vars)
1479 : BaseSumBooleanConstraint(s, vars) {}
1481 ~SumBooleanLessOrEqualToOne()
override {}
1483 void Post()
override {
1484 for (
int i = 0; i <
vars_.size(); ++i) {
1485 if (!
vars_[i]->Bound()) {
1487 &SumBooleanLessOrEqualToOne::Update,
1488 "Update",
vars_[i]);
1489 vars_[i]->WhenBound(u);
1494 void InitialPropagate()
override {
1495 for (
int i = 0; i <
vars_.size(); ++i) {
1496 if (
vars_[i]->Min() == 1) {
1497 PushAllToZeroExcept(
vars_[i]);
1503 void Update(IntVar*
var) {
1506 if (
var->Min() == 1) {
1507 PushAllToZeroExcept(
var);
1512 void PushAllToZeroExcept(IntVar*
var) {
1514 for (
int i = 0; i <
vars_.size(); ++i) {
1515 IntVar*
const other =
vars_[i];
1516 if (other !=
var && other->Max() != 0) {
1522 std::string DebugString()
const override {
1523 return DebugStringInternal(
"SumBooleanLessOrEqualToOne");
1526 void Accept(ModelVisitor*
const visitor)
const override {
1539 class SumBooleanGreaterOrEqualToOne :
public BaseSumBooleanConstraint {
1541 SumBooleanGreaterOrEqualToOne(Solver*
const s,
1542 const std::vector<IntVar*>& vars);
1543 ~SumBooleanGreaterOrEqualToOne()
override {}
1545 void Post()
override;
1546 void InitialPropagate()
override;
1548 void Update(
int index);
1551 std::string DebugString()
const override;
1553 void Accept(ModelVisitor*
const visitor)
const override {
1565 SumBooleanGreaterOrEqualToOne::SumBooleanGreaterOrEqualToOne(
1566 Solver*
const s,
const std::vector<IntVar*>& vars)
1567 : BaseSumBooleanConstraint(s, vars), bits_(vars.size()) {}
1569 void SumBooleanGreaterOrEqualToOne::Post() {
1570 for (
int i = 0; i <
vars_.size(); ++i) {
1572 solver(),
this, &SumBooleanGreaterOrEqualToOne::Update,
"Update", i);
1573 vars_[i]->WhenRange(d);
1577 void SumBooleanGreaterOrEqualToOne::InitialPropagate() {
1578 for (
int i = 0; i <
vars_.size(); ++i) {
1580 if (
var->Min() == 1LL) {
1584 if (
var->Max() == 1LL) {
1585 bits_.SetToOne(solver(), i);
1588 if (bits_.IsCardinalityZero()) {
1590 }
else if (bits_.IsCardinalityOne()) {
1591 vars_[bits_.GetFirstBit(0)]->SetValue(
int64{1});
1596 void SumBooleanGreaterOrEqualToOne::Update(
int index) {
1601 bits_.SetToZero(solver(),
index);
1602 if (bits_.IsCardinalityZero()) {
1604 }
else if (bits_.IsCardinalityOne()) {
1605 vars_[bits_.GetFirstBit(0)]->SetValue(
int64{1});
1612 std::string SumBooleanGreaterOrEqualToOne::DebugString()
const {
1613 return DebugStringInternal(
"SumBooleanGreaterOrEqualToOne");
1618 class SumBooleanEqualToOne :
public BaseSumBooleanConstraint {
1620 SumBooleanEqualToOne(Solver*
const s,
const std::vector<IntVar*>& vars)
1621 : BaseSumBooleanConstraint(s, vars), active_vars_(0) {}
1623 ~SumBooleanEqualToOne()
override {}
1625 void Post()
override {
1626 for (
int i = 0; i <
vars_.size(); ++i) {
1628 solver(),
this, &SumBooleanEqualToOne::Update,
"Update", i);
1629 vars_[i]->WhenBound(u);
1633 void InitialPropagate()
override {
1638 for (
int i = 0; i <
vars_.size(); ++i) {
1639 const IntVar*
const var =
vars_[i];
1640 if (
var->Min() == 1) {
1644 if (
var->Max() == 1) {
1649 if (min1 > 1 || max1 == 0) {
1651 }
else if (min1 == 1) {
1653 PushAllToZeroExcept(index_min);
1654 }
else if (max1 == 1) {
1656 vars_[index_max]->SetValue(1);
1659 active_vars_.
SetValue(solver(), max1);
1663 void Update(
int index) {
1668 active_vars_.
Decr(solver());
1670 if (active_vars_.
Value() == 0) {
1672 }
else if (active_vars_.
Value() == 1) {
1674 for (
int i = 0; i <
vars_.size(); ++i) {
1676 if (
var->Max() == 1) {
1678 PushAllToZeroExcept(i);
1688 PushAllToZeroExcept(
index);
1693 void PushAllToZeroExcept(
int index) {
1695 for (
int i = 0; i <
vars_.size(); ++i) {
1697 vars_[i]->SetMax(0);
1702 std::string DebugString()
const override {
1703 return DebugStringInternal(
"SumBooleanEqualToOne");
1706 void Accept(ModelVisitor*
const visitor)
const override {
1707 visitor->BeginVisitConstraint(ModelVisitor::kSumEqual,
this);
1708 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
1710 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, 1);
1711 visitor->EndVisitConstraint(ModelVisitor::kSumEqual,
this);
1715 NumericalRev<int> active_vars_;
1720 class SumBooleanEqualToVar :
public BaseSumBooleanConstraint {
1722 SumBooleanEqualToVar(Solver*
const s,
const std::vector<IntVar*>& bool_vars,
1723 IntVar*
const sum_var)
1724 : BaseSumBooleanConstraint(s, bool_vars),
1725 num_possible_true_vars_(0),
1726 num_always_true_vars_(0),
1727 sum_var_(sum_var) {}
1729 ~SumBooleanEqualToVar()
override {}
1731 void Post()
override {
1732 for (
int i = 0; i <
vars_.size(); ++i) {
1734 solver(),
this, &SumBooleanEqualToVar::Update,
"Update", i);
1735 vars_[i]->WhenBound(u);
1737 if (!sum_var_->Bound()) {
1739 solver(),
this, &SumBooleanEqualToVar::UpdateVar,
"UpdateVar");
1740 sum_var_->WhenRange(u);
1744 void InitialPropagate()
override {
1745 int num_always_true_vars = 0;
1746 int possible_true = 0;
1747 for (
int i = 0; i <
vars_.size(); ++i) {
1748 const IntVar*
const var =
vars_[i];
1749 if (
var->Min() == 1) {
1750 num_always_true_vars++;
1752 if (
var->Max() == 1) {
1756 sum_var_->SetRange(num_always_true_vars, possible_true);
1757 const int64 var_min = sum_var_->Min();
1758 const int64 var_max = sum_var_->Max();
1759 if (num_always_true_vars == var_max && possible_true > var_max) {
1760 PushAllUnboundToZero();
1761 }
else if (possible_true == var_min && num_always_true_vars < var_min) {
1762 PushAllUnboundToOne();
1764 num_possible_true_vars_.
SetValue(solver(), possible_true);
1765 num_always_true_vars_.
SetValue(solver(), num_always_true_vars);
1771 if (num_possible_true_vars_.
Value() == sum_var_->Min()) {
1772 PushAllUnboundToOne();
1773 sum_var_->SetValue(num_possible_true_vars_.
Value());
1774 }
else if (num_always_true_vars_.
Value() == sum_var_->Max()) {
1775 PushAllUnboundToZero();
1776 sum_var_->SetValue(num_always_true_vars_.
Value());
1781 void Update(
int index) {
1786 num_possible_true_vars_.
Decr(solver());
1787 sum_var_->SetRange(num_always_true_vars_.
Value(),
1788 num_possible_true_vars_.
Value());
1789 if (num_possible_true_vars_.
Value() == sum_var_->Min()) {
1790 PushAllUnboundToOne();
1794 num_always_true_vars_.
Incr(solver());
1795 sum_var_->SetRange(num_always_true_vars_.
Value(),
1796 num_possible_true_vars_.
Value());
1797 if (num_always_true_vars_.
Value() == sum_var_->Max()) {
1798 PushAllUnboundToZero();
1804 void PushAllUnboundToZero() {
1807 for (
int i = 0; i <
vars_.size(); ++i) {
1808 if (
vars_[i]->Min() == 0) {
1809 vars_[i]->SetValue(0);
1814 if (counter < sum_var_->Min() || counter > sum_var_->Max()) {
1819 void PushAllUnboundToOne() {
1822 for (
int i = 0; i <
vars_.size(); ++i) {
1823 if (
vars_[i]->Max() == 1) {
1824 vars_[i]->SetValue(1);
1828 if (counter < sum_var_->Min() || counter > sum_var_->Max()) {
1833 std::string DebugString()
const override {
1834 return absl::StrFormat(
"%s == %s", DebugStringInternal(
"SumBoolean"),
1835 sum_var_->DebugString());
1838 void Accept(ModelVisitor*
const visitor)
const override {
1839 visitor->BeginVisitConstraint(ModelVisitor::kSumEqual,
this);
1840 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
1842 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
1844 visitor->EndVisitConstraint(ModelVisitor::kSumEqual,
this);
1848 NumericalRev<int> num_possible_true_vars_;
1849 NumericalRev<int> num_always_true_vars_;
1850 IntVar*
const sum_var_;
1861 bool operator<(
const Container& c)
const {
return (
coef < c.coef); }
1871 int64 SortBothChangeConstant(std::vector<IntVar*>*
const vars,
1872 std::vector<int64>*
const coefs,
1874 CHECK(vars !=
nullptr);
1875 CHECK(coefs !=
nullptr);
1876 if (vars->empty()) {
1880 std::vector<Container> to_sort;
1882 if ((*vars)[
index]->Bound()) {
1884 }
else if ((*coefs)[
index] != 0) {
1885 to_sort.push_back(Container((*vars)[
index], (*coefs)[
index]));
1888 if (keep_inside && cst != 0) {
1889 CHECK_LT(to_sort.size(), vars->size());
1890 Solver*
const solver = (*vars)[0]->solver();
1891 to_sort.push_back(Container(solver->MakeIntConst(1), cst));
1894 std::sort(to_sort.begin(), to_sort.end());
1899 vars->resize(to_sort.size());
1900 coefs->resize(to_sort.size());
1906 class BooleanScalProdLessConstant :
public Constraint {
1908 BooleanScalProdLessConstant(Solver*
const s,
const std::vector<IntVar*>& vars,
1909 const std::vector<int64>& coefs,
1914 upper_bound_(upper_bound),
1915 first_unbound_backward_(vars.size() - 1),
1916 sum_of_bound_variables_(0LL),
1917 max_coefficient_(0) {
1918 CHECK(!vars.empty());
1919 for (
int i = 0; i <
vars_.size(); ++i) {
1923 CapSub(upper_bound, SortBothChangeConstant(&
vars_, &coefs_,
false));
1924 max_coefficient_.SetValue(s, coefs_[
vars_.size() - 1]);
1927 ~BooleanScalProdLessConstant()
override {}
1929 void Post()
override {
1930 for (
int var_index = 0; var_index <
vars_.size(); ++var_index) {
1931 if (
vars_[var_index]->Bound()) {
1935 &BooleanScalProdLessConstant::Update,
1936 "InitialPropagate", var_index);
1937 vars_[var_index]->WhenRange(d);
1941 void PushFromTop() {
1942 const int64 slack =
CapSub(upper_bound_, sum_of_bound_variables_.Value());
1946 if (slack < max_coefficient_.Value()) {
1947 int64 last_unbound = first_unbound_backward_.
Value();
1948 for (; last_unbound >= 0; --last_unbound) {
1949 if (!
vars_[last_unbound]->Bound()) {
1950 if (coefs_[last_unbound] <= slack) {
1951 max_coefficient_.SetValue(solver(), coefs_[last_unbound]);
1954 vars_[last_unbound]->SetValue(0);
1958 first_unbound_backward_.
SetValue(solver(), last_unbound);
1962 void InitialPropagate()
override {
1963 Solver*
const s = solver();
1964 int last_unbound = -1;
1971 last_unbound =
index;
1974 sum_of_bound_variables_.SetValue(s, sum);
1975 first_unbound_backward_.
SetValue(s, last_unbound);
1979 void Update(
int var_index) {
1980 if (
vars_[var_index]->Min() == 1) {
1981 sum_of_bound_variables_.SetValue(
1982 solver(),
CapAdd(sum_of_bound_variables_.Value(), coefs_[var_index]));
1987 std::string DebugString()
const override {
1988 return absl::StrFormat(
"BooleanScalProd([%s], [%s]) <= %d)",
1990 absl::StrJoin(coefs_,
", "), upper_bound_);
1993 void Accept(ModelVisitor*
const visitor)
const override {
1994 visitor->BeginVisitConstraint(ModelVisitor::kScalProdLessOrEqual,
this);
1995 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
1997 visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
1999 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, upper_bound_);
2000 visitor->EndVisitConstraint(ModelVisitor::kScalProdLessOrEqual,
this);
2004 std::vector<IntVar*>
vars_;
2005 std::vector<int64> coefs_;
2007 Rev<int> first_unbound_backward_;
2008 Rev<int64> sum_of_bound_variables_;
2009 Rev<int64> max_coefficient_;
2014 class PositiveBooleanScalProdEqVar :
public CastConstraint {
2016 PositiveBooleanScalProdEqVar(Solver*
const s,
2017 const std::vector<IntVar*>& vars,
2018 const std::vector<int64>& coefs,
2020 : CastConstraint(s,
var),
2023 first_unbound_backward_(vars.size() - 1),
2024 sum_of_bound_variables_(0LL),
2025 sum_of_all_variables_(0LL),
2026 max_coefficient_(0) {
2027 SortBothChangeConstant(&
vars_, &coefs_,
true);
2028 max_coefficient_.SetValue(s, coefs_[
vars_.size() - 1]);
2031 ~PositiveBooleanScalProdEqVar()
override {}
2033 void Post()
override {
2034 for (
int var_index = 0; var_index <
vars_.size(); ++var_index) {
2035 if (
vars_[var_index]->Bound()) {
2039 solver(),
this, &PositiveBooleanScalProdEqVar::Update,
"Update",
2041 vars_[var_index]->WhenRange(d);
2045 solver(),
this, &PositiveBooleanScalProdEqVar::Propagate,
2052 target_var_->SetRange(sum_of_bound_variables_.Value(),
2053 sum_of_all_variables_.Value());
2054 const int64 slack_up =
2056 const int64 slack_down =
2058 const int64 max_coeff = max_coefficient_.Value();
2059 if (slack_down < max_coeff || slack_up < max_coeff) {
2060 int64 last_unbound = first_unbound_backward_.
Value();
2061 for (; last_unbound >= 0; --last_unbound) {
2062 if (!
vars_[last_unbound]->Bound()) {
2063 if (coefs_[last_unbound] > slack_up) {
2064 vars_[last_unbound]->SetValue(0);
2065 }
else if (coefs_[last_unbound] > slack_down) {
2066 vars_[last_unbound]->SetValue(1);
2068 max_coefficient_.SetValue(solver(), coefs_[last_unbound]);
2073 first_unbound_backward_.
SetValue(solver(), last_unbound);
2077 void InitialPropagate()
override {
2078 Solver*
const s = solver();
2079 int last_unbound = -1;
2080 int64 sum_bound = 0;
2088 last_unbound =
index;
2091 sum_of_bound_variables_.SetValue(s, sum_bound);
2092 sum_of_all_variables_.SetValue(s, sum_all);
2093 first_unbound_backward_.
SetValue(s, last_unbound);
2097 void Update(
int var_index) {
2098 if (
vars_[var_index]->Min() == 1) {
2099 sum_of_bound_variables_.SetValue(
2100 solver(),
CapAdd(sum_of_bound_variables_.Value(), coefs_[var_index]));
2102 sum_of_all_variables_.SetValue(
2103 solver(),
CapSub(sum_of_all_variables_.Value(), coefs_[var_index]));
2108 std::string DebugString()
const override {
2109 return absl::StrFormat(
"PositiveBooleanScal([%s], [%s]) == %s",
2111 absl::StrJoin(coefs_,
", "),
2115 void Accept(ModelVisitor*
const visitor)
const override {
2116 visitor->BeginVisitConstraint(ModelVisitor::kScalProdEqual,
this);
2117 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
2119 visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
2121 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
2123 visitor->EndVisitConstraint(ModelVisitor::kScalProdEqual,
this);
2127 std::vector<IntVar*>
vars_;
2128 std::vector<int64> coefs_;
2129 Rev<int> first_unbound_backward_;
2130 Rev<int64> sum_of_bound_variables_;
2131 Rev<int64> sum_of_all_variables_;
2132 Rev<int64> max_coefficient_;
2137 class PositiveBooleanScalProd :
public BaseIntExpr {
2141 PositiveBooleanScalProd(Solver*
const s,
const std::vector<IntVar*>& vars,
2142 const std::vector<int64>& coefs)
2143 : BaseIntExpr(s),
vars_(vars), coefs_(coefs) {
2144 CHECK(!vars.empty());
2145 SortBothChangeConstant(&
vars_, &coefs_,
true);
2146 for (
int i = 0; i <
vars_.size(); ++i) {
2151 ~PositiveBooleanScalProd()
override {}
2153 int64 Min()
const override {
2155 for (
int i = 0; i <
vars_.size(); ++i) {
2156 if (
vars_[i]->Min()) {
2165 int64 Max()
const override {
2167 for (
int i = 0; i <
vars_.size(); ++i) {
2168 if (
vars_[i]->Max()) {
2178 int64 current_min = 0;
2179 int64 current_max = 0;
2180 int64 diameter = -1;
2181 for (
int i = 0; i <
vars_.size(); ++i) {
2185 current_min =
CapAdd(current_min, var_min);
2186 current_max =
CapAdd(current_max, var_max);
2187 if (var_min != var_max) {
2188 diameter =
CapSub(var_max, var_min);
2191 if (u >= current_max && l <= current_min) {
2194 if (u < current_min || l > current_max) {
2201 if (
CapSub(u, l) > diameter) {
2205 for (
int i = 0; i <
vars_.size(); ++i) {
2208 const int64 new_min =
2210 const int64 new_max =
2212 if (new_max < 0 || new_min >
coefficient || new_min > new_max) {
2215 if (new_min > 0LL) {
2223 std::string DebugString()
const override {
2224 return absl::StrFormat(
"PositiveBooleanScalProd([%s], [%s])",
2226 absl::StrJoin(coefs_,
", "));
2229 void WhenRange(Demon* d)
override {
2230 for (
int i = 0; i <
vars_.size(); ++i) {
2231 vars_[i]->WhenRange(d);
2234 IntVar* CastToVar()
override {
2235 Solver*
const s = solver();
2238 Range(&vmin, &vmax);
2239 IntVar*
const var = solver()->MakeIntVar(vmin, vmax);
2240 if (!
vars_.empty()) {
2241 CastConstraint*
const ct =
2242 s->RevAlloc(
new PositiveBooleanScalProdEqVar(s,
vars_, coefs_,
var));
2243 s->AddCastConstraint(
ct,
var,
this);
2248 void Accept(ModelVisitor*
const visitor)
const override {
2249 visitor->BeginVisitIntegerExpression(ModelVisitor::kScalProd,
this);
2250 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
2252 visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
2254 visitor->EndVisitIntegerExpression(ModelVisitor::kScalProd,
this);
2258 std::vector<IntVar*>
vars_;
2259 std::vector<int64> coefs_;
2264 class PositiveBooleanScalProdEqCst :
public Constraint {
2266 PositiveBooleanScalProdEqCst(Solver*
const s,
2267 const std::vector<IntVar*>& vars,
2268 const std::vector<int64>& coefs,
int64 constant)
2272 first_unbound_backward_(vars.size() - 1),
2273 sum_of_bound_variables_(0LL),
2274 sum_of_all_variables_(0LL),
2275 constant_(constant),
2276 max_coefficient_(0) {
2277 CHECK(!vars.empty());
2279 CapSub(constant_, SortBothChangeConstant(&
vars_, &coefs_,
false));
2280 max_coefficient_.SetValue(s, coefs_[
vars_.size() - 1]);
2283 ~PositiveBooleanScalProdEqCst()
override {}
2285 void Post()
override {
2286 for (
int var_index = 0; var_index <
vars_.size(); ++var_index) {
2287 if (!
vars_[var_index]->Bound()) {
2289 solver(),
this, &PositiveBooleanScalProdEqCst::Update,
"Update",
2291 vars_[var_index]->WhenRange(d);
2297 if (sum_of_bound_variables_.Value() > constant_ ||
2298 sum_of_all_variables_.Value() < constant_) {
2301 const int64 slack_up =
CapSub(constant_, sum_of_bound_variables_.Value());
2302 const int64 slack_down =
CapSub(sum_of_all_variables_.Value(), constant_);
2303 const int64 max_coeff = max_coefficient_.Value();
2304 if (slack_down < max_coeff || slack_up < max_coeff) {
2305 int64 last_unbound = first_unbound_backward_.
Value();
2306 for (; last_unbound >= 0; --last_unbound) {
2307 if (!
vars_[last_unbound]->Bound()) {
2308 if (coefs_[last_unbound] > slack_up) {
2309 vars_[last_unbound]->SetValue(0);
2310 }
else if (coefs_[last_unbound] > slack_down) {
2311 vars_[last_unbound]->SetValue(1);
2313 max_coefficient_.SetValue(solver(), coefs_[last_unbound]);
2318 first_unbound_backward_.
SetValue(solver(), last_unbound);
2322 void InitialPropagate()
override {
2323 Solver*
const s = solver();
2324 int last_unbound = -1;
2325 int64 sum_bound = 0LL;
2326 int64 sum_all = 0LL;
2333 last_unbound =
index;
2336 sum_of_bound_variables_.SetValue(s, sum_bound);
2337 sum_of_all_variables_.SetValue(s, sum_all);
2338 first_unbound_backward_.
SetValue(s, last_unbound);
2342 void Update(
int var_index) {
2343 if (
vars_[var_index]->Min() == 1) {
2344 sum_of_bound_variables_.SetValue(
2345 solver(),
CapAdd(sum_of_bound_variables_.Value(), coefs_[var_index]));
2347 sum_of_all_variables_.SetValue(
2348 solver(),
CapSub(sum_of_all_variables_.Value(), coefs_[var_index]));
2353 std::string DebugString()
const override {
2354 return absl::StrFormat(
"PositiveBooleanScalProd([%s], [%s]) == %d",
2356 absl::StrJoin(coefs_,
", "), constant_);
2359 void Accept(ModelVisitor*
const visitor)
const override {
2360 visitor->BeginVisitConstraint(ModelVisitor::kScalProdEqual,
this);
2361 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
2363 visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
2365 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, constant_);
2366 visitor->EndVisitConstraint(ModelVisitor::kScalProdEqual,
this);
2370 std::vector<IntVar*>
vars_;
2371 std::vector<int64> coefs_;
2372 Rev<int> first_unbound_backward_;
2373 Rev<int64> sum_of_bound_variables_;
2374 Rev<int64> sum_of_all_variables_;
2376 Rev<int64> max_coefficient_;
2381 #define IS_TYPE(type, tag) type.compare(ModelVisitor::tag) == 0
2383 class ExprLinearizer :
public ModelParser {
2385 explicit ExprLinearizer(
2386 absl::flat_hash_map<IntVar*, int64>*
const variables_to_coefficients)
2387 : variables_to_coefficients_(variables_to_coefficients), constant_(0) {}
2389 ~ExprLinearizer()
override {}
2392 void BeginVisitModel(
const std::string& solver_name)
override {
2393 LOG(
FATAL) <<
"Should not be here";
2396 void EndVisitModel(
const std::string& solver_name)
override {
2397 LOG(
FATAL) <<
"Should not be here";
2400 void BeginVisitConstraint(
const std::string& type_name,
2401 const Constraint*
const constraint)
override {
2402 LOG(
FATAL) <<
"Should not be here";
2405 void EndVisitConstraint(
const std::string& type_name,
2406 const Constraint*
const constraint)
override {
2407 LOG(
FATAL) <<
"Should not be here";
2410 void BeginVisitExtension(
const std::string& type)
override {}
2412 void EndVisitExtension(
const std::string& type)
override {}
2413 void BeginVisitIntegerExpression(
const std::string& type_name,
2414 const IntExpr*
const expr)
override {
2418 void EndVisitIntegerExpression(
const std::string& type_name,
2419 const IntExpr*
const expr)
override {
2420 if (
IS_TYPE(type_name, kSum)) {
2422 }
else if (
IS_TYPE(type_name, kScalProd)) {
2423 VisitScalProd(expr);
2424 }
else if (
IS_TYPE(type_name, kDifference)) {
2425 VisitDifference(expr);
2426 }
else if (
IS_TYPE(type_name, kOpposite)) {
2427 VisitOpposite(expr);
2428 }
else if (
IS_TYPE(type_name, kProduct)) {
2430 }
else if (
IS_TYPE(type_name, kTrace)) {
2433 VisitIntegerExpression(expr);
2438 void VisitIntegerVariable(
const IntVar*
const variable,
2440 IntVar*
const delegate)
override {
2441 if (operation == ModelVisitor::kSumOperation) {
2443 VisitSubExpression(delegate);
2444 }
else if (operation == ModelVisitor::kDifferenceOperation) {
2447 VisitSubExpression(delegate);
2449 }
else if (operation == ModelVisitor::kProductOperation) {
2450 PushMultiplier(
value);
2451 VisitSubExpression(delegate);
2453 }
else if (operation == ModelVisitor::kTraceOperation) {
2454 VisitSubExpression(delegate);
2458 void VisitIntegerVariable(
const IntVar*
const variable,
2459 IntExpr*
const delegate)
override {
2460 if (delegate !=
nullptr) {
2461 VisitSubExpression(delegate);
2463 if (variable->Bound()) {
2464 AddConstant(variable->Min());
2466 RegisterExpression(variable, 1);
2472 void VisitIntegerArgument(
const std::string& arg_name,
int64 value)
override {
2473 Top()->SetIntegerArgument(arg_name,
value);
2476 void VisitIntegerArrayArgument(
const std::string& arg_name,
2477 const std::vector<int64>& values)
override {
2478 Top()->SetIntegerArrayArgument(arg_name, values);
2481 void VisitIntegerMatrixArgument(
const std::string& arg_name,
2482 const IntTupleSet& values)
override {
2483 Top()->SetIntegerMatrixArgument(arg_name, values);
2487 void VisitIntegerExpressionArgument(
const std::string& arg_name,
2488 IntExpr*
const argument)
override {
2489 Top()->SetIntegerExpressionArgument(arg_name, argument);
2492 void VisitIntegerVariableArrayArgument(
2493 const std::string& arg_name,
2494 const std::vector<IntVar*>& arguments)
override {
2495 Top()->SetIntegerVariableArrayArgument(arg_name, arguments);
2499 void VisitIntervalArgument(
const std::string& arg_name,
2500 IntervalVar*
const argument)
override {}
2502 void VisitIntervalArrayArgument(
2503 const std::string& arg_name,
2504 const std::vector<IntervalVar*>& argument)
override {}
2506 void Visit(
const IntExpr*
const expr,
int64 multiplier) {
2507 if (expr->Min() == expr->Max()) {
2508 constant_ =
CapAdd(constant_,
CapProd(expr->Min(), multiplier));
2510 PushMultiplier(multiplier);
2516 int64 Constant()
const {
return constant_; }
2518 std::string DebugString()
const override {
return "ExprLinearizer"; }
2521 void BeginVisit(
bool active) { PushArgumentHolder(); }
2523 void EndVisit() { PopArgumentHolder(); }
2525 void VisitSubExpression(
const IntExpr*
const cp_expr) {
2526 cp_expr->Accept(
this);
2529 void VisitSum(
const IntExpr*
const cp_expr) {
2530 if (Top()->HasIntegerVariableArrayArgument(ModelVisitor::kVarsArgument)) {
2531 const std::vector<IntVar*>& cp_vars =
2532 Top()->FindIntegerVariableArrayArgumentOrDie(
2533 ModelVisitor::kVarsArgument);
2534 for (
int i = 0; i < cp_vars.size(); ++i) {
2535 VisitSubExpression(cp_vars[i]);
2537 }
else if (Top()->HasIntegerExpressionArgument(
2538 ModelVisitor::kLeftArgument)) {
2539 const IntExpr*
const left = Top()->FindIntegerExpressionArgumentOrDie(
2540 ModelVisitor::kLeftArgument);
2541 const IntExpr*
const right = Top()->FindIntegerExpressionArgumentOrDie(
2542 ModelVisitor::kRightArgument);
2543 VisitSubExpression(left);
2544 VisitSubExpression(right);
2546 const IntExpr*
const expr = Top()->FindIntegerExpressionArgumentOrDie(
2547 ModelVisitor::kExpressionArgument);
2549 Top()->FindIntegerArgumentOrDie(ModelVisitor::kValueArgument);
2550 VisitSubExpression(expr);
2555 void VisitScalProd(
const IntExpr*
const cp_expr) {
2556 const std::vector<IntVar*>& cp_vars =
2557 Top()->FindIntegerVariableArrayArgumentOrDie(
2558 ModelVisitor::kVarsArgument);
2559 const std::vector<int64>& cp_coefficients =
2560 Top()->FindIntegerArrayArgumentOrDie(
2561 ModelVisitor::kCoefficientsArgument);
2562 CHECK_EQ(cp_vars.size(), cp_coefficients.size());
2563 for (
int i = 0; i < cp_vars.size(); ++i) {
2566 VisitSubExpression(cp_vars[i]);
2571 void VisitDifference(
const IntExpr*
const cp_expr) {
2572 if (Top()->HasIntegerExpressionArgument(ModelVisitor::kLeftArgument)) {
2573 const IntExpr*
const left = Top()->FindIntegerExpressionArgumentOrDie(
2574 ModelVisitor::kLeftArgument);
2575 const IntExpr*
const right = Top()->FindIntegerExpressionArgumentOrDie(
2576 ModelVisitor::kRightArgument);
2577 VisitSubExpression(left);
2579 VisitSubExpression(right);
2582 const IntExpr*
const expr = Top()->FindIntegerExpressionArgumentOrDie(
2583 ModelVisitor::kExpressionArgument);
2585 Top()->FindIntegerArgumentOrDie(ModelVisitor::kValueArgument);
2588 VisitSubExpression(expr);
2593 void VisitOpposite(
const IntExpr*
const cp_expr) {
2594 const IntExpr*
const expr = Top()->FindIntegerExpressionArgumentOrDie(
2595 ModelVisitor::kExpressionArgument);
2597 VisitSubExpression(expr);
2601 void VisitProduct(
const IntExpr*
const cp_expr) {
2602 if (Top()->HasIntegerExpressionArgument(
2603 ModelVisitor::kExpressionArgument)) {
2604 const IntExpr*
const expr = Top()->FindIntegerExpressionArgumentOrDie(
2605 ModelVisitor::kExpressionArgument);
2607 Top()->FindIntegerArgumentOrDie(ModelVisitor::kValueArgument);
2608 PushMultiplier(
value);
2609 VisitSubExpression(expr);
2612 RegisterExpression(cp_expr, 1);
2616 void VisitTrace(
const IntExpr*
const cp_expr) {
2617 const IntExpr*
const expr = Top()->FindIntegerExpressionArgumentOrDie(
2618 ModelVisitor::kExpressionArgument);
2619 VisitSubExpression(expr);
2622 void VisitIntegerExpression(
const IntExpr*
const cp_expr) {
2623 RegisterExpression(cp_expr, 1);
2626 void RegisterExpression(
const IntExpr*
const expr,
int64 coef) {
2628 (*variables_to_coefficients_)[
const_cast<IntExpr*
>(expr)->Var()];
2632 void AddConstant(
int64 constant) {
2633 constant_ =
CapAdd(constant_,
CapProd(constant, multipliers_.back()));
2636 void PushMultiplier(
int64 multiplier) {
2637 if (multipliers_.empty()) {
2638 multipliers_.push_back(multiplier);
2640 multipliers_.push_back(
CapProd(multiplier, multipliers_.back()));
2644 void PopMultiplier() { multipliers_.pop_back(); }
2648 absl::flat_hash_map<IntVar*, int64>*
const variables_to_coefficients_;
2649 std::vector<int64> multipliers_;
2656 void DeepLinearize(Solver*
const solver,
const std::vector<IntVar*>& pre_vars,
2657 const std::vector<int64>& pre_coefs,
2658 std::vector<IntVar*>* vars, std::vector<int64>* coefs,
2660 CHECK(solver !=
nullptr);
2661 CHECK(vars !=
nullptr);
2662 CHECK(coefs !=
nullptr);
2663 CHECK(constant !=
nullptr);
2665 vars->reserve(pre_vars.size());
2666 coefs->reserve(pre_coefs.size());
2668 bool need_linearization =
false;
2669 for (
int i = 0; i < pre_vars.size(); ++i) {
2670 IntVar*
const variable = pre_vars[i];
2672 if (variable->Bound()) {
2674 }
else if (solver->CastExpression(variable) ==
nullptr) {
2675 vars->push_back(variable);
2678 need_linearization =
true;
2684 if (need_linearization) {
2686 absl::flat_hash_map<IntVar*, int64> variables_to_coefficients;
2687 ExprLinearizer linearizer(&variables_to_coefficients);
2688 for (
int i = 0; i < pre_vars.size(); ++i) {
2689 linearizer.Visit(pre_vars[i], pre_coefs[i]);
2691 *constant = linearizer.Constant();
2692 for (
const auto& variable_to_coefficient : variables_to_coefficients) {
2693 if (variable_to_coefficient.second != 0) {
2694 vars->push_back(variable_to_coefficient.first);
2695 coefs->push_back(variable_to_coefficient.second);
2701 Constraint* MakeScalProdEqualityFct(Solver*
const solver,
2702 const std::vector<IntVar*>& pre_vars,
2703 const std::vector<int64>& pre_coefs,
2706 std::vector<IntVar*> vars;
2707 std::vector<int64> coefs;
2708 DeepLinearize(solver, pre_vars, pre_coefs, &vars, &coefs, &constant);
2709 cst =
CapSub(cst, constant);
2711 const int size = vars.size();
2713 return cst == 0 ? solver->MakeTrueConstraint()
2714 : solver->MakeFalseConstraint();
2718 for (
int i = 0; i < size; ++i) {
2721 return sum == cst ? solver->MakeTrueConstraint()
2722 : solver->MakeFalseConstraint();
2725 return solver->MakeSumEquality(vars, cst);
2729 return solver->RevAlloc(
2730 new PositiveBooleanScalProdEqCst(solver, vars, coefs, cst));
2733 std::vector<int64> opp_coefs(coefs.size());
2734 for (
int i = 0; i < coefs.size(); ++i) {
2735 opp_coefs[i] = -coefs[i];
2737 return solver->RevAlloc(
2738 new PositiveBooleanScalProdEqCst(solver, vars, opp_coefs, -cst));
2746 for (
int i = 0; i < size; ++i) {
2747 if (coefs[i] == 0 || vars[i]->Bound()) {
2749 }
else if (coefs[i] > 0) {
2755 if (positives > 0 && negatives > 0) {
2756 std::vector<IntVar*> pos_terms;
2757 std::vector<IntVar*> neg_terms;
2759 for (
int i = 0; i < size; ++i) {
2760 if (coefs[i] == 0 || vars[i]->Bound()) {
2762 }
else if (coefs[i] > 0) {
2763 pos_terms.push_back(solver->MakeProd(vars[i], coefs[i])->Var());
2765 neg_terms.push_back(solver->MakeProd(vars[i], -coefs[i])->Var());
2768 if (negatives == 1) {
2770 pos_terms.push_back(solver->MakeIntConst(-rhs));
2772 return solver->MakeSumEquality(pos_terms, neg_terms[0]);
2773 }
else if (positives == 1) {
2775 neg_terms.push_back(solver->MakeIntConst(rhs));
2777 return solver->MakeSumEquality(neg_terms, pos_terms[0]);
2780 neg_terms.push_back(solver->MakeIntConst(rhs));
2782 return solver->MakeEquality(solver->MakeSum(pos_terms),
2783 solver->MakeSum(neg_terms));
2785 }
else if (positives == 1) {
2786 IntExpr* pos_term =
nullptr;
2788 for (
int i = 0; i < size; ++i) {
2789 if (coefs[i] == 0 || vars[i]->Bound()) {
2791 }
else if (coefs[i] > 0) {
2792 pos_term = solver->MakeProd(vars[i], coefs[i]);
2794 LOG(
FATAL) <<
"Should not be here";
2797 return solver->MakeEquality(pos_term, rhs);
2798 }
else if (negatives == 1) {
2799 IntExpr* neg_term =
nullptr;
2801 for (
int i = 0; i < size; ++i) {
2802 if (coefs[i] == 0 || vars[i]->Bound()) {
2804 }
else if (coefs[i] > 0) {
2805 LOG(
FATAL) <<
"Should not be here";
2807 neg_term = solver->MakeProd(vars[i], -coefs[i]);
2810 return solver->MakeEquality(neg_term, -rhs);
2811 }
else if (positives > 1) {
2812 std::vector<IntVar*> pos_terms;
2814 for (
int i = 0; i < size; ++i) {
2815 if (coefs[i] == 0 || vars[i]->Bound()) {
2817 }
else if (coefs[i] > 0) {
2818 pos_terms.push_back(solver->MakeProd(vars[i], coefs[i])->Var());
2820 LOG(
FATAL) <<
"Should not be here";
2823 return solver->MakeSumEquality(pos_terms, rhs);
2824 }
else if (negatives > 1) {
2825 std::vector<IntVar*> neg_terms;
2827 for (
int i = 0; i < size; ++i) {
2828 if (coefs[i] == 0 || vars[i]->Bound()) {
2830 }
else if (coefs[i] > 0) {
2831 LOG(
FATAL) <<
"Should not be here";
2833 neg_terms.push_back(solver->MakeProd(vars[i], -coefs[i])->Var());
2836 return solver->MakeSumEquality(neg_terms, -rhs);
2838 std::vector<IntVar*> terms;
2839 for (
int i = 0; i < size; ++i) {
2840 terms.push_back(solver->MakeProd(vars[i], coefs[i])->Var());
2842 return solver->MakeSumEquality(terms, solver->MakeIntConst(cst));
2845 Constraint* MakeScalProdEqualityVarFct(Solver*
const solver,
2846 const std::vector<IntVar*>& pre_vars,
2847 const std::vector<int64>& pre_coefs,
2848 IntVar*
const target) {
2850 std::vector<IntVar*> vars;
2851 std::vector<int64> coefs;
2852 DeepLinearize(solver, pre_vars, pre_coefs, &vars, &coefs, &constant);
2854 const int size = vars.size();
2855 if (size == 0 || AreAllNull<int64>(coefs)) {
2856 return solver->MakeEquality(target, constant);
2859 return solver->MakeSumEquality(vars,
2860 solver->MakeSum(target, -constant)->Var());
2864 return solver->RevAlloc(
new PositiveBooleanScalProdEqVar(
2865 solver, vars, coefs, solver->MakeSum(target, -constant)->Var()));
2867 std::vector<IntVar*> terms;
2868 for (
int i = 0; i < size; ++i) {
2869 terms.push_back(solver->MakeProd(vars[i], coefs[i])->Var());
2871 return solver->MakeSumEquality(terms,
2872 solver->MakeSum(target, -constant)->Var());
2875 Constraint* MakeScalProdGreaterOrEqualFct(Solver* solver,
2876 const std::vector<IntVar*>& pre_vars,
2877 const std::vector<int64>& pre_coefs,
2880 std::vector<IntVar*> vars;
2881 std::vector<int64> coefs;
2882 DeepLinearize(solver, pre_vars, pre_coefs, &vars, &coefs, &constant);
2883 cst =
CapSub(cst, constant);
2885 const int size = vars.size();
2886 if (size == 0 || AreAllNull<int64>(coefs)) {
2887 return cst <= 0 ? solver->MakeTrueConstraint()
2888 : solver->MakeFalseConstraint();
2891 return solver->MakeSumGreaterOrEqual(vars, cst);
2895 std::vector<IntVar*> terms;
2896 for (
int i = 0; i < size; ++i) {
2898 terms.push_back(vars[i]);
2901 return solver->MakeSumGreaterOrEqual(terms, 1);
2903 std::vector<IntVar*> terms;
2904 for (
int i = 0; i < size; ++i) {
2905 terms.push_back(solver->MakeProd(vars[i], coefs[i])->Var());
2907 return solver->MakeSumGreaterOrEqual(terms, cst);
2910 Constraint* MakeScalProdLessOrEqualFct(Solver* solver,
2911 const std::vector<IntVar*>& pre_vars,
2912 const std::vector<int64>& pre_coefs,
2913 int64 upper_bound) {
2915 std::vector<IntVar*> vars;
2916 std::vector<int64> coefs;
2917 DeepLinearize(solver, pre_vars, pre_coefs, &vars, &coefs, &constant);
2918 upper_bound =
CapSub(upper_bound, constant);
2920 const int size = vars.size();
2921 if (size == 0 || AreAllNull<int64>(coefs)) {
2922 return upper_bound >= 0 ? solver->MakeTrueConstraint()
2923 : solver->MakeFalseConstraint();
2928 for (
int i = 0; i < size; ++i) {
2931 return cst <= upper_bound ? solver->MakeTrueConstraint()
2932 : solver->MakeFalseConstraint();
2935 return solver->MakeSumLessOrEqual(vars, upper_bound);
2938 return solver->RevAlloc(
2939 new BooleanScalProdLessConstant(solver, vars, coefs, upper_bound));
2945 for (
int i = 0; i < size; ++i) {
2946 if (coefs[i] == 0 || vars[i]->Bound()) {
2948 }
else if (coefs[i] > 0) {
2954 if (positives > 0 && negatives > 0) {
2955 std::vector<IntVar*> pos_terms;
2956 std::vector<IntVar*> neg_terms;
2957 int64 rhs = upper_bound;
2958 for (
int i = 0; i < size; ++i) {
2959 if (coefs[i] == 0 || vars[i]->Bound()) {
2961 }
else if (coefs[i] > 0) {
2962 pos_terms.push_back(solver->MakeProd(vars[i], coefs[i])->Var());
2964 neg_terms.push_back(solver->MakeProd(vars[i], -coefs[i])->Var());
2967 if (negatives == 1) {
2968 IntExpr*
const neg_term = solver->MakeSum(neg_terms[0], rhs);
2969 return solver->MakeLessOrEqual(solver->MakeSum(pos_terms), neg_term);
2970 }
else if (positives == 1) {
2971 IntExpr*
const pos_term = solver->MakeSum(pos_terms[0], -rhs);
2972 return solver->MakeGreaterOrEqual(solver->MakeSum(neg_terms), pos_term);
2975 neg_terms.push_back(solver->MakeIntConst(rhs));
2977 return solver->MakeLessOrEqual(solver->MakeSum(pos_terms),
2978 solver->MakeSum(neg_terms));
2980 }
else if (positives == 1) {
2981 IntExpr* pos_term =
nullptr;
2982 int64 rhs = upper_bound;
2983 for (
int i = 0; i < size; ++i) {
2984 if (coefs[i] == 0 || vars[i]->Bound()) {
2986 }
else if (coefs[i] > 0) {
2987 pos_term = solver->MakeProd(vars[i], coefs[i]);
2989 LOG(
FATAL) <<
"Should not be here";
2992 return solver->MakeLessOrEqual(pos_term, rhs);
2993 }
else if (negatives == 1) {
2994 IntExpr* neg_term =
nullptr;
2995 int64 rhs = upper_bound;
2996 for (
int i = 0; i < size; ++i) {
2997 if (coefs[i] == 0 || vars[i]->Bound()) {
2999 }
else if (coefs[i] > 0) {
3000 LOG(
FATAL) <<
"Should not be here";
3002 neg_term = solver->MakeProd(vars[i], -coefs[i]);
3005 return solver->MakeGreaterOrEqual(neg_term, -rhs);
3006 }
else if (positives > 1) {
3007 std::vector<IntVar*> pos_terms;
3008 int64 rhs = upper_bound;
3009 for (
int i = 0; i < size; ++i) {
3010 if (coefs[i] == 0 || vars[i]->Bound()) {
3012 }
else if (coefs[i] > 0) {
3013 pos_terms.push_back(solver->MakeProd(vars[i], coefs[i])->Var());
3015 LOG(
FATAL) <<
"Should not be here";
3018 return solver->MakeSumLessOrEqual(pos_terms, rhs);
3019 }
else if (negatives > 1) {
3020 std::vector<IntVar*> neg_terms;
3021 int64 rhs = upper_bound;
3022 for (
int i = 0; i < size; ++i) {
3023 if (coefs[i] == 0 || vars[i]->Bound()) {
3025 }
else if (coefs[i] > 0) {
3026 LOG(
FATAL) <<
"Should not be here";
3028 neg_terms.push_back(solver->MakeProd(vars[i], -coefs[i])->Var());
3031 return solver->MakeSumGreaterOrEqual(neg_terms, -rhs);
3033 std::vector<IntVar*> terms;
3034 for (
int i = 0; i < size; ++i) {
3035 terms.push_back(solver->MakeProd(vars[i], coefs[i])->Var());
3037 return solver->MakeLessOrEqual(solver->MakeSum(terms), upper_bound);
3040 IntExpr* MakeSumArrayAux(Solver*
const solver,
const std::vector<IntVar*>& vars,
3042 const int size = vars.size();
3046 for (
int i = 0; i < size; ++i) {
3048 new_min =
CapAdd(vars[i]->Min(), new_min);
3051 new_max =
CapAdd(vars[i]->Max(), new_max);
3054 IntExpr*
const cache =
3055 solver->Cache()->FindVarArrayExpression(vars, ModelCache::VAR_ARRAY_SUM);
3056 if (cache !=
nullptr) {
3057 return solver->MakeSum(cache, constant);
3059 const std::string
name =
3060 absl::StrFormat(
"Sum([%s])",
JoinNamePtr(vars,
", "));
3061 IntVar*
const sum_var = solver->MakeIntVar(new_min, new_max,
name);
3063 solver->AddConstraint(
3064 solver->RevAlloc(
new SumBooleanEqualToVar(solver, vars, sum_var)));
3065 }
else if (size <= solver->
parameters().array_split_size()) {
3066 solver->AddConstraint(
3067 solver->RevAlloc(
new SmallSumConstraint(solver, vars, sum_var)));
3069 solver->AddConstraint(
3070 solver->RevAlloc(
new SumConstraint(solver, vars, sum_var)));
3072 solver->Cache()->InsertVarArrayExpression(sum_var, vars,
3073 ModelCache::VAR_ARRAY_SUM);
3074 return solver->MakeSum(sum_var, constant);
3078 IntExpr* MakeSumAux(Solver*
const solver,
const std::vector<IntVar*>& vars,
3080 const int size = vars.size();
3082 return solver->MakeIntConst(constant);
3083 }
else if (size == 1) {
3084 return solver->MakeSum(vars[0], constant);
3085 }
else if (size == 2) {
3086 return solver->MakeSum(solver->MakeSum(vars[0], vars[1]), constant);
3088 return MakeSumArrayAux(solver, vars, constant);
3092 IntExpr* MakeScalProdAux(Solver* solver,
const std::vector<IntVar*>& vars,
3093 const std::vector<int64>& coefs,
int64 constant) {
3095 return MakeSumAux(solver, vars, constant);
3098 const int size = vars.size();
3100 return solver->MakeIntConst(constant);
3101 }
else if (size == 1) {
3102 return solver->MakeSum(solver->MakeProd(vars[0], coefs[0]), constant);
3103 }
else if (size == 2) {
3104 if (coefs[0] > 0 && coefs[1] < 0) {
3105 return solver->MakeSum(
3106 solver->MakeDifference(solver->MakeProd(vars[0], coefs[0]),
3107 solver->MakeProd(vars[1], -coefs[1])),
3109 }
else if (coefs[0] < 0 && coefs[1] > 0) {
3110 return solver->MakeSum(
3111 solver->MakeDifference(solver->MakeProd(vars[1], coefs[1]),
3112 solver->MakeProd(vars[0], -coefs[0])),
3115 return solver->MakeSum(
3116 solver->MakeSum(solver->MakeProd(vars[0], coefs[0]),
3117 solver->MakeProd(vars[1], coefs[1])),
3123 if (vars.size() > 8) {
3124 return solver->MakeSum(
3126 ->RegisterIntExpr(solver->RevAlloc(
3127 new PositiveBooleanScalProd(solver, vars, coefs)))
3131 return solver->MakeSum(
3132 solver->RegisterIntExpr(solver->RevAlloc(
3133 new PositiveBooleanScalProd(solver, vars, coefs))),
3144 std::vector<int64> positive_coefs;
3145 std::vector<int64> negative_coefs;
3146 std::vector<IntVar*> positive_coef_vars;
3147 std::vector<IntVar*> negative_coef_vars;
3148 for (
int i = 0; i < size; ++i) {
3149 const int coef = coefs[i];
3151 positive_coefs.push_back(
coef);
3152 positive_coef_vars.push_back(vars[i]);
3153 }
else if (
coef < 0) {
3154 negative_coefs.push_back(-
coef);
3155 negative_coef_vars.push_back(vars[i]);
3158 CHECK_GT(negative_coef_vars.size(), 0);
3159 IntExpr*
const negatives =
3160 MakeScalProdAux(solver, negative_coef_vars, negative_coefs, 0);
3161 if (!positive_coef_vars.empty()) {
3162 IntExpr*
const positives = MakeScalProdAux(solver, positive_coef_vars,
3163 positive_coefs, constant);
3164 return solver->MakeDifference(positives, negatives);
3166 return solver->MakeDifference(constant, negatives);
3171 std::vector<IntVar*> terms;
3172 for (
int i = 0; i < size; ++i) {
3173 terms.push_back(solver->MakeProd(vars[i], coefs[i])->Var());
3175 return MakeSumArrayAux(solver, terms, constant);
3178 IntExpr* MakeScalProdFct(Solver* solver,
const std::vector<IntVar*>& pre_vars,
3179 const std::vector<int64>& pre_coefs) {
3181 std::vector<IntVar*> vars;
3182 std::vector<int64> coefs;
3183 DeepLinearize(solver, pre_vars, pre_coefs, &vars, &coefs, &constant);
3186 return solver->MakeIntConst(constant);
3189 int64 gcd = std::abs(coefs[0]);
3190 for (
int i = 1; i < coefs.size(); ++i) {
3191 gcd = MathUtil::GCD64(gcd, std::abs(coefs[i]));
3196 if (constant != 0 && gcd != 1) {
3197 gcd = MathUtil::GCD64(gcd, std::abs(constant));
3200 for (
int i = 0; i < coefs.size(); ++i) {
3203 return solver->MakeProd(
3204 MakeScalProdAux(solver, vars, coefs, constant / gcd), gcd);
3206 return MakeScalProdAux(solver, vars, coefs, constant);
3209 IntExpr* MakeSumFct(Solver* solver,
const std::vector<IntVar*>& pre_vars) {
3210 absl::flat_hash_map<IntVar*, int64> variables_to_coefficients;
3211 ExprLinearizer linearizer(&variables_to_coefficients);
3212 for (
int i = 0; i < pre_vars.size(); ++i) {
3213 linearizer.Visit(pre_vars[i], 1);
3215 const int64 constant = linearizer.Constant();
3216 std::vector<IntVar*> vars;
3217 std::vector<int64> coefs;
3218 for (
const auto& variable_to_coefficient : variables_to_coefficients) {
3219 if (variable_to_coefficient.second != 0) {
3220 vars.push_back(variable_to_coefficient.first);
3221 coefs.push_back(variable_to_coefficient.second);
3224 return MakeScalProdAux(solver, vars, coefs, constant);
3230 IntExpr* Solver::MakeSum(
const std::vector<IntVar*>& vars) {
3231 const int size = vars.size();
3233 return MakeIntConst(
int64{0});
3234 }
else if (size == 1) {
3236 }
else if (size == 2) {
3237 return MakeSum(vars[0], vars[1]);
3240 model_cache_->FindVarArrayExpression(vars, ModelCache::VAR_ARRAY_SUM);
3241 if (cache !=
nullptr) {
3246 for (
int i = 0; i < size; ++i) {
3248 new_min =
CapAdd(vars[i]->Min(), new_min);
3251 new_max =
CapAdd(vars[i]->Max(), new_max);
3257 const std::string
name =
3258 absl::StrFormat(
"BooleanSum([%s])",
JoinNamePtr(vars,
", "));
3259 sum_expr = MakeIntVar(new_min, new_max,
name);
3261 RevAlloc(
new SumBooleanEqualToVar(
this, vars, sum_expr->
Var())));
3263 sum_expr = MakeSumFct(
this, vars);
3265 const std::string
name =
3266 absl::StrFormat(
"Sum([%s])",
JoinNamePtr(vars,
", "));
3267 sum_expr = MakeIntVar(new_min, new_max,
name);
3269 RevAlloc(
new SafeSumConstraint(
this, vars, sum_expr->
Var())));
3271 model_cache_->InsertVarArrayExpression(sum_expr, vars,
3272 ModelCache::VAR_ARRAY_SUM);
3278 IntExpr* Solver::MakeMin(
const std::vector<IntVar*>& vars) {
3279 const int size = vars.size();
3281 LOG(
WARNING) <<
"operations_research::Solver::MakeMin() was called with an "
3282 "empty list of variables. Was this intentional?";
3284 }
else if (size == 1) {
3286 }
else if (size == 2) {
3287 return MakeMin(vars[0], vars[1]);
3290 model_cache_->FindVarArrayExpression(vars, ModelCache::VAR_ARRAY_MIN);
3291 if (cache !=
nullptr) {
3295 IntVar*
const new_var = MakeBoolVar();
3296 AddConstraint(RevAlloc(
new ArrayBoolAndEq(
this, vars, new_var)));
3297 model_cache_->InsertVarArrayExpression(new_var, vars,
3298 ModelCache::VAR_ARRAY_MIN);
3303 for (
int i = 0; i < size; ++i) {
3304 new_min =
std::min(new_min, vars[i]->Min());
3305 new_max =
std::min(new_max, vars[i]->Max());
3307 IntVar*
const new_var = MakeIntVar(new_min, new_max);
3308 if (size <= parameters_.array_split_size()) {
3309 AddConstraint(RevAlloc(
new SmallMinConstraint(
this, vars, new_var)));
3311 AddConstraint(RevAlloc(
new MinConstraint(
this, vars, new_var)));
3313 model_cache_->InsertVarArrayExpression(new_var, vars,
3314 ModelCache::VAR_ARRAY_MIN);
3321 IntExpr* Solver::MakeMax(
const std::vector<IntVar*>& vars) {
3322 const int size = vars.size();
3324 LOG(
WARNING) <<
"operations_research::Solver::MakeMax() was called with an "
3325 "empty list of variables. Was this intentional?";
3327 }
else if (size == 1) {
3329 }
else if (size == 2) {
3330 return MakeMax(vars[0], vars[1]);
3333 model_cache_->FindVarArrayExpression(vars, ModelCache::VAR_ARRAY_MAX);
3334 if (cache !=
nullptr) {
3338 IntVar*
const new_var = MakeBoolVar();
3339 AddConstraint(RevAlloc(
new ArrayBoolOrEq(
this, vars, new_var)));
3340 model_cache_->InsertVarArrayExpression(new_var, vars,
3341 ModelCache::VAR_ARRAY_MIN);
3346 for (
int i = 0; i < size; ++i) {
3347 new_min =
std::max(new_min, vars[i]->Min());
3348 new_max =
std::max(new_max, vars[i]->Max());
3350 IntVar*
const new_var = MakeIntVar(new_min, new_max);
3351 if (size <= parameters_.array_split_size()) {
3352 AddConstraint(RevAlloc(
new SmallMaxConstraint(
this, vars, new_var)));
3354 AddConstraint(RevAlloc(
new MaxConstraint(
this, vars, new_var)));
3356 model_cache_->InsertVarArrayExpression(new_var, vars,
3357 ModelCache::VAR_ARRAY_MAX);
3364 Constraint* Solver::MakeMinEquality(
const std::vector<IntVar*>& vars,
3366 const int size = vars.size();
3369 return RevAlloc(
new ArrayBoolAndEq(
this, vars, min_var));
3370 }
else if (size <= parameters_.array_split_size()) {
3371 return RevAlloc(
new SmallMinConstraint(
this, vars, min_var));
3373 return RevAlloc(
new MinConstraint(
this, vars, min_var));
3375 }
else if (size == 2) {
3376 return MakeEquality(MakeMin(vars[0], vars[1]), min_var);
3377 }
else if (size == 1) {
3378 return MakeEquality(vars[0], min_var);
3380 LOG(
WARNING) <<
"operations_research::Solver::MakeMinEquality() was called "
3381 "with an empty list of variables. Was this intentional?";
3382 return MakeEquality(min_var,
kint64max);
3386 Constraint* Solver::MakeMaxEquality(
const std::vector<IntVar*>& vars,
3388 const int size = vars.size();
3391 return RevAlloc(
new ArrayBoolOrEq(
this, vars, max_var));
3392 }
else if (size <= parameters_.array_split_size()) {
3393 return RevAlloc(
new SmallMaxConstraint(
this, vars, max_var));
3395 return RevAlloc(
new MaxConstraint(
this, vars, max_var));
3397 }
else if (size == 2) {
3398 return MakeEquality(MakeMax(vars[0], vars[1]), max_var);
3399 }
else if (size == 1) {
3400 return MakeEquality(vars[0], max_var);
3402 LOG(
WARNING) <<
"operations_research::Solver::MakeMaxEquality() was called "
3403 "with an empty list of variables. Was this intentional?";
3404 return MakeEquality(max_var,
kint64min);
3408 Constraint* Solver::MakeSumLessOrEqual(
const std::vector<IntVar*>& vars,
3410 const int size = vars.size();
3412 return RevAlloc(
new SumBooleanLessOrEqualToOne(
this, vars));
3414 return MakeLessOrEqual(MakeSum(vars), cst);
3418 Constraint* Solver::MakeSumGreaterOrEqual(
const std::vector<IntVar*>& vars,
3420 const int size = vars.size();
3422 return RevAlloc(
new SumBooleanGreaterOrEqualToOne(
this, vars));
3424 return MakeGreaterOrEqual(MakeSum(vars), cst);
3428 Constraint* Solver::MakeSumEquality(
const std::vector<IntVar*>& vars,
3430 const int size = vars.size();
3432 return cst == 0 ? MakeTrueConstraint() : MakeFalseConstraint();
3436 return RevAlloc(
new SumBooleanEqualToOne(
this, vars));
3437 }
else if (cst < 0 || cst > size) {
3438 return MakeFalseConstraint();
3440 return RevAlloc(
new SumBooleanEqualToVar(
this, vars, MakeIntConst(cst)));
3443 if (vars.size() == 1) {
3444 return MakeEquality(vars[0], cst);
3445 }
else if (vars.size() == 2) {
3446 return MakeEquality(vars[0], MakeDifference(cst, vars[1]));
3448 if (DetectSumOverflow(vars)) {
3449 return RevAlloc(
new SafeSumConstraint(
this, vars, MakeIntConst(cst)));
3450 }
else if (size <= parameters_.array_split_size()) {
3451 return RevAlloc(
new SmallSumConstraint(
this, vars, MakeIntConst(cst)));
3453 return RevAlloc(
new SumConstraint(
this, vars, MakeIntConst(cst)));
3458 Constraint* Solver::MakeSumEquality(
const std::vector<IntVar*>& vars,
3460 const int size = vars.size();
3462 return MakeEquality(
var,
Zero());
3465 return RevAlloc(
new SumBooleanEqualToVar(
this, vars,
var));
3466 }
else if (size == 0) {
3467 return MakeEquality(
var,
Zero());
3468 }
else if (size == 1) {
3469 return MakeEquality(vars[0],
var);
3470 }
else if (size == 2) {
3471 return MakeEquality(MakeSum(vars[0], vars[1]),
var);
3473 if (DetectSumOverflow(vars)) {
3474 return RevAlloc(
new SafeSumConstraint(
this, vars,
var));
3475 }
else if (size <= parameters_.array_split_size()) {
3476 return RevAlloc(
new SmallSumConstraint(
this, vars,
var));
3478 return RevAlloc(
new SumConstraint(
this, vars,
var));
3483 Constraint* Solver::MakeScalProdEquality(
const std::vector<IntVar*>& vars,
3487 return MakeScalProdEqualityFct(
this, vars,
coefficients, cst);
3490 Constraint* Solver::MakeScalProdEquality(
const std::vector<IntVar*>& vars,
3497 Constraint* Solver::MakeScalProdEquality(
const std::vector<IntVar*>& vars,
3501 return MakeScalProdEqualityVarFct(
this, vars,
coefficients, target);
3504 Constraint* Solver::MakeScalProdEquality(
const std::vector<IntVar*>& vars,
3512 Constraint* Solver::MakeScalProdGreaterOrEqual(
const std::vector<IntVar*>& vars,
3513 const std::vector<int64>& coeffs,
3516 return MakeScalProdGreaterOrEqualFct(
this, vars, coeffs, cst);
3519 Constraint* Solver::MakeScalProdGreaterOrEqual(
const std::vector<IntVar*>& vars,
3520 const std::vector<int>& coeffs,
3523 return MakeScalProdGreaterOrEqualFct(
this, vars,
ToInt64Vector(coeffs), cst);
3527 const std::vector<IntVar*>& vars,
const std::vector<int64>&
coefficients,
3530 return MakeScalProdLessOrEqualFct(
this, vars,
coefficients, cst);
3534 const std::vector<IntVar*>& vars,
const std::vector<int>&
coefficients,
3541 IntExpr* Solver::MakeScalProd(
const std::vector<IntVar*>& vars,
3542 const std::vector<int64>& coefs) {
3544 return MakeScalProdFct(
this, vars, coefs);
3547 IntExpr* Solver::MakeScalProd(
const std::vector<IntVar*>& vars,
3548 const std::vector<int>& coefs) {