OR-Tools  8.2
intervals.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/intervals.h"
15 
16 #include <memory>
17 
18 #include "ortools/sat/integer.h"
19 #include "ortools/util/sort.h"
20 
21 namespace operations_research {
22 namespace sat {
23 
24 IntervalVariable IntervalsRepository::CreateInterval(IntegerVariable start,
25  IntegerVariable end,
26  IntegerVariable size,
27  IntegerValue fixed_size,
28  LiteralIndex is_present) {
30  size == kNoIntegerVariable
31  ? AffineExpression(fixed_size)
32  : AffineExpression(size),
33  is_present, /*add_linear_relation=*/true);
34 }
35 
37  AffineExpression end,
38  AffineExpression size,
39  LiteralIndex is_present,
40  bool add_linear_relation) {
41  // Create the interval.
42  const IntervalVariable i(starts_.size());
43  starts_.push_back(start);
44  ends_.push_back(end);
45  sizes_.push_back(size);
46  is_present_.push_back(is_present);
47 
48  std::vector<Literal> enforcement_literals;
49  if (is_present != kNoLiteralIndex) {
50  enforcement_literals.push_back(Literal(is_present));
51  }
52 
53  if (add_linear_relation) {
54  LinearConstraintBuilder builder(model_, IntegerValue(0), IntegerValue(0));
55  builder.AddTerm(Start(i), IntegerValue(1));
56  builder.AddTerm(Size(i), IntegerValue(1));
57  builder.AddTerm(End(i), IntegerValue(-1));
58  LoadConditionalLinearConstraint(enforcement_literals, builder.Build(),
59  model_);
60  }
61 
62  return i;
63 }
64 
66  const std::vector<IntervalVariable>& tasks, Model* model)
67  : trail_(model->GetOrCreate<Trail>()),
68  integer_trail_(model->GetOrCreate<IntegerTrail>()),
69  precedences_(model->GetOrCreate<PrecedencesPropagator>()) {
70  starts_.clear();
71  ends_.clear();
72  minus_ends_.clear();
73  minus_starts_.clear();
74  sizes_.clear();
75  reason_for_presence_.clear();
76 
77  auto* repository = model->GetOrCreate<IntervalsRepository>();
78  for (const IntervalVariable i : tasks) {
79  if (repository->IsOptional(i)) {
80  reason_for_presence_.push_back(repository->PresenceLiteral(i).Index());
81  } else {
82  reason_for_presence_.push_back(kNoLiteralIndex);
83  }
84  sizes_.push_back(repository->Size(i));
85  starts_.push_back(repository->Start(i));
86  ends_.push_back(repository->End(i));
87  minus_starts_.push_back(repository->Start(i).Negated());
88  minus_ends_.push_back(repository->End(i).Negated());
89  }
90 
91  RegisterWith(model->GetOrCreate<GenericLiteralWatcher>());
92  InitSortedVectors();
94 }
95 
97  Model* model)
98  : trail_(model->GetOrCreate<Trail>()),
99  integer_trail_(model->GetOrCreate<IntegerTrail>()),
100  precedences_(model->GetOrCreate<PrecedencesPropagator>()) {
101  starts_.resize(num_tasks);
102  CHECK_EQ(NumTasks(), num_tasks);
103 }
104 
106  recompute_all_cache_ = true;
107  return true;
108 }
109 
111  const std::vector<int>& watch_indices) {
112  for (const int t : watch_indices) recompute_cache_[t] = true;
113  return true;
114 }
115 
117  // If there was an Untrail before, we need to refresh the cache so that
118  // we never have value from lower in the search tree.
119  //
120  // TODO(user): We could be smarter here, but then this is not visible in our
121  // cpu_profile since we call many times IncrementalPropagate() for each new
122  // decision, but just call Propagate() once after each Untrail().
123  if (level < previous_level_) {
124  recompute_all_cache_ = true;
125  }
126  previous_level_ = level;
127 }
128 
130  const int id = watcher->Register(this);
131  const int num_tasks = starts_.size();
132  for (int t = 0; t < num_tasks; ++t) {
133  watcher->WatchIntegerVariable(sizes_[t].var, id, t);
134  watcher->WatchIntegerVariable(starts_[t].var, id, t);
135  watcher->WatchIntegerVariable(ends_[t].var, id, t);
136  }
137  watcher->SetPropagatorPriority(id, 0);
138 
139  // Note that it is important to register with the integer_trail_ so we are
140  // ALWAYS called before any propagator that depends on this helper.
141  integer_trail_->RegisterReversibleClass(this);
142 }
143 
144 void SchedulingConstraintHelper::UpdateCachedValues(int t) {
145  recompute_cache_[t] = false;
146 
147  const IntegerValue dmin = integer_trail_->LowerBound(sizes_[t]);
148  const IntegerValue smin = integer_trail_->LowerBound(starts_[t]);
149  const IntegerValue smax = integer_trail_->UpperBound(starts_[t]);
150  const IntegerValue emin = integer_trail_->LowerBound(ends_[t]);
151  const IntegerValue emax = integer_trail_->UpperBound(ends_[t]);
152 
153  cached_duration_min_[t] = dmin;
154  cached_start_min_[t] = smin;
155  cached_negated_end_max_[t] = -emax;
156 
157  // Sometimes, for optional interval with non-optional bounds, the two
158  // part of the max here is not the same. We always consider the value assuming
159  // the interval is present.
160  cached_end_min_[t] = std::max(emin, smin + dmin);
161  cached_negated_start_max_[t] = -std::min(smax, emax - dmin);
162 
163  // Note that we use the cached value here for EndMin()/StartMax().
164  const IntegerValue new_shifted_start_min = EndMin(t) - dmin;
165  if (new_shifted_start_min != cached_shifted_start_min_[t]) {
166  recompute_shifted_start_min_ = true;
167  cached_shifted_start_min_[t] = new_shifted_start_min;
168  }
169  const IntegerValue new_negated_shifted_end_max = -(StartMax(t) + dmin);
170  if (new_negated_shifted_end_max != cached_negated_shifted_end_max_[t]) {
171  recompute_negated_shifted_end_max_ = true;
172  cached_negated_shifted_end_max_[t] = new_negated_shifted_end_max;
173  }
174 }
175 
177  const SchedulingConstraintHelper& other, absl::Span<const int> tasks) {
178  current_time_direction_ = other.current_time_direction_;
179 
180  const int num_tasks = tasks.size();
181  starts_.resize(num_tasks);
182  ends_.resize(num_tasks);
183  minus_ends_.resize(num_tasks);
184  minus_starts_.resize(num_tasks);
185  sizes_.resize(num_tasks);
186  reason_for_presence_.resize(num_tasks);
187  for (int i = 0; i < num_tasks; ++i) {
188  const int t = tasks[i];
189  starts_[i] = other.starts_[t];
190  ends_[i] = other.ends_[t];
191  minus_ends_[i] = other.minus_ends_[t];
192  minus_starts_[i] = other.minus_starts_[t];
193  sizes_[i] = other.sizes_[t];
194  reason_for_presence_[i] = other.reason_for_presence_[t];
195  }
196 
197  InitSortedVectors();
199 }
200 
201 void SchedulingConstraintHelper::InitSortedVectors() {
202  const int num_tasks = starts_.size();
203 
204  recompute_all_cache_ = true;
205  recompute_cache_.resize(num_tasks, true);
206 
207  cached_shifted_start_min_.resize(num_tasks);
208  cached_negated_shifted_end_max_.resize(num_tasks);
209  cached_duration_min_.resize(num_tasks);
210  cached_start_min_.resize(num_tasks);
211  cached_end_min_.resize(num_tasks);
212  cached_negated_start_max_.resize(num_tasks);
213  cached_negated_end_max_.resize(num_tasks);
214 
215  task_by_increasing_start_min_.resize(num_tasks);
216  task_by_increasing_end_min_.resize(num_tasks);
217  task_by_decreasing_start_max_.resize(num_tasks);
218  task_by_decreasing_end_max_.resize(num_tasks);
219  task_by_increasing_shifted_start_min_.resize(num_tasks);
220  task_by_negated_shifted_end_max_.resize(num_tasks);
221  for (int t = 0; t < num_tasks; ++t) {
222  task_by_increasing_start_min_[t].task_index = t;
223  task_by_increasing_end_min_[t].task_index = t;
224  task_by_decreasing_start_max_[t].task_index = t;
225  task_by_decreasing_end_max_[t].task_index = t;
226  task_by_increasing_shifted_start_min_[t].task_index = t;
227  task_by_negated_shifted_end_max_[t].task_index = t;
228  }
229 
230  recompute_shifted_start_min_ = true;
231  recompute_negated_shifted_end_max_ = true;
232 }
233 
235  bool is_forward) {
236  if (current_time_direction_ != is_forward) {
237  current_time_direction_ = is_forward;
238 
239  std::swap(starts_, minus_ends_);
240  std::swap(ends_, minus_starts_);
241 
242  std::swap(task_by_increasing_start_min_, task_by_decreasing_end_max_);
243  std::swap(task_by_increasing_end_min_, task_by_decreasing_start_max_);
244  std::swap(task_by_increasing_shifted_start_min_,
245  task_by_negated_shifted_end_max_);
246 
247  std::swap(cached_start_min_, cached_negated_end_max_);
248  std::swap(cached_end_min_, cached_negated_start_max_);
249  std::swap(cached_shifted_start_min_, cached_negated_shifted_end_max_);
250  std::swap(recompute_shifted_start_min_, recompute_negated_shifted_end_max_);
251  }
252  if (recompute_all_cache_) {
253  for (int t = 0; t < recompute_cache_.size(); ++t) {
254  UpdateCachedValues(t);
255  }
256  } else {
257  for (int t = 0; t < recompute_cache_.size(); ++t) {
258  if (recompute_cache_[t]) UpdateCachedValues(t);
259  }
260  }
261  recompute_all_cache_ = false;
262 }
263 
264 const std::vector<TaskTime>&
266  const int num_tasks = NumTasks();
267  for (int i = 0; i < num_tasks; ++i) {
268  TaskTime& ref = task_by_increasing_start_min_[i];
269  ref.time = StartMin(ref.task_index);
270  }
271  IncrementalSort(task_by_increasing_start_min_.begin(),
272  task_by_increasing_start_min_.end());
273  return task_by_increasing_start_min_;
274 }
275 
276 const std::vector<TaskTime>&
278  const int num_tasks = NumTasks();
279  for (int i = 0; i < num_tasks; ++i) {
280  TaskTime& ref = task_by_increasing_end_min_[i];
281  ref.time = EndMin(ref.task_index);
282  }
283  IncrementalSort(task_by_increasing_end_min_.begin(),
284  task_by_increasing_end_min_.end());
285  return task_by_increasing_end_min_;
286 }
287 
288 const std::vector<TaskTime>&
290  const int num_tasks = NumTasks();
291  for (int i = 0; i < num_tasks; ++i) {
292  TaskTime& ref = task_by_decreasing_start_max_[i];
293  ref.time = StartMax(ref.task_index);
294  }
295  IncrementalSort(task_by_decreasing_start_max_.begin(),
296  task_by_decreasing_start_max_.end(),
297  std::greater<TaskTime>());
298  return task_by_decreasing_start_max_;
299 }
300 
301 const std::vector<TaskTime>&
303  const int num_tasks = NumTasks();
304  for (int i = 0; i < num_tasks; ++i) {
305  TaskTime& ref = task_by_decreasing_end_max_[i];
306  ref.time = EndMax(ref.task_index);
307  }
308  IncrementalSort(task_by_decreasing_end_max_.begin(),
309  task_by_decreasing_end_max_.end(), std::greater<TaskTime>());
310  return task_by_decreasing_end_max_;
311 }
312 
313 const std::vector<TaskTime>&
315  if (recompute_shifted_start_min_) {
316  recompute_shifted_start_min_ = false;
317  const int num_tasks = NumTasks();
318  bool is_sorted = true;
319  IntegerValue previous = kMinIntegerValue;
320  for (int i = 0; i < num_tasks; ++i) {
321  TaskTime& ref = task_by_increasing_shifted_start_min_[i];
322  ref.time = ShiftedStartMin(ref.task_index);
323  is_sorted = is_sorted && ref.time >= previous;
324  previous = ref.time;
325  }
326  if (is_sorted) return task_by_increasing_shifted_start_min_;
327  IncrementalSort(task_by_increasing_shifted_start_min_.begin(),
328  task_by_increasing_shifted_start_min_.end());
329  }
330  return task_by_increasing_shifted_start_min_;
331 }
332 
333 // Produces a relaxed reason for StartMax(before) < EndMin(after).
335  int after) {
336  AddOtherReason(before);
337  AddOtherReason(after);
338 
339  std::vector<IntegerVariable> vars;
340 
341  // Reason for StartMax(before).
342  const IntegerValue smax_before = StartMax(before);
343  if (smax_before >= integer_trail_->UpperBound(starts_[before])) {
344  if (starts_[before].var != kNoIntegerVariable) {
345  vars.push_back(NegationOf(starts_[before].var));
346  }
347  } else {
348  if (ends_[before].var != kNoIntegerVariable) {
349  vars.push_back(NegationOf(ends_[before].var));
350  }
351  if (sizes_[before].var != kNoIntegerVariable) {
352  vars.push_back(sizes_[before].var);
353  }
354  }
355 
356  // Reason for EndMin(after);
357  const IntegerValue emin_after = EndMin(after);
358  if (emin_after <= integer_trail_->LowerBound(ends_[after])) {
359  if (ends_[after].var != kNoIntegerVariable) {
360  vars.push_back(ends_[after].var);
361  }
362  } else {
363  if (starts_[after].var != kNoIntegerVariable) {
364  vars.push_back(starts_[after].var);
365  }
366  if (sizes_[after].var != kNoIntegerVariable) {
367  vars.push_back(sizes_[after].var);
368  }
369  }
370 
371  DCHECK_LT(smax_before, emin_after);
372  const IntegerValue slack = emin_after - smax_before - 1;
373  integer_trail_->AppendRelaxedLinearReason(
374  slack, std::vector<IntegerValue>(vars.size(), IntegerValue(1)), vars,
375  &integer_reason_);
376 }
377 
379  CHECK(other_helper_ == nullptr);
380  return integer_trail_->Enqueue(lit, literal_reason_, integer_reason_);
381 }
382 
384  int t, IntegerLiteral lit) {
385  if (IsAbsent(t)) return true;
386  AddOtherReason(t);
388  if (IsOptional(t)) {
389  return integer_trail_->ConditionalEnqueue(
390  PresenceLiteral(t), lit, &literal_reason_, &integer_reason_);
391  }
392  return integer_trail_->Enqueue(lit, literal_reason_, integer_reason_);
393 }
394 
395 // We also run directly the precedence propagator for this variable so that when
396 // we push an interval start for example, we have a chance to push its end.
397 bool SchedulingConstraintHelper::PushIntervalBound(int t, IntegerLiteral lit) {
398  if (!PushIntegerLiteralIfTaskPresent(t, lit)) return false;
399  if (IsAbsent(t)) return true;
400  if (!precedences_->PropagateOutgoingArcs(lit.var)) return false;
401  UpdateCachedValues(t);
402  return true;
403 }
404 
406  IntegerValue new_start_min) {
407  if (starts_[t].var == kNoIntegerVariable) {
408  if (new_start_min > starts_[t].constant) return ReportConflict();
409  return true;
410  }
411  return PushIntervalBound(t, starts_[t].GreaterOrEqual(new_start_min));
412 }
413 
415  IntegerValue new_end_max) {
416  if (ends_[t].var == kNoIntegerVariable) {
417  if (new_end_max < ends_[t].constant) return ReportConflict();
418  return true;
419  }
420  return PushIntervalBound(t, ends_[t].LowerOrEqual(new_end_max));
421 }
422 
424  DCHECK_NE(reason_for_presence_[t], kNoLiteralIndex);
425  DCHECK(!IsAbsent(t));
426 
427  AddOtherReason(t);
428 
429  if (IsPresent(t)) {
430  literal_reason_.push_back(Literal(reason_for_presence_[t]).Negated());
431  return ReportConflict();
432  }
434  integer_trail_->EnqueueLiteral(Literal(reason_for_presence_[t]).Negated(),
435  literal_reason_, integer_reason_);
436  return true;
437 }
438 
440  DCHECK_NE(reason_for_presence_[t], kNoLiteralIndex);
441  DCHECK(!IsPresent(t));
442 
443  AddOtherReason(t);
444 
445  if (IsAbsent(t)) {
446  literal_reason_.push_back(Literal(reason_for_presence_[t]));
447  return ReportConflict();
448  }
450  integer_trail_->EnqueueLiteral(Literal(reason_for_presence_[t]),
451  literal_reason_, integer_reason_);
452  return true;
453 }
454 
457  return integer_trail_->ReportConflict(literal_reason_, integer_reason_);
458 }
459 
461  GenericLiteralWatcher* watcher,
462  bool watch_start_max,
463  bool watch_end_max) const {
464  const int num_tasks = starts_.size();
465  for (int t = 0; t < num_tasks; ++t) {
466  watcher->WatchLowerBound(starts_[t], id);
467  watcher->WatchLowerBound(ends_[t], id);
468  watcher->WatchLowerBound(sizes_[t], id);
469  if (watch_start_max) {
470  watcher->WatchUpperBound(starts_[t], id);
471  }
472  if (watch_end_max) {
473  watcher->WatchUpperBound(ends_[t], id);
474  }
475  if (!IsPresent(t) && !IsAbsent(t)) {
476  watcher->WatchLiteral(Literal(reason_for_presence_[t]), id);
477  }
478  }
479 }
480 
481 void SchedulingConstraintHelper::AddOtherReason(int t) {
482  if (other_helper_ == nullptr || already_added_to_other_reasons_[t]) return;
483  already_added_to_other_reasons_[t] = true;
484  other_helper_->AddStartMaxReason(t, event_for_other_helper_);
485  other_helper_->AddEndMinReason(t, event_for_other_helper_ + 1);
486 }
487 
488 void SchedulingConstraintHelper::ImportOtherReasons() {
489  if (other_helper_ != nullptr) ImportOtherReasons(*other_helper_);
490 }
491 
492 void SchedulingConstraintHelper::ImportOtherReasons(
493  const SchedulingConstraintHelper& other_helper) {
494  literal_reason_.insert(literal_reason_.end(),
495  other_helper.literal_reason_.begin(),
496  other_helper.literal_reason_.end());
497  integer_reason_.insert(integer_reason_.end(),
498  other_helper.integer_reason_.begin(),
499  other_helper.integer_reason_.end());
500 }
501 
503  return absl::StrCat("t=", t, " is_present=", IsPresent(t),
504  " min_size=", SizeMin(t).value(), " start=[",
505  StartMin(t).value(), ",", StartMax(t).value(), "]",
506  " end=[", EndMin(t).value(), ",", EndMax(t).value(), "]");
507 }
508 
509 } // namespace sat
510 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
void push_back(const value_type &x)
void WatchLiteral(Literal l, int id, int watch_index=-1)
Definition: integer.h:1365
void WatchLowerBound(IntegerVariable var, int id, int watch_index=-1)
Definition: integer.h:1373
void WatchIntegerVariable(IntegerVariable i, int id, int watch_index=-1)
Definition: integer.h:1397
void WatchUpperBound(IntegerVariable var, int id, int watch_index=-1)
Definition: integer.h:1391
void SetPropagatorPriority(int id, int priority)
Definition: integer.cc:1962
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
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
void AppendRelaxedLinearReason(IntegerValue slack, absl::Span< const IntegerValue > coeffs, absl::Span< const IntegerVariable > vars, std::vector< IntegerLiteral > *reason) const
Definition: integer.cc:807
IntegerValue LowerBound(IntegerVariable i) const
Definition: integer.h:1300
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
void RegisterReversibleClass(ReversibleInterface *rev)
Definition: integer.h:833
AffineExpression End(IntervalVariable i) const
Definition: intervals.h:94
AffineExpression Start(IntervalVariable i) const
Definition: intervals.h:93
AffineExpression Size(IntervalVariable i) const
Definition: intervals.h:92
IntervalVariable CreateInterval(IntegerVariable start, IntegerVariable end, IntegerVariable size, IntegerValue fixed_size, LiteralIndex is_present)
Definition: intervals.cc:24
void AddTerm(IntegerVariable var, IntegerValue coeff)
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
bool PropagateOutgoingArcs(IntegerVariable var)
Definition: precedences.cc:96
ABSL_MUST_USE_RESULT bool PushIntegerLiteral(IntegerLiteral lit)
Definition: intervals.cc:378
const std::vector< TaskTime > & TaskByDecreasingEndMax()
Definition: intervals.cc:302
ABSL_MUST_USE_RESULT bool PushTaskAbsence(int t)
Definition: intervals.cc:423
SchedulingConstraintHelper(const std::vector< IntervalVariable > &tasks, Model *model)
Definition: intervals.cc:65
const std::vector< TaskTime > & TaskByIncreasingStartMin()
Definition: intervals.cc:265
void WatchAllTasks(int id, GenericLiteralWatcher *watcher, bool watch_start_max=true, bool watch_end_max=true) const
Definition: intervals.cc:460
bool IncrementalPropagate(const std::vector< int > &watch_indices) final
Definition: intervals.cc:110
const std::vector< TaskTime > & TaskByIncreasingEndMin()
Definition: intervals.cc:277
void ResetFromSubset(const SchedulingConstraintHelper &other, absl::Span< const int > tasks)
Definition: intervals.cc:176
ABSL_MUST_USE_RESULT bool PushIntegerLiteralIfTaskPresent(int t, IntegerLiteral lit)
Definition: intervals.cc:383
void RegisterWith(GenericLiteralWatcher *watcher)
Definition: intervals.cc:129
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
void ImportOtherReasons(const SchedulingConstraintHelper &other_helper)
Definition: intervals.cc:492
ABSL_MUST_USE_RESULT bool DecreaseEndMax(int t, IntegerValue new_start_max)
Definition: intervals.cc:414
const std::vector< TaskTime > & TaskByDecreasingStartMax()
Definition: intervals.cc:289
ABSL_MUST_USE_RESULT bool PushTaskPresence(int t)
Definition: intervals.cc:439
const std::vector< TaskTime > & TaskByIncreasingShiftedStartMin()
Definition: intervals.cc:314
void AddReasonForBeingBefore(int before, int after)
Definition: intervals.cc:334
void AddStartMaxReason(int t, IntegerValue upper_bound)
Definition: intervals.h:513
int64 value
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
std::function< int64(const Model &)> LowerBound(IntegerVariable v)
Definition: integer.h:1467
const LiteralIndex kNoLiteralIndex(-1)
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
void LoadConditionalLinearConstraint(const absl::Span< const Literal > enforcement_literals, const LinearConstraint &cst, Model *model)
Definition: integer_expr.h:572
const IntegerVariable kNoIntegerVariable(-1)
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
Definition: integer.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...
void IncrementalSort(int max_comparisons, Iterator begin, Iterator end, Compare comp=Compare{}, bool is_stable=false)
Definition: sort.h:46