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"
19#include "ortools/base/macros.h"
22
23namespace operations_research {
24
25// ----- interval <unary relation> date -----
26
27namespace {
28const char* kUnaryNames[] = {
29 "ENDS_AFTER", "ENDS_AT", "ENDS_BEFORE", "STARTS_AFTER",
30 "STARTS_AT", "STARTS_BEFORE", "CROSS_DATE", "AVOID_DATE",
31};
32
33const 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
38class 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
68void IntervalUnaryRelation::Post() {
69 if (t_->MayBePerformed()) {
70 Demon* d = solver()->MakeConstraintInitialPropagateCallback(this);
71 t_->WhenAnything(d);
72 }
73}
74
75void IntervalUnaryRelation::InitialPropagate() {
76 if (t_->MayBePerformed()) {
77 switch (rel_) {
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;
91 t_->SetStartRange(d_, d_);
92 break;
93
95 t_->SetStartMax(d_);
96 break;
98 t_->SetStartMax(d_);
99 t_->SetEndMin(d_);
100 break;
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
121namespace {
122class 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
154void 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?
163void 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;
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;
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
246namespace {
247class 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
282void 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
297void 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
309std::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
320void 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
332void 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
352void 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
374void 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
383void 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)