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