27 #include "absl/strings/str_format.h"
37 class TreeArrayConstraint :
public Constraint {
39 enum PerformedStatus { UNPERFORMED, PERFORMED, UNDECIDED };
41 TreeArrayConstraint(Solver*
const solver,
42 const std::vector<IntervalVar*>& vars,
43 IntervalVar*
const 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_);
54 tree_.resize(lengths.size());
55 for (
int i = 0; i < lengths.size(); ++i) {
56 tree_[i].resize(lengths[lengths.size() - i - 1]);
60 root_node_ = &tree_[0][0];
63 std::string DebugStringInternal(
const std::string&
name)
const {
68 void AcceptInternal(
const std::string&
name,
69 ModelVisitor*
const visitor)
const {
70 visitor->BeginVisitConstraint(
name,
this);
74 visitor->EndVisitConstraint(
name,
this);
78 void ReduceDomain(
int depth,
int position,
int64 new_start_min,
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);
85 if (new_start_max < info->
start_max.Value()) {
86 info->start_max.SetValue(solver(), new_start_max);
88 if (new_end_min > info->end_min.Value()) {
89 info->end_min.SetValue(solver(), new_end_min);
91 if (new_end_max < info->
end_max.Value()) {
92 info->end_max.SetValue(solver(), new_end_max);
96 info->performed.Value() == UNDECIDED);
97 info->performed.SetValue(solver(),
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(),
117 int64 StartMin(
int depth,
int position)
const {
118 return tree_[depth][position].start_min.Value();
121 int64 StartMax(
int depth,
int position)
const {
122 return tree_[depth][position].start_max.Value();
125 int64 EndMax(
int depth,
int position)
const {
126 return tree_[depth][position].end_max.Value();
129 int64 EndMin(
int depth,
int position)
const {
130 return tree_[depth][position].end_min.Value();
133 PerformedStatus Performed(
int depth,
int position)
const {
134 const int p = tree_[depth][position].performed.Value();
137 return static_cast<PerformedStatus
>(p);
140 int64 RootStartMin()
const {
return root_node_->start_min.Value(); }
142 int64 RootStartMax()
const {
return root_node_->start_max.Value(); }
144 int64 RootEndMin()
const {
return root_node_->end_min.Value(); }
146 int64 RootEndMax()
const {
return root_node_->end_max.Value(); }
148 PerformedStatus RootPerformed()
const {
return Performed(0, 0); }
152 int64 VarStartMin(
int position)
const {
153 return vars_[position]->MayBePerformed() ?
vars_[position]->StartMin() : 0;
156 int64 VarStartMax(
int position)
const {
157 return vars_[position]->MayBePerformed() ?
vars_[position]->StartMax() : 0;
160 int64 VarEndMin(
int position)
const {
161 return vars_[position]->MayBePerformed() ?
vars_[position]->EndMin() : 0;
164 int64 VarEndMax(
int position)
const {
165 return vars_[position]->MayBePerformed() ?
vars_[position]->EndMax() : 0;
168 int64 TargetVarStartMin()
const {
172 int64 TargetVarStartMax()
const {
176 int64 TargetVarEndMin()
const {
180 int64 TargetVarEndMax()
const {
186 PerformedStatus VarPerformed(
int position)
const {
187 IntervalVar*
const var =
vars_[position];
188 if (
var->MustBePerformed()) {
190 }
else if (
var->MayBePerformed()) {
198 PerformedStatus TargetVarPerformed()
const {
209 int Parent(
int position)
const {
return position / block_size_; }
212 int ChildStart(
int position)
const {
return position * block_size_; }
217 int ChildEnd(
int depth,
int position)
const {
219 return std::min((position + 1) * block_size_ - 1, Width(depth + 1) - 1);
222 bool IsLeaf(
int depth)
const {
return depth == MaxDepth(); }
224 int MaxDepth()
const {
return tree_.size() - 1; }
226 int Width(
int depth)
const {
return tree_[depth].size(); }
229 const std::vector<IntervalVar*>
vars_;
248 std::vector<std::vector<NodeInfo> > tree_;
249 const int block_size_;
250 NodeInfo* root_node_;
254 class CoverConstraint :
public TreeArrayConstraint {
256 CoverConstraint(Solver*
const solver,
const std::vector<IntervalVar*>& vars,
257 IntervalVar*
const cover_var)
258 : TreeArrayConstraint(solver, vars, cover_var), cover_demon_(
nullptr) {}
260 ~CoverConstraint()
override {}
262 void Post()
override {
263 for (
int i = 0; i <
vars_.size(); ++i) {
265 solver(),
this, &CoverConstraint::LeafChanged,
"LeafChanged", i);
266 vars_[i]->WhenStartRange(demon);
267 vars_[i]->WhenEndRange(demon);
268 vars_[i]->WhenPerformedBound(demon);
271 solver(),
this, &CoverConstraint::CoverVarChanged,
"CoverVarChanged"));
277 void InitialPropagate()
override {
279 for (
int i = 0; i <
vars_.size(); ++i) {
280 InitLeaf(i, VarStartMin(i), VarStartMax(i), VarEndMin(i), VarEndMax(i),
285 for (
int i = MaxDepth() - 1; i >= 0; --i) {
286 for (
int j = 0; j < Width(i); ++j) {
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);
303 void PropagateRoot() {
305 switch (RootPerformed()) {
311 ABSL_FALLTHROUGH_INTENDED;
313 target_var_->SetStartRange(RootStartMin(), RootStartMax());
314 target_var_->SetEndRange(RootEndMin(), RootEndMax());
324 void CoverVarChanged() {
325 PushDown(0, 0, TargetVarStartMin(), TargetVarStartMax(), TargetVarEndMin(),
326 TargetVarEndMax(), TargetVarPerformed());
329 void PushDown(
int depth,
int position,
int64 new_start_min,
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) &&
345 vars_[position]->SetPerformed(
false);
348 vars_[position]->SetPerformed(
true);
349 ABSL_FALLTHROUGH_INTENDED;
351 vars_[position]->SetStartRange(new_start_min, new_start_max);
352 vars_[position]->SetEndRange(new_end_min, new_end_max);
357 const int block_start = ChildStart(position);
358 const int block_end = ChildEnd(depth, position);
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);
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)) {
377 must_be_performed_count++;
378 ABSL_FALLTHROUGH_INTENDED;
380 may_be_performed_count++;
384 if (may_be_performed_count == 0) {
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);
390 for (
int i = block_start; i <= block_end; ++i) {
395 PushDown(depth + 1, i, new_start_min, new_end_max, new_start_min,
396 new_end_max, UNDECIDED);
402 for (
int i = block_start; i <= block_end; ++i) {
407 PushDown(depth + 1, i, new_start_min, new_end_max, new_start_min,
408 new_end_max, UNDECIDED);
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));
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) {
440 void PushUp(
int position) {
441 int depth = MaxDepth();
443 const int parent = Parent(position);
444 const int parent_depth = depth - 1;
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);
461 if (one_undecided && TargetVarPerformed() == PERFORMED) {
469 depth = parent_depth;
476 std::string DebugString()
const override {
480 void Accept(ModelVisitor*
const visitor)
const override {
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) {
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);
504 std::min(*bucket_start_min, StartMin(parent_depth + 1, k));
506 std::max(*bucket_end_max, EndMax(parent_depth + 1, k));
507 may_be_performed_count++;
510 std::min(*bucket_start_max, StartMax(parent_depth + 1, k));
512 std::max(*bucket_end_min, EndMin(parent_depth + 1, k));
513 must_be_performed_count++;
517 const PerformedStatus up_performed =
518 must_be_performed_count > 0
520 : (may_be_performed_count > 0 ? UNDECIDED : UNPERFORMED);
522 (may_be_performed_count == 1) && (must_be_performed_count == 0);
529 class IntervalEquality :
public Constraint {
531 IntervalEquality(Solver*
const solver, IntervalVar*
const var1,
532 IntervalVar*
const var2)
533 : Constraint(solver), var1_(var1), var2_(var2) {}
535 ~IntervalEquality()
override {}
537 void Post()
override {
538 Demon*
const demon = solver()->MakeConstraintInitialPropagateCallback(
this);
539 var1_->WhenAnything(demon);
540 var2_->WhenAnything(demon);
543 void InitialPropagate()
override {
545 if (!var1_->MayBePerformed()) {
546 var2_->SetPerformed(
false);
548 if (var1_->MustBePerformed()) {
549 var2_->SetPerformed(
true);
551 var2_->SetStartRange(var1_->StartMin(), var1_->StartMax());
552 var2_->SetDurationRange(var1_->DurationMin(), var1_->DurationMax());
553 var2_->SetEndRange(var1_->EndMin(), var1_->EndMax());
555 if (!var2_->MayBePerformed()) {
556 var1_->SetPerformed(
false);
558 if (var2_->MustBePerformed()) {
559 var1_->SetPerformed(
true);
561 var1_->SetStartRange(var2_->StartMin(), var2_->StartMax());
562 var1_->SetDurationRange(var2_->DurationMin(), var2_->DurationMax());
563 var1_->SetEndRange(var2_->EndMin(), var2_->EndMax());
567 std::string DebugString()
const override {
568 return absl::StrFormat(
"Equality(%s, %s)", var1_->DebugString(),
569 var2_->DebugString());
572 void Accept(ModelVisitor*
const visitor)
const override {
580 IntervalVar*
const var1_;
581 IntervalVar*
const var2_;
587 CHECK(!vars.empty());
588 if (vars.size() == 1) {
591 return RevAlloc(
new CoverConstraint(
this, vars, target_var));
597 return RevAlloc(
new IntervalEquality(
this, var1, var2));
#define CHECK_GE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define CHECK_LE(val1, val2)
#define DCHECK_EQ(val1, val2)
A constraint is the main modeling object.
Interval variables are often used in scheduling.
static const char kTargetArgument[]
static const char kIntervalsArgument[]
static const char kLeftArgument[]
static const char kRightArgument[]
static const char kCover[]
static const char kEquality[]
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
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.
T * RevAlloc(T *object)
Registers the given object as being reversible.
static const int64 kint64max
static const int64 kint64min
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
IntervalVar *const target_var_
const std::vector< IntervalVar * > vars_