OR-Tools  8.2
range_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// Range constraints
16
17#include <stddef.h>
18
19#include <string>
20
21#include "absl/strings/str_format.h"
25
26namespace operations_research {
27
28//-----------------------------------------------------------------------------
29// RangeEquality
30
31namespace {
32class RangeEquality : public Constraint {
33 public:
34 RangeEquality(Solver* const s, IntExpr* const l, IntExpr* const r)
35 : Constraint(s), left_(l), right_(r) {}
36
37 ~RangeEquality() override {}
38
39 void Post() override {
40 Demon* const d = solver()->MakeConstraintInitialPropagateCallback(this);
41 left_->WhenRange(d);
42 right_->WhenRange(d);
43 }
44
45 void InitialPropagate() override {
46 left_->SetRange(right_->Min(), right_->Max());
47 right_->SetRange(left_->Min(), left_->Max());
48 }
49
50 std::string DebugString() const override {
51 return left_->DebugString() + " == " + right_->DebugString();
52 }
53
54 IntVar* Var() override { return solver()->MakeIsEqualVar(left_, right_); }
55
56 void Accept(ModelVisitor* const visitor) const override {
57 visitor->BeginVisitConstraint(ModelVisitor::kEquality, this);
58 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
59 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
60 right_);
61 visitor->EndVisitConstraint(ModelVisitor::kEquality, this);
62 }
63
64 private:
65 IntExpr* const left_;
66 IntExpr* const right_;
67};
68
69//-----------------------------------------------------------------------------
70// RangeLessOrEqual
71
72class RangeLessOrEqual : public Constraint {
73 public:
74 RangeLessOrEqual(Solver* const s, IntExpr* const l, IntExpr* const r);
75 ~RangeLessOrEqual() override {}
76 void Post() override;
77 void InitialPropagate() override;
78 std::string DebugString() const override;
79 IntVar* Var() override {
80 return solver()->MakeIsLessOrEqualVar(left_, right_);
81 }
82 void Accept(ModelVisitor* const visitor) const override {
83 visitor->BeginVisitConstraint(ModelVisitor::kLessOrEqual, this);
84 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
85 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
86 right_);
87 visitor->EndVisitConstraint(ModelVisitor::kLessOrEqual, this);
88 }
89
90 private:
91 IntExpr* const left_;
92 IntExpr* const right_;
93 Demon* demon_;
94};
95
96RangeLessOrEqual::RangeLessOrEqual(Solver* const s, IntExpr* const l,
97 IntExpr* const r)
98 : Constraint(s), left_(l), right_(r), demon_(nullptr) {}
99
100void RangeLessOrEqual::Post() {
101 demon_ = solver()->MakeConstraintInitialPropagateCallback(this);
102 left_->WhenRange(demon_);
103 right_->WhenRange(demon_);
104}
105
106void RangeLessOrEqual::InitialPropagate() {
107 left_->SetMax(right_->Max());
108 right_->SetMin(left_->Min());
109 if (left_->Max() <= right_->Min()) {
110 demon_->inhibit(solver());
111 }
112}
113
114std::string RangeLessOrEqual::DebugString() const {
115 return left_->DebugString() + " <= " + right_->DebugString();
116}
117
118//-----------------------------------------------------------------------------
119// RangeLess
120
121class RangeLess : public Constraint {
122 public:
123 RangeLess(Solver* const s, IntExpr* const l, IntExpr* const r);
124 ~RangeLess() override {}
125 void Post() override;
126 void InitialPropagate() override;
127 std::string DebugString() const override;
128 IntVar* Var() override { return solver()->MakeIsLessVar(left_, right_); }
129 void Accept(ModelVisitor* const visitor) const override {
130 visitor->BeginVisitConstraint(ModelVisitor::kLess, this);
131 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
132 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
133 right_);
134 visitor->EndVisitConstraint(ModelVisitor::kLess, this);
135 }
136
137 private:
138 IntExpr* const left_;
139 IntExpr* const right_;
140 Demon* demon_;
141};
142
143RangeLess::RangeLess(Solver* const s, IntExpr* const l, IntExpr* const r)
144 : Constraint(s), left_(l), right_(r), demon_(nullptr) {}
145
146void RangeLess::Post() {
147 demon_ = solver()->MakeConstraintInitialPropagateCallback(this);
148 left_->WhenRange(demon_);
149 right_->WhenRange(demon_);
150}
151
152void RangeLess::InitialPropagate() {
153 left_->SetMax(right_->Max() - 1);
154 right_->SetMin(left_->Min() + 1);
155 if (left_->Max() < right_->Min()) {
156 demon_->inhibit(solver());
157 }
158}
159
160std::string RangeLess::DebugString() const {
161 return left_->DebugString() + " < " + right_->DebugString();
162}
163
164//-----------------------------------------------------------------------------
165// DiffVar
166
167class DiffVar : public Constraint {
168 public:
169 DiffVar(Solver* const s, IntVar* const l, IntVar* const r);
170 ~DiffVar() override {}
171 void Post() override;
172 void InitialPropagate() override;
173 std::string DebugString() const override;
174 IntVar* Var() override { return solver()->MakeIsDifferentVar(left_, right_); }
175 void LeftBound();
176 void RightBound();
177
178 void Accept(ModelVisitor* const visitor) const override {
179 visitor->BeginVisitConstraint(ModelVisitor::kNonEqual, this);
180 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
181 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
182 right_);
183 visitor->EndVisitConstraint(ModelVisitor::kNonEqual, this);
184 }
185
186 private:
187 IntVar* const left_;
188 IntVar* const right_;
189};
190
191DiffVar::DiffVar(Solver* const s, IntVar* const l, IntVar* const r)
192 : Constraint(s), left_(l), right_(r) {}
193
194void DiffVar::Post() {
195 Demon* const left_demon =
196 MakeConstraintDemon0(solver(), this, &DiffVar::LeftBound, "LeftBound");
197 Demon* const right_demon =
198 MakeConstraintDemon0(solver(), this, &DiffVar::RightBound, "RightBound");
199 left_->WhenBound(left_demon);
200 right_->WhenBound(right_demon);
201 // TODO(user) : improve me, separated demons, actually to test
202}
203
204void DiffVar::LeftBound() {
205 if (right_->Size() < 0xFFFFFF) {
206 right_->RemoveValue(left_->Min()); // we use min instead of value
207 } else {
208 solver()->AddConstraint(solver()->MakeNonEquality(right_, left_->Min()));
209 }
210}
211
212void DiffVar::RightBound() {
213 if (left_->Size() < 0xFFFFFF) {
214 left_->RemoveValue(right_->Min()); // see above
215 } else {
216 solver()->AddConstraint(solver()->MakeNonEquality(left_, right_->Min()));
217 }
218}
219
220void DiffVar::InitialPropagate() {
221 if (left_->Bound()) {
222 LeftBound();
223 }
224 if (right_->Bound()) {
225 RightBound();
226 }
227}
228
229std::string DiffVar::DebugString() const {
230 return left_->DebugString() + " != " + right_->DebugString();
231}
232
233// --------------------- Reified API -------------------
234// A reified API transforms an constraint into a status variables.
235// For example x == y is transformed into IsEqual(x, y, b) where
236// b is a boolean variable which is true if and only if x is equal to b.
237
238// IsEqualCt
239
240class IsEqualCt : public CastConstraint {
241 public:
242 IsEqualCt(Solver* const s, IntExpr* const l, IntExpr* const r,
243 IntVar* const b)
244 : CastConstraint(s, b), left_(l), right_(r), range_demon_(nullptr) {}
245
246 ~IsEqualCt() override {}
247
248 void Post() override {
249 range_demon_ = solver()->MakeConstraintInitialPropagateCallback(this);
250 left_->WhenRange(range_demon_);
251 right_->WhenRange(range_demon_);
252 Demon* const target_demon = MakeConstraintDemon0(
253 solver(), this, &IsEqualCt::PropagateTarget, "PropagateTarget");
254 target_var_->WhenBound(target_demon);
255 }
256
257 void InitialPropagate() override {
258 if (target_var_->Bound()) {
259 PropagateTarget();
260 return;
261 }
262 if (left_->Min() > right_->Max() || left_->Max() < right_->Min()) {
263 target_var_->SetValue(0);
264 range_demon_->inhibit(solver());
265 } else if (left_->Bound()) {
266 if (right_->Bound()) {
267 target_var_->SetValue(left_->Min() == right_->Min());
268 } else if (right_->IsVar() && !right_->Var()->Contains(left_->Min())) {
269 range_demon_->inhibit(solver());
270 target_var_->SetValue(0);
271 }
272 } else if (right_->Bound() && left_->IsVar() &&
273 !left_->Var()->Contains(right_->Min())) {
274 range_demon_->inhibit(solver());
275 target_var_->SetValue(0);
276 }
277 }
278
279 void PropagateTarget() {
280 if (target_var_->Min() == 0) {
281 if (left_->Bound()) {
282 range_demon_->inhibit(solver());
283 if (right_->IsVar()) {
284 right_->Var()->RemoveValue(left_->Min());
285 } else {
286 solver()->AddConstraint(
287 solver()->MakeNonEquality(right_, left_->Min()));
288 }
289 } else if (right_->Bound()) {
290 range_demon_->inhibit(solver());
291 if (left_->IsVar()) {
292 left_->Var()->RemoveValue(right_->Min());
293 } else {
294 solver()->AddConstraint(
295 solver()->MakeNonEquality(left_, right_->Min()));
296 }
297 }
298 } else { // Var is true.
299 left_->SetRange(right_->Min(), right_->Max());
300 right_->SetRange(left_->Min(), left_->Max());
301 }
302 }
303
304 std::string DebugString() const override {
305 return absl::StrFormat("IsEqualCt(%s, %s, %s)", left_->DebugString(),
306 right_->DebugString(), target_var_->DebugString());
307 }
308
309 void Accept(ModelVisitor* const visitor) const override {
310 visitor->BeginVisitConstraint(ModelVisitor::kIsEqual, this);
311 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
312 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
313 right_);
314 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
316 visitor->EndVisitConstraint(ModelVisitor::kIsEqual, this);
317 }
318
319 private:
320 IntExpr* const left_;
321 IntExpr* const right_;
322 Demon* range_demon_;
323};
324
325// IsDifferentCt
326
327class IsDifferentCt : public CastConstraint {
328 public:
329 IsDifferentCt(Solver* const s, IntExpr* const l, IntExpr* const r,
330 IntVar* const b)
331 : CastConstraint(s, b), left_(l), right_(r), range_demon_(nullptr) {}
332
333 ~IsDifferentCt() override {}
334
335 void Post() override {
336 range_demon_ = solver()->MakeConstraintInitialPropagateCallback(this);
337 left_->WhenRange(range_demon_);
338 right_->WhenRange(range_demon_);
339 Demon* const target_demon = MakeConstraintDemon0(
340 solver(), this, &IsDifferentCt::PropagateTarget, "PropagateTarget");
341 target_var_->WhenBound(target_demon);
342 }
343
344 void InitialPropagate() override {
345 if (target_var_->Bound()) {
346 PropagateTarget();
347 return;
348 }
349 if (left_->Min() > right_->Max() || left_->Max() < right_->Min()) {
350 target_var_->SetValue(1);
351 range_demon_->inhibit(solver());
352 } else if (left_->Bound()) {
353 if (right_->Bound()) {
354 target_var_->SetValue(left_->Min() != right_->Min());
355 } else if (right_->IsVar() && !right_->Var()->Contains(left_->Min())) {
356 range_demon_->inhibit(solver());
357 target_var_->SetValue(1);
358 }
359 } else if (right_->Bound() && left_->IsVar() &&
360 !left_->Var()->Contains(right_->Min())) {
361 range_demon_->inhibit(solver());
362 target_var_->SetValue(1);
363 }
364 }
365
366 void PropagateTarget() {
367 if (target_var_->Min() == 0) {
368 left_->SetRange(right_->Min(), right_->Max());
369 right_->SetRange(left_->Min(), left_->Max());
370 } else { // Var is true.
371 if (left_->Bound()) {
372 range_demon_->inhibit(solver());
373 solver()->AddConstraint(
374 solver()->MakeNonEquality(right_, left_->Min()));
375 } else if (right_->Bound()) {
376 range_demon_->inhibit(solver());
377 solver()->AddConstraint(
378 solver()->MakeNonEquality(left_, right_->Min()));
379 }
380 }
381 }
382
383 std::string DebugString() const override {
384 return absl::StrFormat("IsDifferentCt(%s, %s, %s)", left_->DebugString(),
385 right_->DebugString(), target_var_->DebugString());
386 }
387
388 void Accept(ModelVisitor* const visitor) const override {
389 visitor->BeginVisitConstraint(ModelVisitor::kIsDifferent, this);
390 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
391 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
392 right_);
393 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
395 visitor->EndVisitConstraint(ModelVisitor::kIsDifferent, this);
396 }
397
398 private:
399 IntExpr* const left_;
400 IntExpr* const right_;
401 Demon* range_demon_;
402};
403
404class IsLessOrEqualCt : public CastConstraint {
405 public:
406 IsLessOrEqualCt(Solver* const s, IntExpr* const l, IntExpr* const r,
407 IntVar* const b)
408 : CastConstraint(s, b), left_(l), right_(r), demon_(nullptr) {}
409
410 ~IsLessOrEqualCt() override {}
411
412 void Post() override {
413 demon_ = solver()->MakeConstraintInitialPropagateCallback(this);
414 left_->WhenRange(demon_);
415 right_->WhenRange(demon_);
416 target_var_->WhenBound(demon_);
417 }
418
419 void InitialPropagate() override {
420 if (target_var_->Bound()) {
421 if (target_var_->Min() == 0) {
422 right_->SetMax(left_->Max() - 1);
423 left_->SetMin(right_->Min() + 1);
424 } else { // Var is true.
425 right_->SetMin(left_->Min());
426 left_->SetMax(right_->Max());
427 }
428 } else if (right_->Min() >= left_->Max()) {
429 demon_->inhibit(solver());
430 target_var_->SetValue(1);
431 } else if (right_->Max() < left_->Min()) {
432 demon_->inhibit(solver());
433 target_var_->SetValue(0);
434 }
435 }
436
437 std::string DebugString() const override {
438 return absl::StrFormat("IsLessOrEqualCt(%s, %s, %s)", left_->DebugString(),
439 right_->DebugString(), target_var_->DebugString());
440 }
441
442 void Accept(ModelVisitor* const visitor) const override {
443 visitor->BeginVisitConstraint(ModelVisitor::kIsLessOrEqual, this);
444 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
445 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
446 right_);
447 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
449 visitor->EndVisitConstraint(ModelVisitor::kIsLessOrEqual, this);
450 }
451
452 private:
453 IntExpr* const left_;
454 IntExpr* const right_;
455 Demon* demon_;
456};
457
458class IsLessCt : public CastConstraint {
459 public:
460 IsLessCt(Solver* const s, IntExpr* const l, IntExpr* const r, IntVar* const b)
461 : CastConstraint(s, b), left_(l), right_(r), demon_(nullptr) {}
462
463 ~IsLessCt() override {}
464
465 void Post() override {
466 demon_ = solver()->MakeConstraintInitialPropagateCallback(this);
467 left_->WhenRange(demon_);
468 right_->WhenRange(demon_);
469 target_var_->WhenBound(demon_);
470 }
471
472 void InitialPropagate() override {
473 if (target_var_->Bound()) {
474 if (target_var_->Min() == 0) {
475 right_->SetMax(left_->Max());
476 left_->SetMin(right_->Min());
477 } else { // Var is true.
478 right_->SetMin(left_->Min() + 1);
479 left_->SetMax(right_->Max() - 1);
480 }
481 } else if (right_->Min() > left_->Max()) {
482 demon_->inhibit(solver());
483 target_var_->SetValue(1);
484 } else if (right_->Max() <= left_->Min()) {
485 demon_->inhibit(solver());
486 target_var_->SetValue(0);
487 }
488 }
489
490 std::string DebugString() const override {
491 return absl::StrFormat("IsLessCt(%s, %s, %s)", left_->DebugString(),
492 right_->DebugString(), target_var_->DebugString());
493 }
494
495 void Accept(ModelVisitor* const visitor) const override {
496 visitor->BeginVisitConstraint(ModelVisitor::kIsLess, this);
497 visitor->VisitIntegerExpressionArgument(ModelVisitor::kLeftArgument, left_);
498 visitor->VisitIntegerExpressionArgument(ModelVisitor::kRightArgument,
499 right_);
500 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
502 visitor->EndVisitConstraint(ModelVisitor::kIsLess, this);
503 }
504
505 private:
506 IntExpr* const left_;
507 IntExpr* const right_;
508 Demon* demon_;
509};
510} // namespace
511
512Constraint* Solver::MakeEquality(IntExpr* const l, IntExpr* const r) {
513 CHECK(l != nullptr) << "left expression nullptr, maybe a bad cast";
514 CHECK(r != nullptr) << "left expression nullptr, maybe a bad cast";
515 CHECK_EQ(this, l->solver());
516 CHECK_EQ(this, r->solver());
517 if (l->Bound()) {
518 return MakeEquality(r, l->Min());
519 } else if (r->Bound()) {
520 return MakeEquality(l, r->Min());
521 } else {
522 return RevAlloc(new RangeEquality(this, l, r));
523 }
524}
525
526Constraint* Solver::MakeLessOrEqual(IntExpr* const l, IntExpr* const r) {
527 CHECK(l != nullptr) << "left expression nullptr, maybe a bad cast";
528 CHECK(r != nullptr) << "left expression nullptr, maybe a bad cast";
529 CHECK_EQ(this, l->solver());
530 CHECK_EQ(this, r->solver());
531 if (l == r) {
532 return MakeTrueConstraint();
533 } else if (l->Bound()) {
534 return MakeGreaterOrEqual(r, l->Min());
535 } else if (r->Bound()) {
536 return MakeLessOrEqual(l, r->Min());
537 } else {
538 return RevAlloc(new RangeLessOrEqual(this, l, r));
539 }
540}
541
542Constraint* Solver::MakeGreaterOrEqual(IntExpr* const l, IntExpr* const r) {
543 return MakeLessOrEqual(r, l);
544}
545
546Constraint* Solver::MakeLess(IntExpr* const l, IntExpr* const r) {
547 CHECK(l != nullptr) << "left expression nullptr, maybe a bad cast";
548 CHECK(r != nullptr) << "left expression nullptr, maybe a bad cast";
549 CHECK_EQ(this, l->solver());
550 CHECK_EQ(this, r->solver());
551 if (l->Bound()) {
552 return MakeGreater(r, l->Min());
553 } else if (r->Bound()) {
554 return MakeLess(l, r->Min());
555 } else {
556 return RevAlloc(new RangeLess(this, l, r));
557 }
558}
559
560Constraint* Solver::MakeGreater(IntExpr* const l, IntExpr* const r) {
561 return MakeLess(r, l);
562}
563
564Constraint* Solver::MakeNonEquality(IntExpr* const l, IntExpr* const r) {
565 CHECK(l != nullptr) << "left expression nullptr, maybe a bad cast";
566 CHECK(r != nullptr) << "left expression nullptr, maybe a bad cast";
567 CHECK_EQ(this, l->solver());
568 CHECK_EQ(this, r->solver());
569 if (l->Bound()) {
570 return MakeNonEquality(r, l->Min());
571 } else if (r->Bound()) {
572 return MakeNonEquality(l, r->Min());
573 }
574 return RevAlloc(new DiffVar(this, l->Var(), r->Var()));
575}
576
577IntVar* Solver::MakeIsEqualVar(IntExpr* const v1, IntExpr* const v2) {
578 CHECK_EQ(this, v1->solver());
579 CHECK_EQ(this, v2->solver());
580 if (v1->Bound()) {
581 return MakeIsEqualCstVar(v2, v1->Min());
582 } else if (v2->Bound()) {
583 return MakeIsEqualCstVar(v1, v2->Min());
584 }
585 IntExpr* cache = model_cache_->FindExprExprExpression(
586 v1, v2, ModelCache::EXPR_EXPR_IS_EQUAL);
587 if (cache == nullptr) {
588 cache = model_cache_->FindExprExprExpression(
589 v2, v1, ModelCache::EXPR_EXPR_IS_EQUAL);
590 }
591 if (cache != nullptr) {
592 return cache->Var();
593 } else {
594 IntVar* boolvar = nullptr;
595 IntExpr* reverse_cache = model_cache_->FindExprExprExpression(
596 v1, v2, ModelCache::EXPR_EXPR_IS_NOT_EQUAL);
597 if (reverse_cache == nullptr) {
598 reverse_cache = model_cache_->FindExprExprExpression(
599 v2, v1, ModelCache::EXPR_EXPR_IS_NOT_EQUAL);
600 }
601 if (reverse_cache != nullptr) {
602 boolvar = MakeDifference(1, reverse_cache)->Var();
603 } else {
604 std::string name1 = v1->name();
605 if (name1.empty()) {
606 name1 = v1->DebugString();
607 }
608 std::string name2 = v2->name();
609 if (name2.empty()) {
610 name2 = v2->DebugString();
611 }
612 boolvar =
613 MakeBoolVar(absl::StrFormat("IsEqualVar(%s, %s)", name1, name2));
614 AddConstraint(MakeIsEqualCt(v1, v2, boolvar));
615 model_cache_->InsertExprExprExpression(boolvar, v1, v2,
616 ModelCache::EXPR_EXPR_IS_EQUAL);
617 }
618 return boolvar;
619 }
620}
621
622Constraint* Solver::MakeIsEqualCt(IntExpr* const v1, IntExpr* const v2,
623 IntVar* b) {
624 CHECK_EQ(this, v1->solver());
625 CHECK_EQ(this, v2->solver());
626 if (v1->Bound()) {
627 return MakeIsEqualCstCt(v2, v1->Min(), b);
628 } else if (v2->Bound()) {
629 return MakeIsEqualCstCt(v1, v2->Min(), b);
630 }
631 if (b->Bound()) {
632 if (b->Min() == 0) {
633 return MakeNonEquality(v1, v2);
634 } else {
635 return MakeEquality(v1, v2);
636 }
637 }
638 return RevAlloc(new IsEqualCt(this, v1, v2, b));
639}
640
641IntVar* Solver::MakeIsDifferentVar(IntExpr* const v1, IntExpr* const v2) {
642 CHECK_EQ(this, v1->solver());
643 CHECK_EQ(this, v2->solver());
644 if (v1->Bound()) {
645 return MakeIsDifferentCstVar(v2, v1->Min());
646 } else if (v2->Bound()) {
647 return MakeIsDifferentCstVar(v1, v2->Min());
648 }
649 IntExpr* cache = model_cache_->FindExprExprExpression(
650 v1, v2, ModelCache::EXPR_EXPR_IS_NOT_EQUAL);
651 if (cache == nullptr) {
652 cache = model_cache_->FindExprExprExpression(
653 v2, v1, ModelCache::EXPR_EXPR_IS_NOT_EQUAL);
654 }
655 if (cache != nullptr) {
656 return cache->Var();
657 } else {
658 IntVar* boolvar = nullptr;
659 IntExpr* reverse_cache = model_cache_->FindExprExprExpression(
660 v1, v2, ModelCache::EXPR_EXPR_IS_EQUAL);
661 if (reverse_cache == nullptr) {
662 reverse_cache = model_cache_->FindExprExprExpression(
663 v2, v1, ModelCache::EXPR_EXPR_IS_EQUAL);
664 }
665 if (reverse_cache != nullptr) {
666 boolvar = MakeDifference(1, reverse_cache)->Var();
667 } else {
668 std::string name1 = v1->name();
669 if (name1.empty()) {
670 name1 = v1->DebugString();
671 }
672 std::string name2 = v2->name();
673 if (name2.empty()) {
674 name2 = v2->DebugString();
675 }
676 boolvar =
677 MakeBoolVar(absl::StrFormat("IsDifferentVar(%s, %s)", name1, name2));
678 AddConstraint(MakeIsDifferentCt(v1, v2, boolvar));
679 }
680 model_cache_->InsertExprExprExpression(boolvar, v1, v2,
681 ModelCache::EXPR_EXPR_IS_NOT_EQUAL);
682 return boolvar;
683 }
684}
685
686Constraint* Solver::MakeIsDifferentCt(IntExpr* const v1, IntExpr* const v2,
687 IntVar* b) {
688 CHECK_EQ(this, v1->solver());
689 CHECK_EQ(this, v2->solver());
690 if (v1->Bound()) {
691 return MakeIsDifferentCstCt(v2, v1->Min(), b);
692 } else if (v2->Bound()) {
693 return MakeIsDifferentCstCt(v1, v2->Min(), b);
694 }
695 return RevAlloc(new IsDifferentCt(this, v1, v2, b));
696}
697
698IntVar* Solver::MakeIsLessOrEqualVar(IntExpr* const left,
699 IntExpr* const right) {
700 CHECK_EQ(this, left->solver());
701 CHECK_EQ(this, right->solver());
702 if (left->Bound()) {
703 return MakeIsGreaterOrEqualCstVar(right, left->Min());
704 } else if (right->Bound()) {
705 return MakeIsLessOrEqualCstVar(left, right->Min());
706 }
707 IntExpr* const cache = model_cache_->FindExprExprExpression(
708 left, right, ModelCache::EXPR_EXPR_IS_LESS_OR_EQUAL);
709 if (cache != nullptr) {
710 return cache->Var();
711 } else {
712 std::string name1 = left->name();
713 if (name1.empty()) {
714 name1 = left->DebugString();
715 }
716 std::string name2 = right->name();
717 if (name2.empty()) {
718 name2 = right->DebugString();
719 }
720 IntVar* const boolvar =
721 MakeBoolVar(absl::StrFormat("IsLessOrEqual(%s, %s)", name1, name2));
722
723 AddConstraint(RevAlloc(new IsLessOrEqualCt(this, left, right, boolvar)));
724 model_cache_->InsertExprExprExpression(
725 boolvar, left, right, ModelCache::EXPR_EXPR_IS_LESS_OR_EQUAL);
726 return boolvar;
727 }
728}
729
730Constraint* Solver::MakeIsLessOrEqualCt(IntExpr* const left,
731 IntExpr* const right, IntVar* const b) {
732 CHECK_EQ(this, left->solver());
733 CHECK_EQ(this, right->solver());
734 if (left->Bound()) {
735 return MakeIsGreaterOrEqualCstCt(right, left->Min(), b);
736 } else if (right->Bound()) {
737 return MakeIsLessOrEqualCstCt(left, right->Min(), b);
738 }
739 return RevAlloc(new IsLessOrEqualCt(this, left, right, b));
740}
741
742IntVar* Solver::MakeIsLessVar(IntExpr* const left, IntExpr* const right) {
743 CHECK_EQ(this, left->solver());
744 CHECK_EQ(this, right->solver());
745 if (left->Bound()) {
746 return MakeIsGreaterCstVar(right, left->Min());
747 } else if (right->Bound()) {
748 return MakeIsLessCstVar(left, right->Min());
749 }
750 IntExpr* const cache = model_cache_->FindExprExprExpression(
751 left, right, ModelCache::EXPR_EXPR_IS_LESS);
752 if (cache != nullptr) {
753 return cache->Var();
754 } else {
755 std::string name1 = left->name();
756 if (name1.empty()) {
757 name1 = left->DebugString();
758 }
759 std::string name2 = right->name();
760 if (name2.empty()) {
761 name2 = right->DebugString();
762 }
763 IntVar* const boolvar =
764 MakeBoolVar(absl::StrFormat("IsLessOrEqual(%s, %s)", name1, name2));
765
766 AddConstraint(RevAlloc(new IsLessCt(this, left, right, boolvar)));
767 model_cache_->InsertExprExprExpression(boolvar, left, right,
768 ModelCache::EXPR_EXPR_IS_LESS);
769 return boolvar;
770 }
771}
772
773Constraint* Solver::MakeIsLessCt(IntExpr* const left, IntExpr* const right,
774 IntVar* const b) {
775 CHECK_EQ(this, left->solver());
776 CHECK_EQ(this, right->solver());
777 if (left->Bound()) {
778 return MakeIsGreaterCstCt(right, left->Min(), b);
779 } else if (right->Bound()) {
780 return MakeIsLessCstCt(left, right->Min(), b);
781 }
782 return RevAlloc(new IsLessCt(this, left, right, b));
783}
784
785IntVar* Solver::MakeIsGreaterOrEqualVar(IntExpr* const left,
786 IntExpr* const right) {
787 return MakeIsLessOrEqualVar(right, left);
788}
789
790Constraint* Solver::MakeIsGreaterOrEqualCt(IntExpr* const left,
791 IntExpr* const right,
792 IntVar* const b) {
793 return MakeIsLessOrEqualCt(right, left, b);
794}
795
796IntVar* Solver::MakeIsGreaterVar(IntExpr* const left, IntExpr* const right) {
797 return MakeIsLessVar(right, left);
798}
799
800Constraint* Solver::MakeIsGreaterCt(IntExpr* const left, IntExpr* const right,
801 IntVar* const b) {
802 return MakeIsLessCt(right, left, b);
803}
804
805} // namespace operations_research
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
A constraint is the main modeling object.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual IntVar * Var()=0
Creates a variable from the expression.
virtual int64 Min() const =0
The class IntVar is a subset of IntExpr.
IntVar * Var() override
Creates a variable from the expression.
virtual std::string name() const
Object naming.
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
IntervalVar *const target_var_