OR-Tools  8.2
timetable.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
22#include "ortools/util/sort.h"
23
24namespace operations_research {
25namespace sat {
26
27void AddReservoirConstraint(std::vector<AffineExpression> times,
28 std::vector<IntegerValue> deltas,
29 std::vector<Literal> presences, int64 min_level,
30 int64 max_level, Model* model) {
31 // We only create a side if it can fail.
32 IntegerValue min_possible(0);
33 IntegerValue max_possible(0);
34 for (const IntegerValue d : deltas) {
35 if (d > 0) {
36 max_possible += d;
37 } else {
38 min_possible += d;
39 }
40 }
41 if (max_possible > max_level) {
42 model->TakeOwnership(new ReservoirTimeTabling(
43 times, deltas, presences, IntegerValue(max_level), model));
44 }
45 if (min_possible < min_level) {
46 for (IntegerValue& ref : deltas) ref = -ref;
47 model->TakeOwnership(new ReservoirTimeTabling(
48 times, deltas, presences, IntegerValue(-min_level), model));
49 }
50}
51
53 const std::vector<AffineExpression>& times,
54 const std::vector<IntegerValue>& deltas,
55 const std::vector<Literal>& presences, IntegerValue capacity, Model* model)
56 : times_(times),
57 deltas_(deltas),
58 presences_(presences),
59 capacity_(capacity),
60 assignment_(model->GetOrCreate<Trail>()->Assignment()),
61 integer_trail_(model->GetOrCreate<IntegerTrail>()) {
62 auto* watcher = model->GetOrCreate<GenericLiteralWatcher>();
63 const int id = watcher->Register(this);
64 const int num_events = times.size();
65 for (int e = 0; e < num_events; e++) {
66 if (deltas_[e] > 0) {
67 watcher->WatchUpperBound(times_[e].var, id);
68 watcher->WatchLiteral(presences_[e], id);
69 }
70 if (deltas_[e] < 0) {
71 watcher->WatchLowerBound(times_[e].var, id);
72 watcher->WatchLiteral(presences_[e].Negated(), id);
73 }
74 }
75 watcher->NotifyThatPropagatorMayNotReachFixedPointInOnePass(id);
76}
77
79 const int num_events = times_.size();
80 if (!BuildProfile()) return false;
81 for (int e = 0; e < num_events; e++) {
82 if (assignment_.LiteralIsFalse(presences_[e])) continue;
83
84 // For positive delta, we can maybe increase the min.
85 if (deltas_[e] > 0 && !TryToIncreaseMin(e)) return false;
86
87 // For negative delta, we can maybe decrease the max.
88 if (deltas_[e] < 0 && !TryToDecreaseMax(e)) return false;
89 }
90 return true;
91}
92
93// We compute the lowest possible profile at time t.
94//
95// TODO(user): If we have precedences between events, we should be able to do
96// more.
97bool ReservoirTimeTabling::BuildProfile() {
98 // Starts by copying the "events" in the profile and sort them by time.
99 profile_.clear();
100 const int num_events = times_.size();
101 profile_.emplace_back(kMinIntegerValue, IntegerValue(0)); // Sentinel.
102 for (int e = 0; e < num_events; e++) {
103 if (deltas_[e] > 0) {
104 // Only consider present event for positive delta.
105 if (!assignment_.LiteralIsTrue(presences_[e])) continue;
106 const IntegerValue ub = integer_trail_->UpperBound(times_[e]);
107 profile_.push_back({ub, deltas_[e]});
108 } else if (deltas_[e] < 0) {
109 // Only consider non-absent event for negative delta.
110 if (assignment_.LiteralIsFalse(presences_[e])) continue;
111 profile_.push_back({integer_trail_->LowerBound(times_[e]), deltas_[e]});
112 }
113 }
114 profile_.emplace_back(kMaxIntegerValue, IntegerValue(0)); // Sentinel.
115 std::sort(profile_.begin(), profile_.end());
116
117 // Accumulate delta and collapse entries.
118 int last = 0;
119 for (const ProfileRectangle& rect : profile_) {
120 if (rect.start == profile_[last].start) {
121 profile_[last].height += rect.height;
122 } else {
123 ++last;
124 profile_[last].start = rect.start;
125 profile_[last].height = rect.height + profile_[last - 1].height;
126 }
127 }
128 profile_.resize(last + 1);
129
130 // Conflict?
131 for (const ProfileRectangle& rect : profile_) {
132 if (rect.height <= capacity_) continue;
133 FillReasonForProfileAtGivenTime(rect.start);
134 return integer_trail_->ReportConflict(literal_reason_, integer_reason_);
135 }
136
137 return true;
138}
139
140// TODO(user): Minimize with how high the profile needs to be. We can also
141// remove from the reason the absence of a negative event provided that the
142// level zero min of the event is greater than t anyway.
143//
144// TODO(user): Make sure the code work with fixed time since pushing always
145// true/false literal to the reason is not completely supported.
146void ReservoirTimeTabling::FillReasonForProfileAtGivenTime(
147 IntegerValue t, int event_to_ignore) {
148 integer_reason_.clear();
149 literal_reason_.clear();
150 const int num_events = times_.size();
151 for (int e = 0; e < num_events; e++) {
152 if (e == event_to_ignore) continue;
153 if (deltas_[e] > 0) {
154 if (!assignment_.LiteralIsTrue(presences_[e])) continue;
155 if (integer_trail_->UpperBound(times_[e]) > t) continue;
156 integer_reason_.push_back(times_[e].LowerOrEqual(t));
157 literal_reason_.push_back(presences_[e].Negated());
158 } else if (deltas_[e] < 0) {
159 if (assignment_.LiteralIsFalse(presences_[e])) {
160 literal_reason_.push_back(presences_[e]);
161 } else if (integer_trail_->LowerBound(times_[e]) > t) {
162 integer_reason_.push_back(times_[e].GreaterOrEqual(t + 1));
163 }
164 }
165 }
166}
167
168// Note that a negative event will always be in the profile, even if its
169// presence is still not settled.
170bool ReservoirTimeTabling::TryToDecreaseMax(int event) {
171 CHECK_LT(deltas_[event], 0);
172 const IntegerValue start = integer_trail_->LowerBound(times_[event]);
173 const IntegerValue end = integer_trail_->UpperBound(times_[event]);
174
175 // We already tested for conflict in BuildProfile().
176 if (start == end) return true;
177
178 // Find the profile rectangle that overlaps the start of the given event.
179 // The sentinel prevents out of bound exceptions.
180 DCHECK(std::is_sorted(profile_.begin(), profile_.end()));
181 int rec_id =
182 std::upper_bound(profile_.begin(), profile_.end(), start,
183 [&](IntegerValue value, const ProfileRectangle& rect) {
184 return value < rect.start;
185 }) -
186 profile_.begin();
187 --rec_id;
188
189 bool push = false;
190 IntegerValue new_end = end;
191 for (; profile_[rec_id].start < end; ++rec_id) {
192 if (profile_[rec_id].height - deltas_[event] > capacity_) {
193 new_end = profile_[rec_id].start;
194 push = true;
195 break;
196 }
197 }
198 if (!push) return true;
199
200 // The reason is simply why the capacity at new_end (without the event)
201 // would overflow.
202 FillReasonForProfileAtGivenTime(new_end, event);
203
204 // Note(user): I don't think this is possible since it would have been
205 // detected at profile construction, but then, since the bound might have been
206 // updated, better be defensive.
207 if (new_end < start) {
208 integer_reason_.push_back(times_[event].GreaterOrEqual(new_end + 1));
209 return integer_trail_->ReportConflict(literal_reason_, integer_reason_);
210 }
211
212 // First, the task MUST be present, otherwise we have a conflict.
213 //
214 // TODO(user): We actually need to look after 'end' to potentially push the
215 // presence in more situation.
216 if (!assignment_.LiteralIsTrue(presences_[event])) {
217 integer_trail_->EnqueueLiteral(presences_[event], literal_reason_,
218 integer_reason_);
219 }
220
221 // Push new_end too. Note that we don't need the presence reason.
222 return integer_trail_->Enqueue(times_[event].LowerOrEqual(new_end),
223 literal_reason_, integer_reason_);
224}
225
226bool ReservoirTimeTabling::TryToIncreaseMin(int event) {
227 CHECK_GT(deltas_[event], 0);
228 const IntegerValue start = integer_trail_->LowerBound(times_[event]);
229 const IntegerValue end = integer_trail_->UpperBound(times_[event]);
230
231 // We already tested for conflict in BuildProfile().
232 if (start == end) return true;
233
234 // Find the profile rectangle containing the end of the given event.
235 // The sentinel prevents out of bound exceptions.
236 //
237 // TODO(user): If the task is no present, we should actually look at the
238 // maximum profile after end to maybe push its absence.
239 DCHECK(std::is_sorted(profile_.begin(), profile_.end()));
240 int rec_id =
241 std::upper_bound(profile_.begin(), profile_.end(), end,
242 [&](IntegerValue value, const ProfileRectangle& rect) {
243 return value < rect.start;
244 }) -
245 profile_.begin();
246 --rec_id;
247
248 bool push = false;
249 IntegerValue new_start = start;
250 if (profile_[rec_id].height + deltas_[event] > capacity_) {
251 if (!assignment_.LiteralIsTrue(presences_[event])) {
252 // Push to false since it wasn't part of the profile and cannot fit.
253 push = true;
254 new_start = end + 1;
255 } else if (profile_[rec_id].start < end) {
256 // It must be at end in this case.
257 push = true;
258 new_start = end;
259 }
260 }
261 if (!push) {
262 for (; profile_[rec_id].start > start; --rec_id) {
263 if (profile_[rec_id - 1].height + deltas_[event] > capacity_) {
264 push = true;
265 new_start = profile_[rec_id].start;
266 break;
267 }
268 }
269 }
270 if (!push) return true;
271
272 // The reason is simply the capacity at new_start - 1;
273 FillReasonForProfileAtGivenTime(new_start - 1, event);
274 return integer_trail_->ConditionalEnqueue(
275 presences_[event], times_[event].GreaterOrEqual(new_start),
276 &literal_reason_, &integer_reason_);
277}
278
280 const std::vector<AffineExpression>& demands, AffineExpression capacity,
281 IntegerTrail* integer_trail, SchedulingConstraintHelper* helper)
282 : num_tasks_(helper->NumTasks()),
283 demands_(demands),
284 capacity_(capacity),
285 integer_trail_(integer_trail),
286 helper_(helper) {
287 // Each task may create at most two profile rectangles. Such pattern appear if
288 // the profile is shaped like the Hanoi tower. The additional space is for
289 // both extremities and the sentinels.
290 profile_.reserve(2 * num_tasks_ + 4);
291
292 // Reversible set of tasks to consider for propagation.
293 forward_num_tasks_to_sweep_ = num_tasks_;
294 forward_tasks_to_sweep_.resize(num_tasks_);
295 backward_num_tasks_to_sweep_ = num_tasks_;
296 backward_tasks_to_sweep_.resize(num_tasks_);
297
298 num_profile_tasks_ = 0;
299 profile_tasks_.resize(num_tasks_);
300 positions_in_profile_tasks_.resize(num_tasks_);
301
302 // Reversible bounds and starting height of the profile.
303 starting_profile_height_ = IntegerValue(0);
304
305 for (int t = 0; t < num_tasks_; ++t) {
306 forward_tasks_to_sweep_[t] = t;
307 backward_tasks_to_sweep_[t] = t;
308 profile_tasks_[t] = t;
309 positions_in_profile_tasks_[t] = t;
310 }
311}
312
314 const int id = watcher->Register(this);
315 helper_->WatchAllTasks(id, watcher);
316 watcher->WatchUpperBound(capacity_.var, id);
317 for (int t = 0; t < num_tasks_; t++) {
318 watcher->WatchLowerBound(demands_[t].var, id);
319 }
320 watcher->RegisterReversibleInt(id, &forward_num_tasks_to_sweep_);
321 watcher->RegisterReversibleInt(id, &backward_num_tasks_to_sweep_);
322 watcher->RegisterReversibleInt(id, &num_profile_tasks_);
323
324 // Changing the times or pushing task absence migth have side effects on the
325 // other intervals, so we would need to be called again in this case.
327}
328
329// Note that we relly on being called again to reach a fixed point.
331 // This can fail if the profile exceeds the resource capacity.
332 if (!BuildProfile()) return false;
333
334 // Update the minimum start times.
335 if (!SweepAllTasks(/*is_forward=*/true)) return false;
336
337 // We reuse the same profile, but reversed, to update the maximum end times.
338 ReverseProfile();
339
340 // Update the maximum end times (reversed problem).
341 if (!SweepAllTasks(/*is_forward=*/false)) return false;
342
343 return true;
344}
345
346bool TimeTablingPerTask::BuildProfile() {
347 helper_->SynchronizeAndSetTimeDirection(true); // forward
348
349 // Update the set of tasks that contribute to the profile. Tasks that were
350 // contributing are still part of the profile so we only need to check the
351 // other tasks.
352 for (int i = num_profile_tasks_; i < num_tasks_; ++i) {
353 const int t1 = profile_tasks_[i];
354 if (helper_->IsPresent(t1) && helper_->StartMax(t1) < helper_->EndMin(t1)) {
355 // Swap values and positions.
356 const int t2 = profile_tasks_[num_profile_tasks_];
357 profile_tasks_[i] = t2;
358 profile_tasks_[num_profile_tasks_] = t1;
359 positions_in_profile_tasks_[t1] = num_profile_tasks_;
360 positions_in_profile_tasks_[t2] = i;
361 num_profile_tasks_++;
362 }
363 }
364
365 const auto& by_decreasing_start_max = helper_->TaskByDecreasingStartMax();
366 const auto& by_end_min = helper_->TaskByIncreasingEndMin();
367
368 // Build the profile.
369 // ------------------
370 profile_.clear();
371
372 // Start and height of the highest profile rectangle.
373 profile_max_height_ = kMinIntegerValue;
374 IntegerValue max_height_start = kMinIntegerValue;
375
376 // Add a sentinel to simplify the algorithm.
377 profile_.emplace_back(kMinIntegerValue, IntegerValue(0));
378
379 // Start and height of the currently built profile rectange.
380 IntegerValue current_start = kMinIntegerValue;
381 IntegerValue current_height = starting_profile_height_;
382
383 // Next start/end of the compulsory parts to be processed. Note that only the
384 // task for which IsInProfile() is true must be considered.
385 int next_start = num_tasks_ - 1;
386 int next_end = 0;
387 while (next_end < num_tasks_) {
388 const IntegerValue old_height = current_height;
389
390 IntegerValue t = by_end_min[next_end].time;
391 if (next_start >= 0) {
392 t = std::min(t, by_decreasing_start_max[next_start].time);
393 }
394
395 // Process the starting compulsory parts.
396 while (next_start >= 0 && by_decreasing_start_max[next_start].time == t) {
397 const int task_index = by_decreasing_start_max[next_start].task_index;
398 if (IsInProfile(task_index)) current_height += DemandMin(task_index);
399 --next_start;
400 }
401
402 // Process the ending compulsory parts.
403 while (next_end < num_tasks_ && by_end_min[next_end].time == t) {
404 const int task_index = by_end_min[next_end].task_index;
405 if (IsInProfile(task_index)) current_height -= DemandMin(task_index);
406 ++next_end;
407 }
408
409 // Insert a new profile rectangle if any.
410 if (current_height != old_height) {
411 profile_.emplace_back(current_start, old_height);
412 if (current_height > profile_max_height_) {
413 profile_max_height_ = current_height;
414 max_height_start = t;
415 }
416 current_start = t;
417 }
418 }
419
420 // Build the last profile rectangle.
421 DCHECK_GE(current_height, 0);
422 profile_.emplace_back(current_start, IntegerValue(0));
423
424 // Add a sentinel to simplify the algorithm.
425 profile_.emplace_back(kMaxIntegerValue, IntegerValue(0));
426
427 // Increase the capacity variable if required.
428 return IncreaseCapacity(max_height_start, profile_max_height_);
429}
430
431void TimeTablingPerTask::ReverseProfile() {
432 helper_->SynchronizeAndSetTimeDirection(false); // backward
433
434 // We keep the sentinels inchanged.
435 for (int i = 1; i + 1 < profile_.size(); ++i) {
436 profile_[i].start = -profile_[i + 1].start;
437 }
438 std::reverse(profile_.begin() + 1, profile_.end() - 1);
439}
440
441bool TimeTablingPerTask::SweepAllTasks(bool is_forward) {
442 // Tasks with a lower or equal demand will not be pushed.
443 const IntegerValue demand_threshold(
444 CapSub(CapacityMax().value(), profile_max_height_.value()));
445
446 // Select the correct members depending on the direction.
447 int& num_tasks =
448 is_forward ? forward_num_tasks_to_sweep_ : backward_num_tasks_to_sweep_;
449 std::vector<int>& tasks =
450 is_forward ? forward_tasks_to_sweep_ : backward_tasks_to_sweep_;
451
452 // TODO(user): On some problem, a big chunk of the time is spend just checking
453 // these conditions below because it requires indirect memory access to fetch
454 // the demand/size/presence/start ...
455 for (int i = num_tasks - 1; i >= 0; --i) {
456 const int t = tasks[i];
457 if (helper_->IsAbsent(t) ||
458 (helper_->IsPresent(t) && helper_->StartIsFixed(t))) {
459 // This tasks does not have to be considered for propagation in the rest
460 // of the sub-tree. Note that StartIsFixed() depends on the time
461 // direction, it is why we use two lists.
462 std::swap(tasks[i], tasks[--num_tasks]);
463 continue;
464 }
465
466 // Skip if demand is too low.
467 if (DemandMin(t) <= demand_threshold) {
468 if (DemandMax(t) == 0) {
469 // We can ignore this task for the rest of the subtree like above.
470 std::swap(tasks[i], tasks[--num_tasks]);
471 }
472
473 // This task does not have to be considered for propagation in this
474 // particular iteration, but maybe it does later.
475 continue;
476 }
477
478 // Skip if size is zero.
479 if (helper_->SizeMin(t) == 0) {
480 if (helper_->SizeMax(t) == 0) {
481 std::swap(tasks[i], tasks[--num_tasks]);
482 }
483 continue;
484 }
485
486 if (!SweepTask(t)) return false;
487 }
488
489 return true;
490}
491
492bool TimeTablingPerTask::SweepTask(int task_id) {
493 const IntegerValue start_max = helper_->StartMax(task_id);
494 const IntegerValue size_min = helper_->SizeMin(task_id);
495 const IntegerValue initial_start_min = helper_->StartMin(task_id);
496 const IntegerValue initial_end_min = helper_->EndMin(task_id);
497
498 IntegerValue new_start_min = initial_start_min;
499 IntegerValue new_end_min = initial_end_min;
500
501 // Find the profile rectangle that overlaps the minimum start time of task_id.
502 // The sentinel prevents out of bound exceptions.
503 DCHECK(std::is_sorted(profile_.begin(), profile_.end()));
504 int rec_id =
505 std::upper_bound(profile_.begin(), profile_.end(), new_start_min,
506 [&](IntegerValue value, const ProfileRectangle& rect) {
507 return value < rect.start;
508 }) -
509 profile_.begin();
510 --rec_id;
511
512 // A profile rectangle is in conflict with the task if its height exceeds
513 // conflict_height.
514 const IntegerValue conflict_height = CapacityMax() - DemandMin(task_id);
515
516 // True if the task is in conflict with at least one profile rectangle.
517 bool conflict_found = false;
518
519 // Last time point during which task_id was in conflict with a profile
520 // rectangle before being pushed.
521 IntegerValue last_initial_conflict = kMinIntegerValue;
522
523 // Push the task from left to right until it does not overlap any conflicting
524 // rectangle. Pushing the task may push the end of its compulsory part on the
525 // right but will not change its start. The main loop of the propagator will
526 // take care of rebuilding the profile with these possible changes and to
527 // propagate again in order to reach the timetabling consistency or to fail if
528 // the profile exceeds the resource capacity.
529 IntegerValue limit = std::min(start_max, new_end_min);
530 for (; profile_[rec_id].start < limit; ++rec_id) {
531 // If the profile rectangle is not conflicting, go to the next rectangle.
532 if (profile_[rec_id].height <= conflict_height) continue;
533
534 conflict_found = true;
535
536 // Compute the next minimum start and end times of task_id. The variables
537 // are not updated yet.
538 new_start_min = profile_[rec_id + 1].start; // i.e. profile_[rec_id].end
539 if (start_max < new_start_min) {
540 if (IsInProfile(task_id)) {
541 // Because the task is part of the profile, we cannot push it further.
542 new_start_min = start_max;
543 } else {
544 // We have a conflict or we can push the task absence. In both cases
545 // we don't need more than start_max + 1 in the explanation below.
546 new_start_min = start_max + 1;
547 }
548 }
549
550 new_end_min = std::max(new_end_min, new_start_min + size_min);
551 limit = std::min(start_max, new_end_min);
552
553 if (profile_[rec_id].start < initial_end_min) {
554 last_initial_conflict = std::min(new_start_min, initial_end_min) - 1;
555 }
556 }
557
558 if (!conflict_found) return true;
559
560 if (initial_start_min != new_start_min &&
561 !UpdateStartingTime(task_id, last_initial_conflict, new_start_min)) {
562 return false;
563 }
564
565 return true;
566}
567
568bool TimeTablingPerTask::UpdateStartingTime(int task_id, IntegerValue left,
569 IntegerValue right) {
570 helper_->ClearReason();
571
572 AddProfileReason(left, right);
573 if (capacity_.var != kNoIntegerVariable) {
574 helper_->MutableIntegerReason()->push_back(
575 integer_trail_->UpperBoundAsLiteral(capacity_.var));
576 }
577
578 // State of the task to be pushed.
579 helper_->AddEndMinReason(task_id, left + 1);
580 helper_->AddSizeMinReason(task_id, IntegerValue(1));
581 if (demands_[task_id].var != kNoIntegerVariable) {
582 helper_->MutableIntegerReason()->push_back(
583 integer_trail_->LowerBoundAsLiteral(demands_[task_id].var));
584 }
585
586 // Explain the increase of the minimum start and end times.
587 return helper_->IncreaseStartMin(task_id, right);
588}
589
590void TimeTablingPerTask::AddProfileReason(IntegerValue left,
591 IntegerValue right) {
592 for (int i = 0; i < num_profile_tasks_; ++i) {
593 const int t = profile_tasks_[i];
594
595 // Do not consider the task if it does not overlap for sure (left, right).
596 const IntegerValue start_max = helper_->StartMax(t);
597 if (right <= start_max) continue;
598 const IntegerValue end_min = helper_->EndMin(t);
599 if (end_min <= left) continue;
600
601 helper_->AddPresenceReason(t);
602 helper_->AddStartMaxReason(t, std::max(left, start_max));
603 helper_->AddEndMinReason(t, std::min(right, end_min));
604 if (demands_[t].var != kNoIntegerVariable) {
605 helper_->MutableIntegerReason()->push_back(
606 integer_trail_->LowerBoundAsLiteral(demands_[t].var));
607 }
608 }
609}
610
611bool TimeTablingPerTask::IncreaseCapacity(IntegerValue time,
612 IntegerValue new_min) {
613 if (new_min <= CapacityMin()) return true;
614
615 helper_->ClearReason();
616 AddProfileReason(time, time + 1);
617 if (capacity_.var == kNoIntegerVariable) {
618 return helper_->ReportConflict();
619 }
620
621 helper_->MutableIntegerReason()->push_back(
622 integer_trail_->UpperBoundAsLiteral(capacity_.var));
623 return helper_->PushIntegerLiteral(capacity_.GreaterOrEqual(new_min));
624}
625
626} // namespace sat
627} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK(condition)
Definition: base/logging.h:884
An Assignment is a variable -> domains mapping, used to report solutions to the user.
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
ABSL_MUST_USE_RESULT bool Enqueue(IntegerLiteral i_lit, absl::Span< const Literal > literal_reason, absl::Span< const IntegerLiteral > integer_reason)
Definition: integer.cc:989
IntegerLiteral LowerBoundAsLiteral(IntegerVariable i) const
Definition: integer.h:1330
bool ReportConflict(absl::Span< const Literal > literal_reason, absl::Span< const IntegerLiteral > integer_reason)
Definition: integer.h:810
void EnqueueLiteral(Literal literal, absl::Span< const Literal > literal_reason, absl::Span< const IntegerLiteral > integer_reason)
Definition: integer.cc:1087
IntegerValue UpperBound(IntegerVariable i) const
Definition: integer.h:1304
IntegerValue LowerBound(IntegerVariable i) const
Definition: integer.h:1300
IntegerLiteral UpperBoundAsLiteral(IntegerVariable i) const
Definition: integer.h:1335
ABSL_MUST_USE_RESULT bool ConditionalEnqueue(Literal lit, IntegerLiteral i_lit, std::vector< Literal > *literal_reason, std::vector< IntegerLiteral > *integer_reason)
Definition: integer.cc:996
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
ReservoirTimeTabling(const std::vector< AffineExpression > &times, const std::vector< IntegerValue > &deltas, const std::vector< Literal > &presences, IntegerValue capacity, Model *model)
Definition: timetable.cc:52
ABSL_MUST_USE_RESULT bool PushIntegerLiteral(IntegerLiteral lit)
Definition: intervals.cc:378
std::vector< IntegerLiteral > * MutableIntegerReason()
Definition: intervals.h:296
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
void AddEndMinReason(int t, IntegerValue lower_bound)
Definition: intervals.h:535
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 AddStartMaxReason(int t, IntegerValue upper_bound)
Definition: intervals.h:513
void RegisterWith(GenericLiteralWatcher *watcher)
Definition: timetable.cc:313
TimeTablingPerTask(const std::vector< AffineExpression > &demands, AffineExpression capacity, IntegerTrail *integer_trail, SchedulingConstraintHelper *helper)
Definition: timetable.cc:279
bool LiteralIsTrue(Literal literal) const
Definition: sat_base.h:150
bool LiteralIsFalse(Literal literal) const
Definition: sat_base.h:147
int64 value
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
int64_t int64
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
const IntegerVariable kNoIntegerVariable(-1)
std::function< void(Model *)> GreaterOrEqual(IntegerVariable v, int64 lb)
Definition: integer.h:1495
void AddReservoirConstraint(std::vector< AffineExpression > times, std::vector< IntegerValue > deltas, std::vector< Literal > presences, int64 min_level, int64 max_level, Model *model)
Definition: timetable.cc:27
std::function< void(Model *)> LowerOrEqual(IntegerVariable v, int64 ub)
Definition: integer.h:1509
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 CapSub(int64 x, int64 y)
int64 time
Definition: resource.cc:1683
int64 capacity
Rev< int64 > end_min
Rev< int64 > start_max
IntegerLiteral GreaterOrEqual(IntegerValue bound) const
Definition: integer.h:1285