22 #include "ortools/sat/sat_parameters.pb.h"
31 const std::vector<IntervalVariable>& vars) {
33 bool is_all_different =
true;
35 for (
const IntervalVariable
var : vars) {
40 is_all_different =
false;
44 if (is_all_different) {
45 std::vector<IntegerVariable> starts;
46 starts.reserve(vars.size());
47 for (
const IntervalVariable
var : vars) {
55 const auto& sat_parameters = *
model->GetOrCreate<SatParameters>();
56 if (vars.size() > 2 && sat_parameters.use_combined_no_overlap()) {
64 model->TakeOwnership(helper);
69 std::vector<AffineExpression> demands(vars.size(), one);
73 model->TakeOwnership(timetable);
77 if (vars.size() == 2) {
80 model->TakeOwnership(propagator);
89 watcher->SetPropagatorPriority(
id, 1);
90 model->TakeOwnership(overload_checker);
92 for (
const bool time_direction : {
true,
false}) {
95 const int id = detectable_precedences->
RegisterWith(watcher);
96 watcher->SetPropagatorPriority(
id, 2);
97 model->TakeOwnership(detectable_precedences);
99 for (
const bool time_direction : {
true,
false}) {
103 watcher->SetPropagatorPriority(
id, 3);
104 model->TakeOwnership(not_last);
106 for (
const bool time_direction : {
true,
false}) {
110 watcher->SetPropagatorPriority(
id, 4);
111 model->TakeOwnership(edge_finding);
118 if (sat_parameters.use_precedences_in_disjunctive_constraint() &&
119 !sat_parameters.use_combined_no_overlap()) {
120 for (
const bool time_direction : {
true,
false}) {
125 watcher->SetPropagatorPriority(
id, 5);
126 model->TakeOwnership(precedences);
133 const std::vector<IntervalVariable>& vars) {
139 for (
int i = 0; i < vars.size(); ++i) {
140 for (
int j = 0; j < i; ++j) {
144 precedences->AddConditionalPrecedence(repository->EndVar(vars[i]),
145 repository->StartVar(vars[j]),
147 precedences->AddConditionalPrecedence(repository->EndVar(vars[j]),
148 repository->StartVar(vars[i]),
156 const std::vector<IntervalVariable>& vars) {
164 int j = sorted_tasks_.size();
165 sorted_tasks_.push_back(e);
167 sorted_tasks_[j] = sorted_tasks_[j - 1];
170 sorted_tasks_[j] = e;
171 DCHECK(std::is_sorted(sorted_tasks_.begin(), sorted_tasks_.end()));
175 if (j <= optimized_restart_) optimized_restart_ = 0;
180 const IntegerValue dmin = helper.
SizeMin(t);
185 const int size = sorted_tasks_.size();
186 for (
int i = 0;; ++i) {
187 if (i == size)
return;
188 if (sorted_tasks_[i].task == e.
task) {
189 sorted_tasks_.erase(sorted_tasks_.begin() + i);
194 optimized_restart_ = sorted_tasks_.size();
195 sorted_tasks_.push_back(e);
196 DCHECK(std::is_sorted(sorted_tasks_.begin(), sorted_tasks_.end()));
200 sorted_tasks_.erase(sorted_tasks_.begin() +
index);
201 optimized_restart_ = 0;
205 DCHECK(std::is_sorted(sorted_tasks_.begin(), sorted_tasks_.end()));
206 const int size = sorted_tasks_.size();
208 for (
int i = optimized_restart_; i < size; ++i) {
209 const Entry& e = sorted_tasks_[i];
211 optimized_restart_ = i;
221 int* critical_index)
const {
223 DCHECK(std::is_sorted(sorted_tasks_.begin(), sorted_tasks_.end()));
224 bool ignored =
false;
225 const int size = sorted_tasks_.size();
230 if (optimized_restart_ + 1 == size &&
231 sorted_tasks_[optimized_restart_].task == task_to_ignore) {
232 optimized_restart_ = 0;
235 for (
int i = optimized_restart_; i < size; ++i) {
236 const Entry& e = sorted_tasks_[i];
237 if (e.
task == task_to_ignore) {
243 if (!ignored) optimized_restart_ = i;
273 std::swap(task_before, task_after);
279 const IntegerValue end_min_before = helper_->
EndMin(task_before);
280 if (helper_->
StartMin(task_after) < end_min_before) {
295 const IntegerValue start_max_after = helper_->
StartMax(task_after);
296 if (helper_->
EndMax(task_before) > start_max_after) {
315 const int id = watcher->
Register(
this);
320 template <
bool time_direction>
323 task_to_disjunctives_.resize(helper_->
NumTasks());
326 const int id = watcher->
Register(
this);
329 watcher->NotifyThatPropagatorMayNotReachFixedPointInOnePass(
id);
332 template <
bool time_direction>
334 const std::vector<IntervalVariable>& vars) {
335 const int index = task_sets_.size();
336 task_sets_.emplace_back(vars.size());
338 for (
const IntervalVariable
var : vars) {
339 task_to_disjunctives_[
var.value()].push_back(
index);
343 template <
bool time_direction>
345 helper_->SynchronizeAndSetTimeDirection(time_direction);
346 const auto& task_by_increasing_end_min = helper_->TaskByIncreasingEndMin();
347 const auto& task_by_decreasing_start_max =
348 helper_->TaskByDecreasingStartMax();
350 for (
auto& task_set : task_sets_) task_set.Clear();
354 const int num_tasks = helper_->NumTasks();
355 task_is_added_.assign(num_tasks,
false);
356 int queue_index = num_tasks - 1;
357 for (
const auto task_time : task_by_increasing_end_min) {
358 const int t = task_time.task_index;
359 const IntegerValue
end_min = task_time.time;
360 if (helper_->IsAbsent(t))
continue;
363 while (queue_index >= 0) {
364 const auto to_insert = task_by_decreasing_start_max[queue_index];
365 const int task_index = to_insert.task_index;
366 const IntegerValue
start_max = to_insert.time;
368 if (helper_->IsPresent(task_index)) {
369 task_is_added_[task_index] =
true;
370 const IntegerValue shifted_smin = helper_->ShiftedStartMin(task_index);
371 const IntegerValue size_min = helper_->SizeMin(task_index);
372 for (
const int d_index : task_to_disjunctives_[task_index]) {
374 task_sets_[d_index].AddEntry({task_index, shifted_smin, size_min});
375 end_mins_[d_index] = task_sets_[d_index].ComputeEndMin();
376 max_of_end_min =
std::max(max_of_end_min, end_mins_[d_index]);
384 IntegerValue new_start_min = helper_->StartMin(t);
385 if (new_start_min >= max_of_end_min)
continue;
386 int best_critical_index = 0;
387 int best_d_index = -1;
388 if (task_is_added_[t]) {
389 for (
const int d_index : task_to_disjunctives_[t]) {
390 if (new_start_min >= end_mins_[d_index])
continue;
391 int critical_index = 0;
392 const IntegerValue end_min_of_critical_tasks =
393 task_sets_[d_index].ComputeEndMin(t,
395 DCHECK_LE(end_min_of_critical_tasks, max_of_end_min);
396 if (end_min_of_critical_tasks > new_start_min) {
397 new_start_min = end_min_of_critical_tasks;
398 best_d_index = d_index;
399 best_critical_index = critical_index;
405 for (
const int d_index : task_to_disjunctives_[t]) {
406 if (end_mins_[d_index] > new_start_min) {
407 new_start_min = end_mins_[d_index];
408 best_d_index = d_index;
411 if (best_d_index != -1) {
412 const IntegerValue end_min_of_critical_tasks =
413 task_sets_[best_d_index].ComputeEndMin(t,
414 &best_critical_index);
415 CHECK_EQ(end_min_of_critical_tasks, new_start_min);
420 if (best_d_index == -1)
continue;
425 helper_->ClearReason();
426 const std::vector<TaskSet::Entry>& sorted_tasks =
427 task_sets_[best_d_index].SortedTasks();
428 const IntegerValue window_start =
429 sorted_tasks[best_critical_index].start_min;
430 for (
int i = best_critical_index; i < sorted_tasks.size(); ++i) {
431 const int ct = sorted_tasks[i].task;
432 if (
ct == t)
continue;
433 helper_->AddPresenceReason(
ct);
434 helper_->AddEnergyAfterReason(
ct, sorted_tasks[i].size_min, window_start);
435 helper_->AddStartMaxReason(
ct,
end_min - 1);
437 helper_->AddEndMinReason(t,
end_min);
438 if (!helper_->IncreaseStartMin(t, new_start_min)) {
446 if (task_is_added_[t]) {
447 const IntegerValue shifted_smin = helper_->ShiftedStartMin(t);
448 const IntegerValue size_min = helper_->SizeMin(t);
449 for (
const int d_index : task_to_disjunctives_[t]) {
450 task_sets_[d_index].NotifyEntryIsNowLastIfPresent(
451 {t, shifted_smin, size_min});
452 end_mins_[d_index] = task_sets_[d_index].ComputeEndMin();
453 max_of_end_min =
std::max(max_of_end_min, end_mins_[d_index]);
476 IntegerValue relevant_end;
477 int relevant_size = 0;
479 const int task = task_time.task_index;
480 if (helper_->
IsAbsent(task))
continue;
482 const IntegerValue
start_min = task_time.time;
484 window_.push_back(task_time);
485 window_end += helper_->
SizeMin(task);
486 if (window_end > helper_->
EndMax(task)) {
487 relevant_size = window_.size();
488 relevant_end = window_end;
496 window_.resize(relevant_size);
497 if (relevant_size > 0 && !PropagateSubwindow(relevant_end)) {
503 window_.push_back(task_time);
509 window_.resize(relevant_size);
510 if (relevant_size > 0 && !PropagateSubwindow(relevant_end)) {
524 bool DisjunctiveOverloadChecker::PropagateSubwindow(
525 IntegerValue global_window_end) {
527 const int window_size = window_.size();
528 theta_tree_.
Reset(window_size);
529 task_by_increasing_end_max_.clear();
530 for (
int i = 0; i < window_size; ++i) {
532 const int task = window_[i].task_index;
534 if (
end_max < global_window_end) {
535 task_to_event_[task] = i;
536 task_by_increasing_end_max_.push_back({task,
end_max});
541 std::sort(task_by_increasing_end_max_.begin(),
542 task_by_increasing_end_max_.end());
543 for (
const auto task_time : task_by_increasing_end_max_) {
544 const int current_task = task_time.task_index;
549 if (helper_->
IsAbsent(current_task))
continue;
551 DCHECK_NE(task_to_event_[current_task], -1);
553 const int current_event = task_to_event_[current_task];
554 const IntegerValue energy_min = helper_->
SizeMin(current_task);
560 energy_min, energy_min);
563 current_event, window_[current_event].
time, energy_min);
567 const IntegerValue current_end = task_time.time;
571 const int critical_event =
573 const IntegerValue window_start = window_[critical_event].time;
574 const IntegerValue window_end =
576 for (
int event = critical_event;
event < window_size;
event++) {
577 const IntegerValue energy_min = theta_tree_.
EnergyMin(event);
578 if (energy_min > 0) {
579 const int task = window_[event].task_index;
596 IntegerValue available_energy;
598 current_end, &critical_event, &optional_event, &available_energy);
600 const int optional_task = window_[optional_event].task_index;
601 const IntegerValue optional_size_min = helper_->
SizeMin(optional_task);
602 const IntegerValue window_start = window_[critical_event].time;
603 const IntegerValue window_end =
604 current_end + optional_size_min - available_energy - 1;
605 for (
int event = critical_event;
event < window_size;
event++) {
606 const IntegerValue energy_min = theta_tree_.
EnergyMin(event);
607 if (energy_min > 0) {
608 const int task = window_[event].task_index;
621 if (!helper_->
IsAbsent(optional_task)) {
633 const int id = watcher->
Register(
this);
643 to_propagate_.clear();
644 processed_.assign(helper_->
NumTasks(),
false);
653 task_by_increasing_end_min_.clear();
656 const int task = task_time.task_index;
657 if (helper_->
IsAbsent(task))
continue;
659 const IntegerValue shifted_smin = task_time.time;
660 const IntegerValue size_min = helper_->
SizeMin(task);
670 const IntegerValue end_min_if_present =
675 if (helper_->
StartMin(task) < window_end) {
676 task_by_increasing_end_min_.push_back({task, end_min_if_present});
677 window_end =
std::max(window_end, shifted_smin) + size_min;
682 if (task_by_increasing_end_min_.size() > 1 && !PropagateSubwindow()) {
687 task_by_increasing_end_min_.clear();
688 task_by_increasing_end_min_.push_back({task, end_min_if_present});
689 window_end = end_min_if_present;
692 if (task_by_increasing_end_min_.size() > 1 && !PropagateSubwindow()) {
699 bool DisjunctiveDetectablePrecedences::PropagateSubwindow() {
700 DCHECK(!task_by_increasing_end_min_.empty());
705 task_by_increasing_end_min_.end());
706 const IntegerValue max_end_min = task_by_increasing_end_min_.back().time;
712 task_by_increasing_start_max_.clear();
713 for (
const TaskTime entry : task_by_increasing_end_min_) {
714 const int task = entry.task_index;
716 if (start_max < max_end_min && helper_->IsPresent(task)) {
717 task_by_increasing_start_max_.push_back({task,
start_max});
720 if (task_by_increasing_start_max_.empty())
return true;
721 std::sort(task_by_increasing_start_max_.begin(),
722 task_by_increasing_start_max_.end());
730 bool need_update =
false;
734 int blocking_task = -1;
735 const int queue_size = task_by_increasing_start_max_.size();
736 for (
const auto task_time : task_by_increasing_end_min_) {
743 const int current_task = task_time.task_index;
744 const IntegerValue current_end_min = task_time.time;
746 for (; queue_index < queue_size; ++queue_index) {
747 const auto to_insert = task_by_increasing_start_max_[queue_index];
748 const IntegerValue
start_max = to_insert.time;
751 const int t = to_insert.task_index;
765 if (!processed_[t]) {
766 if (blocking_task != -1) {
776 <<
" task should have mandatory part: "
778 DCHECK(to_propagate_.empty());
780 to_propagate_.push_back(t);
789 if (blocking_task != current_task) {
790 to_propagate_.push_back(current_task);
791 if (blocking_task != -1)
continue;
793 for (
const int t : to_propagate_) {
795 processed_[t] =
true;
810 if (task_set_end_min > helper_->
StartMin(t)) {
812 const std::vector<TaskSet::Entry>& sorted_tasks =
819 const IntegerValue end_min_if_present =
821 const IntegerValue window_start =
822 sorted_tasks[critical_index].start_min;
823 for (
int i = critical_index; i < sorted_tasks.size(); ++i) {
824 const int ct = sorted_tasks[i].task;
846 if (t == blocking_task) {
857 to_propagate_.clear();
864 const int id = watcher->
Register(
this);
877 const int task = task_time.task_index;
880 const IntegerValue
start_min = task_time.time;
882 window_.push_back(task_time);
883 window_end += helper_->
SizeMin(task);
887 if (window_.size() > 1 && !PropagateSubwindow()) {
893 window_.push_back(task_time);
896 if (window_.size() > 1 && !PropagateSubwindow()) {
902 bool DisjunctivePrecedences::PropagateSubwindow() {
908 index_to_end_vars_.clear();
909 for (
const auto task_time : window_) {
910 const int task = task_time.task_index;
915 index_to_end_vars_.push_back(end_exp.
var);
919 const int size = before_.size();
920 for (
int i = 0; i < size;) {
921 const IntegerVariable
var = before_[i].var;
925 const int initial_i = i;
927 for (; i < size && before_[i].var ==
var; ++i) {
928 const TaskTime task_time = window_[before_[i].index];
933 const AffineExpression& end_exp = helper_->
Ends()[task_time.task_index];
934 min_offset =
std::min(min_offset, before_[i].offset - end_exp.constant);
939 helper_->
SizeMin(task_time.task_index)});
946 const IntegerValue new_lb = task_set_.
ComputeEndMin() + min_offset;
948 const std::vector<TaskSet::Entry>& sorted_tasks = task_set_.
SortedTasks();
953 for (
int j = initial_i; j < i; ++j) {
954 const int task = window_[before_[j].index].task_index;
955 task_to_arc_index_[task] = before_[j].arc_index;
959 const IntegerValue window_start = sorted_tasks[critical_index].start_min;
960 for (
int i = critical_index; i < sorted_tasks.size(); ++i) {
961 const int ct = sorted_tasks[i].task;
966 const AffineExpression& end_exp = helper_->
Ends()[
ct];
968 task_to_arc_index_[
ct], min_offset + end_exp.constant,
985 const int id = watcher->
Register(
this);
995 const auto& task_by_decreasing_start_max =
997 const auto& task_by_increasing_shifted_start_min =
1011 int queue_index = task_by_decreasing_start_max.size() - 1;
1012 const int num_tasks = task_by_increasing_shifted_start_min.size();
1013 for (
int i = 0; i < num_tasks;) {
1014 start_min_window_.clear();
1016 for (; i < num_tasks; ++i) {
1017 const TaskTime task_time = task_by_increasing_shifted_start_min[i];
1019 if (!helper_->
IsPresent(task))
continue;
1022 if (start_min_window_.empty()) {
1023 start_min_window_.push_back(task_time);
1026 start_min_window_.push_back(task_time);
1027 window_end += helper_->
SizeMin(task);
1035 start_max_window_.clear();
1036 for (; queue_index >= 0; queue_index--) {
1037 const auto task_time = task_by_decreasing_start_max[queue_index];
1040 if (task_time.time >= window_end)
break;
1041 if (helper_->
IsAbsent(task_time.task_index))
continue;
1042 start_max_window_.push_back(task_time);
1048 if (start_min_window_.size() <= 1)
continue;
1051 if (!start_max_window_.empty() && !PropagateSubwindow()) {
1058 bool DisjunctiveNotLast::PropagateSubwindow() {
1059 auto& task_by_increasing_end_max = start_max_window_;
1060 for (
TaskTime& entry : task_by_increasing_end_max) {
1061 entry.time = helper_->
EndMax(entry.task_index);
1064 task_by_increasing_end_max.end());
1066 const IntegerValue threshold = task_by_increasing_end_max.back().time;
1067 auto& task_by_increasing_start_max = start_min_window_;
1069 for (
const TaskTime entry : task_by_increasing_start_max) {
1070 const int task = entry.task_index;
1074 task_by_increasing_start_max[queue_size++] = {task,
start_max};
1080 if (queue_size <= 1)
return true;
1082 task_by_increasing_start_max.resize(queue_size);
1083 std::sort(task_by_increasing_start_max.begin(),
1084 task_by_increasing_start_max.end());
1087 int queue_index = 0;
1088 for (
const auto task_time : task_by_increasing_end_max) {
1089 const int t = task_time.task_index;
1090 const IntegerValue
end_max = task_time.time;
1096 while (queue_index < queue_size) {
1097 const auto to_insert = task_by_increasing_start_max[queue_index];
1098 const IntegerValue
start_max = to_insert.time;
1101 const int task_index = to_insert.task_index;
1104 helper_->
SizeMin(task_index)});
1118 int critical_index = 0;
1119 const IntegerValue end_min_of_critical_tasks =
1121 if (end_min_of_critical_tasks <= helper_->StartMax(t))
continue;
1126 const std::vector<TaskSet::Entry>& sorted_tasks = task_set_.
SortedTasks();
1127 const int sorted_tasks_size = sorted_tasks.size();
1128 for (
int i = critical_index; i < sorted_tasks_size; ++i) {
1129 const int ct = sorted_tasks[i].task;
1130 if (t ==
ct)
continue;
1140 end_max > largest_ct_start_max);
1141 if (
end_max > largest_ct_start_max) {
1144 const IntegerValue window_start = sorted_tasks[critical_index].start_min;
1145 for (
int i = critical_index; i < sorted_tasks_size; ++i) {
1146 const int ct = sorted_tasks[i].task;
1147 if (
ct == t)
continue;
1159 if (!helper_->
DecreaseEndMax(t, largest_ct_start_max))
return false;
1166 const int id = watcher->
Register(
this);
1173 const int num_tasks = helper_->
NumTasks();
1175 is_gray_.resize(num_tasks,
false);
1176 non_gray_task_to_event_.resize(num_tasks);
1181 const int task = task_time.task_index;
1182 if (helper_->
IsAbsent(task))
continue;
1186 if (helper_->
StartMin(task) < window_end) {
1187 window_.push_back(task_time);
1188 window_end += helper_->
SizeMin(task);
1194 if (window_.size() > 2 && !PropagateSubwindow(window_end)) {
1200 window_.push_back(task_time);
1201 window_end = task_time.time + helper_->
SizeMin(task);
1203 if (window_.size() > 2 && !PropagateSubwindow(window_end)) {
1209 bool DisjunctiveEdgeFinding::PropagateSubwindow(IntegerValue window_end_min) {
1211 task_by_increasing_end_max_.clear();
1212 for (
const auto task_time : window_) {
1213 const int task = task_time.task_index;
1226 is_gray_[task] =
false;
1227 task_by_increasing_end_max_.push_back({task,
end_max});
1229 is_gray_[task] =
true;
1235 if (task_by_increasing_end_max_.size() < 2)
return true;
1236 std::sort(task_by_increasing_end_max_.begin(),
1237 task_by_increasing_end_max_.end());
1248 const int window_size = window_.size();
1249 event_size_.clear();
1250 theta_tree_.
Reset(window_size);
1251 for (
int event = 0;
event < window_size; ++event) {
1252 const TaskTime task_time = window_[event];
1253 const int task = task_time.task_index;
1254 const IntegerValue energy_min = helper_->
SizeMin(task);
1255 event_size_.push_back(energy_min);
1256 if (is_gray_[task]) {
1259 non_gray_task_to_event_[task] = event;
1268 DCHECK(!is_gray_[task_by_increasing_end_max_.back().task_index]);
1269 const IntegerValue non_gray_end_max =
1270 task_by_increasing_end_max_.back().time;
1273 const IntegerValue non_gray_end_min = theta_tree_.
GetEnvelope();
1274 if (non_gray_end_min > non_gray_end_max) {
1278 const int critical_event =
1280 const IntegerValue window_start = window_[critical_event].time;
1281 const IntegerValue window_end =
1283 for (
int event = critical_event;
event < window_size;
event++) {
1284 const int task = window_[event].task_index;
1285 if (is_gray_[task])
continue;
1303 int critical_event_with_gray;
1305 IntegerValue available_energy;
1307 non_gray_end_max, &critical_event_with_gray, &gray_event,
1309 const int gray_task = window_[gray_event].task_index;
1312 DCHECK(is_gray_[gray_task]);
1313 if (helper_->
StartMin(gray_task) < non_gray_end_min) {
1316 const int critical_event =
1319 const int first_event =
1320 std::min(critical_event, critical_event_with_gray);
1321 const int second_event =
1322 std::max(critical_event, critical_event_with_gray);
1323 const IntegerValue first_start = window_[first_event].time;
1324 const IntegerValue second_start = window_[second_event].time;
1328 const IntegerValue window_end =
1329 non_gray_end_max + event_size_[gray_event] - available_energy - 1;
1330 CHECK_GE(window_end, non_gray_end_max);
1334 for (
int event = first_event;
event < window_size;
event++) {
1335 const int task = window_[event].task_index;
1336 if (is_gray_[task])
continue;
1339 task, event_size_[event],
1340 event >= second_event ? second_start : first_start);
1347 window_[critical_event_with_gray].
time);
1364 if (task_by_increasing_end_max_.size() <= 2)
break;
1367 if (task_by_increasing_end_max_[0].
time >=
1373 const int new_gray_task = task_by_increasing_end_max_.back().task_index;
1374 task_by_increasing_end_max_.pop_back();
1375 const int new_gray_event = non_gray_task_to_event_[new_gray_task];
1376 DCHECK(!is_gray_[new_gray_task]);
1377 is_gray_[new_gray_task] =
true;
1379 window_[new_gray_event].
time,
1380 event_size_[new_gray_event]);
1387 const int id = watcher->
Register(
this);
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
void AddNoOverlap(const std::vector< IntervalVariable > &var)
CombinedDisjunctive(Model *model)
int RegisterWith(GenericLiteralWatcher *watcher)
int RegisterWith(GenericLiteralWatcher *watcher)
int RegisterWith(GenericLiteralWatcher *watcher)
int RegisterWith(GenericLiteralWatcher *watcher)
int RegisterWith(GenericLiteralWatcher *watcher)
int RegisterWith(GenericLiteralWatcher *watcher)
int Register(PropagatorInterface *propagator)
void NotifyThatPropagatorMayNotReachFixedPointInOnePass(int id)
bool IsCurrentlyIgnored(IntegerVariable i) const
IntegerValue LowerBound(IntegerVariable i) const
IntegerValue MaxSize(IntervalVariable i) const
AffineExpression Start(IntervalVariable i) const
IntegerValue MinSize(IntervalVariable i) const
bool IsOptional(IntervalVariable i) const
Class that owns everything related to a particular optimization model.
void AddPrecedenceReason(int arc_index, IntegerValue min_offset, std::vector< Literal > *literal_reason, std::vector< IntegerLiteral > *integer_reason) const
void ComputePrecedences(const std::vector< IntegerVariable > &vars, std::vector< IntegerPrecedences > *output)
BooleanVariable NewBooleanVariable()
IntegerValue ShiftedStartMin(int t) const
IntegerValue EndMin(int t) const
ABSL_MUST_USE_RESULT bool PushIntegerLiteral(IntegerLiteral lit)
std::vector< Literal > * MutableLiteralReason()
ABSL_MUST_USE_RESULT bool PushTaskAbsence(int t)
void WatchAllTasks(int id, GenericLiteralWatcher *watcher, bool watch_start_max=true, bool watch_end_max=true) const
void AddPresenceReason(int t)
std::vector< IntegerLiteral > * MutableIntegerReason()
bool IsPresent(int t) const
void AddEnergyAfterReason(int t, IntegerValue energy_min, IntegerValue time)
bool InPropagationLoop() const
std::string TaskDebugString(int t) const
void AddEndMinReason(int t, IntegerValue lower_bound)
ABSL_MUST_USE_RESULT bool IncreaseStartMin(int t, IntegerValue new_start_min)
void SynchronizeAndSetTimeDirection(bool is_forward)
bool IsAbsent(int t) const
IntegerValue EndMax(int t) const
ABSL_MUST_USE_RESULT bool ReportConflict()
ABSL_MUST_USE_RESULT bool DecreaseEndMax(int t, IntegerValue new_start_max)
IntegerValue StartMin(int t) const
const std::vector< TaskTime > & TaskByDecreasingStartMax()
void AddEndMaxReason(int t, IntegerValue upper_bound)
IntegerValue StartMax(int t) const
const std::vector< TaskTime > & TaskByIncreasingShiftedStartMin()
void AddReasonForBeingBefore(int before, int after)
void AddStartMaxReason(int t, IntegerValue upper_bound)
IntegerValue SizeMin(int t) const
const std::vector< AffineExpression > & Ends() const
void AddUnsortedEntry(const Entry &e)
void NotifyEntryIsNowLastIfPresent(const Entry &e)
void RemoveEntryWithIndex(int index)
int GetCriticalIndex() const
void AddShiftedStartMinEntry(const SchedulingConstraintHelper &helper, int t)
IntegerValue ComputeEndMin() const
void AddEntry(const Entry &e)
IntegerValue ComputeEndMin(int task_to_ignore, int *critical_index) const
const std::vector< Entry > & SortedTasks() const
IntegerType GetEnvelopeOf(int event) const
void GetEventsWithOptionalEnvelopeGreaterThan(IntegerType target_envelope, int *critical_event, int *optional_event, IntegerType *available_energy) const
IntegerType GetOptionalEnvelope() const
void RemoveEvent(int event)
int GetMaxEventWithEnvelopeGreaterThan(IntegerType target_envelope) const
void Reset(int num_events)
void AddOrUpdateOptionalEvent(int event, IntegerType initial_envelope_opt, IntegerType energy_max)
IntegerType EnergyMin(int event) const
void AddOrUpdateEvent(int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max)
IntegerType GetEnvelope() const
void RegisterWith(GenericLiteralWatcher *watcher)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
std::function< void(Model *)> AllDifferentOnBounds(const std::vector< IntegerVariable > &vars)
const IntegerVariable kNoIntegerVariable(-1)
std::function< void(Model *)> DisjunctiveWithBooleanPrecedencesOnly(const std::vector< IntervalVariable > &vars)
std::function< void(Model *)> DisjunctiveWithBooleanPrecedences(const std::vector< IntervalVariable > &vars)
std::function< void(Model *)> Disjunctive(const std::vector< IntervalVariable > &vars)
std::function< IntegerVariable(const Model &)> StartVar(IntervalVariable v)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void IncrementalSort(int max_comparisons, Iterator begin, Iterator end, Compare comp=Compare{}, bool is_stable=false)
static IntegerLiteral GreaterOrEqual(IntegerVariable i, IntegerValue bound)