31 const std::vector<IntervalVariable>& vars) {
33 bool is_all_different =
true;
35 for (
const IntervalVariable
var : vars) {
38 is_all_different =
false;
42 if (is_all_different) {
43 std::vector<IntegerVariable> starts;
44 starts.reserve(vars.size());
45 for (
const IntervalVariable
var : vars) {
53 const auto& sat_parameters = *
model->GetOrCreate<SatParameters>();
54 if (vars.size() > 2 && sat_parameters.use_combined_no_overlap()) {
62 model->TakeOwnership(helper);
67 std::vector<AffineExpression> demands(vars.size(), one);
71 model->TakeOwnership(timetable);
75 if (vars.size() == 2) {
78 model->TakeOwnership(propagator);
87 watcher->SetPropagatorPriority(
id, 1);
88 model->TakeOwnership(overload_checker);
90 for (
const bool time_direction : {
true,
false}) {
93 const int id = detectable_precedences->
RegisterWith(watcher);
94 watcher->SetPropagatorPriority(
id, 2);
95 model->TakeOwnership(detectable_precedences);
97 for (
const bool time_direction : {
true,
false}) {
101 watcher->SetPropagatorPriority(
id, 3);
102 model->TakeOwnership(not_last);
104 for (
const bool time_direction : {
true,
false}) {
108 watcher->SetPropagatorPriority(
id, 4);
109 model->TakeOwnership(edge_finding);
116 if (sat_parameters.use_precedences_in_disjunctive_constraint() &&
117 !sat_parameters.use_combined_no_overlap()) {
118 for (
const bool time_direction : {
true,
false}) {
123 watcher->SetPropagatorPriority(
id, 5);
124 model->TakeOwnership(precedences);
131 const std::vector<IntervalVariable>& vars) {
137 for (
int i = 0; i < vars.size(); ++i) {
138 for (
int j = 0; j < i; ++j) {
142 precedences->AddConditionalPrecedence(repository->EndVar(vars[i]),
143 repository->StartVar(vars[j]),
145 precedences->AddConditionalPrecedence(repository->EndVar(vars[j]),
146 repository->StartVar(vars[i]),
154 const std::vector<IntervalVariable>& vars) {
162 int j = sorted_tasks_.size();
163 sorted_tasks_.push_back(e);
165 sorted_tasks_[j] = sorted_tasks_[j - 1];
168 sorted_tasks_[j] = e;
169 DCHECK(std::is_sorted(sorted_tasks_.begin(), sorted_tasks_.end()));
173 if (j <= optimized_restart_) optimized_restart_ = 0;
178 const IntegerValue dmin = helper.
SizeMin(t);
183 const int size = sorted_tasks_.size();
184 for (
int i = 0;; ++i) {
185 if (i == size)
return;
186 if (sorted_tasks_[i].task == e.
task) {
187 sorted_tasks_.erase(sorted_tasks_.begin() + i);
192 optimized_restart_ = sorted_tasks_.size();
193 sorted_tasks_.push_back(e);
194 DCHECK(std::is_sorted(sorted_tasks_.begin(), sorted_tasks_.end()));
198 sorted_tasks_.erase(sorted_tasks_.begin() +
index);
199 optimized_restart_ = 0;
203 DCHECK(std::is_sorted(sorted_tasks_.begin(), sorted_tasks_.end()));
204 const int size = sorted_tasks_.size();
206 for (
int i = optimized_restart_; i < size; ++i) {
207 const Entry& e = sorted_tasks_[i];
209 optimized_restart_ = i;
219 int* critical_index)
const {
221 DCHECK(std::is_sorted(sorted_tasks_.begin(), sorted_tasks_.end()));
222 bool ignored =
false;
223 const int size = sorted_tasks_.size();
228 if (optimized_restart_ + 1 == size &&
229 sorted_tasks_[optimized_restart_].task == task_to_ignore) {
230 optimized_restart_ = 0;
233 for (
int i = optimized_restart_; i < size; ++i) {
234 const Entry& e = sorted_tasks_[i];
235 if (e.
task == task_to_ignore) {
241 if (!ignored) optimized_restart_ = i;
271 std::swap(task_before, task_after);
277 const IntegerValue end_min_before = helper_->
EndMin(task_before);
278 if (helper_->
StartMin(task_after) < end_min_before) {
293 const IntegerValue start_max_after = helper_->
StartMax(task_after);
294 if (helper_->
EndMax(task_before) > start_max_after) {
313 const int id = watcher->
Register(
this);
318 template <
bool time_direction>
321 task_to_disjunctives_.resize(helper_->
NumTasks());
324 const int id = watcher->
Register(
this);
327 watcher->NotifyThatPropagatorMayNotReachFixedPointInOnePass(
id);
330 template <
bool time_direction>
332 const std::vector<IntervalVariable>& vars) {
333 const int index = task_sets_.size();
334 task_sets_.emplace_back(vars.size());
336 for (
const IntervalVariable
var : vars) {
337 task_to_disjunctives_[
var.value()].push_back(
index);
341 template <
bool time_direction>
343 helper_->SynchronizeAndSetTimeDirection(time_direction);
344 const auto& task_by_increasing_end_min = helper_->TaskByIncreasingEndMin();
345 const auto& task_by_decreasing_start_max =
346 helper_->TaskByDecreasingStartMax();
348 for (
auto& task_set : task_sets_) task_set.Clear();
352 const int num_tasks = helper_->NumTasks();
353 task_is_added_.assign(num_tasks,
false);
354 int queue_index = num_tasks - 1;
355 for (
const auto task_time : task_by_increasing_end_min) {
356 const int t = task_time.task_index;
357 const IntegerValue
end_min = task_time.time;
358 if (helper_->IsAbsent(t))
continue;
361 while (queue_index >= 0) {
362 const auto to_insert = task_by_decreasing_start_max[queue_index];
363 const int task_index = to_insert.task_index;
364 const IntegerValue
start_max = to_insert.time;
366 if (helper_->IsPresent(task_index)) {
367 task_is_added_[task_index] =
true;
368 const IntegerValue shifted_smin = helper_->ShiftedStartMin(task_index);
369 const IntegerValue size_min = helper_->SizeMin(task_index);
370 for (
const int d_index : task_to_disjunctives_[task_index]) {
372 task_sets_[d_index].AddEntry({task_index, shifted_smin, size_min});
373 end_mins_[d_index] = task_sets_[d_index].ComputeEndMin();
374 max_of_end_min =
std::max(max_of_end_min, end_mins_[d_index]);
382 IntegerValue new_start_min = helper_->StartMin(t);
383 if (new_start_min >= max_of_end_min)
continue;
384 int best_critical_index = 0;
385 int best_d_index = -1;
386 if (task_is_added_[t]) {
387 for (
const int d_index : task_to_disjunctives_[t]) {
388 if (new_start_min >= end_mins_[d_index])
continue;
389 int critical_index = 0;
390 const IntegerValue end_min_of_critical_tasks =
391 task_sets_[d_index].ComputeEndMin(t,
393 DCHECK_LE(end_min_of_critical_tasks, max_of_end_min);
394 if (end_min_of_critical_tasks > new_start_min) {
395 new_start_min = end_min_of_critical_tasks;
396 best_d_index = d_index;
397 best_critical_index = critical_index;
403 for (
const int d_index : task_to_disjunctives_[t]) {
404 if (end_mins_[d_index] > new_start_min) {
405 new_start_min = end_mins_[d_index];
406 best_d_index = d_index;
409 if (best_d_index != -1) {
410 const IntegerValue end_min_of_critical_tasks =
411 task_sets_[best_d_index].ComputeEndMin(t,
412 &best_critical_index);
413 CHECK_EQ(end_min_of_critical_tasks, new_start_min);
418 if (best_d_index == -1)
continue;
423 helper_->ClearReason();
424 const std::vector<TaskSet::Entry>& sorted_tasks =
425 task_sets_[best_d_index].SortedTasks();
426 const IntegerValue window_start =
427 sorted_tasks[best_critical_index].start_min;
428 for (
int i = best_critical_index; i < sorted_tasks.size(); ++i) {
429 const int ct = sorted_tasks[i].task;
430 if (
ct == t)
continue;
431 helper_->AddPresenceReason(
ct);
432 helper_->AddEnergyAfterReason(
ct, sorted_tasks[i].size_min, window_start);
433 helper_->AddStartMaxReason(
ct,
end_min - 1);
435 helper_->AddEndMinReason(t,
end_min);
436 if (!helper_->IncreaseStartMin(t, new_start_min)) {
444 if (task_is_added_[t]) {
445 const IntegerValue shifted_smin = helper_->ShiftedStartMin(t);
446 const IntegerValue size_min = helper_->SizeMin(t);
447 for (
const int d_index : task_to_disjunctives_[t]) {
448 task_sets_[d_index].NotifyEntryIsNowLastIfPresent(
449 {t, shifted_smin, size_min});
450 end_mins_[d_index] = task_sets_[d_index].ComputeEndMin();
451 max_of_end_min =
std::max(max_of_end_min, end_mins_[d_index]);
474 IntegerValue relevant_end;
475 int relevant_size = 0;
477 const int task = task_time.task_index;
478 if (helper_->
IsAbsent(task))
continue;
480 const IntegerValue
start_min = task_time.time;
482 window_.push_back(task_time);
483 window_end += helper_->
SizeMin(task);
484 if (window_end > helper_->
EndMax(task)) {
485 relevant_size = window_.size();
486 relevant_end = window_end;
494 window_.resize(relevant_size);
495 if (relevant_size > 0 && !PropagateSubwindow(relevant_end)) {
501 window_.push_back(task_time);
507 window_.resize(relevant_size);
508 if (relevant_size > 0 && !PropagateSubwindow(relevant_end)) {
522 bool DisjunctiveOverloadChecker::PropagateSubwindow(
523 IntegerValue global_window_end) {
525 const int window_size = window_.size();
526 theta_tree_.
Reset(window_size);
527 task_by_increasing_end_max_.clear();
528 for (
int i = 0; i < window_size; ++i) {
530 const int task = window_[i].task_index;
532 if (
end_max < global_window_end) {
533 task_to_event_[task] = i;
534 task_by_increasing_end_max_.push_back({task,
end_max});
539 std::sort(task_by_increasing_end_max_.begin(),
540 task_by_increasing_end_max_.end());
541 for (
const auto task_time : task_by_increasing_end_max_) {
542 const int current_task = task_time.task_index;
547 if (helper_->
IsAbsent(current_task))
continue;
549 DCHECK_NE(task_to_event_[current_task], -1);
551 const int current_event = task_to_event_[current_task];
552 const IntegerValue energy_min = helper_->
SizeMin(current_task);
558 energy_min, energy_min);
561 current_event, window_[current_event].
time, energy_min);
565 const IntegerValue current_end = task_time.time;
569 const int critical_event =
571 const IntegerValue window_start = window_[critical_event].time;
572 const IntegerValue window_end =
574 for (
int event = critical_event;
event < window_size;
event++) {
575 const IntegerValue energy_min = theta_tree_.
EnergyMin(event);
576 if (energy_min > 0) {
577 const int task = window_[event].task_index;
594 IntegerValue available_energy;
596 current_end, &critical_event, &optional_event, &available_energy);
598 const int optional_task = window_[optional_event].task_index;
599 const IntegerValue optional_size_min = helper_->
SizeMin(optional_task);
600 const IntegerValue window_start = window_[critical_event].time;
601 const IntegerValue window_end =
602 current_end + optional_size_min - available_energy - 1;
603 for (
int event = critical_event;
event < window_size;
event++) {
604 const IntegerValue energy_min = theta_tree_.
EnergyMin(event);
605 if (energy_min > 0) {
606 const int task = window_[event].task_index;
619 if (!helper_->
IsAbsent(optional_task)) {
631 const int id = watcher->
Register(
this);
641 to_propagate_.clear();
642 processed_.assign(helper_->
NumTasks(),
false);
651 task_by_increasing_end_min_.clear();
654 const int task = task_time.task_index;
655 if (helper_->
IsAbsent(task))
continue;
657 const IntegerValue shifted_smin = task_time.time;
658 const IntegerValue size_min = helper_->
SizeMin(task);
668 const IntegerValue end_min_if_present =
673 if (helper_->
StartMin(task) < window_end) {
674 task_by_increasing_end_min_.push_back({task, end_min_if_present});
675 window_end =
std::max(window_end, shifted_smin) + size_min;
680 if (task_by_increasing_end_min_.size() > 1 && !PropagateSubwindow()) {
685 task_by_increasing_end_min_.clear();
686 task_by_increasing_end_min_.push_back({task, end_min_if_present});
687 window_end = end_min_if_present;
690 if (task_by_increasing_end_min_.size() > 1 && !PropagateSubwindow()) {
697 bool DisjunctiveDetectablePrecedences::PropagateSubwindow() {
698 DCHECK(!task_by_increasing_end_min_.empty());
703 task_by_increasing_end_min_.end());
704 const IntegerValue max_end_min = task_by_increasing_end_min_.back().time;
710 task_by_increasing_start_max_.clear();
711 for (
const TaskTime entry : task_by_increasing_end_min_) {
712 const int task = entry.task_index;
714 if (start_max < max_end_min && helper_->IsPresent(task)) {
715 task_by_increasing_start_max_.push_back({task,
start_max});
718 if (task_by_increasing_start_max_.empty())
return true;
719 std::sort(task_by_increasing_start_max_.begin(),
720 task_by_increasing_start_max_.end());
728 bool need_update =
false;
732 int blocking_task = -1;
733 const int queue_size = task_by_increasing_start_max_.size();
734 for (
const auto task_time : task_by_increasing_end_min_) {
741 const int current_task = task_time.task_index;
742 const IntegerValue current_end_min = task_time.time;
744 for (; queue_index < queue_size; ++queue_index) {
745 const auto to_insert = task_by_increasing_start_max_[queue_index];
746 const IntegerValue
start_max = to_insert.time;
749 const int t = to_insert.task_index;
763 if (!processed_[t]) {
764 if (blocking_task != -1) {
774 <<
" task should have mandatory part: "
776 DCHECK(to_propagate_.empty());
778 to_propagate_.push_back(t);
787 if (blocking_task != current_task) {
788 to_propagate_.push_back(current_task);
789 if (blocking_task != -1)
continue;
791 for (
const int t : to_propagate_) {
793 processed_[t] =
true;
808 if (task_set_end_min > helper_->
StartMin(t)) {
810 const std::vector<TaskSet::Entry>& sorted_tasks =
817 const IntegerValue end_min_if_present =
819 const IntegerValue window_start =
820 sorted_tasks[critical_index].start_min;
821 for (
int i = critical_index; i < sorted_tasks.size(); ++i) {
822 const int ct = sorted_tasks[i].task;
844 if (t == blocking_task) {
855 to_propagate_.clear();
862 const int id = watcher->
Register(
this);
875 const int task = task_time.task_index;
878 const IntegerValue
start_min = task_time.time;
880 window_.push_back(task_time);
881 window_end += helper_->
SizeMin(task);
885 if (window_.size() > 1 && !PropagateSubwindow()) {
891 window_.push_back(task_time);
894 if (window_.size() > 1 && !PropagateSubwindow()) {
900 bool DisjunctivePrecedences::PropagateSubwindow() {
906 index_to_end_vars_.clear();
907 for (
const auto task_time : window_) {
908 const int task = task_time.task_index;
913 index_to_end_vars_.push_back(end_exp.
var);
917 const int size = before_.size();
918 for (
int i = 0; i < size;) {
919 const IntegerVariable
var = before_[i].var;
923 const int initial_i = i;
925 for (; i < size && before_[i].var ==
var; ++i) {
926 const TaskTime task_time = window_[before_[i].index];
931 const AffineExpression& end_exp = helper_->
Ends()[task_time.task_index];
932 min_offset =
std::min(min_offset, before_[i].offset - end_exp.constant);
937 helper_->
SizeMin(task_time.task_index)});
944 const IntegerValue new_lb = task_set_.
ComputeEndMin() + min_offset;
946 const std::vector<TaskSet::Entry>& sorted_tasks = task_set_.
SortedTasks();
951 for (
int j = initial_i; j < i; ++j) {
952 const int task = window_[before_[j].index].task_index;
953 task_to_arc_index_[task] = before_[j].arc_index;
957 const IntegerValue window_start = sorted_tasks[critical_index].start_min;
958 for (
int i = critical_index; i < sorted_tasks.size(); ++i) {
959 const int ct = sorted_tasks[i].task;
964 const AffineExpression& end_exp = helper_->
Ends()[
ct];
966 task_to_arc_index_[
ct], min_offset + end_exp.constant,
983 const int id = watcher->
Register(
this);
993 const auto& task_by_decreasing_start_max =
995 const auto& task_by_increasing_shifted_start_min =
1009 int queue_index = task_by_decreasing_start_max.size() - 1;
1010 const int num_tasks = task_by_increasing_shifted_start_min.size();
1011 for (
int i = 0; i < num_tasks;) {
1012 start_min_window_.clear();
1014 for (; i < num_tasks; ++i) {
1015 const TaskTime task_time = task_by_increasing_shifted_start_min[i];
1017 if (!helper_->
IsPresent(task))
continue;
1020 if (start_min_window_.empty()) {
1021 start_min_window_.push_back(task_time);
1024 start_min_window_.push_back(task_time);
1025 window_end += helper_->
SizeMin(task);
1033 start_max_window_.clear();
1034 for (; queue_index >= 0; queue_index--) {
1035 const auto task_time = task_by_decreasing_start_max[queue_index];
1038 if (task_time.time >= window_end)
break;
1039 if (helper_->
IsAbsent(task_time.task_index))
continue;
1040 start_max_window_.push_back(task_time);
1046 if (start_min_window_.size() <= 1)
continue;
1049 if (!start_max_window_.empty() && !PropagateSubwindow()) {
1056 bool DisjunctiveNotLast::PropagateSubwindow() {
1057 auto& task_by_increasing_end_max = start_max_window_;
1058 for (
TaskTime& entry : task_by_increasing_end_max) {
1059 entry.time = helper_->
EndMax(entry.task_index);
1062 task_by_increasing_end_max.end());
1064 const IntegerValue threshold = task_by_increasing_end_max.back().time;
1065 auto& task_by_increasing_start_max = start_min_window_;
1067 for (
const TaskTime entry : task_by_increasing_start_max) {
1068 const int task = entry.task_index;
1072 task_by_increasing_start_max[queue_size++] = {task,
start_max};
1078 if (queue_size <= 1)
return true;
1080 task_by_increasing_start_max.resize(queue_size);
1081 std::sort(task_by_increasing_start_max.begin(),
1082 task_by_increasing_start_max.end());
1085 int queue_index = 0;
1086 for (
const auto task_time : task_by_increasing_end_max) {
1087 const int t = task_time.task_index;
1088 const IntegerValue
end_max = task_time.time;
1094 while (queue_index < queue_size) {
1095 const auto to_insert = task_by_increasing_start_max[queue_index];
1096 const IntegerValue
start_max = to_insert.time;
1099 const int task_index = to_insert.task_index;
1102 helper_->
SizeMin(task_index)});
1116 int critical_index = 0;
1117 const IntegerValue end_min_of_critical_tasks =
1119 if (end_min_of_critical_tasks <= helper_->StartMax(t))
continue;
1124 const std::vector<TaskSet::Entry>& sorted_tasks = task_set_.
SortedTasks();
1125 const int sorted_tasks_size = sorted_tasks.size();
1126 for (
int i = critical_index; i < sorted_tasks_size; ++i) {
1127 const int ct = sorted_tasks[i].task;
1128 if (t ==
ct)
continue;
1138 end_max > largest_ct_start_max);
1139 if (
end_max > largest_ct_start_max) {
1142 const IntegerValue window_start = sorted_tasks[critical_index].start_min;
1143 for (
int i = critical_index; i < sorted_tasks_size; ++i) {
1144 const int ct = sorted_tasks[i].task;
1145 if (
ct == t)
continue;
1157 if (!helper_->
DecreaseEndMax(t, largest_ct_start_max))
return false;
1164 const int id = watcher->
Register(
this);
1171 const int num_tasks = helper_->
NumTasks();
1173 is_gray_.resize(num_tasks,
false);
1174 non_gray_task_to_event_.resize(num_tasks);
1179 const int task = task_time.task_index;
1180 if (helper_->
IsAbsent(task))
continue;
1184 if (helper_->
StartMin(task) < window_end) {
1185 window_.push_back(task_time);
1186 window_end += helper_->
SizeMin(task);
1192 if (window_.size() > 2 && !PropagateSubwindow(window_end)) {
1198 window_.push_back(task_time);
1199 window_end = task_time.time + helper_->
SizeMin(task);
1201 if (window_.size() > 2 && !PropagateSubwindow(window_end)) {
1207 bool DisjunctiveEdgeFinding::PropagateSubwindow(IntegerValue window_end_min) {
1209 task_by_increasing_end_max_.clear();
1210 for (
const auto task_time : window_) {
1211 const int task = task_time.task_index;
1224 is_gray_[task] =
false;
1225 task_by_increasing_end_max_.push_back({task,
end_max});
1227 is_gray_[task] =
true;
1233 if (task_by_increasing_end_max_.size() < 2)
return true;
1234 std::sort(task_by_increasing_end_max_.begin(),
1235 task_by_increasing_end_max_.end());
1246 const int window_size = window_.size();
1247 event_size_.clear();
1248 theta_tree_.
Reset(window_size);
1249 for (
int event = 0;
event < window_size; ++event) {
1250 const TaskTime task_time = window_[event];
1251 const int task = task_time.task_index;
1252 const IntegerValue energy_min = helper_->
SizeMin(task);
1253 event_size_.push_back(energy_min);
1254 if (is_gray_[task]) {
1257 non_gray_task_to_event_[task] = event;
1266 DCHECK(!is_gray_[task_by_increasing_end_max_.back().task_index]);
1267 const IntegerValue non_gray_end_max =
1268 task_by_increasing_end_max_.back().time;
1271 const IntegerValue non_gray_end_min = theta_tree_.
GetEnvelope();
1272 if (non_gray_end_min > non_gray_end_max) {
1276 const int critical_event =
1278 const IntegerValue window_start = window_[critical_event].time;
1279 const IntegerValue window_end =
1281 for (
int event = critical_event;
event < window_size;
event++) {
1282 const int task = window_[event].task_index;
1283 if (is_gray_[task])
continue;
1301 int critical_event_with_gray;
1303 IntegerValue available_energy;
1305 non_gray_end_max, &critical_event_with_gray, &gray_event,
1307 const int gray_task = window_[gray_event].task_index;
1310 DCHECK(is_gray_[gray_task]);
1311 if (helper_->
StartMin(gray_task) < non_gray_end_min) {
1314 const int critical_event =
1317 const int first_event =
1318 std::min(critical_event, critical_event_with_gray);
1319 const int second_event =
1320 std::max(critical_event, critical_event_with_gray);
1321 const IntegerValue first_start = window_[first_event].time;
1322 const IntegerValue second_start = window_[second_event].time;
1326 const IntegerValue window_end =
1327 non_gray_end_max + event_size_[gray_event] - available_energy - 1;
1328 CHECK_GE(window_end, non_gray_end_max);
1332 for (
int event = first_event;
event < window_size;
event++) {
1333 const int task = window_[event].task_index;
1334 if (is_gray_[task])
continue;
1337 task, event_size_[event],
1338 event >= second_event ? second_start : first_start);
1345 window_[critical_event_with_gray].
time);
1362 if (task_by_increasing_end_max_.size() <= 2)
break;
1365 if (task_by_increasing_end_max_[0].
time >=
1371 const int new_gray_task = task_by_increasing_end_max_.back().task_index;
1372 task_by_increasing_end_max_.pop_back();
1373 const int new_gray_event = non_gray_task_to_event_[new_gray_task];
1374 DCHECK(!is_gray_[new_gray_task]);
1375 is_gray_[new_gray_task] =
true;
1377 window_[new_gray_event].
time,
1378 event_size_[new_gray_event]);
1385 const int id = watcher->
Register(
this);