27#include "absl/base/attributes.h"
28#include "absl/container/btree_set.h"
29#include "absl/container/flat_hash_map.h"
30#include "absl/log/check.h"
31#include "absl/strings/str_cat.h"
32#include "absl/strings/str_join.h"
33#include "absl/strings/string_view.h"
34#include "absl/types/span.h"
60const double kMinCutViolation = 1e-4;
69 const std::vector<LiteralValueValue>& decomposed_energy =
70 demands_helper->DecomposedEnergies()[t];
71 if (decomposed_energy.empty())
return true;
74 int num_false_literals = 0;
75 int num_true_literals = 0;
76 for (
const auto [lit, fixed_size, fixed_demand] : decomposed_energy) {
77 if (assignment.LiteralIsFalse(lit)) ++num_false_literals;
78 if (assignment.LiteralIsTrue(lit)) ++num_true_literals;
80 if (num_true_literals > 1)
return false;
81 if (num_true_literals == 1 &&
82 num_false_literals < decomposed_energy.size() - 1) {
85 if (num_false_literals == decomposed_energy.size())
return false;
86 if (decomposed_energy.size() == 1 && num_true_literals != 1)
return false;
93 for (
const auto [lit, fixed_size, fixed_demand] : decomposed_energy) {
94 if (assignment.LiteralIsFalse(lit))
continue;
96 if (assignment.LiteralIsTrue(lit)) {
97 if (fixed_size != helper->SizeMin(t) ||
98 fixed_size != helper->SizeMax(t) ||
99 fixed_demand != demands_helper->DemandMin(t) ||
100 fixed_demand != demands_helper->DemandMax(t)) {
106 if (fixed_size < helper->SizeMin(t) || fixed_size > helper->SizeMax(t) ||
107 fixed_demand < demands_helper->DemandMin(t) ||
108 fixed_demand > demands_helper->DemandMax(t)) {
111 propagated_size_min = std::min(propagated_size_min, fixed_size);
112 propagated_size_max = std::max(propagated_size_max, fixed_size);
113 propagated_demand_min = std::min(propagated_demand_min, fixed_demand);
114 propagated_demand_max = std::max(propagated_demand_max, fixed_demand);
117 if (propagated_size_min != helper->SizeMin(t) ||
118 propagated_size_max != helper->SizeMax(t) ||
119 propagated_demand_min != demands_helper->DemandMin(t) ||
120 propagated_demand_max != demands_helper->DemandMax(t)) {
214 ", demand = ",
demand.DebugString(),
", energy = ",
227ABSL_MUST_USE_RESULT
bool AddOneEvent(
228 const EnergyEvent& event, IntegerValue window_start,
229 IntegerValue window_end, LinearConstraintBuilder& cut,
230 bool* add_energy_to_name =
nullptr,
bool* add_quadratic_to_name =
nullptr,
231 bool* add_opt_to_name =
nullptr,
bool* add_lifted_to_name =
nullptr) {
232 if (event.end_min <= window_start || event.start_max >= window_end) {
236 if (event.start_min >= window_start && event.end_max <= window_end) {
238 cut.AddLinearExpression(event.linearized_energy);
240 if (event.energy_is_quadratic && add_quadratic_to_name !=
nullptr) {
241 *add_quadratic_to_name =
true;
243 if (add_energy_to_name !=
nullptr &&
244 event.energy_min > event.size_min * event.demand_min) {
245 *add_energy_to_name =
true;
247 if (!event.IsPresent() && add_opt_to_name !=
nullptr) {
248 *add_opt_to_name =
true;
251 const IntegerValue min_overlap =
252 event.GetMinOverlap(window_start, window_end);
253 if (min_overlap <= 0)
return true;
254 if (add_lifted_to_name !=
nullptr) *add_lifted_to_name =
true;
256 if (event.IsPresent()) {
257 const std::vector<LiteralValueValue>& energy =
event.decomposed_energy;
258 if (energy.empty()) {
259 cut.AddTerm(event.demand, min_overlap);
261 const IntegerValue window_size = window_end - window_start;
262 for (
const auto [lit, fixed_size, fixed_demand] : energy) {
263 const IntegerValue alt_end_min =
264 std::max(event.end_min, event.start_min + fixed_size);
265 const IntegerValue alt_start_max =
266 std::min(event.start_max, event.end_max - fixed_size);
267 const IntegerValue energy_min =
269 std::min({alt_end_min - window_start, window_end - alt_start_max,
270 fixed_size, window_size});
271 if (energy_min == 0)
continue;
272 if (!cut.AddLiteralTerm(lit, energy_min))
return false;
274 if (add_energy_to_name !=
nullptr) *add_energy_to_name =
true;
277 if (add_opt_to_name !=
nullptr) *add_opt_to_name =
true;
279 event.start_min, event.start_max, event.end_min, event.end_max,
280 event.size_min, event.demand_min, event.decomposed_energy,
281 window_start, window_end);
282 if (min_energy > event.size_min * event.demand_min &&
283 add_energy_to_name !=
nullptr) {
284 *add_energy_to_name =
true;
286 if (!cut.AddLiteralTerm(
Literal(event.presence_literal_index),
297std::vector<int64_t> FindPossibleDemands(
const EnergyEvent& event,
300 std::vector<int64_t> possible_demands;
301 if (event.decomposed_energy.empty()) {
302 if (integer_trail->IsFixed(event.demand)) {
303 possible_demands.push_back(
304 integer_trail->FixedValue(event.demand).value());
306 if (integer_trail->InitialVariableDomain(event.demand.var).Size() >
310 for (
const int64_t var_value :
311 integer_trail->InitialVariableDomain(event.demand.var).Values()) {
312 possible_demands.push_back(event.demand.ValueAt(var_value).value());
316 for (
const auto [lit, fixed_size, fixed_demand] : event.decomposed_energy) {
317 if (assignment.LiteralIsFalse(lit))
continue;
318 possible_demands.push_back(fixed_demand.value());
321 return possible_demands;
339 absl::string_view cut_name,
341 std::vector<EnergyEvent> events, IntegerValue capacity,
346 DCHECK(integer_trail->
IsFixed(capacity));
355 std::vector<IntegerValue> time_points;
356 std::vector<std::vector<int64_t>> possible_demands(events.size());
357 const IntegerValue makespan_min = integer_trail->
LowerBound(makespan);
360 for (
int i = 0;
i < events.size(); ++
i) {
362 if (event.start_min < makespan_min) {
363 time_points.push_back(event.start_min);
365 if (event.start_max < makespan_min) {
366 time_points.push_back(event.start_max);
368 if (event.end_min < makespan_min) {
369 time_points.push_back(event.end_min);
371 if (event.end_max < makespan_min) {
372 time_points.push_back(event.end_max);
374 max_end_min = std::max(max_end_min, event.end_min);
375 max_end_max = std::max(max_end_max, event.end_max);
376 possible_demands[
i] = FindPossibleDemands(event, assignment, integer_trail);
378 time_points.push_back(makespan_min);
379 time_points.push_back(max_end_max);
382 const int num_time_points = time_points.size();
383 absl::flat_hash_map<IntegerValue, IntegerValue> reachable_capacity_ending_at;
386 for (
int i = 1;
i < num_time_points; ++
i) {
387 const IntegerValue window_start = time_points[
i - 1];
388 const IntegerValue window_end = time_points[
i];
389 reachable_capacity_subset_sum.
Reset(capacity.value());
390 for (
int i = 0;
i < events.size(); ++
i) {
392 if (event.start_min >= window_end || event.end_max <= window_start) {
395 if (possible_demands[
i].empty()) {
397 reachable_capacity_subset_sum.
Add(capacity.value());
399 reachable_capacity_subset_sum.
AddChoices(possible_demands[
i]);
401 if (reachable_capacity_subset_sum.
CurrentMax() == capacity.value())
break;
403 reachable_capacity_ending_at[window_end] =
407 const double capacity_lp =
ToDouble(capacity);
408 const double makespan_lp = makespan.
LpValue(lp_values);
409 const double makespan_min_lp =
ToDouble(makespan_min);
412 for (
int i = 0;
i + 1 < num_time_points; ++
i) {
414 if (events.size() > 50 &&
time_limit->LimitReached())
return;
416 const IntegerValue window_start = time_points[
i];
418 if (window_start >= max_end_min)
break;
420 IntegerValue cumulated_max_energy = 0;
421 IntegerValue cumulated_max_energy_before_makespan_min = 0;
422 bool use_subset_sum =
false;
423 bool use_subset_sum_before_makespan_min =
false;
425 for (
int j =
i + 1; j < num_time_points; ++j) {
426 const IntegerValue strip_start = time_points[j - 1];
427 const IntegerValue window_end = time_points[j];
428 const IntegerValue max_reachable_capacity_in_current_strip =
429 reachable_capacity_ending_at[window_end];
430 DCHECK_LE(max_reachable_capacity_in_current_strip, capacity);
433 if (max_reachable_capacity_in_current_strip < capacity) {
434 use_subset_sum =
true;
435 if (window_end <= makespan_min) {
436 use_subset_sum_before_makespan_min =
true;
440 const IntegerValue energy_in_strip =
441 (window_end - strip_start) * max_reachable_capacity_in_current_strip;
442 cumulated_max_energy += energy_in_strip;
443 if (window_end <= makespan_min) {
444 cumulated_max_energy_before_makespan_min += energy_in_strip;
447 if (window_start >= makespan_min) {
448 DCHECK_EQ(cumulated_max_energy_before_makespan_min, 0);
450 DCHECK_LE(cumulated_max_energy, capacity * (window_end - window_start));
451 const double max_energy_up_to_makespan_lp =
452 strip_start >= makespan_min
453 ?
ToDouble(cumulated_max_energy_before_makespan_min) +
454 (makespan_lp - makespan_min_lp) * capacity_lp
455 : std::numeric_limits<double>::infinity();
462 bool cut_generated =
true;
463 bool add_opt_to_name =
false;
464 bool add_lifted_to_name =
false;
465 bool add_quadratic_to_name =
false;
466 bool add_energy_to_name =
false;
468 temp_builder.
Clear();
469 const bool use_makespan =
470 max_energy_up_to_makespan_lp <=
471 ToDouble(cumulated_max_energy) + kMinCutViolation;
472 const bool use_subset_sum_in_cut =
473 use_makespan ? use_subset_sum_before_makespan_min : use_subset_sum;
477 temp_builder.
AddTerm(makespan, -capacity);
482 if (!AddOneEvent(event, window_start, window_end, temp_builder,
483 &add_energy_to_name, &add_quadratic_to_name,
484 &add_opt_to_name, &add_lifted_to_name)) {
485 cut_generated =
false;
492 if (!cut_generated)
break;
495 const IntegerValue energy_rhs =
496 use_makespan ? cumulated_max_energy_before_makespan_min
497 : cumulated_max_energy;
502 std::string full_name(cut_name);
503 if (add_energy_to_name) full_name.append(
"_energy");
504 if (add_lifted_to_name) full_name.append(
"_lifted");
505 if (use_makespan) full_name.append(
"_makespan");
506 if (add_opt_to_name) full_name.append(
"_optional");
507 if (add_quadratic_to_name) full_name.append(
"_quadratic");
508 if (use_subset_sum_in_cut) full_name.append(
"_subsetsum");
509 top_n_cuts.
AddCut(std::move(potential_cut), full_name, lp_values);
518 absl::string_view cut_name,
522 double max_possible_energy_lp = 0.0;
524 max_possible_energy_lp +=
event.linearized_energy_lp_value;
534 const double capacity_lp = capacity.
LpValue(lp_values);
538 absl::btree_set<IntegerValue> time_points_set;
541 time_points_set.insert(event.start_min);
542 time_points_set.insert(event.start_max);
543 time_points_set.insert(event.end_min);
544 time_points_set.insert(event.end_max);
545 max_end_min = std::max(max_end_min, event.end_min);
547 const std::vector<IntegerValue> time_points(time_points_set.begin(),
548 time_points_set.end());
549 const int num_time_points = time_points.size();
553 for (
int i = 0;
i + 1 < num_time_points; ++
i) {
555 if (events.size() > 50 &&
time_limit->LimitReached())
return;
557 const IntegerValue window_start = time_points[
i];
559 if (window_start >= max_end_min)
break;
561 for (
int j =
i + 1; j < num_time_points; ++j) {
562 const IntegerValue window_end = time_points[j];
563 const double available_energy_lp =
564 ToDouble(window_end - window_start) * capacity_lp;
565 if (available_energy_lp >= max_possible_energy_lp)
break;
567 bool cut_generated =
true;
568 bool add_opt_to_name =
false;
569 bool add_lifted_to_name =
false;
570 bool add_quadratic_to_name =
false;
571 bool add_energy_to_name =
false;
572 temp_builder.
Clear();
575 temp_builder.
AddTerm(capacity, window_start - window_end);
579 if (!AddOneEvent(event, window_start, window_end, temp_builder,
580 &add_energy_to_name, &add_quadratic_to_name,
581 &add_opt_to_name, &add_lifted_to_name)) {
582 cut_generated =
false;
589 if (!cut_generated)
break;
596 std::string full_name(cut_name);
597 if (add_energy_to_name) full_name.append(
"_energy");
598 if (add_lifted_to_name) full_name.append(
"_lifted");
599 if (add_opt_to_name) full_name.append(
"_optional");
600 if (add_quadratic_to_name) full_name.append(
"_quadratic");
601 top_n_cuts.
AddCut(std::move(potential_cut), full_name, lp_values);
612 const std::optional<AffineExpression>& makespan,
Model* model) {
618 helper, model, &result.
vars,
620 if (makespan.has_value() && !makespan.value().IsConstant()) {
621 result.
vars.push_back(makespan.value().var);
628 result.
generate_cuts = [makespan, capacity, demands_helper, helper,
634 const auto& lp_values = manager->LpValues();
637 std::vector<EnergyEvent> events;
644 if (!DecomposedEnergyIsPropagated(assignment,
i, helper,
667 if (makespan.has_value() && integer_trail->
IsFixed(capacity)) {
669 "CumulativeEnergyM", lp_values, events,
685 const std::optional<AffineExpression>& makespan,
Model* model) {
689 helper, model, &result.
vars,
691 if (makespan.has_value() && !makespan.value().IsConstant()) {
692 result.
vars.push_back(makespan.value().var);
701 const auto& lp_values = manager->LpValues();
702 std::vector<EnergyEvent> events;
705 if (helper->
SizeMin(
i) == 0)
continue;
708 e.
demand = IntegerValue(1);
719 if (makespan.has_value()) {
721 "NoOverlapEnergyM", lp_values, events,
722 IntegerValue(1), makespan.value(),
time_limit, model,
745 struct TimeTableEvent {
749 double demand_lp = 0.0;
750 bool is_positive =
false;
751 bool use_decomposed_energy_min =
false;
752 bool is_optional =
false;
761 std::vector<TimeTableEvent> events;
762 const auto& lp_values = manager->LpValues();
763 if (lp_values.empty())
return true;
764 const double capacity_lp = capacity.
LpValue(lp_values);
771 const IntegerValue start_max = helper->
StartMax(
i);
772 const IntegerValue end_min = helper->
EndMin(
i);
774 if (start_max >= end_min)
continue;
777 e1.interval_index =
i;
785 e1.demand_lp = e1.demand.LpValue(lp_values);
786 e1.is_positive =
true;
787 e1.use_decomposed_energy_min =
791 TimeTableEvent e2 = e1;
793 e2.is_positive =
false;
795 events.push_back(e1);
796 events.push_back(e2);
802 std::stable_sort(events.begin(), events.end(),
803 [](
const TimeTableEvent&
i,
const TimeTableEvent& j) {
804 return std::tie(i.time, i.is_positive) <
805 std::tie(j.time, j.is_positive);
808 double sum_of_demand_lp = 0.0;
809 bool positive_event_added_since_last_check =
false;
810 for (
int i = 0;
i < events.size(); ++
i) {
811 const TimeTableEvent& e = events[
i];
813 positive_event_added_since_last_check =
true;
814 sum_of_demand_lp += e.demand_lp;
818 if (positive_event_added_since_last_check) {
821 positive_event_added_since_last_check =
false;
823 if (sum_of_demand_lp >= capacity_lp + kMinCutViolation) {
825 bool use_decomposed_energy_min =
false;
826 bool use_optional =
false;
828 cut.
AddTerm(capacity, IntegerValue(-1));
831 DCHECK(!events[
i].is_positive);
832 const IntegerValue time_point = events[
i - 1].time;
834 for (
int j = 0; j <
i; ++j) {
835 const TimeTableEvent& cut_event = events[j];
836 const int t = cut_event.interval_index;
837 DCHECK_LE(helper->
StartMax(t), time_point);
838 if (!cut_event.is_positive || helper->
EndMin(t) <= time_point) {
843 use_decomposed_energy_min |= cut_event.use_decomposed_energy_min;
844 use_optional |= cut_event.is_optional;
847 std::string cut_name =
"CumulativeTimeTable";
848 if (use_optional) cut_name +=
"_optional";
849 if (use_decomposed_energy_min) cut_name +=
"_energy";
850 top_n_cuts.
AddCut(cut.
Build(), cut_name, lp_values);
856 sum_of_demand_lp -= e.demand_lp;
872 start(helper->Starts()[t]),
875 end(helper->Ends()[t]),
890 absl::string_view cut_name,
bool ignore_zero_size_intervals,
892 std::vector<CachedIntervalData> events, IntegerValue capacity_max,
895 const int num_events = events.size();
896 if (num_events <= 1)
return;
899 events.begin(), events.end(),
901 return e1.start_min < e2.start_min ||
902 (e1.start_min == e2.start_min && e1.end_max < e2.end_max);
914 const auto add_balas_disjunctive_cut =
915 [&](absl::string_view local_cut_name, IntegerValue start_min_1,
917 IntegerValue start_min_2, IntegerValue duration_min_2,
920 if (start_min_2 >= start_min_1 + duration_min_1 ||
921 start_min_1 >= start_min_2 + duration_min_2) {
924 const IntegerValue coeff_1 = duration_min_1 + start_min_1 - start_min_2;
925 const IntegerValue coeff_2 = duration_min_2 + start_min_2 - start_min_1;
926 const IntegerValue rhs = duration_min_1 * duration_min_2 +
927 duration_min_1 * start_min_2 +
928 duration_min_2 * start_min_1;
930 if (
ToDouble(coeff_1) * start_1.LpValue(lp_values) +
931 ToDouble(coeff_2) * start_2.LpValue(lp_values) <=
936 top_n_cuts.
AddCut(cut.
Build(), local_cut_name, lp_values);
940 for (
int i = 0;
i + 1 < num_events; ++
i) {
942 for (
int j =
i + 1; j < num_events; ++j) {
949 if (ignore_zero_size_intervals &&
957 if (interval_1_can_precede_2 && !interval_2_can_precede_1 &&
965 absl::StrCat(cut_name,
"DetectedPrecedence"),
967 }
else if (interval_2_can_precede_1 && !interval_1_can_precede_2 &&
975 absl::StrCat(cut_name,
"DetectedPrecedence"),
978 add_balas_disjunctive_cut(absl::StrCat(cut_name,
"DisjunctionOnStart"),
981 add_balas_disjunctive_cut(absl::StrCat(cut_name,
"DisjunctionOnEnd"),
999 helper, model, &result.
vars,
1004 result.
generate_cuts = [integer_trail, helper, demands_helper, capacity,
1008 std::vector<CachedIntervalData> events;
1009 for (
int t = 0; t < helper->
NumTasks(); ++t) {
1012 event.demand_min = demands_helper->
DemandMin(t);
1013 events.push_back(event);
1016 const IntegerValue capacity_max = integer_trail->
UpperBound(capacity);
1019 manager->LpValues(), std::move(events), capacity_max, model, manager);
1030 helper, model, &result.
vars,
1037 std::vector<CachedIntervalData> events;
1038 for (
int t = 0; t < helper->
NumTasks(); ++t) {
1041 event.demand_min = IntegerValue(1);
1042 events.push_back(event);
1047 manager->LpValues(), std::move(events), IntegerValue(1), model,
1064 start(helper->Starts()[t]),
1065 end(helper->Ends()[t]) {
1066 if (demands_helper ==
nullptr) {
1087 return absl::StrCat(
1088 "CompletionTimeEvent(task_index = ",
task_index,
1090 ", size_min = ",
size_min,
", end = ",
end.DebugString(),
1095 ", lifted = ",
lifted,
", decomposed_energy = [",
1098 absl::StrAppend(out, e.left_value,
" * ", e.right_value);
1104 const absl::Span<const CompletionTimeEvent> events,
Model* model) {
1105 max_task_index_ = 0;
1106 if (events.empty())
return;
1109 for (
const auto& event : events) {
1110 max_task_index_ = std::max(max_task_index_, event.task_index);
1112 if (events.size() > 100)
return;
1117 std::vector<CompletionTimeEvent> sorted_events(events.begin(), events.end());
1118 std::sort(sorted_events.begin(), sorted_events.end(),
1120 return a.task_index < b.task_index;
1122 predecessors_.reserve(max_task_index_ + 1);
1123 for (
const auto& e1 : sorted_events) {
1124 for (
const auto& e2 : sorted_events) {
1125 if (e2.task_index == e1.task_index)
continue;
1128 while (predecessors_.size() <= e1.task_index) predecessors_.Add({});
1129 predecessors_.AppendToLastVector(e2.task_index);
1133 VLOG(2) <<
"num_tasks:" << max_task_index_ + 1
1134 <<
" num_precedences:" << predecessors_.num_entries()
1135 <<
" predecessors size:" << predecessors_.size();
1139 absl::Span<const CompletionTimeEvent> events,
1140 absl::Span<const int> permutation) {
1141 if (predecessors_.num_entries() == 0)
return true;
1142 visited_.assign(max_task_index_ + 1,
false);
1143 for (
int i = permutation.size() - 1;
i >= 0; --
i) {
1145 if (event.task_index >= predecessors_.size())
continue;
1146 for (
const int predecessor : predecessors_[event.task_index]) {
1147 if (visited_[predecessor])
return false;
1149 visited_[
event.task_index] =
true;
1156bool ComputeWeightedSumOfEndMinsOfOnePermutationForNoOverlap(
1157 absl::Span<const CompletionTimeEvent> events,
1158 absl::Span<const int> permutation, IntegerValue& sum_of_ends,
1159 IntegerValue& sum_of_weighted_ends) {
1162 sum_of_weighted_ends = 0;
1166 for (
const int index : permutation) {
1168 const IntegerValue task_start_min =
1169 std::max(event.start_min, end_min_of_previous_task);
1170 if (event.start_max < task_start_min)
return false;
1172 end_min_of_previous_task = task_start_min +
event.size_min;
1173 sum_of_ends += end_min_of_previous_task;
1174 sum_of_weighted_ends +=
event.energy_min * end_min_of_previous_task;
1187bool ComputeWeightedSumOfEndMinsOfOnePermutation(
1188 absl::Span<const CompletionTimeEvent> events,
1189 absl::Span<const int> permutation, IntegerValue capacity_max,
1190 CtExhaustiveHelper& helper, IntegerValue& sum_of_ends,
1191 IntegerValue& sum_of_weighted_ends,
bool& cut_use_precedences) {
1192 DCHECK_EQ(permutation.size(), events.size());
1194 if (capacity_max == 1) {
1195 return ComputeWeightedSumOfEndMinsOfOnePermutationForNoOverlap(
1196 events, permutation, sum_of_ends, sum_of_weighted_ends);
1201 sum_of_weighted_ends = 0;
1206 IntegerValue demand_min_of_previous_task = 0;
1209 for (
const int index : permutation) {
1211 const IntegerValue threshold =
1212 std::max(event.start_min,
1213 (event.demand_min + demand_min_of_previous_task > capacity_max)
1214 ? end_min_of_previous_task
1215 : start_min_of_previous_task);
1216 if (event.start_max < threshold) {
1220 start_min_of_previous_task = threshold;
1221 end_min_of_previous_task = threshold +
event.size_min;
1222 demand_min_of_previous_task =
event.demand_min;
1227 helper.profile_.clear();
1232 helper.assigned_ends_.assign(helper.max_task_index() + 1,
kMinIntegerValue);
1234 for (
const int index : permutation) {
1236 const IntegerValue start_min =
1237 std::max(event.start_min, start_of_previous_task);
1241 auto profile_it = helper.profile_.begin();
1242 while ((profile_it + 1)->first <= start_min ||
1243 profile_it->second < event.demand_min) {
1247 IntegerValue actual_start = std::max(start_min, profile_it->first);
1248 const IntegerValue initial_start_min = actual_start;
1253 if (event.task_index < helper.predecessors().size()) {
1254 for (
const int predecessor : helper.predecessors()[event.task_index]) {
1257 std::max(actual_start, helper.assigned_ends_[predecessor]);
1261 if (actual_start > initial_start_min) {
1262 cut_use_precedences =
true;
1264 while ((profile_it + 1)->first <= actual_start) ++profile_it;
1265 VLOG(3) <<
"push from " << initial_start_min <<
" to " << actual_start;
1269 if (actual_start > event.start_max) {
1273 const IntegerValue actual_end = actual_start +
event.size_min;
1276 helper.assigned_ends_[
event.task_index] = actual_end;
1277 sum_of_ends += actual_end;
1278 sum_of_weighted_ends +=
event.energy_min * actual_end;
1279 start_of_previous_task = actual_start;
1282 if (event.task_index == events[permutation.back()].task_index)
break;
1285 helper.new_profile_.clear();
1286 const IntegerValue demand_min =
event.demand_min;
1289 helper.new_profile_.push_back(
1290 {actual_start, profile_it->second - demand_min});
1294 while (profile_it->first < actual_end) {
1295 helper.new_profile_.push_back(
1296 {profile_it->first, profile_it->second - demand_min});
1301 if (profile_it->first > actual_end) {
1302 helper.new_profile_.push_back({actual_end, (profile_it - 1)->second});
1306 helper.new_profile_.insert(helper.new_profile_.end(), profile_it,
1307 helper.profile_.end());
1309 helper.profile_.swap(helper.new_profile_);
1314const int kCtExhaustiveTargetSize = 6;
1318const int kExplorationLimit = 873;
1323 absl::Span<const CompletionTimeEvent> events, IntegerValue capacity_max,
1324 double unweighted_threshold,
double weighted_threshold,
1326 double& min_sum_of_weighted_ends,
bool& cut_use_precedences,
1327 int& exploration_credit) {
1329 min_sum_of_ends = std::numeric_limits<double>::max();
1330 min_sum_of_weighted_ends = std::numeric_limits<double>::max();
1332 for (
int i = 0;
i < events.size(); ++
i) {
1337 for (
int i = 0;
i < events.size(); ++
i) {
1338 const int task_i = events[
i].task_index;
1339 if (task_i >= predecessors.size())
continue;
1340 for (
const int task_j : predecessors[task_i]) {
1348 bool is_dag =
false;
1349 int num_valid_permutations = 0;
1352 if (--exploration_credit < 0)
break;
1354 IntegerValue sum_of_ends = 0;
1355 IntegerValue sum_of_weighted_ends = 0;
1357 if (ComputeWeightedSumOfEndMinsOfOnePermutation(
1358 events, permutation, capacity_max, helper, sum_of_ends,
1359 sum_of_weighted_ends, cut_use_precedences)) {
1360 min_sum_of_ends = std::min(
ToDouble(sum_of_ends), min_sum_of_ends);
1361 min_sum_of_weighted_ends =
1362 std::min(
ToDouble(sum_of_weighted_ends), min_sum_of_weighted_ends);
1363 ++num_valid_permutations;
1365 if (min_sum_of_ends <= unweighted_threshold &&
1366 min_sum_of_weighted_ends <= weighted_threshold) {
1376 : num_valid_permutations > 0
1379 VLOG(2) <<
"DP: size:" << events.size()
1380 <<
", num_valid_permutations:" << num_valid_permutations
1381 <<
", min_sum_of_end_mins:" << min_sum_of_ends
1382 <<
", min_sum_of_weighted_end_mins:" << min_sum_of_weighted_ends
1383 <<
", unweighted_threshold:" << unweighted_threshold
1384 <<
", weighted_threshold:" << weighted_threshold
1385 <<
", exploration_credit:" << exploration_credit
1386 <<
", status:" << status;
1394 absl::string_view cut_name, std::vector<CompletionTimeEvent> events,
1401 events.begin(), events.end(),
1403 return std::tie(e1.start_min, e1.energy_min, e1.lp_end, e1.task_index) <
1404 std::tie(e2.start_min, e2.energy_min, e2.lp_end, e2.task_index);
1406 for (
int start = 0; start + 1 < events.size(); ++start) {
1408 if (start > 0 && events[start].start_min == events[start - 1].start_min) {
1412 bool cut_use_precedences =
false;
1413 const IntegerValue sequence_start_min = events[start].start_min;
1418 for (
int before = 0; before < start; ++before) {
1419 if (events[before].start_min + events[before].size_min >
1420 sequence_start_min) {
1428 return std::tie(e1.lp_end, e1.task_index) <
1429 std::tie(e2.lp_end, e2.task_index);
1432 double sum_of_ends_lp = 0.0;
1433 double sum_of_weighted_ends_lp = 0.0;
1434 IntegerValue sum_of_demands = 0;
1435 double sum_of_square_energies = 0;
1436 double min_sum_of_ends = std::numeric_limits<double>::max();
1437 double min_sum_of_weighted_ends = std::numeric_limits<double>::max();
1438 int exploration_limit = kExplorationLimit;
1441 for (
int i = 0;
i < kMaxSize; ++
i) {
1443 const double energy =
ToDouble(event.energy_min);
1444 sum_of_ends_lp +=
event.lp_end;
1445 sum_of_weighted_ends_lp +=
event.lp_end * energy;
1446 sum_of_demands +=
event.demand_min;
1447 sum_of_square_energies += energy * energy;
1453 if (
i <= 1 || sum_of_demands <= capacity_max)
continue;
1455 absl::Span<const CompletionTimeEvent> tasks_to_explore =
1459 tasks_to_explore, capacity_max,
1460 sum_of_ends_lp + kMinCutViolation,
1461 sum_of_weighted_ends_lp +
1463 helper, min_sum_of_ends, min_sum_of_weighted_ends,
1464 cut_use_precedences, exploration_limit);
1472 const double unweigthed_violation =
1473 (min_sum_of_ends - sum_of_ends_lp) / std::sqrt(
ToDouble(
i + 1));
1474 const double weighted_violation =
1475 (min_sum_of_weighted_ends - sum_of_weighted_ends_lp) /
1476 std::sqrt(sum_of_square_energies);
1479 if (unweigthed_violation > weighted_violation &&
1480 unweigthed_violation > kMinCutViolation) {
1482 bool is_lifted =
false;
1483 for (
int j = 0; j <=
i; ++j) {
1485 is_lifted |=
event.lifted;
1486 cut.
AddTerm(event.end, IntegerValue(1));
1488 std::string full_name(cut_name);
1489 if (cut_use_precedences) full_name.append(
"_prec");
1490 if (is_lifted) full_name.append(
"_lifted");
1495 if (weighted_violation >= unweigthed_violation &&
1496 weighted_violation > kMinCutViolation) {
1499 bool is_lifted =
false;
1500 for (
int j = 0; j <=
i; ++j) {
1502 is_lifted |=
event.lifted;
1503 cut.
AddTerm(event.end, event.energy_min);
1505 std::string full_name(cut_name);
1506 if (is_lifted) full_name.append(
"_lifted");
1507 if (cut_use_precedences) full_name.append(
"_prec");
1508 full_name.append(
"_weighted");
1521CompletionTimeEvent CopyAndTrimEventAfter(
const CompletionTimeEvent& old_event,
1522 IntegerValue time) {
1523 CHECK_GT(time, old_event.start_min);
1524 CHECK_GT(old_event.start_min + old_event.size_min, time);
1525 CompletionTimeEvent
event = old_event;
1526 event.lifted =
true;
1529 const IntegerValue shift = time -
event.start_min;
1530 CHECK_GT(shift, IntegerValue(0));
1531 event.size_min -= shift;
1532 event.energy_min =
event.size_min *
event.demand_min;
1533 if (!event.decomposed_energy.empty()) {
1536 for (
auto& [literal, fixed_size, fixed_demand] : event.decomposed_energy) {
1537 CHECK_GT(fixed_size, shift);
1538 fixed_size -= shift;
1539 propagated_energy_min =
1540 std::min(propagated_energy_min, fixed_demand * fixed_size);
1543 DCHECK_GT(propagated_energy_min, 0);
1544 if (propagated_energy_min > event.energy_min) {
1545 event.use_decomposed_energy_min =
true;
1546 event.energy_min = propagated_energy_min;
1548 event.use_decomposed_energy_min =
false;
1551 event.start_min = time;
1557void AddEventDemandsToCapacitySubsetSum(
1559 IntegerValue capacity_max, std::vector<int64_t>& tmp_possible_demands,
1561 if (dp.CurrentMax() != capacity_max) {
1562 if (event.demand_is_fixed) {
1563 dp.Add(event.demand_min.value());
1564 }
else if (!event.decomposed_energy.empty()) {
1565 tmp_possible_demands.clear();
1566 for (
const auto& [literal, size, demand] : event.decomposed_energy) {
1567 if (assignment.LiteralIsFalse(literal))
continue;
1568 if (assignment.LiteralIsTrue(literal)) {
1569 tmp_possible_demands.assign({demand.value()});
1572 tmp_possible_demands.push_back(demand.value());
1574 dp.AddChoices(tmp_possible_demands);
1578 dp.Add(capacity_max.value());
1630 absl::string_view cut_name, std::vector<CompletionTimeEvent> events,
1635 std::vector<int64_t> tmp_possible_demands;
1639 events.begin(), events.end(),
1641 return std::tie(e1.start_min, e1.demand_min, e1.lp_end) <
1642 std::tie(e2.start_min, e2.demand_min, e2.lp_end);
1646 for (
int start = 0; start + 1 < events.size(); ++start) {
1648 if (start > 0 && events[start].start_min == events[start - 1].start_min) {
1652 const IntegerValue sequence_start_min = events[start].start_min;
1653 std::vector<CompletionTimeEvent> residual_tasks(events.begin() + start,
1661 for (
int before = 0; before < start; ++before) {
1662 if (events[before].start_min + events[before].size_min >
1663 sequence_start_min) {
1665 CopyAndTrimEventAfter(events[before], sequence_start_min);
1666 if (event.energy_min <= 0)
continue;
1667 residual_tasks.push_back(std::move(event));
1673 if (residual_tasks.size() <= kCtExhaustiveTargetSize)
continue;
1677 double best_efficacy = 0.01;
1678 IntegerValue best_min_contrib = 0;
1679 bool best_uses_subset_sum =
false;
1682 IntegerValue sum_event_contributions = 0;
1684 IntegerValue sum_energy = 0;
1686 IntegerValue sum_square_energy = 0;
1688 double lp_contrib = 0.0;
1696 residual_tasks.begin(), residual_tasks.end(),
1698 return e1.lp_end < e2.lp_end;
1702 for (
int i = 0;
i < residual_tasks.size(); ++
i) {
1704 DCHECK_GE(event.start_min, sequence_start_min);
1707 if (!
AddTo(event.energy_min, &sum_energy))
break;
1716 &sum_event_contributions)) {
1719 if (!
AddSquareTo(event.energy_min, &sum_square_energy))
break;
1721 lp_contrib +=
event.lp_end *
ToDouble(event.energy_min);
1722 current_start_min = std::min(current_start_min, event.start_min);
1725 AddEventDemandsToCapacitySubsetSum(event, assignment, capacity_max,
1726 tmp_possible_demands, dp);
1729 if (
i < kCtExhaustiveTargetSize)
continue;
1731 const IntegerValue reachable_capacity = dp.
CurrentMax();
1734 const IntegerValue large_rectangle_contrib =
1737 const IntegerValue mean_large_rectangle_contrib =
1738 CeilRatio(large_rectangle_contrib, reachable_capacity);
1740 IntegerValue min_contrib =
1741 CapAddI(sum_event_contributions, mean_large_rectangle_contrib);
1743 min_contrib =
CeilRatio(min_contrib, 2);
1746 if (!
AddProductTo(sum_energy, current_start_min, &min_contrib))
break;
1750 const double efficacy = (
ToDouble(min_contrib) - lp_contrib) /
1751 std::sqrt(
ToDouble(sum_square_energy));
1759 if (efficacy > best_efficacy) {
1760 best_efficacy = efficacy;
1762 best_min_contrib = min_contrib;
1763 best_uses_subset_sum = reachable_capacity < capacity_max;
1769 if (best_end != -1) {
1771 bool is_lifted =
false;
1772 bool add_energy_to_name =
false;
1773 for (
int i = 0;
i <= best_end; ++
i) {
1775 is_lifted |=
event.lifted;
1776 add_energy_to_name |=
event.use_decomposed_energy_min;
1777 cut.
AddTerm(event.end, event.energy_min);
1779 std::string full_name(cut_name);
1780 if (add_energy_to_name) full_name.append(
"_energy");
1781 if (is_lifted) full_name.append(
"_lifted");
1782 if (best_uses_subset_sum) full_name.append(
"_subsetsum");
1800 auto generate_cuts = [model, manager,
1801 helper](
bool time_is_forward) ->
bool {
1805 std::vector<CompletionTimeEvent> events;
1806 const auto& lp_values = manager->LpValues();
1807 for (
int index = 0; index < helper->
NumTasks(); ++index) {
1808 if (!helper->
IsPresent(index))
continue;
1809 const IntegerValue size_min = helper->
SizeMin(index);
1812 event.lp_end =
event.end.LpValue(lp_values);
1813 events.push_back(event);
1818 helper.
Init(events, model);
1821 "NoOverlapCompletionTimeExhaustive", events,
1822 IntegerValue(1), helper, model, manager)) {
1827 "NoOverlapCompletionTimeQueyrane", std::move(events),
1828 IntegerValue(1), model, manager);
1831 if (!generate_cuts(
true))
return false;
1832 if (!generate_cuts(
false))
return false;
1851 result.
generate_cuts = [integer_trail, helper, demands_helper, capacity,
1854 auto generate_cuts = [integer_trail, sat_solver, model, manager, helper,
1856 capacity](
bool time_is_forward) ->
bool {
1857 DCHECK_EQ(sat_solver->CurrentDecisionLevel(), 0);
1858 if (!helper->SynchronizeAndSetTimeDirection(time_is_forward)) {
1861 if (!demands_helper->CacheAllEnergyValues())
return true;
1863 std::vector<CompletionTimeEvent> events;
1864 const auto& lp_values = manager->LpValues();
1866 for (
int index = 0; index < helper->NumTasks(); ++index) {
1867 if (!helper->IsPresent(index))
continue;
1868 if (!DecomposedEnergyIsPropagated(assignment, index, helper,
1872 if (helper->SizeMin(index) > 0 &&
1873 demands_helper->DemandMin(index) > 0) {
1875 event.lp_end =
event.end.LpValue(lp_values);
1876 events.push_back(event);
1881 helper.
Init(events, model);
1883 const IntegerValue capacity_max = integer_trail->
UpperBound(capacity);
1885 "CumulativeCompletionTimeExhaustive", events, capacity_max,
1886 helper, model, manager)) {
1891 std::move(events), capacity_max,
1896 if (!generate_cuts(
true))
return false;
1897 if (!generate_cuts(
false))
return false;
RelationStatus GetLevelZeroPrecedenceStatus(AffineExpression a, AffineExpression b) const
Return the status of a <= b;.
const CompactVectorVector< int > & predecessors() const
void Init(absl::Span< const CompletionTimeEvent > events, Model *model)
int max_task_index() const
bool PermutationIsCompatibleWithPrecedences(absl::Span< const CompletionTimeEvent > events, absl::Span< const int > permutation)
std::vector< CompletionTimeEvent > residual_events_
DagTopologicalSortIterator valid_permutation_iterator_
std::vector< int > task_to_index_
void AddArc(int from, int to)
Must be called before iteration starts or between iterations.
IntegerValue LowerBound(IntegerVariable i) const
Returns the current lower/upper bound of the given integer variable.
IntegerValue UpperBound(IntegerVariable i) const
IntegerValue FixedValue(IntegerVariable i) const
Checks that the variable is fixed and returns its value.
bool IsFixed(IntegerVariable i) const
Checks if the variable is fixed.
void AddQuadraticLowerBound(AffineExpression left, AffineExpression right, IntegerTrail *integer_trail, bool *is_quadratic=nullptr)
LinearExpression BuildExpression()
ABSL_MUST_USE_RESULT bool AddLiteralTerm(Literal lit, IntegerValue coeff=IntegerValue(1))
void AddTerm(IntegerVariable var, IntegerValue coeff)
void AddLinearExpression(const LinearExpression &expr)
void AddConstant(IntegerValue value)
Adds the corresponding term to the current linear expression.
void Clear()
Clears all added terms and constants. Keeps the original bounds.
LinearConstraint BuildConstraint(IntegerValue lb, IntegerValue ub)
ABSL_MUST_USE_RESULT bool AddDecomposedProduct(absl::Span< const LiteralValueValue > product)
const util_intops::StrongVector< IntegerVariable, double > & LpValues()
To simplify CutGenerator api.
LiteralIndex Index() const
void AddChoices(absl::Span< const int64_t > choices)
int64_t CurrentMax() const
void Add(int64_t value)
Add a value to the base set for which subset sums will be taken.
void Reset(int64_t bound)
IntegerValue StartMax(int t) const
int NumTasks() const
Returns the number of task.
absl::Span< const AffineExpression > Sizes() const
bool IsPresent(int t) const
Literal PresenceLiteral(int index) const
IntegerValue SizeMin(int t) const
ABSL_MUST_USE_RESULT bool SynchronizeAndSetTimeDirection(bool is_forward)
bool IsAbsent(int t) const
IntegerValue EndMin(int t) const
bool DemandIsFixed(int t) const
bool CacheAllEnergyValues()
bool EnergyIsQuadratic(int t) const
const std::vector< std::vector< LiteralValueValue > > & DecomposedEnergies() const
IntegerValue DemandMax(int t) const
const std::vector< AffineExpression > & Demands() const
IntegerValue DemandMin(int t) const
ABSL_MUST_USE_RESULT bool AddLinearizedDemand(int t, LinearConstraintBuilder *builder) const
IntegerValue EnergyMin(int t) const
void TransferToManager(LinearConstraintManager *manager)
Empty the local pool and add all its content to the manager.
void AddCut(LinearConstraint ct, absl::string_view name, const util_intops::StrongVector< IntegerVariable, double > &lp_solution)
Adds a cut to the local pool.
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
bool AddSquareTo(IntegerValue a, IntegerValue *result)
Computes result += a * a, and return false iff there is an overflow.
bool AddProductTo(IntegerValue a, IntegerValue b, IntegerValue *result)
Computes result += a * b, and return false iff there is an overflow.
CutGenerator CreateCumulativeCompletionTimeCutGenerator(SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands_helper, const AffineExpression &capacity, Model *model)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
bool AddTo(IntegerValue a, IntegerValue *result)
CompletionTimeExplorationStatus ComputeMinSumOfWeightedEndMins(absl::Span< const CompletionTimeEvent > events, IntegerValue capacity_max, double unweighted_threshold, double weighted_threshold, CtExhaustiveHelper &helper, double &min_sum_of_ends, double &min_sum_of_weighted_ends, bool &cut_use_precedences, int &exploration_credit)
void GenerateCompletionTimeCutsWithEnergy(absl::string_view cut_name, std::vector< CompletionTimeEvent > events, IntegerValue capacity_max, Model *model, LinearConstraintManager *manager)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
const LiteralIndex kNoLiteralIndex(-1)
CutGenerator CreateCumulativePrecedenceCutGenerator(SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands_helper, const AffineExpression &capacity, Model *model)
ABSL_MUST_USE_RESULT bool GenerateShortCompletionTimeCutsWithExactBound(absl::string_view cut_name, std::vector< CompletionTimeEvent > events, IntegerValue capacity_max, CtExhaustiveHelper &helper, Model *model, LinearConstraintManager *manager)
void GenerateCumulativeEnergeticCuts(absl::string_view cut_name, const util_intops::StrongVector< IntegerVariable, double > &lp_values, std::vector< EnergyEvent > events, const AffineExpression &capacity, TimeLimit *time_limit, Model *model, LinearConstraintManager *manager)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
CutGenerator CreateCumulativeEnergyCutGenerator(SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands_helper, const AffineExpression &capacity, const std::optional< AffineExpression > &makespan, Model *model)
void GenerateCutsBetweenPairOfNonOverlappingTasks(absl::string_view cut_name, bool ignore_zero_size_intervals, const util_intops::StrongVector< IntegerVariable, double > &lp_values, std::vector< CachedIntervalData > events, IntegerValue capacity_max, Model *model, LinearConstraintManager *manager)
void AddIntegerVariableFromIntervals(const SchedulingConstraintHelper *helper, Model *model, std::vector< IntegerVariable > *vars, int mask)
void GenerateCumulativeEnergeticCutsWithMakespanAndFixedCapacity(absl::string_view cut_name, const util_intops::StrongVector< IntegerVariable, double > &lp_values, std::vector< EnergyEvent > events, IntegerValue capacity, AffineExpression makespan, TimeLimit *time_limit, Model *model, LinearConstraintManager *manager)
CutGenerator CreateCumulativeTimeTableCutGenerator(SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands_helper, const AffineExpression &capacity, Model *model)
void AppendVariablesFromCapacityAndDemands(const AffineExpression &capacity, SchedulingDemandHelper *demands_helper, Model *model, std::vector< IntegerVariable > *vars)
CutGenerator CreateNoOverlapCompletionTimeCutGenerator(SchedulingConstraintHelper *helper, Model *model)
IntegerValue CapAddI(IntegerValue a, IntegerValue b)
CutGenerator CreateNoOverlapEnergyCutGenerator(SchedulingConstraintHelper *helper, const std::optional< AffineExpression > &makespan, Model *model)
CutGenerator CreateNoOverlapPrecedenceCutGenerator(SchedulingConstraintHelper *helper, Model *model)
CompletionTimeExplorationStatus
bool AtMinOrMaxInt64I(IntegerValue t)
IntegerValue CapProdI(IntegerValue a, IntegerValue b)
Overflows and saturated arithmetic.
double ToDouble(IntegerValue value)
IntegerValue ComputeEnergyMinInWindow(IntegerValue start_min, IntegerValue start_max, IntegerValue end_min, IntegerValue end_max, IntegerValue size_min, IntegerValue demand_min, absl::Span< const LiteralValueValue > filtered_energy, IntegerValue window_start, IntegerValue window_end)
In SWIG mode, we don't want anything besides these top-level includes.
ClosedInterval::Iterator end(ClosedInterval interval)
AffineExpression Negated() const
double LpValue(const util_intops::StrongVector< IntegerVariable, double > &lp_values) const
Returns the affine expression value under a given LP solution.
CachedIntervalData(int t, SchedulingConstraintHelper *helper)
Internal methods and data structures, useful for testing.
std::vector< LiteralValueValue > decomposed_energy
AffineExpression start
Start and end affine expressions and lp value of the end of the interval.
IntegerValue energy_min
The energy min of this event.
CompletionTimeEvent(int t, SchedulingConstraintHelper *x_helper, SchedulingDemandHelper *demands_helper)
IntegerValue start_min
Cache of the bounds of the interval.
int task_index
The index of the task in the helper.
std::string DebugString() const
bool use_decomposed_energy_min
IntegerValue demand_min
Cache of the bounds of the demand.
absl::AnyInvocable< bool(LinearConstraintManager *manager)> generate_cuts
std::vector< IntegerVariable > vars
bool only_run_at_level_zero
AffineExpression demand
We need this for linearizing the energy in some cases.
ABSL_MUST_USE_RESULT bool FillEnergyLp(AffineExpression size, const util_intops::StrongVector< IntegerVariable, double > &lp_values, Model *model)
bool energy_is_quadratic
True if linearized_energy is not exact and a McCormick relaxation.
IntegerValue start_min
Cache of the bounds of the interval.
LiteralIndex presence_literal_index
If set, this event is optional and its presence is controlled by this.
EnergyEvent(int t, SchedulingConstraintHelper *x_helper)
IntegerValue demand_min
Cache of the bounds of the demand.
bool use_decomposed_energy
double linearized_energy_lp_value
IntegerValue GetMinOverlap(IntegerValue start, IntegerValue end) const
std::vector< LiteralValueValue > decomposed_energy
LinearExpression linearized_energy
std::string DebugString() const
IntegerValue energy_min
The energy min of this event.
double NormalizedViolation(const util_intops::StrongVector< IntegerVariable, double > &lp_values) const