OR-Tools  8.2
timetabling.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>
15 
16 #include "absl/strings/str_format.h"
18 #include "ortools/base/logging.h"
19 #include "ortools/base/macros.h"
22 
23 namespace operations_research {
24 
25 // ----- interval <unary relation> date -----
26 
27 namespace {
28 const char* kUnaryNames[] = {
29  "ENDS_AFTER", "ENDS_AT", "ENDS_BEFORE", "STARTS_AFTER",
30  "STARTS_AT", "STARTS_BEFORE", "CROSS_DATE", "AVOID_DATE",
31 };
32 
33 const char* kBinaryNames[] = {
34  "ENDS_AFTER_END", "ENDS_AFTER_START", "ENDS_AT_END",
35  "ENDS_AT_START", "STARTS_AFTER_END", "STARTS_AFTER_START",
36  "STARTS_AT_END", "STARTS_AT_START", "STAYS_IN_SYNC"};
37 
38 class IntervalUnaryRelation : public Constraint {
39  public:
40  IntervalUnaryRelation(Solver* const s, IntervalVar* const t, int64 d,
42  : Constraint(s), t_(t), d_(d), rel_(rel) {}
43  ~IntervalUnaryRelation() override {}
44 
45  void Post() override;
46 
47  void InitialPropagate() override;
48 
49  std::string DebugString() const override {
50  return absl::StrFormat("(%s %s %d)", t_->DebugString(), kUnaryNames[rel_],
51  d_);
52  }
53 
54  void Accept(ModelVisitor* const visitor) const override {
55  visitor->BeginVisitConstraint(ModelVisitor::kIntervalUnaryRelation, this);
56  visitor->VisitIntervalArgument(ModelVisitor::kIntervalArgument, t_);
57  visitor->VisitIntegerArgument(ModelVisitor::kRelationArgument, rel_);
58  visitor->VisitIntegerArgument(ModelVisitor::kValueArgument, d_);
59  visitor->EndVisitConstraint(ModelVisitor::kIntervalUnaryRelation, this);
60  }
61 
62  private:
63  IntervalVar* const t_;
64  const int64 d_;
66 };
67 
68 void IntervalUnaryRelation::Post() {
69  if (t_->MayBePerformed()) {
70  Demon* d = solver()->MakeConstraintInitialPropagateCallback(this);
71  t_->WhenAnything(d);
72  }
73 }
74 
75 void IntervalUnaryRelation::InitialPropagate() {
76  if (t_->MayBePerformed()) {
77  switch (rel_) {
78  case Solver::ENDS_AFTER:
79  t_->SetEndMin(d_);
80  break;
81  case Solver::ENDS_AT:
82  t_->SetEndRange(d_, d_);
83  break;
85  t_->SetEndMax(d_);
86  break;
88  t_->SetStartMin(d_);
89  break;
90  case Solver::STARTS_AT:
91  t_->SetStartRange(d_, d_);
92  break;
93 
95  t_->SetStartMax(d_);
96  break;
97  case Solver::CROSS_DATE:
98  t_->SetStartMax(d_);
99  t_->SetEndMin(d_);
100  break;
101  case Solver::AVOID_DATE:
102  if (t_->EndMin() > d_) {
103  t_->SetStartMin(d_);
104  } else if (t_->StartMax() < d_) {
105  t_->SetEndMax(d_);
106  }
107  break;
108  }
109  }
110 }
111 } // namespace
112 
115  int64 d) {
116  return RevAlloc(new IntervalUnaryRelation(this, t, d, r));
117 }
118 
119 // ----- interval <binary relation> interval -----
120 
121 namespace {
122 class IntervalBinaryRelation : public Constraint {
123  public:
124  IntervalBinaryRelation(Solver* const s, IntervalVar* const t1,
125  IntervalVar* const t2,
127  : Constraint(s), t1_(t1), t2_(t2), rel_(rel), delay_(delay) {}
128  ~IntervalBinaryRelation() override {}
129 
130  void Post() override;
131 
132  void InitialPropagate() override;
133 
134  std::string DebugString() const override {
135  return absl::StrFormat("(%s %s %s)", t1_->DebugString(), kBinaryNames[rel_],
136  t2_->DebugString());
137  }
138 
139  void Accept(ModelVisitor* const visitor) const override {
140  visitor->BeginVisitConstraint(ModelVisitor::kIntervalBinaryRelation, this);
141  visitor->VisitIntervalArgument(ModelVisitor::kLeftArgument, t1_);
142  visitor->VisitIntegerArgument(ModelVisitor::kRelationArgument, rel_);
143  visitor->VisitIntervalArgument(ModelVisitor::kRightArgument, t2_);
144  visitor->EndVisitConstraint(ModelVisitor::kIntervalBinaryRelation, this);
145  }
146 
147  private:
148  IntervalVar* const t1_;
149  IntervalVar* const t2_;
151  const int64 delay_;
152 };
153 
154 void IntervalBinaryRelation::Post() {
155  if (t1_->MayBePerformed() && t2_->MayBePerformed()) {
156  Demon* d = solver()->MakeConstraintInitialPropagateCallback(this);
157  t1_->WhenAnything(d);
158  t2_->WhenAnything(d);
159  }
160 }
161 
162 // TODO(user) : make code more compact, use function pointers?
163 void IntervalBinaryRelation::InitialPropagate() {
164  if (t2_->MustBePerformed() && t1_->MayBePerformed()) {
165  switch (rel_) {
167  t1_->SetEndMin(t2_->EndMin() + delay_);
168  break;
170  t1_->SetEndMin(t2_->StartMin() + delay_);
171  break;
172  case Solver::ENDS_AT_END:
173  t1_->SetEndRange(t2_->EndMin() + delay_, t2_->EndMax() + delay_);
174  break;
176  t1_->SetEndRange(t2_->StartMin() + delay_, t2_->StartMax() + delay_);
177  break;
179  t1_->SetStartMin(t2_->EndMin() + delay_);
180  break;
182  t1_->SetStartMin(t2_->StartMin() + delay_);
183  break;
185  t1_->SetStartRange(t2_->EndMin() + delay_, t2_->EndMax() + delay_);
186  break;
188  t1_->SetStartRange(t2_->StartMin() + delay_, t2_->StartMax() + delay_);
189  break;
191  t1_->SetStartRange(t2_->StartMin() + delay_, t2_->StartMax() + delay_);
192  t1_->SetEndRange(t2_->EndMin() + delay_, t2_->EndMax() + delay_);
193  break;
194  }
195  }
196 
197  if (t1_->MustBePerformed() && t2_->MayBePerformed()) {
198  switch (rel_) {
200  t2_->SetEndMax(t1_->EndMax() - delay_);
201  break;
203  t2_->SetStartMax(t1_->EndMax() - delay_);
204  break;
205  case Solver::ENDS_AT_END:
206  t2_->SetEndRange(t1_->EndMin() - delay_, t1_->EndMax() - delay_);
207  break;
209  t2_->SetStartRange(t1_->EndMin() - delay_, t1_->EndMax() - delay_);
210  break;
212  t2_->SetEndMax(t1_->StartMax() - delay_);
213  break;
215  t2_->SetStartMax(t1_->StartMax() - delay_);
216  break;
218  t2_->SetEndRange(t1_->StartMin() - delay_, t1_->StartMax() - delay_);
219  break;
221  t2_->SetStartRange(t1_->StartMin() - delay_, t1_->StartMax() - delay_);
222  break;
224  t2_->SetStartRange(t1_->StartMin() - delay_, t1_->StartMax() - delay_);
225  t2_->SetEndRange(t1_->EndMin() - delay_, t1_->EndMax() - delay_);
226  break;
227  }
228  }
229 }
230 } // namespace
231 
234  IntervalVar* const t2) {
235  return RevAlloc(new IntervalBinaryRelation(this, t1, t2, r, 0));
236 }
237 
240  IntervalVar* const t2, int64 delay) {
241  return RevAlloc(new IntervalBinaryRelation(this, t1, t2, r, delay));
242 }
243 
244 // ----- activity a before activity b or activity b before activity a -----
245 
246 namespace {
247 class TemporalDisjunction : public Constraint {
248  public:
249  enum State { ONE_BEFORE_TWO, TWO_BEFORE_ONE, UNDECIDED };
250 
251  TemporalDisjunction(Solver* const s, IntervalVar* const t1,
252  IntervalVar* const t2, IntVar* const alt)
253  : Constraint(s), t1_(t1), t2_(t2), alt_(alt), state_(UNDECIDED) {}
254  ~TemporalDisjunction() override {}
255 
256  void Post() override;
257  void InitialPropagate() override;
258  std::string DebugString() const override;
259 
260  void RangeDemon1();
261  void RangeDemon2();
262  void RangeAlt();
263  void Decide(State s);
264  void TryToDecide();
265 
266  void Accept(ModelVisitor* const visitor) const override {
267  visitor->BeginVisitConstraint(ModelVisitor::kIntervalDisjunction, this);
268  visitor->VisitIntervalArgument(ModelVisitor::kLeftArgument, t1_);
269  visitor->VisitIntervalArgument(ModelVisitor::kRightArgument, t2_);
270  visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
271  alt_);
272  visitor->EndVisitConstraint(ModelVisitor::kIntervalDisjunction, this);
273  }
274 
275  private:
276  IntervalVar* const t1_;
277  IntervalVar* const t2_;
278  IntVar* const alt_;
279  State state_;
280 };
281 
282 void TemporalDisjunction::Post() {
283  Solver* const s = solver();
284  Demon* d = MakeConstraintDemon0(s, this, &TemporalDisjunction::RangeDemon1,
285  "RangeDemon1");
286  t1_->WhenAnything(d);
287  d = MakeConstraintDemon0(s, this, &TemporalDisjunction::RangeDemon2,
288  "RangeDemon2");
289  t2_->WhenAnything(d);
290  if (alt_ != nullptr) {
291  d = MakeConstraintDemon0(s, this, &TemporalDisjunction::RangeAlt,
292  "RangeAlt");
293  alt_->WhenRange(d);
294  }
295 }
296 
297 void TemporalDisjunction::InitialPropagate() {
298  if (alt_ != nullptr) {
299  alt_->SetRange(0, 1);
300  }
301  if (alt_ != nullptr && alt_->Bound()) {
302  RangeAlt();
303  } else {
304  RangeDemon1();
305  RangeDemon2();
306  }
307 }
308 
309 std::string TemporalDisjunction::DebugString() const {
310  std::string out;
311  (out = absl::StrFormat("TemporalDisjunction(%s, %s", t1_->DebugString(),
312  t2_->DebugString()));
313  if (alt_ != nullptr) {
314  absl::StrAppendFormat(&out, " => %s", alt_->DebugString());
315  }
316  out += ") ";
317  return out;
318 }
319 
320 void TemporalDisjunction::TryToDecide() {
321  DCHECK_EQ(UNDECIDED, state_);
322  if (t1_->MayBePerformed() && t2_->MayBePerformed() &&
323  (t1_->MustBePerformed() || t2_->MustBePerformed())) {
324  if (t1_->EndMin() > t2_->StartMax()) {
325  Decide(TWO_BEFORE_ONE);
326  } else if (t2_->EndMin() > t1_->StartMax()) {
327  Decide(ONE_BEFORE_TWO);
328  }
329  }
330 }
331 
332 void TemporalDisjunction::RangeDemon1() {
333  switch (state_) {
334  case ONE_BEFORE_TWO: {
335  if (t1_->MustBePerformed() && t2_->MayBePerformed()) {
336  t2_->SetStartMin(t1_->EndMin());
337  }
338  break;
339  }
340  case TWO_BEFORE_ONE: {
341  if (t1_->MustBePerformed() && t2_->MayBePerformed()) {
342  t2_->SetEndMax(t1_->StartMax());
343  }
344  break;
345  }
346  case UNDECIDED: {
347  TryToDecide();
348  }
349  }
350 }
351 
352 void TemporalDisjunction::RangeDemon2() {
353  if (t1_->MayBePerformed() || t2_->MayBePerformed()) {
354  switch (state_) {
355  case ONE_BEFORE_TWO: {
356  if (t2_->MustBePerformed() && t1_->MayBePerformed()) {
357  t1_->SetEndMax(t2_->StartMax());
358  }
359  break;
360  }
361  case TWO_BEFORE_ONE: {
362  if (t2_->MustBePerformed() && t1_->MayBePerformed()) {
363  t1_->SetStartMin(t2_->EndMin());
364  }
365  break;
366  }
367  case UNDECIDED: {
368  TryToDecide();
369  }
370  }
371  }
372 }
373 
374 void TemporalDisjunction::RangeAlt() {
375  DCHECK(alt_ != nullptr);
376  if (alt_->Value() == 0) {
377  Decide(ONE_BEFORE_TWO);
378  } else {
379  Decide(TWO_BEFORE_ONE);
380  }
381 }
382 
383 void TemporalDisjunction::Decide(State s) {
384  // Should Decide on a fixed state?
385  DCHECK_NE(s, UNDECIDED);
386  if (state_ != UNDECIDED && state_ != s) {
387  solver()->Fail();
388  }
389  solver()->SaveValue(reinterpret_cast<int*>(&state_));
390  state_ = s;
391  if (alt_ != nullptr) {
392  if (s == ONE_BEFORE_TWO) {
393  alt_->SetValue(0);
394  } else {
395  alt_->SetValue(1);
396  }
397  }
398  RangeDemon1();
399  RangeDemon2();
400 }
401 } // namespace
402 
404  IntervalVar* const t2,
405  IntVar* const alt) {
406  return RevAlloc(new TemporalDisjunction(this, t1, t2, alt));
407 }
408 
410  IntervalVar* const t2) {
411  return RevAlloc(new TemporalDisjunction(this, t1, t2, nullptr));
412 }
413 
414 } // namespace operations_research
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
A constraint is the main modeling object.
virtual void SetRange(int64 l, int64 u)
This method sets both the min and the max of the expression.
virtual void SetValue(int64 v)
This method sets the value of the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual void WhenRange(Demon *d)=0
Attach a demon that will watch the min or the max of the expression.
The class IntVar is a subset of IntExpr.
virtual int64 Value() const =0
This method returns the value of the variable.
Interval variables are often used in scheduling.
virtual int64 StartMax() const =0
void WhenAnything(Demon *const d)
Attaches a demon awakened when anything about this interval changes.
Definition: interval.cc:2227
virtual int64 EndMax() const =0
virtual void SetEndMax(int64 m)=0
virtual void SetStartMin(int64 m)=0
virtual void SetEndMin(int64 m)=0
virtual void SetEndRange(int64 mi, int64 ma)=0
virtual bool MustBePerformed() const =0
These methods query, set, and watch the performed status of the interval var.
virtual void SetStartMax(int64 m)=0
virtual int64 StartMin() const =0
These methods query, set, and watch the start position of the interval var.
virtual void SetStartRange(int64 mi, int64 ma)=0
virtual int64 EndMin() const =0
These methods query, set, and watch the end position of the interval var.
virtual bool MayBePerformed() const =0
static const char kIntervalUnaryRelation[]
static const char kIntervalBinaryRelation[]
Constraint * MakeIntervalVarRelation(IntervalVar *const t, UnaryIntervalRelation r, int64 d)
This method creates a relation between an interval var and a date.
Definition: timetabling.cc:113
UnaryIntervalRelation
This enum is used in Solver::MakeIntervalVarRelation to specify the temporal relation between an inte...
@ ENDS_BEFORE
t ends before d, i.e. End(t) <= d.
@ AVOID_DATE
STARTS_AFTER or ENDS_BEFORE, i.e.
@ ENDS_AFTER
t ends after d, i.e. End(t) >= d.
@ STARTS_BEFORE
t starts before d, i.e. Start(t) <= d.
@ STARTS_AT
t starts at d, i.e. Start(t) == d.
@ ENDS_AT
t ends at d, i.e. End(t) == d.
@ STARTS_AFTER
t starts after d, i.e. Start(t) >= d.
@ CROSS_DATE
STARTS_BEFORE and ENDS_AFTER at the same time, i.e.
BinaryIntervalRelation
This enum is used in Solver::MakeIntervalVarRelation to specify the temporal relation between the two...
@ ENDS_AFTER_END
t1 ends after t2 end, i.e. End(t1) >= End(t2) + delay.
@ ENDS_AFTER_START
t1 ends after t2 start, i.e. End(t1) >= Start(t2) + delay.
@ STAYS_IN_SYNC
STARTS_AT_START and ENDS_AT_END at the same time.
@ ENDS_AT_END
t1 ends at t2 end, i.e. End(t1) == End(t2) + delay.
@ STARTS_AT_END
t1 starts at t2 end, i.e. Start(t1) == End(t2) + delay.
@ ENDS_AT_START
t1 ends at t2 start, i.e. End(t1) == Start(t2) + delay.
@ STARTS_AFTER_END
t1 starts after t2 end, i.e. Start(t1) >= End(t2) + delay.
@ STARTS_AFTER_START
t1 starts after t2 start, i.e. Start(t1) >= Start(t2) + delay.
@ STARTS_AT_START
t1 starts at t2 start, i.e. Start(t1) == Start(t2) + delay.
Constraint * MakeIntervalVarRelationWithDelay(IntervalVar *const t1, BinaryIntervalRelation r, IntervalVar *const t2, int64 delay)
This method creates a relation between two interval vars.
Definition: timetabling.cc:238
Constraint * MakeTemporalDisjunction(IntervalVar *const t1, IntervalVar *const t2, IntVar *const alt)
This constraint implements a temporal disjunction between two interval vars t1 and t2.
Definition: timetabling.cc:403
T * RevAlloc(T *object)
Registers the given object as being reversible.
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)