OR-Tools  8.2
alldiff_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// AllDifferent constraints
16
17#include <algorithm>
18#include <memory>
19#include <string>
20#include <utility>
21#include <vector>
22
23#include "absl/strings/str_format.h"
29
30namespace operations_research {
31namespace {
32
33class BaseAllDifferent : public Constraint {
34 public:
35 BaseAllDifferent(Solver* const s, const std::vector<IntVar*>& vars)
36 : Constraint(s), vars_(vars) {}
37 ~BaseAllDifferent() override {}
38 std::string DebugStringInternal(const std::string& name) const {
39 return absl::StrFormat("%s(%s)", name, JoinDebugStringPtr(vars_, ", "));
40 }
41
42 protected:
43 const std::vector<IntVar*> vars_;
44 int64 size() const { return vars_.size(); }
45};
46
47//-----------------------------------------------------------------------------
48// ValueAllDifferent
49
50class ValueAllDifferent : public BaseAllDifferent {
51 public:
52 ValueAllDifferent(Solver* const s, const std::vector<IntVar*>& vars)
53 : BaseAllDifferent(s, vars) {}
54 ~ValueAllDifferent() override {}
55
56 void Post() override;
57 void InitialPropagate() override;
58 void OneMove(int index);
59 bool AllMoves();
60
61 std::string DebugString() const override {
62 return DebugStringInternal("ValueAllDifferent");
63 }
64 void Accept(ModelVisitor* const visitor) const override {
65 visitor->BeginVisitConstraint(ModelVisitor::kAllDifferent, this);
66 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
67 vars_);
68 visitor->VisitIntegerArgument(ModelVisitor::kRangeArgument, 0);
69 visitor->EndVisitConstraint(ModelVisitor::kAllDifferent, this);
70 }
71
72 private:
73 RevSwitch all_instantiated_;
74};
75
76void ValueAllDifferent::Post() {
77 for (int i = 0; i < size(); ++i) {
78 IntVar* var = vars_[i];
79 Demon* d = MakeConstraintDemon1(solver(), this, &ValueAllDifferent::OneMove,
80 "OneMove", i);
81 var->WhenBound(d);
82 }
83}
84
85void ValueAllDifferent::InitialPropagate() {
86 for (int i = 0; i < size(); ++i) {
87 if (vars_[i]->Bound()) {
88 OneMove(i);
89 }
90 }
91}
92
93void ValueAllDifferent::OneMove(int index) {
94 if (!AllMoves()) {
95 const int64 val = vars_[index]->Value();
96 for (int j = 0; j < size(); ++j) {
97 if (index != j) {
98 if (vars_[j]->Size() < 0xFFFFFF) {
99 vars_[j]->RemoveValue(val);
100 } else {
101 solver()->AddConstraint(solver()->MakeNonEquality(vars_[j], val));
102 }
103 }
104 }
105 }
106}
107
108bool ValueAllDifferent::AllMoves() {
109 if (all_instantiated_.Switched() || size() == 0) {
110 return true;
111 }
112 for (int i = 0; i < size(); ++i) {
113 if (!vars_[i]->Bound()) {
114 return false;
115 }
116 }
117 std::unique_ptr<int64[]> values(new int64[size()]);
118 for (int i = 0; i < size(); ++i) {
119 values[i] = vars_[i]->Value();
120 }
121 std::sort(values.get(), values.get() + size());
122 for (int i = 0; i < size() - 1; ++i) {
123 if (values[i] == values[i + 1]) {
124 values.reset(); // prevent leaks (solver()->Fail() won't return)
125 solver()->Fail();
126 }
127 }
128 all_instantiated_.Switch(solver());
129 return true;
130}
131
132// ---------- Bounds All Different ----------
133// See http://www.cs.uwaterloo.ca/~cquimper/Papers/ijcai03_TR.pdf for details.
134
135class RangeBipartiteMatching {
136 public:
137 struct Interval {
142 };
143
144 RangeBipartiteMatching(Solver* const solver, int size)
145 : solver_(solver),
146 size_(size),
147 intervals_(new Interval[size + 1]),
148 min_sorted_(new Interval*[size]),
149 max_sorted_(new Interval*[size]),
150 bounds_(new int64[2 * size + 2]),
151 tree_(new int[2 * size + 2]),
152 diff_(new int64[2 * size + 2]),
153 hall_(new int[2 * size + 2]),
154 active_size_(0) {
155 for (int i = 0; i < size; ++i) {
156 max_sorted_[i] = &intervals_[i];
157 min_sorted_[i] = max_sorted_[i];
158 }
159 }
160
161 void SetRange(int index, int64 imin, int64 imax) {
162 intervals_[index].min = imin;
163 intervals_[index].max = imax;
164 }
165
166 bool Propagate() {
167 SortArray();
168
169 const bool modified1 = PropagateMin();
170 const bool modified2 = PropagateMax();
171 return modified1 || modified2;
172 }
173
174 int64 Min(int index) const { return intervals_[index].min; }
175
176 int64 Max(int index) const { return intervals_[index].max; }
177
178 private:
179 // This method sorts the min_sorted_ and max_sorted_ arrays and fill
180 // the bounds_ array (and set the active_size_ counter).
181 void SortArray() {
182 std::sort(min_sorted_.get(), min_sorted_.get() + size_,
183 CompareIntervalMin());
184 std::sort(max_sorted_.get(), max_sorted_.get() + size_,
185 CompareIntervalMax());
186
187 int64 min = min_sorted_[0]->min;
188 int64 max = max_sorted_[0]->max + 1;
189 int64 last = min - 2;
190 bounds_[0] = last;
191
192 int i = 0;
193 int j = 0;
194 int nb = 0;
195 for (;;) { // merge min_sorted_[] and max_sorted_[] into bounds_[].
196 if (i < size_ && min <= max) { // make sure min_sorted_ exhausted first.
197 if (min != last) {
198 last = min;
199 bounds_[++nb] = last;
200 }
201 min_sorted_[i]->min_rank = nb;
202 if (++i < size_) {
203 min = min_sorted_[i]->min;
204 }
205 } else {
206 if (max != last) {
207 last = max;
208 bounds_[++nb] = last;
209 }
210 max_sorted_[j]->max_rank = nb;
211 if (++j == size_) {
212 break;
213 }
214 max = max_sorted_[j]->max + 1;
215 }
216 }
217 active_size_ = nb;
218 bounds_[nb + 1] = bounds_[nb] + 2;
219 }
220
221 // These two methods will actually do the new bounds computation.
222 bool PropagateMin() {
223 bool modified = false;
224
225 for (int i = 1; i <= active_size_ + 1; ++i) {
226 hall_[i] = i - 1;
227 tree_[i] = i - 1;
228 diff_[i] = bounds_[i] - bounds_[i - 1];
229 }
230 // visit intervals in increasing max order
231 for (int i = 0; i < size_; ++i) {
232 const int x = max_sorted_[i]->min_rank;
233 const int y = max_sorted_[i]->max_rank;
234 int z = PathMax(tree_.get(), x + 1);
235 int j = tree_[z];
236 if (--diff_[z] == 0) {
237 tree_[z] = z + 1;
238 z = PathMax(tree_.get(), z + 1);
239 tree_[z] = j;
240 }
241 PathSet(x + 1, z, z, tree_.get()); // path compression
242 if (diff_[z] < bounds_[z] - bounds_[y]) {
243 solver_->Fail();
244 }
245 if (hall_[x] > x) {
246 int w = PathMax(hall_.get(), hall_[x]);
247 max_sorted_[i]->min = bounds_[w];
248 PathSet(x, w, w, hall_.get()); // path compression
249 modified = true;
250 }
251 if (diff_[z] == bounds_[z] - bounds_[y]) {
252 PathSet(hall_[y], j - 1, y, hall_.get()); // mark hall interval
253 hall_[y] = j - 1;
254 }
255 }
256 return modified;
257 }
258
259 bool PropagateMax() {
260 bool modified = false;
261
262 for (int i = 0; i <= active_size_; i++) {
263 tree_[i] = i + 1;
264 hall_[i] = i + 1;
265 diff_[i] = bounds_[i + 1] - bounds_[i];
266 }
267 // visit intervals in decreasing min order
268 for (int i = size_ - 1; i >= 0; --i) {
269 const int x = min_sorted_[i]->max_rank;
270 const int y = min_sorted_[i]->min_rank;
271 int z = PathMin(tree_.get(), x - 1);
272 int j = tree_[z];
273 if (--diff_[z] == 0) {
274 tree_[z] = z - 1;
275 z = PathMin(tree_.get(), z - 1);
276 tree_[z] = j;
277 }
278 PathSet(x - 1, z, z, tree_.get());
279 if (diff_[z] < bounds_[y] - bounds_[z]) {
280 solver_->Fail();
281 // useless. Should have been caught by the PropagateMin() method.
282 }
283 if (hall_[x] < x) {
284 int w = PathMin(hall_.get(), hall_[x]);
285 min_sorted_[i]->max = bounds_[w] - 1;
286 PathSet(x, w, w, hall_.get());
287 modified = true;
288 }
289 if (diff_[z] == bounds_[y] - bounds_[z]) {
290 PathSet(hall_[y], j + 1, y, hall_.get());
291 hall_[y] = j + 1;
292 }
293 }
294 return modified;
295 }
296
297 // TODO(user) : use better sort, use bounding boxes of modifications to
298 // improve the sorting (only modified vars).
299
300 // This method is used by the STL sort.
301 struct CompareIntervalMin {
302 bool operator()(const Interval* i1, const Interval* i2) const {
303 return (i1->min < i2->min);
304 }
305 };
306
307 // This method is used by the STL sort.
308 struct CompareIntervalMax {
309 bool operator()(const Interval* i1, const Interval* i2) const {
310 return (i1->max < i2->max);
311 }
312 };
313
314 void PathSet(int start, int end, int to, int* const tree) {
315 int l = start;
316 while (l != end) {
317 int k = l;
318 l = tree[k];
319 tree[k] = to;
320 }
321 }
322
323 int PathMin(const int* const tree, int index) {
324 int i = index;
325 while (tree[i] < i) {
326 i = tree[i];
327 }
328 return i;
329 }
330
331 int PathMax(const int* const tree, int index) {
332 int i = index;
333 while (tree[i] > i) {
334 i = tree[i];
335 }
336 return i;
337 }
338
339 Solver* const solver_;
340 const int size_;
341 std::unique_ptr<Interval[]> intervals_;
342 std::unique_ptr<Interval*[]> min_sorted_;
343 std::unique_ptr<Interval*[]> max_sorted_;
344 // bounds_[1..active_size_] hold set of min & max in the n intervals_
345 // while bounds_[0] and bounds_[active_size_ + 1] allow sentinels.
346 std::unique_ptr<int64[]> bounds_;
347 std::unique_ptr<int[]> tree_; // tree links.
348 std::unique_ptr<int64[]> diff_; // diffs between critical capacities.
349 std::unique_ptr<int[]> hall_; // hall interval links.
350 int active_size_;
351};
352
353class BoundsAllDifferent : public BaseAllDifferent {
354 public:
355 BoundsAllDifferent(Solver* const s, const std::vector<IntVar*>& vars)
356 : BaseAllDifferent(s, vars), matching_(s, vars.size()) {}
357
358 ~BoundsAllDifferent() override {}
359
360 void Post() override {
361 Demon* range = MakeDelayedConstraintDemon0(
362 solver(), this, &BoundsAllDifferent::IncrementalPropagate,
363 "IncrementalPropagate");
364
365 for (int i = 0; i < size(); ++i) {
366 vars_[i]->WhenRange(range);
367 Demon* bound = MakeConstraintDemon1(solver(), this,
368 &BoundsAllDifferent::PropagateValue,
369 "PropagateValue", i);
370 vars_[i]->WhenBound(bound);
371 }
372 }
373
374 void InitialPropagate() override {
375 IncrementalPropagate();
376 for (int i = 0; i < size(); ++i) {
377 if (vars_[i]->Bound()) {
378 PropagateValue(i);
379 }
380 }
381 }
382
383 virtual void IncrementalPropagate() {
384 for (int i = 0; i < size(); ++i) {
385 matching_.SetRange(i, vars_[i]->Min(), vars_[i]->Max());
386 }
387
388 if (matching_.Propagate()) {
389 for (int i = 0; i < size(); ++i) {
390 vars_[i]->SetRange(matching_.Min(i), matching_.Max(i));
391 }
392 }
393 }
394
395 void PropagateValue(int index) {
396 const int64 to_remove = vars_[index]->Value();
397 for (int j = 0; j < index; j++) {
398 if (vars_[j]->Size() < 0xFFFFFF) {
399 vars_[j]->RemoveValue(to_remove);
400 } else {
401 solver()->AddConstraint(solver()->MakeNonEquality(vars_[j], to_remove));
402 }
403 }
404 for (int j = index + 1; j < size(); j++) {
405 if (vars_[j]->Size() < 0xFFFFFF) {
406 vars_[j]->RemoveValue(to_remove);
407 } else {
408 solver()->AddConstraint(solver()->MakeNonEquality(vars_[j], to_remove));
409 }
410 }
411 }
412
413 std::string DebugString() const override {
414 return DebugStringInternal("BoundsAllDifferent");
415 }
416
417 void Accept(ModelVisitor* const visitor) const override {
418 visitor->BeginVisitConstraint(ModelVisitor::kAllDifferent, this);
419 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
420 vars_);
421 visitor->VisitIntegerArgument(ModelVisitor::kRangeArgument, 1);
422 visitor->EndVisitConstraint(ModelVisitor::kAllDifferent, this);
423 }
424
425 private:
426 RangeBipartiteMatching matching_;
427};
428
429class SortConstraint : public Constraint {
430 public:
431 SortConstraint(Solver* const solver,
432 const std::vector<IntVar*>& original_vars,
433 const std::vector<IntVar*>& sorted_vars)
434 : Constraint(solver),
435 ovars_(original_vars),
436 svars_(sorted_vars),
437 mins_(original_vars.size(), 0),
438 maxs_(original_vars.size(), 0),
439 matching_(solver, original_vars.size()) {}
440
441 ~SortConstraint() override {}
442
443 void Post() override {
444 Demon* const demon =
445 solver()->MakeDelayedConstraintInitialPropagateCallback(this);
446 for (int i = 0; i < size(); ++i) {
447 ovars_[i]->WhenRange(demon);
448 svars_[i]->WhenRange(demon);
449 }
450 }
451
452 void InitialPropagate() override {
453 for (int i = 0; i < size(); ++i) {
454 int64 vmin = 0;
455 int64 vmax = 0;
456 ovars_[i]->Range(&vmin, &vmax);
457 mins_[i] = vmin;
458 maxs_[i] = vmax;
459 }
460 // Propagates from variables to sorted variables.
461 std::sort(mins_.begin(), mins_.end());
462 std::sort(maxs_.begin(), maxs_.end());
463 for (int i = 0; i < size(); ++i) {
464 svars_[i]->SetRange(mins_[i], maxs_[i]);
465 }
466 // Maintains sortedness.
467 for (int i = 0; i < size() - 1; ++i) {
468 svars_[i + 1]->SetMin(svars_[i]->Min());
469 }
470 for (int i = size() - 1; i > 0; --i) {
471 svars_[i - 1]->SetMax(svars_[i]->Max());
472 }
473 // Reverse propagation.
474 for (int i = 0; i < size(); ++i) {
475 int64 imin = 0;
476 int64 imax = 0;
477 FindIntersectionRange(i, &imin, &imax);
478 matching_.SetRange(i, imin, imax);
479 }
480 matching_.Propagate();
481 for (int i = 0; i < size(); ++i) {
482 const int64 vmin = svars_[matching_.Min(i)]->Min();
483 const int64 vmax = svars_[matching_.Max(i)]->Max();
484 ovars_[i]->SetRange(vmin, vmax);
485 }
486 }
487
488 void Accept(ModelVisitor* const visitor) const override {
489 visitor->BeginVisitConstraint(ModelVisitor::kSortingConstraint, this);
490 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
491 ovars_);
492 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kTargetArgument,
493 svars_);
494 visitor->EndVisitConstraint(ModelVisitor::kSortingConstraint, this);
495 }
496
497 std::string DebugString() const override {
498 return absl::StrFormat("Sort(%s, %s)", JoinDebugStringPtr(ovars_, ", "),
499 JoinDebugStringPtr(svars_, ", "));
500 }
501
502 private:
503 int64 size() const { return ovars_.size(); }
504
505 void FindIntersectionRange(int index, int64* const range_min,
506 int64* const range_max) const {
507 // Naive version.
508 // TODO(user): Implement log(n) version.
509 int64 imin = 0;
510 while (imin < size() && NotIntersect(index, imin)) {
511 imin++;
512 }
513 if (imin == size()) {
514 solver()->Fail();
515 }
516 int64 imax = size() - 1;
517 while (imax > imin && NotIntersect(index, imax)) {
518 imax--;
519 }
520 *range_min = imin;
521 *range_max = imax;
522 }
523
524 bool NotIntersect(int oindex, int sindex) const {
525 return ovars_[oindex]->Min() > svars_[sindex]->Max() ||
526 ovars_[oindex]->Max() < svars_[sindex]->Min();
527 }
528
529 const std::vector<IntVar*> ovars_;
530 const std::vector<IntVar*> svars_;
531 std::vector<int64> mins_;
532 std::vector<int64> maxs_;
533 RangeBipartiteMatching matching_;
534};
535
536// All variables are pairwise different, unless they are assigned to
537// the escape value.
538class AllDifferentExcept : public Constraint {
539 public:
540 AllDifferentExcept(Solver* const s, std::vector<IntVar*> vars,
541 int64 escape_value)
542 : Constraint(s), vars_(std::move(vars)), escape_value_(escape_value) {}
543
544 ~AllDifferentExcept() override {}
545
546 void Post() override {
547 for (int i = 0; i < vars_.size(); ++i) {
548 IntVar* const var = vars_[i];
549 Demon* const d = MakeConstraintDemon1(
550 solver(), this, &AllDifferentExcept::Propagate, "Propagate", i);
551 var->WhenBound(d);
552 }
553 }
554
555 void InitialPropagate() override {
556 for (int i = 0; i < vars_.size(); ++i) {
557 if (vars_[i]->Bound()) {
558 Propagate(i);
559 }
560 }
561 }
562
563 void Propagate(int index) {
564 const int64 val = vars_[index]->Value();
565 if (val != escape_value_) {
566 for (int j = 0; j < vars_.size(); ++j) {
567 if (index != j) {
568 vars_[j]->RemoveValue(val);
569 }
570 }
571 }
572 }
573
574 std::string DebugString() const override {
575 return absl::StrFormat("AllDifferentExcept([%s], %d",
576 JoinDebugStringPtr(vars_, ", "), escape_value_);
577 }
578
579 void Accept(ModelVisitor* const visitor) const override {
580 visitor->BeginVisitConstraint(ModelVisitor::kAllDifferent, this);
581 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
582 vars_);
583 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, escape_value_);
584 visitor->EndVisitConstraint(ModelVisitor::kAllDifferent, this);
585 }
586
587 private:
588 std::vector<IntVar*> vars_;
589 const int64 escape_value_;
590};
591
592// Creates a constraint that states that all variables in the first
593// vector are different from all variables from the second group,
594// unless they are assigned to the escape value if it is defined. Thus
595// the set of values in the first vector minus the escape value does
596// not intersect the set of values in the second vector.
597class NullIntersectArrayExcept : public Constraint {
598 public:
599 NullIntersectArrayExcept(Solver* const s, std::vector<IntVar*> first_vars,
600 std::vector<IntVar*> second_vars, int64 escape_value)
601 : Constraint(s),
602 first_vars_(std::move(first_vars)),
603 second_vars_(std::move(second_vars)),
604 escape_value_(escape_value),
605 has_escape_value_(true) {}
606
607 NullIntersectArrayExcept(Solver* const s, std::vector<IntVar*> first_vars,
608 std::vector<IntVar*> second_vars)
609 : Constraint(s),
610 first_vars_(std::move(first_vars)),
611 second_vars_(std::move(second_vars)),
612 escape_value_(0),
613 has_escape_value_(false) {}
614
615 ~NullIntersectArrayExcept() override {}
616
617 void Post() override {
618 for (int i = 0; i < first_vars_.size(); ++i) {
619 IntVar* const var = first_vars_[i];
620 Demon* const d = MakeConstraintDemon1(
621 solver(), this, &NullIntersectArrayExcept::PropagateFirst,
622 "PropagateFirst", i);
623 var->WhenBound(d);
624 }
625 for (int i = 0; i < second_vars_.size(); ++i) {
626 IntVar* const var = second_vars_[i];
627 Demon* const d = MakeConstraintDemon1(
628 solver(), this, &NullIntersectArrayExcept::PropagateSecond,
629 "PropagateSecond", i);
630 var->WhenBound(d);
631 }
632 }
633
634 void InitialPropagate() override {
635 for (int i = 0; i < first_vars_.size(); ++i) {
636 if (first_vars_[i]->Bound()) {
637 PropagateFirst(i);
638 }
639 }
640 for (int i = 0; i < second_vars_.size(); ++i) {
641 if (second_vars_[i]->Bound()) {
642 PropagateSecond(i);
643 }
644 }
645 }
646
647 void PropagateFirst(int index) {
648 const int64 val = first_vars_[index]->Value();
649 if (!has_escape_value_ || val != escape_value_) {
650 for (int j = 0; j < second_vars_.size(); ++j) {
651 second_vars_[j]->RemoveValue(val);
652 }
653 }
654 }
655
656 void PropagateSecond(int index) {
657 const int64 val = second_vars_[index]->Value();
658 if (!has_escape_value_ || val != escape_value_) {
659 for (int j = 0; j < first_vars_.size(); ++j) {
660 first_vars_[j]->RemoveValue(val);
661 }
662 }
663 }
664
665 std::string DebugString() const override {
666 return absl::StrFormat("NullIntersectArray([%s], [%s], escape = %d",
667 JoinDebugStringPtr(first_vars_, ", "),
668 JoinDebugStringPtr(second_vars_, ", "),
669 escape_value_);
670 }
671
672 void Accept(ModelVisitor* const visitor) const override {
673 visitor->BeginVisitConstraint(ModelVisitor::kNullIntersect, this);
674 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kLeftArgument,
675 first_vars_);
676 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kRightArgument,
677 second_vars_);
678 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, escape_value_);
679 visitor->EndVisitConstraint(ModelVisitor::kNullIntersect, this);
680 }
681
682 private:
683 std::vector<IntVar*> first_vars_;
684 std::vector<IntVar*> second_vars_;
685 const int64 escape_value_;
686 const bool has_escape_value_;
687};
688} // namespace
689
690Constraint* Solver::MakeAllDifferent(const std::vector<IntVar*>& vars) {
691 return MakeAllDifferent(vars, true);
692}
693
694Constraint* Solver::MakeAllDifferent(const std::vector<IntVar*>& vars,
695 bool stronger_propagation) {
696 const int size = vars.size();
697 for (int i = 0; i < size; ++i) {
698 CHECK_EQ(this, vars[i]->solver());
699 }
700 if (size < 2) {
701 return MakeTrueConstraint();
702 } else if (size == 2) {
703 return MakeNonEquality(const_cast<IntVar* const>(vars[0]),
704 const_cast<IntVar* const>(vars[1]));
705 } else {
706 if (stronger_propagation) {
707 return RevAlloc(new BoundsAllDifferent(this, vars));
708 } else {
709 return RevAlloc(new ValueAllDifferent(this, vars));
710 }
711 }
712}
713
714Constraint* Solver::MakeSortingConstraint(const std::vector<IntVar*>& vars,
715 const std::vector<IntVar*>& sorted) {
716 CHECK_EQ(vars.size(), sorted.size());
717 return RevAlloc(new SortConstraint(this, vars, sorted));
718}
719
720Constraint* Solver::MakeAllDifferentExcept(const std::vector<IntVar*>& vars,
721 int64 escape_value) {
722 int escape_candidates = 0;
723 for (int i = 0; i < vars.size(); ++i) {
724 escape_candidates += (vars[i]->Contains(escape_value));
725 }
726 if (escape_candidates <= 1) {
727 return MakeAllDifferent(vars);
728 } else {
729 return RevAlloc(new AllDifferentExcept(this, vars, escape_value));
730 }
731}
732
733Constraint* Solver::MakeNullIntersect(const std::vector<IntVar*>& first_vars,
734 const std::vector<IntVar*>& second_vars) {
735 return RevAlloc(new NullIntersectArrayExcept(this, first_vars, second_vars));
736}
737
739 const std::vector<IntVar*>& first_vars,
740 const std::vector<IntVar*>& second_vars, int64 escape_value) {
741 int first_escape_candidates = 0;
742 for (int i = 0; i < first_vars.size(); ++i) {
743 first_escape_candidates += (first_vars[i]->Contains(escape_value));
744 }
745 int second_escape_candidates = 0;
746 for (int i = 0; i < second_vars.size(); ++i) {
747 second_escape_candidates += (second_vars[i]->Contains(escape_value));
748 }
749 if (first_escape_candidates == 0 || second_escape_candidates == 0) {
750 return RevAlloc(
751 new NullIntersectArrayExcept(this, first_vars, second_vars));
752 } else {
753 return RevAlloc(new NullIntersectArrayExcept(this, first_vars, second_vars,
754 escape_value));
755 }
756}
757} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
const std::vector< IntVar * > vars_
Definition: alldiff_cst.cc:43
int max_rank
Definition: alldiff_cst.cc:141
int64 max
Definition: alldiff_cst.cc:139
int min_rank
Definition: alldiff_cst.cc:140
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
A constraint is the main modeling object.
The class IntVar is a subset of IntExpr.
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
void Switch(Solver *const solver)
Constraint * MakeNullIntersectExcept(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars, int64 escape_value)
Creates a constraint that states that all variables in the first vector are different from all variab...
Definition: alldiff_cst.cc:738
Constraint * MakeNullIntersect(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars)
Creates a constraint that states that all variables in the first vector are different from all variab...
Definition: alldiff_cst.cc:733
Constraint * MakeAllDifferentExcept(const std::vector< IntVar * > &vars, int64 escape_value)
All variables are pairwise different, unless they are assigned to the escape value.
Definition: alldiff_cst.cc:720
Constraint * MakeTrueConstraint()
This constraint always succeeds.
Definition: constraints.cc:515
Constraint * MakeNonEquality(IntExpr *const left, IntExpr *const right)
left != right
Definition: range_cst.cc:564
Constraint * MakeAllDifferent(const std::vector< IntVar * > &vars)
All variables are pairwise different.
Definition: alldiff_cst.cc:690
Constraint * MakeSortingConstraint(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &sorted)
Creates a constraint binding the arrays of variables "vars" and "sorted_vars": sorted_vars[0] must be...
Definition: alldiff_cst.cc:714
T * RevAlloc(T *object)
Registers the given object as being reversible.
const std::string name
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Demon * MakeDelayedConstraintDemon0(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)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:45
STL namespace.
int index
Definition: pack.cc:508
int64 bound