Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
table.cc
Go to the documentation of this file.
1// Copyright 2010-2024 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// This file implements the table constraints.
16
17#include <algorithm>
18#include <cstdint>
19#include <limits>
20#include <memory>
21#include <string>
22#include <vector>
23
24#include "absl/container/flat_hash_map.h"
25#include "absl/log/check.h"
26#include "absl/strings/str_format.h"
27#include "absl/strings/str_join.h"
28#include "absl/types/span.h"
31#include "ortools/util/bitset.h"
34
35namespace operations_research {
36namespace {
37// ----- Presolve helpers -----
38// TODO(user): Move this out of this file.
39struct AffineTransformation { // y == a*x + b.
40 AffineTransformation() : a(1), b(0) {}
41 AffineTransformation(int64_t aa, int64_t bb) : a(aa), b(bb) {
42 CHECK_NE(a, 0);
43 }
44 int64_t a;
45 int64_t b;
46
47 bool Reverse(int64_t value, int64_t* const reverse) const {
48 const int64_t temp = value - b;
49 if (temp % a == 0) {
50 *reverse = temp / a;
51 DCHECK_EQ(Forward(*reverse), value);
52 return true;
53 } else {
54 return false;
55 }
56 }
57
58 int64_t Forward(int64_t value) const { return value * a + b; }
59
60 int64_t UnsafeReverse(int64_t value) const { return (value - b) / a; }
61
62 void Clear() {
63 a = 1;
64 b = 0;
65 }
66
67 std::string DebugString() const {
68 return absl::StrFormat("(%d * x + %d)", a, b);
69 }
70};
71
72// TODO(user): Move this out too.
73class VarLinearizer : public ModelParser {
74 public:
75 VarLinearizer() : target_var_(nullptr), transformation_(nullptr) {}
76 ~VarLinearizer() override {}
77
78 void VisitIntegerVariable(const IntVar* const variable,
79 const std::string& operation, int64_t value,
80 IntVar* const delegate) override {
81 if (operation == ModelVisitor::kSumOperation) {
82 AddConstant(value);
83 delegate->Accept(this);
84 } else if (operation == ModelVisitor::kDifferenceOperation) {
85 AddConstant(value);
86 PushMultiplier(-1);
87 delegate->Accept(this);
88 PopMultiplier();
89 } else if (operation == ModelVisitor::kProductOperation) {
90 PushMultiplier(value);
91 delegate->Accept(this);
92 PopMultiplier();
93 } else if (operation == ModelVisitor::kTraceOperation) {
94 *target_var_ = const_cast<IntVar*>(variable);
95 transformation_->a = multipliers_.back();
96 }
97 }
98
99 void VisitIntegerVariable(const IntVar* const variable,
100 IntExpr* const delegate) override {
101 *target_var_ = const_cast<IntVar*>(variable);
102 transformation_->a = multipliers_.back();
103 }
104
105 void Visit(const IntVar* const var, IntVar** const target_var,
106 AffineTransformation* const transformation) {
107 target_var_ = target_var;
108 transformation_ = transformation;
109 transformation->Clear();
110 PushMultiplier(1);
111 var->Accept(this);
112 PopMultiplier();
113 CHECK(multipliers_.empty());
114 }
115
116 std::string DebugString() const override { return "VarLinearizer"; }
117
118 private:
119 void AddConstant(int64_t constant) {
120 transformation_->b += constant * multipliers_.back();
121 }
122
123 void PushMultiplier(int64_t multiplier) {
124 if (multipliers_.empty()) {
125 multipliers_.push_back(multiplier);
126 } else {
127 multipliers_.push_back(multiplier * multipliers_.back());
128 }
129 }
130
131 void PopMultiplier() { multipliers_.pop_back(); }
132
133 std::vector<int64_t> multipliers_;
134 IntVar** target_var_;
135 AffineTransformation* transformation_;
136};
137
138static const int kBitsInUint64 = 64;
139
140// ----- Positive Table Constraint -----
141
142// Structure of the constraint:
143
144// Tuples are indexed, we maintain a bitset for active tuples.
145
146// For each var and each value, we maintain a bitset mask of tuples
147// containing this value for this variable.
148
149// Propagation: When a value is removed, blank all active tuples using the
150// var-value mask.
151// Then we scan all other variable/values to see if there is an active
152// tuple that supports it.
153
154class BasePositiveTableConstraint : public Constraint {
155 public:
156 BasePositiveTableConstraint(Solver* const s, const std::vector<IntVar*>& vars,
157 const IntTupleSet& tuples)
158 : Constraint(s),
159 tuple_count_(tuples.NumTuples()),
160 arity_(vars.size()),
161 vars_(arity_),
162 holes_(arity_),
163 iterators_(arity_),
164 tuples_(tuples),
165 transformations_(arity_) {
166 // This constraint is intensive on domain and holes iterations on
167 // variables. Thus we can visit all variables to get to the
168 // boolean or domain int var beneath it. Then we can reverse
169 // process the tupleset to move in parallel to the simplifications
170 // of the variables. This way, we can keep the memory efficient
171 // nature of shared tuplesets (especially important for
172 // transitions constraints which are a chain of table
173 // constraints). The cost in running time is small as the tuples
174 // are read only once to construct the bitset data structures.
175 VarLinearizer linearizer;
176 for (int i = 0; i < arity_; ++i) {
177 linearizer.Visit(vars[i], &vars_[i], &transformations_[i]);
178 }
179 // Create hole iterators
180 for (int i = 0; i < arity_; ++i) {
181 holes_[i] = vars_[i]->MakeHoleIterator(true);
182 iterators_[i] = vars_[i]->MakeDomainIterator(true);
183 }
184 }
185
186 ~BasePositiveTableConstraint() override {}
187
188 std::string DebugString() const override {
189 return absl::StrFormat("AllowedAssignments(arity = %d, tuple_count = %d)",
190 arity_, tuple_count_);
191 }
192
193 void Accept(ModelVisitor* const visitor) const override {
194 visitor->BeginVisitConstraint(ModelVisitor::kAllowedAssignments, this);
195 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
196 vars_);
197 visitor->VisitIntegerMatrixArgument(ModelVisitor::kTuplesArgument, tuples_);
198 visitor->EndVisitConstraint(ModelVisitor::kAllowedAssignments, this);
199 }
200
201 protected:
202 bool TupleValue(int tuple_index, int var_index, int64_t* const value) const {
203 return transformations_[var_index].Reverse(
204 tuples_.Value(tuple_index, var_index), value);
205 }
206
207 int64_t UnsafeTupleValue(int tuple_index, int var_index) const {
208 return transformations_[var_index].UnsafeReverse(
209 tuples_.Value(tuple_index, var_index));
210 }
211
212 bool IsTupleSupported(int tuple_index) {
213 for (int var_index = 0; var_index < arity_; ++var_index) {
214 int64_t value = 0;
215 if (!TupleValue(tuple_index, var_index, &value) ||
216 !vars_[var_index]->Contains(value)) {
217 return false;
218 }
219 }
220 return true;
221 }
222
223 const int tuple_count_;
224 const int arity_;
225 std::vector<IntVar*> vars_;
226 std::vector<IntVarIterator*> holes_;
227 std::vector<IntVarIterator*> iterators_;
228 std::vector<int64_t> to_remove_;
229
230 private:
231 // All allowed tuples.
232 const IntTupleSet tuples_;
233 // The set of affine transformations that describe the
234 // simplification of the variables.
235 std::vector<AffineTransformation> transformations_;
236};
237
238class PositiveTableConstraint : public BasePositiveTableConstraint {
239 public:
240 typedef absl::flat_hash_map<int, std::vector<uint64_t>> ValueBitset;
241
242 PositiveTableConstraint(Solver* const s, const std::vector<IntVar*>& vars,
243 const IntTupleSet& tuples)
244 : BasePositiveTableConstraint(s, vars, tuples),
245 word_length_(BitLength64(tuples.NumTuples())),
246 active_tuples_(tuples.NumTuples()) {}
247
248 ~PositiveTableConstraint() override {}
249
250 void Post() override {
252 solver(), this, &PositiveTableConstraint::Propagate, "Propagate");
253 for (int i = 0; i < arity_; ++i) {
254 vars_[i]->WhenDomain(d);
255 Demon* u = MakeConstraintDemon1(
256 solver(), this, &PositiveTableConstraint::Update, "Update", i);
257 vars_[i]->WhenDomain(u);
258 }
259 // Initialize masks.
260 masks_.clear();
261 masks_.resize(arity_);
262 for (int i = 0; i < tuple_count_; ++i) {
263 InitializeMask(i);
264 }
265 // Initialize the active tuple bitset.
266 std::vector<uint64_t> actives(word_length_, 0);
267 for (int tuple_index = 0; tuple_index < tuple_count_; ++tuple_index) {
268 if (IsTupleSupported(tuple_index)) {
269 SetBit64(actives.data(), tuple_index);
270 }
271 }
272 active_tuples_.Init(solver(), actives);
273 }
274
275 void InitialPropagate() override {
276 // Build active_ structure.
277 for (int var_index = 0; var_index < arity_; ++var_index) {
278 for (const auto& it : masks_[var_index]) {
279 if (!vars_[var_index]->Contains(it.first)) {
280 active_tuples_.RevSubtract(solver(), it.second);
281 }
282 }
283 }
284 if (active_tuples_.Empty()) {
285 solver()->Fail();
286 }
287 // Remove unreached values.
288 for (int var_index = 0; var_index < arity_; ++var_index) {
289 const ValueBitset& mask = masks_[var_index];
290 IntVar* const var = vars_[var_index];
291 to_remove_.clear();
292 for (const int64_t value : InitAndGetValues(iterators_[var_index])) {
293 if (!mask.contains(value)) {
294 to_remove_.push_back(value);
295 }
296 }
297 if (!to_remove_.empty()) {
298 var->RemoveValues(to_remove_);
299 }
300 }
301 }
302
303 void Propagate() {
304 for (int var_index = 0; var_index < arity_; ++var_index) {
305 IntVar* const var = vars_[var_index];
306 to_remove_.clear();
307 for (const int64_t value : InitAndGetValues(iterators_[var_index])) {
308 if (!Supported(var_index, value)) {
309 to_remove_.push_back(value);
310 }
311 }
312 if (!to_remove_.empty()) {
313 var->RemoveValues(to_remove_);
314 }
315 }
316 }
317
318 void Update(int index) {
319 const ValueBitset& var_masks = masks_[index];
320 IntVar* const var = vars_[index];
321 const int64_t old_max = var->OldMax();
322 const int64_t vmin = var->Min();
323 const int64_t vmax = var->Max();
324 for (int64_t value = var->OldMin(); value < vmin; ++value) {
325 const auto& it = var_masks.find(value);
326 if (it != var_masks.end()) {
327 BlankActives(it->second);
328 }
329 }
330 for (const int64_t value : InitAndGetValues(holes_[index])) {
331 const auto& it = var_masks.find(value);
332 if (it != var_masks.end()) {
333 BlankActives(it->second);
334 }
335 }
336 for (int64_t value = vmax + 1; value <= old_max; ++value) {
337 const auto& it = var_masks.find(value);
338 if (it != var_masks.end()) {
339 BlankActives(it->second);
340 }
341 }
342 }
343
344 void BlankActives(const std::vector<uint64_t>& mask) {
345 if (!mask.empty()) {
346 active_tuples_.RevSubtract(solver(), mask);
347 if (active_tuples_.Empty()) {
348 solver()->Fail();
349 }
350 }
351 }
352
353 bool Supported(int var_index, int64_t value) {
354 DCHECK_GE(var_index, 0);
355 DCHECK_LT(var_index, arity_);
356 DCHECK(masks_[var_index].contains(value));
357 const std::vector<uint64_t>& mask = masks_[var_index][value];
358 int tmp = 0;
359 return active_tuples_.Intersects(mask, &tmp);
360 }
361
362 std::string DebugString() const override {
363 return absl::StrFormat("PositiveTableConstraint([%s], %d tuples)",
365 }
366
367 protected:
368 void InitializeMask(int tuple_index) {
369 std::vector<int64_t> cache(arity_);
370 for (int var_index = 0; var_index < arity_; ++var_index) {
371 if (!TupleValue(tuple_index, var_index, &cache[var_index])) {
372 return;
373 }
374 }
375 for (int var_index = 0; var_index < arity_; ++var_index) {
376 const int64_t value = cache[var_index];
377 std::vector<uint64_t>& mask = masks_[var_index][value];
378 if (mask.empty()) {
379 mask.assign(word_length_, 0);
380 }
381 SetBit64(mask.data(), tuple_index);
382 }
383 }
384
385 const int word_length_;
386 UnsortedNullableRevBitset active_tuples_;
387 std::vector<ValueBitset> masks_;
388 std::vector<uint64_t> temp_mask_;
389};
390
391// ----- Compact Tables -----
392
393class CompactPositiveTableConstraint : public BasePositiveTableConstraint {
394 public:
395 CompactPositiveTableConstraint(Solver* const s,
396 const std::vector<IntVar*>& vars,
397 const IntTupleSet& tuples)
398 : BasePositiveTableConstraint(s, vars, tuples),
399 word_length_(BitLength64(tuples.NumTuples())),
400 active_tuples_(tuples.NumTuples()),
401 masks_(arity_),
402 mask_starts_(arity_),
403 mask_ends_(arity_),
404 original_min_(arity_, 0),
407 demon_(nullptr),
408 touched_var_(-1),
409 var_sizes_(arity_, 0) {}
410
411 ~CompactPositiveTableConstraint() override {}
412
413 void Post() override {
414 demon_ = solver()->RegisterDemon(MakeDelayedConstraintDemon0(
415 solver(), this, &CompactPositiveTableConstraint::Propagate,
416 "Propagate"));
417 for (int i = 0; i < arity_; ++i) {
418 Demon* const u = MakeConstraintDemon1(
419 solver(), this, &CompactPositiveTableConstraint::Update, "Update", i);
420 vars_[i]->WhenDomain(u);
421 }
422 for (int i = 0; i < arity_; ++i) {
423 var_sizes_.SetValue(solver(), i, vars_[i]->Size());
424 }
425 }
426
427 void InitialPropagate() override {
428 BuildMasks();
429 FillMasksAndActiveTuples();
430 ComputeMasksBoundaries();
431 BuildSupports();
432 RemoveUnsupportedValues();
433 }
434
435 // ----- Propagation -----
436
437 void Propagate() {
438 // Reset touch_var_ if in mode (more than 1 variable was modified).
439 if (touched_var_ == -2) {
440 touched_var_ = -1;
441 }
442 // This methods scans all values of all variables to see if they
443 // are still supported.
444 // This method is not attached to any particular variable, but is pushed
445 // at a delayed priority after Update(var_index) is called.
446 for (int var_index = 0; var_index < arity_; ++var_index) {
447 // This demons runs in low priority. Thus we know all the
448 // variables that have changed since the last time it was run.
449 // In that case, if only one var was touched, as propagation is
450 // exact, we do not need to recheck that variable.
451 if (var_index == touched_var_) {
452 touched_var_ = -1; // Clean now, it is a 1 time flag.
453 continue;
454 }
455 IntVar* const var = vars_[var_index];
456 const int64_t original_min = original_min_[var_index];
457 const int64_t var_size = var->Size();
458 // The domain iterator is very slow, let's try to see if we can
459 // work our way around.
460 switch (var_size) {
461 case 1: {
462 if (!Supported(var_index, var->Min() - original_min)) {
463 solver()->Fail();
464 }
465 break;
466 }
467 case 2: {
468 const int64_t var_min = var->Min();
469 const int64_t var_max = var->Max();
470 const bool min_support = Supported(var_index, var_min - original_min);
471 const bool max_support = Supported(var_index, var_max - original_min);
472 if (!min_support) {
473 if (!max_support) {
474 solver()->Fail();
475 } else {
476 var->SetValue(var_max);
477 var_sizes_.SetValue(solver(), var_index, 1);
478 }
479 } else if (!max_support) {
480 var->SetValue(var_min);
481 var_sizes_.SetValue(solver(), var_index, 1);
482 }
483 break;
484 }
485 default: {
486 to_remove_.clear();
487 const int64_t var_min = var->Min();
488 const int64_t var_max = var->Max();
489 int64_t new_min = var_min;
490 int64_t new_max = var_max;
491 // If the domain of a variable is an interval, it is much
492 // faster to iterate on that interval instead of using the
493 // iterator.
494 if (var_max - var_min + 1 == var_size) {
495 for (; new_min <= var_max; ++new_min) {
496 if (Supported(var_index, new_min - original_min)) {
497 break;
498 }
499 }
500 for (; new_max >= new_min; --new_max) {
501 if (Supported(var_index, new_max - original_min)) {
502 break;
503 }
504 }
505 var->SetRange(new_min, new_max);
506 for (int64_t value = new_min + 1; value < new_max; ++value) {
507 if (!Supported(var_index, value - original_min)) {
508 to_remove_.push_back(value);
509 }
510 }
511 } else { // Domain is sparse.
512 // Let's not collect all values below the first supported
513 // value as this can easily and more rapidly be taken care
514 // of by a SetRange() call.
515 new_min = std::numeric_limits<int64_t>::max(); // escape value.
516 for (const int64_t value :
517 InitAndGetValues(iterators_[var_index])) {
518 if (!Supported(var_index, value - original_min)) {
519 to_remove_.push_back(value);
520 } else {
521 if (new_min == std::numeric_limits<int64_t>::max()) {
522 new_min = value;
523 // This will be covered by the SetRange.
524 to_remove_.clear();
525 }
526 new_max = value;
527 }
528 }
529 var->SetRange(new_min, new_max);
530 // Trim the to_remove vector.
531 int index = to_remove_.size() - 1;
532 while (index >= 0 && to_remove_[index] > new_max) {
533 index--;
534 }
535 to_remove_.resize(index + 1);
536 }
537 var->RemoveValues(to_remove_);
538 var_sizes_.SetValue(solver(), var_index, var->Size());
539 }
540 }
541 }
542 }
543
544 void Update(int var_index) {
545 if (vars_[var_index]->Size() == var_sizes_.Value(var_index)) {
546 return;
547 }
548 // This method will update the set of active tuples by masking out all
549 // tuples attached to values of the variables that have been removed.
550
551 // We first collect the complete set of tuples to blank out in temp_mask_.
552 IntVar* const var = vars_[var_index];
553 bool changed = false;
554 const int64_t omin = original_min_[var_index];
555 const int64_t var_size = var->Size();
556 const int64_t var_min = var->Min();
557 const int64_t var_max = var->Max();
558
559 switch (var_size) {
560 case 1: {
561 changed = AndMaskWithActive(masks_[var_index][var_min - omin]);
562 break;
563 }
564 case 2: {
565 SetTempMask(var_index, var_min - omin);
566 OrTempMask(var_index, var_max - omin);
567 changed = AndMaskWithActive(temp_mask_);
568 break;
569 }
570 default: {
571 const int64_t estimated_hole_size =
572 var_sizes_.Value(var_index) - var_size;
573 const int64_t old_min = var->OldMin();
574 const int64_t old_max = var->OldMax();
575 // Rough estimation of the number of operation if we scan
576 // deltas in the domain of the variable.
577 const int64_t number_of_operations =
578 estimated_hole_size + var_min - old_min + old_max - var_max;
579 if (number_of_operations < var_size) {
580 // Let's scan the removed values since last run.
581 for (int64_t value = old_min; value < var_min; ++value) {
582 changed |= SubtractMaskFromActive(masks_[var_index][value - omin]);
583 }
584 for (const int64_t value : InitAndGetValues(holes_[var_index])) {
585 changed |= SubtractMaskFromActive(masks_[var_index][value - omin]);
586 }
587 for (int64_t value = var_max + 1; value <= old_max; ++value) {
588 changed |= SubtractMaskFromActive(masks_[var_index][value - omin]);
589 }
590 } else {
591 ClearTempMask();
592 // Let's build the mask of supported tuples from the current
593 // domain.
594 if (var_max - var_min + 1 == var_size) { // Contiguous.
595 for (int64_t value = var_min; value <= var_max; ++value) {
596 OrTempMask(var_index, value - omin);
597 }
598 } else {
599 for (const int64_t value :
600 InitAndGetValues(iterators_[var_index])) {
601 OrTempMask(var_index, value - omin);
602 }
603 }
604 // Then we and this mask with active_tuples_.
605 changed = AndMaskWithActive(temp_mask_);
606 }
607 // We maintain the size of the variables incrementally (when it
608 // is > 2).
609 var_sizes_.SetValue(solver(), var_index, var_size);
610 }
611 }
612 // We push the propagate method only if something has changed.
613 if (changed) {
614 if (touched_var_ == -1 || touched_var_ == var_index) {
615 touched_var_ = var_index;
616 } else {
617 touched_var_ = -2; // more than one var.
618 }
619 EnqueueDelayedDemon(demon_);
620 }
621 }
622
623 std::string DebugString() const override {
624 return absl::StrFormat("CompactPositiveTableConstraint([%s], %d tuples)",
626 }
627
628 private:
629 // ----- Initialization -----
630
631 void BuildMasks() {
632 // Build masks.
633 for (int i = 0; i < arity_; ++i) {
634 original_min_[i] = vars_[i]->Min();
635 const int64_t span = vars_[i]->Max() - original_min_[i] + 1;
636 masks_[i].resize(span);
637 }
638 }
639
640 void FillMasksAndActiveTuples() {
641 std::vector<uint64_t> actives(word_length_, 0);
642 for (int tuple_index = 0; tuple_index < tuple_count_; ++tuple_index) {
643 if (IsTupleSupported(tuple_index)) {
644 SetBit64(actives.data(), tuple_index);
645 // Fill in all masks.
646 for (int var_index = 0; var_index < arity_; ++var_index) {
647 const int64_t value = UnsafeTupleValue(tuple_index, var_index);
648 const int64_t value_index = value - original_min_[var_index];
649 DCHECK_GE(value_index, 0);
650 DCHECK_LT(value_index, masks_[var_index].size());
651 if (masks_[var_index][value_index].empty()) {
652 masks_[var_index][value_index].assign(word_length_, 0);
653 }
654 SetBit64(masks_[var_index][value_index].data(), tuple_index);
655 }
656 }
657 }
658 active_tuples_.Init(solver(), actives);
659 }
660
661 void RemoveUnsupportedValues() {
662 // remove unreached values.
663 for (int var_index = 0; var_index < arity_; ++var_index) {
664 IntVar* const var = vars_[var_index];
665 to_remove_.clear();
666 for (const int64_t value : InitAndGetValues(iterators_[var_index])) {
667 if (masks_[var_index][value - original_min_[var_index]].empty()) {
668 to_remove_.push_back(value);
669 }
670 }
671 if (!to_remove_.empty()) {
672 var->RemoveValues(to_remove_);
673 }
674 }
675 }
676
677 void ComputeMasksBoundaries() {
678 for (int var_index = 0; var_index < arity_; ++var_index) {
679 mask_starts_[var_index].resize(masks_[var_index].size());
680 mask_ends_[var_index].resize(masks_[var_index].size());
681 for (int value_index = 0; value_index < masks_[var_index].size();
682 ++value_index) {
683 const std::vector<uint64_t>& mask = masks_[var_index][value_index];
684 if (mask.empty()) {
685 continue;
686 }
687 int start = 0;
688 while (start < word_length_ && mask[start] == 0) {
689 start++;
690 }
691 DCHECK_LT(start, word_length_);
692 int end = word_length_ - 1;
693 while (end > start && mask[end] == 0) {
694 end--;
695 }
696 DCHECK_LE(start, end);
697 DCHECK_NE(mask[start], 0);
698 DCHECK_NE(mask[end], 0);
699 mask_starts_[var_index][value_index] = start;
700 mask_ends_[var_index][value_index] = end;
701 }
702 }
703 }
704
705 void BuildSupports() {
706 for (int var_index = 0; var_index < arity_; ++var_index) {
707 supports_[var_index].resize(masks_[var_index].size());
708 }
709 }
710
711 // ----- Helpers during propagation -----
712
713 bool AndMaskWithActive(const std::vector<uint64_t>& mask) {
714 const bool result = active_tuples_.RevAnd(solver(), mask);
715 if (active_tuples_.Empty()) {
716 solver()->Fail();
717 }
718 return result;
719 }
720
721 bool SubtractMaskFromActive(const std::vector<uint64_t>& mask) {
722 const bool result = active_tuples_.RevSubtract(solver(), mask);
723 if (active_tuples_.Empty()) {
724 solver()->Fail();
725 }
726 return result;
727 }
728
729 bool Supported(int var_index, int64_t value_index) {
730 DCHECK_GE(var_index, 0);
731 DCHECK_LT(var_index, arity_);
732 DCHECK_GE(value_index, 0);
733 DCHECK_LT(value_index, masks_[var_index].size());
734 const std::vector<uint64_t>& mask = masks_[var_index][value_index];
735 DCHECK(!mask.empty());
736 return active_tuples_.Intersects(mask, &supports_[var_index][value_index]);
737 }
738
739 void OrTempMask(int var_index, int64_t value_index) {
740 const std::vector<uint64_t>& mask = masks_[var_index][value_index];
741 if (!mask.empty()) {
742 const int mask_span = mask_ends_[var_index][value_index] -
743 mask_starts_[var_index][value_index] + 1;
744 if (active_tuples_.ActiveWordSize() < mask_span) {
745 for (int i : active_tuples_.active_words()) {
746 temp_mask_[i] |= mask[i];
747 }
748 } else {
749 for (int i = mask_starts_[var_index][value_index];
750 i <= mask_ends_[var_index][value_index]; ++i) {
751 temp_mask_[i] |= mask[i];
752 }
753 }
754 }
755 }
756
757 void SetTempMask(int var_index, int64_t value_index) {
758 // We assume memset is much faster that looping and assigning.
759 // Still we do want to stay sparse if possible.
760 // Thus we switch between dense and sparse initialization by
761 // comparing the number of operations in both case, with constant factor.
762 // TODO(user): experiment with different constant values.
763 if (active_tuples_.ActiveWordSize() < word_length_ / 4) {
764 for (int i : active_tuples_.active_words()) {
765 temp_mask_[i] = masks_[var_index][value_index][i];
766 }
767 } else {
768 temp_mask_ = masks_[var_index][value_index];
769 }
770 }
771
772 void ClearTempMask() {
773 // See comment above.
774 if (active_tuples_.ActiveWordSize() < word_length_ / 4) {
775 for (int i : active_tuples_.active_words()) {
776 temp_mask_[i] = 0;
777 }
778 } else {
779 temp_mask_.assign(word_length_, 0);
780 }
781 }
782
783 // The length in 64 bit words of the number of tuples.
784 int64_t word_length_;
785 // The active bitset.
786 UnsortedNullableRevBitset active_tuples_;
787 // The masks per value per variable.
788 std::vector<std::vector<std::vector<uint64_t>>> masks_;
789 // The range of active indices in the masks.
790 std::vector<std::vector<int>> mask_starts_;
791 std::vector<std::vector<int>> mask_ends_;
792 // The min on the vars at creation time.
793 std::vector<int64_t> original_min_;
794 // A temporary mask use for computation.
795 std::vector<uint64_t> temp_mask_;
796 // The index of the word in the active bitset supporting each value per
797 // variable.
798 std::vector<std::vector<int>> supports_;
799 Demon* demon_;
800 int touched_var_;
801 RevArray<int64_t> var_sizes_;
802};
803
804// ----- Small Compact Table. -----
805
806// TODO(user): regroup code with CompactPositiveTableConstraint.
807
808class SmallCompactPositiveTableConstraint : public BasePositiveTableConstraint {
809 public:
810 SmallCompactPositiveTableConstraint(Solver* const s,
811 const std::vector<IntVar*>& vars,
812 const IntTupleSet& tuples)
813 : BasePositiveTableConstraint(s, vars, tuples),
815 stamp_(0),
816 masks_(arity_),
817 original_min_(arity_, 0),
818 demon_(nullptr),
819 touched_var_(-1) {
820 CHECK_GE(tuple_count_, 0);
821 CHECK_GE(arity_, 0);
822 CHECK_LE(tuples.NumTuples(), kBitsInUint64);
823 }
824
825 ~SmallCompactPositiveTableConstraint() override {}
826
827 void Post() override {
828 demon_ = solver()->RegisterDemon(MakeDelayedConstraintDemon0(
829 solver(), this, &SmallCompactPositiveTableConstraint::Propagate,
830 "Propagate"));
831 for (int i = 0; i < arity_; ++i) {
832 if (!vars_[i]->Bound()) {
833 Demon* const update_demon = MakeConstraintDemon1(
834 solver(), this, &SmallCompactPositiveTableConstraint::Update,
835 "Update", i);
836 vars_[i]->WhenDomain(update_demon);
837 }
838 }
839 stamp_ = 0;
840 }
841
842 void InitMasks() {
843 // Build masks.
844 for (int i = 0; i < arity_; ++i) {
845 original_min_[i] = vars_[i]->Min();
846 const int64_t span = vars_[i]->Max() - original_min_[i] + 1;
847 masks_[i].assign(span, 0);
848 }
849 }
850
851 bool IsTupleSupported(int tuple_index) {
852 for (int var_index = 0; var_index < arity_; ++var_index) {
853 int64_t value = 0;
854 if (!TupleValue(tuple_index, var_index, &value) ||
855 !vars_[var_index]->Contains(value)) {
856 return false;
857 }
858 }
859 return true;
860 }
861
862 void ComputeActiveTuples() {
863 active_tuples_ = 0;
864 // Compute active_tuples_ and update masks.
865 for (int tuple_index = 0; tuple_index < tuple_count_; ++tuple_index) {
866 if (IsTupleSupported(tuple_index)) {
867 const uint64_t local_mask = OneBit64(tuple_index);
868 active_tuples_ |= local_mask;
869 for (int var_index = 0; var_index < arity_; ++var_index) {
870 const int64_t value = UnsafeTupleValue(tuple_index, var_index);
871 masks_[var_index][value - original_min_[var_index]] |= local_mask;
872 }
873 }
874 }
875 if (!active_tuples_) {
876 solver()->Fail();
877 }
878 }
879
880 void RemoveUnsupportedValues() {
881 // remove unreached values.
882 for (int var_index = 0; var_index < arity_; ++var_index) {
883 IntVar* const var = vars_[var_index];
884 const int64_t original_min = original_min_[var_index];
885 to_remove_.clear();
886 for (const int64_t value : InitAndGetValues(iterators_[var_index])) {
887 if (masks_[var_index][value - original_min] == 0) {
888 to_remove_.push_back(value);
889 }
890 }
891 if (!to_remove_.empty()) {
892 var->RemoveValues(to_remove_);
893 }
894 }
895 }
896
897 void InitialPropagate() override {
898 InitMasks();
899 ComputeActiveTuples();
900 RemoveUnsupportedValues();
901 }
902
903 void Propagate() {
904 // This methods scans all the values of all the variables to see if they
905 // are still supported.
906 // This method is not attached to any particular variable, but is pushed
907 // at a delayed priority and awakened by Update(var_index).
908
909 // Reset touch_var_ if in mode (more than 1 variable was modified).
910 if (touched_var_ == -2) {
911 touched_var_ = -1;
912 }
913
914 // We cache active_tuples_.
915 const uint64_t actives = active_tuples_;
916
917 // We scan all variables and check their domains.
918 for (int var_index = 0; var_index < arity_; ++var_index) {
919 // This demons runs in low priority. Thus we know all the
920 // variables that have changed since the last time it was run.
921 // In that case, if only one var was touched, as propagation is
922 // exact, we do not need to recheck that variable.
923 if (var_index == touched_var_) {
924 touched_var_ = -1; // Clean it, it is a one time flag.
925 continue;
926 }
927 const std::vector<uint64_t>& var_mask = masks_[var_index];
928 const int64_t original_min = original_min_[var_index];
929 IntVar* const var = vars_[var_index];
930 const int64_t var_size = var->Size();
931 switch (var_size) {
932 case 1: {
933 if ((var_mask[var->Min() - original_min] & actives) == 0) {
934 // The difference with the non-small version of the table
935 // is that checking the validity of the resulting active
936 // tuples is cheap. Therefore we do not delay the check
937 // code.
938 solver()->Fail();
939 }
940 break;
941 }
942 case 2: {
943 const int64_t var_min = var->Min();
944 const int64_t var_max = var->Max();
945 const bool min_support =
946 (var_mask[var_min - original_min] & actives) != 0;
947 const bool max_support =
948 (var_mask[var_max - original_min] & actives) != 0;
949 if (!min_support && !max_support) {
950 solver()->Fail();
951 } else if (!min_support) {
952 var->SetValue(var_max);
953 } else if (!max_support) {
954 var->SetValue(var_min);
955 }
956 break;
957 }
958 default: {
959 to_remove_.clear();
960 const int64_t var_min = var->Min();
961 const int64_t var_max = var->Max();
962 int64_t new_min = var_min;
963 int64_t new_max = var_max;
964 if (var_max - var_min + 1 == var_size) {
965 // Contiguous case.
966 for (; new_min <= var_max; ++new_min) {
967 if ((var_mask[new_min - original_min] & actives) != 0) {
968 break;
969 }
970 }
971 for (; new_max >= new_min; --new_max) {
972 if ((var_mask[new_max - original_min] & actives) != 0) {
973 break;
974 }
975 }
976 var->SetRange(new_min, new_max);
977 for (int64_t value = new_min + 1; value < new_max; ++value) {
978 if ((var_mask[value - original_min] & actives) == 0) {
979 to_remove_.push_back(value);
980 }
981 }
982 } else {
983 bool min_set = false;
984 int last_size = 0;
985 for (const int64_t value :
986 InitAndGetValues(iterators_[var_index])) {
987 // The iterator is not safe w.r.t. deletion. Thus we
988 // postpone all value removals.
989 if ((var_mask[value - original_min] & actives) == 0) {
990 if (min_set) {
991 to_remove_.push_back(value);
992 }
993 } else {
994 if (!min_set) {
995 new_min = value;
996 min_set = true;
997 }
998 new_max = value;
999 last_size = to_remove_.size();
1000 }
1001 }
1002 if (min_set) {
1003 var->SetRange(new_min, new_max);
1004 } else {
1005 solver()->Fail();
1006 }
1007 to_remove_.resize(last_size);
1008 }
1009 var->RemoveValues(to_remove_);
1010 }
1011 }
1012 }
1013 }
1014
1015 void Update(int var_index) {
1016 // This method updates the set of active tuples by masking out all
1017 // tuples attached to values of the variables that have been removed.
1018
1019 IntVar* const var = vars_[var_index];
1020 const int64_t original_min = original_min_[var_index];
1021 const int64_t var_size = var->Size();
1022 switch (var_size) {
1023 case 1: {
1024 ApplyMask(var_index, masks_[var_index][var->Min() - original_min]);
1025 return;
1026 }
1027 case 2: {
1028 ApplyMask(var_index, masks_[var_index][var->Min() - original_min] |
1029 masks_[var_index][var->Max() - original_min]);
1030 return;
1031 }
1032 default: {
1033 // We first collect the complete set of tuples to blank out in
1034 // temp_mask.
1035 const std::vector<uint64_t>& var_mask = masks_[var_index];
1036 const int64_t old_min = var->OldMin();
1037 const int64_t old_max = var->OldMax();
1038 const int64_t var_min = var->Min();
1039 const int64_t var_max = var->Max();
1040 const bool contiguous = var_size == var_max - var_min + 1;
1041 const bool nearly_contiguous =
1042 var_size > (var_max - var_min + 1) * 7 / 10;
1043
1044 // Count the number of masks to collect to compare the deduction
1045 // vs the construction of the new active bitset.
1046 // TODO(user): Implement HolesSize() on IntVar* and use it
1047 // to remove this code and the var_sizes in the non_small
1048 // version.
1049 uint64_t hole_mask = 0;
1050 if (!contiguous) {
1051 for (const int64_t value : InitAndGetValues(holes_[var_index])) {
1052 hole_mask |= var_mask[value - original_min];
1053 }
1054 }
1055 const int64_t hole_operations = var_min - old_min + old_max - var_max;
1056 // We estimate the domain iterator to be 4x slower.
1057 const int64_t domain_operations = contiguous ? var_size : 4 * var_size;
1058 if (hole_operations < domain_operations) {
1059 for (int64_t value = old_min; value < var_min; ++value) {
1060 hole_mask |= var_mask[value - original_min];
1061 }
1062 for (int64_t value = var_max + 1; value <= old_max; ++value) {
1063 hole_mask |= var_mask[value - original_min];
1064 }
1065 // We reverse the mask as this was negative information.
1066 ApplyMask(var_index, ~hole_mask);
1067 } else {
1068 uint64_t domain_mask = 0;
1069 if (contiguous) {
1070 for (int64_t value = var_min; value <= var_max; ++value) {
1071 domain_mask |= var_mask[value - original_min];
1072 }
1073 } else if (nearly_contiguous) {
1074 for (int64_t value = var_min; value <= var_max; ++value) {
1075 if (var->Contains(value)) {
1076 domain_mask |= var_mask[value - original_min];
1077 }
1078 }
1079 } else {
1080 for (const int64_t value :
1081 InitAndGetValues(iterators_[var_index])) {
1082 domain_mask |= var_mask[value - original_min];
1083 }
1084 }
1085 ApplyMask(var_index, domain_mask);
1086 }
1087 }
1088 }
1089 }
1090
1091 std::string DebugString() const override {
1092 return absl::StrFormat(
1093 "SmallCompactPositiveTableConstraint([%s], %d tuples)",
1095 }
1096
1097 private:
1098 void ApplyMask(int var_index, uint64_t mask) {
1099 if ((~mask & active_tuples_) != 0) {
1100 // Check if we need to save the active_tuples in this node.
1101 const uint64_t current_stamp = solver()->stamp();
1102 if (stamp_ < current_stamp) {
1103 stamp_ = current_stamp;
1104 solver()->SaveValue(&active_tuples_);
1105 }
1106 active_tuples_ &= mask;
1107 if (active_tuples_) {
1108 // Maintain touched_var_.
1109 if (touched_var_ == -1 || touched_var_ == var_index) {
1110 touched_var_ = var_index;
1111 } else {
1112 touched_var_ = -2; // more than one var.
1113 }
1114 EnqueueDelayedDemon(demon_);
1115 } else {
1116 // Clean it before failing.
1117 touched_var_ = -1;
1118 solver()->Fail();
1119 }
1120 }
1121 }
1122
1123 // Bitset of active tuples.
1124 uint64_t active_tuples_;
1125 // Stamp of the active_tuple bitset.
1126 uint64_t stamp_;
1127 // The masks per value per variable.
1128 std::vector<std::vector<uint64_t>> masks_;
1129 // The min on the vars at creation time.
1130 std::vector<int64_t> original_min_;
1131 Demon* demon_;
1132 int touched_var_;
1133};
1134
1135bool HasCompactDomains(const std::vector<IntVar*>& vars) {
1136 return true; // Always assume compact table.
1137}
1138
1139// ---------- Deterministic Finite Automaton ----------
1140
1141// This constraint implements a finite automaton when transitions are
1142// the values of the variables in the array.
1143// that is state[i+1] = transition[var[i]][state[i]] if
1144// (state[i], var[i], state[i+1]) in the transition table.
1145// There is only one possible transition for a state/value pair.
1146class TransitionConstraint : public Constraint {
1147 public:
1148 static const int kStatePosition;
1149 static const int kNextStatePosition;
1150 static const int kTransitionTupleSize;
1151 TransitionConstraint(Solver* const s, const std::vector<IntVar*>& vars,
1152 const IntTupleSet& transition_table,
1153 int64_t initial_state,
1154 const std::vector<int64_t>& final_states)
1155 : Constraint(s),
1156 vars_(vars),
1157 transition_table_(transition_table),
1158 initial_state_(initial_state),
1159 final_states_(final_states) {}
1160
1161 TransitionConstraint(Solver* const s, const std::vector<IntVar*>& vars,
1162 const IntTupleSet& transition_table,
1163 int64_t initial_state,
1164 absl::Span<const int> final_states)
1165 : Constraint(s),
1166 vars_(vars),
1167 transition_table_(transition_table),
1168 initial_state_(initial_state),
1169 final_states_(final_states.size()) {
1170 for (int i = 0; i < final_states.size(); ++i) {
1171 final_states_[i] = final_states[i];
1172 }
1173 }
1174
1175 ~TransitionConstraint() override {}
1176
1177 void Post() override {
1178 Solver* const s = solver();
1179 int64_t state_min = std::numeric_limits<int64_t>::max();
1180 int64_t state_max = std::numeric_limits<int64_t>::min();
1181 const int nb_vars = vars_.size();
1182 for (int i = 0; i < transition_table_.NumTuples(); ++i) {
1183 state_max =
1184 std::max(state_max, transition_table_.Value(i, kStatePosition));
1185 state_max =
1186 std::max(state_max, transition_table_.Value(i, kNextStatePosition));
1187 state_min =
1188 std::min(state_min, transition_table_.Value(i, kStatePosition));
1189 state_min =
1190 std::min(state_min, transition_table_.Value(i, kNextStatePosition));
1191 }
1192
1193 std::vector<IntVar*> states;
1194 states.push_back(s->MakeIntConst(initial_state_));
1195 for (int var_index = 1; var_index < nb_vars; ++var_index) {
1196 states.push_back(s->MakeIntVar(state_min, state_max));
1197 }
1198 states.push_back(s->MakeIntVar(final_states_));
1199 CHECK_EQ(nb_vars + 1, states.size());
1200
1201 const int num_tuples = transition_table_.NumTuples();
1202
1203 for (int var_index = 0; var_index < nb_vars; ++var_index) {
1204 std::vector<IntVar*> tmp_vars(3);
1205 tmp_vars[0] = states[var_index];
1206 tmp_vars[1] = vars_[var_index];
1207 tmp_vars[2] = states[var_index + 1];
1208 // We always build the compact versions of the tables.
1209 if (num_tuples <= kBitsInUint64) {
1210 s->AddConstraint(s->RevAlloc(new SmallCompactPositiveTableConstraint(
1211 s, tmp_vars, transition_table_)));
1212 } else {
1213 s->AddConstraint(s->RevAlloc(new CompactPositiveTableConstraint(
1214 s, tmp_vars, transition_table_)));
1215 }
1216 }
1217 }
1218
1219 void InitialPropagate() override {}
1220
1221 void Accept(ModelVisitor* const visitor) const override {
1222 visitor->BeginVisitConstraint(ModelVisitor::kTransition, this);
1223 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
1224 vars_);
1225 visitor->VisitIntegerArgument(ModelVisitor::kInitialState, initial_state_);
1226 visitor->VisitIntegerArrayArgument(ModelVisitor::kFinalStatesArgument,
1227 final_states_);
1228 visitor->VisitIntegerMatrixArgument(ModelVisitor::kTuplesArgument,
1229 transition_table_);
1230 visitor->EndVisitConstraint(ModelVisitor::kTransition, this);
1231 }
1232
1233 std::string DebugString() const override {
1234 return absl::StrFormat(
1235 "TransitionConstraint([%s], %d transitions, initial = %d, final = "
1236 "[%s])",
1237 JoinDebugStringPtr(vars_, ", "), transition_table_.NumTuples(),
1238 initial_state_, absl::StrJoin(final_states_, ", "));
1239 }
1240
1241 private:
1242 // Variable representing transitions between states. See header file.
1243 const std::vector<IntVar*> vars_;
1244 // The transition as tuples (state, value, next_state).
1245 const IntTupleSet transition_table_;
1246 // The initial state before the first transition.
1247 const int64_t initial_state_;
1248 // Vector of final state after the last transision.
1249 std::vector<int64_t> final_states_;
1250};
1251
1252const int TransitionConstraint::kStatePosition = 0;
1253const int TransitionConstraint::kNextStatePosition = 2;
1254const int TransitionConstraint::kTransitionTupleSize = 3;
1255} // namespace
1256
1257// --------- API ----------
1258
1259Constraint* Solver::MakeAllowedAssignments(const std::vector<IntVar*>& vars,
1260 const IntTupleSet& tuples) {
1261 if (HasCompactDomains(vars)) {
1262 if (tuples.NumTuples() < kBitsInUint64 && parameters_.use_small_table()) {
1263 return RevAlloc(
1264 new SmallCompactPositiveTableConstraint(this, vars, tuples));
1265 } else {
1266 return RevAlloc(new CompactPositiveTableConstraint(this, vars, tuples));
1267 }
1268 }
1269 return RevAlloc(new PositiveTableConstraint(this, vars, tuples));
1270}
1271
1273 const std::vector<IntVar*>& vars, const IntTupleSet& transition_table,
1274 int64_t initial_state, const std::vector<int64_t>& final_states) {
1275 return RevAlloc(new TransitionConstraint(this, vars, transition_table,
1276 initial_state, final_states));
1277}
1278
1280 const std::vector<IntVar*>& vars, const IntTupleSet& transition_table,
1281 int64_t initial_state, const std::vector<int>& final_states) {
1282 return RevAlloc(new TransitionConstraint(this, vars, transition_table,
1283 initial_state, final_states));
1284}
1285
1286} // namespace operations_research
IntegerValue size
const std::vector< IntVar * > vars_
--— Main IntTupleSet class --—
Definition tuple_set.h:47
int NumTuples() const
Returns the number of tuples.
Definition tuple_set.h:345
Constraint * MakeAllowedAssignments(const std::vector< IntVar * > &vars, const IntTupleSet &tuples)
------— API -------—
Definition table.cc:1259
Constraint * MakeTransitionConstraint(const std::vector< IntVar * > &vars, const IntTupleSet &transition_table, int64_t initial_state, const std::vector< int64_t > &final_states)
Definition table.cc:1272
static const int kTransitionTupleSize
Definition table.cc:1150
const int word_length_
The length in 64 bit words of the number of tuples.
Definition table.cc:385
static const int kStatePosition
Definition table.cc:1148
const int arity_
Definition table.cc:224
static const int kNextStatePosition
Definition table.cc:1149
std::vector< ValueBitset > masks_
The masks per value per variable.
Definition table.cc:387
int64_t b
Definition table.cc:45
const int tuple_count_
Definition table.cc:223
int64_t a
Definition table.cc:44
std::vector< uint64_t > temp_mask_
A temporary mask use for computation.
Definition table.cc:388
UnsortedNullableRevBitset active_tuples_
The active bitset.
Definition table.cc:386
int64_t value
IntVar * var
std::vector< int > supports_
int index
In SWIG mode, we don't want anything besides these top-level includes.
std::string JoinDebugStringPtr(const std::vector< T > &v, absl::string_view separator)
Join v[i]->DebugString().
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
uint64_t OneBit64(int pos)
Returns a word with only bit pos set.
Definition bitset.h:42
uint64_t BitLength64(uint64_t size)
Returns the number of words needed to store size bits.
Definition bitset.h:342
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
void SetBit64(uint64_t *const bitset, uint64_t pos)
Sets the bit pos to true in bitset.
Definition bitset.h:358
int var_index
Definition search.cc:3268
std::optional< int64_t > end
int64_t start