OR-Tools  8.2
routing_breaks.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
14#include <algorithm>
15
17
18namespace operations_research {
19
21 DCHECK_LE(tasks->num_chain_tasks, tasks->start_min.size());
22 DCHECK_EQ(tasks->start_min.size(), tasks->start_max.size());
23 DCHECK_EQ(tasks->start_min.size(), tasks->duration_min.size());
24 DCHECK_EQ(tasks->start_min.size(), tasks->duration_max.size());
25 DCHECK_EQ(tasks->start_min.size(), tasks->end_min.size());
26 DCHECK_EQ(tasks->start_min.size(), tasks->end_max.size());
27 DCHECK_EQ(tasks->start_min.size(), tasks->is_preemptible.size());
28 // Do forward deductions, then backward deductions.
29 // All propagators are followed by Precedences(),
30 // except MirrorTasks() after which Precedences() would make no deductions,
31 // and DetectablePrecedencesWithChain() which is stronger than Precedences().
32 // Precedences() is a propagator that does obvious deductions quickly (O(n)),
33 // so interleaving Precedences() speeds up the propagation fixed point.
34 if (!Precedences(tasks) || !EdgeFinding(tasks) || !Precedences(tasks) ||
36 return false;
37 }
38 if (!tasks->forbidden_intervals.empty()) {
39 if (!ForbiddenIntervals(tasks) || !Precedences(tasks)) return false;
40 }
41 if (!tasks->distance_duration.empty()) {
42 if (!DistanceDuration(tasks) || !Precedences(tasks)) return false;
43 }
44 if (!MirrorTasks(tasks) || !EdgeFinding(tasks) || !Precedences(tasks) ||
46 return false;
47 }
48 return true;
49}
50
52 const int num_chain_tasks = tasks->num_chain_tasks;
53 if (num_chain_tasks > 0) {
54 // Propagate forwards.
55 int64 time = tasks->start_min[0];
56 for (int task = 0; task < num_chain_tasks; ++task) {
57 time = std::max(tasks->start_min[task], time);
58 tasks->start_min[task] = time;
59 time = CapAdd(time, tasks->duration_min[task]);
60 if (tasks->end_max[task] < time) return false;
61 time = std::max(time, tasks->end_min[task]);
62 tasks->end_min[task] = time;
63 }
64 // Propagate backwards.
65 time = tasks->end_max[num_chain_tasks - 1];
66 for (int task = num_chain_tasks - 1; task >= 0; --task) {
67 time = std::min(tasks->end_max[task], time);
68 tasks->end_max[task] = time;
69 time = CapSub(time, tasks->duration_min[task]);
70 if (time < tasks->start_min[task]) return false;
71 time = std::min(time, tasks->start_max[task]);
72 tasks->start_max[task] = time;
73 }
74 }
75 const int num_tasks = tasks->start_min.size();
76 for (int task = 0; task < num_tasks; ++task) {
77 // Enforce start + duration <= end.
78 tasks->end_min[task] =
79 std::max(tasks->end_min[task],
80 CapAdd(tasks->start_min[task], tasks->duration_min[task]));
81 tasks->start_max[task] =
82 std::min(tasks->start_max[task],
83 CapSub(tasks->end_max[task], tasks->duration_min[task]));
84 tasks->duration_max[task] =
85 std::min(tasks->duration_max[task],
86 CapSub(tasks->end_max[task], tasks->start_min[task]));
87 if (!tasks->is_preemptible[task]) {
88 // Enforce start + duration == end for nonpreemptibles.
89 tasks->end_max[task] =
90 std::min(tasks->end_max[task],
91 CapAdd(tasks->start_max[task], tasks->duration_max[task]));
92 tasks->start_min[task] =
93 std::max(tasks->start_min[task],
94 CapSub(tasks->end_min[task], tasks->duration_max[task]));
95 tasks->duration_min[task] =
96 std::max(tasks->duration_min[task],
97 CapSub(tasks->end_min[task], tasks->start_max[task]));
98 }
99 if (tasks->duration_min[task] > tasks->duration_max[task]) return false;
100 if (tasks->end_min[task] > tasks->end_max[task]) return false;
101 if (tasks->start_min[task] > tasks->start_max[task]) return false;
102 }
103 return true;
104}
105
107 const int num_tasks = tasks->start_min.size();
108 // For all tasks, start_min := -end_max and end_max := -start_min.
109 for (int task = 0; task < num_tasks; ++task) {
110 const int64 t = -tasks->start_min[task];
111 tasks->start_min[task] = -tasks->end_max[task];
112 tasks->end_max[task] = t;
113 }
114 // For all tasks, start_max := -end_min and end_min := -start_max.
115 for (int task = 0; task < num_tasks; ++task) {
116 const int64 t = -tasks->start_max[task];
117 tasks->start_max[task] = -tasks->end_min[task];
118 tasks->end_min[task] = t;
119 }
120 // In the mirror problem, tasks linked by precedences are in reversed order.
121 const int num_chain_tasks = tasks->num_chain_tasks;
122 for (const auto it :
123 {tasks->start_min.begin(), tasks->start_max.begin(),
124 tasks->duration_min.begin(), tasks->duration_max.begin(),
125 tasks->end_min.begin(), tasks->end_max.begin()}) {
126 std::reverse(it, it + num_chain_tasks);
127 std::reverse(it + num_chain_tasks, it + num_tasks);
128 }
129 std::reverse(tasks->is_preemptible.begin(),
130 tasks->is_preemptible.begin() + num_chain_tasks);
131 std::reverse(tasks->is_preemptible.begin() + num_chain_tasks,
132 tasks->is_preemptible.begin() + num_tasks);
133 return true;
134}
135
137 const int num_tasks = tasks->start_min.size();
138 // Prepare start_min events for tree.
139 tasks_by_start_min_.resize(num_tasks);
140 std::iota(tasks_by_start_min_.begin(), tasks_by_start_min_.end(), 0);
141 std::sort(
142 tasks_by_start_min_.begin(), tasks_by_start_min_.end(),
143 [&](int i, int j) { return tasks->start_min[i] < tasks->start_min[j]; });
144 event_of_task_.resize(num_tasks);
145 for (int event = 0; event < num_tasks; ++event) {
146 event_of_task_[tasks_by_start_min_[event]] = event;
147 }
148 // Tasks will be browsed according to end_max order.
149 tasks_by_end_max_.resize(num_tasks);
150 std::iota(tasks_by_end_max_.begin(), tasks_by_end_max_.end(), 0);
151 std::sort(
152 tasks_by_end_max_.begin(), tasks_by_end_max_.end(),
153 [&](int i, int j) { return tasks->end_max[i] < tasks->end_max[j]; });
154
155 // Generic overload checking: insert tasks by end_max,
156 // fail if envelope > end_max.
157 theta_lambda_tree_.Reset(num_tasks);
158 for (const int task : tasks_by_end_max_) {
159 theta_lambda_tree_.AddOrUpdateEvent(
160 event_of_task_[task], tasks->start_min[task], tasks->duration_min[task],
161 tasks->duration_min[task]);
162 if (theta_lambda_tree_.GetEnvelope() > tasks->end_max[task]) {
163 return false;
164 }
165 }
166
167 // Generic edge finding: from full set of tasks, at each end_max event in
168 // decreasing order, check lambda feasibility, then move end_max task from
169 // theta to lambda.
170 for (int i = num_tasks - 1; i >= 0; --i) {
171 const int task = tasks_by_end_max_[i];
172 const int64 envelope = theta_lambda_tree_.GetEnvelope();
173 // If a nonpreemptible optional would overload end_max, push to envelope.
174 while (theta_lambda_tree_.GetOptionalEnvelope() > tasks->end_max[task]) {
175 int critical_event; // Dummy value.
176 int optional_event;
177 int64 available_energy; // Dummy value.
179 tasks->end_max[task], &critical_event, &optional_event,
180 &available_energy);
181 const int optional_task = tasks_by_start_min_[optional_event];
182 tasks->start_min[optional_task] =
183 std::max(tasks->start_min[optional_task], envelope);
184 theta_lambda_tree_.RemoveEvent(optional_event);
185 }
186 if (!tasks->is_preemptible[task]) {
187 theta_lambda_tree_.AddOrUpdateOptionalEvent(event_of_task_[task],
188 tasks->start_min[task],
189 tasks->duration_min[task]);
190 } else {
191 theta_lambda_tree_.RemoveEvent(event_of_task_[task]);
192 }
193 }
194 return true;
195}
196
198 const int num_tasks = tasks->start_min.size();
199 // Prepare start_min events for tree.
200 tasks_by_start_min_.resize(num_tasks);
201 std::iota(tasks_by_start_min_.begin(), tasks_by_start_min_.end(), 0);
202 std::sort(
203 tasks_by_start_min_.begin(), tasks_by_start_min_.end(),
204 [&](int i, int j) { return tasks->start_min[i] < tasks->start_min[j]; });
205 event_of_task_.resize(num_tasks);
206 for (int event = 0; event < num_tasks; ++event) {
207 event_of_task_[tasks_by_start_min_[event]] = event;
208 }
209 theta_lambda_tree_.Reset(num_tasks);
210
211 // Sort nonchain tasks by start max = end_max - duration_min.
212 const int num_chain_tasks = tasks->num_chain_tasks;
213 nonchain_tasks_by_start_max_.resize(num_tasks - num_chain_tasks);
214 std::iota(nonchain_tasks_by_start_max_.begin(),
215 nonchain_tasks_by_start_max_.end(), num_chain_tasks);
216 std::sort(nonchain_tasks_by_start_max_.begin(),
217 nonchain_tasks_by_start_max_.end(), [&tasks](int i, int j) {
218 return tasks->end_max[i] - tasks->duration_min[i] <
219 tasks->end_max[j] - tasks->duration_min[j];
220 });
221
222 // Detectable precedences, specialized for routes: for every task on route,
223 // put all tasks before it in the tree, then push with envelope.
224 int index_nonchain = 0;
225 for (int i = 0; i < num_chain_tasks; ++i) {
226 if (!tasks->is_preemptible[i]) {
227 // Add all nonchain tasks detected before i.
228 while (index_nonchain < nonchain_tasks_by_start_max_.size()) {
229 const int task = nonchain_tasks_by_start_max_[index_nonchain];
230 if (tasks->end_max[task] - tasks->duration_min[task] >=
231 tasks->start_min[i] + tasks->duration_min[i])
232 break;
233 theta_lambda_tree_.AddOrUpdateEvent(
234 event_of_task_[task], tasks->start_min[task],
235 tasks->duration_min[task], tasks->duration_min[task]);
236 index_nonchain++;
237 }
238 }
239 // All chain and nonchain tasks before i are now in the tree, push i.
240 const int64 new_start_min = theta_lambda_tree_.GetEnvelope();
241 // Add i to the tree before updating it.
242 theta_lambda_tree_.AddOrUpdateEvent(event_of_task_[i], tasks->start_min[i],
243 tasks->duration_min[i],
244 tasks->duration_min[i]);
245 tasks->start_min[i] = std::max(tasks->start_min[i], new_start_min);
246 }
247 return true;
248}
249
251 if (tasks->forbidden_intervals.empty()) return true;
252 const int num_tasks = tasks->start_min.size();
253 for (int task = 0; task < num_tasks; ++task) {
254 if (tasks->duration_min[task] == 0) continue;
255 if (tasks->forbidden_intervals[task] == nullptr) continue;
256 // If start_min forbidden, push to next feasible value.
257 {
258 const auto& interval =
259 tasks->forbidden_intervals[task]->FirstIntervalGreaterOrEqual(
260 tasks->start_min[task]);
261 if (interval == tasks->forbidden_intervals[task]->end()) continue;
262 if (interval->start <= tasks->start_min[task]) {
263 tasks->start_min[task] = CapAdd(interval->end, 1);
264 }
265 }
266 // If end_max forbidden, push to next feasible value.
267 {
268 const int64 start_max =
269 CapSub(tasks->end_max[task], tasks->duration_min[task]);
270 const auto& interval =
271 tasks->forbidden_intervals[task]->LastIntervalLessOrEqual(start_max);
272 if (interval == tasks->forbidden_intervals[task]->end()) continue;
273 if (interval->end >= start_max) {
274 tasks->end_max[task] =
275 CapAdd(interval->start, tasks->duration_min[task] - 1);
276 }
277 }
278 if (CapAdd(tasks->start_min[task], tasks->duration_min[task]) >
279 tasks->end_max[task]) {
280 return false;
281 }
282 }
283 return true;
284}
285
287 if (tasks->distance_duration.empty()) return true;
288 if (tasks->num_chain_tasks == 0) return true;
289 const int route_start = 0;
290 const int route_end = tasks->num_chain_tasks - 1;
291 const int num_tasks = tasks->start_min.size();
292 for (int i = 0; i < tasks->distance_duration.size(); ++i) {
293 const int64 max_distance = tasks->distance_duration[i].first;
294 const int64 minimum_break_duration = tasks->distance_duration[i].second;
295
296 // This is a sweeping algorithm that looks whether the union of intervals
297 // defined by breaks and route start/end is (-infty, +infty).
298 // Those intervals are:
299 // - route start: (-infty, start_max + distance]
300 // - route end: [end_min, +infty)
301 // - breaks: [start_min, end_max + distance) if their duration_max
302 // is >= min_duration, empty set otherwise.
303 // If sweeping finds that a time point can be covered by only one interval,
304 // it will force the corresponding break or route start/end to cover this
305 // point, which can force a break to be above minimum_break_duration.
306
307 // We suppose break tasks are ordered, so the algorithm supposes that
308 // start_min(task_n) <= start_min(task_{n+1}) and
309 // end_max(task_n) <= end_max(task_{n+1}).
310 for (int task = tasks->num_chain_tasks + 1; task < num_tasks; ++task) {
311 tasks->start_min[task] =
312 std::max(tasks->start_min[task], tasks->start_min[task - 1]);
313 }
314 for (int task = num_tasks - 2; task >= tasks->num_chain_tasks; --task) {
315 tasks->end_max[task] =
316 std::min(tasks->end_max[task], tasks->end_max[task + 1]);
317 }
318 // Skip breaks that cannot be performed after start.
319 int index_break_by_emax = tasks->num_chain_tasks;
320 while (index_break_by_emax < num_tasks &&
321 tasks->end_max[index_break_by_emax] <= tasks->end_max[route_start]) {
322 ++index_break_by_emax;
323 }
324 // Special case: no breaks after start.
325 if (index_break_by_emax == num_tasks) {
326 tasks->end_min[route_start] =
327 std::max(tasks->end_min[route_start],
328 CapSub(tasks->start_min[route_end], max_distance));
329 tasks->start_max[route_end] =
330 std::min(tasks->start_max[route_end],
331 CapAdd(tasks->end_max[route_start], max_distance));
332 continue;
333 }
334 // There will be a break after start, so route_start coverage is tested.
335 // Initial state: start at -inf with route_start in task_set.
336 // Sweep over profile, looking for time points where the number of
337 // covering breaks is <= 1. If it is 0, fail, otherwise force the
338 // unique break to cover it.
339 // Route start and end get a special treatment, not sure generalizing
340 // would be better.
341 int64 xor_active_tasks = route_start;
342 int num_active_tasks = 1;
343 int64 previous_time = kint64min;
344 const int64 route_start_time =
345 CapAdd(tasks->end_max[route_start], max_distance);
346 const int64 route_end_time = tasks->start_min[route_end];
347 int index_break_by_smin = tasks->num_chain_tasks;
348 while (index_break_by_emax < num_tasks) {
349 // Find next time point among start/end of covering intervals.
350 int64 current_time =
351 CapAdd(tasks->end_max[index_break_by_emax], max_distance);
352 if (index_break_by_smin < num_tasks) {
353 current_time =
354 std::min(current_time, tasks->start_min[index_break_by_smin]);
355 }
356 if (previous_time < route_start_time && route_start_time < current_time) {
357 current_time = route_start_time;
358 }
359 if (previous_time < route_end_time && route_end_time < current_time) {
360 current_time = route_end_time;
361 }
362 // If num_active_tasks was 1, the unique active task must cover from
363 // previous_time to current_time.
364 if (num_active_tasks == 1) {
365 // xor_active_tasks is the unique task that can cover [previous_time,
366 // current_time).
367 if (xor_active_tasks != route_end) {
368 tasks->end_min[xor_active_tasks] =
369 std::max(tasks->end_min[xor_active_tasks],
370 CapSub(current_time, max_distance));
371 if (xor_active_tasks != route_start) {
372 tasks->duration_min[xor_active_tasks] = std::max(
373 tasks->duration_min[xor_active_tasks],
374 std::max(
375 minimum_break_duration,
376 CapSub(CapSub(current_time, max_distance), previous_time)));
377 }
378 }
379 }
380 // Process covering intervals that start or end at current_time.
381 while (index_break_by_smin < num_tasks &&
382 current_time == tasks->start_min[index_break_by_smin]) {
383 if (tasks->duration_max[index_break_by_smin] >=
384 minimum_break_duration) {
385 xor_active_tasks ^= index_break_by_smin;
386 ++num_active_tasks;
387 }
388 ++index_break_by_smin;
389 }
390 while (index_break_by_emax < num_tasks &&
391 current_time ==
392 CapAdd(tasks->end_max[index_break_by_emax], max_distance)) {
393 if (tasks->duration_max[index_break_by_emax] >=
394 minimum_break_duration) {
395 xor_active_tasks ^= index_break_by_emax;
396 --num_active_tasks;
397 }
398 ++index_break_by_emax;
399 }
400 if (current_time == route_start_time) {
401 xor_active_tasks ^= route_start;
402 --num_active_tasks;
403 }
404 if (current_time == route_end_time) {
405 xor_active_tasks ^= route_end;
406 ++num_active_tasks;
407 }
408 // If num_active_tasks becomes 1, the unique active task must cover from
409 // current_time.
410 if (num_active_tasks <= 0) return false;
411 if (num_active_tasks == 1) {
412 if (xor_active_tasks != route_start) {
413 // xor_active_tasks is the unique task that can cover from
414 // current_time to the next time point.
415 tasks->start_max[xor_active_tasks] =
416 std::min(tasks->start_max[xor_active_tasks], current_time);
417 if (xor_active_tasks != route_end) {
418 tasks->duration_min[xor_active_tasks] = std::max(
419 tasks->duration_min[xor_active_tasks], minimum_break_duration);
420 }
421 }
422 }
423 previous_time = current_time;
424 }
425 }
426 return true;
427}
428
430 const int num_chain_tasks = tasks->num_chain_tasks;
431 if (num_chain_tasks < 1) return true;
432 // TODO(user): add stronger bounds.
433 // The duration of the chain plus that of nonchain tasks that must be
434 // performed during the chain is a lower bound of the chain span.
435 {
436 int64 sum_chain_durations = 0;
437 const auto duration_start = tasks->duration_min.begin();
438 const auto duration_end = tasks->duration_min.begin() + num_chain_tasks;
439 for (auto it = duration_start; it != duration_end; ++it) {
440 sum_chain_durations = CapAdd(sum_chain_durations, *it);
441 }
442 int64 sum_forced_nonchain_durations = 0;
443 for (int i = num_chain_tasks; i < tasks->start_min.size(); ++i) {
444 // Tasks that can be executed before or after are skipped.
445 if (tasks->end_min[i] <= tasks->start_max[0] ||
446 tasks->end_min[num_chain_tasks - 1] <= tasks->start_max[i]) {
447 continue;
448 }
449 sum_forced_nonchain_durations =
450 CapAdd(sum_forced_nonchain_durations, tasks->duration_min[i]);
451 }
452 tasks->span_min =
453 std::max(tasks->span_min,
454 CapAdd(sum_chain_durations, sum_forced_nonchain_durations));
455 }
456 // The difference end of the chain - start of the chain is a lower bound.
457 {
458 const int64 end_minus_start =
459 CapSub(tasks->end_min[num_chain_tasks - 1], tasks->start_max[0]);
460 tasks->span_min = std::max(tasks->span_min, end_minus_start);
461 }
462
463 return tasks->span_min <= tasks->span_max;
464}
465
466// Computes a lower bound of the span of the chain, taking into account only
467// the first nonchain task.
468// TODO(user): extend to arbitrary number of nonchain tasks.
470 // Do nothing if there are no chain tasks or no nonchain tasks.
471 const int num_chain_tasks = tasks->num_chain_tasks;
472 if (num_chain_tasks < 1) return true;
473 if (num_chain_tasks == tasks->start_min.size()) return true;
474 const int task_index = num_chain_tasks;
475 if (!Precedences(tasks)) return false;
476 const int64 min_possible_chain_end = tasks->end_min[num_chain_tasks - 1];
477 const int64 max_possible_chain_start = tasks->start_max[0];
478 // For each chain task i, compute cumulated duration of chain tasks before it.
479 int64 total_duration = 0;
480 {
481 total_duration_before_.resize(num_chain_tasks);
482 for (int i = 0; i < num_chain_tasks; ++i) {
483 total_duration_before_[i] = total_duration;
484 total_duration = CapAdd(total_duration, tasks->duration_min[i]);
485 }
486 }
487 // Estimate span min of chain tasks. Use the schedule that ends at
488 // min_possible_chain_end and starts at smallest of start_max[0] or the
489 // threshold where pushing start[0] later does not make a difference to the
490 // chain span because of chain precedence constraints,
491 // i.e. min_possible_chain_end - total_duration.
492 {
493 const int64 chain_span_min =
494 min_possible_chain_end -
495 std::min(tasks->start_max[0], min_possible_chain_end - total_duration);
496 if (chain_span_min > tasks->span_max) {
497 return false;
498 } else {
499 tasks->span_min = std::max(tasks->span_min, chain_span_min);
500 }
501 // If task can be performed before or after the chain,
502 // span_min is chain_span_min.
503 if (tasks->end_min[task_index] <= tasks->start_max[0] ||
504 tasks->end_min[num_chain_tasks - 1] <= tasks->start_max[task_index]) {
505 return true;
506 }
507 }
508 // Scan all possible preemption positions of the nontask chain,
509 // keep the one that yields the minimum span.
510 int64 span_min = kint64max;
511 bool schedule_is_feasible = false;
512 for (int i = 0; i < num_chain_tasks; ++i) {
513 if (!tasks->is_preemptible[i]) continue;
514 // Estimate span min if tasks is performed during i.
515 // For all possible minimal-span schedules, there is a schedule where task i
516 // and nonchain task form a single block. Thus, we only consider those.
517 const int64 block_start_min =
518 std::max(tasks->start_min[i],
519 tasks->start_min[task_index] - tasks->duration_min[i]);
520 const int64 block_start_max =
521 std::min(tasks->start_max[task_index],
522 tasks->start_max[i] - tasks->duration_min[task_index]);
523 if (block_start_min > block_start_max) continue;
524
525 // Compute the block start that yields the minimal span.
526 // Given a feasible block start, a chain of minimum span constrained to
527 // this particular block start can be obtained by scheduling all tasks after
528 // the block at their earliest, and all tasks before it at their latest.
529 // The span can be decomposed into two parts: the head, which are the
530 // tasks that are before the block, and the tail, which are the block and
531 // the tasks after it.
532 // When the block start varies, the head length of the optimal schedule
533 // described above decreases as much as the block start decreases, until
534 // an inflection point at which it stays constant. That inflection value
535 // is the one where the precedence constraints force the chain start to
536 // decrease because of durations.
537 const int64 head_inflection =
538 max_possible_chain_start + total_duration_before_[i];
539 // The map from block start to minimal tail length also has an inflection
540 // point, that additionally depends on the nonchain task's duration.
541 const int64 tail_inflection = min_possible_chain_end -
542 (total_duration - total_duration_before_[i]) -
543 tasks->duration_min[task_index];
544 // All block start values between these two yield the same minimal span.
545 // Indeed, first, mind that the inflection points might be in any order.
546 // - if head_inflection < tail_inflection, then inside the interval
547 // [head_inflection, tail_inflection], increasing the block start by delta
548 // decreases the tail length by delta and increases the head length by
549 // delta too.
550 // - if tail_inflection < head_inflection, then inside the interval
551 // [tail_inflection, head_inflection], head length is constantly at
552 // total_duration_before_[i], and tail length is also constant.
553 // In both cases, outside of the interval, one part is constant and the
554 // other increases as much as the distance to the interval.
555 // We can abstract inflection point to the interval they form.
556 const int64 optimal_interval_min_start =
557 std::min(head_inflection, tail_inflection);
558 const int64 optimal_interval_max_start =
559 std::max(head_inflection, tail_inflection);
560 // If the optimal interval for block start intersects the feasible interval,
561 // we can select any point within it, for instance the earliest one.
562 int64 block_start = std::max(optimal_interval_min_start, block_start_min);
563 // If the intervals do not intersect, the feasible value closest to the
564 // optimal interval has the minimal span, because the span increases as
565 // much as the distance to the optimal interval.
566 if (optimal_interval_max_start < block_start_min) {
567 // Optimal interval is before feasible interval, closest is feasible min.
568 block_start = block_start_min;
569 } else if (block_start_max < optimal_interval_min_start) {
570 // Optimal interval is after feasible interval, closest is feasible max.
571 block_start = block_start_max;
572 }
573 // Compute span for the chosen block start.
574 const int64 head_duration =
575 std::max(block_start, head_inflection) - max_possible_chain_start;
576 const int64 tail_duration =
577 min_possible_chain_end - std::min(block_start, tail_inflection);
578 const int64 optimal_span_at_i = head_duration + tail_duration;
579 span_min = std::min(span_min, optimal_span_at_i);
580 schedule_is_feasible = true;
581 }
582 if (!schedule_is_feasible || span_min > tasks->span_max) {
583 return false;
584 } else {
585 tasks->span_min = std::max(tasks->span_min, span_min);
586 return true;
587 }
588}
589
590void AppendTasksFromPath(const std::vector<int64>& path,
591 const TravelBounds& travel_bounds,
592 const RoutingDimension& dimension,
594 const int num_nodes = path.size();
595 DCHECK_EQ(travel_bounds.pre_travels.size(), num_nodes - 1);
596 DCHECK_EQ(travel_bounds.post_travels.size(), num_nodes - 1);
597 for (int i = 0; i < num_nodes; ++i) {
598 const int64 cumul_min = dimension.CumulVar(path[i])->Min();
599 const int64 cumul_max = dimension.CumulVar(path[i])->Max();
600 // Add task associated to visit i.
601 // Visits start at Cumul(path[i]) - before_visit
602 // and end at Cumul(path[i]) + after_visit
603 {
604 const int64 before_visit =
605 (i == 0) ? 0 : travel_bounds.post_travels[i - 1];
606 const int64 after_visit =
607 (i == num_nodes - 1) ? 0 : travel_bounds.pre_travels[i];
608
609 tasks->start_min.push_back(CapSub(cumul_min, before_visit));
610 tasks->start_max.push_back(CapSub(cumul_max, before_visit));
611 tasks->duration_min.push_back(CapAdd(before_visit, after_visit));
612 tasks->duration_max.push_back(CapAdd(before_visit, after_visit));
613 tasks->end_min.push_back(CapAdd(cumul_min, after_visit));
614 tasks->end_max.push_back(CapAdd(cumul_max, after_visit));
615 tasks->is_preemptible.push_back(false);
616 }
617 if (i == num_nodes - 1) break;
618
619 // Tasks from travels.
620 // A travel task starts at Cumul(path[i]) + pre_travel,
621 // last for FixedTransitVar(path[i]) - pre_travel - post_travel,
622 // and must end at the latest at Cumul(path[i+1]) - post_travel.
623 {
624 const int64 pre_travel = travel_bounds.pre_travels[i];
625 const int64 post_travel = travel_bounds.post_travels[i];
626 tasks->start_min.push_back(CapAdd(cumul_min, pre_travel));
627 tasks->start_max.push_back(CapAdd(cumul_max, pre_travel));
628 tasks->duration_min.push_back(
629 std::max<int64>(0, CapSub(travel_bounds.min_travels[i],
630 CapAdd(pre_travel, post_travel))));
631 tasks->duration_max.push_back(
632 travel_bounds.max_travels[i] == kint64max
633 ? kint64max
634 : std::max<int64>(0, CapSub(travel_bounds.max_travels[i],
635 CapAdd(pre_travel, post_travel))));
636 tasks->end_min.push_back(
637 CapSub(dimension.CumulVar(path[i + 1])->Min(), post_travel));
638 tasks->end_max.push_back(
639 CapSub(dimension.CumulVar(path[i + 1])->Max(), post_travel));
640 tasks->is_preemptible.push_back(true);
641 }
642 }
643}
644
645void FillTravelBoundsOfVehicle(int vehicle, const std::vector<int64>& path,
646 const RoutingDimension& dimension,
647 TravelBounds* travel_bounds) {
648 // Fill path and min/max/pre/post travel bounds.
649 FillPathEvaluation(path, dimension.transit_evaluator(vehicle),
650 &travel_bounds->min_travels);
651 const int num_travels = travel_bounds->min_travels.size();
652 travel_bounds->max_travels.assign(num_travels, kint64max);
653 {
654 const int index = dimension.GetPreTravelEvaluatorOfVehicle(vehicle);
655 if (index == -1) {
656 travel_bounds->pre_travels.assign(num_travels, 0);
657 } else {
658 FillPathEvaluation(path, dimension.model()->TransitCallback(index),
659 &travel_bounds->pre_travels);
660 }
661 }
662 {
663 const int index = dimension.GetPostTravelEvaluatorOfVehicle(vehicle);
664 if (index == -1) {
665 travel_bounds->post_travels.assign(num_travels, 0);
666 } else {
667 FillPathEvaluation(path, dimension.model()->TransitCallback(index),
668 &travel_bounds->post_travels);
669 }
670 }
671}
672
673void AppendTasksFromIntervals(const std::vector<IntervalVar*>& intervals,
675 for (IntervalVar* interval : intervals) {
676 if (!interval->MustBePerformed()) continue;
677 tasks->start_min.push_back(interval->StartMin());
678 tasks->start_max.push_back(interval->StartMax());
679 tasks->duration_min.push_back(interval->DurationMin());
680 tasks->duration_max.push_back(interval->DurationMax());
681 tasks->end_min.push_back(interval->EndMin());
682 tasks->end_max.push_back(interval->EndMax());
683 tasks->is_preemptible.push_back(false);
684 }
685}
686
688 const RoutingDimension* dimension)
689 : Constraint(dimension->model()->solver()),
690 model_(dimension->model()),
691 dimension_(dimension) {
692 vehicle_demons_.resize(model_->vehicles());
693}
694
696 for (int vehicle = 0; vehicle < model_->vehicles(); vehicle++) {
697 if (dimension_->GetBreakIntervalsOfVehicle(vehicle).empty() &&
698 dimension_->GetBreakDistanceDurationOfVehicle(vehicle).empty()) {
699 continue;
700 }
701 vehicle_demons_[vehicle] = MakeDelayedConstraintDemon1(
702 solver(), this, &GlobalVehicleBreaksConstraint::PropagateVehicle,
703 "PropagateVehicle", vehicle);
704 for (IntervalVar* interval :
705 dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
706 interval->WhenAnything(vehicle_demons_[vehicle]);
707 }
708 }
709 const int num_cumuls = dimension_->cumuls().size();
710 const int num_nexts = model_->Nexts().size();
711 for (int node = 0; node < num_cumuls; node++) {
712 Demon* dimension_demon = MakeConstraintDemon1(
713 solver(), this, &GlobalVehicleBreaksConstraint::PropagateNode,
714 "PropagateNode", node);
715 if (node < num_nexts) {
716 model_->NextVar(node)->WhenBound(dimension_demon);
717 dimension_->SlackVar(node)->WhenRange(dimension_demon);
718 }
719 model_->VehicleVar(node)->WhenBound(dimension_demon);
720 dimension_->CumulVar(node)->WhenRange(dimension_demon);
721 }
722}
723
725 for (int vehicle = 0; vehicle < model_->vehicles(); vehicle++) {
726 if (!dimension_->GetBreakIntervalsOfVehicle(vehicle).empty() ||
727 !dimension_->GetBreakDistanceDurationOfVehicle(vehicle).empty()) {
728 PropagateVehicle(vehicle);
729 }
730 }
731}
732
733// This dispatches node events to the right vehicle propagator.
734// It also filters out a part of uninteresting events, on which the vehicle
735// propagator will not find anything new.
736void GlobalVehicleBreaksConstraint::PropagateNode(int node) {
737 if (!model_->VehicleVar(node)->Bound()) return;
738 const int vehicle = model_->VehicleVar(node)->Min();
739 if (vehicle < 0 || vehicle_demons_[vehicle] == nullptr) return;
740 EnqueueDelayedDemon(vehicle_demons_[vehicle]);
741}
742
743void GlobalVehicleBreaksConstraint::FillPartialPathOfVehicle(int vehicle) {
744 path_.clear();
745 int current = model_->Start(vehicle);
746 while (!model_->IsEnd(current)) {
747 path_.push_back(current);
748 current = model_->NextVar(current)->Bound()
749 ? model_->NextVar(current)->Min()
750 : model_->End(vehicle);
751 }
752 path_.push_back(current);
753}
754
755void GlobalVehicleBreaksConstraint::FillPathTravels(
756 const std::vector<int64>& path) {
757 const int num_travels = path.size() - 1;
758 travel_bounds_.min_travels.resize(num_travels);
759 travel_bounds_.max_travels.resize(num_travels);
760 for (int i = 0; i < num_travels; ++i) {
761 travel_bounds_.min_travels[i] = dimension_->FixedTransitVar(path[i])->Min();
762 travel_bounds_.max_travels[i] = dimension_->FixedTransitVar(path[i])->Max();
763 }
764}
765
766// First, perform energy-based reasoning on intervals and cumul variables.
767// Then, perform reasoning on slack variables.
768void GlobalVehicleBreaksConstraint::PropagateVehicle(int vehicle) {
769 // Fill path and pre/post travel information.
770 FillPartialPathOfVehicle(vehicle);
771 const int num_nodes = path_.size();
772 FillPathTravels(path_);
773 {
774 const int index = dimension_->GetPreTravelEvaluatorOfVehicle(vehicle);
775 if (index == -1) {
776 travel_bounds_.pre_travels.assign(num_nodes - 1, 0);
777 } else {
779 &travel_bounds_.pre_travels);
780 }
781 }
782 {
783 const int index = dimension_->GetPostTravelEvaluatorOfVehicle(vehicle);
784 if (index == -1) {
785 travel_bounds_.post_travels.assign(num_nodes - 1, 0);
786 } else {
788 &travel_bounds_.post_travels);
789 }
790 }
791 // The last travel might not be fixed: in that case, relax its information.
792 if (!model_->NextVar(path_[num_nodes - 2])->Bound()) {
793 travel_bounds_.min_travels.back() = 0;
794 travel_bounds_.max_travels.back() = kint64max;
795 travel_bounds_.pre_travels.back() = 0;
796 travel_bounds_.post_travels.back() = 0;
797 }
798
799 // Fill tasks from path, break intervals, and break constraints.
800 tasks_.Clear();
801 AppendTasksFromPath(path_, travel_bounds_, *dimension_, &tasks_);
802 tasks_.num_chain_tasks = tasks_.start_min.size();
804 &tasks_);
805 tasks_.distance_duration =
806 dimension_->GetBreakDistanceDurationOfVehicle(vehicle);
807
808 // Do the actual reasoning, no need to continue if infeasible.
809 if (!disjunctive_propagator_.Propagate(&tasks_)) solver()->Fail();
810
811 // Make task translators to help set new bounds of CP variables.
812 task_translators_.clear();
813 for (int i = 0; i < num_nodes; ++i) {
814 const int64 before_visit =
815 (i == 0) ? 0 : travel_bounds_.post_travels[i - 1];
816 const int64 after_visit =
817 (i == num_nodes - 1) ? 0 : travel_bounds_.pre_travels[i];
818 task_translators_.emplace_back(dimension_->CumulVar(path_[i]), before_visit,
819 after_visit);
820 if (i == num_nodes - 1) break;
821 task_translators_.emplace_back(); // Dummy translator for travel tasks.
822 }
823 for (IntervalVar* interval :
824 dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
825 if (!interval->MustBePerformed()) continue;
826 task_translators_.emplace_back(interval);
827 }
828
829 // Push new bounds to CP variables.
830 const int num_tasks = tasks_.start_min.size();
831 for (int task = 0; task < num_tasks; ++task) {
832 task_translators_[task].SetStartMin(tasks_.start_min[task]);
833 task_translators_[task].SetStartMax(tasks_.start_max[task]);
834 task_translators_[task].SetDurationMin(tasks_.duration_min[task]);
835 task_translators_[task].SetEndMin(tasks_.end_min[task]);
836 task_translators_[task].SetEndMax(tasks_.end_max[task]);
837 }
838
839 // Reasoning on slack variables: when intervals must be inside an arc,
840 // that arc's slack must be large enough to accommodate for those.
841 // TODO(user): Make a version more efficient than O(n^2).
842 if (dimension_->GetBreakIntervalsOfVehicle(vehicle).empty()) return;
843 // If the last arc of the path was not bound, do not change slack.
844 const int64 last_bound_arc =
845 num_nodes - 2 - (model_->NextVar(path_[num_nodes - 2])->Bound() ? 0 : 1);
846 for (int i = 0; i <= last_bound_arc; ++i) {
847 const int64 arc_start_max =
848 CapSub(dimension_->CumulVar(path_[i])->Max(),
849 i > 0 ? travel_bounds_.post_travels[i - 1] : 0);
850 const int64 arc_end_min =
851 CapAdd(dimension_->CumulVar(path_[i + 1])->Min(),
852 i < num_nodes - 2 ? travel_bounds_.pre_travels[i + 1] : 0);
853 int64 total_break_inside_arc = 0;
854 for (IntervalVar* interval :
855 dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
856 if (!interval->MustBePerformed()) continue;
857 const int64 interval_start_max = interval->StartMax();
858 const int64 interval_end_min = interval->EndMin();
859 const int64 interval_duration_min = interval->DurationMin();
860 // If interval cannot end before the arc's from node and
861 // cannot start after the 'to' node, then it must be inside the arc.
862 if (arc_start_max < interval_end_min &&
863 interval_start_max < arc_end_min) {
864 total_break_inside_arc += interval_duration_min;
865 }
866 }
867 dimension_->SlackVar(path_[i])->SetMin(total_break_inside_arc);
868 }
869 // Reasoning on optional intervals.
870 // TODO(user): merge this with energy-based reasoning.
871 // If there is no optional interval, skip the rest of this function.
872 {
873 bool has_optional = false;
874 for (const IntervalVar* interval :
875 dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
876 if (interval->MayBePerformed() && !interval->MustBePerformed()) {
877 has_optional = true;
878 break;
879 }
880 }
881 if (!has_optional) return;
882 }
883 const std::vector<IntervalVar*>& break_intervals =
884 dimension_->GetBreakIntervalsOfVehicle(vehicle);
885 for (int pos = 0; pos < num_nodes - 1; ++pos) {
886 const int64 current_slack_max = dimension_->SlackVar(path_[pos])->Max();
887 const int64 visit_start_offset =
888 pos > 0 ? travel_bounds_.post_travels[pos - 1] : 0;
889 const int64 visit_start_max =
890 CapSub(dimension_->CumulVar(path_[pos])->Max(), visit_start_offset);
891 const int64 visit_end_offset =
892 (pos < num_nodes - 1) ? travel_bounds_.pre_travels[pos] : 0;
893 const int64 visit_end_min =
894 CapAdd(dimension_->CumulVar(path_[pos])->Min(), visit_end_offset);
895
896 for (IntervalVar* interval : break_intervals) {
897 if (!interval->MayBePerformed()) continue;
898 const bool interval_is_performed = interval->MustBePerformed();
899 const int64 interval_start_max = interval->StartMax();
900 const int64 interval_end_min = interval->EndMin();
901 const int64 interval_duration_min = interval->DurationMin();
902 // When interval cannot fit inside current arc,
903 // do disjunctive reasoning on full arc.
904 if (pos < num_nodes - 1 && interval_duration_min > current_slack_max) {
905 // The arc lasts from CumulVar(path_[pos]) - post_travel_[pos] to
906 // CumulVar(path_[pos+1]) + pre_travel_[pos+1].
907 const int64 arc_start_offset =
908 pos > 0 ? travel_bounds_.post_travels[pos - 1] : 0;
909 const int64 arc_start_max = visit_start_max;
910 const int64 arc_end_offset =
911 (pos < num_nodes - 2) ? travel_bounds_.pre_travels[pos + 1] : 0;
912 const int64 arc_end_min =
913 CapAdd(dimension_->CumulVar(path_[pos + 1])->Min(), arc_end_offset);
914 // Interval not before.
915 if (arc_start_max < interval_end_min) {
916 interval->SetStartMin(arc_end_min);
917 if (interval_is_performed) {
918 dimension_->CumulVar(path_[pos + 1])
919 ->SetMax(CapSub(interval_start_max, arc_end_offset));
920 }
921 }
922 // Interval not after.
923 if (interval_start_max < arc_end_min) {
924 interval->SetEndMax(arc_start_max);
925 if (interval_is_performed) {
926 dimension_->CumulVar(path_[pos])
927 ->SetMin(CapSub(interval_end_min, arc_start_offset));
928 }
929 }
930 continue;
931 }
932 // Interval could fit inside arc: do disjunctive reasoning between
933 // interval and visit.
934 // Interval not before.
935 if (visit_start_max < interval_end_min) {
936 interval->SetStartMin(visit_end_min);
937 if (interval_is_performed) {
938 dimension_->CumulVar(path_[pos])
939 ->SetMax(CapSub(interval_start_max, visit_end_offset));
940 }
941 }
942 // Interval not after.
943 if (interval_start_max < visit_end_min) {
944 interval->SetEndMax(visit_start_max);
945 if (interval_is_performed) {
946 dimension_->CumulVar(path_[pos])
947 ->SetMin(CapAdd(interval_end_min, visit_start_offset));
948 }
949 }
950 }
951 }
952}
953
954namespace {
955class VehicleBreaksFilter : public BasePathFilter {
956 public:
957 VehicleBreaksFilter(const RoutingModel& routing_model,
958 const RoutingDimension& dimension);
959 std::string DebugString() const override { return "VehicleBreaksFilter"; }
960 bool AcceptPath(int64 path_start, int64 chain_start,
961 int64 chain_end) override;
962
963 private:
964 // Fills path_ with the path of vehicle, start to end.
965 void FillPathOfVehicle(int64 vehicle);
966 std::vector<int64> path_;
967 // Handles to model.
968 const RoutingModel& model_;
969 const RoutingDimension& dimension_;
970 // Strong energy-based filtering algorithm.
971 DisjunctivePropagator disjunctive_propagator_;
972 DisjunctivePropagator::Tasks tasks_;
973 // Used to check whether propagation changed a vector.
974 std::vector<int64> old_start_min_;
975 std::vector<int64> old_start_max_;
976 std::vector<int64> old_end_min_;
977 std::vector<int64> old_end_max_;
978
979 std::vector<int> start_to_vehicle_;
980 TravelBounds travel_bounds_;
981};
982
983VehicleBreaksFilter::VehicleBreaksFilter(const RoutingModel& routing_model,
984 const RoutingDimension& dimension)
985 : BasePathFilter(routing_model.Nexts(),
986 routing_model.Size() + routing_model.vehicles()),
987 model_(routing_model),
988 dimension_(dimension) {
989 DCHECK(dimension_.HasBreakConstraints());
990 start_to_vehicle_.resize(Size(), -1);
991 for (int i = 0; i < routing_model.vehicles(); ++i) {
992 start_to_vehicle_[routing_model.Start(i)] = i;
993 }
994}
995
996void VehicleBreaksFilter::FillPathOfVehicle(int64 vehicle) {
997 path_.clear();
998 int current = model_.Start(vehicle);
999 while (!model_.IsEnd(current)) {
1000 path_.push_back(current);
1001 current = GetNext(current);
1002 }
1003 path_.push_back(current);
1004}
1005
1006bool VehicleBreaksFilter::AcceptPath(int64 path_start, int64 chain_start,
1007 int64 chain_end) {
1008 const int vehicle = start_to_vehicle_[path_start];
1009 if (dimension_.GetBreakIntervalsOfVehicle(vehicle).empty() &&
1010 dimension_.GetBreakDistanceDurationOfVehicle(vehicle).empty()) {
1011 return true;
1012 }
1013 // Fill path and pre/post travel information.
1014 FillPathOfVehicle(vehicle);
1015 FillTravelBoundsOfVehicle(vehicle, path_, dimension_, &travel_bounds_);
1016 // Fill tasks from path, forbidden intervals, breaks and break constraints.
1017 tasks_.Clear();
1018 AppendTasksFromPath(path_, travel_bounds_, dimension_, &tasks_);
1019 tasks_.num_chain_tasks = tasks_.start_min.size();
1021 &tasks_);
1022 // Add forbidden intervals only if a node has some.
1023 tasks_.forbidden_intervals.clear();
1024 if (std::any_of(path_.begin(), path_.end(), [this](int64 node) {
1025 return dimension_.forbidden_intervals()[node].NumIntervals() > 0;
1026 })) {
1027 tasks_.forbidden_intervals.assign(tasks_.start_min.size(), nullptr);
1028 for (int i = 0; i < path_.size(); ++i) {
1029 tasks_.forbidden_intervals[2 * i] =
1030 &(dimension_.forbidden_intervals()[path_[i]]);
1031 }
1032 }
1033 // Max distance duration constraint.
1034 tasks_.distance_duration =
1035 dimension_.GetBreakDistanceDurationOfVehicle(vehicle);
1036
1037 // Reduce bounds until failure or fixed point is reached.
1038 // We set a maximum amount of iterations to avoid slow propagation.
1039 bool is_feasible = true;
1040 int maximum_num_iterations = 8;
1041 while (--maximum_num_iterations >= 0) {
1042 old_start_min_ = tasks_.start_min;
1043 old_start_max_ = tasks_.start_max;
1044 old_end_min_ = tasks_.end_min;
1045 old_end_max_ = tasks_.end_max;
1046 is_feasible = disjunctive_propagator_.Propagate(&tasks_);
1047 if (!is_feasible) break;
1048 // If fixed point reached, stop.
1049 if ((old_start_min_ == tasks_.start_min) &&
1050 (old_start_max_ == tasks_.start_max) &&
1051 (old_end_min_ == tasks_.end_min) && (old_end_max_ == tasks_.end_max)) {
1052 break;
1053 }
1054 }
1055 return is_feasible;
1056}
1057
1058} // namespace
1059
1061 const RoutingModel& routing_model, const RoutingDimension& dimension) {
1062 return routing_model.solver()->RevAlloc(
1063 new VehicleBreaksFilter(routing_model, dimension));
1064}
1065
1066} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
A constraint is the main modeling object.
A Demon is the base element of a propagation queue.
bool EdgeFinding(Tasks *tasks)
Does edge-finding deductions on all tasks.
bool Precedences(Tasks *tasks)
Propagates the deductions from the chain of precedences, if there is one.
bool DistanceDuration(Tasks *tasks)
Propagates distance_duration constraints, if any.
bool MirrorTasks(Tasks *tasks)
Transforms the problem with a time symmetry centered in 0.
bool ForbiddenIntervals(Tasks *tasks)
Tasks might have holes in their domain, this enforces such holes.
bool Propagate(Tasks *tasks)
Computes new bounds for all tasks, returns false if infeasible.
bool DetectablePrecedencesWithChain(Tasks *tasks)
Does detectable precedences deductions on tasks in the chain precedence, taking the time windows of n...
bool ChainSpanMinDynamic(Tasks *tasks)
Computes a lower bound of the span of the chain, taking into account only the first nonchain task.
bool ChainSpanMin(Tasks *tasks)
Propagates a lower bound of the chain span, end[num_chain_tasks] - start[0], to span_min.
void Post() override
This method is called when the constraint is processed by the solver.
void InitialPropagate() override
This method performs the initial propagation of the constraint.
GlobalVehicleBreaksConstraint(const RoutingDimension *dimension)
virtual void SetMax(int64 m)=0
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual void SetMin(int64 m)=0
virtual int64 Max() const =0
virtual int64 Min() const =0
virtual void WhenRange(Demon *d)=0
Attach a demon that will watch the min or the max of the expression.
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
Interval variables are often used in scheduling.
virtual int64 StartMax() const =0
virtual int64 DurationMax() const =0
virtual int64 EndMax() const =0
virtual bool MustBePerformed() const =0
These methods query, set, and watch the performed status of the interval var.
virtual int64 StartMin() const =0
These methods query, set, and watch the start position of the interval var.
virtual int64 EndMin() const =0
These methods query, set, and watch the end position of the interval var.
virtual int64 DurationMin() const =0
These methods query, set, and watch the duration of the interval var.
void EnqueueDelayedDemon(Demon *const d)
This method pushes the demon onto the propagation queue.
Dimensions represent quantities accumulated at nodes along the routes.
Definition: routing.h:2368
IntVar * CumulVar(int64 index) const
Get the cumul, transit and slack variables for the given node (given as int64 var index).
Definition: routing.h:2386
const std::vector< std::pair< int64, int64 > > & GetBreakDistanceDurationOfVehicle(int vehicle) const
Returns the pairs (distance, duration) specified by break distance constraints.
Definition: routing.cc:6939
const std::vector< IntVar * > & cumuls() const
Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by i...
Definition: routing.h:2394
const RoutingModel::TransitCallback2 & transit_evaluator(int vehicle) const
Returns the callback evaluating the transit value between two node indices for a given vehicle.
Definition: routing.h:2449
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
Definition: routing.cc:6900
IntVar * SlackVar(int64 index) const
Definition: routing.h:2389
int GetPreTravelEvaluatorOfVehicle(int vehicle) const
!defined(SWIGPYTHON)
Definition: routing.cc:6911
RoutingModel * model() const
Returns the model on which the dimension was created.
Definition: routing.h:2372
const std::vector< IntervalVar * > & GetBreakIntervalsOfVehicle(int vehicle) const
Returns the break intervals set by SetBreakIntervalsOfVehicle().
Definition: routing.cc:6904
IntVar * FixedTransitVar(int64 index) const
Definition: routing.h:2388
const std::vector< SortedDisjointIntervalList > & forbidden_intervals() const
Returns forbidden intervals for each node.
Definition: routing.h:2400
int GetPostTravelEvaluatorOfVehicle(int vehicle) const
Definition: routing.cc:6917
Solver * solver() const
Returns the underlying constraint solver.
Definition: routing.h:1327
const TransitCallback2 & TransitCallback(int callback_index) const
Definition: routing.h:413
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
Definition: routing.h:1182
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
Definition: routing.h:1207
const std::vector< IntVar * > & Nexts() const
Returns all next variables of the model, such that Nexts(i) is the next variable of the node correspo...
Definition: routing.h:1200
int vehicles() const
Returns the number of vehicle routes in the model.
Definition: routing.h:1345
IntVar * VehicleVar(int64 index) const
Returns the vehicle variable of the node corresponding to index.
Definition: routing.h:1222
int64 Start(int vehicle) const
Model inspection.
Definition: routing.h:1180
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Definition: routing.h:1186
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
T * RevAlloc(T *object)
Registers the given object as being reversible.
void GetEventsWithOptionalEnvelopeGreaterThan(IntegerType target_envelope, int *critical_event, int *optional_event, IntegerType *available_energy) const
Definition: theta_tree.cc:189
void AddOrUpdateOptionalEvent(int event, IntegerType initial_envelope_opt, IntegerType energy_max)
Definition: theta_tree.cc:124
void AddOrUpdateEvent(int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max)
Definition: theta_tree.cc:111
GRBmodel * model
static const int64 kint64max
int64_t int64
static const int64 kint64min
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
void AppendTasksFromPath(const std::vector< int64 > &path, const TravelBounds &travel_bounds, const RoutingDimension &dimension, DisjunctivePropagator::Tasks *tasks)
IntVarLocalSearchFilter * MakeVehicleBreaksFilter(const RoutingModel &routing_model, const RoutingDimension &dimension)
int64 CapSub(int64 x, int64 y)
void FillTravelBoundsOfVehicle(int vehicle, const std::vector< int64 > &path, const RoutingDimension &dimension, TravelBounds *travel_bounds)
void AppendTasksFromIntervals(const std::vector< IntervalVar * > &intervals, DisjunctivePropagator::Tasks *tasks)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
void FillPathEvaluation(const std::vector< int64 > &path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64 > *values)
Definition: routing.cc:6215
int index
Definition: pack.cc:508
int64 time
Definition: resource.cc:1683
IntervalVar * interval
Definition: resource.cc:98
Rev< int64 > start_max
Rev< int64 > start_min
A structure to hold tasks described by their features.
Definition: routing.h:1961
std::vector< const SortedDisjointIntervalList * > forbidden_intervals
Definition: routing.h:1970
std::vector< std::pair< int64, int64 > > distance_duration
Definition: routing.h:1971
std::vector< int64 > max_travels
Definition: routing.h:2033
std::vector< int64 > min_travels
Definition: routing.h:2032
std::vector< int64 > post_travels
Definition: routing.h:2035
std::vector< int64 > pre_travels
Definition: routing.h:2034