OR-Tools  8.2
sched_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// This file contains implementations of several scheduling constraints.
15// The implemented constraints are:
16//
17// * Cover constraints: ensure that an interval is the convex hull of
18// a set of interval variables. This includes the performed status
19// (one interval performed implies the cover var performed, all
20// intervals unperformed implies the cover var unperformed, cover
21// var unperformed implies all intervals unperformed, cover var
22// performed implis at least one interval performed).
23
24#include <string>
25#include <vector>
26
27#include "absl/strings/str_format.h"
30#include "ortools/base/macros.h"
34
35namespace operations_research {
36namespace {
37class TreeArrayConstraint : public Constraint {
38 public:
39 enum PerformedStatus { UNPERFORMED, PERFORMED, UNDECIDED };
40
41 TreeArrayConstraint(Solver* const solver,
42 const std::vector<IntervalVar*>& vars,
43 IntervalVar* const target_var)
44 : Constraint(solver),
45 vars_(vars),
46 target_var_(target_var),
47 block_size_(solver->parameters().array_split_size()) {
48 std::vector<int> lengths;
49 lengths.push_back(vars_.size());
50 while (lengths.back() > 1) {
51 const int current = lengths.back();
52 lengths.push_back((current + block_size_ - 1) / block_size_);
53 }
54 tree_.resize(lengths.size());
55 for (int i = 0; i < lengths.size(); ++i) {
56 tree_[i].resize(lengths[lengths.size() - i - 1]);
57 }
58 DCHECK_GE(tree_.size(), 1);
59 DCHECK_EQ(1, tree_[0].size());
60 root_node_ = &tree_[0][0];
61 }
62
63 std::string DebugStringInternal(const std::string& name) const {
64 return absl::StrFormat("Cover(%s) == %s", JoinDebugStringPtr(vars_, ", "),
65 target_var_->DebugString());
66 }
67
68 void AcceptInternal(const std::string& name,
69 ModelVisitor* const visitor) const {
70 visitor->BeginVisitConstraint(name, this);
71 visitor->VisitIntervalArrayArgument(ModelVisitor::kIntervalsArgument,
72 vars_);
73 visitor->VisitIntervalArgument(ModelVisitor::kTargetArgument, target_var_);
74 visitor->EndVisitConstraint(name, this);
75 }
76
77 // Reduce the range of a given node (interval, state).
78 void ReduceDomain(int depth, int position, int64 new_start_min,
79 int64 new_start_max, int64 new_end_min, int64 new_end_max,
80 PerformedStatus performed) {
81 NodeInfo* const info = &tree_[depth][position];
82 if (new_start_min > info->start_min.Value()) {
83 info->start_min.SetValue(solver(), new_start_min);
84 }
85 if (new_start_max < info->start_max.Value()) {
86 info->start_max.SetValue(solver(), new_start_max);
87 }
88 if (new_end_min > info->end_min.Value()) {
89 info->end_min.SetValue(solver(), new_end_min);
90 }
91 if (new_end_max < info->end_max.Value()) {
92 info->end_max.SetValue(solver(), new_end_max);
93 }
94 if (performed != UNDECIDED) {
95 CHECK(performed == info->performed.Value() ||
96 info->performed.Value() == UNDECIDED);
97 info->performed.SetValue(solver(), performed);
98 }
99 }
100
101 void InitLeaf(int position, int64 start_min, int64 start_max, int64 end_min,
102 int64 end_max, PerformedStatus performed) {
103 InitNode(MaxDepth(), position, start_min, start_max, end_min, end_max,
104 performed);
105 }
106
107 void InitNode(int depth, int position, int64 start_min, int64 start_max,
108 int64 end_min, int64 end_max, PerformedStatus performed) {
109 tree_[depth][position].start_min.SetValue(solver(), start_min);
110 tree_[depth][position].start_max.SetValue(solver(), start_max);
111 tree_[depth][position].end_min.SetValue(solver(), end_min);
112 tree_[depth][position].end_max.SetValue(solver(), end_max);
113 tree_[depth][position].performed.SetValue(solver(),
114 static_cast<int>(performed));
115 }
116
117 int64 StartMin(int depth, int position) const {
118 return tree_[depth][position].start_min.Value();
119 }
120
121 int64 StartMax(int depth, int position) const {
122 return tree_[depth][position].start_max.Value();
123 }
124
125 int64 EndMax(int depth, int position) const {
126 return tree_[depth][position].end_max.Value();
127 }
128
129 int64 EndMin(int depth, int position) const {
130 return tree_[depth][position].end_min.Value();
131 }
132
133 PerformedStatus Performed(int depth, int position) const {
134 const int p = tree_[depth][position].performed.Value();
135 CHECK_GE(p, UNPERFORMED);
136 CHECK_LE(p, UNDECIDED);
137 return static_cast<PerformedStatus>(p);
138 }
139
140 int64 RootStartMin() const { return root_node_->start_min.Value(); }
141
142 int64 RootStartMax() const { return root_node_->start_max.Value(); }
143
144 int64 RootEndMin() const { return root_node_->end_min.Value(); }
145
146 int64 RootEndMax() const { return root_node_->end_max.Value(); }
147
148 PerformedStatus RootPerformed() const { return Performed(0, 0); }
149
150 // This getters query first if the var can be performed, and will
151 // return a default value if not.
152 int64 VarStartMin(int position) const {
153 return vars_[position]->MayBePerformed() ? vars_[position]->StartMin() : 0;
154 }
155
156 int64 VarStartMax(int position) const {
157 return vars_[position]->MayBePerformed() ? vars_[position]->StartMax() : 0;
158 }
159
160 int64 VarEndMin(int position) const {
161 return vars_[position]->MayBePerformed() ? vars_[position]->EndMin() : 0;
162 }
163
164 int64 VarEndMax(int position) const {
165 return vars_[position]->MayBePerformed() ? vars_[position]->EndMax() : 0;
166 }
167
168 int64 TargetVarStartMin() const {
169 return target_var_->MayBePerformed() ? target_var_->StartMin() : 0;
170 }
171
172 int64 TargetVarStartMax() const {
173 return target_var_->MayBePerformed() ? target_var_->StartMax() : 0;
174 }
175
176 int64 TargetVarEndMin() const {
177 return target_var_->MayBePerformed() ? target_var_->EndMin() : 0;
178 }
179
180 int64 TargetVarEndMax() const {
181 return target_var_->MayBePerformed() ? target_var_->EndMax() : 0;
182 }
183
184 // Returns the performed status of the 'position' nth interval
185 // var of the problem.
186 PerformedStatus VarPerformed(int position) const {
187 IntervalVar* const var = vars_[position];
188 if (var->MustBePerformed()) {
189 return PERFORMED;
190 } else if (var->MayBePerformed()) {
191 return UNDECIDED;
192 } else {
193 return UNPERFORMED;
194 }
195 }
196
197 // Returns the performed status of the target var.
198 PerformedStatus TargetVarPerformed() const {
199 if (target_var_->MustBePerformed()) {
200 return PERFORMED;
201 } else if (target_var_->MayBePerformed()) {
202 return UNDECIDED;
203 } else {
204 return UNPERFORMED;
205 }
206 }
207
208 // Returns the position of the parent of a node with a given position.
209 int Parent(int position) const { return position / block_size_; }
210
211 // Returns the index of the first child of a node at a given 'position'.
212 int ChildStart(int position) const { return position * block_size_; }
213
214 // Returns the index of the last child of a node at a given
215 // 'position'. The depth is needed to make sure that do not overlap
216 // the width of the tree at a given depth.
217 int ChildEnd(int depth, int position) const {
218 DCHECK_LT(depth + 1, tree_.size());
219 return std::min((position + 1) * block_size_ - 1, Width(depth + 1) - 1);
220 }
221
222 bool IsLeaf(int depth) const { return depth == MaxDepth(); }
223
224 int MaxDepth() const { return tree_.size() - 1; }
225
226 int Width(int depth) const { return tree_[depth].size(); }
227
228 protected:
229 const std::vector<IntervalVar*> vars_;
230 IntervalVar* const target_var_;
231
232 private:
233 struct NodeInfo {
234 NodeInfo()
235 : start_min(0),
236 start_max(0),
237 end_min(0),
238 end_max(0),
239 performed(UNDECIDED) {}
240
241 Rev<int64> start_min;
242 Rev<int64> start_max;
243 Rev<int64> end_min;
244 Rev<int64> end_max;
245 Rev<int> performed;
246 };
247
248 std::vector<std::vector<NodeInfo> > tree_;
249 const int block_size_;
250 NodeInfo* root_node_;
251};
252
253// This constraint implements cover(vars) == cover_var.
254class CoverConstraint : public TreeArrayConstraint {
255 public:
256 CoverConstraint(Solver* const solver, const std::vector<IntervalVar*>& vars,
257 IntervalVar* const cover_var)
258 : TreeArrayConstraint(solver, vars, cover_var), cover_demon_(nullptr) {}
259
260 ~CoverConstraint() override {}
261
262 void Post() override {
263 for (int i = 0; i < vars_.size(); ++i) {
264 Demon* const demon = MakeConstraintDemon1(
265 solver(), this, &CoverConstraint::LeafChanged, "LeafChanged", i);
266 vars_[i]->WhenStartRange(demon);
267 vars_[i]->WhenEndRange(demon);
268 vars_[i]->WhenPerformedBound(demon);
269 }
270 cover_demon_ = solver()->RegisterDemon(MakeDelayedConstraintDemon0(
271 solver(), this, &CoverConstraint::CoverVarChanged, "CoverVarChanged"));
272 target_var_->WhenStartRange(cover_demon_);
273 target_var_->WhenEndRange(cover_demon_);
274 target_var_->WhenPerformedBound(cover_demon_);
275 }
276
277 void InitialPropagate() override {
278 // Copy vars to leaf nodes.
279 for (int i = 0; i < vars_.size(); ++i) {
280 InitLeaf(i, VarStartMin(i), VarStartMax(i), VarEndMin(i), VarEndMax(i),
281 VarPerformed(i));
282 }
283
284 // Compute up.
285 for (int i = MaxDepth() - 1; i >= 0; --i) {
286 for (int j = 0; j < Width(i); ++j) {
287 int64 bucket_start_min = kint64max;
288 int64 bucket_start_max = kint64max;
289 int64 bucket_end_min = kint64min;
290 int64 bucket_end_max = kint64min;
291 bool one_undecided = false;
292 const PerformedStatus up_performed = ComputePropagationUp(
293 i, j, &bucket_start_min, &bucket_start_max, &bucket_end_min,
294 &bucket_end_max, &one_undecided);
295 InitNode(i, j, bucket_start_min, bucket_start_max, bucket_end_min,
296 bucket_end_max, up_performed);
297 }
298 }
299 // Compute down.
300 PropagateRoot();
301 }
302
303 void PropagateRoot() {
304 // Propagate from the root of the tree to the target var.
305 switch (RootPerformed()) {
306 case UNPERFORMED:
307 target_var_->SetPerformed(false);
308 break;
309 case PERFORMED:
310 target_var_->SetPerformed(true);
311 ABSL_FALLTHROUGH_INTENDED;
312 case UNDECIDED:
313 target_var_->SetStartRange(RootStartMin(), RootStartMax());
314 target_var_->SetEndRange(RootEndMin(), RootEndMax());
315 break;
316 }
317 // Check if we need to propagate back. This is useful in case the
318 // target var is performed and only one last interval var may be
319 // performed, and thus needs to change is status to performed.
320 CoverVarChanged();
321 }
322
323 // Propagates from top to bottom.
324 void CoverVarChanged() {
325 PushDown(0, 0, TargetVarStartMin(), TargetVarStartMax(), TargetVarEndMin(),
326 TargetVarEndMax(), TargetVarPerformed());
327 }
328
329 void PushDown(int depth, int position, int64 new_start_min,
330 int64 new_start_max, int64 new_end_min, int64 new_end_max,
331 PerformedStatus performed) {
332 // TODO(user): Propagate start_max and end_min going down.
333 // Nothing to do?
334 if (new_start_min <= StartMin(depth, position) &&
335 new_start_max >= StartMax(depth, position) &&
336 new_end_min <= EndMin(depth, position) &&
337 new_end_max >= EndMax(depth, position) &&
338 (performed == UNDECIDED || performed == Performed(depth, position))) {
339 return;
340 }
341 // Leaf node -> push to leaf var.
342 if (IsLeaf(depth)) {
343 switch (performed) {
344 case UNPERFORMED:
345 vars_[position]->SetPerformed(false);
346 break;
347 case PERFORMED:
348 vars_[position]->SetPerformed(true);
349 ABSL_FALLTHROUGH_INTENDED;
350 case UNDECIDED:
351 vars_[position]->SetStartRange(new_start_min, new_start_max);
352 vars_[position]->SetEndRange(new_end_min, new_end_max);
353 }
354 return;
355 }
356
357 const int block_start = ChildStart(position);
358 const int block_end = ChildEnd(depth, position);
359
360 switch (performed) {
361 case UNPERFORMED: { // Mark all node unperformed.
362 for (int i = block_start; i <= block_end; ++i) {
363 PushDown(depth + 1, i, new_start_min, new_start_max, new_end_min,
364 new_end_max, UNPERFORMED);
365 }
366 break;
367 }
368 case PERFORMED: { // Count number of undecided or performed;
369 int candidate = -1;
370 int may_be_performed_count = 0;
371 int must_be_performed_count = 0;
372 for (int i = block_start; i <= block_end; ++i) {
373 switch (Performed(depth + 1, i)) {
374 case UNPERFORMED:
375 break;
376 case PERFORMED:
377 must_be_performed_count++;
378 ABSL_FALLTHROUGH_INTENDED;
379 case UNDECIDED:
380 may_be_performed_count++;
381 candidate = i;
382 }
383 }
384 if (may_be_performed_count == 0) {
385 solver()->Fail();
386 } else if (may_be_performed_count == 1) {
387 PushDown(depth + 1, candidate, new_start_min, new_start_max,
388 new_end_min, new_end_max, PERFORMED);
389 } else {
390 for (int i = block_start; i <= block_end; ++i) {
391 // Since there are more than 1 active child node, we
392 // cannot propagate on new_start_max and new_end_min. Thus
393 // we substitute them with safe bounds e.g. new_end_max
394 // and new_start_min.
395 PushDown(depth + 1, i, new_start_min, new_end_max, new_start_min,
396 new_end_max, UNDECIDED);
397 }
398 }
399 break;
400 }
401 case UNDECIDED: {
402 for (int i = block_start; i <= block_end; ++i) {
403 // Since there are more than 1 active child node, we
404 // cannot propagate on new_start_max and new_end_min. Thus
405 // we substitute them with safe bounds e.g. new_end_max
406 // and new_start_min.
407 PushDown(depth + 1, i, new_start_min, new_end_max, new_start_min,
408 new_end_max, UNDECIDED);
409 }
410 }
411 }
412 }
413
414 void LeafChanged(int term_index) {
415 ReduceDomain(MaxDepth(), term_index, VarStartMin(term_index),
416 VarStartMax(term_index), VarEndMin(term_index),
417 VarEndMax(term_index), VarPerformed(term_index));
418 // Do we need to propagate up?
419 const int parent = Parent(term_index);
420 const int parent_depth = MaxDepth() - 1;
421 const int64 parent_start_min = StartMin(parent_depth, parent);
422 const int64 parent_start_max = StartMax(parent_depth, parent);
423 const int64 parent_end_min = EndMin(parent_depth, parent);
424 const int64 parent_end_max = EndMax(parent_depth, parent);
425 IntervalVar* const var = vars_[term_index];
426 const bool performed_bound = var->IsPerformedBound();
427 const bool was_performed_bound = var->WasPerformedBound();
428 if (performed_bound == was_performed_bound && var->MayBePerformed() &&
429 var->OldStartMin() != parent_start_min &&
430 var->OldStartMax() != parent_start_max &&
431 var->OldEndMin() != parent_end_min &&
432 var->OldEndMax() != parent_end_max) {
433 // We were not a support of the parent bounds, and the performed
434 // status has not changed. There is no need to propagate up.
435 return;
436 }
437 PushUp(term_index);
438 }
439
440 void PushUp(int position) {
441 int depth = MaxDepth();
442 while (depth > 0) {
443 const int parent = Parent(position);
444 const int parent_depth = depth - 1;
445 int64 bucket_start_min = kint64max;
446 int64 bucket_start_max = kint64max;
447 int64 bucket_end_min = kint64min;
448 int64 bucket_end_max = kint64min;
449 bool one_undecided = false;
450 const PerformedStatus status_up = ComputePropagationUp(
451 parent_depth, parent, &bucket_start_min, &bucket_start_max,
452 &bucket_end_min, &bucket_end_max, &one_undecided);
453 if (bucket_start_min > StartMin(parent_depth, parent) ||
454 bucket_start_max < StartMax(parent_depth, parent) ||
455 bucket_end_min > EndMin(parent_depth, parent) ||
456 bucket_end_max < EndMax(parent_depth, parent) ||
457 status_up != Performed(parent_depth, parent)) {
458 ReduceDomain(parent_depth, parent, bucket_start_min, bucket_start_max,
459 bucket_end_min, bucket_end_max, status_up);
460 } else {
461 if (one_undecided && TargetVarPerformed() == PERFORMED) {
462 // This may be the last possible interval that can and
463 // should be performed.
464 PropagateRoot();
465 }
466 // There is nothing more to propagate up. We can stop now.
467 return;
468 }
469 depth = parent_depth;
470 position = parent;
471 }
472 DCHECK_EQ(0, depth);
473 PropagateRoot();
474 }
475
476 std::string DebugString() const override {
477 return DebugStringInternal(ModelVisitor::kCover);
478 }
479
480 void Accept(ModelVisitor* const visitor) const override {
481 AcceptInternal(ModelVisitor::kCover, visitor);
482 }
483
484 private:
485 PerformedStatus ComputePropagationUp(int parent_depth, int parent_position,
486 int64* const bucket_start_min,
487 int64* const bucket_start_max,
488 int64* const bucket_end_min,
489 int64* const bucket_end_max,
490 bool* one_undecided) {
491 *bucket_start_min = kint64max;
492 *bucket_start_max = kint64max;
493 *bucket_end_min = kint64min;
494 *bucket_end_max = kint64min;
495
496 int may_be_performed_count = 0;
497 int must_be_performed_count = 0;
498 const int block_start = ChildStart(parent_position);
499 const int block_end = ChildEnd(parent_depth, parent_position);
500 for (int k = block_start; k <= block_end; ++k) {
501 const PerformedStatus performed = Performed(parent_depth + 1, k);
502 if (performed != UNPERFORMED) {
503 *bucket_start_min =
504 std::min(*bucket_start_min, StartMin(parent_depth + 1, k));
505 *bucket_end_max =
506 std::max(*bucket_end_max, EndMax(parent_depth + 1, k));
507 may_be_performed_count++;
508 if (performed == PERFORMED) {
509 *bucket_start_max =
510 std::min(*bucket_start_max, StartMax(parent_depth + 1, k));
511 *bucket_end_min =
512 std::max(*bucket_end_min, EndMin(parent_depth + 1, k));
513 must_be_performed_count++;
514 }
515 }
516 }
517 const PerformedStatus up_performed =
518 must_be_performed_count > 0
519 ? PERFORMED
520 : (may_be_performed_count > 0 ? UNDECIDED : UNPERFORMED);
521 *one_undecided =
522 (may_be_performed_count == 1) && (must_be_performed_count == 0);
523 return up_performed;
524 }
525
526 Demon* cover_demon_;
527};
528
529class IntervalEquality : public Constraint {
530 public:
531 IntervalEquality(Solver* const solver, IntervalVar* const var1,
532 IntervalVar* const var2)
533 : Constraint(solver), var1_(var1), var2_(var2) {}
534
535 ~IntervalEquality() override {}
536
537 void Post() override {
538 Demon* const demon = solver()->MakeConstraintInitialPropagateCallback(this);
539 var1_->WhenAnything(demon);
540 var2_->WhenAnything(demon);
541 }
542
543 void InitialPropagate() override {
544 // Naive code. Can be split by property (performed, start...).
545 if (!var1_->MayBePerformed()) {
546 var2_->SetPerformed(false);
547 } else {
548 if (var1_->MustBePerformed()) {
549 var2_->SetPerformed(true);
550 }
551 var2_->SetStartRange(var1_->StartMin(), var1_->StartMax());
552 var2_->SetDurationRange(var1_->DurationMin(), var1_->DurationMax());
553 var2_->SetEndRange(var1_->EndMin(), var1_->EndMax());
554 }
555 if (!var2_->MayBePerformed()) {
556 var1_->SetPerformed(false);
557 } else {
558 if (var2_->MustBePerformed()) {
559 var1_->SetPerformed(true);
560 }
561 var1_->SetStartRange(var2_->StartMin(), var2_->StartMax());
562 var1_->SetDurationRange(var2_->DurationMin(), var2_->DurationMax());
563 var1_->SetEndRange(var2_->EndMin(), var2_->EndMax());
564 }
565 }
566
567 std::string DebugString() const override {
568 return absl::StrFormat("Equality(%s, %s)", var1_->DebugString(),
569 var2_->DebugString());
570 }
571
572 void Accept(ModelVisitor* const visitor) const override {
573 visitor->BeginVisitConstraint(ModelVisitor::kEquality, this);
574 visitor->VisitIntervalArgument(ModelVisitor::kLeftArgument, var1_);
575 visitor->VisitIntervalArgument(ModelVisitor::kRightArgument, var2_);
576 visitor->EndVisitConstraint(ModelVisitor::kEquality, this);
577 }
578
579 private:
580 IntervalVar* const var1_;
581 IntervalVar* const var2_;
582};
583} // namespace
584
585Constraint* Solver::MakeCover(const std::vector<IntervalVar*>& vars,
586 IntervalVar* const target_var) {
587 CHECK(!vars.empty());
588 if (vars.size() == 1) {
589 return MakeEquality(vars[0], target_var);
590 } else {
591 return RevAlloc(new CoverConstraint(this, vars, target_var));
592 }
593}
594
596 IntervalVar* const var2) {
597 return RevAlloc(new IntervalEquality(this, var1, var2));
598}
599} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
A constraint is the main modeling object.
Interval variables are often used in scheduling.
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
Definition: range_cst.cc:512
Constraint * MakeCover(const std::vector< IntervalVar * > &vars, IntervalVar *const target_var)
This constraint states that the target_var is the convex hull of the intervals.
T * RevAlloc(T *object)
Registers the given object as being reversible.
SatParameters parameters
const std::string name
IntVar * var
Definition: expr_array.cc:1858
static const int64 kint64max
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)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:45
Rev< int64 > end_min
Rev< int64 > end_max
IntervalVar *const target_var_
Rev< int > performed
Rev< int64 > start_max
Rev< int64 > start_min
const std::vector< IntervalVar * > vars_