1 // Copyright 2010-2021 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 #include "ortools/sat/timetable_edgefinding.h"
15
16 #include <algorithm>
17 #include <cstdint>
18 #include <functional>
19 #include <memory>
20 #include <vector>
21
22 #include "ortools/base/int_type.h"
23 #include "ortools/base/integral_types.h"
24 #include "ortools/base/iterator_adaptors.h"
25 #include "ortools/base/logging.h"
26 #include "ortools/util/sort.h"
27
28 namespace operations_research {
29 namespace sat {
30
TimeTableEdgeFinding(const std::vector<AffineExpression> & demands,AffineExpression capacity,SchedulingConstraintHelper * helper,IntegerTrail * integer_trail)31 TimeTableEdgeFinding::TimeTableEdgeFinding(
32 const std::vector<AffineExpression>& demands, AffineExpression capacity,
33 SchedulingConstraintHelper* helper, IntegerTrail* integer_trail)
34 : num_tasks_(helper->NumTasks()),
35 demands_(demands),
36 capacity_(capacity),
37 helper_(helper),
38 integer_trail_(integer_trail) {
39 // Edge finding structures.
40 mandatory_energy_before_end_max_.resize(num_tasks_);
41 mandatory_energy_before_start_min_.resize(num_tasks_);
42
43 // Energy of free parts.
44 size_free_.resize(num_tasks_);
45 energy_free_.resize(num_tasks_);
46 }
47
RegisterWith(GenericLiteralWatcher * watcher)48 void TimeTableEdgeFinding::RegisterWith(GenericLiteralWatcher* watcher) {
49 const int id = watcher->Register(this);
50 watcher->WatchUpperBound(capacity_.var, id);
51 helper_->WatchAllTasks(id, watcher);
52 for (int t = 0; t < num_tasks_; t++) {
53 watcher->WatchLowerBound(demands_[t].var, id);
54 }
55 }
56
Propagate()57 bool TimeTableEdgeFinding::Propagate() {
58 while (true) {
59 const int64_t old_timestamp = integer_trail_->num_enqueues();
60
61 if (!helper_->SynchronizeAndSetTimeDirection(true)) return false;
62 if (!TimeTableEdgeFindingPass()) return false;
63
64 if (!helper_->SynchronizeAndSetTimeDirection(false)) return false;
65 if (!TimeTableEdgeFindingPass()) return false;
66
67 // Stop if no propagation.
68 if (old_timestamp == integer_trail_->num_enqueues()) break;
69 }
70 return true;
71 }
72
BuildTimeTable()73 void TimeTableEdgeFinding::BuildTimeTable() {
74 scp_.clear();
75 ecp_.clear();
76
77 // Build start of compulsory part events.
78 for (const auto task_time :
79 ::gtl::reversed_view(helper_->TaskByDecreasingStartMax())) {
80 const int t = task_time.task_index;
81 if (!helper_->IsPresent(t)) continue;
82 if (task_time.time < helper_->EndMin(t)) {
83 scp_.push_back(task_time);
84 }
85 }
86
87 // Build end of compulsory part events.
88 for (const auto task_time : helper_->TaskByIncreasingEndMin()) {
89 const int t = task_time.task_index;
90 if (!helper_->IsPresent(t)) continue;
91 if (helper_->StartMax(t) < task_time.time) {
92 ecp_.push_back(task_time);
93 }
94 }
95
96 DCHECK_EQ(scp_.size(), ecp_.size());
97
98 const std::vector<TaskTime>& by_decreasing_end_max =
99 helper_->TaskByDecreasingEndMax();
100 const std::vector<TaskTime>& by_start_min =
101 helper_->TaskByIncreasingStartMin();
102
103 IntegerValue height = IntegerValue(0);
104 IntegerValue energy = IntegerValue(0);
105
106 // We don't care since at the beginning heigh is zero, and previous_time will
107 // be correct after the first iteration.
108 IntegerValue previous_time = IntegerValue(0);
109
110 int index_scp = 0; // index of the next value in scp
111 int index_ecp = 0; // index of the next value in ecp
112 int index_smin = 0; // index of the next value in by_start_min_
113 int index_emax = num_tasks_ - 1; // index of the next value in by_end_max_
114
115 while (index_emax >= 0) {
116 // Next time point.
117 // TODO(user): could be simplified with a sentinel.
118 IntegerValue time = by_decreasing_end_max[index_emax].time;
119 if (index_smin < num_tasks_) {
120 time = std::min(time, by_start_min[index_smin].time);
121 }
122 if (index_scp < scp_.size()) {
123 time = std::min(time, scp_[index_scp].time);
124 }
125 if (index_ecp < ecp_.size()) {
126 time = std::min(time, ecp_[index_ecp].time);
127 }
128
129 // Total amount of energy contained in the timetable until time.
130 energy += (time - previous_time) * height;
131 previous_time = time;
132
133 // Store the energy contained in the timetable just before those events.
134 while (index_smin < num_tasks_ && by_start_min[index_smin].time == time) {
135 mandatory_energy_before_start_min_[by_start_min[index_smin].task_index] =
136 energy;
137 index_smin++;
138 }
139
140 // Store the energy contained in the timetable just before those events.
141 while (index_emax >= 0 && by_decreasing_end_max[index_emax].time == time) {
142 mandatory_energy_before_end_max_[by_decreasing_end_max[index_emax]
143 .task_index] = energy;
144 index_emax--;
145 }
146
147 // Process the starting compulsory parts.
148 while (index_scp < scp_.size() && scp_[index_scp].time == time) {
149 height += DemandMin(scp_[index_scp].task_index);
150 index_scp++;
151 }
152
153 // Process the ending compulsory parts.
154 while (index_ecp < ecp_.size() && ecp_[index_ecp].time == time) {
155 height -= DemandMin(ecp_[index_ecp].task_index);
156 index_ecp++;
157 }
158 }
159 }
160
TimeTableEdgeFindingPass()161 bool TimeTableEdgeFinding::TimeTableEdgeFindingPass() {
162 // Initialize the data structures and build the free parts.
163 // --------------------------------------------------------
164 for (int t = 0; t < num_tasks_; ++t) {
165 // If the task has no mandatory part, then its free part is the task itself.
166 const IntegerValue start_max = helper_->StartMax(t);
167 const IntegerValue end_min = helper_->EndMin(t);
168 if (start_max >= end_min) {
169 size_free_[t] = helper_->SizeMin(t);
170 } else {
171 size_free_[t] = helper_->SizeMin(t) + start_max - end_min;
172 }
173 energy_free_[t] = size_free_[t] * DemandMin(t);
174 }
175
176 BuildTimeTable();
177 const auto& by_start_min = helper_->TaskByIncreasingStartMin();
178
179 IntegerValue previous_end = kMaxIntegerValue;
180
181 // Apply the Timetabling Edge Finding filtering rule.
182 // --------------------------------------------------
183 // The loop order is not important for correctness.
184 for (const TaskTime end_task_time : helper_->TaskByDecreasingEndMax()) {
185 const int end_task = end_task_time.task_index;
186
187 // TODO(user): consider optional tasks for additional propagation.
188 if (!helper_->IsPresent(end_task)) continue;
189 if (energy_free_[end_task] == 0) continue;
190
191 // We only need to consider each time point once.
192 if (end_task_time.time == previous_end) continue;
193 previous_end = end_task_time.time;
194
195 // Energy of the free parts contained in the interval [begin, end).
196 IntegerValue energy_free_parts = IntegerValue(0);
197
198 // Task that requires the biggest additional amount of energy to be
199 // scheduled at its minimum start time in the task interval [begin, end).
200 int max_task = -1;
201 IntegerValue free_energy_of_max_task_in_window(0);
202 IntegerValue extra_energy_required_by_max_task = kMinIntegerValue;
203
204 // Process task by decreasing start min.
205 for (const TaskTime begin_task_time : gtl::reversed_view(by_start_min)) {
206 const int begin_task = begin_task_time.task_index;
207
208 // TODO(user): consider optional tasks for additional propagation.
209 if (!helper_->IsPresent(begin_task)) continue;
210 if (energy_free_[begin_task] == 0) continue;
211
212 // The considered time window. Note that we use the "cached" values so
213 // that our mandatory energy before computation is correct.
214 const IntegerValue begin = begin_task_time.time; // Start min.
215 const IntegerValue end = end_task_time.time; // End max.
216
217 // Not a valid time window.
218 if (end <= begin) continue;
219
220 // We consider two different cases: either the free part overlaps the
221 // end of the interval (right) or it does not (inside).
222 //
223 // begin end
224 // v v
225 // right: ======|===
226 //
227 // begin end
228 // v v
229 // inside: ========== |
230 //
231 // In the inside case, the additional amount of energy required to
232 // schedule the task at its minimum start time is equal to the whole
233 // energy of the free part. In the right case, the additional energy is
234 // equal to the largest part of the free part that can fit in the task
235 // interval.
236 const IntegerValue end_max = helper_->EndMax(begin_task);
237 if (end_max <= end) {
238 // The whole task energy is contained in the task interval.
239 energy_free_parts += energy_free_[begin_task];
240 } else {
241 const IntegerValue demand_min = DemandMin(begin_task);
242 const IntegerValue extra_energy =
243 std::min(size_free_[begin_task], (end - begin)) * demand_min;
244
245 // This is not in the paper, but it is almost free for us to account for
246 // the free energy of this task that must be present in the window.
247 const IntegerValue free_energy_in_window =
248 std::max(IntegerValue(0),
249 size_free_[begin_task] - (end_max - end)) *
250 demand_min;
251
252 if (extra_energy > extra_energy_required_by_max_task) {
253 max_task = begin_task;
254 extra_energy_required_by_max_task = extra_energy;
255
256 // Account for the free energy of the old max task, and cache the
257 // new one for later.
258 energy_free_parts += free_energy_of_max_task_in_window;
259 free_energy_of_max_task_in_window = free_energy_in_window;
260 } else {
261 energy_free_parts += free_energy_in_window;
262 }
263 }
264
265 // No task to push. This happens if all the tasks that overlap the task
266 // interval are entirely contained in it.
267 // TODO(user): check that we should not fail if the interval is
268 // overloaded, i.e., available_energy < 0.
269 if (max_task == -1) continue;
270
271 // Compute the amount of energy available to schedule max_task.
272 const IntegerValue interval_energy = CapacityMax() * (end - begin);
273 const IntegerValue energy_mandatory =
274 mandatory_energy_before_end_max_[end_task] -
275 mandatory_energy_before_start_min_[begin_task];
276 const IntegerValue available_energy =
277 interval_energy - energy_free_parts - energy_mandatory;
278
279 // Enough energy to schedule max_task at its minimum start time.
280 if (extra_energy_required_by_max_task <= available_energy) continue;
281
282 // Compute the length of the mandatory subpart of max_task that should be
283 // considered as available.
284 //
285 // TODO(user): Because this use updated bounds, it might be more than what
286 // we accounted for in the precomputation. This is correct but could be
287 // improved uppon.
288 const IntegerValue mandatory_in = std::max(
289 IntegerValue(0), std::min(end, helper_->EndMin(max_task)) -
290 std::max(begin, helper_->StartMax(max_task)));
291
292 // Compute the new minimum start time of max_task.
293 const IntegerValue new_start =
294 end - mandatory_in - (available_energy / DemandMin(max_task));
295
296 // Push and explain only if the new start is bigger than the current one.
297 if (helper_->StartMin(max_task) < new_start) {
298 if (!IncreaseStartMin(begin, end, max_task, new_start)) return false;
299 }
300 }
301 }
302
303 return true;
304 }
305
IncreaseStartMin(IntegerValue begin,IntegerValue end,int task_index,IntegerValue new_start)306 bool TimeTableEdgeFinding::IncreaseStartMin(IntegerValue begin,
307 IntegerValue end, int task_index,
308 IntegerValue new_start) {
309 helper_->ClearReason();
310 std::vector<IntegerLiteral>* mutable_reason = helper_->MutableIntegerReason();
311
312 // Capacity of the resource.
313 if (capacity_.var != kNoIntegerVariable) {
314 mutable_reason->push_back(
315 integer_trail_->UpperBoundAsLiteral(capacity_.var));
316 }
317
318 // Variables of the task to be pushed. We do not need the end max for this
319 // task and we only need for it to begin in the time window.
320 if (demands_[task_index].var != kNoIntegerVariable) {
321 mutable_reason->push_back(
322 integer_trail_->LowerBoundAsLiteral(demands_[task_index].var));
323 }
324 helper_->AddStartMinReason(task_index, begin);
325 helper_->AddSizeMinReason(task_index);
326
327 // Task contributing to the energy in the interval.
328 for (int t = 0; t < num_tasks_; ++t) {
329 if (t == task_index) continue;
330 if (!helper_->IsPresent(t)) continue;
331 if (helper_->EndMax(t) <= begin) continue;
332 if (helper_->StartMin(t) >= end) continue;
333
334 if (demands_[t].var != kNoIntegerVariable) {
335 mutable_reason->push_back(
336 integer_trail_->LowerBoundAsLiteral(demands_[t].var));
337 }
338
339 // We need the reason for the energy contribution of this interval into
340 // [begin, end].
341 //
342 // TODO(user): Since we actually do not account fully for this energy, we
343 // could relax the reason more.
344 //
345 // TODO(user): This reason might not be enough in the presence of variable
346 // size intervals where StartMax and EndMin give rise to more energy
347 // that just using size min and these bounds. Fix.
348 helper_->AddStartMinReason(t, std::min(begin, helper_->StartMin(t)));
349 helper_->AddEndMaxReason(t, std::max(end, helper_->EndMax(t)));
350 helper_->AddSizeMinReason(t);
351 helper_->AddPresenceReason(t);
352 }
353
354 return helper_->IncreaseStartMin(task_index, new_start);
355 }
356
357 } // namespace sat
358 } // namespace operations_research
359