OR-Tools  8.1
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"
22 #include "ortools/base/logging.h"
23 #include "ortools/constraint_solver/constraint_solver.h"
24 #include "ortools/constraint_solver/constraint_solveri.h"
25 
26 namespace operations_research {
27 
28 //-----------------------------------------------------------------------------
29 // RangeEquality
30 
31 namespace {
32 class 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 
72 class 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 
96 RangeLessOrEqual::RangeLessOrEqual(Solver* const s, IntExpr* const l,
97  IntExpr* const r)
98  : Constraint(s), left_(l), right_(r), demon_(nullptr) {}
99 
100 void RangeLessOrEqual::Post() {
101  demon_ = solver()->MakeConstraintInitialPropagateCallback(this);
102  left_->WhenRange(demon_);
103  right_->WhenRange(demon_);
104 }
105 
106 void 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 
114 std::string RangeLessOrEqual::DebugString() const {
115  return left_->DebugString() + " <= " + right_->DebugString();
116 }
117 
118 //-----------------------------------------------------------------------------
119 // RangeLess
120 
121 class 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 
143 RangeLess::RangeLess(Solver* const s, IntExpr* const l, IntExpr* const r)
144  : Constraint(s), left_(l), right_(r), demon_(nullptr) {}
145 
146 void RangeLess::Post() {
147  demon_ = solver()->MakeConstraintInitialPropagateCallback(this);
148  left_->WhenRange(demon_);
149  right_->WhenRange(demon_);
150 }
151 
152 void 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 
160 std::string RangeLess::DebugString() const {
161  return left_->DebugString() + " < " + right_->DebugString();
162 }
163 
164 //-----------------------------------------------------------------------------
165 // DiffVar
166 
167 class 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 
191 DiffVar::DiffVar(Solver* const s, IntVar* const l, IntVar* const r)
192  : Constraint(s), left_(l), right_(r) {}
193 
194 void 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 
204 void 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 
212 void 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 
220 void DiffVar::InitialPropagate() {
221  if (left_->Bound()) {
222  LeftBound();
223  }
224  if (right_->Bound()) {
225  RightBound();
226  }
227 }
228 
229 std::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 
240 class 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,
315  target_var_);
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 
327 class 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,
394  target_var_);
395  visitor->EndVisitConstraint(ModelVisitor::kIsDifferent, this);
396  }
397 
398  private:
399  IntExpr* const left_;
400  IntExpr* const right_;
401  Demon* range_demon_;
402 };
403 
404 class 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,
448  target_var_);
449  visitor->EndVisitConstraint(ModelVisitor::kIsLessOrEqual, this);
450  }
451 
452  private:
453  IntExpr* const left_;
454  IntExpr* const right_;
455  Demon* demon_;
456 };
457 
458 class 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,
501  target_var_);
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 
512 Constraint* 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 
526 Constraint* 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 
542 Constraint* Solver::MakeGreaterOrEqual(IntExpr* const l, IntExpr* const r) {
543  return MakeLessOrEqual(r, l);
544 }
545 
546 Constraint* 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 
560 Constraint* Solver::MakeGreater(IntExpr* const l, IntExpr* const r) {
561  return MakeLess(r, l);
562 }
563 
564 Constraint* 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 
577 IntVar* 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 
622 Constraint* 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 
641 IntVar* 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 
686 Constraint* 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 
698 IntVar* 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 
730 Constraint* 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 
742 IntVar* 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 
773 Constraint* 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 
785 IntVar* Solver::MakeIsGreaterOrEqualVar(IntExpr* const left,
786  IntExpr* const right) {
787  return MakeIsLessOrEqualVar(right, left);
788 }
789 
790 Constraint* Solver::MakeIsGreaterOrEqualCt(IntExpr* const left,
791  IntExpr* const right,
792  IntVar* const b) {
793  return MakeIsLessOrEqualCt(right, left, b);
794 }
795 
796 IntVar* Solver::MakeIsGreaterVar(IntExpr* const left, IntExpr* const right) {
797  return MakeIsLessVar(right, left);
798 }
799 
800 Constraint* Solver::MakeIsGreaterCt(IntExpr* const left, IntExpr* const right,
801  IntVar* const b) {
802  return MakeIsLessCt(right, left, b);
803 }
804 
805 } // namespace operations_research
operations_research::IntVar
The class IntVar is a subset of IntExpr.
Definition: constraint_solver.h:3992
operations_research::ModelVisitor::kEquality
static const char kEquality[]
Definition: constraint_solver.h:3354
operations_research::PropagationBaseObject::name
virtual std::string name() const
Object naming.
Definition: constraint_solver.cc:2505
logging.h
operations_research::IntExpr::Min
virtual int64 Min() const =0
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
constraint_solveri.h
operations_research::IntExpr::Bound
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
Definition: constraint_solver.h:3857
constraint_solver.h
operations_research::PropagationBaseObject::DebugString
std::string DebugString() const override
Definition: constraint_solver.h:3167
CHECK_EQ
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
target_var_
IntervalVar *const target_var_
Definition: sched_constraints.cc:230
operations_research::Constraint
A constraint is the main modeling object.
Definition: constraint_solver.h:3579
operations_research::ModelVisitor::kLeftArgument
static const char kLeftArgument[]
Definition: constraint_solver.h:3458
operations_research::ModelVisitor::kRightArgument
static const char kRightArgument[]
Definition: constraint_solver.h:3470
b
int64 b
Definition: constraint_solver/table.cc:43
operations_research::IntExpr
The class IntExpr is the base of all integer expressions in constraint programming.
Definition: constraint_solver.h:3831
operations_research::MakeConstraintDemon0
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
Definition: constraint_solveri.h:525
operations_research::PropagationBaseObject::solver
Solver * solver() const
Definition: constraint_solver.h:3174
CHECK
#define CHECK(condition)
Definition: base/logging.h:495
operations_research::IntExpr::Var
virtual IntVar * Var()=0
Creates a variable from the expression.
operations_research::IntVar::Var
IntVar * Var() override
Creates a variable from the expression.
Definition: constraint_solver.h:3999
operations_research::ModelVisitor::kLessOrEqual
static const char kLessOrEqual[]
Definition: constraint_solver.h:3374