OR-Tools  8.2
sched_search.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 <cstring>
15#include <string>
16#include <vector>
17
18#include "absl/strings/str_format.h"
24
25namespace operations_research {
26namespace {
27int64 ValueToIndex(int64 value) { return value - 1; }
28
29int64 IndexToValue(int64 index) { return index + 1; }
30} // namespace
31
32// ----- SequenceVar -----
33
34// TODO(user): Add better class invariants, in particular checks
35// that ranked_first, ranked_last, and unperformed are truly disjoint.
36
38 const std::vector<IntervalVar*>& intervals,
39 const std::vector<IntVar*>& nexts,
40 const std::string& name)
42 intervals_(intervals),
43 nexts_(nexts),
44 previous_(nexts.size() + 1, -1) {
46}
47
49
51 return intervals_[index];
52}
53
54IntVar* SequenceVar::Next(int index) const { return nexts_[index]; }
55
56std::string SequenceVar::DebugString() const {
57 int64 hmin, hmax, dmin, dmax;
58 HorizonRange(&hmin, &hmax);
59 DurationRange(&dmin, &dmax);
60 int unperformed = 0;
61 int ranked = 0;
62 int not_ranked = 0;
63 ComputeStatistics(&ranked, &not_ranked, &unperformed);
64 return absl::StrFormat(
65 "%s(horizon = %d..%d, duration = %d..%d, not ranked = %d, ranked = %d, "
66 "nexts = [%s])",
67 name(), hmin, hmax, dmin, dmax, not_ranked, ranked,
68 JoinDebugStringPtr(nexts_, ", "));
69}
70
71void SequenceVar::Accept(ModelVisitor* const visitor) const {
72 visitor->VisitSequenceVariable(this);
73}
74
75void SequenceVar::DurationRange(int64* const dmin, int64* const dmax) const {
76 int64 dur_min = 0;
77 int64 dur_max = 0;
78 for (int i = 0; i < intervals_.size(); ++i) {
79 IntervalVar* const t = intervals_[i];
80 if (t->MayBePerformed()) {
81 if (t->MustBePerformed()) {
82 dur_min += t->DurationMin();
83 }
84 dur_max += t->DurationMax();
85 }
86 }
87 *dmin = dur_min;
88 *dmax = dur_max;
89}
90
91void SequenceVar::HorizonRange(int64* const hmin, int64* const hmax) const {
92 int64 hor_min = kint64max;
93 int64 hor_max = kint64min;
94 for (int i = 0; i < intervals_.size(); ++i) {
95 IntervalVar* const t = intervals_[i];
96 if (t->MayBePerformed()) {
97 IntervalVar* const t = intervals_[i];
98 hor_min = std::min(hor_min, t->StartMin());
99 hor_max = std::max(hor_max, t->EndMax());
100 }
101 }
102 *hmin = hor_min;
103 *hmax = hor_max;
104}
105
107 int64* const hmax) const {
108 absl::flat_hash_set<int> decided;
109 for (int i = 0; i < intervals_.size(); ++i) {
110 if (intervals_[i]->CannotBePerformed()) {
111 decided.insert(i);
112 }
113 }
114 int first = 0;
115 while (nexts_[first]->Bound()) {
116 first = nexts_[first]->Min();
117 if (first < nexts_.size()) {
118 decided.insert(ValueToIndex(first));
119 } else {
120 break;
121 }
122 }
123 if (first != nexts_.size()) {
124 UpdatePrevious();
125 int last = nexts_.size();
126 while (previous_[last] != -1) {
127 last = previous_[last];
128 decided.insert(ValueToIndex(last));
129 }
130 }
131 int64 hor_min = kint64max;
132 int64 hor_max = kint64min;
133 for (int i = 0; i < intervals_.size(); ++i) {
134 if (!gtl::ContainsKey(decided, i)) {
135 IntervalVar* const t = intervals_[i];
136 hor_min = std::min(hor_min, t->StartMin());
137 hor_max = std::max(hor_max, t->EndMax());
138 }
139 }
140 *hmin = hor_min;
141 *hmax = hor_max;
142}
143
144void SequenceVar::ComputeStatistics(int* const ranked, int* const not_ranked,
145 int* const unperformed) const {
146 *unperformed = 0;
147 for (int i = 0; i < intervals_.size(); ++i) {
148 if (intervals_[i]->CannotBePerformed()) {
149 (*unperformed)++;
150 }
151 }
152 *ranked = 0;
153 int first = 0;
154 while (first < nexts_.size() && nexts_[first]->Bound()) {
155 first = nexts_[first]->Min();
156 (*ranked)++;
157 }
158 if (first != nexts_.size()) {
159 UpdatePrevious();
160 int last = nexts_.size();
161 while (previous_[last] != -1) {
162 last = previous_[last];
163 (*ranked)++;
164 }
165 } else { // We counted the sentinel.
166 (*ranked)--;
167 }
168 *not_ranked = intervals_.size() - *ranked - *unperformed;
169}
170
171int SequenceVar::ComputeForwardFrontier() {
172 int first = 0;
173 while (first != nexts_.size() && nexts_[first]->Bound()) {
174 first = nexts_[first]->Min();
175 }
176 return first;
177}
178
179int SequenceVar::ComputeBackwardFrontier() {
180 UpdatePrevious();
181 int last = nexts_.size();
182 while (previous_[last] != -1) {
183 last = previous_[last];
184 }
185 return last;
186}
187
189 std::vector<int>* const possible_firsts,
190 std::vector<int>* const possible_lasts) {
191 possible_firsts->clear();
192 possible_lasts->clear();
193 absl::flat_hash_set<int> to_check;
194 for (int i = 0; i < intervals_.size(); ++i) {
195 if (intervals_[i]->MayBePerformed()) {
196 to_check.insert(i);
197 }
198 }
199 int first = 0;
200 while (nexts_[first]->Bound()) {
201 first = nexts_[first]->Min();
202 if (first == nexts_.size()) {
203 return;
204 }
205 to_check.erase(ValueToIndex(first));
206 }
207
208 IntVar* const forward_var = nexts_[first];
209 std::vector<int> candidates;
210 int64 smallest_start_max = kint64max;
211 int ssm_support = -1;
212 for (int64 i = forward_var->Min(); i <= forward_var->Max(); ++i) {
213 // TODO(user): use domain iterator.
214 if (i != 0 && i < IndexToValue(intervals_.size()) &&
215 intervals_[ValueToIndex(i)]->MayBePerformed() &&
216 forward_var->Contains(i)) {
217 const int candidate = ValueToIndex(i);
218 candidates.push_back(candidate);
219 if (intervals_[candidate]->MustBePerformed()) {
220 if (smallest_start_max > intervals_[candidate]->StartMax()) {
221 smallest_start_max = intervals_[candidate]->StartMax();
222 ssm_support = candidate;
223 }
224 }
225 }
226 }
227 for (int i = 0; i < candidates.size(); ++i) {
228 const int candidate = candidates[i];
229 if (candidate == ssm_support ||
230 intervals_[candidate]->EndMin() <= smallest_start_max) {
231 possible_firsts->push_back(candidate);
232 }
233 }
234
235 UpdatePrevious();
236 int last = nexts_.size();
237 while (previous_[last] != -1) {
238 last = previous_[last];
239 to_check.erase(ValueToIndex(last));
240 }
241
242 candidates.clear();
243 int64 biggest_end_min = kint64min;
244 int bem_support = -1;
245 for (const int candidate : to_check) {
246 if (nexts_[IndexToValue(candidate)]->Contains(last)) {
247 candidates.push_back(candidate);
248 if (intervals_[candidate]->MustBePerformed()) {
249 if (biggest_end_min < intervals_[candidate]->EndMin()) {
250 biggest_end_min = intervals_[candidate]->EndMin();
251 bem_support = candidate;
252 }
253 }
254 }
255 }
256
257 for (int i = 0; i < candidates.size(); ++i) {
258 const int candidate = candidates[i];
259 if (candidate == bem_support ||
260 intervals_[candidate]->StartMax() >= biggest_end_min) {
261 possible_lasts->push_back(candidate);
262 }
263 }
264}
265
266void SequenceVar::RankSequence(const std::vector<int>& rank_first,
267 const std::vector<int>& rank_last,
268 const std::vector<int>& unperformed) {
269 solver()->GetPropagationMonitor()->RankSequence(this, rank_first, rank_last,
270 unperformed);
271 // Mark unperformed.
272 for (const int value : unperformed) {
273 intervals_[value]->SetPerformed(false);
274 }
275 // Forward.
276 int forward = 0;
277 for (int i = 0; i < rank_first.size(); ++i) {
278 const int next = 1 + rank_first[i];
279 nexts_[forward]->SetValue(next);
280 forward = next;
281 }
282 // Backward.
283 int backward = IndexToValue(intervals_.size());
284 for (int i = 0; i < rank_last.size(); ++i) {
285 const int next = 1 + rank_last[i];
286 nexts_[next]->SetValue(backward);
287 backward = next;
288 }
289}
290
293 intervals_[index]->SetPerformed(true);
294 int forward_frontier = 0;
295 while (forward_frontier != nexts_.size() &&
296 nexts_[forward_frontier]->Bound()) {
297 forward_frontier = nexts_[forward_frontier]->Min();
298 if (forward_frontier == IndexToValue(index)) {
299 return;
300 }
301 }
302 DCHECK_LT(forward_frontier, nexts_.size());
303 nexts_[forward_frontier]->SetValue(IndexToValue(index));
304}
305
308 const int forward_frontier = ComputeForwardFrontier();
309 if (forward_frontier < nexts_.size()) {
310 nexts_[forward_frontier]->RemoveValue(IndexToValue(index));
311 }
312}
313
316 intervals_[index]->SetPerformed(true);
317 UpdatePrevious();
318 int backward_frontier = nexts_.size();
319 while (previous_[backward_frontier] != -1) {
320 backward_frontier = previous_[backward_frontier];
321 if (backward_frontier == IndexToValue(index)) {
322 return;
323 }
324 }
325 DCHECK_NE(backward_frontier, 0);
326 nexts_[IndexToValue(index)]->SetValue(backward_frontier);
327}
328
331 const int backward_frontier = ComputeBackwardFrontier();
332 nexts_[IndexToValue(index)]->RemoveValue(backward_frontier);
333}
334
335void SequenceVar::UpdatePrevious() const {
336 for (int i = 0; i < intervals_.size() + 2; ++i) {
337 previous_[i] = -1;
338 }
339 for (int i = 0; i < nexts_.size(); ++i) {
340 if (nexts_[i]->Bound()) {
341 previous_[nexts_[i]->Min()] = i;
342 }
343 }
344}
345
346void SequenceVar::FillSequence(std::vector<int>* const rank_first,
347 std::vector<int>* const rank_last,
348 std::vector<int>* const unperformed) const {
349 CHECK(rank_first != nullptr);
350 CHECK(rank_last != nullptr);
351 CHECK(unperformed != nullptr);
352 rank_first->clear();
353 rank_last->clear();
354 unperformed->clear();
355 for (int i = 0; i < intervals_.size(); ++i) {
356 if (intervals_[i]->CannotBePerformed()) {
357 unperformed->push_back(i);
358 }
359 }
360 int first = 0;
361 while (nexts_[first]->Bound()) {
362 first = nexts_[first]->Min();
363 if (first < nexts_.size()) {
364 rank_first->push_back(ValueToIndex(first));
365 } else {
366 break;
367 }
368 }
369 if (first != nexts_.size()) {
370 UpdatePrevious();
371 int last = nexts_.size();
372 while (previous_[last] != -1) {
373 last = previous_[last];
374 rank_last->push_back(ValueToIndex(last));
375 }
376 }
377}
378
379// ----- Decisions and DecisionBuilders on interval vars -----
380
381// TODO(user) : treat optional intervals
382// TODO(user) : Call DecisionVisitor and pass name of variable
383namespace {
384//
385// Forward scheduling.
386//
387class ScheduleOrPostpone : public Decision {
388 public:
389 ScheduleOrPostpone(IntervalVar* const var, int64 est, int64* const marker)
390 : var_(var), est_(est), marker_(marker) {}
391 ~ScheduleOrPostpone() override {}
392
393 void Apply(Solver* const s) override {
394 var_->SetPerformed(true);
395 if (est_.Value() < var_->StartMin()) {
396 est_.SetValue(s, var_->StartMin());
397 }
398 var_->SetStartRange(est_.Value(), est_.Value());
399 }
400
401 void Refute(Solver* const s) override {
402 s->SaveAndSetValue(marker_, est_.Value());
403 }
404
405 void Accept(DecisionVisitor* const visitor) const override {
406 CHECK(visitor != nullptr);
407 visitor->VisitScheduleOrPostpone(var_, est_.Value());
408 }
409
410 std::string DebugString() const override {
411 return absl::StrFormat("ScheduleOrPostpone(%s at %d)", var_->DebugString(),
412 est_.Value());
413 }
414
415 private:
416 IntervalVar* const var_;
417 NumericalRev<int64> est_;
418 int64* const marker_;
419};
420
421class SetTimesForward : public DecisionBuilder {
422 public:
423 explicit SetTimesForward(const std::vector<IntervalVar*>& vars)
424 : vars_(vars), markers_(vars.size(), kint64min) {}
425
426 ~SetTimesForward() override {}
427
428 Decision* Next(Solver* const s) override {
429 int64 best_est = kint64max;
430 int64 best_lct = kint64max;
431 int support = -1;
432 // We are looking for the interval that has the smallest start min
433 // (tie break with smallest end max) and is not postponed. And
434 // you're going to schedule that interval at its start min.
435 for (int i = 0; i < vars_.size(); ++i) {
436 IntervalVar* const v = vars_[i];
437 if (v->MayBePerformed() && v->StartMax() != v->StartMin() &&
438 !IsPostponed(i) &&
439 (v->StartMin() < best_est ||
440 (v->StartMin() == best_est && v->EndMax() < best_lct))) {
441 best_est = v->StartMin();
442 best_lct = v->EndMax();
443 support = i;
444 }
445 }
446 // TODO(user) : remove this crude quadratic loop with
447 // reversibles range reduction.
448 if (support == -1) { // All intervals are either fixed or postponed.
449 UnperformPostponedTaskBefore(kint64max);
450 return nullptr;
451 }
452 UnperformPostponedTaskBefore(best_est);
453 return s->RevAlloc(
454 new ScheduleOrPostpone(vars_[support], best_est, &markers_[support]));
455 }
456
457 std::string DebugString() const override { return "SetTimesForward()"; }
458
459 void Accept(ModelVisitor* const visitor) const override {
460 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);
461 visitor->VisitIntervalArrayArgument(ModelVisitor::kIntervalsArgument,
462 vars_);
463 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);
464 }
465
466 private:
467 bool IsPostponed(int index) {
468 DCHECK(vars_[index]->MayBePerformed());
469 return vars_[index]->StartMin() <= markers_[index];
470 }
471
472 void UnperformPostponedTaskBefore(int64 date) {
473 for (int i = 0; i < vars_.size(); ++i) {
474 IntervalVar* const v = vars_[i];
475 if (v->MayBePerformed() && v->StartMin() != v->StartMax() &&
476 IsPostponed(i) &&
477 // There are two rules here:
478 // - v->StartMax() <= date: the interval should have been scheduled
479 // as it cannot be scheduled later (assignment is chronological).
480 // - v->EndMin() <= date: The interval can fit before the current
481 // start date. In that case, it 'should' always fit, and as it has
482 // not be scheduled, then we are missing it. So, as a dominance
483 // rule, it should be marked as unperformed.
484 (v->EndMin() <= date || v->StartMax() <= date)) {
485 v->SetPerformed(false);
486 }
487 }
488 }
489
490 const std::vector<IntervalVar*> vars_;
491 std::vector<int64> markers_;
492};
493
494//
495// Backward scheduling.
496//
497class ScheduleOrExpedite : public Decision {
498 public:
499 ScheduleOrExpedite(IntervalVar* const var, int64 est, int64* const marker)
500 : var_(var), est_(est), marker_(marker) {}
501 ~ScheduleOrExpedite() override {}
502
503 void Apply(Solver* const s) override {
504 var_->SetPerformed(true);
505 if (est_.Value() > var_->EndMax()) {
506 est_.SetValue(s, var_->EndMax());
507 }
508 var_->SetEndRange(est_.Value(), est_.Value());
509 }
510
511 void Refute(Solver* const s) override {
512 s->SaveAndSetValue(marker_, est_.Value() - 1);
513 }
514
515 void Accept(DecisionVisitor* const visitor) const override {
516 CHECK(visitor != nullptr);
517 visitor->VisitScheduleOrExpedite(var_, est_.Value());
518 }
519
520 std::string DebugString() const override {
521 return absl::StrFormat("ScheduleOrExpedite(%s at %d)", var_->DebugString(),
522 est_.Value());
523 }
524
525 private:
526 IntervalVar* const var_;
527 NumericalRev<int64> est_;
528 int64* const marker_;
529};
530
531class SetTimesBackward : public DecisionBuilder {
532 public:
533 explicit SetTimesBackward(const std::vector<IntervalVar*>& vars)
534 : vars_(vars), markers_(vars.size(), kint64max) {}
535
536 ~SetTimesBackward() override {}
537
538 Decision* Next(Solver* const s) override {
539 int64 best_end = kint64min;
540 int64 best_start = kint64min;
541 int support = -1;
542 int refuted = 0;
543 for (int i = 0; i < vars_.size(); ++i) {
544 IntervalVar* const v = vars_[i];
545 if (v->MayBePerformed() && v->EndMax() > v->EndMin()) {
546 if (v->EndMax() <= markers_[i] &&
547 (v->EndMax() > best_end ||
548 (v->EndMax() == best_end && v->StartMin() > best_start))) {
549 best_end = v->EndMax();
550 best_start = v->StartMin();
551 support = i;
552 } else {
553 refuted++;
554 }
555 }
556 }
557 // TODO(user) : remove this crude quadratic loop with
558 // reversibles range reduction.
559 if (support == -1) {
560 if (refuted == 0) {
561 return nullptr;
562 } else {
563 s->Fail();
564 }
565 }
566 return s->RevAlloc(new ScheduleOrExpedite(
567 vars_[support], vars_[support]->EndMax(), &markers_[support]));
568 }
569
570 std::string DebugString() const override { return "SetTimesBackward()"; }
571
572 void Accept(ModelVisitor* const visitor) const override {
573 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);
574 visitor->VisitIntervalArrayArgument(ModelVisitor::kIntervalsArgument,
575 vars_);
576 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);
577 }
578
579 private:
580 const std::vector<IntervalVar*> vars_;
581 std::vector<int64> markers_;
582};
583
584// ----- Decisions and DecisionBuilders on sequences -----
585
586class RankFirst : public Decision {
587 public:
588 RankFirst(SequenceVar* const seq, int index)
589 : sequence_(seq), index_(index) {}
590 ~RankFirst() override {}
591
592 void Apply(Solver* const s) override { sequence_->RankFirst(index_); }
593
594 void Refute(Solver* const s) override { sequence_->RankNotFirst(index_); }
595
596 void Accept(DecisionVisitor* const visitor) const override {
597 CHECK(visitor != nullptr);
598 visitor->VisitRankFirstInterval(sequence_, index_);
599 }
600
601 std::string DebugString() const override {
602 return absl::StrFormat("RankFirst(%s, %d)", sequence_->DebugString(),
603 index_);
604 }
605
606 private:
607 SequenceVar* const sequence_;
608 const int index_;
609};
610
611class RankLast : public Decision {
612 public:
613 RankLast(SequenceVar* const seq, int index) : sequence_(seq), index_(index) {}
614 ~RankLast() override {}
615
616 void Apply(Solver* const s) override { sequence_->RankLast(index_); }
617
618 void Refute(Solver* const s) override { sequence_->RankNotLast(index_); }
619
620 void Accept(DecisionVisitor* const visitor) const override {
621 CHECK(visitor != nullptr);
622 visitor->VisitRankLastInterval(sequence_, index_);
623 }
624
625 std::string DebugString() const override {
626 return absl::StrFormat("RankLast(%s, %d)", sequence_->DebugString(),
627 index_);
628 }
629
630 private:
631 SequenceVar* const sequence_;
632 const int index_;
633};
634
635class RankFirstIntervalVars : public DecisionBuilder {
636 public:
637 RankFirstIntervalVars(const std::vector<SequenceVar*>& sequences,
639 : sequences_(sequences), strategy_(str) {}
640
641 ~RankFirstIntervalVars() override {}
642
643 Decision* Next(Solver* const s) override {
644 SequenceVar* best_sequence = nullptr;
645 best_possible_firsts_.clear();
646 while (true) {
647 if (FindSequenceVar(s, &best_sequence)) {
648 // No not create a choice point if it is not needed.
649 DCHECK(best_sequence != nullptr);
650 if (best_possible_firsts_.size() == 1 &&
651 best_sequence->Interval(best_possible_firsts_.back())
652 ->MustBePerformed()) {
653 best_sequence->RankFirst(best_possible_firsts_.back());
654 continue;
655 }
656 int best_interval = -1;
657 if (!FindIntervalVar(s, best_sequence, &best_interval)) {
658 s->Fail();
659 }
660 CHECK_NE(-1, best_interval);
661 return s->RevAlloc(new RankFirst(best_sequence, best_interval));
662 } else {
663 return nullptr;
664 }
665 }
666 }
667
668 void Accept(ModelVisitor* const visitor) const override {
669 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);
670 visitor->VisitSequenceArrayArgument(ModelVisitor::kSequencesArgument,
671 sequences_);
672 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);
673 }
674
675 private:
676 // Selects the interval var to rank.
677 bool FindIntervalVarOnStartMin(Solver* const s,
678 SequenceVar* const best_sequence,
679 int* const best_interval_index) {
680 int best_interval = -1;
681 int64 best_start_min = kint64max;
682 for (int index = 0; index < best_possible_firsts_.size(); ++index) {
683 const int candidate = best_possible_firsts_[index];
684 IntervalVar* const interval = best_sequence->Interval(candidate);
685 if (interval->StartMin() < best_start_min) {
686 best_interval = candidate;
687 best_start_min = interval->StartMin();
688 }
689 }
690 if (best_interval == -1) {
691 return false;
692 } else {
693 *best_interval_index = best_interval;
694 return true;
695 }
696 }
697
698 bool FindIntervalVarRandomly(Solver* const s,
699 SequenceVar* const best_sequence,
700 int* const best_interval_index) {
701 DCHECK(!best_possible_firsts_.empty());
702 const int index = s->Rand32(best_possible_firsts_.size());
703 *best_interval_index = best_possible_firsts_[index];
704 return true;
705 }
706
707 bool FindIntervalVar(Solver* const s, SequenceVar* const best_sequence,
708 int* const best_interval_index) {
709 switch (strategy_) {
713 return FindIntervalVarOnStartMin(s, best_sequence, best_interval_index);
715 return FindIntervalVarRandomly(s, best_sequence, best_interval_index);
716 default:
717 LOG(FATAL) << "Unknown strategy " << strategy_;
718 return false;
719 }
720 }
721
722 // Selects the sequence var to start ranking.
723 bool FindSequenceVarOnSlack(Solver* const s,
724 SequenceVar** const best_sequence) {
725 int64 best_slack = kint64max;
726 int64 best_ahmin = kint64max;
727 *best_sequence = nullptr;
728 best_possible_firsts_.clear();
729 for (int i = 0; i < sequences_.size(); ++i) {
730 SequenceVar* const candidate_sequence = sequences_[i];
731 int ranked = 0;
732 int not_ranked = 0;
733 int unperformed = 0;
734 candidate_sequence->ComputeStatistics(&ranked, &not_ranked, &unperformed);
735 if (not_ranked > 0) {
736 candidate_possible_firsts_.clear();
737 candidate_possible_lasts_.clear();
738 candidate_sequence->ComputePossibleFirstsAndLasts(
739 &candidate_possible_firsts_, &candidate_possible_lasts_);
740 // No possible first, failing.
741 if (candidate_possible_firsts_.empty()) {
742 s->Fail();
743 }
744 // Only 1 candidate, and non optional: ranking without branching.
745 if (candidate_possible_firsts_.size() == 1 &&
746 candidate_sequence->Interval(candidate_possible_firsts_.back())
747 ->MustBePerformed()) {
748 *best_sequence = candidate_sequence;
749 best_possible_firsts_ = candidate_possible_firsts_;
750 return true;
751 }
752
753 // Evaluating the sequence.
754 int64 hmin, hmax, dmin, dmax;
755 candidate_sequence->HorizonRange(&hmin, &hmax);
756 candidate_sequence->DurationRange(&dmin, &dmax);
757 int64 ahmin, ahmax;
758 candidate_sequence->ActiveHorizonRange(&ahmin, &ahmax);
759 const int64 current_slack = (hmax - hmin - dmax);
760 if (current_slack < best_slack ||
761 (current_slack == best_slack && ahmin < best_ahmin)) {
762 best_slack = current_slack;
763 *best_sequence = candidate_sequence;
764 best_possible_firsts_ = candidate_possible_firsts_;
765 best_ahmin = ahmin;
766 }
767 }
768 }
769 return *best_sequence != nullptr;
770 }
771
772 bool FindSequenceVarRandomly(Solver* const s,
773 SequenceVar** const best_sequence) {
774 std::vector<SequenceVar*> all_candidates;
775 std::vector<std::vector<int>> all_possible_firsts;
776 for (int i = 0; i < sequences_.size(); ++i) {
777 SequenceVar* const candidate_sequence = sequences_[i];
778 int ranked = 0;
779 int not_ranked = 0;
780 int unperformed = 0;
781 candidate_sequence->ComputeStatistics(&ranked, &not_ranked, &unperformed);
782 if (not_ranked > 0) {
783 candidate_possible_firsts_.clear();
784 candidate_possible_lasts_.clear();
785 candidate_sequence->ComputePossibleFirstsAndLasts(
786 &candidate_possible_firsts_, &candidate_possible_lasts_);
787 // No possible first, failing.
788 if (candidate_possible_firsts_.empty()) {
789 s->Fail();
790 }
791 // Only 1 candidate, and non optional: ranking without branching.
792 if (candidate_possible_firsts_.size() == 1 &&
793 candidate_sequence->Interval(candidate_possible_firsts_.back())
794 ->MustBePerformed()) {
795 *best_sequence = candidate_sequence;
796 best_possible_firsts_ = candidate_possible_firsts_;
797 return true;
798 }
799
800 all_candidates.push_back(candidate_sequence);
801 all_possible_firsts.push_back(candidate_possible_firsts_);
802 }
803 }
804 if (all_candidates.empty()) {
805 return false;
806 }
807 const int chosen = s->Rand32(all_candidates.size());
808 *best_sequence = all_candidates[chosen];
809 best_possible_firsts_ = all_possible_firsts[chosen];
810 return true;
811 }
812
813 bool FindSequenceVar(Solver* const s, SequenceVar** const best_sequence) {
814 switch (strategy_) {
818 return FindSequenceVarOnSlack(s, best_sequence);
820 return FindSequenceVarRandomly(s, best_sequence);
821 default:
822 LOG(FATAL) << "Unknown strategy " << strategy_;
823 }
824 }
825
826 const std::vector<SequenceVar*> sequences_;
827 const Solver::SequenceStrategy strategy_;
828 std::vector<int> best_possible_firsts_;
829 std::vector<int> candidate_possible_firsts_;
830 std::vector<int> candidate_possible_lasts_;
831};
832} // namespace
833
835 int64* const marker) {
836 CHECK(var != nullptr);
837 CHECK(marker != nullptr);
838 return RevAlloc(new ScheduleOrPostpone(var, est, marker));
839}
840
842 int64* const marker) {
843 CHECK(var != nullptr);
844 CHECK(marker != nullptr);
845 return RevAlloc(new ScheduleOrExpedite(var, est, marker));
846}
847
848DecisionBuilder* Solver::MakePhase(const std::vector<IntervalVar*>& intervals,
849 IntervalStrategy str) {
850 switch (str) {
854 return RevAlloc(new SetTimesForward(intervals));
856 return RevAlloc(new SetTimesBackward(intervals));
857 default:
858 LOG(FATAL) << "Unknown strategy " << str;
859 }
860}
861
863 int index) {
864 CHECK(sequence != nullptr);
865 return RevAlloc(new RankFirst(sequence, index));
866}
867
869 CHECK(sequence != nullptr);
870 return RevAlloc(new RankLast(sequence, index));
871}
872
873DecisionBuilder* Solver::MakePhase(const std::vector<SequenceVar*>& sequences,
874 SequenceStrategy str) {
875 return RevAlloc(new RankFirstIntervalVars(sequences, str));
876}
877
878} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
const std::vector< IntVar * > vars_
Definition: alldiff_cst.cc:43
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_NE(val1, val2)
Definition: base/logging.h:698
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
A DecisionBuilder is responsible for creating the search tree.
A Decision represents a choice point in the search tree.
virtual int64 Min() const =0
The class IntVar is a subset of IntExpr.
virtual bool Contains(int64 v) const =0
This method returns whether the value 'v' is in the domain of the variable.
Interval variables are often used in scheduling.
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 DurationMin() const =0
These methods query, set, and watch the duration of the interval var.
virtual bool MayBePerformed() const =0
virtual void VisitSequenceVariable(const SequenceVar *const variable)
static const char kVariableGroupExtension[]
virtual std::string name() const
Object naming.
virtual void RankLast(SequenceVar *const var, int index)=0
virtual void RankNotLast(SequenceVar *const var, int index)=0
virtual void RankNotFirst(SequenceVar *const var, int index)=0
virtual void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)=0
virtual void RankFirst(SequenceVar *const var, int index)=0
SequenceVar modifiers.
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
void ComputePossibleFirstsAndLasts(std::vector< int > *const possible_firsts, std::vector< int > *const possible_lasts)
Computes the set of indices of interval variables that can be ranked first in the set of unranked act...
void FillSequence(std::vector< int > *const rank_first, std::vector< int > *const rank_last, std::vector< int > *const unperformed) const
Clears 'rank_first' and 'rank_last', and fills them with the intervals in the order of the ranks.
void RankSequence(const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)
Applies the following sequence of ranks, ranks first, then rank last.
void ComputeStatistics(int *const ranked, int *const not_ranked, int *const unperformed) const
Compute statistics on the sequence.
void ActiveHorizonRange(int64 *const hmin, int64 *const hmax) const
Returns the minimum start min and the maximum end max of all unranked interval vars in the sequence.
void HorizonRange(int64 *const hmin, int64 *const hmax) const
Returns the minimum start min and the maximum end max of all interval vars in the sequence.
Definition: sched_search.cc:91
IntVar * Next(int index) const
Returns the next of the index_th interval of the sequence.
Definition: sched_search.cc:54
IntervalVar * Interval(int index) const
Returns the index_th interval of the sequence.
Definition: sched_search.cc:50
void RankLast(int index)
Ranks the index_th interval var first of all unranked interval vars.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
Definition: sched_search.cc:71
void DurationRange(int64 *const dmin, int64 *const dmax) const
Returns the minimum and maximum duration of combined interval vars in the sequence.
Definition: sched_search.cc:75
void RankFirst(int index)
Ranks the index_th interval var first of all unranked interval vars.
void RankNotLast(int index)
Indicates that the index_th interval var will not be ranked first of all currently unranked interval ...
void RankNotFirst(int index)
Indicates that the index_th interval var will not be ranked first of all currently unranked interval ...
SequenceVar(Solver *const s, const std::vector< IntervalVar * > &intervals, const std::vector< IntVar * > &nexts, const std::string &name)
Definition: sched_search.cc:37
std::string DebugString() const override
Definition: sched_search.cc:56
IntervalStrategy
This enum describes the straregy used to select the next interval variable and its value to be fixed.
@ INTERVAL_SET_TIMES_FORWARD
Selects the variable with the lowest starting time of all variables, and fixes its starting time to t...
@ INTERVAL_SIMPLE
The simple is INTERVAL_SET_TIMES_FORWARD.
@ INTERVAL_SET_TIMES_BACKWARD
Selects the variable with the highest ending time of all variables, and fixes the ending time to this...
@ INTERVAL_DEFAULT
The default is INTERVAL_SET_TIMES_FORWARD.
Decision * MakeScheduleOrExpedite(IntervalVar *const var, int64 est, int64 *const marker)
Returns a decision that tries to schedule a task at a given time.
PropagationMonitor * GetPropagationMonitor() const
Returns the propagation monitor.
Decision * MakeRankFirstInterval(SequenceVar *const sequence, int index)
Returns a decision that tries to rank first the ith interval var in the sequence variable.
Decision * MakeScheduleOrPostpone(IntervalVar *const var, int64 est, int64 *const marker)
Returns a decision that tries to schedule a task at a given time.
DecisionBuilder * MakePhase(const std::vector< IntVar * > &vars, IntVarStrategy var_str, IntValueStrategy val_str)
Phases on IntVar arrays.
Definition: search.cc:2008
SequenceStrategy
Used for scheduling. Not yet implemented.
Decision * MakeRankLastInterval(SequenceVar *const sequence, int index)
Returns a decision that tries to rank last the ith interval var in the sequence variable.
T * RevAlloc(T *object)
Registers the given object as being reversible.
Block * next
const std::string name
int64 value
IntVar * var
Definition: expr_array.cc:1858
static const int64 kint64max
int64_t int64
static const int64 kint64min
const int FATAL
Definition: log_severity.h:32
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:45
int index
Definition: pack.cc:508
IntervalVar * interval
Definition: resource.cc:98