16 #include "absl/strings/str_format.h"
28 const char* kUnaryNames[] = {
29 "ENDS_AFTER",
"ENDS_AT",
"ENDS_BEFORE",
"STARTS_AFTER",
30 "STARTS_AT",
"STARTS_BEFORE",
"CROSS_DATE",
"AVOID_DATE",
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"};
38 class IntervalUnaryRelation :
public Constraint {
40 IntervalUnaryRelation(Solver*
const s, IntervalVar*
const t,
int64 d,
42 : Constraint(s), t_(t), d_(d), rel_(rel) {}
43 ~IntervalUnaryRelation()
override {}
47 void InitialPropagate()
override;
49 std::string DebugString()
const override {
50 return absl::StrFormat(
"(%s %s %d)", t_->DebugString(), kUnaryNames[rel_],
54 void Accept(ModelVisitor*
const visitor)
const override {
63 IntervalVar*
const t_;
68 void IntervalUnaryRelation::Post() {
70 Demon* d = solver()->MakeConstraintInitialPropagateCallback(
this);
75 void IntervalUnaryRelation::InitialPropagate() {
116 return RevAlloc(
new IntervalUnaryRelation(
this, t, d, r));
122 class IntervalBinaryRelation :
public Constraint {
127 :
Constraint(s), t1_(t1), t2_(t2), rel_(rel), delay_(delay) {}
128 ~IntervalBinaryRelation()
override {}
130 void Post()
override;
132 void InitialPropagate()
override;
134 std::string DebugString()
const override {
135 return absl::StrFormat(
"(%s %s %s)", t1_->DebugString(), kBinaryNames[rel_],
139 void Accept(ModelVisitor*
const visitor)
const override {
148 IntervalVar*
const t1_;
149 IntervalVar*
const t2_;
154 void IntervalBinaryRelation::Post() {
156 Demon* d = solver()->MakeConstraintInitialPropagateCallback(
this);
163 void IntervalBinaryRelation::InitialPropagate() {
235 return RevAlloc(
new IntervalBinaryRelation(
this, t1, t2, r, 0));
241 return RevAlloc(
new IntervalBinaryRelation(
this, t1, t2, r, delay));
247 class TemporalDisjunction :
public Constraint {
249 enum State { ONE_BEFORE_TWO, TWO_BEFORE_ONE, UNDECIDED };
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 {}
256 void Post()
override;
257 void InitialPropagate()
override;
258 std::string DebugString()
const override;
263 void Decide(State s);
266 void Accept(ModelVisitor*
const visitor)
const override {
276 IntervalVar*
const t1_;
277 IntervalVar*
const t2_;
282 void TemporalDisjunction::Post() {
283 Solver*
const s = solver();
290 if (alt_ !=
nullptr) {
297 void TemporalDisjunction::InitialPropagate() {
298 if (alt_ !=
nullptr) {
301 if (alt_ !=
nullptr && alt_->
Bound()) {
309 std::string TemporalDisjunction::DebugString()
const {
311 (out = absl::StrFormat(
"TemporalDisjunction(%s, %s", t1_->
DebugString(),
313 if (alt_ !=
nullptr) {
314 absl::StrAppendFormat(&out,
" => %s", alt_->
DebugString());
320 void TemporalDisjunction::TryToDecide() {
325 Decide(TWO_BEFORE_ONE);
327 Decide(ONE_BEFORE_TWO);
332 void TemporalDisjunction::RangeDemon1() {
334 case ONE_BEFORE_TWO: {
340 case TWO_BEFORE_ONE: {
352 void TemporalDisjunction::RangeDemon2() {
355 case ONE_BEFORE_TWO: {
361 case TWO_BEFORE_ONE: {
374 void TemporalDisjunction::RangeAlt() {
376 if (alt_->
Value() == 0) {
377 Decide(ONE_BEFORE_TWO);
379 Decide(TWO_BEFORE_ONE);
383 void TemporalDisjunction::Decide(State s) {
386 if (state_ != UNDECIDED && state_ != s) {
389 solver()->SaveValue(
reinterpret_cast<int*
>(&state_));
391 if (alt_ !=
nullptr) {
392 if (s == ONE_BEFORE_TWO) {
406 return RevAlloc(
new TemporalDisjunction(
this, t1, t2, alt));
411 return RevAlloc(
new TemporalDisjunction(
this, t1, t2,
nullptr));
#define DCHECK_NE(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
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.
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 kIntervalArgument[]
static const char kTargetArgument[]
static const char kIntervalUnaryRelation[]
static const char kValueArgument[]
static const char kIntervalDisjunction[]
static const char kRelationArgument[]
static const char kLeftArgument[]
static const char kRightArgument[]
static const char kIntervalBinaryRelation[]
std::string DebugString() const override
Constraint * MakeIntervalVarRelation(IntervalVar *const t, UnaryIntervalRelation r, int64 d)
This method creates a relation between an interval var and a date.
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.
Constraint * MakeTemporalDisjunction(IntervalVar *const t1, IntervalVar *const t2, IntVar *const alt)
This constraint implements a temporal disjunction between two interval vars t1 and t2.
T * RevAlloc(T *object)
Registers the given object as being reversible.
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)