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) {
#define DCHECK_NE(val1, val2)
#define CHECK_LT(val1, val2)
#define CHECK_EQ(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)
A constraint is the main modeling object.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual IntVar * Var()=0
Creates a variable from the expression.
The class IntVar is a subset of IntExpr.
static const char kSumEqual[]
static const char kTargetArgument[]
static const char kValueArgument[]
static const char kMaxEqual[]
static const char kSumLessOrEqual[]
static const char kVarsArgument[]
static const char kMinEqual[]
static const char kSumGreaterOrEqual[]
void Decr(Solver *const s)
void Incr(Solver *const s)
void SetValue(Solver *const s, const T &val)
const std::vector< IntVar * > vars_
#define IS_TYPE(type, tag)
static const int64 kint64max
static const int64 kint64min
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapSub(int64 x, int64 y)
bool AreAllNegative(const std::vector< T > &values)
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
bool AreAllBoundOrNull(const std::vector< IntVar * > &vars, const std::vector< T > &values)
Returns true if all the variables are assigned to a single value, or if their corresponding value is ...
bool AreAllBooleans(const std::vector< IntVar * > &vars)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
int64 CapAdd(int64 x, int64 y)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
bool AreAllNull(const std::vector< T > &values)
int64 CapProd(int64 x, int64 y)
bool AreAllPositive(const std::vector< T > &values)
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
bool AreAllOnes(const std::vector< T > &values)
std::string JoinNamePtr(const std::vector< T > &v, const std::string &separator)
std::vector< double > coefficients
IntervalVar *const target_var_