OR-Tools  8.1
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"
29 #include "ortools/base/logging.h"
30 #include "ortools/base/macros.h"
34 
35 namespace operations_research {
36 namespace {
37 class 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.
254 class 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 
529 class 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 
585 Constraint* 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
operations_research::ModelVisitor::kEquality
static const char kEquality[]
Definition: constraint_solver.h:3354
var
IntVar * var
Definition: expr_array.cc:1858
min
int64 min
Definition: alldiff_cst.cc:138
integral_types.h
DCHECK_LT
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
max
int64 max
Definition: alldiff_cst.cc:139
end_max
Rev< int64 > end_max
Definition: sched_constraints.cc:244
CHECK_GE
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
operations_research::Solver::RevAlloc
T * RevAlloc(T *object)
Registers the given object as being reversible.
Definition: constraint_solver.h:791
start_min
Rev< int64 > start_min
Definition: sched_constraints.cc:241
logging.h
macros.h
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
kint64min
static const int64 kint64min
Definition: integral_types.h:60
operations_research::ModelVisitor::kTargetArgument
static const char kTargetArgument[]
Definition: constraint_solver.h:3482
operations_research::ModelVisitor::kCover
static const char kCover[]
Definition: constraint_solver.h:3343
int64
int64_t int64
Definition: integral_types.h:34
constraint_solveri.h
operations_research::MakeDelayedConstraintDemon0
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
Definition: constraint_solveri.h:688
constraint_solver.h
operations_research::Rev::Value
const T & Value() const
Definition: constraint_solver.h:3734
operations_research::Solver::MakeEquality
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
Definition: range_cst.cc:512
string_array.h
operations_research::Solver::MakeCover
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.
Definition: sched_constraints.cc:585
operations_research::MakeConstraintDemon1
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
Definition: constraint_solveri.h:566
target_var_
IntervalVar *const target_var_
Definition: sched_constraints.cc:230
start_max
Rev< int64 > start_max
Definition: sched_constraints.cc:242
operations_research::ModelVisitor::kIntervalsArgument
static const char kIntervalsArgument[]
Definition: constraint_solver.h:3455
operations_research::IntervalVar
Interval variables are often used in scheduling.
Definition: constraint_solver.h:4389
CHECK_LE
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
performed
Rev< int > performed
Definition: sched_constraints.cc:245
DCHECK_GE
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
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
end_min
Rev< int64 > end_min
Definition: sched_constraints.cc:243
vars_
const std::vector< IntervalVar * > vars_
Definition: sched_constraints.cc:229
DCHECK_EQ
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
CHECK
#define CHECK(condition)
Definition: base/logging.h:495
parameters
SatParameters parameters
Definition: cp_model_fz_solver.cc:108
name
const std::string name
Definition: default_search.cc:808
operations_research::JoinDebugStringPtr
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:45
kint64max
static const int64 kint64max
Definition: integral_types.h:62