OR-Tools  8.2
default_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 <cstddef>
15#include <functional>
16#include <limits>
17#include <memory>
18#include <string>
19#include <utility>
20#include <vector>
21
22#include "absl/container/flat_hash_set.h"
23#include "absl/strings/str_format.h"
27#include "ortools/base/macros.h"
33
34ABSL_FLAG(int, cp_impact_divider, 10, "Divider for continuous update.");
35
36namespace operations_research {
37
38namespace {
39// Default constants for search phase parameters.
40const int kDefaultNumberOfSplits = 100;
41const int kDefaultHeuristicPeriod = 100;
42const int kDefaultHeuristicNumFailuresLimit = 30;
43const bool kDefaultUseLastConflict = true;
44} // namespace
45
47 : var_selection_schema(DefaultPhaseParameters::CHOOSE_MAX_SUM_IMPACT),
48 value_selection_schema(DefaultPhaseParameters::SELECT_MIN_IMPACT),
49 initialization_splits(kDefaultNumberOfSplits),
50 run_all_heuristics(true),
51 heuristic_period(kDefaultHeuristicPeriod),
52 heuristic_num_failures_limit(kDefaultHeuristicNumFailuresLimit),
53 persistent_impact(true),
54 random_seed(CpRandomSeed()),
55 display_level(DefaultPhaseParameters::NORMAL),
56 use_last_conflict(kDefaultUseLastConflict),
57 decision_builder(nullptr) {}
58
59namespace {
60// ----- DomainWatcher -----
61
62// This class follows the domains of variables and will report the log of the
63// search space of all integer variables.
64class DomainWatcher {
65 public:
66 DomainWatcher(const std::vector<IntVar*>& vars, int cache_size)
67 : vars_(vars) {
68 cached_log_.Init(cache_size);
69 }
70
71 double LogSearchSpaceSize() {
72 double result = 0.0;
73 for (int index = 0; index < vars_.size(); ++index) {
74 result += cached_log_.Log2(vars_[index]->Size());
75 }
76 return result;
77 }
78
79 double Log2(int64 size) const { return cached_log_.Log2(size); }
80
81 private:
82 std::vector<IntVar*> vars_;
83 CachedLog cached_log_;
84 DISALLOW_COPY_AND_ASSIGN(DomainWatcher);
85};
86
87// ---------- FindVar decision visitor ---------
88
89class FindVar : public DecisionVisitor {
90 public:
91 enum Operation { NONE, ASSIGN, SPLIT_LOW, SPLIT_HIGH };
92
93 FindVar() : var_(nullptr), value_(0), operation_(NONE) {}
94
95 ~FindVar() override {}
96
97 void VisitSetVariableValue(IntVar* const var, int64 value) override {
98 var_ = var;
99 value_ = value;
100 operation_ = ASSIGN;
101 }
102
103 void VisitSplitVariableDomain(IntVar* const var, int64 value,
104 bool start_with_lower_half) override {
105 var_ = var;
106 value_ = value;
107 operation_ = start_with_lower_half ? SPLIT_LOW : SPLIT_HIGH;
108 }
109
110 void VisitScheduleOrPostpone(IntervalVar* const var, int64 est) override {
111 operation_ = NONE;
112 }
113
114 virtual void VisitTryRankFirst(SequenceVar* const sequence, int index) {
115 operation_ = NONE;
116 }
117
118 virtual void VisitTryRankLast(SequenceVar* const sequence, int index) {
119 operation_ = NONE;
120 }
121
122 void VisitUnknownDecision() override { operation_ = NONE; }
123
124 // Returns the current variable.
125 IntVar* const var() const {
126 CHECK_NE(operation_, NONE);
127 return var_;
128 }
129
130 // Returns the value of the current variable.
131 int64 value() const {
132 CHECK_NE(operation_, NONE);
133 return value_;
134 }
135
136 Operation operation() const { return operation_; }
137
138 std::string DebugString() const override {
139 return "FindVar decision visitor";
140 }
141
142 private:
143 IntVar* var_;
144 int64 value_;
145 Operation operation_;
146};
147
148// ----- Auxiliary decision builders to init impacts -----
149
150// This class initialize impacts by scanning each value of the domain
151// of the variable.
152class InitVarImpacts : public DecisionBuilder {
153 public:
154 // ----- main -----
155 InitVarImpacts()
156 : var_(nullptr),
157 update_impact_callback_(nullptr),
158 new_start_(false),
159 var_index_(0),
160 value_index_(-1),
161 update_impact_closure_([this]() { UpdateImpacts(); }),
162 updater_(update_impact_closure_) {
163 CHECK(update_impact_closure_ != nullptr);
164 }
165
166 ~InitVarImpacts() override {}
167
168 void UpdateImpacts() {
169 // the Min is always the value we just set.
170 update_impact_callback_(var_index_, var_->Min());
171 }
172
173 void Init(IntVar* const var, IntVarIterator* const iterator, int var_index) {
174 var_ = var;
175 iterator_ = iterator;
176 var_index_ = var_index;
177 new_start_ = true;
178 value_index_ = 0;
179 }
180
181 Decision* Next(Solver* const solver) override {
182 CHECK(var_ != nullptr);
183 CHECK(iterator_ != nullptr);
184 if (new_start_) {
185 active_values_.clear();
186 for (const int64 value : InitAndGetValues(iterator_)) {
187 active_values_.push_back(value);
188 }
189 new_start_ = false;
190 }
191 if (value_index_ == active_values_.size()) {
192 return nullptr;
193 }
194 updater_.var_ = var_;
195 updater_.value_ = active_values_[value_index_];
196 value_index_++;
197 return &updater_;
198 }
199
200 void set_update_impact_callback(std::function<void(int, int64)> callback) {
201 update_impact_callback_ = std::move(callback);
202 }
203
204 private:
205 // ----- helper decision -----
206 class AssignCallFail : public Decision {
207 public:
208 explicit AssignCallFail(const std::function<void()>& update_impact_closure)
209 : var_(nullptr),
210 value_(0),
211 update_impact_closure_(update_impact_closure) {
212 CHECK(update_impact_closure_ != nullptr);
213 }
214 ~AssignCallFail() override {}
215 void Apply(Solver* const solver) override {
216 CHECK(var_ != nullptr);
217 var_->SetValue(value_);
218 // We call the closure on the part that cannot fail.
219 update_impact_closure_();
220 solver->Fail();
221 }
222 void Refute(Solver* const solver) override {}
223 // Public data for easy access.
224 IntVar* var_;
225 int64 value_;
226
227 private:
228 const std::function<void()>& update_impact_closure_;
229 DISALLOW_COPY_AND_ASSIGN(AssignCallFail);
230 };
231
232 IntVar* var_;
233 std::function<void(int, int64)> update_impact_callback_;
234 bool new_start_;
235 IntVarIterator* iterator_;
236 int var_index_;
237 std::vector<int64> active_values_;
238 int value_index_;
239 std::function<void()> update_impact_closure_;
240 AssignCallFail updater_;
241};
242
243// This class initialize impacts by scanning at most 'split_size'
244// intervals on the domain of the variable.
245
246class InitVarImpactsWithSplits : public DecisionBuilder {
247 public:
248 // ----- helper decision -----
249 class AssignIntervalCallFail : public Decision {
250 public:
251 explicit AssignIntervalCallFail(
252 const std::function<void()>& update_impact_closure)
253 : var_(nullptr),
254 value_min_(0),
255 value_max_(0),
256 update_impact_closure_(update_impact_closure) {
257 CHECK(update_impact_closure_ != nullptr);
258 }
259 ~AssignIntervalCallFail() override {}
260 void Apply(Solver* const solver) override {
261 CHECK(var_ != nullptr);
262 var_->SetRange(value_min_, value_max_);
263 // We call the closure on the part that cannot fail.
264 update_impact_closure_();
265 solver->Fail();
266 }
267 void Refute(Solver* const solver) override {}
268
269 // Public for easy access.
270 IntVar* var_;
273
274 private:
275 const std::function<void()>& update_impact_closure_;
276 DISALLOW_COPY_AND_ASSIGN(AssignIntervalCallFail);
277 };
278
279 // ----- main -----
280
281 explicit InitVarImpactsWithSplits(int split_size)
282 : var_(nullptr),
283 update_impact_callback_(nullptr),
284 new_start_(false),
285 var_index_(0),
286 min_value_(0),
287 max_value_(0),
288 split_size_(split_size),
289 split_index_(-1),
290 update_impact_closure_([this]() { UpdateImpacts(); }),
291 updater_(update_impact_closure_) {
292 CHECK(update_impact_closure_ != nullptr);
293 }
294
295 ~InitVarImpactsWithSplits() override {}
296
297 void UpdateImpacts() {
298 for (const int64 value : InitAndGetValues(iterator_)) {
299 update_impact_callback_(var_index_, value);
300 }
301 }
302
303 void Init(IntVar* const var, IntVarIterator* const iterator, int var_index) {
304 var_ = var;
305 iterator_ = iterator;
306 var_index_ = var_index;
307 new_start_ = true;
308 split_index_ = 0;
309 }
310
311 int64 IntervalStart(int index) const {
312 const int64 length = max_value_ - min_value_ + 1;
313 return (min_value_ + length * index / split_size_);
314 }
315
316 Decision* Next(Solver* const solver) override {
317 if (new_start_) {
318 min_value_ = var_->Min();
319 max_value_ = var_->Max();
320 new_start_ = false;
321 }
322 if (split_index_ == split_size_) {
323 return nullptr;
324 }
325 updater_.var_ = var_;
326 updater_.value_min_ = IntervalStart(split_index_);
327 split_index_++;
328 if (split_index_ == split_size_) {
329 updater_.value_max_ = max_value_;
330 } else {
331 updater_.value_max_ = IntervalStart(split_index_) - 1;
332 }
333 return &updater_;
334 }
335
336 void set_update_impact_callback(std::function<void(int, int64)> callback) {
337 update_impact_callback_ = std::move(callback);
338 }
339
340 private:
341 IntVar* var_;
342 std::function<void(int, int64)> update_impact_callback_;
343 bool new_start_;
344 IntVarIterator* iterator_;
345 int var_index_;
346 int64 min_value_;
347 int64 max_value_;
348 const int split_size_;
349 int split_index_;
350 std::function<void()> update_impact_closure_;
351 AssignIntervalCallFail updater_;
352};
353
354// ----- ImpactRecorder
355
356// This class will record the impacts of all assignment of values to
357// variables. Its main output is to find the optimal pair (variable/value)
358// based on default phase parameters.
359class ImpactRecorder : public SearchMonitor {
360 public:
361 static const int kLogCacheSize;
362 static const double kPerfectImpact;
363 static const double kFailureImpact;
364 static const double kInitFailureImpact;
365 static const int kUninitializedVarIndex;
366
367 ImpactRecorder(Solver* const solver, DomainWatcher* const domain_watcher,
368 const std::vector<IntVar*>& vars,
370 : SearchMonitor(solver),
371 domain_watcher_(domain_watcher),
372 vars_(vars),
373 size_(vars.size()),
374 current_log_space_(0.0),
375 impacts_(size_),
376 original_min_(size_, 0LL),
377 domain_iterators_(new IntVarIterator*[size_]),
378 display_level_(display_level),
379 current_var_(kUninitializedVarIndex),
380 current_value_(0),
381 init_done_(false) {
382 for (int i = 0; i < size_; ++i) {
383 domain_iterators_[i] = vars_[i]->MakeDomainIterator(true);
384 var_map_[vars_[i]] = i;
385 }
386 }
387
388 void ApplyDecision(Decision* const d) override {
389 if (!init_done_) {
390 return;
391 }
392 d->Accept(&find_var_);
393 if (find_var_.operation() == FindVar::ASSIGN &&
394 gtl::ContainsKey(var_map_, find_var_.var())) {
395 current_var_ = var_map_[find_var_.var()];
396 current_value_ = find_var_.value();
397 current_log_space_ = domain_watcher_->LogSearchSpaceSize();
398 } else {
399 current_var_ = kUninitializedVarIndex;
400 current_value_ = 0;
401 }
402 }
403
404 void AfterDecision(Decision* const d, bool apply) override {
405 if (init_done_ && current_var_ != kUninitializedVarIndex) {
406 if (current_log_space_ > 0.0) {
407 const double log_space = domain_watcher_->LogSearchSpaceSize();
408 if (apply) {
409 const double impact = kPerfectImpact - log_space / current_log_space_;
410 UpdateImpact(current_var_, current_value_, impact);
411 current_var_ = kUninitializedVarIndex;
412 current_value_ = 0;
413 }
414 current_log_space_ = log_space;
415 }
416 }
417 }
418
419 void BeginFail() override {
420 if (init_done_ && current_var_ != kUninitializedVarIndex) {
421 UpdateImpact(current_var_, current_value_, kFailureImpact);
422 current_var_ = kUninitializedVarIndex;
423 current_value_ = 0;
424 }
425 }
426
427 void ResetAllImpacts() {
428 for (int i = 0; i < size_; ++i) {
429 original_min_[i] = vars_[i]->Min();
430 // By default, we init impacts to 2.0 -> equivalent to failure.
431 // This will be overwritten to real impact values on valid domain
432 // values during the FirstRun() method.
433 impacts_[i].resize(vars_[i]->Max() - vars_[i]->Min() + 1,
435 }
436
437 for (int i = 0; i < size_; ++i) {
438 for (int j = 0; j < impacts_[i].size(); ++j) {
439 impacts_[i][j] = kInitFailureImpact;
440 }
441 }
442 }
443
444 void UpdateImpact(int var_index, int64 value, double impact) {
445 const int64 value_index = value - original_min_[var_index];
446 const double current_impact = impacts_[var_index][value_index];
447 const double new_impact =
448 (current_impact * (absl::GetFlag(FLAGS_cp_impact_divider) - 1) +
449 impact) /
450 absl::GetFlag(FLAGS_cp_impact_divider);
451 impacts_[var_index][value_index] = new_impact;
452 }
453
454 void InitImpact(int var_index, int64 value) {
455 const double log_space = domain_watcher_->LogSearchSpaceSize();
456 const double impact = kPerfectImpact - log_space / current_log_space_;
457 const int64 value_index = value - original_min_[var_index];
458 DCHECK_LT(var_index, size_);
459 DCHECK_LT(value_index, impacts_[var_index].size());
460 impacts_[var_index][value_index] = impact;
461 init_count_++;
462 }
463
464 void FirstRun(int64 splits) {
465 Solver* const s = solver();
466 current_log_space_ = domain_watcher_->LogSearchSpaceSize();
467 if (display_level_ != DefaultPhaseParameters::NONE) {
468 LOG(INFO) << " - initial log2(SearchSpace) = " << current_log_space_;
469 }
470 const int64 init_time = s->wall_time();
471 ResetAllImpacts();
472 int64 removed_counter = 0;
473 FirstRunVariableContainers* container =
474 s->RevAlloc(new FirstRunVariableContainers(this, splits));
475 // Loop on the variables, scan domains and initialize impacts.
476 for (int var_index = 0; var_index < size_; ++var_index) {
477 IntVar* const var = vars_[var_index];
478 if (var->Bound()) {
479 continue;
480 }
481 IntVarIterator* const iterator = domain_iterators_[var_index];
482 DecisionBuilder* init_decision_builder = nullptr;
483 const bool no_split = var->Size() < splits;
484 if (no_split) {
485 // The domain is small enough, we scan it completely.
486 container->without_split()->set_update_impact_callback(
487 container->update_impact_callback());
488 container->without_split()->Init(var, iterator, var_index);
489 init_decision_builder = container->without_split();
490 } else {
491 // The domain is too big, we scan it in initialization_splits
492 // intervals.
493 container->with_splits()->set_update_impact_callback(
494 container->update_impact_callback());
495 container->with_splits()->Init(var, iterator, var_index);
496 init_decision_builder = container->with_splits();
497 }
498 // Reset the number of impacts initialized.
499 init_count_ = 0;
500 // Use Solve() to scan all values of one variable.
501 s->Solve(init_decision_builder);
502
503 // If we have not initialized all values, then they can be removed.
504 // As the iterator is not stable w.r.t. deletion, we need to store
505 // removed values in an intermediate vector.
506 if (init_count_ != var->Size() && no_split) {
507 container->ClearRemovedValues();
508 for (const int64 value : InitAndGetValues(iterator)) {
509 const int64 value_index = value - original_min_[var_index];
510 if (impacts_[var_index][value_index] == kInitFailureImpact) {
511 container->PushBackRemovedValue(value);
512 }
513 }
514 CHECK(container->HasRemovedValues()) << var->DebugString();
515 removed_counter += container->NumRemovedValues();
516 const double old_log = domain_watcher_->Log2(var->Size());
517 var->RemoveValues(container->removed_values());
518 current_log_space_ += domain_watcher_->Log2(var->Size()) - old_log;
519 }
520 }
521 if (display_level_ != DefaultPhaseParameters::NONE) {
522 if (removed_counter) {
523 LOG(INFO) << " - init done, time = " << s->wall_time() - init_time
524 << " ms, " << removed_counter
525 << " values removed, log2(SearchSpace) = "
526 << current_log_space_;
527 } else {
528 LOG(INFO) << " - init done, time = " << s->wall_time() - init_time
529 << " ms";
530 }
531 }
532 s->SaveAndSetValue(&init_done_, true);
533 }
534
535 // This method scans the domain of one variable and returns the sum
536 // of the impacts of all values in its domain, along with the value
537 // with minimal impact.
538 void ScanVarImpacts(int var_index, int64* const best_impact_value,
539 double* const var_impacts,
542 CHECK(best_impact_value != nullptr);
543 CHECK(var_impacts != nullptr);
544 double max_impact = -std::numeric_limits<double>::max();
545 double min_impact = std::numeric_limits<double>::max();
546 double sum_var_impact = 0.0;
547 int64 min_impact_value = -1;
548 int64 max_impact_value = -1;
549 for (const int64 value : InitAndGetValues(domain_iterators_[var_index])) {
550 const int64 value_index = value - original_min_[var_index];
551 DCHECK_LT(var_index, size_);
552 DCHECK_LT(value_index, impacts_[var_index].size());
553 const double current_impact = impacts_[var_index][value_index];
554 sum_var_impact += current_impact;
555 if (current_impact > max_impact) {
556 max_impact = current_impact;
557 max_impact_value = value;
558 }
559 if (current_impact < min_impact) {
560 min_impact = current_impact;
561 min_impact_value = value;
562 }
563 }
564
565 switch (var_select) {
567 *var_impacts = sum_var_impact / vars_[var_index]->Size();
568 break;
569 }
571 *var_impacts = max_impact;
572 break;
573 }
574 default: {
575 *var_impacts = sum_var_impact;
576 break;
577 }
578 }
579
580 switch (value_select) {
582 *best_impact_value = min_impact_value;
583 break;
584 }
586 *best_impact_value = max_impact_value;
587 break;
588 }
589 }
590 }
591
592 std::string DebugString() const override { return "ImpactRecorder"; }
593
594 private:
595 // A container for the variables needed in FirstRun that is reversibly
596 // allocable.
597 class FirstRunVariableContainers : public BaseObject {
598 public:
599 FirstRunVariableContainers(ImpactRecorder* impact_recorder, int64 splits)
600 : update_impact_callback_(
601 [impact_recorder](int var_index, int64 value) {
602 impact_recorder->InitImpact(var_index, value);
603 }),
604 removed_values_(),
605 without_splits_(),
606 with_splits_(splits) {}
607 std::function<void(int, int64)> update_impact_callback() const {
608 return update_impact_callback_;
609 }
610 void PushBackRemovedValue(int64 value) { removed_values_.push_back(value); }
611 bool HasRemovedValues() const { return !removed_values_.empty(); }
612 void ClearRemovedValues() { removed_values_.clear(); }
613 size_t NumRemovedValues() const { return removed_values_.size(); }
614 const std::vector<int64>& removed_values() const { return removed_values_; }
615 InitVarImpacts* without_split() { return &without_splits_; }
616 InitVarImpactsWithSplits* with_splits() { return &with_splits_; }
617
618 std::string DebugString() const override {
619 return "FirstRunVariableContainers";
620 }
621
622 private:
623 const std::function<void(int, int64)> update_impact_callback_;
624 std::vector<int64> removed_values_;
625 InitVarImpacts without_splits_;
626 InitVarImpactsWithSplits with_splits_;
627 };
628
629 DomainWatcher* const domain_watcher_;
630 std::vector<IntVar*> vars_;
631 const int size_;
632 double current_log_space_;
633 // impacts_[i][j] stores the average search space reduction when assigning
634 // original_min_[i] + j to variable i.
635 std::vector<std::vector<double> > impacts_;
636 std::vector<int64> original_min_;
637 std::unique_ptr<IntVarIterator*[]> domain_iterators_;
638 int64 init_count_;
639 const DefaultPhaseParameters::DisplayLevel display_level_;
640 int current_var_;
641 int64 current_value_;
642 FindVar find_var_;
643 absl::flat_hash_map<const IntVar*, int> var_map_;
644 bool init_done_;
645
646 DISALLOW_COPY_AND_ASSIGN(ImpactRecorder);
647};
648
649const int ImpactRecorder::kLogCacheSize = 1000;
650const double ImpactRecorder::kPerfectImpact = 1.0;
651const double ImpactRecorder::kFailureImpact = 1.0;
652const double ImpactRecorder::kInitFailureImpact = 2.0;
654
655// This structure stores 'var[index] (left?==:!=) value'.
656class ChoiceInfo {
657 public:
658 ChoiceInfo() : value_(0), var_(nullptr), left_(false) {}
659
660 ChoiceInfo(IntVar* const var, int64 value, bool left)
661 : value_(value), var_(var), left_(left) {}
662
663 std::string DebugString() const {
664 return absl::StrFormat("%s %s %d", var_->name(), (left_ ? "==" : "!="),
665 value_);
666 }
667
668 IntVar* var() const { return var_; }
669
670 bool left() const { return left_; }
671
672 int64 value() const { return value_; }
673
674 void set_left(bool left) { left_ = left; }
675
676 private:
677 int64 value_;
678 IntVar* var_;
679 bool left_;
680};
681
682// ---------- Heuristics ----------
683
684class RunHeuristicsAsDives : public Decision {
685 public:
686 RunHeuristicsAsDives(Solver* const solver, const std::vector<IntVar*>& vars,
688 bool run_all_heuristics, int random_seed,
689 int heuristic_period, int heuristic_num_failures_limit)
690 : heuristic_limit_(nullptr),
691 display_level_(level),
692 run_all_heuristics_(run_all_heuristics),
693 random_(random_seed),
694 heuristic_period_(heuristic_period),
695 heuristic_branch_count_(0),
696 heuristic_runs_(0) {
697 Init(solver, vars, heuristic_num_failures_limit);
698 }
699
700 ~RunHeuristicsAsDives() override { gtl::STLDeleteElements(&heuristics_); }
701
702 void Apply(Solver* const solver) override {
703 if (!RunAllHeuristics(solver)) {
704 solver->Fail();
705 }
706 }
707
708 void Refute(Solver* const solver) override {}
709
710 bool ShouldRun() {
711 if (heuristic_period_ <= 0) {
712 return false;
713 }
714 ++heuristic_branch_count_;
715 return heuristic_branch_count_ % heuristic_period_ == 0;
716 }
717
718 bool RunOneHeuristic(Solver* const solver, int index) {
719 HeuristicWrapper* const wrapper = heuristics_[index];
720 heuristic_runs_++;
721
722 const bool result =
723 solver->SolveAndCommit(wrapper->phase, heuristic_limit_);
724 if (result && display_level_ != DefaultPhaseParameters::NONE) {
725 LOG(INFO) << " --- solution found by heuristic " << wrapper->name
726 << " --- ";
727 }
728 return result;
729 }
730
731 bool RunAllHeuristics(Solver* const solver) {
732 if (run_all_heuristics_) {
733 for (int index = 0; index < heuristics_.size(); ++index) {
734 for (int run = 0; run < heuristics_[index]->runs; ++run) {
735 if (RunOneHeuristic(solver, index)) {
736 return true;
737 }
738 }
739 }
740 return false;
741 } else {
742 DCHECK_GT(heuristics_.size(), 0);
743 const int index = absl::Uniform<int>(random_, 0, heuristics_.size());
744 return RunOneHeuristic(solver, index);
745 }
746 }
747
748 int Rand32(int size) {
749 DCHECK_GT(size, 0);
750 return absl::Uniform<int>(random_, 0, size);
751 }
752
753 void Init(Solver* const solver, const std::vector<IntVar*>& vars,
754 int heuristic_num_failures_limit) {
755 const int kRunOnce = 1;
756 const int kRunMore = 2;
757 const int kRunALot = 3;
758
759 heuristics_.push_back(new HeuristicWrapper(
761 Solver::ASSIGN_MIN_VALUE, "AssignMinValueToMinDomainSize", kRunOnce));
762
763 heuristics_.push_back(new HeuristicWrapper(
765 Solver::ASSIGN_MAX_VALUE, "AssignMaxValueToMinDomainSize", kRunOnce));
766
767 heuristics_.push_back(
768 new HeuristicWrapper(solver, vars, Solver::CHOOSE_MIN_SIZE_LOWEST_MIN,
770 "AssignCenterValueToMinDomainSize", kRunOnce));
771
772 heuristics_.push_back(new HeuristicWrapper(
774 "AssignRandomValueToFirstUnbound", kRunALot));
775
776 heuristics_.push_back(new HeuristicWrapper(
778 "AssignMinValueToRandomVariable", kRunMore));
779
780 heuristics_.push_back(new HeuristicWrapper(
782 "AssignMaxValueToRandomVariable", kRunMore));
783
784 heuristics_.push_back(new HeuristicWrapper(
786 "AssignRandomValueToRandomVariable", kRunMore));
787
788 heuristic_limit_ = solver->MakeFailuresLimit(heuristic_num_failures_limit);
789 }
790
791 int heuristic_runs() const { return heuristic_runs_; }
792
793 private:
794 // This class wraps one heuristic with extra information: name and
795 // number of runs.
796 struct HeuristicWrapper {
797 HeuristicWrapper(Solver* const solver, const std::vector<IntVar*>& vars,
798 Solver::IntVarStrategy var_strategy,
799 Solver::IntValueStrategy value_strategy,
800 const std::string& heuristic_name, int heuristic_runs)
801 : phase(solver->MakePhase(vars, var_strategy, value_strategy)),
802 name(heuristic_name),
803 runs(heuristic_runs) {}
804
805 // The decision builder we are going to use in this dive.
806 DecisionBuilder* const phase;
807 // A name for logging purposes.
808 const std::string name;
809 // How many times we will run this particular heuristic in case the
810 // parameter run_all_heuristics is true. This is useful for random
811 // heuristics where it makes sense to run them more than once.
812 const int runs;
813 };
814
815 std::vector<HeuristicWrapper*> heuristics_;
816 SearchMonitor* heuristic_limit_;
818 bool run_all_heuristics_;
819 std::mt19937 random_;
820 const int heuristic_period_;
821 int heuristic_branch_count_;
822 int heuristic_runs_;
823};
824
825// ---------- DefaultIntegerSearch ----------
826
827// Default phase decision builder.
828class DefaultIntegerSearch : public DecisionBuilder {
829 public:
830 static const double kSmallSearchSpaceLimit;
831
832 DefaultIntegerSearch(Solver* const solver, const std::vector<IntVar*>& vars,
833 const DefaultPhaseParameters& parameters)
834 : vars_(vars),
835 parameters_(parameters),
836 domain_watcher_(vars, ImpactRecorder::kLogCacheSize),
837 impact_recorder_(solver, &domain_watcher_, vars,
838 parameters.display_level),
839 heuristics_(solver, vars_, parameters_.display_level,
840 parameters_.run_all_heuristics, parameters_.random_seed,
841 parameters_.heuristic_period,
842 parameters_.heuristic_num_failures_limit),
843 find_var_(),
844 last_int_var_(nullptr),
845 last_int_value_(0),
846 last_operation_(FindVar::NONE),
847 last_conflict_count_(0),
848 init_done_(false) {}
849
850 ~DefaultIntegerSearch() override {}
851
852 Decision* Next(Solver* const solver) override {
853 CheckInit(solver);
854
855 if (heuristics_.ShouldRun()) {
856 return &heuristics_;
857 }
858
859 Decision* const decision = parameters_.decision_builder != nullptr
860 ? parameters_.decision_builder->Next(solver)
861 : ImpactNext(solver);
862
863 // Returns early if the search tree is finished anyway.
864 if (decision == nullptr) {
865 ClearLastDecision();
866 return nullptr;
867 }
868
869 // The main goal of last conflict is to branch on a decision
870 // variable different from the one being evaluated. We need to
871 // retrieve first the variable in the current decision.
872 decision->Accept(&find_var_);
873 IntVar* const decision_var =
874 find_var_.operation() != FindVar::NONE ? find_var_.var() : nullptr;
875
876 // We will hijack the search heuristics if
877 // - we use last conflict
878 // - we have stored the last decision from the search heuristics
879 // - the variable stored is different from the variable of the current
880 // decision
881 // - this variable is not bound already
882 // Furthermore, each case will also verify that the stored decision is
883 // compatible with the current domain variable.
884 if (parameters_.use_last_conflict && last_int_var_ != nullptr &&
885 !last_int_var_->Bound() &&
886 (decision_var == nullptr || decision_var != last_int_var_)) {
887 switch (last_operation_) {
888 case FindVar::ASSIGN: {
889 if (last_int_var_->Contains(last_int_value_)) {
890 Decision* const assign =
891 solver->MakeAssignVariableValue(last_int_var_, last_int_value_);
892 ClearLastDecision();
893 last_conflict_count_++;
894 return assign;
895 }
896 break;
897 }
898 case FindVar::SPLIT_LOW: {
899 if (last_int_var_->Max() > last_int_value_ &&
900 last_int_var_->Min() <= last_int_value_) {
901 Decision* const split = solver->MakeVariableLessOrEqualValue(
902 last_int_var_, last_int_value_);
903 ClearLastDecision();
904 last_conflict_count_++;
905 return split;
906 }
907 break;
908 }
909 case FindVar::SPLIT_HIGH: {
910 if (last_int_var_->Min() < last_int_value_ &&
911 last_int_var_->Max() >= last_int_value_) {
912 Decision* const split = solver->MakeVariableGreaterOrEqualValue(
913 last_int_var_, last_int_value_);
914 ClearLastDecision();
915 last_conflict_count_++;
916 return split;
917 }
918 break;
919 }
920 default: {
921 break;
922 }
923 }
924 }
925
926 if (parameters_.use_last_conflict) {
927 // Store the last decision to replay it upon failure.
928 decision->Accept(&find_var_);
929 if (find_var_.operation() != FindVar::NONE) {
930 last_int_var_ = find_var_.var();
931 last_int_value_ = find_var_.value();
932 last_operation_ = find_var_.operation();
933 }
934 }
935
936 return decision;
937 }
938
939 void ClearLastDecision() {
940 last_int_var_ = nullptr;
941 last_int_value_ = 0;
942 last_operation_ = FindVar::NONE;
943 }
944
945 void AppendMonitors(Solver* const solver,
946 std::vector<SearchMonitor*>* const extras) override {
947 CHECK(solver != nullptr);
948 CHECK(extras != nullptr);
949 if (parameters_.decision_builder == nullptr) {
950 extras->push_back(&impact_recorder_);
951 }
952 }
953
954 void Accept(ModelVisitor* const visitor) const override {
955 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);
956 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
957 vars_);
958 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);
959 }
960
961 std::string DebugString() const override {
962 std::string out = "DefaultIntegerSearch(";
963
964 if (parameters_.decision_builder == nullptr) {
965 out.append("Impact Based Search, ");
966 } else {
967 out.append(parameters_.decision_builder->DebugString());
968 out.append(", ");
969 }
970 out.append(JoinDebugStringPtr(vars_, ", "));
971 out.append(")");
972 return out;
973 }
974
975 std::string StatString() const {
976 const int runs = heuristics_.heuristic_runs();
977 std::string result;
978 if (runs > 0) {
979 if (!result.empty()) {
980 result.append(", ");
981 }
982 if (runs == 1) {
983 result.append("1 heuristic run");
984 } else {
985 absl::StrAppendFormat(&result, "%d heuristic runs", runs);
986 }
987 }
988 if (last_conflict_count_ > 0) {
989 if (!result.empty()) {
990 result.append(", ");
991 }
992 if (last_conflict_count_ == 1) {
993 result.append("1 last conflict hint");
994 } else {
995 absl::StrAppendFormat(&result, "%d last conflict hints",
996 last_conflict_count_);
997 }
998 }
999 return result;
1000 }
1001
1002 private:
1003 void CheckInit(Solver* const solver) {
1004 if (init_done_) {
1005 return;
1006 }
1007 if (parameters_.decision_builder == nullptr) {
1008 // Decide if we are doing impacts, no if one variable is too big.
1009 for (int i = 0; i < vars_.size(); ++i) {
1010 if (vars_[i]->Max() - vars_[i]->Min() > 0xFFFFFF) {
1011 if (parameters_.display_level == DefaultPhaseParameters::VERBOSE) {
1012 LOG(INFO) << "Domains are too large, switching to simple "
1013 << "heuristics";
1014 }
1015 solver->SaveValue(
1016 reinterpret_cast<void**>(&parameters_.decision_builder));
1017 parameters_.decision_builder =
1018 solver->MakePhase(vars_, Solver::CHOOSE_MIN_SIZE_LOWEST_MIN,
1020 solver->SaveAndSetValue(&init_done_, true);
1021 return;
1022 }
1023 }
1024 // No if the search space is too small.
1025 if (domain_watcher_.LogSearchSpaceSize() < kSmallSearchSpaceLimit) {
1026 if (parameters_.display_level == DefaultPhaseParameters::VERBOSE) {
1027 LOG(INFO) << "Search space is too small, switching to simple "
1028 << "heuristics";
1029 }
1030 solver->SaveValue(
1031 reinterpret_cast<void**>(&parameters_.decision_builder));
1032 parameters_.decision_builder = solver->MakePhase(
1034 solver->SaveAndSetValue(&init_done_, true);
1035 return;
1036 }
1037
1038 if (parameters_.display_level != DefaultPhaseParameters::NONE) {
1039 LOG(INFO) << "Init impact based search phase on " << vars_.size()
1040 << " variables, initialization splits = "
1041 << parameters_.initialization_splits
1042 << ", heuristic_period = " << parameters_.heuristic_period
1043 << ", run_all_heuristics = "
1044 << parameters_.run_all_heuristics;
1045 }
1046 // Init the impacts.
1047 impact_recorder_.FirstRun(parameters_.initialization_splits);
1048 }
1049 if (parameters_.persistent_impact) {
1050 init_done_ = true;
1051 } else {
1052 solver->SaveAndSetValue(&init_done_, true);
1053 }
1054 }
1055
1056 // This method will do an exhaustive scan of all domains of all
1057 // variables to select the variable with the maximal sum of impacts
1058 // per value in its domain, and then select the value with the
1059 // minimal impact.
1060 Decision* ImpactNext(Solver* const solver) {
1061 IntVar* var = nullptr;
1062 int64 value = 0;
1063 double best_var_impact = -std::numeric_limits<double>::max();
1064 for (int i = 0; i < vars_.size(); ++i) {
1065 if (!vars_[i]->Bound()) {
1066 int64 current_value = 0;
1067 double current_var_impact = 0.0;
1068 impact_recorder_.ScanVarImpacts(i, &current_value, &current_var_impact,
1069 parameters_.var_selection_schema,
1070 parameters_.value_selection_schema);
1071 if (current_var_impact > best_var_impact) {
1072 var = vars_[i];
1073 value = current_value;
1074 best_var_impact = current_var_impact;
1075 }
1076 }
1077 }
1078 if (var == nullptr) {
1079 return nullptr;
1080 } else {
1081 return solver->MakeAssignVariableValue(var, value);
1082 }
1083 }
1084
1085 // ----- data members -----
1086
1087 std::vector<IntVar*> vars_;
1088 DefaultPhaseParameters parameters_;
1089 DomainWatcher domain_watcher_;
1090 ImpactRecorder impact_recorder_;
1091 RunHeuristicsAsDives heuristics_;
1092 FindVar find_var_;
1093 IntVar* last_int_var_;
1094 int64 last_int_value_;
1095 FindVar::Operation last_operation_;
1096 int last_conflict_count_;
1097 bool init_done_;
1098};
1099
1101} // namespace
1102
1103// ---------- API ----------
1104
1106 DefaultIntegerSearch* const dis = dynamic_cast<DefaultIntegerSearch*>(db);
1107 return dis != nullptr ? dis->StatString() : "";
1108}
1109
1110DecisionBuilder* Solver::MakeDefaultPhase(const std::vector<IntVar*>& vars) {
1112 return MakeDefaultPhase(vars, parameters);
1113}
1114
1116 const std::vector<IntVar*>& vars,
1118 return RevAlloc(new DefaultIntegerSearch(this, vars, parameters));
1119}
1120} // namespace operations_research
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 CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
A DecisionBuilder is responsible for creating the search tree.
static const char kVariableGroupExtension[]
ConstraintSolverParameters parameters() const
Stored Parameters.
IntValueStrategy
This enum describes the strategy used to select the next variable value to set.
@ ASSIGN_CENTER_VALUE
Selects the first possible value which is the closest to the center of the domain of the selected var...
@ ASSIGN_MIN_VALUE
Selects the min value of the selected variable.
@ ASSIGN_RANDOM_VALUE
Selects randomly one of the possible values of the selected variable.
@ ASSIGN_MAX_VALUE
Selects the max value of the selected variable.
IntVarStrategy
This enum describes the strategy used to select the next branching variable at each node during the s...
@ CHOOSE_RANDOM
Randomly select one of the remaining unbound variables.
@ CHOOSE_FIRST_UNBOUND
Select the first unbound variable.
@ CHOOSE_MIN_SIZE_LOWEST_MIN
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_MIN_SIZE_HIGHEST_MAX
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
DecisionBuilder * MakeDefaultPhase(const std::vector< IntVar * > &vars)
T * RevAlloc(T *object)
Registers the given object as being reversible.
SatParameters parameters
const int runs
int64 value_min_
static const double kSmallSearchSpaceLimit
static const int kUninitializedVarIndex
static const double kFailureImpact
static const int kLogCacheSize
const std::string name
static const double kInitFailureImpact
ABSL_FLAG(int, cp_impact_divider, 10, "Divider for continuous update.")
DecisionBuilder *const phase
static const double kPerfectImpact
int64 value_max_
int64 value
IntVar * var
Definition: expr_array.cc:1858
IntVarIterator *const iterator_
MPCallback * callback
int64_t int64
const int INFO
Definition: log_severity.h:31
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
void STLDeleteElements(T *container)
Definition: stl_util.h:372
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::string DefaultPhaseStatString(DecisionBuilder *db)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:45
int index
Definition: pack.cc:508
This struct holds all parameters for the default search.