OR-Tools  8.2
count_cst.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14//
15// Count constraints
16
17#include <algorithm>
18#include <string>
19#include <vector>
20
21#include "absl/strings/str_format.h"
22#include "absl/strings/str_join.h"
28
29namespace operations_research {
30Constraint* Solver::MakeCount(const std::vector<IntVar*>& vars, int64 value,
31 int64 max_count) {
32 std::vector<IntVar*> tmp_sum;
33 for (int i = 0; i < vars.size(); ++i) {
34 if (vars[i]->Contains(value)) {
35 if (vars[i]->Bound()) {
36 max_count--;
37 } else {
38 tmp_sum.push_back(MakeIsEqualCstVar(vars[i], value));
39 }
40 }
41 }
42 return MakeSumEquality(tmp_sum, max_count);
43}
44
45Constraint* Solver::MakeCount(const std::vector<IntVar*>& vars, int64 value,
46 IntVar* max_count) {
47 if (max_count->Bound()) {
48 return MakeCount(vars, value, max_count->Min());
49 } else {
50 std::vector<IntVar*> tmp_sum;
51 int64 num_vars_bound_to_v = 0;
52 for (int i = 0; i < vars.size(); ++i) {
53 if (vars[i]->Contains(value)) {
54 if (vars[i]->Bound()) {
55 ++num_vars_bound_to_v;
56 } else {
57 tmp_sum.push_back(MakeIsEqualCstVar(vars[i], value));
58 }
59 }
60 }
61 return MakeSumEquality(tmp_sum,
62 MakeSum(max_count, -num_vars_bound_to_v)->Var());
63 }
64}
65
66// ---------- Distribute ----------
67
68namespace {
69class AtMost : public Constraint {
70 public:
71 AtMost(Solver* const s, std::vector<IntVar*> vars, int64 value,
72 int64 max_count)
73 : Constraint(s),
74 vars_(std::move(vars)),
75 value_(value),
76 max_count_(max_count),
77 current_count_(0) {}
78
79 ~AtMost() override {}
80
81 void Post() override {
82 for (IntVar* var : vars_) {
83 if (!var->Bound() && var->Contains(value_)) {
84 Demon* const d = MakeConstraintDemon1(solver(), this, &AtMost::OneBound,
85 "OneBound", var);
86 var->WhenBound(d);
87 }
88 }
89 }
90
91 void InitialPropagate() override {
92 for (IntVar* var : vars_) {
93 if (var->Bound() && var->Min() == value_) {
94 current_count_.Incr(solver());
95 }
96 }
97 CheckCount();
98 }
99
100 void OneBound(IntVar* var) {
101 if (var->Min() == value_) {
102 current_count_.Incr(solver());
103 CheckCount();
104 }
105 }
106
107 void CheckCount() {
108 if (current_count_.Value() < max_count_) {
109 return;
110 }
111
112 // Remove all remaining values.
113 int forced = 0;
114 for (IntVar* var : vars_) {
115 if (var->Bound()) {
116 if (var->Min() == value_) {
117 forced++;
118 }
119 } else {
120 var->RemoveValue(value_);
121 }
122 }
123 if (forced > max_count_) {
124 solver()->Fail();
125 }
126 }
127
128 std::string DebugString() const override {
129 return absl::StrFormat("AtMost(%s, %d, %d)",
130 JoinDebugStringPtr(vars_, ", "), value_, max_count_);
131 }
132
133 void Accept(ModelVisitor* const visitor) const override {
134 visitor->BeginVisitConstraint(ModelVisitor::kAtMost, this);
135 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
136 vars_);
137 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, value_);
138 visitor->VisitIntegerArgument(ModelVisitor::kCountArgument, max_count_);
139 visitor->EndVisitConstraint(ModelVisitor::kAtMost, this);
140 }
141
142 private:
143 const std::vector<IntVar*> vars_;
144 const int64 value_;
145 const int64 max_count_;
146 NumericalRev<int> current_count_;
147};
148
149class Distribute : public Constraint {
150 public:
151 Distribute(Solver* const s, const std::vector<IntVar*>& vars,
152 const std::vector<int64>& values,
153 const std::vector<IntVar*>& cards)
154 : Constraint(s),
155 vars_(vars),
156 values_(values),
157 cards_(cards),
158 undecided_(vars.size(), cards.size()),
159 min_(cards.size(), 0),
160 max_(cards.size(), 0) {}
161
162 ~Distribute() override {}
163
164 void Post() override;
165 void InitialPropagate() override;
166 void OneBound(int index);
167 void OneDomain(int index);
168 void CountVar(int cindex);
169 void CardMin(int cindex);
170 void CardMax(int cindex);
171 std::string DebugString() const override {
172 return absl::StrFormat(
173 "Distribute(vars = [%s], values = [%s], cards = [%s])",
174 JoinDebugStringPtr(vars_, ", "), absl::StrJoin(values_, ", "),
175 JoinDebugStringPtr(cards_, ", "));
176 }
177
178 void Accept(ModelVisitor* const visitor) const override {
179 visitor->BeginVisitConstraint(ModelVisitor::kDistribute, this);
180 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
181 vars_);
182 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument, values_);
183 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCardsArgument,
184 cards_);
185 visitor->EndVisitConstraint(ModelVisitor::kDistribute, this);
186 }
187
188 private:
189 int64 var_size() const { return vars_.size(); }
190 int64 card_size() const { return cards_.size(); }
191
192 const std::vector<IntVar*> vars_;
193 const std::vector<int64> values_;
194 const std::vector<IntVar*> cards_;
195 RevBitMatrix undecided_;
196 NumericalRevArray<int> min_;
197 NumericalRevArray<int> max_;
198};
199
200void Distribute::Post() {
201 for (int i = 0; i < var_size(); ++i) {
202 IntVar* const var = vars_[i];
203 if (!var->Bound()) {
204 Demon* d = MakeConstraintDemon1(solver(), this, &Distribute::OneBound,
205 "OneBound", i);
206 var->WhenBound(d);
207 d = MakeConstraintDemon1(solver(), this, &Distribute::OneDomain,
208 "OneDomain", i);
209 var->WhenDomain(d);
210 }
211 }
212 for (int i = 0; i < card_size(); ++i) {
213 if (!cards_[i]->Bound()) {
214 Demon* d =
215 MakeConstraintDemon1(solver(), this, &Distribute::CountVar, "Var", i);
216 cards_[i]->WhenRange(d);
217 }
218 }
219}
220
221void Distribute::InitialPropagate() {
222 Solver* const s = solver();
223 for (int j = 0; j < card_size(); ++j) {
224 int min = 0;
225 int max = 0;
226 for (int i = 0; i < var_size(); ++i) {
227 IntVar* const var = vars_[i];
228 if (var->Bound()) {
229 if (var->Min() == values_[j]) {
230 min++;
231 max++;
232 }
233 } else {
234 if (var->Contains(values_[j])) {
235 max++;
236 undecided_.SetToOne(s, i, j);
237 }
238 }
239 }
240 cards_[j]->SetRange(min, max);
241 if (cards_[j]->Max() == min) {
242 CardMin(j);
243 } else if (cards_[j]->Min() == max) {
244 CardMax(j);
245 }
246 min_.SetValue(s, j, min);
247 max_.SetValue(s, j, max);
248 }
249}
250
251void Distribute::OneBound(int index) {
252 IntVar* const var = vars_[index];
253 Solver* const s = solver();
254 for (int j = 0; j < card_size(); ++j) {
255 if (undecided_.IsSet(index, j)) {
256 undecided_.SetToZero(s, index, j);
257 if (var->Min() == values_[j]) {
258 min_.Incr(s, j);
259 cards_[j]->SetMin(min_[j]);
260 if (min_[j] == cards_[j]->Max()) {
261 CardMin(j);
262 }
263 } else {
264 max_.Decr(s, j);
265 cards_[j]->SetMax(max_[j]);
266 if (max_[j] == cards_[j]->Min()) {
267 CardMax(j);
268 }
269 }
270 }
271 }
272}
273
274void Distribute::OneDomain(int index) {
275 IntVar* const var = vars_[index];
276 Solver* const s = solver();
277 for (int j = 0; j < card_size(); ++j) {
278 if (undecided_.IsSet(index, j)) {
279 if (!var->Contains(values_[j])) {
280 undecided_.SetToZero(s, index, j);
281 max_.Decr(s, j);
282 cards_[j]->SetMax(max_[j]);
283 if (max_[j] == cards_[j]->Min()) {
284 CardMax(j);
285 }
286 }
287 }
288 }
289}
290
291void Distribute::CountVar(int cindex) {
292 if (cards_[cindex]->Min() > max_[cindex] ||
293 cards_[cindex]->Max() < min_[cindex]) {
294 solver()->Fail();
295 }
296 if (cards_[cindex]->Min() == max_[cindex]) {
297 CardMax(cindex);
298 }
299 if (cards_[cindex]->Max() == min_[cindex]) {
300 CardMin(cindex);
301 }
302}
303
304void Distribute::CardMin(int cindex) {
305 for (int i = 0; i < var_size(); ++i) {
306 if (undecided_.IsSet(i, cindex)) {
307 vars_[i]->RemoveValue(values_[cindex]);
308 }
309 }
310}
311
312void Distribute::CardMax(int cindex) {
313 for (int i = 0; i < var_size(); ++i) {
314 if (undecided_.IsSet(i, cindex)) {
315 vars_[i]->SetValue(values_[cindex]);
316 }
317 }
318}
319
320// ----- FastDistribute -----
321
322class FastDistribute : public Constraint {
323 public:
324 FastDistribute(Solver* const s, const std::vector<IntVar*>& vars,
325 const std::vector<IntVar*>& cards);
326 ~FastDistribute() override {}
327
328 void Post() override;
329 void InitialPropagate() override;
330 void OneBound(int index);
331 void OneDomain(int index);
332 void CountVar(int card_index);
333 void CardMin(int card_index);
334 void CardMax(int card_index);
335 std::string DebugString() const override;
336 void SetRevCannotContribute(int64 var_index, int64 card_index) {
337 Solver* const s = solver();
338 undecided_.SetToZero(s, var_index, card_index);
339 max_.Decr(s, card_index);
340 cards_[card_index]->SetMax(max_[card_index]);
341 if (max_[card_index] == cards_[card_index]->Min()) {
342 CardMax(card_index);
343 }
344 }
345 void SetRevDoContribute(int64 var_index, int64 card_index) {
346 Solver* const s = solver();
347 undecided_.SetToZero(s, var_index, card_index);
348 min_.Incr(s, card_index);
349 cards_[card_index]->SetMin(min_[card_index]);
350 if (min_[card_index] == cards_[card_index]->Max()) {
351 CardMin(card_index);
352 }
353 }
354
355 void Accept(ModelVisitor* const visitor) const override {
356 visitor->BeginVisitConstraint(ModelVisitor::kDistribute, this);
357 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
358 vars_);
359 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCardsArgument,
360 cards_);
361 visitor->EndVisitConstraint(ModelVisitor::kDistribute, this);
362 }
363
364 private:
365 int64 var_size() const { return vars_.size(); }
366 int64 card_size() const { return cards_.size(); }
367
368 const std::vector<IntVar*> vars_;
369 const std::vector<IntVar*> cards_;
370 RevBitMatrix undecided_;
371 NumericalRevArray<int> min_;
372 NumericalRevArray<int> max_;
373 std::vector<IntVarIterator*> holes_;
374};
375
376FastDistribute::FastDistribute(Solver* const s,
377 const std::vector<IntVar*>& vars,
378 const std::vector<IntVar*>& cards)
379 : Constraint(s),
380 vars_(vars),
381 cards_(cards),
382 undecided_(vars.size(), cards.size()),
383 min_(cards.size(), 0),
384 max_(cards.size(), 0),
385 holes_(vars.size()) {
386 for (int var_index = 0; var_index < var_size(); ++var_index) {
387 holes_[var_index] = vars_[var_index]->MakeHoleIterator(true);
388 }
389}
390
391std::string FastDistribute::DebugString() const {
392 return absl::StrFormat("FastDistribute(vars = [%s], cards = [%s])",
393 JoinDebugStringPtr(vars_, ", "),
394 JoinDebugStringPtr(cards_, ", "));
395}
396
397void FastDistribute::Post() {
398 for (int var_index = 0; var_index < var_size(); ++var_index) {
399 IntVar* const var = vars_[var_index];
400 if (!var->Bound()) {
401 Demon* d = MakeConstraintDemon1(solver(), this, &FastDistribute::OneBound,
402 "OneBound", var_index);
403 var->WhenBound(d);
404 d = MakeConstraintDemon1(solver(), this, &FastDistribute::OneDomain,
405 "OneDomain", var_index);
406 var->WhenDomain(d);
407 }
408 }
409 for (int card_index = 0; card_index < card_size(); ++card_index) {
410 if (!cards_[card_index]->Bound()) {
411 Demon* d = MakeConstraintDemon1(solver(), this, &FastDistribute::CountVar,
412 "Var", card_index);
413 cards_[card_index]->WhenRange(d);
414 }
415 }
416}
417
418void FastDistribute::InitialPropagate() {
419 Solver* const s = solver();
420 for (int card_index = 0; card_index < card_size(); ++card_index) {
421 int min = 0;
422 int max = 0;
423 for (int var_index = 0; var_index < var_size(); ++var_index) {
424 IntVar* const var = vars_[var_index];
425 if (var->Bound() && var->Min() == card_index) {
426 min++;
427 max++;
428 } else if (var->Contains(card_index)) {
429 max++;
430 undecided_.SetToOne(s, var_index, card_index);
431 }
432 }
433 min_.SetValue(s, card_index, min);
434 max_.SetValue(s, card_index, max);
435 CountVar(card_index);
436 }
437}
438
439void FastDistribute::OneBound(int index) {
440 IntVar* const var = vars_[index];
441 for (int card_index = 0; card_index < card_size(); ++card_index) {
442 if (undecided_.IsSet(index, card_index)) {
443 if (var->Min() == card_index) {
444 SetRevDoContribute(index, card_index);
445 } else {
446 SetRevCannotContribute(index, card_index);
447 }
448 }
449 }
450}
451
452void FastDistribute::OneDomain(int index) {
453 IntVar* const var = vars_[index];
454 const int64 oldmin = var->OldMin();
455 const int64 oldmax = var->OldMax();
456 const int64 vmin = var->Min();
457 const int64 vmax = var->Max();
458 for (int64 card_index = std::max(oldmin, int64{0});
459 card_index < std::min(vmin, card_size()); ++card_index) {
460 if (undecided_.IsSet(index, card_index)) {
461 SetRevCannotContribute(index, card_index);
462 }
463 }
464 for (const int64 card_index : InitAndGetValues(holes_[index])) {
465 if (card_index >= 0 && card_index < card_size() &&
466 undecided_.IsSet(index, card_index)) {
467 SetRevCannotContribute(index, card_index);
468 }
469 }
470 for (int64 card_index = std::max(vmax + 1, int64{0});
471 card_index <= std::min(oldmax, card_size() - 1); ++card_index) {
472 if (undecided_.IsSet(index, card_index)) {
473 SetRevCannotContribute(index, card_index);
474 }
475 }
476}
477
478void FastDistribute::CountVar(int card_index) {
479 const int64 stored_min = min_[card_index];
480 const int64 stored_max = max_[card_index];
481 cards_[card_index]->SetRange(min_[card_index], max_[card_index]);
482 if (cards_[card_index]->Min() == stored_max) {
483 CardMax(card_index);
484 }
485 if (cards_[card_index]->Max() == stored_min) {
486 CardMin(card_index);
487 }
488}
489
490void FastDistribute::CardMin(int card_index) {
491 for (int var_index = 0; var_index < var_size(); ++var_index) {
492 if (undecided_.IsSet(var_index, card_index)) {
493 vars_[var_index]->RemoveValue(card_index);
494 }
495 }
496}
497
498void FastDistribute::CardMax(int card_index) {
499 for (int var_index = 0; var_index < var_size(); ++var_index) {
500 if (undecided_.IsSet(var_index, card_index)) {
501 vars_[var_index]->SetValue(card_index);
502 }
503 }
504}
505
506// ----- BoundedDistribute -----
507
508class BoundedDistribute : public Constraint {
509 public:
510 BoundedDistribute(Solver* const s, const std::vector<IntVar*>& vars,
511 const std::vector<int64>& values,
512 const std::vector<int64>& card_min,
513 const std::vector<int64>& card_max);
514 ~BoundedDistribute() override {}
515
516 void Post() override;
517 void InitialPropagate() override;
518 void OneBound(int index);
519 void OneDomain(int index);
520 void CountVar(int card_index);
521 void CardMin(int card_index);
522 void CardMax(int card_index);
523 std::string DebugString() const override;
524 void SetRevCannotContribute(int64 var_index, int64 card_index) {
525 Solver* const s = solver();
526 undecided_.SetToZero(s, var_index, card_index);
527 max_.Decr(s, card_index);
528 if (max_[card_index] < card_min_[card_index]) {
529 solver()->Fail();
530 }
531 if (max_[card_index] == card_min_[card_index]) {
532 CardMax(card_index);
533 }
534 }
535 void SetRevDoContribute(int64 var_index, int64 card_index) {
536 Solver* const s = solver();
537 undecided_.SetToZero(s, var_index, card_index);
538 min_.Incr(s, card_index);
539 if (min_[card_index] > card_max_[card_index]) {
540 solver()->Fail();
541 }
542 if (min_[card_index] == card_max_[card_index]) {
543 CardMin(card_index);
544 }
545 }
546
547 void Accept(ModelVisitor* const visitor) const override {
548 visitor->BeginVisitConstraint(ModelVisitor::kDistribute, this);
549 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
550 vars_);
551 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument, values_);
552 visitor->VisitIntegerArrayArgument(ModelVisitor::kMinArgument, card_min_);
553 visitor->VisitIntegerArrayArgument(ModelVisitor::kMaxArgument, card_max_);
554 visitor->EndVisitConstraint(ModelVisitor::kDistribute, this);
555 }
556
557 private:
558 int64 var_size() const { return vars_.size(); }
559 int64 card_size() const { return values_.size(); }
560
561 const std::vector<IntVar*> vars_;
562 const std::vector<int64> values_;
563 const std::vector<int64> card_min_;
564 const std::vector<int64> card_max_;
565 RevBitMatrix undecided_;
566 NumericalRevArray<int> min_;
567 NumericalRevArray<int> max_;
568 std::vector<IntVarIterator*> holes_;
569};
570
571BoundedDistribute::BoundedDistribute(Solver* const s,
572 const std::vector<IntVar*>& vars,
573 const std::vector<int64>& values,
574 const std::vector<int64>& card_min,
575 const std::vector<int64>& card_max)
576 : Constraint(s),
577 vars_(vars),
578 values_(values),
579 card_min_(card_min),
580 card_max_(card_max),
581 undecided_(vars.size(), values.size()),
582 min_(values.size(), 0),
583 max_(values.size(), 0),
584 holes_(vars.size()) {
585 for (int var_index = 0; var_index < var_size(); ++var_index) {
586 holes_[var_index] = vars_[var_index]->MakeHoleIterator(true);
587 }
588}
589
590std::string BoundedDistribute::DebugString() const {
591 return absl::StrFormat(
592 "BoundedDistribute([%s], values = [%s], card_min = [%s], card_max = "
593 "[%s]",
594 JoinDebugStringPtr(vars_, ", "), absl::StrJoin(values_, ", "),
595 absl::StrJoin(card_min_, ", "), absl::StrJoin(card_max_, ", "));
596}
597
598void BoundedDistribute::Post() {
599 for (int var_index = 0; var_index < var_size(); ++var_index) {
600 IntVar* const var = vars_[var_index];
601 if (!var->Bound()) {
602 Demon* d = MakeConstraintDemon1(
603 solver(), this, &BoundedDistribute::OneBound, "OneBound", var_index);
604 var->WhenBound(d);
605 d = MakeConstraintDemon1(solver(), this, &BoundedDistribute::OneDomain,
606 "OneDomain", var_index);
607 var->WhenDomain(d);
608 }
609 }
610}
611
612void BoundedDistribute::InitialPropagate() {
613 Solver* const s = solver();
614
615 int64 sum_card_min = 0;
616 for (int i = 0; i < card_size(); ++i) {
617 if (card_max_[i] < card_min_[i]) {
618 solver()->Fail();
619 }
620 sum_card_min += card_min_[i];
621 }
622 if (sum_card_min > var_size()) {
623 s->Fail();
624 }
625 if (sum_card_min == var_size()) {
626 for (int i = 0; i < var_size(); ++i) {
627 vars_[i]->SetValues(values_);
628 }
629 }
630
631 for (int card_index = 0; card_index < card_size(); ++card_index) {
632 const int64 value = values_[card_index];
633 int min = 0;
634 int max = 0;
635 for (int i = 0; i < var_size(); ++i) {
636 IntVar* const var = vars_[i];
637 if (var->Bound()) {
638 if (var->Min() == value) {
639 min++;
640 max++;
641 }
642 } else if (var->Contains(value)) {
643 max++;
644 undecided_.SetToOne(s, i, card_index);
645 }
646 }
647 min_.SetValue(s, card_index, min);
648 max_.SetValue(s, card_index, max);
649 CountVar(card_index);
650 }
651}
652
653void BoundedDistribute::OneBound(int index) {
654 IntVar* const var = vars_[index];
655 const int64 var_min = var->Min();
656 for (int card_index = 0; card_index < card_size(); ++card_index) {
657 if (undecided_.IsSet(index, card_index)) {
658 if (var_min == values_[card_index]) {
659 SetRevDoContribute(index, card_index);
660 } else {
661 SetRevCannotContribute(index, card_index);
662 }
663 }
664 }
665}
666
667void BoundedDistribute::OneDomain(int index) {
668 IntVar* const var = vars_[index];
669 for (int card_index = 0; card_index < card_size(); ++card_index) {
670 if (undecided_.IsSet(index, card_index)) {
671 if (!var->Contains(values_[card_index])) {
672 SetRevCannotContribute(index, card_index);
673 }
674 }
675 }
676}
677
678void BoundedDistribute::CountVar(int card_index) {
679 const int64 stored_min = min_[card_index];
680 const int64 stored_max = max_[card_index];
681 if (card_min_[card_index] > stored_max ||
682 card_max_[card_index] < stored_min) {
683 solver()->Fail();
684 }
685 if (card_min_[card_index] == stored_max) {
686 CardMax(card_index);
687 }
688 if (card_max_[card_index] == stored_min) {
689 CardMin(card_index);
690 }
691}
692
693void BoundedDistribute::CardMin(int card_index) {
694 for (int var_index = 0; var_index < var_size(); ++var_index) {
695 if (undecided_.IsSet(var_index, card_index)) {
696 vars_[var_index]->RemoveValue(values_[card_index]);
697 }
698 }
699}
700
701void BoundedDistribute::CardMax(int card_index) {
702 for (int var_index = 0; var_index < var_size(); ++var_index) {
703 if (undecided_.IsSet(var_index, card_index)) {
704 vars_[var_index]->SetValue(values_[card_index]);
705 }
706 }
707}
708
709// ----- BoundedFastDistribute -----
710
711class BoundedFastDistribute : public Constraint {
712 public:
713 BoundedFastDistribute(Solver* const s, const std::vector<IntVar*>& vars,
714 const std::vector<int64>& card_min,
715 const std::vector<int64>& card_max);
716 ~BoundedFastDistribute() override {}
717
718 void Post() override;
719 void InitialPropagate() override;
720 void OneBound(int index);
721 void OneDomain(int index);
722 void CountVar(int card_index);
723 void CardMin(int card_index);
724 void CardMax(int card_index);
725 std::string DebugString() const override;
726 void SetRevCannotContribute(int64 var_index, int64 card_index) {
727 Solver* const s = solver();
728 undecided_.SetToZero(s, var_index, card_index);
729 max_.Decr(s, card_index);
730 if (max_[card_index] < card_min_[card_index]) {
731 solver()->Fail();
732 }
733 if (max_[card_index] == card_min_[card_index]) {
734 CardMax(card_index);
735 }
736 }
737 void SetRevDoContribute(int64 var_index, int64 card_index) {
738 Solver* const s = solver();
739 undecided_.SetToZero(s, var_index, card_index);
740 min_.Incr(s, card_index);
741 if (min_[card_index] > card_max_[card_index]) {
742 solver()->Fail();
743 }
744 if (min_[card_index] == card_max_[card_index]) {
745 CardMin(card_index);
746 }
747 }
748
749 void Accept(ModelVisitor* const visitor) const override {
750 visitor->BeginVisitConstraint(ModelVisitor::kDistribute, this);
751 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
752 vars_);
753 visitor->VisitIntegerArrayArgument(ModelVisitor::kMinArgument, card_min_);
754 visitor->VisitIntegerArrayArgument(ModelVisitor::kMaxArgument, card_max_);
755 visitor->EndVisitConstraint(ModelVisitor::kDistribute, this);
756 }
757
758 private:
759 int64 var_size() const { return vars_.size(); }
760 int64 card_size() const { return card_min_.size(); }
761
762 const std::vector<IntVar*> vars_;
763 const std::vector<int64> card_min_;
764 const std::vector<int64> card_max_;
765 RevBitMatrix undecided_;
766 NumericalRevArray<int> min_;
767 NumericalRevArray<int> max_;
768 std::vector<IntVarIterator*> holes_;
769};
770
771BoundedFastDistribute::BoundedFastDistribute(Solver* const s,
772 const std::vector<IntVar*>& vars,
773 const std::vector<int64>& card_min,
774 const std::vector<int64>& card_max)
775 : Constraint(s),
776 vars_(vars),
777 card_min_(card_min),
778 card_max_(card_max),
779 undecided_(vars.size(), card_min.size()),
780 min_(card_min.size(), 0),
781 max_(card_max.size(), 0),
782 holes_(vars.size()) {
783 for (int var_index = 0; var_index < var_size(); ++var_index) {
784 holes_[var_index] = vars_[var_index]->MakeHoleIterator(true);
785 }
786}
787
788std::string BoundedFastDistribute::DebugString() const {
789 return absl::StrFormat(
790 "BoundedFastDistribute([%s], card_min = [%s], card_max = [%s]",
791 JoinDebugStringPtr(vars_, ", "), absl::StrJoin(card_min_, ", "),
792 absl::StrJoin(card_max_, ", "));
793}
794
795void BoundedFastDistribute::Post() {
796 for (int var_index = 0; var_index < var_size(); ++var_index) {
797 IntVar* const var = vars_[var_index];
798 if (!var->Bound()) {
799 Demon* d =
800 MakeConstraintDemon1(solver(), this, &BoundedFastDistribute::OneBound,
801 "OneBound", var_index);
802 var->WhenBound(d);
803 d = MakeConstraintDemon1(solver(), this,
804 &BoundedFastDistribute::OneDomain, "OneDomain",
805 var_index);
806 var->WhenDomain(d);
807 }
808 }
809}
810
811void BoundedFastDistribute::InitialPropagate() {
812 Solver* const s = solver();
813
814 int64 sum_card_min = 0;
815 for (int i = 0; i < card_size(); ++i) {
816 if (card_max_[i] < card_min_[i]) {
817 solver()->Fail();
818 }
819 sum_card_min += card_min_[i];
820 }
821 if (sum_card_min > var_size()) {
822 s->Fail();
823 }
824 if (sum_card_min == var_size()) {
825 for (int i = 0; i < var_size(); ++i) {
826 vars_[i]->SetRange(0, card_size() - 1);
827 }
828 }
829
830 for (int card_index = 0; card_index < card_size(); ++card_index) {
831 int min = 0;
832 int max = 0;
833 for (int i = 0; i < var_size(); ++i) {
834 IntVar* const var = vars_[i];
835 if (var->Bound()) {
836 if (var->Min() == card_index) {
837 min++;
838 max++;
839 }
840 } else if (var->Contains(card_index)) {
841 max++;
842 undecided_.SetToOne(s, i, card_index);
843 }
844 }
845 min_.SetValue(s, card_index, min);
846 max_.SetValue(s, card_index, max);
847 CountVar(card_index);
848 }
849}
850
851void BoundedFastDistribute::OneBound(int index) {
852 IntVar* const var = vars_[index];
853 const int64 var_min = var->Min();
854 for (int card_index = 0; card_index < card_size(); ++card_index) {
855 if (undecided_.IsSet(index, card_index)) {
856 if (var_min == card_index) {
857 SetRevDoContribute(index, card_index);
858 } else {
859 SetRevCannotContribute(index, card_index);
860 }
861 }
862 }
863}
864
865void BoundedFastDistribute::OneDomain(int index) {
866 IntVar* const var = vars_[index];
867 const int64 oldmin = var->OldMin();
868 const int64 oldmax = var->OldMax();
869 const int64 vmin = var->Min();
870 const int64 vmax = var->Max();
871 for (int64 card_index = std::max(oldmin, int64{0});
872 card_index < std::min(vmin, card_size()); ++card_index) {
873 if (undecided_.IsSet(index, card_index)) {
874 SetRevCannotContribute(index, card_index);
875 }
876 }
877 for (const int64 card_index : InitAndGetValues(holes_[index])) {
878 if (card_index >= 0 && card_index < card_size() &&
879 undecided_.IsSet(index, card_index)) {
880 SetRevCannotContribute(index, card_index);
881 }
882 }
883 for (int64 card_index = std::max(vmax + 1, int64{0});
884 card_index <= std::min(oldmax, card_size() - 1); ++card_index) {
885 if (undecided_.IsSet(index, card_index)) {
886 SetRevCannotContribute(index, card_index);
887 }
888 }
889}
890
891void BoundedFastDistribute::CountVar(int card_index) {
892 const int64 stored_min = min_[card_index];
893 const int64 stored_max = max_[card_index];
894 if (card_min_[card_index] > stored_max ||
895 card_max_[card_index] < stored_min) {
896 solver()->Fail();
897 }
898 if (card_min_[card_index] == stored_max) {
899 CardMax(card_index);
900 }
901 if (card_max_[card_index] == stored_min) {
902 CardMin(card_index);
903 }
904}
905
906void BoundedFastDistribute::CardMin(int card_index) {
907 for (int var_index = 0; var_index < var_size(); ++var_index) {
908 if (undecided_.IsSet(var_index, card_index)) {
909 vars_[var_index]->RemoveValue(card_index);
910 }
911 }
912}
913
914void BoundedFastDistribute::CardMax(int card_index) {
915 for (int var_index = 0; var_index < var_size(); ++var_index) {
916 if (undecided_.IsSet(var_index, card_index)) {
917 vars_[var_index]->SetValue(card_index);
918 }
919 }
920}
921
922// ----- SetAllToZero -----
923
924class SetAllToZero : public Constraint {
925 public:
926 SetAllToZero(Solver* const s, const std::vector<IntVar*>& vars)
927 : Constraint(s), vars_(vars) {}
928
929 ~SetAllToZero() override {}
930
931 void Post() override {}
932
933 void InitialPropagate() override {
934 for (int i = 0; i < vars_.size(); ++i) {
935 vars_[i]->SetValue(0);
936 }
937 }
938
939 std::string DebugString() const override { return "SetAllToZero()"; }
940
941 void Accept(ModelVisitor* const visitor) const override {
942 visitor->BeginVisitConstraint(ModelVisitor::kDistribute, this);
943 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCardsArgument,
944 vars_);
945 visitor->EndVisitConstraint(ModelVisitor::kDistribute, this);
946 }
947
948 private:
949 const std::vector<IntVar*> vars_;
950};
951} // namespace
952
953// ----- Factory -----
954
955Constraint* Solver::MakeAtMost(std::vector<IntVar*> vars, int64 value,
956 int64 max_count) {
957 CHECK_GE(max_count, 0);
958 if (max_count >= vars.size()) {
959 return MakeTrueConstraint();
960 }
961 return RevAlloc(new AtMost(this, std::move(vars), value, max_count));
962}
963
964Constraint* Solver::MakeDistribute(const std::vector<IntVar*>& vars,
965 const std::vector<int64>& values,
966 const std::vector<IntVar*>& cards) {
967 if (vars.empty()) {
968 return RevAlloc(new SetAllToZero(this, cards));
969 }
970 CHECK_EQ(values.size(), cards.size());
971 for (IntVar* const var : vars) {
972 CHECK_EQ(this, var->solver());
973 }
974
975 // TODO(user) : we can sort values (and cards) before doing the test.
976 bool fast = true;
977 for (int i = 0; i < values.size(); ++i) {
978 if (values[i] != i) {
979 fast = false;
980 break;
981 }
982 }
983 for (IntVar* const card : cards) {
984 CHECK_EQ(this, card->solver());
985 }
986 if (fast) {
987 return RevAlloc(new FastDistribute(this, vars, cards));
988 } else {
989 return RevAlloc(new Distribute(this, vars, values, cards));
990 }
991}
992
993Constraint* Solver::MakeDistribute(const std::vector<IntVar*>& vars,
994 const std::vector<int>& values,
995 const std::vector<IntVar*>& cards) {
996 return MakeDistribute(vars, ToInt64Vector(values), cards);
997}
998
999Constraint* Solver::MakeDistribute(const std::vector<IntVar*>& vars,
1000 const std::vector<IntVar*>& cards) {
1001 if (vars.empty()) {
1002 return RevAlloc(new SetAllToZero(this, cards));
1003 }
1004 for (IntVar* const var : vars) {
1005 CHECK_EQ(this, var->solver());
1006 }
1007 for (IntVar* const card : cards) {
1008 CHECK_EQ(this, card->solver());
1009 }
1010 return RevAlloc(new FastDistribute(this, vars, cards));
1011}
1012
1013Constraint* Solver::MakeDistribute(const std::vector<IntVar*>& vars,
1014 int64 card_min, int64 card_max,
1015 int64 card_size) {
1016 const int vsize = vars.size();
1017 CHECK_NE(vsize, 0);
1018 for (IntVar* const var : vars) {
1019 CHECK_EQ(this, var->solver());
1020 }
1021 if (card_min == 0 && card_max >= vsize) {
1022 return MakeTrueConstraint();
1023 } else if (card_min > vsize || card_max < 0 || card_max < card_min) {
1024 return MakeFalseConstraint();
1025 } else {
1026 std::vector<int64> mins(card_size, card_min);
1027 std::vector<int64> maxes(card_size, card_max);
1028 return RevAlloc(new BoundedFastDistribute(this, vars, mins, maxes));
1029 }
1030}
1031
1032Constraint* Solver::MakeDistribute(const std::vector<IntVar*>& vars,
1033 const std::vector<int64>& card_min,
1034 const std::vector<int64>& card_max) {
1035 const int vsize = vars.size();
1036 CHECK_NE(vsize, 0);
1037 int64 cmax = kint64max;
1038 int64 cmin = kint64min;
1039 for (int i = 0; i < card_max.size(); ++i) {
1040 cmax = std::min(cmax, card_max[i]);
1041 cmin = std::max(cmin, card_min[i]);
1042 }
1043 if (cmax < 0 || cmin > vsize) {
1044 return MakeFalseConstraint();
1045 } else if (cmax >= vsize && cmin == 0) {
1046 return MakeTrueConstraint();
1047 } else {
1048 return RevAlloc(new BoundedFastDistribute(this, vars, card_min, card_max));
1049 }
1050}
1051
1052Constraint* Solver::MakeDistribute(const std::vector<IntVar*>& vars,
1053 const std::vector<int>& card_min,
1054 const std::vector<int>& card_max) {
1055 return MakeDistribute(vars, ToInt64Vector(card_min), ToInt64Vector(card_max));
1056}
1057
1058Constraint* Solver::MakeDistribute(const std::vector<IntVar*>& vars,
1059 const std::vector<int64>& values,
1060 const std::vector<int64>& card_min,
1061 const std::vector<int64>& card_max) {
1062 CHECK_NE(vars.size(), 0);
1063 CHECK_EQ(card_min.size(), values.size());
1064 CHECK_EQ(card_min.size(), card_max.size());
1065 if (AreAllOnes(card_min) && AreAllOnes(card_max) &&
1066 values.size() == vars.size() && IsIncreasingContiguous(values) &&
1067 IsArrayInRange(vars, values.front(), values.back())) {
1068 return MakeAllDifferent(vars);
1069 } else {
1070 return RevAlloc(
1071 new BoundedDistribute(this, vars, values, card_min, card_max));
1072 }
1073}
1074
1075Constraint* Solver::MakeDistribute(const std::vector<IntVar*>& vars,
1076 const std::vector<int>& values,
1077 const std::vector<int>& card_min,
1078 const std::vector<int>& card_max) {
1079 return MakeDistribute(vars, ToInt64Vector(values), ToInt64Vector(card_min),
1080 ToInt64Vector(card_max));
1081}
1082} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
const std::vector< IntVar * > vars_
Definition: alldiff_cst.cc:43
int64 max
Definition: alldiff_cst.cc:139
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
A constraint is the main modeling object.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual int64 Max() const =0
virtual int64 Min() const =0
The class IntVar is a subset of IntExpr.
virtual int64 OldMax() const =0
Returns the previous max.
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
virtual bool Contains(int64 v) const =0
This method returns whether the value 'v' is in the domain of the variable.
virtual void WhenDomain(Demon *d)=0
This method attaches a demon that will watch any domain modification of the domain of the variable.
virtual int64 OldMin() const =0
Returns the previous min.
bool IsSet(int64 row, int64 column) const
Returns whether the 'column' bit in the 'row' row is set.
void SetToOne(Solver *const solver, int64 row, int64 column)
Sets the 'column' bit in the 'row' row.
Definition: utilities.cc:167
void SetToZero(Solver *const solver, int64 row, int64 column)
Erases the 'column' bit in the 'row' row.
Definition: utilities.cc:175
Constraint * MakeFalseConstraint()
This constraint always fails.
Definition: constraints.cc:520
IntVar * MakeIsEqualCstVar(IntExpr *const var, int64 value)
status var of (var == value)
Definition: expr_cst.cc:460
Constraint * MakeTrueConstraint()
This constraint always succeeds.
Definition: constraints.cc:515
Constraint * MakeDistribute(const std::vector< IntVar * > &vars, const std::vector< int64 > &values, const std::vector< IntVar * > &cards)
Aggregated version of count: |{i | v[i] == values[j]}| == cards[j].
Definition: count_cst.cc:964
Constraint * MakeAtMost(std::vector< IntVar * > vars, int64 value, int64 max_count)
|{i | vars[i] == value}| <= max_count
Definition: count_cst.cc:955
Constraint * MakeSumEquality(const std::vector< IntVar * > &vars, int64 cst)
Definition: expr_array.cc:3428
Constraint * MakeCount(const std::vector< IntVar * > &vars, int64 value, int64 max_count)
|{i | vars[i] == value}| == max_count
Definition: count_cst.cc:30
Constraint * MakeAllDifferent(const std::vector< IntVar * > &vars)
All variables are pairwise different.
Definition: alldiff_cst.cc:690
IntExpr * MakeSum(IntExpr *const left, IntExpr *const right)
left + right.
T * RevAlloc(T *object)
Registers the given object as being reversible.
std::vector< IntVarIterator * > holes_
int64 value
IntVar * var
Definition: expr_array.cc:1858
static const int64 kint64max
int64_t int64
static const int64 kint64min
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool IsArrayInRange(const std::vector< IntVar * > &vars, T range_min, T range_max)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
bool IsIncreasingContiguous(const std::vector< T > &values)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:45
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
Definition: utilities.cc:822
bool AreAllOnes(const std::vector< T > &values)
STL namespace.
int index
Definition: pack.cc:508