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