20#include "absl/log/check.h"
39 constraint->RegisterWith(watcher);
40 model->TakeOwnership(constraint);
46 : capacity_(capacity),
50 const int num_tasks = helper_->
NumTasks();
51 task_to_start_event_.resize(num_tasks);
55 const int id = watcher->
Register(
this);
67 const IntegerValue capacity_max = integer_trail_->
UpperBound(capacity_);
69 if (capacity_max <= 0)
return true;
72 start_event_task_time_.clear();
75 const int task = task_time.task_index;
77 task_to_start_event_[task] = -1;
80 start_event_task_time_.emplace_back(task_time);
81 task_to_start_event_[task] = num_events;
84 start_event_is_present_.assign(num_events,
false);
85 theta_tree_.
Reset(num_events);
87 bool tree_has_mandatory_intervals =
false;
91 for (
const auto [current_task, current_end] :
93 if (task_to_start_event_[current_task] == -1)
continue;
97 const int current_event = task_to_start_event_[current_task];
98 const IntegerValue
start_min = start_event_task_time_[current_event].time;
99 const bool is_present = helper_->
IsPresent(current_task);
100 start_event_is_present_[current_event] = is_present;
102 tree_has_mandatory_intervals =
true;
113 if (tree_has_mandatory_intervals) {
115 const IntegerValue envelope = theta_tree_.
GetEnvelope();
116 const int critical_event =
118 const IntegerValue window_start =
119 start_event_task_time_[critical_event].time;
120 const IntegerValue window_end = current_end;
121 const IntegerValue window_size = window_end - window_start;
122 if (window_size == 0)
continue;
123 const IntegerValue new_capacity_min =
124 CeilRatio(envelope - window_start * capacity_max, window_size);
132 if (new_capacity_min > integer_trail_->
LowerBound(capacity_)) {
134 for (
int event = critical_event;
event < num_events;
event++) {
135 if (start_event_is_present_[event]) {
136 const int task = start_event_task_time_[event].task_index;
168 int event_with_new_energy_max;
169 IntegerValue new_energy_max;
171 current_end * capacity_max, &critical_event,
172 &event_with_new_energy_max, &new_energy_max);
174 const IntegerValue window_start =
175 start_event_task_time_[critical_event].time;
178 const IntegerValue window_end = current_end;
179 for (
int event = critical_event;
event < num_events;
event++) {
180 if (start_event_is_present_[event]) {
181 if (event == event_with_new_energy_max)
continue;
182 const int task = start_event_task_time_[event].task_index;
194 const int task_with_new_energy_max =
195 start_event_task_time_[event_with_new_energy_max].task_index;
203 if (helper_->
IsPresent(task_with_new_energy_max)) {
205 task_to_start_event_[task_with_new_energy_max],
206 start_event_task_time_[event_with_new_energy_max].
time *
208 demands_->
EnergyMin(task_with_new_energy_max), new_energy_max);
210 theta_tree_.
RemoveEvent(event_with_new_energy_max);
219 const std::vector<int>& subtasks,
const std::vector<IntegerValue>& offsets,
228 is_in_subtasks_.assign(helper->
NumTasks(),
false);
229 task_offsets_.assign(helper->
NumTasks(), 0);
230 for (
int i = 0;
i < subtasks.size(); ++
i) {
231 is_in_subtasks_[subtasks[
i]] =
true;
232 task_offsets_[subtasks[
i]] = offsets[
i];
243 IntegerValue energy_after_time(0);
244 IntegerValue profile_height(0);
249 const IntegerValue capacity_max = integer_trail_->
UpperBound(capacity_);
250 dp_.
Reset(capacity_max.value());
256 for (
int i = profile.size() - 1;
i >= 0;) {
259 const int t = profile[
i].task;
260 if (!helper_->
IsPresent(t) || !is_in_subtasks_[t]) {
266 const IntegerValue
time = profile[
i].time;
267 if (profile_height > 0) {
268 energy_after_time += profile_height * (previous_time -
time);
270 previous_time =
time;
274 const IntegerValue saved_capa_max = dp_.
CurrentMax();
275 const IntegerValue saved_min_offset = min_offset;
277 for (;
i >= 0 && profile[
i].time ==
time; --
i) {
279 const int t = profile[
i].task;
280 if (!helper_->
IsPresent(t) || !is_in_subtasks_[t])
continue;
282 min_offset = std::min(min_offset, task_offsets_[t]);
283 const IntegerValue demand_min = demands_->
DemandMin(t);
284 if (profile[
i].is_first) {
285 profile_height -= demand_min;
287 profile_height += demand_min;
288 if (demands_->
Demands()[t].IsConstant()) {
289 dp_.
Add(demand_min.value());
291 dp_.
Add(capacity_max.value());
303 if (energy_after_time == 0)
continue;
304 DCHECK_GT(saved_capa_max, 0);
306 const IntegerValue end_min_with_offset =
307 time +
CeilRatio(energy_after_time, saved_capa_max) + saved_min_offset;
308 if (end_min_with_offset > best_bound) {
310 best_bound = end_min_with_offset;
313 DCHECK_EQ(profile_height, 0);
316 if (best_bound > integer_trail_->
LowerBound(var_to_push_)) {
320 for (
int t = 0; t < helper_->
NumTasks(); ++t) {
321 if (!is_in_subtasks_[t])
continue;
324 const IntegerValue size_min = helper_->
SizeMin(t);
325 if (size_min == 0)
continue;
327 const IntegerValue demand_min = demands_->
DemandMin(t);
328 if (demand_min == 0)
continue;
331 if (
end_min <= best_time)
continue;
356 const int id = watcher->
Register(
this);
359 for (
const int t : subtasks_) {
Implementation of AddCumulativeOverloadChecker().
void RegisterWith(GenericLiteralWatcher *watcher)
CumulativeEnergyConstraint(AffineExpression capacity, SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands, Model *model)
void RegisterWith(GenericLiteralWatcher *watcher)
CumulativeIsAfterSubsetConstraint(IntegerVariable var, AffineExpression capacity, const std::vector< int > &subtasks, const std::vector< IntegerValue > &offsets, SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands, Model *model)
void NotifyThatPropagatorMayNotReachFixedPointInOnePass(int id)
void WatchLiteral(Literal l, int id, int watch_index=-1)
void WatchUpperBound(IntegerVariable var, int id, int watch_index=-1)
void WatchLowerBound(IntegerVariable var, int id, int watch_index=-1)
void SetPropagatorPriority(int id, int priority)
int Register(PropagatorInterface *propagator)
Registers a propagator and returns its unique ids.
IntegerValue LowerBound(IntegerVariable i) const
Returns the current lower/upper bound of the given integer variable.
IntegerLiteral UpperBoundAsLiteral(IntegerVariable i) const
IntegerValue UpperBound(IntegerVariable i) const
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)
void AddPresenceReason(int t)
absl::Span< const TaskTime > TaskByIncreasingStartMin()
std::vector< IntegerLiteral > * MutableIntegerReason()
int NumTasks() const
Returns the number of task.
ABSL_MUST_USE_RESULT bool ReportConflict()
absl::Span< const AffineExpression > Sizes() const
const std::vector< ProfileEvent > & GetEnergyProfile()
bool IsPresent(int t) const
void SetTimeDirection(bool is_forward)
Literal PresenceLiteral(int index) const
void AddSizeMinReason(int t)
absl::Span< const AffineExpression > Starts() const
void AddEndMaxReason(int t, IntegerValue upper_bound)
absl::Span< const AffineExpression > Ends() const
void AddEndMinReason(int t, IntegerValue lower_bound)
void ClearReason()
Functions to clear and then set the current reason.
IntegerValue SizeMin(int t) const
absl::Span< const TaskTime > TaskByDecreasingEndMax()
ABSL_MUST_USE_RESULT bool SynchronizeAndSetTimeDirection(bool is_forward)
bool IsAbsent(int t) const
void WatchAllTasks(int id, GenericLiteralWatcher *watcher, bool watch_start_max=true, bool watch_end_max=true) const
IntegerValue EndMin(int t) const
ABSL_MUST_USE_RESULT bool PushIntegerLiteral(IntegerLiteral lit)
void AddStartMinReason(int t, IntegerValue lower_bound)
void AddDemandMinReason(int t)
IntegerValue EnergyMax(int t) const
void AddEnergyMinReason(int t)
void CacheAllEnergyValues()
const std::vector< AffineExpression > & Demands() const
ABSL_MUST_USE_RESULT bool DecreaseEnergyMax(int t, IntegerValue value)
IntegerValue DemandMin(int t) const
IntegerValue EnergyMin(int t) const
void Reset(int num_events)
IntegerType GetOptionalEnvelope() const
IntegerType GetEnvelope() const
void RemoveEvent(int event)
Makes event absent, compute the new envelope in O(log n).
void AddOrUpdateEvent(int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max)
void GetEventsWithOptionalEnvelopeGreaterThan(IntegerType target_envelope, int *critical_event, int *optional_event, IntegerType *available_energy) const
int GetMaxEventWithEnvelopeGreaterThan(IntegerType target_envelope) const
void AddOrUpdateOptionalEvent(int event, IntegerType initial_envelope_opt, IntegerType energy_max)
ReverseView< Container > reversed_view(const Container &c)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue.value())
const IntegerVariable kNoIntegerVariable(-1)
void AddCumulativeOverloadChecker(AffineExpression capacity, SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands, Model *model)
In SWIG mode, we don't want anything besides these top-level includes.
IntegerLiteral GreaterOrEqual(IntegerValue bound) const
var * coeff + constant >= bound.
static IntegerLiteral GreaterOrEqual(IntegerVariable i, IntegerValue bound)