OR-Tools  8.2
constraints.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#include <string.h>
15
16#include <algorithm>
17#include <memory>
18#include <string>
19#include <utility>
20#include <vector>
21
22#include "absl/strings/str_cat.h"
23#include "absl/strings/str_format.h"
30
31namespace operations_research {
32
35 "InitialPropagate");
36}
37
39 Constraint* const ct) {
41 "InitialPropagate");
42}
43
44namespace {
45class ActionDemon : public Demon {
46 public:
47 explicit ActionDemon(const Solver::Action& action) : action_(action) {
48 CHECK(action != nullptr);
49 }
50
51 ~ActionDemon() override {}
52
53 void Run(Solver* const solver) override { action_(solver); }
54
55 private:
56 Solver::Action action_;
57};
58
59class ClosureDemon : public Demon {
60 public:
61 explicit ClosureDemon(const Solver::Closure& closure) : closure_(closure) {
62 CHECK(closure != nullptr);
63 }
64
65 ~ClosureDemon() override {}
66
67 void Run(Solver* const solver) override { closure_(); }
68
69 private:
70 Solver::Closure closure_;
71};
72
73// ----- True and False Constraint -----
74
75class TrueConstraint : public Constraint {
76 public:
77 explicit TrueConstraint(Solver* const s) : Constraint(s) {}
78 ~TrueConstraint() override {}
79
80 void Post() override {}
81 void InitialPropagate() override {}
82 std::string DebugString() const override { return "TrueConstraint()"; }
83
84 void Accept(ModelVisitor* const visitor) const override {
85 visitor->BeginVisitConstraint(ModelVisitor::kTrueConstraint, this);
86 visitor->EndVisitConstraint(ModelVisitor::kTrueConstraint, this);
87 }
88 IntVar* Var() override { return solver()->MakeIntConst(1); }
89};
90
91class FalseConstraint : public Constraint {
92 public:
93 explicit FalseConstraint(Solver* const s) : Constraint(s) {}
94 FalseConstraint(Solver* const s, const std::string& explanation)
95 : Constraint(s), explanation_(explanation) {}
96 ~FalseConstraint() override {}
97
98 void Post() override {}
99 void InitialPropagate() override { solver()->Fail(); }
100 std::string DebugString() const override {
101 return absl::StrCat("FalseConstraint(", explanation_, ")");
102 }
103
104 void Accept(ModelVisitor* const visitor) const override {
105 visitor->BeginVisitConstraint(ModelVisitor::kFalseConstraint, this);
106 visitor->EndVisitConstraint(ModelVisitor::kFalseConstraint, this);
107 }
108 IntVar* Var() override { return solver()->MakeIntConst(0); }
109
110 private:
111 const std::string explanation_;
112};
113
114// ----- Map Variable Domain to Boolean Var Array -----
115// TODO(user) : optimize constraint to avoid ping pong.
116// After a boolvar is set to 0, we remove the value from the var.
117// There is no need to rescan the var to find the hole if the size at the end of
118// UpdateActive() is the same as the size at the beginning of VarDomain().
119
120class MapDomain : public Constraint {
121 public:
122 MapDomain(Solver* const s, IntVar* const var,
123 const std::vector<IntVar*>& actives)
124 : Constraint(s), var_(var), actives_(actives) {
125 holes_ = var->MakeHoleIterator(true);
126 }
127
128 ~MapDomain() override {}
129
130 void Post() override {
131 Demon* vd = MakeConstraintDemon0(solver(), this, &MapDomain::VarDomain,
132 "VarDomain");
133 var_->WhenDomain(vd);
134 Demon* vb =
135 MakeConstraintDemon0(solver(), this, &MapDomain::VarBound, "VarBound");
136 var_->WhenBound(vb);
137 std::unique_ptr<IntVarIterator> domain_it(
138 var_->MakeDomainIterator(/*reversible=*/false));
139 for (const int64 index : InitAndGetValues(domain_it.get())) {
140 if (index >= 0 && index < actives_.size() && !actives_[index]->Bound()) {
141 Demon* d = MakeConstraintDemon1(
142 solver(), this, &MapDomain::UpdateActive, "UpdateActive", index);
143 actives_[index]->WhenDomain(d);
144 }
145 }
146 }
147
148 void InitialPropagate() override {
149 for (int i = 0; i < actives_.size(); ++i) {
150 actives_[i]->SetRange(int64{0}, int64{1});
151 if (!var_->Contains(i)) {
152 actives_[i]->SetValue(0);
153 } else if (actives_[i]->Max() == 0LL) {
154 var_->RemoveValue(i);
155 }
156 if (actives_[i]->Min() == 1LL) {
157 var_->SetValue(i);
158 }
159 }
160 if (var_->Bound()) {
161 VarBound();
162 }
163 }
164
165 void UpdateActive(int64 index) {
166 IntVar* const act = actives_[index];
167 if (act->Max() == 0) {
168 var_->RemoveValue(index);
169 } else if (act->Min() == 1) {
170 var_->SetValue(index);
171 }
172 }
173
174 void VarDomain() {
175 const int64 oldmin = var_->OldMin();
176 const int64 oldmax = var_->OldMax();
177 const int64 vmin = var_->Min();
178 const int64 vmax = var_->Max();
179 const int64 size = actives_.size();
180 for (int64 j = std::max(oldmin, int64{0}); j < std::min(vmin, size); ++j) {
181 actives_[j]->SetValue(0);
182 }
183 for (const int64 j : InitAndGetValues(holes_)) {
184 if (j >= 0 && j < size) {
185 actives_[j]->SetValue(0);
186 }
187 }
188 for (int64 j = std::max(vmax + int64{1}, int64{0});
189 j <= std::min(oldmax, size - int64{1}); ++j) {
190 actives_[j]->SetValue(int64{0});
191 }
192 }
193
194 void VarBound() {
195 const int64 val = var_->Min();
196 if (val >= 0 && val < actives_.size()) {
197 actives_[val]->SetValue(1);
198 }
199 }
200 std::string DebugString() const override {
201 return absl::StrFormat("MapDomain(%s, [%s])", var_->DebugString(),
202 JoinDebugStringPtr(actives_, ", "));
203 }
204
205 void Accept(ModelVisitor* const visitor) const override {
206 visitor->BeginVisitConstraint(ModelVisitor::kMapDomain, this);
207 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
208 var_);
209 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
210 actives_);
211 visitor->EndVisitConstraint(ModelVisitor::kMapDomain, this);
212 }
213
214 private:
215 IntVar* const var_;
216 std::vector<IntVar*> actives_;
217 IntVarIterator* holes_;
218};
219
220// ----- Lex constraint -----
221
222class LexicalLess : public Constraint {
223 public:
224 LexicalLess(Solver* const s, const std::vector<IntVar*>& left,
225 const std::vector<IntVar*>& right, bool strict)
226 : Constraint(s),
227 left_(left),
228 right_(right),
229 active_var_(0),
230 strict_(strict),
231 demon_(nullptr) {
232 CHECK_EQ(left.size(), right.size());
233 }
234
235 ~LexicalLess() override {}
236
237 void Post() override {
238 const int position = JumpEqualVariables(0);
239 active_var_.SetValue(solver(), position);
240 if (position < left_.size()) {
241 demon_ = solver()->MakeConstraintInitialPropagateCallback(this);
242 left_[position]->WhenRange(demon_);
243 right_[position]->WhenRange(demon_);
244 }
245 }
246
247 void InitialPropagate() override {
248 const int position = JumpEqualVariables(active_var_.Value());
249 if (position >= left_.size()) {
250 if (strict_) {
251 solver()->Fail();
252 }
253 return;
254 }
255 if (position != active_var_.Value()) {
256 left_[position]->WhenRange(demon_);
257 right_[position]->WhenRange(demon_);
258 active_var_.SetValue(solver(), position);
259 }
260 const int next_non_equal = JumpEqualVariables(position + 1);
261 if ((strict_ && next_non_equal == left_.size()) ||
262 (next_non_equal < left_.size() &&
263 left_[next_non_equal]->Min() > right_[next_non_equal]->Max())) {
264 // We need to be strict if we are the last in the array, or if
265 // the next one is impossible.
266 left_[position]->SetMax(right_[position]->Max() - 1);
267 right_[position]->SetMin(left_[position]->Min() + 1);
268 } else {
269 left_[position]->SetMax(right_[position]->Max());
270 right_[position]->SetMin(left_[position]->Min());
271 }
272 }
273
274 std::string DebugString() const override {
275 return absl::StrFormat(
276 "%s([%s], [%s])", strict_ ? "LexicalLess" : "LexicalLessOrEqual",
277 JoinDebugStringPtr(left_, ", "), JoinDebugStringPtr(right_, ", "));
278 }
279
280 void Accept(ModelVisitor* const visitor) const override {
281 visitor->BeginVisitConstraint(ModelVisitor::kLexLess, this);
282 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kLeftArgument,
283 left_);
284 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kRightArgument,
285 right_);
286 visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, strict_);
287 visitor->EndVisitConstraint(ModelVisitor::kLexLess, this);
288 }
289
290 private:
291 int JumpEqualVariables(int start_position) const {
292 int position = start_position;
293 while (position < left_.size() && left_[position]->Bound() &&
294 right_[position]->Bound() &&
295 left_[position]->Min() == right_[position]->Min()) {
296 position++;
297 }
298 return position;
299 }
300
301 std::vector<IntVar*> left_;
302 std::vector<IntVar*> right_;
303 NumericalRev<int> active_var_;
304 const bool strict_;
305 Demon* demon_;
306};
307
308// ----- Inverse permutation constraint -----
309
310class InversePermutationConstraint : public Constraint {
311 public:
312 InversePermutationConstraint(Solver* const s,
313 const std::vector<IntVar*>& left,
314 const std::vector<IntVar*>& right)
315 : Constraint(s),
316 left_(left),
317 right_(right),
318 left_hole_iterators_(left.size()),
319 left_domain_iterators_(left_.size()),
320 right_hole_iterators_(right_.size()),
321 right_domain_iterators_(right_.size()) {
322 CHECK_EQ(left_.size(), right_.size());
323 for (int i = 0; i < left_.size(); ++i) {
324 left_hole_iterators_[i] = left_[i]->MakeHoleIterator(true);
325 left_domain_iterators_[i] = left_[i]->MakeDomainIterator(true);
326 right_hole_iterators_[i] = right_[i]->MakeHoleIterator(true);
327 right_domain_iterators_[i] = right_[i]->MakeDomainIterator(true);
328 }
329 }
330
331 ~InversePermutationConstraint() override {}
332
333 void Post() override {
334 for (int i = 0; i < left_.size(); ++i) {
335 Demon* const left_demon = MakeConstraintDemon1(
336 solver(), this,
337 &InversePermutationConstraint::PropagateHolesOfLeftVarToRight,
338 "PropagateHolesOfLeftVarToRight", i);
339 left_[i]->WhenDomain(left_demon);
340 Demon* const right_demon = MakeConstraintDemon1(
341 solver(), this,
342 &InversePermutationConstraint::PropagateHolesOfRightVarToLeft,
343 "PropagateHolesOfRightVarToLeft", i);
344 right_[i]->WhenDomain(right_demon);
345 }
346 solver()->AddConstraint(
347 solver()->MakeAllDifferent(left_, /*stronger_propagation=*/false));
348 solver()->AddConstraint(
349 solver()->MakeAllDifferent(right_, /*stronger_propagation=*/false));
350 }
351
352 void InitialPropagate() override {
353 const int size = left_.size();
354 for (int i = 0; i < size; ++i) {
355 left_[i]->SetRange(0, size - 1);
356 right_[i]->SetRange(0, size - 1);
357 }
358 for (int i = 0; i < size; ++i) {
359 PropagateDomain(i, left_[i], left_domain_iterators_[i], right_);
360 PropagateDomain(i, right_[i], right_domain_iterators_[i], left_);
361 }
362 }
363
364 void PropagateHolesOfLeftVarToRight(int index) {
365 PropagateHoles(index, left_[index], left_hole_iterators_[index], right_);
366 }
367
368 void PropagateHolesOfRightVarToLeft(int index) {
369 PropagateHoles(index, right_[index], right_hole_iterators_[index], left_);
370 }
371
372 std::string DebugString() const override {
373 return absl::StrFormat("InversePermutationConstraint([%s], [%s])",
374 JoinDebugStringPtr(left_, ", "),
375 JoinDebugStringPtr(right_, ", "));
376 }
377
378 void Accept(ModelVisitor* const visitor) const override {
379 visitor->BeginVisitConstraint(ModelVisitor::kInversePermutation, this);
380 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kLeftArgument,
381 left_);
382 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kRightArgument,
383 right_);
384 visitor->EndVisitConstraint(ModelVisitor::kInversePermutation, this);
385 }
386
387 private:
388 // See PropagateHolesOfLeftVarToRight() and PropagateHolesOfRightVarToLeft().
389 void PropagateHoles(int index, IntVar* const var, IntVarIterator* const holes,
390 const std::vector<IntVar*>& inverse) {
391 const int64 oldmin = std::max(var->OldMin(), int64{0});
392 const int64 oldmax =
393 std::min(var->OldMax(), static_cast<int64>(left_.size() - 1));
394 const int64 vmin = var->Min();
395 const int64 vmax = var->Max();
396 for (int64 value = oldmin; value < vmin; ++value) {
397 inverse[value]->RemoveValue(index);
398 }
399 for (const int64 hole : InitAndGetValues(holes)) {
400 if (hole >= 0 && hole < left_.size()) {
401 inverse[hole]->RemoveValue(index);
402 }
403 }
404 for (int64 value = vmax + 1; value <= oldmax; ++value) {
405 inverse[value]->RemoveValue(index);
406 }
407 }
408
409 void PropagateDomain(int index, IntVar* const var,
410 IntVarIterator* const domain,
411 const std::vector<IntVar*>& inverse) {
412 // Iterators are not safe w.r.t. removal. Postponing deletions.
413 tmp_removed_values_.clear();
414 for (const int64 value : InitAndGetValues(domain)) {
415 if (!inverse[value]->Contains(index)) {
416 tmp_removed_values_.push_back(value);
417 }
418 }
419 // Once we've finished iterating over the domain, we may call
420 // RemoveValues().
421 if (!tmp_removed_values_.empty()) {
422 var->RemoveValues(tmp_removed_values_);
423 }
424 }
425
426 std::vector<IntVar*> left_;
427 std::vector<IntVar*> right_;
428 std::vector<IntVarIterator*> left_hole_iterators_;
429 std::vector<IntVarIterator*> left_domain_iterators_;
430 std::vector<IntVarIterator*> right_hole_iterators_;
431 std::vector<IntVarIterator*> right_domain_iterators_;
432
433 // used only in PropagateDomain().
434 std::vector<int64> tmp_removed_values_;
435};
436
437// Index of first Max Value
438
439class IndexOfFirstMaxValue : public Constraint {
440 public:
441 IndexOfFirstMaxValue(Solver* solver, IntVar* index,
442 const std::vector<IntVar*>& vars)
443 : Constraint(solver), index_(index), vars_(vars) {}
444
445 ~IndexOfFirstMaxValue() override {}
446
447 void Post() override {
448 Demon* const demon =
449 solver()->MakeDelayedConstraintInitialPropagateCallback(this);
450 index_->WhenRange(demon);
451 for (IntVar* const var : vars_) {
452 var->WhenRange(demon);
453 }
454 }
455
456 void InitialPropagate() override {
457 const int64 vsize = vars_.size();
458 const int64 imin = std::max(int64{0}, index_->Min());
459 const int64 imax = std::min(vsize - 1, index_->Max());
460 int64 max_max = kint64min;
461 int64 max_min = kint64min;
462
463 // Compute min and max value in the current interval covered by index_.
464 for (int i = imin; i <= imax; ++i) {
465 max_max = std::max(max_max, vars_[i]->Max());
466 max_min = std::max(max_min, vars_[i]->Min());
467 }
468
469 // Propagate the fact that the first maximum value belongs to the
470 // [imin..imax].
471 for (int i = 0; i < imin; ++i) {
472 vars_[i]->SetMax(max_max - 1);
473 }
474 for (int i = imax + 1; i < vsize; ++i) {
475 vars_[i]->SetMax(max_max);
476 }
477
478 // Shave bounds for index_.
479 int64 min_index = imin;
480 while (vars_[min_index]->Max() < max_min) {
481 min_index++;
482 }
483 int64 max_index = imax;
484 while (vars_[max_index]->Max() < max_min) {
485 max_index--;
486 }
487 index_->SetRange(min_index, max_index);
488 }
489
490 std::string DebugString() const override {
491 return absl::StrFormat("IndexMax(%s, [%s])", index_->DebugString(),
492 JoinDebugStringPtr(vars_, ", "));
493 }
494
495 void Accept(ModelVisitor* const visitor) const override {
496 // TODO(user): Implement me.
497 }
498
499 private:
500 IntVar* const index_;
501 const std::vector<IntVar*> vars_;
502};
503} // namespace
504
505// ----- API -----
506
508 return RevAlloc(new ActionDemon(action));
509}
510
512 return RevAlloc(new ClosureDemon(closure));
513}
514
516 DCHECK(true_constraint_ != nullptr);
517 return true_constraint_;
518}
519
521 DCHECK(false_constraint_ != nullptr);
522 return false_constraint_;
523}
524Constraint* Solver::MakeFalseConstraint(const std::string& explanation) {
525 return RevAlloc(new FalseConstraint(this, explanation));
526}
527
528void Solver::InitCachedConstraint() {
529 DCHECK(true_constraint_ == nullptr);
530 true_constraint_ = RevAlloc(new TrueConstraint(this));
531 DCHECK(false_constraint_ == nullptr);
532 false_constraint_ = RevAlloc(new FalseConstraint(this));
533}
534
536 const std::vector<IntVar*>& actives) {
537 return RevAlloc(new MapDomain(this, var, actives));
538}
539
540Constraint* Solver::MakeLexicalLess(const std::vector<IntVar*>& left,
541 const std::vector<IntVar*>& right) {
542 return RevAlloc(new LexicalLess(this, left, right, true));
543}
544
545Constraint* Solver::MakeLexicalLessOrEqual(const std::vector<IntVar*>& left,
546 const std::vector<IntVar*>& right) {
547 return RevAlloc(new LexicalLess(this, left, right, false));
548}
549
551 const std::vector<IntVar*>& left, const std::vector<IntVar*>& right) {
552 return RevAlloc(new InversePermutationConstraint(this, left, right));
553}
554
556 IntVar* index, const std::vector<IntVar*>& vars) {
557 return RevAlloc(new IndexOfFirstMaxValue(this, index, vars));
558}
559
561 IntVar* index, const std::vector<IntVar*>& vars) {
562 std::vector<IntVar*> opp_vars(vars.size());
563 for (int i = 0; i < vars.size(); ++i) {
564 opp_vars[i] = MakeOpposite(vars[i])->Var();
565 }
566 return RevAlloc(new IndexOfFirstMaxValue(this, index, opp_vars));
567}
568} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
const std::vector< IntVar * > vars_
Definition: alldiff_cst.cc:43
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define DCHECK(condition)
Definition: base/logging.h:884
A constraint is the main modeling object.
virtual void InitialPropagate()=0
This method performs the initial propagation of the constraint.
A Demon is the base element of a propagation queue.
virtual IntVar * Var()=0
Creates a variable from the expression.
The class IntVar is a subset of IntExpr.
void SetValue(Solver *const s, const T &val)
Constraint * MakeMapDomain(IntVar *const var, const std::vector< IntVar * > &actives)
This constraint maps the domain of 'var' onto the array of variables 'actives'.
Definition: constraints.cc:535
Constraint * MakeFalseConstraint()
This constraint always fails.
Definition: constraints.cc:520
Constraint * MakeIndexOfFirstMinValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
Creates a constraint that binds the index variable to the index of the first variable with the minimu...
Definition: constraints.cc:560
Demon * MakeActionDemon(Action action)
Creates a demon from a callback.
Definition: constraints.cc:507
Constraint * MakeLexicalLess(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that left is lexicographically less than right.
Definition: constraints.cc:540
Demon * MakeClosureDemon(Closure closure)
!defined(SWIG)
Definition: constraints.cc:511
IntExpr * MakeOpposite(IntExpr *const expr)
-expr
Demon * MakeConstraintInitialPropagateCallback(Constraint *const ct)
This method is a specialized case of the MakeConstraintDemon method to call the InitiatePropagate of ...
Definition: constraints.cc:33
Constraint * MakeTrueConstraint()
This constraint always succeeds.
Definition: constraints.cc:515
Constraint * MakeLexicalLessOrEqual(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that left is lexicographically less than or equal to right.
Definition: constraints.cc:545
Constraint * MakeInversePermutationConstraint(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that 'left' and 'right' both represent permutations of [0....
Definition: constraints.cc:550
Demon * MakeDelayedConstraintInitialPropagateCallback(Constraint *const ct)
This method is a specialized case of the MakeConstraintDemon method to call the InitiatePropagate of ...
Definition: constraints.cc:38
std::function< void()> Closure
std::function< void(Solver *)> Action
Constraint * MakeIndexOfFirstMaxValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
Creates a constraint that binds the index variable to the index of the first variable with the maximu...
Definition: constraints.cc:555
T * RevAlloc(T *object)
Registers the given object as being reversible.
std::vector< IntVarIterator * > holes_
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
static const int64 kint64min
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)
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:45
int index
Definition: pack.cc:508