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 
14 #include "ortools/sat/timetable.h"
15 
16 #include <algorithm>
17 #include <functional>
18 #include <memory>
19 
20 #include "ortools/base/int_type.h"
21 #include "ortools/base/logging.h"
22 #include "ortools/util/sort.h"
23 
24 namespace operations_research {
25 namespace sat {
26 
27 void 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.
97 bool 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.
146 void 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.
170 bool 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 
226 bool 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 
346 bool 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 
431 void 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 
441 bool 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 
492 bool 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 
568 bool 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 
590 void 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 
611 bool 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
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
std::vector< IntegerLiteral > * MutableIntegerReason()
Definition: intervals.h:296
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 kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
const IntegerVariable kNoIntegerVariable(-1)
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 *)> GreaterOrEqual(IntegerVariable v, int64 lb)
Definition: integer.h:1495
std::function< void(Model *)> LowerOrEqual(IntegerVariable v, int64 ub)
Definition: integer.h:1509
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