OR-Tools  8.2
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 <algorithm>
15#include <functional>
16#include <list>
17#include <memory>
18#include <queue>
19#include <string>
20#include <utility>
21#include <vector>
22
23#include "absl/base/casts.h"
24#include "absl/container/flat_hash_map.h"
25#include "absl/memory/memory.h"
26#include "absl/strings/str_cat.h"
27#include "absl/strings/str_format.h"
28#include "absl/strings/str_join.h"
29#include "absl/time/time.h"
30#include "ortools/base/bitmap.h"
32#include "ortools/base/hash.h"
35#include "ortools/base/macros.h"
39#include "ortools/base/timer.h"
42#include "ortools/constraint_solver/search_limit.pb.h"
44
45ABSL_FLAG(bool, cp_use_sparse_gls_penalties, false,
46 "Use sparse implementation to store Guided Local Search penalties");
47ABSL_FLAG(bool, cp_log_to_vlog, false,
48 "Whether search related logging should be "
49 "vlog or info.");
50ABSL_FLAG(int64, cp_large_domain_no_splitting_limit, 0xFFFFF,
51 "Size limit to allow holes in variables from the strategy.");
52namespace operations_research {
53
54// ---------- Search Log ---------
55
56SearchLog::SearchLog(Solver* const s, OptimizeVar* const obj, IntVar* const var,
57 double scaling_factor, double offset,
58 std::function<std::string()> display_callback,
59 bool display_on_new_solutions_only, int period)
60 : SearchMonitor(s),
61 period_(period),
62 timer_(new WallTimer),
63 var_(var),
64 obj_(obj),
65 scaling_factor_(scaling_factor),
66 offset_(offset),
67 display_callback_(std::move(display_callback)),
68 display_on_new_solutions_only_(display_on_new_solutions_only),
69 nsol_(0),
70 tick_(0),
71 objective_min_(kint64max),
72 objective_max_(kint64min),
73 min_right_depth_(kint32max),
74 max_depth_(0),
75 sliding_min_depth_(0),
76 sliding_max_depth_(0) {
77 CHECK(obj == nullptr || var == nullptr)
78 << "Either var or obj need to be nullptr.";
79}
80
82
83std::string SearchLog::DebugString() const { return "SearchLog"; }
84
86 const std::string buffer =
87 absl::StrFormat("Start search (%s)", MemoryUsage());
88 OutputLine(buffer);
89 timer_->Restart();
90 min_right_depth_ = kint32max;
91}
92
94 const int64 branches = solver()->branches();
95 int64 ms = timer_->GetInMs();
96 if (ms == 0) {
97 ms = 1;
98 }
99 const std::string buffer = absl::StrFormat(
100 "End search (time = %d ms, branches = %d, failures = %d, %s, speed = %d "
101 "branches/s)",
102 ms, branches, solver()->failures(), MemoryUsage(), branches * 1000 / ms);
103 OutputLine(buffer);
104}
105
107 Maintain();
108 const int depth = solver()->SearchDepth();
109 std::string obj_str = "";
110 int64 current = 0;
111 bool objective_updated = false;
112 const auto scaled_str = [this](int64 value) {
113 if (scaling_factor_ != 1.0 || offset_ != 0.0) {
114 return absl::StrFormat("%d (%.8lf)", value,
115 scaling_factor_ * (value + offset_));
116 } else {
117 return absl::StrCat(value);
118 }
119 };
120 if (obj_ != nullptr && obj_->Var()->Bound()) {
121 current = obj_->Var()->Value();
122 obj_str = obj_->Print();
123 objective_updated = true;
124 } else if (var_ != nullptr && var_->Bound()) {
125 current = var_->Value();
126 absl::StrAppend(&obj_str, scaled_str(current), ", ");
127 objective_updated = true;
128 } else {
130 absl::StrAppend(&obj_str, scaled_str(current), ", ");
131 objective_updated = true;
132 }
133 if (objective_updated) {
134 if (current > objective_min_) {
135 absl::StrAppend(&obj_str,
136 "objective minimum = ", scaled_str(objective_min_), ", ");
137 } else {
138 objective_min_ = current;
139 }
140 if (current < objective_max_) {
141 absl::StrAppend(&obj_str,
142 "objective maximum = ", scaled_str(objective_max_), ", ");
143 } else {
144 objective_max_ = current;
145 }
146 }
147 std::string log;
148 absl::StrAppendFormat(&log,
149 "Solution #%d (%stime = %d ms, branches = %d,"
150 " failures = %d, depth = %d",
151 nsol_++, obj_str, timer_->GetInMs(),
152 solver()->branches(), solver()->failures(), depth);
153 if (!solver()->SearchContext().empty()) {
154 absl::StrAppendFormat(&log, ", %s", solver()->SearchContext());
155 }
156 if (solver()->neighbors() != 0) {
157 absl::StrAppendFormat(&log,
158 ", neighbors = %d, filtered neighbors = %d,"
159 " accepted neighbors = %d",
160 solver()->neighbors(), solver()->filtered_neighbors(),
161 solver()->accepted_neighbors());
162 }
163 absl::StrAppendFormat(&log, ", %s", MemoryUsage());
164 const int progress = solver()->TopProgressPercent();
165 if (progress != SearchMonitor::kNoProgress) {
166 absl::StrAppendFormat(&log, ", limit = %d%%", progress);
167 }
168 if (display_callback_) {
169 absl::StrAppendFormat(&log, ", %s", display_callback_());
170 }
171 log.append(")");
172 OutputLine(log);
173 return false;
174}
175
177
179
181 std::string buffer = absl::StrFormat(
182 "Finished search tree (time = %d ms, branches = %d,"
183 " failures = %d",
184 timer_->GetInMs(), solver()->branches(), solver()->failures());
185 if (solver()->neighbors() != 0) {
186 absl::StrAppendFormat(&buffer,
187 ", neighbors = %d, filtered neighbors = %d,"
188 " accepted neigbors = %d",
189 solver()->neighbors(), solver()->filtered_neighbors(),
190 solver()->accepted_neighbors());
191 }
192 absl::StrAppendFormat(&buffer, ", %s", MemoryUsage());
193 if (!display_on_new_solutions_only_ && display_callback_) {
194 absl::StrAppendFormat(&buffer, ", %s", display_callback_());
195 }
196 buffer.append(")");
197 OutputLine(buffer);
198}
199
200void SearchLog::ApplyDecision(Decision* const decision) {
201 Maintain();
202 const int64 b = solver()->branches();
203 if (b % period_ == 0 && b > 0) {
205 }
206}
207
208void SearchLog::RefuteDecision(Decision* const decision) {
209 min_right_depth_ = std::min(min_right_depth_, solver()->SearchDepth());
210 ApplyDecision(decision);
211}
212
214 std::string buffer =
215 absl::StrFormat("%d branches, %d ms, %d failures", solver()->branches(),
216 timer_->GetInMs(), solver()->failures());
217 if (min_right_depth_ != kint32max && max_depth_ != 0) {
218 const int depth = solver()->SearchDepth();
219 absl::StrAppendFormat(&buffer, ", tree pos=%d/%d/%d minref=%d max=%d",
220 sliding_min_depth_, depth, sliding_max_depth_,
221 min_right_depth_, max_depth_);
222 sliding_min_depth_ = depth;
223 sliding_max_depth_ = depth;
224 }
225 if (obj_ != nullptr && objective_min_ != kint64max &&
226 objective_max_ != kint64min) {
227 absl::StrAppendFormat(&buffer,
228 ", objective minimum = %d"
229 ", objective maximum = %d",
230 objective_min_, objective_max_);
231 }
232 const int progress = solver()->TopProgressPercent();
233 if (progress != SearchMonitor::kNoProgress) {
234 absl::StrAppendFormat(&buffer, ", limit = %d%%", progress);
235 }
236 OutputLine(buffer);
237}
238
240 const int current_depth = solver()->SearchDepth();
241 sliding_min_depth_ = std::min(current_depth, sliding_min_depth_);
242 sliding_max_depth_ = std::max(current_depth, sliding_max_depth_);
243 max_depth_ = std::max(current_depth, max_depth_);
244}
245
246void SearchLog::BeginInitialPropagation() { tick_ = timer_->GetInMs(); }
247
249 const int64 delta = std::max<int64>(timer_->GetInMs() - tick_, 0);
250 const std::string buffer = absl::StrFormat(
251 "Root node processed (time = %d ms, constraints = %d, %s)", delta,
252 solver()->constraints(), MemoryUsage());
253 OutputLine(buffer);
254}
255
256void SearchLog::OutputLine(const std::string& line) {
257 if (absl::GetFlag(FLAGS_cp_log_to_vlog)) {
258 VLOG(1) << line;
259 } else {
260 LOG(INFO) << line;
261 }
262}
263
264std::string SearchLog::MemoryUsage() {
265 static const int64 kDisplayThreshold = 2;
266 static const int64 kKiloByte = 1024;
267 static const int64 kMegaByte = kKiloByte * kKiloByte;
268 static const int64 kGigaByte = kMegaByte * kKiloByte;
269 const int64 memory_usage = Solver::MemoryUsage();
270 if (memory_usage > kDisplayThreshold * kGigaByte) {
271 return absl::StrFormat("memory used = %.2lf GB",
272 memory_usage * 1.0 / kGigaByte);
273 } else if (memory_usage > kDisplayThreshold * kMegaByte) {
274 return absl::StrFormat("memory used = %.2lf MB",
275 memory_usage * 1.0 / kMegaByte);
276 } else if (memory_usage > kDisplayThreshold * kKiloByte) {
277 return absl::StrFormat("memory used = %2lf KB",
278 memory_usage * 1.0 / kKiloByte);
279 } else {
280 return absl::StrFormat("memory used = %d", memory_usage);
281 }
282}
283
285 return MakeSearchLog(branch_period, static_cast<IntVar*>(nullptr));
286}
287
288SearchMonitor* Solver::MakeSearchLog(int branch_period, IntVar* const var) {
289 return MakeSearchLog(branch_period, var, nullptr);
290}
291
293 int branch_period, std::function<std::string()> display_callback) {
294 return MakeSearchLog(branch_period, static_cast<IntVar*>(nullptr),
295 std::move(display_callback));
296}
297
299 int branch_period, IntVar* const var,
300 std::function<std::string()> display_callback) {
301 return RevAlloc(new SearchLog(this, nullptr, var, 1.0, 0.0,
302 std::move(display_callback), true,
303 branch_period));
304}
305
307 OptimizeVar* const opt_var) {
308 return MakeSearchLog(branch_period, opt_var, nullptr);
309}
310
312 int branch_period, OptimizeVar* const opt_var,
313 std::function<std::string()> display_callback) {
314 return RevAlloc(new SearchLog(this, opt_var, nullptr, 1.0, 0.0,
315 std::move(display_callback), true,
316 branch_period));
317}
318
320 return RevAlloc(new SearchLog(this, parameters.objective, parameters.variable,
321 parameters.scaling_factor, parameters.offset,
322 std::move(parameters.display_callback),
323 parameters.display_on_new_solutions_only,
324 parameters.branch_period));
325}
326
327// ---------- Search Trace ----------
328namespace {
329class SearchTrace : public SearchMonitor {
330 public:
331 SearchTrace(Solver* const s, const std::string& prefix)
332 : SearchMonitor(s), prefix_(prefix) {}
333 ~SearchTrace() override {}
334
335 void EnterSearch() override {
336 LOG(INFO) << prefix_ << " EnterSearch(" << solver()->SolveDepth() << ")";
337 }
338 void RestartSearch() override {
339 LOG(INFO) << prefix_ << " RestartSearch(" << solver()->SolveDepth() << ")";
340 }
341 void ExitSearch() override {
342 LOG(INFO) << prefix_ << " ExitSearch(" << solver()->SolveDepth() << ")";
343 }
344 void BeginNextDecision(DecisionBuilder* const b) override {
345 LOG(INFO) << prefix_ << " BeginNextDecision(" << b << ") ";
346 }
347 void EndNextDecision(DecisionBuilder* const b, Decision* const d) override {
348 if (d) {
349 LOG(INFO) << prefix_ << " EndNextDecision(" << b << ", " << d << ") ";
350 } else {
351 LOG(INFO) << prefix_ << " EndNextDecision(" << b << ") ";
352 }
353 }
354 void ApplyDecision(Decision* const d) override {
355 LOG(INFO) << prefix_ << " ApplyDecision(" << d << ") ";
356 }
357 void RefuteDecision(Decision* const d) override {
358 LOG(INFO) << prefix_ << " RefuteDecision(" << d << ") ";
359 }
360 void AfterDecision(Decision* const d, bool apply) override {
361 LOG(INFO) << prefix_ << " AfterDecision(" << d << ", " << apply << ") ";
362 }
363 void BeginFail() override {
364 LOG(INFO) << prefix_ << " BeginFail(" << solver()->SearchDepth() << ")";
365 }
366 void EndFail() override {
367 LOG(INFO) << prefix_ << " EndFail(" << solver()->SearchDepth() << ")";
368 }
369 void BeginInitialPropagation() override {
370 LOG(INFO) << prefix_ << " BeginInitialPropagation()";
371 }
372 void EndInitialPropagation() override {
373 LOG(INFO) << prefix_ << " EndInitialPropagation()";
374 }
375 bool AtSolution() override {
376 LOG(INFO) << prefix_ << " AtSolution()";
377 return false;
378 }
379 bool AcceptSolution() override {
380 LOG(INFO) << prefix_ << " AcceptSolution()";
381 return true;
382 }
383 void NoMoreSolutions() override {
384 LOG(INFO) << prefix_ << " NoMoreSolutions()";
385 }
386
387 std::string DebugString() const override { return "SearchTrace"; }
388
389 private:
390 const std::string prefix_;
391};
392} // namespace
393
394SearchMonitor* Solver::MakeSearchTrace(const std::string& prefix) {
395 return RevAlloc(new SearchTrace(this, prefix));
396}
397
398// ---------- Callback-based search monitors ----------
399namespace {
400class AtSolutionCallback : public SearchMonitor {
401 public:
402 AtSolutionCallback(Solver* const solver, std::function<void()> callback)
403 : SearchMonitor(solver), callback_(std::move(callback)) {}
404 ~AtSolutionCallback() override {}
405 bool AtSolution() override;
406
407 private:
408 const std::function<void()> callback_;
409};
410
411bool AtSolutionCallback::AtSolution() {
412 callback_();
413 return false;
414}
415
416} // namespace
417
419 return RevAlloc(new AtSolutionCallback(this, std::move(callback)));
420}
421
422namespace {
423class EnterSearchCallback : public SearchMonitor {
424 public:
425 EnterSearchCallback(Solver* const solver, std::function<void()> callback)
426 : SearchMonitor(solver), callback_(std::move(callback)) {}
427 ~EnterSearchCallback() override {}
428 void EnterSearch() override;
429
430 private:
431 const std::function<void()> callback_;
432};
433
434void EnterSearchCallback::EnterSearch() { callback_(); }
435
436} // namespace
437
439 return RevAlloc(new EnterSearchCallback(this, std::move(callback)));
440}
441
442namespace {
443class ExitSearchCallback : public SearchMonitor {
444 public:
445 ExitSearchCallback(Solver* const solver, std::function<void()> callback)
446 : SearchMonitor(solver), callback_(std::move(callback)) {}
447 ~ExitSearchCallback() override {}
448 void ExitSearch() override;
449
450 private:
451 const std::function<void()> callback_;
452};
453
454void ExitSearchCallback::ExitSearch() { callback_(); }
455
456} // namespace
457
459 return RevAlloc(new ExitSearchCallback(this, std::move(callback)));
460}
461
462// ---------- Composite Decision Builder --------
463
464namespace {
465class CompositeDecisionBuilder : public DecisionBuilder {
466 public:
467 CompositeDecisionBuilder();
468 explicit CompositeDecisionBuilder(const std::vector<DecisionBuilder*>& dbs);
469 ~CompositeDecisionBuilder() override;
470 void Add(DecisionBuilder* const db);
471 void AppendMonitors(Solver* const solver,
472 std::vector<SearchMonitor*>* const monitors) override;
473 void Accept(ModelVisitor* const visitor) const override;
474
475 protected:
476 std::vector<DecisionBuilder*> builders_;
477};
478
479CompositeDecisionBuilder::CompositeDecisionBuilder() {}
480
481CompositeDecisionBuilder::CompositeDecisionBuilder(
482 const std::vector<DecisionBuilder*>& dbs) {
483 for (int i = 0; i < dbs.size(); ++i) {
484 Add(dbs[i]);
485 }
486}
487
488CompositeDecisionBuilder::~CompositeDecisionBuilder() {}
489
490void CompositeDecisionBuilder::Add(DecisionBuilder* const db) {
491 if (db != nullptr) {
492 builders_.push_back(db);
493 }
494}
495
496void CompositeDecisionBuilder::AppendMonitors(
497 Solver* const solver, std::vector<SearchMonitor*>* const monitors) {
498 for (DecisionBuilder* const db : builders_) {
499 db->AppendMonitors(solver, monitors);
500 }
501}
502
503void CompositeDecisionBuilder::Accept(ModelVisitor* const visitor) const {
504 for (DecisionBuilder* const db : builders_) {
505 db->Accept(visitor);
506 }
507}
508} // namespace
509
510// ---------- Compose Decision Builder ----------
511
512namespace {
513class ComposeDecisionBuilder : public CompositeDecisionBuilder {
514 public:
515 ComposeDecisionBuilder();
516 explicit ComposeDecisionBuilder(const std::vector<DecisionBuilder*>& dbs);
517 ~ComposeDecisionBuilder() override;
518 Decision* Next(Solver* const s) override;
519 std::string DebugString() const override;
520
521 private:
522 int start_index_;
523};
524
525ComposeDecisionBuilder::ComposeDecisionBuilder() : start_index_(0) {}
526
527ComposeDecisionBuilder::ComposeDecisionBuilder(
528 const std::vector<DecisionBuilder*>& dbs)
529 : CompositeDecisionBuilder(dbs), start_index_(0) {}
530
531ComposeDecisionBuilder::~ComposeDecisionBuilder() {}
532
533Decision* ComposeDecisionBuilder::Next(Solver* const s) {
534 const int size = builders_.size();
535 for (int i = start_index_; i < size; ++i) {
536 Decision* d = builders_[i]->Next(s);
537 if (d != nullptr) {
538 s->SaveAndSetValue(&start_index_, i);
539 return d;
540 }
541 }
542 s->SaveAndSetValue(&start_index_, size);
543 return nullptr;
544}
545
546std::string ComposeDecisionBuilder::DebugString() const {
547 return absl::StrFormat("ComposeDecisionBuilder(%s)",
549}
550} // namespace
551
552DecisionBuilder* Solver::Compose(DecisionBuilder* const db1,
553 DecisionBuilder* const db2) {
554 ComposeDecisionBuilder* c = RevAlloc(new ComposeDecisionBuilder());
555 c->Add(db1);
556 c->Add(db2);
557 return c;
558}
559
560DecisionBuilder* Solver::Compose(DecisionBuilder* const db1,
561 DecisionBuilder* const db2,
562 DecisionBuilder* const db3) {
563 ComposeDecisionBuilder* c = RevAlloc(new ComposeDecisionBuilder());
564 c->Add(db1);
565 c->Add(db2);
566 c->Add(db3);
567 return c;
568}
569
570DecisionBuilder* Solver::Compose(DecisionBuilder* const db1,
571 DecisionBuilder* const db2,
572 DecisionBuilder* const db3,
573 DecisionBuilder* const db4) {
574 ComposeDecisionBuilder* c = RevAlloc(new ComposeDecisionBuilder());
575 c->Add(db1);
576 c->Add(db2);
577 c->Add(db3);
578 c->Add(db4);
579 return c;
580}
581
582DecisionBuilder* Solver::Compose(const std::vector<DecisionBuilder*>& dbs) {
583 if (dbs.size() == 1) {
584 return dbs[0];
585 }
586 return RevAlloc(new ComposeDecisionBuilder(dbs));
587}
588
589// ---------- ClosureDecision ---------
590
591namespace {
592class ClosureDecision : public Decision {
593 public:
594 ClosureDecision(Solver::Action apply, Solver::Action refute)
595 : apply_(std::move(apply)), refute_(std::move(refute)) {}
596 ~ClosureDecision() override {}
597
598 void Apply(Solver* const s) override { apply_(s); }
599
600 void Refute(Solver* const s) override { refute_(s); }
601
602 std::string DebugString() const override { return "ClosureDecision"; }
603
604 private:
605 Solver::Action apply_;
606 Solver::Action refute_;
607};
608} // namespace
609
610Decision* Solver::MakeDecision(Action apply, Action refute) {
611 return RevAlloc(new ClosureDecision(std::move(apply), std::move(refute)));
612}
613
614// ---------- Try Decision Builder ----------
615
616namespace {
617
618class TryDecisionBuilder;
619
620class TryDecision : public Decision {
621 public:
622 explicit TryDecision(TryDecisionBuilder* const try_builder);
623 ~TryDecision() override;
624 void Apply(Solver* const solver) override;
625 void Refute(Solver* const solver) override;
626 std::string DebugString() const override { return "TryDecision"; }
627
628 private:
629 TryDecisionBuilder* const try_builder_;
630};
631
632class TryDecisionBuilder : public CompositeDecisionBuilder {
633 public:
634 TryDecisionBuilder();
635 explicit TryDecisionBuilder(const std::vector<DecisionBuilder*>& dbs);
636 ~TryDecisionBuilder() override;
637 Decision* Next(Solver* const solver) override;
638 std::string DebugString() const override;
639 void AdvanceToNextBuilder(Solver* const solver);
640
641 private:
642 TryDecision try_decision_;
643 int current_builder_;
644 bool start_new_builder_;
645};
646
647TryDecision::TryDecision(TryDecisionBuilder* const try_builder)
648 : try_builder_(try_builder) {}
649
650TryDecision::~TryDecision() {}
651
652void TryDecision::Apply(Solver* const solver) {}
653
654void TryDecision::Refute(Solver* const solver) {
655 try_builder_->AdvanceToNextBuilder(solver);
656}
657
658TryDecisionBuilder::TryDecisionBuilder()
659 : CompositeDecisionBuilder(),
660 try_decision_(this),
661 current_builder_(-1),
662 start_new_builder_(true) {}
663
664TryDecisionBuilder::TryDecisionBuilder(const std::vector<DecisionBuilder*>& dbs)
665 : CompositeDecisionBuilder(dbs),
666 try_decision_(this),
667 current_builder_(-1),
668 start_new_builder_(true) {}
669
670TryDecisionBuilder::~TryDecisionBuilder() {}
671
672Decision* TryDecisionBuilder::Next(Solver* const solver) {
673 if (current_builder_ < 0) {
674 solver->SaveAndSetValue(&current_builder_, 0);
675 start_new_builder_ = true;
676 }
677 if (start_new_builder_) {
678 start_new_builder_ = false;
679 return &try_decision_;
680 } else {
681 return builders_[current_builder_]->Next(solver);
682 }
683}
684
685std::string TryDecisionBuilder::DebugString() const {
686 return absl::StrFormat("TryDecisionBuilder(%s)",
688}
689
690void TryDecisionBuilder::AdvanceToNextBuilder(Solver* const solver) {
691 ++current_builder_;
692 start_new_builder_ = true;
693 if (current_builder_ >= builders_.size()) {
694 solver->Fail();
695 }
696}
697
698} // namespace
699
701 DecisionBuilder* const db2) {
702 TryDecisionBuilder* try_db = RevAlloc(new TryDecisionBuilder());
703 try_db->Add(db1);
704 try_db->Add(db2);
705 return try_db;
706}
707
709 DecisionBuilder* const db2,
710 DecisionBuilder* const db3) {
711 TryDecisionBuilder* try_db = RevAlloc(new TryDecisionBuilder());
712 try_db->Add(db1);
713 try_db->Add(db2);
714 try_db->Add(db3);
715 return try_db;
716}
717
719 DecisionBuilder* const db2,
720 DecisionBuilder* const db3,
721 DecisionBuilder* const db4) {
722 TryDecisionBuilder* try_db = RevAlloc(new TryDecisionBuilder());
723 try_db->Add(db1);
724 try_db->Add(db2);
725 try_db->Add(db3);
726 try_db->Add(db4);
727 return try_db;
728}
729
730DecisionBuilder* Solver::Try(const std::vector<DecisionBuilder*>& dbs) {
731 return RevAlloc(new TryDecisionBuilder(dbs));
732}
733
734// ---------- Variable Assignments ----------
735
736// ----- BaseAssignmentSelector -----
737
738namespace {
739class BaseVariableAssignmentSelector : public BaseObject {
740 public:
741 BaseVariableAssignmentSelector(Solver* solver,
742 const std::vector<IntVar*>& vars)
743 : solver_(solver),
744 vars_(vars),
746 last_unbound_(vars.size() - 1) {}
747
748 ~BaseVariableAssignmentSelector() override {}
749
750 virtual int64 SelectValue(const IntVar* v, int64 id) = 0;
751
752 // Returns -1 if no variable are suitable.
753 virtual int64 ChooseVariable() = 0;
754
755 int64 ChooseVariableWrapper() {
756 int64 i;
757 for (i = first_unbound_.Value(); i <= last_unbound_.Value(); ++i) {
758 if (!vars_[i]->Bound()) {
759 break;
760 }
761 }
762 first_unbound_.SetValue(solver_, i);
763 if (i > last_unbound_.Value()) {
764 return -1;
765 }
766 for (i = last_unbound_.Value(); i >= first_unbound_.Value(); --i) {
767 if (!vars_[i]->Bound()) {
768 break;
769 }
770 }
771 last_unbound_.SetValue(solver_, i);
772 return ChooseVariable();
773 }
774
775 void Accept(ModelVisitor* const visitor) const {
776 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);
777 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
778 vars_);
779 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);
780 }
781
782 const std::vector<IntVar*>& vars() const { return vars_; }
783
784 protected:
785 Solver* const solver_;
786 std::vector<IntVar*> vars_;
787 Rev<int64> first_unbound_;
788 Rev<int64> last_unbound_;
789};
790
791// ----- Choose first unbound --
792
793int64 ChooseFirstUnbound(Solver* solver, const std::vector<IntVar*>& vars,
794 int64 first_unbound, int64 last_unbound) {
795 for (int64 i = first_unbound; i <= last_unbound; ++i) {
796 if (!vars[i]->Bound()) {
797 return i;
798 }
799 }
800 return -1;
801}
802
803// ----- Choose Min Size Lowest Min -----
804
805int64 ChooseMinSizeLowestMin(Solver* solver, const std::vector<IntVar*>& vars,
806 int64 first_unbound, int64 last_unbound) {
807 uint64 best_size = kuint64max;
808 int64 best_min = kint64max;
809 int64 best_index = -1;
810 for (int64 i = first_unbound; i <= last_unbound; ++i) {
811 IntVar* const var = vars[i];
812 if (!var->Bound()) {
813 if (var->Size() < best_size ||
814 (var->Size() == best_size && var->Min() < best_min)) {
815 best_size = var->Size();
816 best_min = var->Min();
817 best_index = i;
818 }
819 }
820 }
821 return best_index;
822}
823
824// ----- Choose Min Size Highest Min -----
825
826int64 ChooseMinSizeHighestMin(Solver* solver, const std::vector<IntVar*>& vars,
827 int64 first_unbound, int64 last_unbound) {
828 uint64 best_size = kuint64max;
829 int64 best_min = kint64min;
830 int64 best_index = -1;
831 for (int64 i = first_unbound; i <= last_unbound; ++i) {
832 IntVar* const var = vars[i];
833 if (!var->Bound()) {
834 if (var->Size() < best_size ||
835 (var->Size() == best_size && var->Min() > best_min)) {
836 best_size = var->Size();
837 best_min = var->Min();
838 best_index = i;
839 }
840 }
841 }
842 return best_index;
843}
844
845// ----- Choose Min Size Lowest Max -----
846
847int64 ChooseMinSizeLowestMax(Solver* solver, const std::vector<IntVar*>& vars,
848 int64 first_unbound, int64 last_unbound) {
849 uint64 best_size = kuint64max;
850 int64 best_max = kint64max;
851 int64 best_index = -1;
852 for (int64 i = first_unbound; i <= last_unbound; ++i) {
853 IntVar* const var = vars[i];
854 if (!var->Bound()) {
855 if (var->Size() < best_size ||
856 (var->Size() == best_size && var->Max() < best_max)) {
857 best_size = var->Size();
858 best_max = var->Max();
859 best_index = i;
860 }
861 }
862 }
863 return best_index;
864}
865
866// ----- Choose Min Size Highest Max -----
867
868int64 ChooseMinSizeHighestMax(Solver* solver, const std::vector<IntVar*>& vars,
869 int64 first_unbound, int64 last_unbound) {
870 uint64 best_size = kuint64max;
871 int64 best_max = kint64min;
872 int64 best_index = -1;
873 for (int64 i = first_unbound; i <= last_unbound; ++i) {
874 IntVar* const var = vars[i];
875 if (!var->Bound()) {
876 if (var->Size() < best_size ||
877 (var->Size() == best_size && var->Max() > best_max)) {
878 best_size = var->Size();
879 best_max = var->Max();
880 best_index = i;
881 }
882 }
883 }
884 return best_index;
885}
886
887// ----- Choose Lowest Min --
888
889int64 ChooseLowestMin(Solver* solver, const std::vector<IntVar*>& vars,
890 int64 first_unbound, int64 last_unbound) {
891 int64 best_min = kint64max;
892 int64 best_index = -1;
893 for (int64 i = first_unbound; i <= last_unbound; ++i) {
894 IntVar* const var = vars[i];
895 if (!var->Bound()) {
896 if (var->Min() < best_min) {
897 best_min = var->Min();
898 best_index = i;
899 }
900 }
901 }
902 return best_index;
903}
904
905// ----- Choose Highest Max -----
906
907int64 ChooseHighestMax(Solver* solver, const std::vector<IntVar*>& vars,
908 int64 first_unbound, int64 last_unbound) {
909 int64 best_max = kint64min;
910 int64 best_index = -1;
911 for (int64 i = first_unbound; i <= last_unbound; ++i) {
912 IntVar* const var = vars[i];
913 if (!var->Bound()) {
914 if (var->Max() > best_max) {
915 best_max = var->Max();
916 best_index = i;
917 }
918 }
919 }
920 return best_index;
921}
922
923// ----- Choose Lowest Size --
924
925int64 ChooseMinSize(Solver* solver, const std::vector<IntVar*>& vars,
926 int64 first_unbound, int64 last_unbound) {
927 uint64 best_size = kuint64max;
928 int64 best_index = -1;
929 for (int64 i = first_unbound; i <= last_unbound; ++i) {
930 IntVar* const var = vars[i];
931 if (!var->Bound()) {
932 if (var->Size() < best_size) {
933 best_size = var->Size();
934 best_index = i;
935 }
936 }
937 }
938 return best_index;
939}
940
941// ----- Choose Highest Size -----
942
943int64 ChooseMaxSize(Solver* solver, const std::vector<IntVar*>& vars,
944 int64 first_unbound, int64 last_unbound) {
945 uint64 best_size = 0;
946 int64 best_index = -1;
947 for (int64 i = first_unbound; i <= last_unbound; ++i) {
948 IntVar* const var = vars[i];
949 if (!var->Bound()) {
950 if (var->Size() > best_size) {
951 best_size = var->Size();
952 best_index = i;
953 }
954 }
955 }
956 return best_index;
957}
958
959// ----- Choose Highest Regret -----
960
961class HighestRegretSelectorOnMin : public BaseObject {
962 public:
963 explicit HighestRegretSelectorOnMin(const std::vector<IntVar*>& vars)
964 : iterators_(vars.size()) {
965 for (int64 i = 0; i < vars.size(); ++i) {
966 iterators_[i] = vars[i]->MakeDomainIterator(true);
967 }
968 }
969 ~HighestRegretSelectorOnMin() override {}
970 int64 Choose(Solver* const s, const std::vector<IntVar*>& vars,
971 int64 first_unbound, int64 last_unbound);
972 std::string DebugString() const override { return "MaxRegretSelector"; }
973
974 int64 ComputeRegret(IntVar* var, int64 index) const {
975 DCHECK(!var->Bound());
976 const int64 vmin = var->Min();
977 IntVarIterator* const iterator = iterators_[index];
978 iterator->Init();
979 iterator->Next();
980 return iterator->Value() - vmin;
981 }
982
983 private:
984 std::vector<IntVarIterator*> iterators_;
985};
986
987int64 HighestRegretSelectorOnMin::Choose(Solver* const s,
988 const std::vector<IntVar*>& vars,
989 int64 first_unbound,
990 int64 last_unbound) {
991 int64 best_regret = 0;
992 int64 index = -1;
993 for (int64 i = first_unbound; i <= last_unbound; ++i) {
994 IntVar* const var = vars[i];
995 if (!var->Bound()) {
996 const int64 regret = ComputeRegret(var, i);
997 if (regret > best_regret) {
998 best_regret = regret;
999 index = i;
1000 }
1001 }
1002 }
1003 return index;
1004}
1005
1006// ----- Choose random unbound --
1007
1008int64 ChooseRandom(Solver* solver, const std::vector<IntVar*>& vars,
1009 int64 first_unbound, int64 last_unbound) {
1010 const int64 span = last_unbound - first_unbound + 1;
1011 const int64 shift = solver->Rand32(span);
1012 for (int64 i = 0; i < span; ++i) {
1013 const int64 index = (i + shift) % span + first_unbound;
1014 if (!vars[index]->Bound()) {
1015 return index;
1016 }
1017 }
1018 return -1;
1019}
1020
1021// ----- Choose min eval -----
1022
1023class CheapestVarSelector : public BaseObject {
1024 public:
1025 explicit CheapestVarSelector(std::function<int64(int64)> var_evaluator)
1026 : var_evaluator_(std::move(var_evaluator)) {}
1027 ~CheapestVarSelector() override {}
1028 int64 Choose(Solver* const s, const std::vector<IntVar*>& vars,
1029 int64 first_unbound, int64 last_unbound);
1030 std::string DebugString() const override { return "CheapestVarSelector"; }
1031
1032 private:
1033 std::function<int64(int64)> var_evaluator_;
1034};
1035
1036int64 CheapestVarSelector::Choose(Solver* const s,
1037 const std::vector<IntVar*>& vars,
1038 int64 first_unbound, int64 last_unbound) {
1039 int64 best_eval = kint64max;
1040 int64 index = -1;
1041 for (int64 i = first_unbound; i <= last_unbound; ++i) {
1042 if (!vars[i]->Bound()) {
1043 const int64 eval = var_evaluator_(i);
1044 if (eval < best_eval) {
1045 best_eval = eval;
1046 index = i;
1047 }
1048 }
1049 }
1050 return index;
1051}
1052
1053// ----- Path selector -----
1054// Follow path, where var[i] is represents the next of i
1055
1056class PathSelector : public BaseObject {
1057 public:
1058 PathSelector() : first_(kint64max) {}
1059 ~PathSelector() override {}
1060 int64 Choose(Solver* const s, const std::vector<IntVar*>& vars,
1061 int64 first_unbound, int64 last_unbound);
1062 std::string DebugString() const override { return "ChooseNextOnPath"; }
1063
1064 private:
1065 bool UpdateIndex(const std::vector<IntVar*>& vars, int64* index) const;
1066 bool FindPathStart(const std::vector<IntVar*>& vars, int64* index) const;
1067
1068 Rev<int64> first_;
1069};
1070
1071int64 PathSelector::Choose(Solver* const s, const std::vector<IntVar*>& vars,
1072 int64 first_unbound, int64 last_unbound) {
1073 int64 index = first_.Value();
1074 if (!UpdateIndex(vars, &index)) {
1075 return -1;
1076 }
1077 int64 count = 0;
1078 while (vars[index]->Bound()) {
1079 index = vars[index]->Value();
1080 if (!UpdateIndex(vars, &index)) {
1081 return -1;
1082 }
1083 ++count;
1084 if (count >= vars.size() &&
1085 !FindPathStart(vars, &index)) { // Cycle detected
1086 return -1;
1087 }
1088 }
1089 first_.SetValue(s, index);
1090 return index;
1091}
1092
1093bool PathSelector::UpdateIndex(const std::vector<IntVar*>& vars,
1094 int64* index) const {
1095 if (*index >= vars.size()) {
1096 if (!FindPathStart(vars, index)) {
1097 return false;
1098 }
1099 }
1100 return true;
1101}
1102
1103// Select variables on a path:
1104// 1. Try to extend an existing route: look for an unbound variable, to which
1105// some other variable points.
1106// 2. If no such road is found, try to find a start node of a route: look for
1107// an unbound variable, to which no other variable can point.
1108// 3. If everything else fails, pick the first unbound variable.
1109bool PathSelector::FindPathStart(const std::vector<IntVar*>& vars,
1110 int64* index) const {
1111 // Try to extend an existing path
1112 for (int64 i = vars.size() - 1; i >= 0; --i) {
1113 if (vars[i]->Bound()) {
1114 const int64 next = vars[i]->Value();
1115 if (next < vars.size() && !vars[next]->Bound()) {
1116 *index = next;
1117 return true;
1118 }
1119 }
1120 }
1121 // Pick path start
1122 for (int64 i = vars.size() - 1; i >= 0; --i) {
1123 if (!vars[i]->Bound()) {
1124 bool has_possible_prev = false;
1125 for (int64 j = 0; j < vars.size(); ++j) {
1126 if (vars[j]->Contains(i)) {
1127 has_possible_prev = true;
1128 break;
1129 }
1130 }
1131 if (!has_possible_prev) {
1132 *index = i;
1133 return true;
1134 }
1135 }
1136 }
1137 // Pick first unbound
1138 for (int64 i = 0; i < vars.size(); ++i) {
1139 if (!vars[i]->Bound()) {
1140 *index = i;
1141 return true;
1142 }
1143 }
1144 return false;
1145}
1146
1147// ----- Select min -----
1148
1149int64 SelectMinValue(const IntVar* v, int64 id) { return v->Min(); }
1150
1151// ----- Select max -----
1152
1153int64 SelectMaxValue(const IntVar* v, int64 id) { return v->Max(); }
1154
1155// ----- Select random -----
1156
1157int64 SelectRandomValue(const IntVar* v, int64 id) {
1158 const uint64 span = v->Max() - v->Min() + 1;
1159 if (span > absl::GetFlag(FLAGS_cp_large_domain_no_splitting_limit)) {
1160 // Do not create holes in large domains.
1161 return v->Min();
1162 }
1163 const uint64 size = v->Size();
1164 Solver* const s = v->solver();
1165 if (size > span / 4) { // Dense enough, we can try to find the
1166 // value randomly.
1167 for (;;) {
1168 const int64 value = v->Min() + s->Rand64(span);
1169 if (v->Contains(value)) {
1170 return value;
1171 }
1172 }
1173 } else { // Not dense enough, we will count.
1174 int64 index = s->Rand64(size);
1175 if (index <= size / 2) {
1176 for (int64 i = v->Min(); i <= v->Max(); ++i) {
1177 if (v->Contains(i)) {
1178 if (--index == 0) {
1179 return i;
1180 }
1181 }
1182 }
1183 CHECK_LE(index, 0);
1184 } else {
1185 for (int64 i = v->Max(); i > v->Min(); --i) {
1186 if (v->Contains(i)) {
1187 if (--index == 0) {
1188 return i;
1189 }
1190 }
1191 }
1192 CHECK_LE(index, 0);
1193 }
1194 }
1195 return 0;
1196}
1197
1198// ----- Select center -----
1199
1200int64 SelectCenterValue(const IntVar* v, int64 id) {
1201 const int64 vmin = v->Min();
1202 const int64 vmax = v->Max();
1203 if (vmax - vmin > absl::GetFlag(FLAGS_cp_large_domain_no_splitting_limit)) {
1204 // Do not create holes in large domains.
1205 return vmin;
1206 }
1207 const int64 mid = (vmin + vmax) / 2;
1208 if (v->Contains(mid)) {
1209 return mid;
1210 }
1211 const int64 diameter = vmax - mid; // always greater than mid - vmix.
1212 for (int64 i = 1; i <= diameter; ++i) {
1213 if (v->Contains(mid - i)) {
1214 return mid - i;
1215 }
1216 if (v->Contains(mid + i)) {
1217 return mid + i;
1218 }
1219 }
1220 return 0;
1221}
1222
1223// ----- Select center -----
1224
1225int64 SelectSplitValue(const IntVar* v, int64 id) {
1226 const int64 vmin = v->Min();
1227 const int64 vmax = v->Max();
1228 const uint64 delta = vmax - vmin;
1229 const int64 mid = vmin + delta / 2;
1230 return mid;
1231}
1232
1233// ----- Select the value yielding the cheapest "eval" for a var -----
1234
1235class CheapestValueSelector : public BaseObject {
1236 public:
1237 CheapestValueSelector(std::function<int64(int64, int64)> eval,
1238 std::function<int64(int64)> tie_breaker)
1239 : eval_(std::move(eval)), tie_breaker_(std::move(tie_breaker)) {}
1240 ~CheapestValueSelector() override {}
1241 int64 Select(const IntVar* v, int64 id);
1242 std::string DebugString() const override { return "CheapestValue"; }
1243
1244 private:
1245 std::function<int64(int64, int64)> eval_;
1246 std::function<int64(int64)> tie_breaker_;
1247 std::vector<int64> cache_;
1248};
1249
1250int64 CheapestValueSelector::Select(const IntVar* v, int64 id) {
1251 cache_.clear();
1252 int64 best = kint64max;
1253 std::unique_ptr<IntVarIterator> it(v->MakeDomainIterator(false));
1254 for (const int64 i : InitAndGetValues(it.get())) {
1255 int64 eval = eval_(id, i);
1256 if (eval < best) {
1257 best = eval;
1258 cache_.clear();
1259 cache_.push_back(i);
1260 } else if (eval == best) {
1261 cache_.push_back(i);
1262 }
1263 }
1264 DCHECK_GT(cache_.size(), 0);
1265 if (tie_breaker_ == nullptr || cache_.size() == 1) {
1266 return cache_.back();
1267 } else {
1268 return cache_[tie_breaker_(cache_.size())];
1269 }
1270}
1271
1272// ----- Select the best value for the var, based on a comparator callback -----
1273
1274// The comparator should be a total order, but does not have to be a strict
1275// ordering. If there is a tie between two values val1 and val2, i.e. if
1276// !comparator(var_id, val1, val2) && !comparator(var_id, val2, val1), then
1277// the lowest value wins.
1278// comparator(var_id, val1, val2) == true means than val1 should be preferred
1279// over val2 for variable var_id.
1280class BestValueByComparisonSelector : public BaseObject {
1281 public:
1282 explicit BestValueByComparisonSelector(
1284 : comparator_(std::move(comparator)) {}
1285 ~BestValueByComparisonSelector() override {}
1286 int64 Select(const IntVar* v, int64 id);
1287 std::string DebugString() const override {
1288 return "BestValueByComparisonSelector";
1289 }
1290
1291 private:
1293};
1294
1295int64 BestValueByComparisonSelector::Select(const IntVar* v, int64 id) {
1296 std::unique_ptr<IntVarIterator> it(v->MakeDomainIterator(false));
1297 it->Init();
1298 DCHECK(it->Ok()); // At least one value.
1299 int64 best_value = it->Value();
1300 for (it->Next(); it->Ok(); it->Next()) {
1301 const int64 candidate_value = it->Value();
1302 if (comparator_(id, candidate_value, best_value)) {
1303 best_value = candidate_value;
1304 }
1305 }
1306 return best_value;
1307}
1308
1309// ----- VariableAssignmentSelector -----
1310
1311class VariableAssignmentSelector : public BaseVariableAssignmentSelector {
1312 public:
1313 VariableAssignmentSelector(Solver* solver, const std::vector<IntVar*>& vars,
1314 Solver::VariableIndexSelector var_selector,
1315 Solver::VariableValueSelector value_selector,
1316 const std::string& name)
1317 : BaseVariableAssignmentSelector(solver, vars),
1318 var_selector_(std::move(var_selector)),
1319 value_selector_(std::move(value_selector)),
1320 name_(name) {}
1321 ~VariableAssignmentSelector() override {}
1322 int64 SelectValue(const IntVar* var, int64 id) override {
1323 return value_selector_(var, id);
1324 }
1325 int64 ChooseVariable() override {
1326 return var_selector_(solver_, vars_, first_unbound_.Value(),
1327 last_unbound_.Value());
1328 }
1329 std::string DebugString() const override;
1330
1331 private:
1332 Solver::VariableIndexSelector var_selector_;
1333 Solver::VariableValueSelector value_selector_;
1334 const std::string name_;
1335};
1336
1337std::string VariableAssignmentSelector::DebugString() const {
1338 return absl::StrFormat("%s(%s)", name_, JoinDebugStringPtr(vars_, ", "));
1339}
1340
1341// ----- Base Global Evaluator-based selector -----
1342
1343class BaseEvaluatorSelector : public BaseVariableAssignmentSelector {
1344 public:
1345 BaseEvaluatorSelector(Solver* solver, const std::vector<IntVar*>& vars,
1346 std::function<int64(int64, int64)> evaluator);
1347 ~BaseEvaluatorSelector() override {}
1348
1349 protected:
1350 struct Element {
1351 Element() : var(0), value(0) {}
1352 Element(int64 i, int64 j) : var(i), value(j) {}
1355 };
1356
1357 std::string DebugStringInternal(const std::string& name) const {
1358 return absl::StrFormat("%s(%s)", name, JoinDebugStringPtr(vars_, ", "));
1359 }
1360
1361 std::function<int64(int64, int64)> evaluator_;
1362};
1363
1364BaseEvaluatorSelector::BaseEvaluatorSelector(
1365 Solver* solver, const std::vector<IntVar*>& vars,
1366 std::function<int64(int64, int64)> evaluator)
1367 : BaseVariableAssignmentSelector(solver, vars),
1368 evaluator_(std::move(evaluator)) {}
1369
1370// ----- Global Dynamic Evaluator-based selector -----
1371
1372class DynamicEvaluatorSelector : public BaseEvaluatorSelector {
1373 public:
1374 DynamicEvaluatorSelector(Solver* solver, const std::vector<IntVar*>& vars,
1375 std::function<int64(int64, int64)> evaluator,
1376 std::function<int64(int64)> tie_breaker);
1377 ~DynamicEvaluatorSelector() override {}
1378 int64 SelectValue(const IntVar* var, int64 id) override;
1379 int64 ChooseVariable() override;
1380 std::string DebugString() const override;
1381
1382 private:
1383 int64 first_;
1384 std::function<int64(int64)> tie_breaker_;
1385 std::vector<Element> cache_;
1386};
1387
1388DynamicEvaluatorSelector::DynamicEvaluatorSelector(
1389 Solver* solver, const std::vector<IntVar*>& vars,
1390 std::function<int64(int64, int64)> evaluator,
1391 std::function<int64(int64)> tie_breaker)
1392 : BaseEvaluatorSelector(solver, vars, std::move(evaluator)),
1393 first_(-1),
1394 tie_breaker_(std::move(tie_breaker)) {}
1395
1396int64 DynamicEvaluatorSelector::SelectValue(const IntVar* var, int64 id) {
1397 return cache_[first_].value;
1398}
1399
1400int64 DynamicEvaluatorSelector::ChooseVariable() {
1401 int64 best_evaluation = kint64max;
1402 cache_.clear();
1403 for (int64 i = 0; i < vars_.size(); ++i) {
1404 const IntVar* const var = vars_[i];
1405 if (!var->Bound()) {
1406 std::unique_ptr<IntVarIterator> it(var->MakeDomainIterator(false));
1407 for (const int64 j : InitAndGetValues(it.get())) {
1408 const int64 value = evaluator_(i, j);
1409 if (value < best_evaluation) {
1410 best_evaluation = value;
1411 cache_.clear();
1412 cache_.push_back(Element(i, j));
1413 } else if (value == best_evaluation && tie_breaker_) {
1414 cache_.push_back(Element(i, j));
1415 }
1416 }
1417 }
1418 }
1419
1420 if (cache_.empty()) {
1421 return -1;
1422 }
1423
1424 if (tie_breaker_ == nullptr || cache_.size() == 1) {
1425 first_ = 0;
1426 return cache_.front().var;
1427 } else {
1428 first_ = tie_breaker_(cache_.size());
1429 return cache_[first_].var;
1430 }
1431}
1432
1433std::string DynamicEvaluatorSelector::DebugString() const {
1434 return DebugStringInternal("AssignVariablesOnDynamicEvaluator");
1435}
1436
1437// ----- Global Dynamic Evaluator-based selector -----
1438
1439class StaticEvaluatorSelector : public BaseEvaluatorSelector {
1440 public:
1441 StaticEvaluatorSelector(Solver* solver, const std::vector<IntVar*>& vars,
1442 const std::function<int64(int64, int64)>& evaluator);
1443 ~StaticEvaluatorSelector() override {}
1444 int64 SelectValue(const IntVar* var, int64 id) override;
1445 int64 ChooseVariable() override;
1446 std::string DebugString() const override;
1447
1448 private:
1449 class Compare {
1450 public:
1451 explicit Compare(std::function<int64(int64, int64)> evaluator)
1452 : evaluator_(std::move(evaluator)) {}
1453 bool operator()(const Element& lhs, const Element& rhs) const {
1454 const int64 value_lhs = Value(lhs);
1455 const int64 value_rhs = Value(rhs);
1456 return value_lhs < value_rhs ||
1457 (value_lhs == value_rhs &&
1458 (lhs.var < rhs.var ||
1459 (lhs.var == rhs.var && lhs.value < rhs.value)));
1460 }
1461 int64 Value(const Element& element) const {
1462 return evaluator_(element.var, element.value);
1463 }
1464
1465 private:
1466 std::function<int64(int64, int64)> evaluator_;
1467 };
1468
1469 Compare comp_;
1470 std::vector<Element> elements_;
1471 int64 first_;
1472};
1473
1474StaticEvaluatorSelector::StaticEvaluatorSelector(
1475 Solver* solver, const std::vector<IntVar*>& vars,
1476 const std::function<int64(int64, int64)>& evaluator)
1477 : BaseEvaluatorSelector(solver, vars, evaluator),
1478 comp_(evaluator),
1479 first_(-1) {}
1480
1481int64 StaticEvaluatorSelector::SelectValue(const IntVar* var, int64 id) {
1482 return elements_[first_].value;
1483}
1484
1485int64 StaticEvaluatorSelector::ChooseVariable() {
1486 if (first_ == -1) { // first call to select. update assignment costs
1487 // Two phases: compute size then filland sort
1488 int64 element_size = 0;
1489 for (int64 i = 0; i < vars_.size(); ++i) {
1490 if (!vars_[i]->Bound()) {
1491 element_size += vars_[i]->Size();
1492 }
1493 }
1494 elements_.resize(element_size);
1495 int count = 0;
1496 for (int i = 0; i < vars_.size(); ++i) {
1497 const IntVar* const var = vars_[i];
1498 if (!var->Bound()) {
1499 std::unique_ptr<IntVarIterator> it(var->MakeDomainIterator(false));
1500 for (const int64 value : InitAndGetValues(it.get())) {
1501 elements_[count++] = Element(i, value);
1502 }
1503 }
1504 }
1505 // Sort is stable here given the tie-breaking rules in comp_.
1506 std::sort(elements_.begin(), elements_.end(), comp_);
1507 solver_->SaveAndSetValue<int64>(&first_, 0);
1508 }
1509 for (int64 i = first_; i < elements_.size(); ++i) {
1510 const Element& element = elements_[i];
1511 IntVar* const var = vars_[element.var];
1512 if (!var->Bound() && var->Contains(element.value)) {
1513 solver_->SaveAndSetValue(&first_, i);
1514 return element.var;
1515 }
1516 }
1517 solver_->SaveAndSetValue(&first_, static_cast<int64>(elements_.size()));
1518 return -1;
1519}
1520
1521std::string StaticEvaluatorSelector::DebugString() const {
1522 return DebugStringInternal("AssignVariablesOnStaticEvaluator");
1523}
1524
1525// ----- AssignOneVariableValue decision -----
1526
1527class AssignOneVariableValue : public Decision {
1528 public:
1529 AssignOneVariableValue(IntVar* const v, int64 val);
1530 ~AssignOneVariableValue() override {}
1531 void Apply(Solver* const s) override;
1532 void Refute(Solver* const s) override;
1533 std::string DebugString() const override;
1534 void Accept(DecisionVisitor* const visitor) const override {
1535 visitor->VisitSetVariableValue(var_, value_);
1536 }
1537
1538 private:
1539 IntVar* const var_;
1540 int64 value_;
1541};
1542
1543AssignOneVariableValue::AssignOneVariableValue(IntVar* const v, int64 val)
1544 : var_(v), value_(val) {}
1545
1546std::string AssignOneVariableValue::DebugString() const {
1547 return absl::StrFormat("[%s == %d] or [%s != %d]", var_->DebugString(),
1548 value_, var_->DebugString(), value_);
1549}
1550
1551void AssignOneVariableValue::Apply(Solver* const s) { var_->SetValue(value_); }
1552
1553void AssignOneVariableValue::Refute(Solver* const s) {
1554 var_->RemoveValue(value_);
1555}
1556} // namespace
1557
1558Decision* Solver::MakeAssignVariableValue(IntVar* const var, int64 val) {
1559 return RevAlloc(new AssignOneVariableValue(var, val));
1560}
1561
1562// ----- AssignOneVariableValueOrFail decision -----
1563
1564namespace {
1565class AssignOneVariableValueOrFail : public Decision {
1566 public:
1567 AssignOneVariableValueOrFail(IntVar* const v, int64 value);
1568 ~AssignOneVariableValueOrFail() override {}
1569 void Apply(Solver* const s) override;
1570 void Refute(Solver* const s) override;
1571 std::string DebugString() const override;
1572 void Accept(DecisionVisitor* const visitor) const override {
1573 visitor->VisitSetVariableValue(var_, value_);
1574 }
1575
1576 private:
1577 IntVar* const var_;
1578 const int64 value_;
1579};
1580
1581AssignOneVariableValueOrFail::AssignOneVariableValueOrFail(IntVar* const v,
1582 int64 value)
1583 : var_(v), value_(value) {}
1584
1585std::string AssignOneVariableValueOrFail::DebugString() const {
1586 return absl::StrFormat("[%s == %d] or fail", var_->DebugString(), value_);
1587}
1588
1589void AssignOneVariableValueOrFail::Apply(Solver* const s) {
1590 var_->SetValue(value_);
1591}
1592
1593void AssignOneVariableValueOrFail::Refute(Solver* const s) { s->Fail(); }
1594} // namespace
1595
1597 int64 value) {
1598 return RevAlloc(new AssignOneVariableValueOrFail(var, value));
1599}
1600
1601// ----- AssignOneVariableValueOrDoNothing decision -----
1602
1603namespace {
1604class AssignOneVariableValueDoNothing : public Decision {
1605 public:
1606 AssignOneVariableValueDoNothing(IntVar* const v, int64 value)
1607 : var_(v), value_(value) {}
1608 ~AssignOneVariableValueDoNothing() override {}
1609 void Apply(Solver* const s) override { var_->SetValue(value_); }
1610 void Refute(Solver* const s) override {}
1611 std::string DebugString() const override {
1612 return absl::StrFormat("[%s == %d] or []", var_->DebugString(), value_);
1613 }
1614 void Accept(DecisionVisitor* const visitor) const override {
1615 visitor->VisitSetVariableValue(var_, value_);
1616 }
1617
1618 private:
1619 IntVar* const var_;
1620 const int64 value_;
1621};
1622
1623} // namespace
1624
1626 int64 value) {
1627 return RevAlloc(new AssignOneVariableValueDoNothing(var, value));
1628}
1629
1630// ----- AssignOneVariableValue decision -----
1631
1632namespace {
1633class SplitOneVariable : public Decision {
1634 public:
1635 SplitOneVariable(IntVar* const v, int64 val, bool start_with_lower_half);
1636 ~SplitOneVariable() override {}
1637 void Apply(Solver* const s) override;
1638 void Refute(Solver* const s) override;
1639 std::string DebugString() const override;
1640 void Accept(DecisionVisitor* const visitor) const override {
1641 visitor->VisitSplitVariableDomain(var_, value_, start_with_lower_half_);
1642 }
1643
1644 private:
1645 IntVar* const var_;
1646 const int64 value_;
1647 const bool start_with_lower_half_;
1648};
1649
1650SplitOneVariable::SplitOneVariable(IntVar* const v, int64 val,
1651 bool start_with_lower_half)
1652 : var_(v), value_(val), start_with_lower_half_(start_with_lower_half) {}
1653
1654std::string SplitOneVariable::DebugString() const {
1655 if (start_with_lower_half_) {
1656 return absl::StrFormat("[%s <= %d]", var_->DebugString(), value_);
1657 } else {
1658 return absl::StrFormat("[%s >= %d]", var_->DebugString(), value_);
1659 }
1660}
1661
1662void SplitOneVariable::Apply(Solver* const s) {
1663 if (start_with_lower_half_) {
1664 var_->SetMax(value_);
1665 } else {
1666 var_->SetMin(value_ + 1);
1667 }
1668}
1669
1670void SplitOneVariable::Refute(Solver* const s) {
1671 if (start_with_lower_half_) {
1672 var_->SetMin(value_ + 1);
1673 } else {
1674 var_->SetMax(value_);
1675 }
1676}
1677} // namespace
1678
1680 bool start_with_lower_half) {
1681 return RevAlloc(new SplitOneVariable(var, val, start_with_lower_half));
1682}
1683
1685 return MakeSplitVariableDomain(var, value, true);
1686}
1687
1689 int64 value) {
1690 return MakeSplitVariableDomain(var, value, false);
1691}
1692
1693// ----- AssignVariablesValues decision -----
1694
1695namespace {
1696class AssignVariablesValues : public Decision {
1697 public:
1698 AssignVariablesValues(const std::vector<IntVar*>& vars,
1699 const std::vector<int64>& values);
1700 ~AssignVariablesValues() override {}
1701 void Apply(Solver* const s) override;
1702 void Refute(Solver* const s) override;
1703 std::string DebugString() const override;
1704 void Accept(DecisionVisitor* const visitor) const override {
1705 for (int i = 0; i < vars_.size(); ++i) {
1706 visitor->VisitSetVariableValue(vars_[i], values_[i]);
1707 }
1708 }
1709
1710 virtual void Accept(ModelVisitor* const visitor) const {
1711 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);
1712 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
1713 vars_);
1714 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);
1715 }
1716
1717 private:
1718 const std::vector<IntVar*> vars_;
1719 const std::vector<int64> values_;
1720};
1721
1722AssignVariablesValues::AssignVariablesValues(const std::vector<IntVar*>& vars,
1723 const std::vector<int64>& values)
1724 : vars_(vars), values_(values) {}
1725
1726std::string AssignVariablesValues::DebugString() const {
1727 std::string out;
1728 for (int i = 0; i < vars_.size(); ++i) {
1729 absl::StrAppendFormat(&out, "[%s == %d]", vars_[i]->DebugString(),
1730 values_[i]);
1731 }
1732 return out;
1733}
1734
1735void AssignVariablesValues::Apply(Solver* const s) {
1736 for (int i = 0; i < vars_.size(); ++i) {
1737 vars_[i]->SetValue(values_[i]);
1738 }
1739}
1740
1741void AssignVariablesValues::Refute(Solver* const s) {
1742 std::vector<IntVar*> terms;
1743 for (int i = 0; i < vars_.size(); ++i) {
1744 IntVar* term = s->MakeBoolVar();
1745 s->MakeIsDifferentCstCt(vars_[i], values_[i], term);
1746 terms.push_back(term);
1747 }
1748 s->AddConstraint(s->MakeSumGreaterOrEqual(terms, 1));
1749}
1750} // namespace
1751
1752Decision* Solver::MakeAssignVariablesValues(const std::vector<IntVar*>& vars,
1753 const std::vector<int64>& values) {
1754 CHECK_EQ(vars.size(), values.size());
1755 return RevAlloc(new AssignVariablesValues(vars, values));
1756}
1757
1758// ----- AssignAllVariables -----
1759
1760namespace {
1761class BaseAssignVariables : public DecisionBuilder {
1762 public:
1763 enum Mode {
1764 ASSIGN,
1765 SPLIT_LOWER,
1766 SPLIT_UPPER,
1767 };
1768
1769 BaseAssignVariables(BaseVariableAssignmentSelector* const selector, Mode mode)
1770 : selector_(selector), mode_(mode) {}
1771
1772 ~BaseAssignVariables() override;
1773 Decision* Next(Solver* const s) override;
1774 std::string DebugString() const override;
1775 static BaseAssignVariables* MakePhase(
1776 Solver* const s, const std::vector<IntVar*>& vars,
1777 Solver::VariableIndexSelector var_selector,
1778 Solver::VariableValueSelector value_selector,
1779 const std::string& value_selector_name, BaseAssignVariables::Mode mode);
1780
1781 static Solver::VariableIndexSelector MakeVariableSelector(
1782 Solver* const s, const std::vector<IntVar*>& vars,
1784 switch (str) {
1788 return ChooseFirstUnbound;
1790 return ChooseRandom;
1792 return ChooseMinSizeLowestMin;
1794 return ChooseMinSizeHighestMin;
1796 return ChooseMinSizeLowestMax;
1798 return ChooseMinSizeHighestMax;
1800 return ChooseLowestMin;
1802 return ChooseHighestMax;
1804 return ChooseMinSize;
1806 return ChooseMaxSize;
1808 HighestRegretSelectorOnMin* const selector =
1809 s->RevAlloc(new HighestRegretSelectorOnMin(vars));
1810 return [selector](Solver* solver, const std::vector<IntVar*>& vars,
1811 int first_unbound, int last_unbound) {
1812 return selector->Choose(solver, vars, first_unbound, last_unbound);
1813 };
1814 }
1815 case Solver::CHOOSE_PATH: {
1816 PathSelector* const selector = s->RevAlloc(new PathSelector());
1817 return [selector](Solver* solver, const std::vector<IntVar*>& vars,
1818 int first_unbound, int last_unbound) {
1819 return selector->Choose(solver, vars, first_unbound, last_unbound);
1820 };
1821 }
1822 default:
1823 LOG(FATAL) << "Unknown int var strategy " << str;
1824 return nullptr;
1825 }
1826 }
1827
1828 static Solver::VariableValueSelector MakeValueSelector(
1829 Solver* const s, Solver::IntValueStrategy val_str) {
1830 switch (val_str) {
1834 return SelectMinValue;
1836 return SelectMaxValue;
1838 return SelectRandomValue;
1840 return SelectCenterValue;
1842 return SelectSplitValue;
1844 return SelectSplitValue;
1845 default:
1846 LOG(FATAL) << "Unknown int value strategy " << val_str;
1847 return nullptr;
1848 }
1849 }
1850
1851 void Accept(ModelVisitor* const visitor) const override {
1852 selector_->Accept(visitor);
1853 }
1854
1855 protected:
1856 BaseVariableAssignmentSelector* const selector_;
1857 const Mode mode_;
1858};
1859
1860BaseAssignVariables::~BaseAssignVariables() {}
1861
1862Decision* BaseAssignVariables::Next(Solver* const s) {
1863 const std::vector<IntVar*>& vars = selector_->vars();
1864 int id = selector_->ChooseVariableWrapper();
1865 if (id >= 0 && id < vars.size()) {
1866 IntVar* const var = vars[id];
1867 const int64 value = selector_->SelectValue(var, id);
1868 switch (mode_) {
1869 case ASSIGN:
1870 return s->RevAlloc(new AssignOneVariableValue(var, value));
1871 case SPLIT_LOWER:
1872 return s->RevAlloc(new SplitOneVariable(var, value, true));
1873 case SPLIT_UPPER:
1874 return s->RevAlloc(new SplitOneVariable(var, value, false));
1875 }
1876 }
1877 return nullptr;
1878}
1879
1880std::string BaseAssignVariables::DebugString() const {
1881 return selector_->DebugString();
1882}
1883
1884BaseAssignVariables* BaseAssignVariables::MakePhase(
1885 Solver* const s, const std::vector<IntVar*>& vars,
1886 Solver::VariableIndexSelector var_selector,
1887 Solver::VariableValueSelector value_selector,
1888 const std::string& value_selector_name, BaseAssignVariables::Mode mode) {
1889 BaseVariableAssignmentSelector* const selector =
1890 s->RevAlloc(new VariableAssignmentSelector(
1891 s, vars, std::move(var_selector), std::move(value_selector),
1892 value_selector_name));
1893 return s->RevAlloc(new BaseAssignVariables(selector, mode));
1894}
1895
1896std::string ChooseVariableName(Solver::IntVarStrategy var_str) {
1897 switch (var_str) {
1901 return "ChooseFirstUnbound";
1903 return "ChooseRandom";
1905 return "ChooseMinSizeLowestMin";
1907 return "ChooseMinSizeHighestMin";
1909 return "ChooseMinSizeLowestMax";
1911 return "ChooseMinSizeHighestMax";
1913 return "ChooseLowestMin";
1915 return "ChooseHighestMax";
1917 return "ChooseMinSize";
1919 return "ChooseMaxSize;";
1921 return "HighestRegretSelectorOnMin";
1923 return "PathSelector";
1924 default:
1925 LOG(FATAL) << "Unknown int var strategy " << var_str;
1926 return "";
1927 }
1928}
1929
1930std::string SelectValueName(Solver::IntValueStrategy val_str) {
1931 switch (val_str) {
1935 return "SelectMinValue";
1937 return "SelectMaxValue";
1939 return "SelectRandomValue";
1941 return "SelectCenterValue";
1943 return "SelectSplitValue";
1945 return "SelectSplitValue";
1946 default:
1947 LOG(FATAL) << "Unknown int value strategy " << val_str;
1948 return "";
1949 }
1950}
1951
1952std::string BuildHeuristicsName(Solver::IntVarStrategy var_str,
1953 Solver::IntValueStrategy val_str) {
1954 return ChooseVariableName(var_str) + "_" + SelectValueName(val_str);
1955}
1956} // namespace
1957
1959 Solver::IntVarStrategy var_str,
1960 Solver::IntValueStrategy val_str) {
1961 std::vector<IntVar*> vars(1);
1962 vars[0] = v0;
1963 return MakePhase(vars, var_str, val_str);
1964}
1965
1967 Solver::IntVarStrategy var_str,
1968 Solver::IntValueStrategy val_str) {
1969 std::vector<IntVar*> vars(2);
1970 vars[0] = v0;
1971 vars[1] = v1;
1972 return MakePhase(vars, var_str, val_str);
1973}
1974
1976 IntVar* const v2,
1977 Solver::IntVarStrategy var_str,
1978 Solver::IntValueStrategy val_str) {
1979 std::vector<IntVar*> vars(3);
1980 vars[0] = v0;
1981 vars[1] = v1;
1982 vars[2] = v2;
1983 return MakePhase(vars, var_str, val_str);
1984}
1985
1987 IntVar* const v2, IntVar* const v3,
1988 Solver::IntVarStrategy var_str,
1989 Solver::IntValueStrategy val_str) {
1990 std::vector<IntVar*> vars(4);
1991 vars[0] = v0;
1992 vars[1] = v1;
1993 vars[2] = v2;
1994 vars[3] = v3;
1995 return MakePhase(vars, var_str, val_str);
1996}
1997
1998BaseAssignVariables::Mode ChooseMode(Solver::IntValueStrategy val_str) {
1999 BaseAssignVariables::Mode mode = BaseAssignVariables::ASSIGN;
2000 if (val_str == Solver::SPLIT_LOWER_HALF) {
2001 mode = BaseAssignVariables::SPLIT_LOWER;
2002 } else if (val_str == Solver::SPLIT_UPPER_HALF) {
2003 mode = BaseAssignVariables::SPLIT_UPPER;
2004 }
2005 return mode;
2006}
2007
2008DecisionBuilder* Solver::MakePhase(const std::vector<IntVar*>& vars,
2009 Solver::IntVarStrategy var_str,
2010 Solver::IntValueStrategy val_str) {
2011 Solver::VariableIndexSelector var_selector =
2012 BaseAssignVariables::MakeVariableSelector(this, vars, var_str);
2013 Solver::VariableValueSelector value_selector =
2014 BaseAssignVariables::MakeValueSelector(this, val_str);
2015 const std::string name = BuildHeuristicsName(var_str, val_str);
2016 return BaseAssignVariables::MakePhase(
2017 this, vars, var_selector, value_selector, name, ChooseMode(val_str));
2018}
2019
2020DecisionBuilder* Solver::MakePhase(const std::vector<IntVar*>& vars,
2021 Solver::IndexEvaluator1 var_evaluator,
2022 Solver::IntValueStrategy val_str) {
2023 CHECK(var_evaluator != nullptr);
2024 CheapestVarSelector* const var_selector =
2025 RevAlloc(new CheapestVarSelector(std::move(var_evaluator)));
2026 Solver::VariableIndexSelector choose_variable =
2027 [var_selector](Solver* solver, const std::vector<IntVar*>& vars,
2028 int first_unbound, int last_unbound) {
2029 return var_selector->Choose(solver, vars, first_unbound, last_unbound);
2030 };
2031 Solver::VariableValueSelector select_value =
2032 BaseAssignVariables::MakeValueSelector(this, val_str);
2033 const std::string name = "ChooseCheapestVariable_" + SelectValueName(val_str);
2034 return BaseAssignVariables::MakePhase(
2035 this, vars, choose_variable, select_value, name, ChooseMode(val_str));
2036}
2037
2038DecisionBuilder* Solver::MakePhase(const std::vector<IntVar*>& vars,
2039 Solver::IntVarStrategy var_str,
2040 Solver::IndexEvaluator2 value_evaluator) {
2041 Solver::VariableIndexSelector choose_variable =
2042 BaseAssignVariables::MakeVariableSelector(this, vars, var_str);
2043 CheapestValueSelector* const value_selector =
2044 RevAlloc(new CheapestValueSelector(std::move(value_evaluator), nullptr));
2045 Solver::VariableValueSelector select_value =
2046 [value_selector](const IntVar* var, int64 id) {
2047 return value_selector->Select(var, id);
2048 };
2049 const std::string name = ChooseVariableName(var_str) + "_SelectCheapestValue";
2050 return BaseAssignVariables::MakePhase(this, vars, choose_variable,
2051 select_value, name,
2052 BaseAssignVariables::ASSIGN);
2053}
2054
2056 const std::vector<IntVar*>& vars, IntVarStrategy var_str,
2057 VariableValueComparator var_val1_val2_comparator) {
2058 Solver::VariableIndexSelector choose_variable =
2059 BaseAssignVariables::MakeVariableSelector(this, vars, var_str);
2060 BestValueByComparisonSelector* const value_selector = RevAlloc(
2061 new BestValueByComparisonSelector(std::move(var_val1_val2_comparator)));
2062 Solver::VariableValueSelector select_value =
2063 [value_selector](const IntVar* var, int64 id) {
2064 return value_selector->Select(var, id);
2065 };
2066 return BaseAssignVariables::MakePhase(this, vars, choose_variable,
2067 select_value, "CheapestValue",
2068 BaseAssignVariables::ASSIGN);
2069}
2070
2071DecisionBuilder* Solver::MakePhase(const std::vector<IntVar*>& vars,
2072 Solver::IndexEvaluator1 var_evaluator,
2073 Solver::IndexEvaluator2 value_evaluator) {
2074 CheapestVarSelector* const var_selector =
2075 RevAlloc(new CheapestVarSelector(std::move(var_evaluator)));
2076 Solver::VariableIndexSelector choose_variable =
2077 [var_selector](Solver* solver, const std::vector<IntVar*>& vars,
2078 int first_unbound, int last_unbound) {
2079 return var_selector->Choose(solver, vars, first_unbound, last_unbound);
2080 };
2081 CheapestValueSelector* value_selector =
2082 RevAlloc(new CheapestValueSelector(std::move(value_evaluator), nullptr));
2083 Solver::VariableValueSelector select_value =
2084 [value_selector](const IntVar* var, int64 id) {
2085 return value_selector->Select(var, id);
2086 };
2087 return BaseAssignVariables::MakePhase(this, vars, choose_variable,
2088 select_value, "CheapestValue",
2089 BaseAssignVariables::ASSIGN);
2090}
2091
2092DecisionBuilder* Solver::MakePhase(const std::vector<IntVar*>& vars,
2093 Solver::IntVarStrategy var_str,
2094 Solver::IndexEvaluator2 value_evaluator,
2095 Solver::IndexEvaluator1 tie_breaker) {
2096 Solver::VariableIndexSelector choose_variable =
2097 BaseAssignVariables::MakeVariableSelector(this, vars, var_str);
2098 CheapestValueSelector* value_selector = RevAlloc(new CheapestValueSelector(
2099 std::move(value_evaluator), std::move(tie_breaker)));
2100 Solver::VariableValueSelector select_value =
2101 [value_selector](const IntVar* var, int64 id) {
2102 return value_selector->Select(var, id);
2103 };
2104 return BaseAssignVariables::MakePhase(this, vars, choose_variable,
2105 select_value, "CheapestValue",
2106 BaseAssignVariables::ASSIGN);
2107}
2108
2109DecisionBuilder* Solver::MakePhase(const std::vector<IntVar*>& vars,
2110 Solver::IndexEvaluator1 var_evaluator,
2111 Solver::IndexEvaluator2 value_evaluator,
2112 Solver::IndexEvaluator1 tie_breaker) {
2113 CheapestVarSelector* const var_selector =
2114 RevAlloc(new CheapestVarSelector(std::move(var_evaluator)));
2115 Solver::VariableIndexSelector choose_variable =
2116 [var_selector](Solver* solver, const std::vector<IntVar*>& vars,
2117 int first_unbound, int last_unbound) {
2118 return var_selector->Choose(solver, vars, first_unbound, last_unbound);
2119 };
2120 CheapestValueSelector* value_selector = RevAlloc(new CheapestValueSelector(
2121 std::move(value_evaluator), std::move(tie_breaker)));
2122 Solver::VariableValueSelector select_value =
2123 [value_selector](const IntVar* var, int64 id) {
2124 return value_selector->Select(var, id);
2125 };
2126 return BaseAssignVariables::MakePhase(this, vars, choose_variable,
2127 select_value, "CheapestValue",
2128 BaseAssignVariables::ASSIGN);
2129}
2130
2131DecisionBuilder* Solver::MakePhase(const std::vector<IntVar*>& vars,
2134 return MakePhase(vars, std::move(eval), nullptr, str);
2135}
2136
2137DecisionBuilder* Solver::MakePhase(const std::vector<IntVar*>& vars,
2139 Solver::IndexEvaluator1 tie_breaker,
2141 BaseVariableAssignmentSelector* selector = nullptr;
2142 switch (str) {
2144 // TODO(user): support tie breaker
2145 selector = RevAlloc(new StaticEvaluatorSelector(this, vars, eval));
2146 break;
2147 }
2149 selector = RevAlloc(new DynamicEvaluatorSelector(this, vars, eval,
2150 std::move(tie_breaker)));
2151 break;
2152 }
2153 }
2154 return RevAlloc(
2155 new BaseAssignVariables(selector, BaseAssignVariables::ASSIGN));
2156}
2157
2158// ----- AssignAllVariablesFromAssignment decision builder -----
2159
2160namespace {
2161class AssignVariablesFromAssignment : public DecisionBuilder {
2162 public:
2163 AssignVariablesFromAssignment(const Assignment* const assignment,
2164 DecisionBuilder* const db,
2165 const std::vector<IntVar*>& vars)
2166 : assignment_(assignment), db_(db), vars_(vars), iter_(0) {}
2167
2168 ~AssignVariablesFromAssignment() override {}
2169
2170 Decision* Next(Solver* const s) override {
2171 if (iter_ < vars_.size()) {
2172 IntVar* const var = vars_[iter_++];
2173 return s->RevAlloc(
2174 new AssignOneVariableValue(var, assignment_->Value(var)));
2175 } else {
2176 return db_->Next(s);
2177 }
2178 }
2179
2180 void Accept(ModelVisitor* const visitor) const override {
2181 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);
2182 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
2183 vars_);
2184 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);
2185 }
2186
2187 private:
2188 const Assignment* const assignment_;
2189 DecisionBuilder* const db_;
2190 const std::vector<IntVar*> vars_;
2191 int iter_;
2192};
2193} // namespace
2194
2196 Assignment* const assignment, DecisionBuilder* const db,
2197 const std::vector<IntVar*>& vars) {
2198 return RevAlloc(new AssignVariablesFromAssignment(assignment, db, vars));
2199}
2200
2201// ---------- Solution Collectors -----------
2202
2203// ----- Base Class -----
2204
2206 const Assignment* const assignment)
2207 : SearchMonitor(solver),
2208 prototype_(assignment == nullptr ? nullptr : new Assignment(assignment)) {
2209}
2210
2212 : SearchMonitor(solver), prototype_(new Assignment(solver)) {}
2213
2215 for (auto& data : solution_data_) {
2216 delete data.solution;
2217 }
2219}
2220
2222 if (prototype_ != nullptr) {
2223 prototype_->Add(var);
2224 }
2225}
2226
2227void SolutionCollector::Add(const std::vector<IntVar*>& vars) {
2228 if (prototype_ != nullptr) {
2229 prototype_->Add(vars);
2230 }
2231}
2232
2234 if (prototype_ != nullptr) {
2235 prototype_->Add(var);
2236 }
2237}
2238
2239void SolutionCollector::Add(const std::vector<IntervalVar*>& vars) {
2240 if (prototype_ != nullptr) {
2241 prototype_->Add(vars);
2242 }
2243}
2244
2246 if (prototype_ != nullptr) {
2247 prototype_->Add(var);
2248 }
2249}
2250
2251void SolutionCollector::Add(const std::vector<SequenceVar*>& vars) {
2252 if (prototype_ != nullptr) {
2253 prototype_->Add(vars);
2254 }
2255}
2256
2258 if (prototype_ != nullptr && objective != nullptr) {
2259 prototype_->AddObjective(objective);
2260 }
2261}
2262
2264 for (auto& data : solution_data_) {
2265 delete data.solution;
2266 }
2268 solution_data_.clear();
2269 recycle_solutions_.clear();
2270}
2271
2274}
2275
2277 if (!solution_data_.empty()) {
2278 FreeSolution(solution_data_.back().solution);
2279 solution_data_.pop_back();
2280 }
2281}
2282
2285 Assignment* solution = nullptr;
2286 if (prototype_ != nullptr) {
2287 if (!recycle_solutions_.empty()) {
2289 DCHECK(solution != nullptr);
2290 recycle_solutions_.pop_back();
2291 } else {
2292 solution = new Assignment(prototype_.get());
2293 }
2294 solution->Store();
2295 }
2296 SolutionData data;
2297 data.solution = solution;
2298 data.time = solver()->wall_time();
2299 data.branches = solver()->branches();
2300 data.failures = solver()->failures();
2301 if (solution != nullptr) {
2303 } else {
2304 data.objective_value = 0;
2305 }
2306 return data;
2307}
2308
2310 if (solution != nullptr) {
2311 recycle_solutions_.push_back(solution);
2312 }
2313}
2314
2316 CHECK_GE(n, 0) << "wrong index in solution getter";
2317 CHECK_LT(n, solution_data_.size()) << "wrong index in solution getter";
2318}
2319
2321 check_index(n);
2322 return solution_data_[n].solution;
2323}
2324
2326
2328 check_index(n);
2329 return solution_data_[n].time;
2330}
2331
2333 check_index(n);
2334 return solution_data_[n].branches;
2335}
2336
2338 check_index(n);
2339 return solution_data_[n].failures;
2340}
2341
2343 check_index(n);
2344 return solution_data_[n].objective_value;
2345}
2346
2348 return solution(n)->Value(var);
2349}
2350
2352 return solution(n)->StartValue(var);
2353}
2354
2356 return solution(n)->DurationValue(var);
2357}
2358
2360 return solution(n)->EndValue(var);
2361}
2362
2364 return solution(n)->PerformedValue(var);
2365}
2366
2368 int n, SequenceVar* const var) const {
2369 return solution(n)->ForwardSequence(var);
2370}
2371
2373 int n, SequenceVar* const var) const {
2374 return solution(n)->BackwardSequence(var);
2375}
2376
2377const std::vector<int>& SolutionCollector::Unperformed(
2378 int n, SequenceVar* const var) const {
2379 return solution(n)->Unperformed(var);
2380}
2381
2382namespace {
2383// ----- First Solution Collector -----
2384
2385// Collect first solution, useful when looking satisfaction problems
2386class FirstSolutionCollector : public SolutionCollector {
2387 public:
2388 FirstSolutionCollector(Solver* const s, const Assignment* const a);
2389 explicit FirstSolutionCollector(Solver* const s);
2390 ~FirstSolutionCollector() override;
2391 void EnterSearch() override;
2392 bool AtSolution() override;
2393 std::string DebugString() const override;
2394
2395 private:
2396 bool done_;
2397};
2398
2399FirstSolutionCollector::FirstSolutionCollector(Solver* const s,
2400 const Assignment* const a)
2401 : SolutionCollector(s, a), done_(false) {}
2402
2403FirstSolutionCollector::FirstSolutionCollector(Solver* const s)
2404 : SolutionCollector(s), done_(false) {}
2405
2406FirstSolutionCollector::~FirstSolutionCollector() {}
2407
2408void FirstSolutionCollector::EnterSearch() {
2410 done_ = false;
2411}
2412
2413bool FirstSolutionCollector::AtSolution() {
2414 if (!done_) {
2415 PushSolution();
2416 done_ = true;
2417 }
2418 return false;
2419}
2420
2421std::string FirstSolutionCollector::DebugString() const {
2422 if (prototype_ == nullptr) {
2423 return "FirstSolutionCollector()";
2424 } else {
2425 return "FirstSolutionCollector(" + prototype_->DebugString() + ")";
2426 }
2427}
2428} // namespace
2429
2431 const Assignment* const assignment) {
2432 return RevAlloc(new FirstSolutionCollector(this, assignment));
2433}
2434
2436 return RevAlloc(new FirstSolutionCollector(this));
2437}
2438
2439// ----- Last Solution Collector -----
2440
2441// Collect last solution, useful when optimizing
2442namespace {
2443class LastSolutionCollector : public SolutionCollector {
2444 public:
2445 LastSolutionCollector(Solver* const s, const Assignment* const a);
2446 explicit LastSolutionCollector(Solver* const s);
2447 ~LastSolutionCollector() override;
2448 bool AtSolution() override;
2449 std::string DebugString() const override;
2450};
2451
2452LastSolutionCollector::LastSolutionCollector(Solver* const s,
2453 const Assignment* const a)
2454 : SolutionCollector(s, a) {}
2455
2456LastSolutionCollector::LastSolutionCollector(Solver* const s)
2457 : SolutionCollector(s) {}
2458
2459LastSolutionCollector::~LastSolutionCollector() {}
2460
2461bool LastSolutionCollector::AtSolution() {
2462 PopSolution();
2463 PushSolution();
2464 return true;
2465}
2466
2467std::string LastSolutionCollector::DebugString() const {
2468 if (prototype_ == nullptr) {
2469 return "LastSolutionCollector()";
2470 } else {
2471 return "LastSolutionCollector(" + prototype_->DebugString() + ")";
2472 }
2473}
2474} // namespace
2475
2477 const Assignment* const assignment) {
2478 return RevAlloc(new LastSolutionCollector(this, assignment));
2479}
2480
2482 return RevAlloc(new LastSolutionCollector(this));
2483}
2484
2485// ----- Best Solution Collector -----
2486
2487namespace {
2488class BestValueSolutionCollector : public SolutionCollector {
2489 public:
2490 BestValueSolutionCollector(Solver* const s, const Assignment* const a,
2491 bool maximize);
2492 BestValueSolutionCollector(Solver* const s, bool maximize);
2493 ~BestValueSolutionCollector() override {}
2494 void EnterSearch() override;
2495 bool AtSolution() override;
2496 std::string DebugString() const override;
2497
2498 public:
2499 const bool maximize_;
2501};
2502
2503BestValueSolutionCollector::BestValueSolutionCollector(
2504 Solver* const s, const Assignment* const a, bool maximize)
2505 : SolutionCollector(s, a),
2506 maximize_(maximize),
2507 best_(maximize ? kint64min : kint64max) {}
2508
2509BestValueSolutionCollector::BestValueSolutionCollector(Solver* const s,
2510 bool maximize)
2511 : SolutionCollector(s),
2512 maximize_(maximize),
2513 best_(maximize ? kint64min : kint64max) {}
2514
2515void BestValueSolutionCollector::EnterSearch() {
2516 SolutionCollector::EnterSearch();
2518}
2519
2520bool BestValueSolutionCollector::AtSolution() {
2521 if (prototype_ != nullptr) {
2522 const IntVar* objective = prototype_->Objective();
2523 if (objective != nullptr) {
2524 if (maximize_ && (solution_count() == 0 || objective->Max() > best_)) {
2525 PopSolution();
2526 PushSolution();
2527 best_ = objective->Max();
2528 } else if (!maximize_ &&
2529 (solution_count() == 0 || objective->Min() < best_)) {
2530 PopSolution();
2531 PushSolution();
2532 best_ = objective->Min();
2533 }
2534 }
2535 }
2536 return true;
2537}
2538
2539std::string BestValueSolutionCollector::DebugString() const {
2540 if (prototype_ == nullptr) {
2541 return "BestValueSolutionCollector()";
2542 } else {
2543 return "BestValueSolutionCollector(" + prototype_->DebugString() + ")";
2544 }
2545}
2546} // namespace
2547
2548SolutionCollector* Solver::MakeBestValueSolutionCollector(
2549 const Assignment* const assignment, bool maximize) {
2550 return RevAlloc(new BestValueSolutionCollector(this, assignment, maximize));
2551}
2552
2553SolutionCollector* Solver::MakeBestValueSolutionCollector(bool maximize) {
2554 return RevAlloc(new BestValueSolutionCollector(this, maximize));
2555}
2556
2557// ----- N Best Solution Collector -----
2558
2559namespace {
2560class NBestValueSolutionCollector : public SolutionCollector {
2561 public:
2562 NBestValueSolutionCollector(Solver* const solver,
2563 const Assignment* const assignment,
2564 int solution_count, bool maximize);
2565 NBestValueSolutionCollector(Solver* const solver, int solution_count,
2566 bool maximize);
2567 ~NBestValueSolutionCollector() override { Clear(); }
2568 void EnterSearch() override;
2569 void ExitSearch() override;
2570 bool AtSolution() override;
2571 std::string DebugString() const override;
2572
2573 public:
2574 void Clear();
2575
2576 const bool maximize_;
2577 std::priority_queue<std::pair<int64, SolutionData>> solutions_pq_;
2579};
2580
2581NBestValueSolutionCollector::NBestValueSolutionCollector(
2582 Solver* const solver, const Assignment* const assignment,
2583 int solution_count, bool maximize)
2584 : SolutionCollector(solver, assignment),
2585 maximize_(maximize),
2586 solution_count_(solution_count) {}
2587
2588NBestValueSolutionCollector::NBestValueSolutionCollector(Solver* const solver,
2589 int solution_count,
2590 bool maximize)
2591 : SolutionCollector(solver),
2592 maximize_(maximize),
2593 solution_count_(solution_count) {}
2594
2595void NBestValueSolutionCollector::EnterSearch() {
2596 SolutionCollector::EnterSearch();
2597 // TODO(user): Remove this when fast local search works with
2598 // multiple solutions collected.
2599 if (solution_count_ > 1) {
2600 solver()->SetUseFastLocalSearch(false);
2601 }
2602 Clear();
2603}
2604
2605void NBestValueSolutionCollector::ExitSearch() {
2606 while (!solutions_pq_.empty()) {
2607 Push(solutions_pq_.top().second);
2608 solutions_pq_.pop();
2609 }
2610}
2611
2612bool NBestValueSolutionCollector::AtSolution() {
2613 if (prototype_ != nullptr) {
2614 const IntVar* objective = prototype_->Objective();
2615 if (objective != nullptr) {
2616 const int64 objective_value =
2617 maximize_ ? CapSub(0, objective->Max()) : objective->Min();
2618 if (solutions_pq_.size() < solution_count_) {
2619 solutions_pq_.push(
2620 {objective_value, BuildSolutionDataForCurrentState()});
2621 } else if (!solutions_pq_.empty()) {
2622 const auto& top = solutions_pq_.top();
2623 if (top.first > objective_value) {
2624 FreeSolution(solutions_pq_.top().second.solution);
2625 solutions_pq_.pop();
2626 solutions_pq_.push(
2627 {objective_value, BuildSolutionDataForCurrentState()});
2628 }
2629 }
2630 }
2631 }
2632 return true;
2633}
2634
2635std::string NBestValueSolutionCollector::DebugString() const {
2636 if (prototype_ == nullptr) {
2637 return "NBestValueSolutionCollector()";
2638 } else {
2639 return "NBestValueSolutionCollector(" + prototype_->DebugString() + ")";
2640 }
2641}
2642
2643void NBestValueSolutionCollector::Clear() {
2644 while (!solutions_pq_.empty()) {
2645 delete solutions_pq_.top().second.solution;
2646 solutions_pq_.pop();
2647 }
2648}
2649
2650} // namespace
2651
2652SolutionCollector* Solver::MakeNBestValueSolutionCollector(
2653 const Assignment* const assignment, int solution_count, bool maximize) {
2654 if (solution_count == 1) {
2655 return MakeBestValueSolutionCollector(assignment, maximize);
2656 }
2657 return RevAlloc(new NBestValueSolutionCollector(this, assignment,
2658 solution_count, maximize));
2659}
2660
2661SolutionCollector* Solver::MakeNBestValueSolutionCollector(int solution_count,
2662 bool maximize) {
2663 if (solution_count == 1) {
2664 return MakeBestValueSolutionCollector(maximize);
2665 }
2666 return RevAlloc(
2667 new NBestValueSolutionCollector(this, solution_count, maximize));
2668}
2669
2670// ----- All Solution Collector -----
2671
2672// collect all solutions
2673namespace {
2674class AllSolutionCollector : public SolutionCollector {
2675 public:
2676 AllSolutionCollector(Solver* const s, const Assignment* const a);
2677 explicit AllSolutionCollector(Solver* const s);
2678 ~AllSolutionCollector() override;
2679 bool AtSolution() override;
2680 std::string DebugString() const override;
2681};
2682
2683AllSolutionCollector::AllSolutionCollector(Solver* const s,
2684 const Assignment* const a)
2685 : SolutionCollector(s, a) {}
2686
2687AllSolutionCollector::AllSolutionCollector(Solver* const s)
2688 : SolutionCollector(s) {}
2689
2690AllSolutionCollector::~AllSolutionCollector() {}
2691
2692bool AllSolutionCollector::AtSolution() {
2693 PushSolution();
2694 return true;
2695}
2696
2697std::string AllSolutionCollector::DebugString() const {
2698 if (prototype_ == nullptr) {
2699 return "AllSolutionCollector()";
2700 } else {
2701 return "AllSolutionCollector(" + prototype_->DebugString() + ")";
2702 }
2703}
2704} // namespace
2705
2707 const Assignment* const assignment) {
2708 return RevAlloc(new AllSolutionCollector(this, assignment));
2709}
2710
2712 return RevAlloc(new AllSolutionCollector(this));
2713}
2714
2715// ---------- Objective Management ----------
2716
2717OptimizeVar::OptimizeVar(Solver* const s, bool maximize, IntVar* const a,
2718 int64 step)
2719 : SearchMonitor(s),
2720 var_(a),
2721 step_(step),
2723 maximize_(maximize),
2724 found_initial_solution_(false) {
2725 CHECK_GT(step_, 0);
2726 // TODO(user): Store optimization direction in Solver. Besides making the
2727 // code simpler it would also having two monitors optimizing in opposite
2728 // directions.
2729 if (maximize) {
2731 } else {
2733 }
2734}
2735
2737
2740 if (maximize_) {
2741 best_ = kint64min;
2742 } else {
2743 best_ = kint64max;
2744 }
2745}
2746
2748 if (solver()->SearchDepth() == 0) { // after a restart.
2749 ApplyBound();
2750 }
2751}
2752
2755 if (maximize_) {
2756 var_->SetMin(best_ + step_);
2757 } else {
2758 var_->SetMax(best_ - step_);
2759 }
2760 }
2761}
2762
2764
2766 const int64 val = var_->Value();
2768 return true;
2769 } else {
2770 // This code should never return false in sequential mode because
2771 // ApplyBound should have been called before. In parallel, this is
2772 // no longer true. That is why we keep it there, just in case.
2773 return (maximize_ && val > best_) || (!maximize_ && val < best_);
2774 }
2775}
2776
2778 int64 val = var_->Value();
2779 if (maximize_) {
2781 best_ = val;
2782 } else {
2784 best_ = val;
2785 }
2787 return true;
2788}
2789
2791 if (delta != nullptr) {
2792 const bool delta_has_objective = delta->HasObjective();
2793 if (!delta_has_objective) {
2794 delta->AddObjective(var_);
2795 }
2796 if (delta->Objective() == var_) {
2797 const Assignment* const local_search_state =
2799 if (maximize_) {
2800 const int64 delta_min_objective =
2801 delta_has_objective ? delta->ObjectiveMin() : kint64min;
2802 const int64 min_objective =
2803 local_search_state->HasObjective()
2804 ? CapAdd(local_search_state->ObjectiveMin(), step_)
2805 : kint64min;
2806 delta->SetObjectiveMin(
2807 std::max({var_->Min(), min_objective, delta_min_objective}));
2808
2809 } else {
2810 const int64 delta_max_objective =
2811 delta_has_objective ? delta->ObjectiveMax() : kint64max;
2812 const int64 max_objective =
2813 local_search_state->HasObjective()
2814 ? CapSub(local_search_state->ObjectiveMax(), step_)
2815 : kint64max;
2816 delta->SetObjectiveMax(
2817 std::min({var_->Max(), max_objective, delta_max_objective}));
2818 }
2819 }
2820 }
2821 return true;
2822}
2823
2824std::string OptimizeVar::Print() const {
2825 return absl::StrFormat("objective value = %d, ", var_->Value());
2826}
2827
2828std::string OptimizeVar::DebugString() const {
2829 std::string out;
2830 if (maximize_) {
2831 out = "MaximizeVar(";
2832 } else {
2833 out = "MinimizeVar(";
2834 }
2835 absl::StrAppendFormat(&out, "%s, step = %d, best = %d)", var_->DebugString(),
2836 step_, best_);
2837 return out;
2838}
2839
2840void OptimizeVar::Accept(ModelVisitor* const visitor) const {
2845 var_);
2847}
2848
2850 return RevAlloc(new OptimizeVar(this, false, v, step));
2851}
2852
2854 return RevAlloc(new OptimizeVar(this, true, v, step));
2855}
2856
2857OptimizeVar* Solver::MakeOptimize(bool maximize, IntVar* const v, int64 step) {
2858 return RevAlloc(new OptimizeVar(this, maximize, v, step));
2859}
2860
2861namespace {
2862class WeightedOptimizeVar : public OptimizeVar {
2863 public:
2864 WeightedOptimizeVar(Solver* solver, bool maximize,
2865 const std::vector<IntVar*>& sub_objectives,
2866 const std::vector<int64>& weights, int64 step)
2867 : OptimizeVar(solver, maximize,
2868 solver->MakeScalProd(sub_objectives, weights)->Var(), step),
2869 sub_objectives_(sub_objectives),
2870 weights_(weights) {
2871 CHECK_EQ(sub_objectives.size(), weights.size());
2872 }
2873
2874 ~WeightedOptimizeVar() override {}
2875 std::string Print() const override;
2876
2877 private:
2878 const std::vector<IntVar*> sub_objectives_;
2879 const std::vector<int64> weights_;
2880
2881 DISALLOW_COPY_AND_ASSIGN(WeightedOptimizeVar);
2882};
2883
2884std::string WeightedOptimizeVar::Print() const {
2885 std::string result(OptimizeVar::Print());
2886 result.append("\nWeighted Objective:\n");
2887 for (int i = 0; i < sub_objectives_.size(); ++i) {
2888 absl::StrAppendFormat(&result, "Variable %s,\tvalue %d,\tweight %d\n",
2889 sub_objectives_[i]->name(),
2890 sub_objectives_[i]->Value(), weights_[i]);
2891 }
2892 return result;
2893}
2894} // namespace
2895
2897 bool maximize, const std::vector<IntVar*>& sub_objectives,
2898 const std::vector<int64>& weights, int64 step) {
2899 return RevAlloc(
2900 new WeightedOptimizeVar(this, maximize, sub_objectives, weights, step));
2901}
2902
2904 const std::vector<IntVar*>& sub_objectives,
2905 const std::vector<int64>& weights, int64 step) {
2906 return RevAlloc(
2907 new WeightedOptimizeVar(this, false, sub_objectives, weights, step));
2908}
2909
2911 const std::vector<IntVar*>& sub_objectives,
2912 const std::vector<int64>& weights, int64 step) {
2913 return RevAlloc(
2914 new WeightedOptimizeVar(this, true, sub_objectives, weights, step));
2915}
2916
2918 bool maximize, const std::vector<IntVar*>& sub_objectives,
2919 const std::vector<int>& weights, int64 step) {
2920 return MakeWeightedOptimize(maximize, sub_objectives, ToInt64Vector(weights),
2921 step);
2922}
2923
2925 const std::vector<IntVar*>& sub_objectives, const std::vector<int>& weights,
2926 int64 step) {
2927 return MakeWeightedMinimize(sub_objectives, ToInt64Vector(weights), step);
2928}
2929
2931 const std::vector<IntVar*>& sub_objectives, const std::vector<int>& weights,
2932 int64 step) {
2933 return MakeWeightedMaximize(sub_objectives, ToInt64Vector(weights), step);
2934}
2935
2936// ---------- Metaheuristics ---------
2937
2938namespace {
2939class Metaheuristic : public SearchMonitor {
2940 public:
2941 Metaheuristic(Solver* const solver, bool maximize, IntVar* objective,
2942 int64 step);
2943 ~Metaheuristic() override {}
2944
2945 bool AtSolution() override;
2946 void EnterSearch() override;
2947 void RefuteDecision(Decision* const d) override;
2948 bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;
2949
2950 protected:
2951 IntVar* const objective_;
2954 int64 best_;
2955 bool maximize_;
2956};
2957
2958Metaheuristic::Metaheuristic(Solver* const solver, bool maximize,
2959 IntVar* objective, int64 step)
2960 : SearchMonitor(solver),
2961 objective_(objective),
2962 step_(step),
2965 maximize_(maximize) {}
2966
2967bool Metaheuristic::AtSolution() {
2968 current_ = objective_->Value();
2969 if (maximize_) {
2971 } else {
2973 }
2974 return true;
2975}
2976
2977void Metaheuristic::EnterSearch() {
2978 // TODO(user): Remove this when fast local search works with
2979 // metaheuristics.
2980 solver()->SetUseFastLocalSearch(false);
2981 if (maximize_) {
2982 best_ = objective_->Min();
2984 } else {
2985 best_ = objective_->Max();
2987 }
2988}
2989
2990void Metaheuristic::RefuteDecision(Decision* d) {
2991 if (maximize_) {
2992 if (objective_->Max() < best_ + step_) {
2993 solver()->Fail();
2994 }
2995 } else if (objective_->Min() > best_ - step_) {
2996 solver()->Fail();
2997 }
2998}
2999
3000bool Metaheuristic::AcceptDelta(Assignment* delta, Assignment* deltadelta) {
3001 if (delta != nullptr) {
3002 if (!delta->HasObjective()) {
3003 delta->AddObjective(objective_);
3004 }
3005 if (delta->Objective() == objective_) {
3006 if (maximize_) {
3007 delta->SetObjectiveMin(
3008 std::max(objective_->Min(), delta->ObjectiveMin()));
3009 } else {
3010 delta->SetObjectiveMax(
3011 std::min(objective_->Max(), delta->ObjectiveMax()));
3012 }
3013 }
3014 }
3015 return true;
3016}
3017
3018// ---------- Tabu Search ----------
3019
3020class TabuSearch : public Metaheuristic {
3021 public:
3022 TabuSearch(Solver* const s, bool maximize, IntVar* objective, int64 step,
3023 const std::vector<IntVar*>& vars, int64 keep_tenure,
3024 int64 forbid_tenure, double tabu_factor);
3025 ~TabuSearch() override {}
3026 void EnterSearch() override;
3027 void ApplyDecision(Decision* d) override;
3028 bool AtSolution() override;
3029 bool LocalOptimum() override;
3030 void AcceptNeighbor() override;
3031 std::string DebugString() const override { return "Tabu Search"; }
3032
3033 protected:
3034 struct VarValue {
3035 VarValue(IntVar* const var, int64 value, int64 stamp)
3036 : var_(var), value_(value), stamp_(stamp) {}
3037 IntVar* const var_;
3038 const int64 value_;
3040 };
3041 typedef std::list<VarValue> TabuList;
3042
3043 virtual std::vector<IntVar*> CreateTabuVars();
3044 const TabuList& forbid_tabu_list() { return forbid_tabu_list_; }
3045
3046 private:
3047 void AgeList(int64 tenure, TabuList* list);
3048 void AgeLists();
3049
3050 const std::vector<IntVar*> vars_;
3051 Assignment assignment_;
3052 int64 last_;
3053 TabuList keep_tabu_list_;
3054 int64 keep_tenure_;
3055 TabuList forbid_tabu_list_;
3056 int64 forbid_tenure_;
3057 double tabu_factor_;
3058 int64 stamp_;
3059 bool found_initial_solution_;
3060
3061 DISALLOW_COPY_AND_ASSIGN(TabuSearch);
3062};
3063
3064TabuSearch::TabuSearch(Solver* const s, bool maximize, IntVar* objective,
3065 int64 step, const std::vector<IntVar*>& vars,
3066 int64 keep_tenure, int64 forbid_tenure,
3067 double tabu_factor)
3068 : Metaheuristic(s, maximize, objective, step),
3069 vars_(vars),
3070 assignment_(s),
3071 last_(kint64max),
3072 keep_tenure_(keep_tenure),
3073 forbid_tenure_(forbid_tenure),
3074 tabu_factor_(tabu_factor),
3075 stamp_(0),
3076 found_initial_solution_(false) {
3077 assignment_.Add(vars_);
3078}
3079
3080void TabuSearch::EnterSearch() {
3081 Metaheuristic::EnterSearch();
3082 found_initial_solution_ = false;
3083}
3084
3085void TabuSearch::ApplyDecision(Decision* const d) {
3086 Solver* const s = solver();
3087 if (d == s->balancing_decision()) {
3088 return;
3089 }
3090 // Aspiration criterion
3091 // Accept a neighbor if it improves the best solution found so far
3092 IntVar* aspiration = s->MakeBoolVar();
3093 if (maximize_) {
3094 s->AddConstraint(s->MakeIsGreaterOrEqualCstCt(
3095 objective_, CapAdd(best_, step_), aspiration));
3096 } else {
3097 s->AddConstraint(s->MakeIsLessOrEqualCstCt(objective_, CapSub(best_, step_),
3098 aspiration));
3099 }
3100
3101 IntVar* tabu_var = nullptr;
3102 {
3103 // Creating the vector in a scope to make sure it gets deleted before
3104 // adding further constraints which could fail and lead to a leak.
3105 const std::vector<IntVar*> tabu_vars = CreateTabuVars();
3106 if (!tabu_vars.empty()) {
3107 tabu_var = s->MakeIsGreaterOrEqualCstVar(s->MakeSum(tabu_vars)->Var(),
3108 tabu_vars.size() * tabu_factor_);
3109 }
3110 }
3111
3112 if (tabu_var != nullptr) {
3113 s->AddConstraint(
3114 s->MakeGreaterOrEqual(s->MakeSum(aspiration, tabu_var), int64{1}));
3115 }
3116
3117 // Go downhill to the next local optimum
3118 if (maximize_) {
3120 s->AddConstraint(s->MakeGreaterOrEqual(objective_, bound));
3121 } else {
3123 s->AddConstraint(s->MakeLessOrEqual(objective_, bound));
3124 }
3125
3126 // Avoid cost plateau's which lead to tabu cycles
3127 if (found_initial_solution_) {
3128 s->AddConstraint(s->MakeNonEquality(objective_, last_));
3129 }
3130}
3131
3132std::vector<IntVar*> TabuSearch::CreateTabuVars() {
3133 Solver* const s = solver();
3134
3135 // Tabu criterion
3136 // A variable in the "keep" list must keep its value, a variable in the
3137 // "forbid" list must not take its value in the list. The tabu criterion is
3138 // softened by the tabu factor which gives the number of violations to
3139 // the tabu criterion which is tolerated; a factor of 1 means no violations
3140 // allowed, a factor of 0 means all violations allowed.
3141 std::vector<IntVar*> tabu_vars;
3142 for (const VarValue& vv : keep_tabu_list_) {
3143 tabu_vars.push_back(s->MakeIsEqualCstVar(vv.var_, vv.value_));
3144 }
3145 for (const VarValue& vv : forbid_tabu_list_) {
3146 tabu_vars.push_back(s->MakeIsDifferentCstVar(vv.var_, vv.value_));
3147 }
3148 return tabu_vars;
3149}
3150
3151bool TabuSearch::AtSolution() {
3152 if (!Metaheuristic::AtSolution()) {
3153 return false;
3154 }
3155 found_initial_solution_ = true;
3156 last_ = current_;
3157
3158 // New solution found: add new assignments to tabu lists; this is only
3159 // done after the first local optimum (stamp_ != 0)
3160 if (0 != stamp_) {
3161 for (int i = 0; i < vars_.size(); ++i) {
3162 IntVar* const var = vars_[i];
3163 const int64 old_value = assignment_.Value(var);
3164 const int64 new_value = var->Value();
3165 if (old_value != new_value) {
3166 if (keep_tenure_ > 0) {
3167 VarValue keep_value(var, new_value, stamp_);
3168 keep_tabu_list_.push_front(keep_value);
3169 }
3170 if (forbid_tenure_ > 0) {
3171 VarValue forbid_value(var, old_value, stamp_);
3172 forbid_tabu_list_.push_front(forbid_value);
3173 }
3174 }
3175 }
3176 }
3177 assignment_.Store();
3178
3179 return true;
3180}
3181
3182bool TabuSearch::LocalOptimum() {
3183 AgeLists();
3184 if (maximize_) {
3186 } else {
3188 }
3189 return found_initial_solution_;
3190}
3191
3193 if (0 != stamp_) {
3194 AgeLists();
3195 }
3196}
3197
3198void TabuSearch::AgeList(int64 tenure, TabuList* list) {
3199 while (!list->empty() && list->back().stamp_ < stamp_ - tenure) {
3200 list->pop_back();
3201 }
3202}
3203
3204void TabuSearch::AgeLists() {
3205 AgeList(keep_tenure_, &keep_tabu_list_);
3206 AgeList(forbid_tenure_, &forbid_tabu_list_);
3207 ++stamp_;
3208}
3209
3210class GenericTabuSearch : public TabuSearch {
3211 public:
3212 GenericTabuSearch(Solver* const s, bool maximize, IntVar* objective,
3213 int64 step, const std::vector<IntVar*>& vars,
3214 int64 forbid_tenure)
3215 : TabuSearch(s, maximize, objective, step, vars, 0, forbid_tenure, 1) {}
3216 std::string DebugString() const override { return "Generic Tabu Search"; }
3217
3218 protected:
3219 std::vector<IntVar*> CreateTabuVars() override;
3220};
3221
3222std::vector<IntVar*> GenericTabuSearch::CreateTabuVars() {
3223 Solver* const s = solver();
3224
3225 // Tabu criterion
3226 // At least one element of the forbid_tabu_list must change value.
3227 std::vector<IntVar*> forbid_values;
3228 for (const VarValue& vv : forbid_tabu_list()) {
3229 forbid_values.push_back(s->MakeIsDifferentCstVar(vv.var_, vv.value_));
3230 }
3231 std::vector<IntVar*> tabu_vars;
3232 if (!forbid_values.empty()) {
3233 tabu_vars.push_back(s->MakeIsGreaterCstVar(s->MakeSum(forbid_values), 0));
3234 }
3235 return tabu_vars;
3236}
3237
3238} // namespace
3239
3240SearchMonitor* Solver::MakeTabuSearch(bool maximize, IntVar* const v,
3241 int64 step,
3242 const std::vector<IntVar*>& vars,
3243 int64 keep_tenure, int64 forbid_tenure,
3244 double tabu_factor) {
3245 return RevAlloc(new TabuSearch(this, maximize, v, step, vars, keep_tenure,
3246 forbid_tenure, tabu_factor));
3247}
3248
3249SearchMonitor* Solver::MakeGenericTabuSearch(
3250 bool maximize, IntVar* const v, int64 step,
3251 const std::vector<IntVar*>& tabu_vars, int64 forbid_tenure) {
3252 return RevAlloc(
3253 new GenericTabuSearch(this, maximize, v, step, tabu_vars, forbid_tenure));
3254}
3255
3256// ---------- Simulated Annealing ----------
3257
3258namespace {
3259class SimulatedAnnealing : public Metaheuristic {
3260 public:
3261 SimulatedAnnealing(Solver* const s, bool maximize, IntVar* objective,
3262 int64 step, int64 initial_temperature);
3263 ~SimulatedAnnealing() override {}
3264 void EnterSearch() override;
3265 void ApplyDecision(Decision* d) override;
3266 bool AtSolution() override;
3267 bool LocalOptimum() override;
3268 void AcceptNeighbor() override;
3269 std::string DebugString() const override { return "Simulated Annealing"; }
3270
3271 private:
3272 double Temperature() const;
3273
3274 const int64 temperature0_;
3275 int64 iteration_;
3276 std::mt19937 rand_;
3277 bool found_initial_solution_;
3278
3279 DISALLOW_COPY_AND_ASSIGN(SimulatedAnnealing);
3280};
3281
3282SimulatedAnnealing::SimulatedAnnealing(Solver* const s, bool maximize,
3283 IntVar* objective, int64 step,
3284 int64 initial_temperature)
3285 : Metaheuristic(s, maximize, objective, step),
3286 temperature0_(initial_temperature),
3287 iteration_(0),
3288 rand_(CpRandomSeed()),
3289 found_initial_solution_(false) {}
3290
3291void SimulatedAnnealing::EnterSearch() {
3292 Metaheuristic::EnterSearch();
3293 found_initial_solution_ = false;
3294}
3295
3296void SimulatedAnnealing::ApplyDecision(Decision* const d) {
3297 Solver* const s = solver();
3298 if (d == s->balancing_decision()) {
3299 return;
3300 }
3301 const double rand_double = absl::Uniform<double>(rand_, 0.0, 1.0);
3302#if defined(_MSC_VER) || defined(__ANDROID__)
3303 const double rand_log2_double = log(rand_double) / log(2.0L);
3304#else
3305 const double rand_log2_double = log2(rand_double);
3306#endif
3307 const int64 energy_bound = Temperature() * rand_log2_double;
3308 if (maximize_) {
3309 const int64 bound =
3310 (current_ > kint64min) ? current_ + step_ + energy_bound : current_;
3311 s->AddConstraint(s->MakeGreaterOrEqual(objective_, bound));
3312 } else {
3313 const int64 bound =
3314 (current_ < kint64max) ? current_ - step_ - energy_bound : current_;
3315 s->AddConstraint(s->MakeLessOrEqual(objective_, bound));
3316 }
3317}
3318
3319bool SimulatedAnnealing::AtSolution() {
3320 if (!Metaheuristic::AtSolution()) {
3321 return false;
3322 }
3323 found_initial_solution_ = true;
3324 return true;
3325}
3326
3327bool SimulatedAnnealing::LocalOptimum() {
3328 if (maximize_) {
3330 } else {
3332 }
3333 ++iteration_;
3334 return found_initial_solution_ && Temperature() > 0;
3335}
3336
3338 if (iteration_ > 0) {
3339 ++iteration_;
3340 }
3341}
3342
3343double SimulatedAnnealing::Temperature() const {
3344 if (iteration_ > 0) {
3345 return (1.0 * temperature0_) / iteration_; // Cauchy annealing
3346 } else {
3347 return 0.;
3348 }
3349}
3350} // namespace
3351
3353 int64 step,
3354 int64 initial_temperature) {
3355 return RevAlloc(
3356 new SimulatedAnnealing(this, maximize, v, step, initial_temperature));
3357}
3358
3359// ---------- Guided Local Search ----------
3360
3361typedef std::pair<int64, int64> Arc;
3362
3363namespace {
3364// Base GLS penalties abstract class. Maintains the penalty frequency for each
3365// (variable, value) arc.
3366class GuidedLocalSearchPenalties {
3367 public:
3368 virtual ~GuidedLocalSearchPenalties() {}
3369 virtual bool HasValues() const = 0;
3370 virtual void Increment(const Arc& arc) = 0;
3371 virtual int64 Value(const Arc& arc) const = 0;
3372 virtual void Reset() = 0;
3373};
3374
3375// Dense GLS penalties implementation using a matrix to store penalties.
3376class GuidedLocalSearchPenaltiesTable : public GuidedLocalSearchPenalties {
3377 public:
3378 explicit GuidedLocalSearchPenaltiesTable(int size);
3379 ~GuidedLocalSearchPenaltiesTable() override {}
3380 bool HasValues() const override { return has_values_; }
3381 void Increment(const Arc& arc) override;
3382 int64 Value(const Arc& arc) const override;
3383 void Reset() override;
3384
3385 private:
3386 std::vector<std::vector<int64>> penalties_;
3387 bool has_values_;
3388};
3389
3390GuidedLocalSearchPenaltiesTable::GuidedLocalSearchPenaltiesTable(int size)
3391 : penalties_(size), has_values_(false) {}
3392
3393void GuidedLocalSearchPenaltiesTable::Increment(const Arc& arc) {
3394 std::vector<int64>& first_penalties = penalties_[arc.first];
3395 const int64 second = arc.second;
3396 if (second >= first_penalties.size()) {
3397 first_penalties.resize(second + 1, 0);
3398 }
3399 ++first_penalties[second];
3400 has_values_ = true;
3401}
3402
3403void GuidedLocalSearchPenaltiesTable::Reset() {
3404 has_values_ = false;
3405 for (int i = 0; i < penalties_.size(); ++i) {
3406 penalties_[i].clear();
3407 }
3408}
3409
3411 const std::vector<int64>& first_penalties = penalties_[arc.first];
3412 const int64 second = arc.second;
3413 if (second >= first_penalties.size()) {
3414 return 0;
3415 } else {
3416 return first_penalties[second];
3417 }
3418}
3419
3420// Sparse GLS penalties implementation using hash_map to store penalties.
3421class GuidedLocalSearchPenaltiesMap : public GuidedLocalSearchPenalties {
3422 public:
3423 explicit GuidedLocalSearchPenaltiesMap(int size);
3424 ~GuidedLocalSearchPenaltiesMap() override {}
3425 bool HasValues() const override { return (!penalties_.empty()); }
3426 void Increment(const Arc& arc) override;
3427 int64 Value(const Arc& arc) const override;
3428 void Reset() override;
3429
3430 private:
3431 Bitmap penalized_;
3432 absl::flat_hash_map<Arc, int64> penalties_;
3433};
3434
3435GuidedLocalSearchPenaltiesMap::GuidedLocalSearchPenaltiesMap(int size)
3436 : penalized_(size, false) {}
3437
3438void GuidedLocalSearchPenaltiesMap::Increment(const Arc& arc) {
3439 ++penalties_[arc];
3440 penalized_.Set(arc.first, true);
3441}
3442
3443void GuidedLocalSearchPenaltiesMap::Reset() {
3444 penalties_.clear();
3445 penalized_.Clear();
3446}
3447
3449 if (penalized_.Get(arc.first)) {
3450 return gtl::FindWithDefault(penalties_, arc, 0);
3451 }
3452 return 0;
3453}
3454
3455class GuidedLocalSearch : public Metaheuristic {
3456 public:
3457 GuidedLocalSearch(Solver* const s, IntVar* objective, bool maximize,
3458 int64 step, const std::vector<IntVar*>& vars,
3459 double penalty_factor);
3460 ~GuidedLocalSearch() override {}
3461 bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;
3462 void ApplyDecision(Decision* d) override;
3463 bool AtSolution() override;
3464 void EnterSearch() override;
3465 bool LocalOptimum() override;
3466 virtual int64 AssignmentElementPenalty(const Assignment& assignment,
3467 int index) = 0;
3468 virtual int64 AssignmentPenalty(const Assignment& assignment, int index,
3469 int64 next) = 0;
3470 virtual bool EvaluateElementValue(const Assignment::IntContainer& container,
3471 int64 index, int* container_index,
3472 int64* penalty) = 0;
3473 virtual IntExpr* MakeElementPenalty(int index) = 0;
3474 std::string DebugString() const override { return "Guided Local Search"; }
3475
3476 protected:
3477 struct Comparator {
3478 bool operator()(const std::pair<Arc, double>& i,
3479 const std::pair<Arc, double>& j) {
3480 return i.second > j.second;
3481 }
3482 };
3483
3484 int64 Evaluate(const Assignment* delta, int64 current_penalty,
3485 const int64* const out_values, bool cache_delta_values);
3486
3488 Assignment assignment_;
3491 const std::vector<IntVar*> vars_;
3492 absl::flat_hash_map<const IntVar*, int64> indices_;
3493 const double penalty_factor_;
3494 std::unique_ptr<GuidedLocalSearchPenalties> penalties_;
3495 std::unique_ptr<int64[]> current_penalized_values_;
3496 std::unique_ptr<int64[]> delta_cache_;
3498};
3499
3500GuidedLocalSearch::GuidedLocalSearch(Solver* const s, IntVar* objective,
3501 bool maximize, int64 step,
3502 const std::vector<IntVar*>& vars,
3503 double penalty_factor)
3504 : Metaheuristic(s, maximize, objective, step),
3505 penalized_objective_(nullptr),
3506 assignment_(s),
3509 vars_(vars),
3510 penalty_factor_(penalty_factor),
3511 incremental_(false) {
3512 if (!vars.empty()) {
3513 // TODO(user): Remove scoped_array.
3514 assignment_.Add(vars_);
3515 current_penalized_values_ = absl::make_unique<int64[]>(vars_.size());
3516 delta_cache_ = absl::make_unique<int64[]>(vars_.size());
3517 memset(current_penalized_values_.get(), 0,
3518 vars_.size() * sizeof(*current_penalized_values_.get()));
3519 }
3520 for (int i = 0; i < vars_.size(); ++i) {
3521 indices_[vars_[i]] = i;
3522 }
3523 if (absl::GetFlag(FLAGS_cp_use_sparse_gls_penalties)) {
3524 penalties_ = absl::make_unique<GuidedLocalSearchPenaltiesMap>(vars_.size());
3525 } else {
3526 penalties_ =
3527 absl::make_unique<GuidedLocalSearchPenaltiesTable>(vars_.size());
3528 }
3529}
3530
3531// Add the following constraint (includes aspiration criterion):
3532// if minimizing,
3533// objective =< Max(current penalized cost - penalized_objective - step,
3534// best solution cost - step)
3535// if maximizing,
3536// objective >= Min(current penalized cost - penalized_objective + step,
3537// best solution cost + step)
3538void GuidedLocalSearch::ApplyDecision(Decision* const d) {
3539 if (d == solver()->balancing_decision()) {
3540 return;
3541 }
3543 if (penalties_->HasValues()) {
3544 // Computing sum of penalties expression.
3545 // Scope needed to avoid potential leak of elements.
3546 {
3547 std::vector<IntVar*> elements;
3548 for (int i = 0; i < vars_.size(); ++i) {
3549 elements.push_back(MakeElementPenalty(i)->Var());
3550 const int64 penalty = AssignmentElementPenalty(assignment_, i);
3551 current_penalized_values_[i] = penalty;
3552 delta_cache_[i] = penalty;
3555 }
3556 penalized_objective_ = solver()->MakeSum(elements)->Var();
3557 }
3559 incremental_ = false;
3560 if (maximize_) {
3561 IntExpr* min_pen_exp =
3562 solver()->MakeDifference(current_ + step_, penalized_objective_);
3563 IntVar* min_exp = solver()->MakeMin(min_pen_exp, best_ + step_)->Var();
3564 solver()->AddConstraint(
3565 solver()->MakeGreaterOrEqual(objective_, min_exp));
3566 } else {
3567 IntExpr* max_pen_exp =
3568 solver()->MakeDifference(current_ - step_, penalized_objective_);
3569 IntVar* max_exp = solver()->MakeMax(max_pen_exp, best_ - step_)->Var();
3570 solver()->AddConstraint(solver()->MakeLessOrEqual(objective_, max_exp));
3571 }
3572 } else {
3573 penalized_objective_ = nullptr;
3574 if (maximize_) {
3576 objective_->SetMin(bound);
3577 } else {
3579 objective_->SetMax(bound);
3580 }
3581 }
3582}
3583
3584bool GuidedLocalSearch::AtSolution() {
3585 if (!Metaheuristic::AtSolution()) {
3586 return false;
3587 }
3588 if (penalized_objective_ != nullptr) { // In case no move has been found
3589 current_ += penalized_objective_->Value();
3590 }
3591 assignment_.Store();
3592 return true;
3593}
3594
3595void GuidedLocalSearch::EnterSearch() {
3596 Metaheuristic::EnterSearch();
3597 penalized_objective_ = nullptr;
3600 memset(current_penalized_values_.get(), 0,
3601 vars_.size() * sizeof(*current_penalized_values_.get()));
3602 penalties_->Reset();
3603}
3604
3605// GLS filtering; compute the penalized value corresponding to the delta and
3606// modify objective bound accordingly.
3607bool GuidedLocalSearch::AcceptDelta(Assignment* delta, Assignment* deltadelta) {
3608 if (delta != nullptr || deltadelta != nullptr) {
3609 if (!penalties_->HasValues()) {
3610 return Metaheuristic::AcceptDelta(delta, deltadelta);
3611 }
3612 int64 penalty = 0;
3613 if (!deltadelta->Empty()) {
3614 if (!incremental_) {
3615 penalty = Evaluate(delta, assignment_penalized_value_,
3616 current_penalized_values_.get(), true);
3617 } else {
3618 penalty = Evaluate(deltadelta, old_penalized_value_, delta_cache_.get(),
3619 true);
3620 }
3621 incremental_ = true;
3622 } else {
3623 if (incremental_) {
3624 for (int i = 0; i < vars_.size(); ++i) {
3626 }
3628 }
3629 incremental_ = false;
3630 penalty = Evaluate(delta, assignment_penalized_value_,
3631 current_penalized_values_.get(), false);
3632 }
3633 old_penalized_value_ = penalty;
3634 if (!delta->HasObjective()) {
3635 delta->AddObjective(objective_);
3636 }
3637 if (delta->Objective() == objective_) {
3638 if (maximize_) {
3639 delta->SetObjectiveMin(
3641 CapAdd(best_, step_)),
3642 delta->ObjectiveMin()));
3643 } else {
3644 delta->SetObjectiveMax(
3646 CapSub(best_, step_)),
3647 delta->ObjectiveMax()));
3648 }
3649 }
3650 }
3651 return true;
3652}
3653
3654int64 GuidedLocalSearch::Evaluate(const Assignment* delta,
3655 int64 current_penalty,
3656 const int64* const out_values,
3657 bool cache_delta_values) {
3658 int64 penalty = current_penalty;
3659 const Assignment::IntContainer& container = delta->IntVarContainer();
3660 const int size = container.Size();
3661 for (int i = 0; i < size; ++i) {
3662 const IntVarElement& new_element = container.Element(i);
3663 IntVar* var = new_element.Var();
3664 int64 index = -1;
3665 if (gtl::FindCopy(indices_, var, &index)) {
3666 penalty = CapSub(penalty, out_values[index]);
3667 int64 new_penalty = 0;
3668 if (EvaluateElementValue(container, index, &i, &new_penalty)) {
3669 penalty = CapAdd(penalty, new_penalty);
3670 if (cache_delta_values) {
3671 delta_cache_[index] = new_penalty;
3672 }
3673 }
3674 }
3675 }
3676 return penalty;
3677}
3678
3679// Penalize all the most expensive arcs (var, value) according to their utility:
3680// utility(i, j) = cost(i, j) / (1 + penalty(i, j))
3681bool GuidedLocalSearch::LocalOptimum() {
3682 std::vector<std::pair<Arc, double>> utility(vars_.size());
3683 for (int i = 0; i < vars_.size(); ++i) {
3684 if (!assignment_.Bound(vars_[i])) {
3685 // Never synced with a solution, problem infeasible.
3686 return false;
3687 }
3688 const int64 var_value = assignment_.Value(vars_[i]);
3689 const int64 value =
3690 (var_value != i) ? AssignmentPenalty(assignment_, i, var_value) : 0;
3691 const Arc arc(i, var_value);
3692 const int64 penalty = penalties_->Value(arc);
3693 utility[i] = std::pair<Arc, double>(arc, value / (penalty + 1.0));
3694 }
3695 Comparator comparator;
3696 std::sort(utility.begin(), utility.end(), comparator);
3697 int64 utility_value = utility[0].second;
3698 penalties_->Increment(utility[0].first);
3699 for (int i = 1; i < utility.size() && utility_value == utility[i].second;
3700 ++i) {
3701 penalties_->Increment(utility[i].first);
3702 }
3703 if (maximize_) {
3705 } else {
3707 }
3708 return true;
3709}
3710
3711class BinaryGuidedLocalSearch : public GuidedLocalSearch {
3712 public:
3713 BinaryGuidedLocalSearch(Solver* const solver, IntVar* const objective,
3714 std::function<int64(int64, int64)> objective_function,
3715 bool maximize, int64 step,
3716 const std::vector<IntVar*>& vars,
3717 double penalty_factor);
3718 ~BinaryGuidedLocalSearch() override {}
3719 IntExpr* MakeElementPenalty(int index) override;
3720 int64 AssignmentElementPenalty(const Assignment& assignment,
3721 int index) override;
3722 int64 AssignmentPenalty(const Assignment& assignment, int index,
3723 int64 next) override;
3724 bool EvaluateElementValue(const Assignment::IntContainer& container,
3725 int64 index, int* container_index,
3726 int64* penalty) override;
3727
3728 private:
3729 int64 PenalizedValue(int64 i, int64 j);
3730 std::function<int64(int64, int64)> objective_function_;
3731};
3732
3733BinaryGuidedLocalSearch::BinaryGuidedLocalSearch(
3734 Solver* const solver, IntVar* const objective,
3735 std::function<int64(int64, int64)> objective_function, bool maximize,
3736 int64 step, const std::vector<IntVar*>& vars, double penalty_factor)
3737 : GuidedLocalSearch(solver, objective, maximize, step, vars,
3738 penalty_factor),
3739 objective_function_(std::move(objective_function)) {}
3740
3741IntExpr* BinaryGuidedLocalSearch::MakeElementPenalty(int index) {
3742 return solver()->MakeElement(
3743 [this, index](int64 i) { return PenalizedValue(index, i); },
3744 vars_[index]);
3745}
3746
3747int64 BinaryGuidedLocalSearch::AssignmentElementPenalty(
3748 const Assignment& assignment, int index) {
3749 return PenalizedValue(index, assignment.Value(vars_[index]));
3750}
3751
3752int64 BinaryGuidedLocalSearch::AssignmentPenalty(const Assignment& assignment,
3753 int index, int64 next) {
3754 return objective_function_(index, next);
3755}
3756
3757bool BinaryGuidedLocalSearch::EvaluateElementValue(
3758 const Assignment::IntContainer& container, int64 index,
3759 int* container_index, int64* penalty) {
3760 const IntVarElement& element = container.Element(*container_index);
3761 if (element.Activated()) {
3762 *penalty = PenalizedValue(index, element.Value());
3763 return true;
3764 }
3765 return false;
3766}
3767
3768// Penalized value for (i, j) = penalty_factor_ * penalty(i, j) * cost (i, j)
3769int64 BinaryGuidedLocalSearch::PenalizedValue(int64 i, int64 j) {
3770 const Arc arc(i, j);
3771 const int64 penalty = penalties_->Value(arc);
3772 if (penalty != 0) { // objective_function_->Run(i, j) can be costly
3773 const double penalized_value_fp =
3774 penalty_factor_ * penalty * objective_function_(i, j);
3775 const int64 penalized_value = (penalized_value_fp <= kint64max)
3776 ? static_cast<int64>(penalized_value_fp)
3777 : kint64max;
3778 if (maximize_) {
3779 return -penalized_value;
3780 } else {
3781 return penalized_value;
3782 }
3783 } else {
3784 return 0;
3785 }
3786}
3787
3788class TernaryGuidedLocalSearch : public GuidedLocalSearch {
3789 public:
3790 TernaryGuidedLocalSearch(
3791 Solver* const solver, IntVar* const objective,
3792 std::function<int64(int64, int64, int64)> objective_function,
3793 bool maximize, int64 step, const std::vector<IntVar*>& vars,
3794 const std::vector<IntVar*>& secondary_vars, double penalty_factor);
3795 ~TernaryGuidedLocalSearch() override {}
3796 IntExpr* MakeElementPenalty(int index) override;
3797 int64 AssignmentElementPenalty(const Assignment& assignment,
3798 int index) override;
3799 int64 AssignmentPenalty(const Assignment& assignment, int index,
3800 int64 next) override;
3801 bool EvaluateElementValue(const Assignment::IntContainer& container,
3802 int64 index, int* container_index,
3803 int64* penalty) override;
3804
3805 private:
3806 int64 PenalizedValue(int64 i, int64 j, int64 k);
3807 int64 GetAssignmentSecondaryValue(const Assignment::IntContainer& container,
3808 int index, int* container_index) const;
3809
3810 const std::vector<IntVar*> secondary_vars_;
3811 std::function<int64(int64, int64, int64)> objective_function_;
3812};
3813
3814TernaryGuidedLocalSearch::TernaryGuidedLocalSearch(
3815 Solver* const solver, IntVar* const objective,
3816 std::function<int64(int64, int64, int64)> objective_function, bool maximize,
3817 int64 step, const std::vector<IntVar*>& vars,
3818 const std::vector<IntVar*>& secondary_vars, double penalty_factor)
3819 : GuidedLocalSearch(solver, objective, maximize, step, vars,
3820 penalty_factor),
3821 secondary_vars_(secondary_vars),
3822 objective_function_(std::move(objective_function)) {
3823 if (!secondary_vars.empty()) {
3824 assignment_.Add(secondary_vars);
3825 }
3826}
3827
3828IntExpr* TernaryGuidedLocalSearch::MakeElementPenalty(int index) {
3829 return solver()->MakeElement(
3830 [this, index](int64 i, int64 j) { return PenalizedValue(index, i, j); },
3831 vars_[index], secondary_vars_[index]);
3832}
3833
3834int64 TernaryGuidedLocalSearch::AssignmentElementPenalty(
3835 const Assignment& assignment, int index) {
3836 return PenalizedValue(index, assignment.Value(vars_[index]),
3837 assignment.Value(secondary_vars_[index]));
3838}
3839
3840int64 TernaryGuidedLocalSearch::AssignmentPenalty(const Assignment& assignment,
3841 int index, int64 next) {
3842 return objective_function_(index, next,
3843 assignment.Value(secondary_vars_[index]));
3844}
3845
3846bool TernaryGuidedLocalSearch::EvaluateElementValue(
3847 const Assignment::IntContainer& container, int64 index,
3848 int* container_index, int64* penalty) {
3849 const IntVarElement& element = container.Element(*container_index);
3850 if (element.Activated()) {
3851 *penalty = PenalizedValue(
3852 index, element.Value(),
3853 GetAssignmentSecondaryValue(container, index, container_index));
3854 return true;
3855 }
3856 return false;
3857}
3858
3859// Penalized value for (i, j) = penalty_factor_ * penalty(i, j) * cost (i, j)
3860int64 TernaryGuidedLocalSearch::PenalizedValue(int64 i, int64 j, int64 k) {
3861 const Arc arc(i, j);
3862 const int64 penalty = penalties_->Value(arc);
3863 if (penalty != 0) { // objective_function_(i, j, k) can be costly
3864 const double penalized_value_fp =
3865 penalty_factor_ * penalty * objective_function_(i, j, k);
3866 const int64 penalized_value = (penalized_value_fp <= kint64max)
3867 ? static_cast<int64>(penalized_value_fp)
3868 : kint64max;
3869 if (maximize_) {
3870 return -penalized_value;
3871 } else {
3872 return penalized_value;
3873 }
3874 } else {
3875 return 0;
3876 }
3877}
3878
3879int64 TernaryGuidedLocalSearch::GetAssignmentSecondaryValue(
3880 const Assignment::IntContainer& container, int index,
3881 int* container_index) const {
3882 const IntVar* secondary_var = secondary_vars_[index];
3883 int hint_index = *container_index + 1;
3884 if (hint_index > 0 && hint_index < container.Size() &&
3885 secondary_var == container.Element(hint_index).Var()) {
3886 *container_index = hint_index;
3887 return container.Element(hint_index).Value();
3888 } else {
3889 return container.Element(secondary_var).Value();
3890 }
3891}
3892} // namespace
3893
3894SearchMonitor* Solver::MakeGuidedLocalSearch(
3895 bool maximize, IntVar* const objective,
3896 Solver::IndexEvaluator2 objective_function, int64 step,
3897 const std::vector<IntVar*>& vars, double penalty_factor) {
3898 return RevAlloc(new BinaryGuidedLocalSearch(
3899 this, objective, std::move(objective_function), maximize, step, vars,
3900 penalty_factor));
3901}
3902
3903SearchMonitor* Solver::MakeGuidedLocalSearch(
3904 bool maximize, IntVar* const objective,
3905 Solver::IndexEvaluator3 objective_function, int64 step,
3906 const std::vector<IntVar*>& vars,
3907 const std::vector<IntVar*>& secondary_vars, double penalty_factor) {
3908 return RevAlloc(new TernaryGuidedLocalSearch(
3909 this, objective, std::move(objective_function), maximize, step, vars,
3910 secondary_vars, penalty_factor));
3911}
3912
3913// ---------- Search Limits ----------
3914
3915// ----- Base Class -----
3916
3917SearchLimit::~SearchLimit() {}
3918
3919void SearchLimit::EnterSearch() {
3920 crossed_ = false;
3921 Init();
3922}
3923
3924void SearchLimit::BeginNextDecision(DecisionBuilder* const b) {
3925 PeriodicCheck();
3926 TopPeriodicCheck();
3927}
3928
3929void SearchLimit::RefuteDecision(Decision* const d) {
3930 PeriodicCheck();
3931 TopPeriodicCheck();
3932}
3933
3934void SearchLimit::PeriodicCheck() {
3935 if (crossed_ || Check()) {
3936 crossed_ = true;
3937 solver()->Fail();
3938 }
3939}
3940
3941void SearchLimit::TopPeriodicCheck() {
3942 if (solver()->TopLevelSearch() != solver()->ActiveSearch()) {
3943 solver()->TopPeriodicCheck();
3944 }
3945}
3946
3947// ----- Regular Limit -----
3948
3949RegularLimit::RegularLimit(Solver* const s, absl::Duration time, int64 branches,
3950 int64 failures, int64 solutions,
3951 bool smart_time_check, bool cumulative)
3952 : SearchLimit(s),
3953 duration_limit_(time),
3954 solver_time_at_limit_start_(s->Now()),
3955 last_time_elapsed_(absl::ZeroDuration()),
3956 check_count_(0),
3957 next_check_(0),
3958 smart_time_check_(smart_time_check),
3959 branches_(branches),
3960 branches_offset_(0),
3961 failures_(failures),
3962 failures_offset_(0),
3963 solutions_(solutions),
3964 solutions_offset_(0),
3965 cumulative_(cumulative) {}
3966
3968
3969void RegularLimit::Copy(const SearchLimit* const limit) {
3970 const RegularLimit* const regular =
3971 reinterpret_cast<const RegularLimit* const>(limit);
3972 duration_limit_ = regular->duration_limit_;
3973 branches_ = regular->branches_;
3974 failures_ = regular->failures_;
3975 solutions_ = regular->solutions_;
3976 smart_time_check_ = regular->smart_time_check_;
3977 cumulative_ = regular->cumulative_;
3978}
3979
3981
3983 Solver* const s = solver();
3984 return s->MakeLimit(wall_time(), branches_, failures_, solutions_,
3985 smart_time_check_);
3986}
3987
3989 Solver* const s = solver();
3990 // Warning limits might be kint64max, do not move the offset to the rhs
3991 return s->branches() - branches_offset_ >= branches_ ||
3992 s->failures() - failures_offset_ >= failures_ || CheckTime() ||
3993 s->solutions() - solutions_offset_ >= solutions_;
3994}
3995
3997 Solver* const s = solver();
3998 int64 progress = GetPercent(s->branches(), branches_offset_, branches_);
3999 progress = std::max(progress,
4000 GetPercent(s->failures(), failures_offset_, failures_));
4001 progress = std::max(
4002 progress, GetPercent(s->solutions(), solutions_offset_, solutions_));
4003 if (duration_limit() != absl::InfiniteDuration()) {
4004 progress = std::max(progress, (100 * TimeElapsed()) / duration_limit());
4005 }
4006 return progress;
4007}
4008
4010 Solver* const s = solver();
4011 branches_offset_ = s->branches();
4012 failures_offset_ = s->failures();
4013 solver_time_at_limit_start_ = s->Now();
4014 last_time_elapsed_ = absl::ZeroDuration();
4015 solutions_offset_ = s->solutions();
4016 check_count_ = 0;
4017 next_check_ = 0;
4018}
4019
4021 if (cumulative_) {
4022 // Reduce the limits by the amount consumed during this search
4023 Solver* const s = solver();
4024 branches_ -= s->branches() - branches_offset_;
4025 failures_ -= s->failures() - failures_offset_;
4026 duration_limit_ -= s->Now() - solver_time_at_limit_start_;
4027 solutions_ -= s->solutions() - solutions_offset_;
4028 }
4029}
4030
4031void RegularLimit::UpdateLimits(absl::Duration time, int64 branches,
4032 int64 failures, int64 solutions) {
4033 duration_limit_ = time;
4034 branches_ = branches;
4035 failures_ = failures;
4036 solutions_ = solutions;
4037}
4038
4040 Solver* const s = solver();
4041 return s->solutions() + s->unchecked_solutions() - solutions_offset_ >=
4042 solutions_;
4043}
4044
4045std::string RegularLimit::DebugString() const {
4046 return absl::StrFormat(
4047 "RegularLimit(crossed = %i, duration_limit = %s, "
4048 "branches = %d, failures = %d, solutions = %d cumulative = %s",
4049 crossed(), absl::FormatDuration(duration_limit()), branches_, failures_,
4050 solutions_, (cumulative_ ? "true" : "false"));
4051}
4052
4053void RegularLimit::Accept(ModelVisitor* const visitor) const {
4057 branches_);
4059 failures_);
4061 solutions_);
4063 smart_time_check_);
4066}
4067
4068bool RegularLimit::CheckTime() { return TimeElapsed() >= duration_limit(); }
4069
4070absl::Duration RegularLimit::TimeElapsed() {
4071 const int64 kMaxSkip = 100;
4072 const int64 kCheckWarmupIterations = 100;
4073 ++check_count_;
4074 if (duration_limit() != absl::InfiniteDuration() &&
4075 next_check_ <= check_count_) {
4076 Solver* const s = solver();
4077 absl::Duration elapsed = s->Now() - solver_time_at_limit_start_;
4078 if (smart_time_check_ && check_count_ > kCheckWarmupIterations &&
4079 elapsed > absl::ZeroDuration()) {
4080 const int64 estimated_check_count_at_limit = MathUtil::FastInt64Round(
4081 check_count_ * absl::FDivDuration(duration_limit_, elapsed));
4082 next_check_ =
4083 std::min(check_count_ + kMaxSkip, estimated_check_count_at_limit);
4084 }
4085 last_time_elapsed_ = elapsed;
4086 }
4087 return last_time_elapsed_;
4088}
4089
4092 /*smart_time_check=*/false, /*cumulative=*/false);
4093}
4094
4096 return MakeLimit(absl::InfiniteDuration(), branches, kint64max, kint64max,
4097 /*smart_time_check=*/false, /*cumulative=*/false);
4098}
4099
4101 return MakeLimit(absl::InfiniteDuration(), kint64max, failures, kint64max,
4102 /*smart_time_check=*/false, /*cumulative=*/false);
4103}
4104
4106 return MakeLimit(absl::InfiniteDuration(), kint64max, kint64max, solutions,
4107 /*smart_time_check=*/false, /*cumulative=*/false);
4108}
4109
4111 int64 solutions, bool smart_time_check,
4112 bool cumulative) {
4113 return MakeLimit(absl::Milliseconds(time), branches, failures, solutions,
4114 smart_time_check, cumulative);
4115}
4116
4117RegularLimit* Solver::MakeLimit(absl::Duration time, int64 branches,
4118 int64 failures, int64 solutions,
4119 bool smart_time_check, bool cumulative) {
4121 smart_time_check, cumulative));
4122}
4123
4124RegularLimit* Solver::MakeLimit(const RegularLimitParameters& proto) {
4125 return MakeLimit(proto.time() == kint64max ? absl::InfiniteDuration()
4126 : absl::Milliseconds(proto.time()),
4127 proto.branches(), proto.failures(), proto.solutions(),
4128 proto.smart_time_check(), proto.cumulative());
4129}
4130
4131RegularLimitParameters Solver::MakeDefaultRegularLimitParameters() const {
4132 RegularLimitParameters proto;
4133 proto.set_time(kint64max);
4134 proto.set_branches(kint64max);
4135 proto.set_failures(kint64max);
4136 proto.set_solutions(kint64max);
4137 proto.set_smart_time_check(false);
4138 proto.set_cumulative(false);
4139 return proto;
4140}
4141
4142// ----- Improvement Search Limit -----
4143
4145 Solver* const s, IntVar* objective_var, bool maximize,
4146 double objective_scaling_factor, double objective_offset,
4147 double improvement_rate_coefficient,
4148 int improvement_rate_solutions_distance)
4149 : SearchLimit(s),
4150 objective_var_(objective_var),
4151 maximize_(maximize),
4152 objective_scaling_factor_(objective_scaling_factor),
4153 objective_offset_(objective_offset),
4154 improvement_rate_coefficient_(improvement_rate_coefficient),
4155 improvement_rate_solutions_distance_(
4156 improvement_rate_solutions_distance) {
4157 Init();
4158}
4159
4161
4163 best_objective_ = maximize_ ? -std::numeric_limits<double>::infinity()
4164 : std::numeric_limits<double>::infinity();
4165 threshold_ = std::numeric_limits<double>::infinity();
4166 objective_updated_ = false;
4167 gradient_stage_ = true;
4168}
4169
4171 const ImprovementSearchLimit* const improv =
4172 reinterpret_cast<const ImprovementSearchLimit* const>(limit);
4173 objective_var_ = improv->objective_var_;
4174 maximize_ = improv->maximize_;
4175 objective_scaling_factor_ = improv->objective_scaling_factor_;
4176 objective_offset_ = improv->objective_offset_;
4177 improvement_rate_coefficient_ = improv->improvement_rate_coefficient_;
4178 improvement_rate_solutions_distance_ =
4179 improv->improvement_rate_solutions_distance_;
4180 improvements_ = improv->improvements_;
4181 threshold_ = improv->threshold_;
4182 best_objective_ = improv->best_objective_;
4183 objective_updated_ = improv->objective_updated_;
4184 gradient_stage_ = improv->gradient_stage_;
4185}
4186
4188 Solver* const s = solver();
4189 return s->MakeImprovementLimit(
4190 objective_var_, maximize_, objective_scaling_factor_, objective_offset_,
4191 improvement_rate_coefficient_, improvement_rate_solutions_distance_);
4192}
4193
4195 if (!objective_updated_) {
4196 return false;
4197 }
4198 objective_updated_ = false;
4199
4200 if (improvements_.size() <= improvement_rate_solutions_distance_) {
4201 return false;
4202 }
4203
4204 const std::pair<double, int64> cur = improvements_.back();
4205 const std::pair<double, int64> prev = improvements_.front();
4206 DCHECK_GT(cur.second, prev.second);
4207 double improvement_rate =
4208 std::abs(prev.first - cur.first) / (cur.second - prev.second);
4209 if (gradient_stage_) {
4210 threshold_ = fmin(threshold_, improvement_rate);
4211 } else if (improvement_rate_coefficient_ * improvement_rate < threshold_) {
4212 return true;
4213 }
4214
4215 return false;
4216}
4217
4219 const int64 new_objective =
4220 objective_var_ != nullptr && objective_var_->Bound()
4221 ? objective_var_->Value()
4222 : (maximize_
4225
4226 const double scaled_new_objective =
4227 objective_scaling_factor_ * (new_objective + objective_offset_);
4228
4229 const bool is_improvement = maximize_
4230 ? scaled_new_objective > best_objective_
4231 : scaled_new_objective < best_objective_;
4232
4233 if (gradient_stage_ && !is_improvement) {
4234 gradient_stage_ = false;
4235 // In case we haven't got enough solutions during the first stage, the limit
4236 // never stops the search.
4237 if (threshold_ == std::numeric_limits<double>::infinity()) {
4238 threshold_ = -1;
4239 }
4240 }
4241
4242 if (is_improvement) {
4243 best_objective_ = scaled_new_objective;
4244 objective_updated_ = true;
4245 improvements_.push_back(
4246 std::make_pair(scaled_new_objective, solver()->neighbors()));
4247 // We need to have 'improvement_rate_solutions_distance_' + 1 element in the
4248 // 'improvements_', so the distance between improvements is
4249 // 'improvement_rate_solutions_distance_'.
4250 if (improvements_.size() - 1 > improvement_rate_solutions_distance_) {
4251 improvements_.pop_front();
4252 }
4253 DCHECK_LE(improvements_.size() - 1, improvement_rate_solutions_distance_);
4254 }
4255
4256 return true;
4257}
4258
4260 IntVar* objective_var, bool maximize, double objective_scaling_factor,
4261 double objective_offset, double improvement_rate_coefficient,
4262 int improvement_rate_solutions_distance) {
4264 this, objective_var, maximize, objective_scaling_factor, objective_offset,
4265 improvement_rate_coefficient, improvement_rate_solutions_distance));
4266}
4267
4268// A limit whose Check function is the OR of two underlying limits.
4269namespace {
4270class ORLimit : public SearchLimit {
4271 public:
4272 ORLimit(SearchLimit* limit_1, SearchLimit* limit_2)
4273 : SearchLimit(limit_1->solver()), limit_1_(limit_1), limit_2_(limit_2) {
4274 CHECK(limit_1 != nullptr);
4275 CHECK(limit_2 != nullptr);
4276 CHECK_EQ(limit_1->solver(), limit_2->solver())
4277 << "Illegal arguments: cannot combines limits that belong to different "
4278 << "solvers, because the reversible allocations could delete one and "
4279 << "not the other.";
4280 }
4281
4282 bool Check() override {
4283 // Check being non-const, there may be side effects. So we always call both
4284 // checks.
4285 const bool check_1 = limit_1_->Check();
4286 const bool check_2 = limit_2_->Check();
4287 return check_1 || check_2;
4288 }
4289
4290 void Init() override {
4291 limit_1_->Init();
4292 limit_2_->Init();
4293 }
4294
4295 void Copy(const SearchLimit* const limit) override {
4296 LOG(FATAL) << "Not implemented.";
4297 }
4298
4299 SearchLimit* MakeClone() const override {
4300 // Deep cloning: the underlying limits are cloned, too.
4301 return solver()->MakeLimit(limit_1_->MakeClone(), limit_2_->MakeClone());
4302 }
4303
4304 void EnterSearch() override {
4305 limit_1_->EnterSearch();
4306 limit_2_->EnterSearch();
4307 }
4308 void BeginNextDecision(DecisionBuilder* const b) override {
4309 limit_1_->BeginNextDecision(b);
4310 limit_2_->BeginNextDecision(b);
4311 }
4312 void PeriodicCheck() override {
4313 limit_1_->PeriodicCheck();
4314 limit_2_->PeriodicCheck();
4315 }
4316 void RefuteDecision(Decision* const d) override {
4317 limit_1_->RefuteDecision(d);
4318 limit_2_->RefuteDecision(d);
4319 }
4320 std::string DebugString() const override {
4321 return absl::StrCat("OR limit (", limit_1_->DebugString(), " OR ",
4322 limit_2_->DebugString(), ")");
4323 }
4324
4325 private:
4326 SearchLimit* const limit_1_;
4327 SearchLimit* const limit_2_;
4328};
4329} // namespace
4330
4332 SearchLimit* const limit_2) {
4333 return RevAlloc(new ORLimit(limit_1, limit_2));
4334}
4335
4336namespace {
4337class CustomLimit : public SearchLimit {
4338 public:
4339 CustomLimit(Solver* const s, std::function<bool()> limiter);
4340 bool Check() override;
4341 void Init() override;
4342 void Copy(const SearchLimit* const limit) override;
4343 SearchLimit* MakeClone() const override;
4344
4345 private:
4346 std::function<bool()> limiter_;
4347};
4348
4349CustomLimit::CustomLimit(Solver* const s, std::function<bool()> limiter)
4350 : SearchLimit(s), limiter_(std::move(limiter)) {}
4351
4352bool CustomLimit::Check() {
4353 if (limiter_) return limiter_();
4354 return false;
4355}
4356
4357void CustomLimit::Init() {}
4358
4359void CustomLimit::Copy(const SearchLimit* const limit) {
4360 const CustomLimit* const custom =
4361 reinterpret_cast<const CustomLimit* const>(limit);
4362 limiter_ = custom->limiter_;
4363}
4364
4365SearchLimit* CustomLimit::MakeClone() const {
4366 return solver()->RevAlloc(new CustomLimit(solver(), limiter_));
4367}
4368} // namespace
4369
4370SearchLimit* Solver::MakeCustomLimit(std::function<bool()> limiter) {
4371 return RevAlloc(new CustomLimit(this, std::move(limiter)));
4372}
4373
4374// ---------- SolveOnce ----------
4375
4376namespace {
4377class SolveOnce : public DecisionBuilder {
4378 public:
4379 explicit SolveOnce(DecisionBuilder* const db) : db_(db) {
4380 CHECK(db != nullptr);
4381 }
4382
4383 SolveOnce(DecisionBuilder* const db,
4384 const std::vector<SearchMonitor*>& monitors)
4385 : db_(db), monitors_(monitors) {
4386 CHECK(db != nullptr);
4387 }
4388
4389 ~SolveOnce() override {}
4390
4391 Decision* Next(Solver* s) override {
4392 bool res = s->SolveAndCommit(db_, monitors_);
4393 if (!res) {
4394 s->Fail();
4395 }
4396 return nullptr;
4397 }
4398
4399 std::string DebugString() const override {
4400 return absl::StrFormat("SolveOnce(%s)", db_->DebugString());
4401 }
4402
4403 void Accept(ModelVisitor* const visitor) const override {
4404 db_->Accept(visitor);
4405 }
4406
4407 private:
4408 DecisionBuilder* const db_;
4409 std::vector<SearchMonitor*> monitors_;
4410};
4411} // namespace
4412
4414 return RevAlloc(new SolveOnce(db));
4415}
4416
4418 SearchMonitor* const monitor1) {
4419 std::vector<SearchMonitor*> monitors;
4420 monitors.push_back(monitor1);
4421 return RevAlloc(new SolveOnce(db, monitors));
4422}
4423
4425 SearchMonitor* const monitor1,
4426 SearchMonitor* const monitor2) {
4427 std::vector<SearchMonitor*> monitors;
4428 monitors.push_back(monitor1);
4429 monitors.push_back(monitor2);
4430 return RevAlloc(new SolveOnce(db, monitors));
4431}
4432
4434 SearchMonitor* const monitor1,
4435 SearchMonitor* const monitor2,
4436 SearchMonitor* const monitor3) {
4437 std::vector<SearchMonitor*> monitors;
4438 monitors.push_back(monitor1);
4439 monitors.push_back(monitor2);
4440 monitors.push_back(monitor3);
4441 return RevAlloc(new SolveOnce(db, monitors));
4442}
4443
4445 SearchMonitor* const monitor1,
4446 SearchMonitor* const monitor2,
4447 SearchMonitor* const monitor3,
4448 SearchMonitor* const monitor4) {
4449 std::vector<SearchMonitor*> monitors;
4450 monitors.push_back(monitor1);
4451 monitors.push_back(monitor2);
4452 monitors.push_back(monitor3);
4453 monitors.push_back(monitor4);
4454 return RevAlloc(new SolveOnce(db, monitors));
4455}
4456
4458 DecisionBuilder* const db, const std::vector<SearchMonitor*>& monitors) {
4459 return RevAlloc(new SolveOnce(db, monitors));
4460}
4461
4462// ---------- NestedOptimize ----------
4463
4464namespace {
4465class NestedOptimize : public DecisionBuilder {
4466 public:
4467 NestedOptimize(DecisionBuilder* const db, Assignment* const solution,
4468 bool maximize, int64 step)
4469 : db_(db),
4470 solution_(solution),
4471 maximize_(maximize),
4472 step_(step),
4473 collector_(nullptr) {
4474 CHECK(db != nullptr);
4475 CHECK(solution != nullptr);
4476 CHECK(solution->HasObjective());
4477 AddMonitors();
4478 }
4479
4480 NestedOptimize(DecisionBuilder* const db, Assignment* const solution,
4481 bool maximize, int64 step,
4482 const std::vector<SearchMonitor*>& monitors)
4483 : db_(db),
4484 solution_(solution),
4485 maximize_(maximize),
4486 step_(step),
4487 monitors_(monitors),
4488 collector_(nullptr) {
4489 CHECK(db != nullptr);
4490 CHECK(solution != nullptr);
4491 CHECK(solution->HasObjective());
4492 AddMonitors();
4493 }
4494
4495 void AddMonitors() {
4496 Solver* const solver = solution_->solver();
4497 collector_ = solver->MakeLastSolutionCollector(solution_);
4498 monitors_.push_back(collector_);
4499 OptimizeVar* const optimize =
4500 solver->MakeOptimize(maximize_, solution_->Objective(), step_);
4501 monitors_.push_back(optimize);
4502 }
4503
4504 Decision* Next(Solver* solver) override {
4505 solver->Solve(db_, monitors_);
4506 if (collector_->solution_count() == 0) {
4507 solver->Fail();
4508 }
4509 collector_->solution(0)->Restore();
4510 return nullptr;
4511 }
4512
4513 std::string DebugString() const override {
4514 return absl::StrFormat("NestedOptimize(db = %s, maximize = %d, step = %d)",
4515 db_->DebugString(), maximize_, step_);
4516 }
4517
4518 void Accept(ModelVisitor* const visitor) const override {
4519 db_->Accept(visitor);
4520 }
4521
4522 private:
4523 DecisionBuilder* const db_;
4524 Assignment* const solution_;
4525 const bool maximize_;
4526 const int64 step_;
4527 std::vector<SearchMonitor*> monitors_;
4528 SolutionCollector* collector_;
4529};
4530} // namespace
4531
4533 Assignment* const solution,
4534 bool maximize, int64 step) {
4535 return RevAlloc(new NestedOptimize(db, solution, maximize, step));
4536}
4537
4539 Assignment* const solution,
4540 bool maximize, int64 step,
4541 SearchMonitor* const monitor1) {
4542 std::vector<SearchMonitor*> monitors;
4543 monitors.push_back(monitor1);
4544 return RevAlloc(new NestedOptimize(db, solution, maximize, step, monitors));
4545}
4546
4548 Assignment* const solution,
4549 bool maximize, int64 step,
4550 SearchMonitor* const monitor1,
4551 SearchMonitor* const monitor2) {
4552 std::vector<SearchMonitor*> monitors;
4553 monitors.push_back(monitor1);
4554 monitors.push_back(monitor2);
4555 return RevAlloc(new NestedOptimize(db, solution, maximize, step, monitors));
4556}
4557
4559 Assignment* const solution,
4560 bool maximize, int64 step,
4561 SearchMonitor* const monitor1,
4562 SearchMonitor* const monitor2,
4563 SearchMonitor* const monitor3) {
4564 std::vector<SearchMonitor*> monitors;
4565 monitors.push_back(monitor1);
4566 monitors.push_back(monitor2);
4567 monitors.push_back(monitor3);
4568 return RevAlloc(new NestedOptimize(db, solution, maximize, step, monitors));
4569}
4570
4572 DecisionBuilder* const db, Assignment* const solution, bool maximize,
4573 int64 step, SearchMonitor* const monitor1, SearchMonitor* const monitor2,
4574 SearchMonitor* const monitor3, SearchMonitor* const monitor4) {
4575 std::vector<SearchMonitor*> monitors;
4576 monitors.push_back(monitor1);
4577 monitors.push_back(monitor2);
4578 monitors.push_back(monitor3);
4579 monitors.push_back(monitor4);
4580 return RevAlloc(new NestedOptimize(db, solution, maximize, step, monitors));
4581}
4582
4584 DecisionBuilder* const db, Assignment* const solution, bool maximize,
4585 int64 step, const std::vector<SearchMonitor*>& monitors) {
4586 return RevAlloc(new NestedOptimize(db, solution, maximize, step, monitors));
4587}
4588
4589// ---------- Restart ----------
4590
4591namespace {
4592// Luby Strategy
4593int64 NextLuby(int i) {
4594 DCHECK_GT(i, 0);
4595 DCHECK_LT(i, kint32max);
4596 int64 power;
4597
4598 // let's find the least power of 2 >= (i+1).
4599 power = 2;
4600 // Cannot overflow, because bounded by kint32max + 1.
4601 while (power < (i + 1)) {
4602 power <<= 1;
4603 }
4604 if (power == i + 1) {
4605 return (power / 2);
4606 }
4607 return NextLuby(i - (power / 2) + 1);
4608}
4609
4610class LubyRestart : public SearchMonitor {
4611 public:
4612 LubyRestart(Solver* const s, int scale_factor)
4613 : SearchMonitor(s),
4614 scale_factor_(scale_factor),
4615 iteration_(1),
4616 current_fails_(0),
4617 next_step_(scale_factor) {
4618 CHECK_GE(scale_factor, 1);
4619 }
4620
4621 ~LubyRestart() override {}
4622
4623 void BeginFail() override {
4624 if (++current_fails_ >= next_step_) {
4625 current_fails_ = 0;
4626 next_step_ = NextLuby(++iteration_) * scale_factor_;
4627 solver()->RestartCurrentSearch();
4628 }
4629 }
4630
4631 std::string DebugString() const override {
4632 return absl::StrFormat("LubyRestart(%i)", scale_factor_);
4633 }
4634
4635 private:
4636 const int scale_factor_;
4637 int iteration_;
4638 int64 current_fails_;
4639 int64 next_step_;
4640};
4641} // namespace
4642
4644 return RevAlloc(new LubyRestart(this, scale_factor));
4645}
4646
4647// ----- Constant Restart -----
4648
4649namespace {
4650class ConstantRestart : public SearchMonitor {
4651 public:
4652 ConstantRestart(Solver* const s, int frequency)
4653 : SearchMonitor(s), frequency_(frequency), current_fails_(0) {
4654 CHECK_GE(frequency, 1);
4655 }
4656
4657 ~ConstantRestart() override {}
4658
4659 void BeginFail() override {
4660 if (++current_fails_ >= frequency_) {
4661 current_fails_ = 0;
4662 solver()->RestartCurrentSearch();
4663 }
4664 }
4665
4666 std::string DebugString() const override {
4667 return absl::StrFormat("ConstantRestart(%i)", frequency_);
4668 }
4669
4670 private:
4671 const int frequency_;
4672 int64 current_fails_;
4673};
4674} // namespace
4675
4677 return RevAlloc(new ConstantRestart(this, frequency));
4678}
4679
4680// ---------- Symmetry Breaking ----------
4681
4682// The symmetry manager maintains a list of problem symmetries. Each
4683// symmetry is called on each decision and should return a term
4684// representing the boolean status of the symmetrical decision.
4685// e.g. : the decision is x == 3, the symmetrical decision is y == 5
4686// then the symmetry breaker should use
4687// AddIntegerVariableEqualValueClause(y, 5). Once this is done, upon
4688// refutation, for each symmetry breaker, the system adds a constraint
4689// that will forbid the symmetrical variation of the current explored
4690// search tree. This constraint can be expressed very simply just by
4691// keeping the list of current symmetrical decisions.
4692//
4693// This is called Symmetry Breaking During Search (Ian Gent, Barbara
4694// Smith, ECAI 2000).
4695// http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3788&rep=rep1&type=pdf
4696//
4698 public:
4700 const std::vector<SymmetryBreaker*>& visitors)
4701 : SearchMonitor(s),
4702 visitors_(visitors),
4703 clauses_(visitors.size()),
4704 decisions_(visitors.size()),
4705 directions_(visitors.size()) { // false = left.
4706 for (int i = 0; i < visitors_.size(); ++i) {
4707 visitors_[i]->set_symmetry_manager_and_index(this, i);
4708 }
4709 }
4710
4711 ~SymmetryManager() override {}
4712
4713 void EndNextDecision(DecisionBuilder* const db, Decision* const d) override {
4714 if (d) {
4715 for (int i = 0; i < visitors_.size(); ++i) {
4716 const void* const last = clauses_[i].Last();
4717 d->Accept(visitors_[i]);
4718 if (last != clauses_[i].Last()) {
4719 // Synchroneous push of decision as marker.
4720 decisions_[i].Push(solver(), d);
4721 directions_[i].Push(solver(), false);
4722 }
4723 }
4724 }
4725 }
4726
4727 void RefuteDecision(Decision* d) override {
4728 for (int i = 0; i < visitors_.size(); ++i) {
4729 if (decisions_[i].Last() != nullptr && decisions_[i].LastValue() == d) {
4730 CheckSymmetries(i);
4731 }
4732 }
4733 }
4734
4735 // TODO(user) : Improve speed, cache previous min and build them
4736 // incrementally.
4739 SimpleRevFIFO<bool>::Iterator tmp_dir(&directions_[index]);
4740 Constraint* ct = nullptr;
4741 {
4742 std::vector<IntVar*> guard;
4743 // keep the last entry for later, if loop doesn't exit.
4744 ++tmp;
4745 ++tmp_dir;
4746 while (tmp.ok()) {
4747 IntVar* const term = *tmp;
4748 if (!*tmp_dir) {
4749 if (term->Max() == 0) {
4750 // Premise is wrong. The clause will never apply.
4751 return;
4752 }
4753 if (term->Min() == 0) {
4754 DCHECK_EQ(1, term->Max());
4755 // Premise may be true. Adding to guard vector.
4756 guard.push_back(term);
4757 }
4758 }
4759 ++tmp;
4760 ++tmp_dir;
4761 }
4762 guard.push_back(clauses_[index].LastValue());
4763 directions_[index].SetLastValue(true);
4764 // Given premises: xi = ai
4765 // and a term y != b
4766 // The following is equivalent to
4767 // And(xi == a1) => y != b.
4768 ct = solver()->MakeEquality(solver()->MakeMin(guard), Zero());
4769 }
4770 DCHECK(ct != nullptr);
4772 }
4773
4774 void AddTermToClause(SymmetryBreaker* const visitor, IntVar* const term) {
4775 clauses_[visitor->index_in_symmetry_manager()].Push(solver(), term);
4776 }
4777
4778 std::string DebugString() const override { return "SymmetryManager"; }
4779
4780 private:
4781 const std::vector<SymmetryBreaker*> visitors_;
4782 std::vector<SimpleRevFIFO<IntVar*>> clauses_;
4783 std::vector<SimpleRevFIFO<Decision*>> decisions_;
4784 std::vector<SimpleRevFIFO<bool>> directions_;
4785};
4786
4787// ----- Symmetry Breaker -----
4788
4790 int64 value) {
4791 CHECK(var != nullptr);
4792 Solver* const solver = var->solver();
4793 IntVar* const term = solver->MakeIsEqualCstVar(var, value);
4794 symmetry_manager()->AddTermToClause(this, term);
4795}
4796
4798 IntVar* const var, int64 value) {
4799 CHECK(var != nullptr);
4800 Solver* const solver = var->solver();
4801 IntVar* const term = solver->MakeIsGreaterOrEqualCstVar(var, value);
4802 symmetry_manager()->AddTermToClause(this, term);
4803}
4804
4806 IntVar* const var, int64 value) {
4807 CHECK(var != nullptr);
4808 Solver* const solver = var->solver();
4809 IntVar* const term = solver->MakeIsLessOrEqualCstVar(var, value);
4810 symmetry_manager()->AddTermToClause(this, term);
4811}
4812
4813// ----- API -----
4814
4816 const std::vector<SymmetryBreaker*>& visitors) {
4817 return RevAlloc(new SymmetryManager(this, visitors));
4818}
4819
4821 std::vector<SymmetryBreaker*> visitors;
4822 visitors.push_back(v1);
4823 return MakeSymmetryManager(visitors);
4824}
4825
4827 SymmetryBreaker* const v2) {
4828 std::vector<SymmetryBreaker*> visitors;
4829 visitors.push_back(v1);
4830 visitors.push_back(v2);
4831 return MakeSymmetryManager(visitors);
4832}
4833
4835 SymmetryBreaker* const v2,
4836 SymmetryBreaker* const v3) {
4837 std::vector<SymmetryBreaker*> visitors;
4838 visitors.push_back(v1);
4839 visitors.push_back(v2);
4840 visitors.push_back(v3);
4841 return MakeSymmetryManager(visitors);
4842}
4843
4845 SymmetryBreaker* const v2,
4846 SymmetryBreaker* const v3,
4847 SymmetryBreaker* const v4) {
4848 std::vector<SymmetryBreaker*> visitors;
4849 visitors.push_back(v1);
4850 visitors.push_back(v2);
4851 visitors.push_back(v3);
4852 visitors.push_back(v4);
4853 return MakeSymmetryManager(visitors);
4854}
4855} // 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_LE(val1, val2)
Definition: base/logging.h:887
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#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
#define DCHECK(condition)
Definition: base/logging.h:884
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define VLOG(verboselevel)
Definition: base/logging.h:978
An Assignment is a variable -> domains mapping, used to report solutions to the user.
const std::vector< int > & Unperformed(const SequenceVar *const var) const
int64 Value(const IntVar *const var) const
const std::vector< int > & BackwardSequence(const SequenceVar *const var) const
int64 StartValue(const IntervalVar *const var) const
const std::vector< int > & ForwardSequence(const SequenceVar *const var) const
int64 DurationValue(const IntervalVar *const var) const
int64 EndValue(const IntervalVar *const var) const
int64 PerformedValue(const IntervalVar *const var) const
A BaseObject is the root of all reversibly allocated objects.
bool Get(uint32 index) const
Definition: bitmap.h:58
void Set(uint32 index, bool value)
Definition: bitmap.h:62
A constraint is the main modeling object.
A DecisionBuilder is responsible for creating the search tree.
A Decision represents a choice point in the search tree.
virtual void Accept(DecisionVisitor *const visitor) const
Accepts the given visitor.
virtual void Apply(Solver *const s)=0
Apply will be called first when the decision is executed.
virtual void Refute(Solver *const s)=0
Refute will be called after a backtrack.
std::string DebugString() const override
bool Check() override
This method is called to check the status of the limit.
Definition: search.cc:4194
void Init() override
This method is called when the search limit is initialized.
Definition: search.cc:4162
void Copy(const SearchLimit *const limit) override
Copy a limit.
Definition: search.cc:4170
bool AtSolution() override
This method is called when a valid solution is found.
Definition: search.cc:4218
ImprovementSearchLimit(Solver *const s, IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
Definition: search.cc:4144
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Definition: search.cc:4187
The class IntExpr is the base of all integer expressions in constraint programming.
virtual void SetMax(int64 m)=0
virtual void SetValue(int64 v)
This method sets the value of the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual void SetMin(int64 m)=0
virtual int64 Max() const =0
virtual int64 Min() const =0
The class IntVar is a subset of IntExpr.
virtual int64 Value() const =0
This method returns the value of the variable.
Interval variables are often used in scheduling.
static int64 FastInt64Round(double x)
Definition: mathutil.h:138
static const char kSolutionLimitArgument[]
static const char kBranchesLimitArgument[]
static const char kSmartTimeCheckArgument[]
virtual void BeginVisitExtension(const std::string &type)
virtual void EndVisitExtension(const std::string &type)
virtual void VisitIntegerArgument(const std::string &arg_name, int64 value)
Visit integer arguments.
static const char kVariableGroupExtension[]
static const char kFailuresLimitArgument[]
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *const argument)
Visit integer expression argument.
This class encapsulates an objective.
void EnterSearch() override
Beginning of the search.
Definition: search.cc:2738
void BeginNextDecision(DecisionBuilder *const db) override
Before calling DecisionBuilder::Next.
Definition: search.cc:2747
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
Definition: search.cc:2840
bool AcceptSolution() override
This method is called when a solution is found.
Definition: search.cc:2765
virtual std::string Print() const
Definition: search.cc:2824
bool AtSolution() override
This method is called when a valid solution is found.
Definition: search.cc:2777
void RefuteDecision(Decision *const d) override
Before refuting the decision.
Definition: search.cc:2763
IntVar * Var() const
Returns the variable that is optimized.
OptimizeVar(Solver *const s, bool maximize, IntVar *const a, int64 step)
Definition: search.cc:2717
bool AcceptDelta(Assignment *delta, Assignment *deltadelta) override
Internal methods.
Definition: search.cc:2790
std::string DebugString() const override
Definition: search.cc:2828
Usual limit based on wall_time, number of explored branches and number of failures in the search tree...
bool Check() override
This method is called to check the status of the limit.
Definition: search.cc:3988
absl::Duration duration_limit() const
bool IsUncheckedSolutionLimitReached() override
Returns true if the limit of solutions has been reached including unchecked solutions.
Definition: search.cc:4039
void Init() override
This method is called when the search limit is initialized.
Definition: search.cc:4009
void ExitSearch() override
End of the search.
Definition: search.cc:4020
int ProgressPercent() override
Returns a percentage representing the propress of the search before reaching limits.
Definition: search.cc:3996
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
Definition: search.cc:4053
void Copy(const SearchLimit *const limit) override
Copy a limit.
Definition: search.cc:3969
void UpdateLimits(absl::Duration time, int64 branches, int64 failures, int64 solutions)
Definition: search.cc:4031
RegularLimit * MakeIdenticalClone() const
Definition: search.cc:3982
std::string DebugString() const override
Definition: search.cc:4045
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Definition: search.cc:3980
Base class of all search limits.
bool crossed() const
Returns true if the limit has been crossed.
The base class of all search logs that periodically outputs information when the search is running.
void BeginFail() override
Just when the failure occurs.
Definition: search.cc:178
virtual void OutputLine(const std::string &line)
Definition: search.cc:256
void EnterSearch() override
Beginning of the search.
Definition: search.cc:85
void RefuteDecision(Decision *const decision) override
Before refuting the decision.
Definition: search.cc:208
void ExitSearch() override
End of the search.
Definition: search.cc:93
SearchLog(Solver *const s, OptimizeVar *const obj, IntVar *const var, double scaling_factor, double offset, std::function< std::string()> display_callback, bool display_on_new_solutions_only, int period)
Definition: search.cc:56
void BeginInitialPropagation() override
Before the initial propagation.
Definition: search.cc:246
void NoMoreSolutions() override
When the search tree is finished.
Definition: search.cc:180
void ApplyDecision(Decision *const decision) override
Before applying the decision.
Definition: search.cc:200
bool AtSolution() override
This method is called when a valid solution is found.
Definition: search.cc:106
std::string DebugString() const override
Definition: search.cc:83
void AcceptUncheckedNeighbor() override
After accepting an unchecked neighbor during local search.
Definition: search.cc:176
void EndInitialPropagation() override
After the initial propagation.
Definition: search.cc:248
A search monitor is a simple set of callbacks to monitor all search events.
virtual void ExitSearch()
End of the search.
virtual bool AtSolution()
This method is called when a valid solution is found.
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
This iterator is not stable with respect to deletion.
This class represent a reversible FIFO structure.
This class is the root class of all solution collectors.
void EnterSearch() override
Beginning of the search.
Definition: search.cc:2263
int64 Value(int n, IntVar *const var) const
This is a shortcut to get the Value of 'var' in the nth solution.
Definition: search.cc:2347
int64 failures(int n) const
Returns the number of failures encountered at the time of the nth solution.
Definition: search.cc:2337
void Push(const SolutionData &data)
void PushSolution()
Push the current state as a new solution.
Definition: search.cc:2272
void AddObjective(IntVar *const objective)
Definition: search.cc:2257
std::vector< Assignment * > recycle_solutions_
std::vector< SolutionData > solution_data_
void Add(IntVar *const var)
Add API.
Definition: search.cc:2221
int solution_count() const
Returns how many solutions were stored during the search.
Definition: search.cc:2325
int64 DurationValue(int n, IntervalVar *const var) const
This is a shortcut to get the DurationValue of 'var' in the nth solution.
Definition: search.cc:2355
int64 PerformedValue(int n, IntervalVar *const var) const
This is a shortcut to get the PerformedValue of 'var' in the nth solution.
Definition: search.cc:2363
const std::vector< int > & Unperformed(int n, SequenceVar *const var) const
This is a shortcut to get the list of unperformed of 'var' in the nth solution.
Definition: search.cc:2377
SolutionData BuildSolutionDataForCurrentState()
Definition: search.cc:2284
Assignment * solution(int n) const
Returns the nth solution.
Definition: search.cc:2320
int64 wall_time(int n) const
Returns the wall time in ms for the nth solution.
Definition: search.cc:2327
int64 EndValue(int n, IntervalVar *const var) const
This is a shortcut to get the EndValue of 'var' in the nth solution.
Definition: search.cc:2359
const std::vector< int > & ForwardSequence(int n, SequenceVar *const var) const
This is a shortcut to get the ForwardSequence of 'var' in the nth solution.
Definition: search.cc:2367
int64 objective_value(int n) const
Returns the objective value of the nth solution.
Definition: search.cc:2342
void FreeSolution(Assignment *solution)
Definition: search.cc:2309
std::unique_ptr< Assignment > prototype_
SolutionCollector(Solver *const solver, const Assignment *assignment)
Definition: search.cc:2205
int64 branches(int n) const
Returns the number of branches when the nth solution was found.
Definition: search.cc:2332
void PopSolution()
Remove and delete the last popped solution.
Definition: search.cc:2276
std::string DebugString() const override
const std::vector< int > & BackwardSequence(int n, SequenceVar *const var) const
This is a shortcut to get the BackwardSequence of 'var' in the nth solution.
Definition: search.cc:2372
int64 StartValue(int n, IntervalVar *const var) const
This is a shortcut to get the StartValue of 'var' in the nth solution.
Definition: search.cc:2351
SearchMonitor * MakeLubyRestart(int scale_factor)
This search monitor will restart the search periodically.
Definition: search.cc:4643
SolutionCollector * MakeAllSolutionCollector()
Collect all solutions of the search.
Definition: search.cc:2711
RegularLimit * MakeLimit(absl::Duration time, int64 branches, int64 failures, int64 solutions, bool smart_time_check=false, bool cumulative=false)
Limits the search with the 'time', 'branches', 'failures' and 'solutions' limits.
Definition: search.cc:4117
Decision * MakeSplitVariableDomain(IntVar *const var, int64 val, bool start_with_lower_half)
Definition: search.cc:1679
OptimizeVar * MakeWeightedMaximize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a maximization weigthed objective.
Definition: search.cc:2910
SolutionCollector * MakeLastSolutionCollector()
Collect the last solution of the search.
Definition: search.cc:2481
RegularLimit * MakeSolutionsLimit(int64 solutions)
Creates a search limit that constrains the number of solutions found during the search.
Definition: search.cc:4105
SearchMonitor * MakeAtSolutionCallback(std::function< void()> callback)
Definition: search.cc:418
IntVar * MakeIsGreaterOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var >= value)
Definition: expr_cst.cc:677
SearchLimit * MakeCustomLimit(std::function< bool()> limiter)
Callback-based search limit.
Definition: search.cc:4370
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
Definition: range_cst.cc:512
int64 solutions() const
The number of solutions found since the start of the search.
Decision * MakeAssignVariableValueOrFail(IntVar *const var, int64 value)
Definition: search.cc:1596
OptimizeVar * MakeMaximize(IntVar *const v, int64 step)
Creates a maximization objective.
Definition: search.cc:2853
ConstraintSolverParameters parameters() const
Stored Parameters.
int64 failures() const
The number of failures encountered since the creation of the solver.
SearchMonitor * MakeSymmetryManager(const std::vector< SymmetryBreaker * > &visitors)
Symmetry Breaking.
Definition: search.cc:4815
std::function< bool(int64, int64, int64)> VariableValueComparator
SearchMonitor * MakeSimulatedAnnealing(bool maximize, IntVar *const v, int64 step, int64 initial_temperature)
Creates a Simulated Annealing monitor.
Definition: search.cc:3352
absl::Time Now() const
The 'absolute time' as seen by the solver.
Assignment * GetOrCreateLocalSearchState()
Returns (or creates) an assignment representing the state of local search.
DecisionBuilder * Try(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which will create a search tree where each decision builder is called from...
Definition: search.cc:700
RegularLimit * MakeFailuresLimit(int64 failures)
Creates a search limit that constrains the number of failures that can happen when exploring the sear...
Definition: search.cc:4100
SearchMonitor * MakeSearchLog(int branch_period)
The SearchMonitors below will display a periodic search log on LOG(INFO) every branch_period branches...
Definition: search.cc:284
IntValueStrategy
This enum describes the strategy used to select the next variable value to set.
@ INT_VALUE_SIMPLE
The simple selection is ASSIGN_MIN_VALUE.
@ ASSIGN_CENTER_VALUE
Selects the first possible value which is the closest to the center of the domain of the selected var...
@ SPLIT_UPPER_HALF
Split the domain in two around the center, and choose the lower part first.
@ 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.
@ INT_VALUE_DEFAULT
The default behavior is ASSIGN_MIN_VALUE.
@ ASSIGN_MAX_VALUE
Selects the max value of the selected variable.
@ SPLIT_LOWER_HALF
Split the domain in two around the center, and choose the lower part first.
Decision * MakeAssignVariablesValues(const std::vector< IntVar * > &vars, const std::vector< int64 > &values)
Definition: search.cc:1752
Decision * MakeAssignVariableValueOrDoNothing(IntVar *const var, int64 value)
Definition: search.cc:1625
void AddConstraint(Constraint *const c)
Adds the constraint 'c' to the model.
DecisionBuilder * MakeSolveOnce(DecisionBuilder *const db)
SolveOnce will collapse a search tree described by a decision builder 'db' and a set of monitors and ...
Definition: search.cc:4413
Decision * MakeVariableLessOrEqualValue(IntVar *const var, int64 value)
Definition: search.cc:1684
int SearchDepth() const
Gets the search depth of the current active search.
IntVar * MakeIsEqualCstVar(IntExpr *const var, int64 value)
status var of (var == value)
Definition: expr_cst.cc:460
OptimizeVar * MakeWeightedOptimize(bool maximize, const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a weighted objective with a given sense (true = maximization).
Definition: search.cc:2896
int64 wall_time() const
DEPRECATED: Use Now() instead.
RegularLimit * MakeBranchesLimit(int64 branches)
Creates a search limit that constrains the number of branches explored in the search tree.
Definition: search.cc:4095
ImprovementSearchLimit * MakeImprovementLimit(IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
Limits the search based on the improvements of 'objective_var'.
Definition: search.cc:4259
SearchMonitor * MakeConstantRestart(int frequency)
This search monitor will restart the search periodically after 'frequency' failures.
Definition: search.cc:4676
std::function< int64(int64, int64, int64)> IndexEvaluator3
EvaluatorStrategy
This enum is used by Solver::MakePhase to specify how to select variables and values during the searc...
@ CHOOSE_STATIC_GLOBAL_BEST
Pairs are compared at the first call of the selector, and results are cached.
@ CHOOSE_DYNAMIC_GLOBAL_BEST
Pairs are compared each time a variable is selected.
void set_optimization_direction(OptimizationDirection direction)
int64 neighbors() const
The number of neighbors created.
RegularLimitParameters MakeDefaultRegularLimitParameters() const
Creates a regular limit proto containing default values.
Definition: search.cc:4131
RegularLimit * MakeTimeLimit(absl::Duration time)
Creates a search limit that constrains the running time.
Definition: search.cc:4090
Decision * MakeVariableGreaterOrEqualValue(IntVar *const var, int64 value)
Definition: search.cc:1688
SearchMonitor * MakeSearchTrace(const std::string &prefix)
Creates a search monitor that will trace precisely the behavior of the search.
Definition: search.cc:394
std::function< int64(int64)> IndexEvaluator1
Callback typedefs.
int TopProgressPercent()
Returns a percentage representing the propress of the search before reaching the limits of the top-le...
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_MIN_SIZE
Among unbound variables, select the variable with the smallest size.
@ CHOOSE_FIRST_UNBOUND
Select the first unbound variable.
@ CHOOSE_PATH
Selects the next unbound variable on a path, the path being defined by the variables: var[i] correspo...
@ CHOOSE_HIGHEST_MAX
Among unbound variables, select the variable with the highest maximal value.
@ CHOOSE_MIN_SIZE_LOWEST_MIN
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ INT_VAR_DEFAULT
The default behavior is CHOOSE_FIRST_UNBOUND.
@ CHOOSE_MIN_SIZE_HIGHEST_MAX
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_MAX_REGRET_ON_MIN
Among unbound variables, select the variable with the largest gap between the first and the second va...
@ CHOOSE_MIN_SIZE_HIGHEST_MIN
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_MAX_SIZE
Among unbound variables, select the variable with the highest size.
@ INT_VAR_SIMPLE
The simple selection is CHOOSE_FIRST_UNBOUND.
@ CHOOSE_MIN_SIZE_LOWEST_MAX
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_LOWEST_MIN
Among unbound variables, select the variable with the smallest minimal value.
DecisionBuilder * MakePhase(const std::vector< IntVar * > &vars, IntVarStrategy var_str, IntValueStrategy val_str)
Phases on IntVar arrays.
Definition: search.cc:2008
std::function< int64(int64, int64)> IndexEvaluator2
DecisionBuilder * MakeNestedOptimize(DecisionBuilder *const db, Assignment *const solution, bool maximize, int64 step)
NestedOptimize will collapse a search tree described by a decision builder 'db' and a set of monitors...
Definition: search.cc:4532
int64 unchecked_solutions() const
The number of unchecked solutions found by local search.
SearchMonitor * MakeEnterSearchCallback(std::function< void()> callback)
--— Callback-based search monitors --—
Definition: search.cc:438
OptimizeVar * MakeWeightedMinimize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a minimization weighted objective.
Definition: search.cc:2903
int64 branches() const
The number of branches explored since the creation of the solver.
std::function< int64(Solver *solver, const std::vector< IntVar * > &vars, int64 first_unbound, int64 last_unbound)> VariableIndexSelector
std::function< void(Solver *)> Action
SolutionCollector * MakeFirstSolutionCollector()
Collect the first solution of the search.
Definition: search.cc:2435
IntVar * MakeIsLessOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var <= value)
Definition: expr_cst.cc:776
OptimizeVar * MakeMinimize(IntVar *const v, int64 step)
Creates a minimization objective.
Definition: search.cc:2849
std::function< int64(const IntVar *v, int64 id)> VariableValueSelector
SearchMonitor * MakeExitSearchCallback(std::function< void()> callback)
Definition: search.cc:458
static int64 MemoryUsage()
Current memory usage in bytes.
DecisionBuilder * MakeDecisionBuilderFromAssignment(Assignment *const assignment, DecisionBuilder *const db, const std::vector< IntVar * > &vars)
Returns a decision builder for which the left-most leaf corresponds to assignment,...
Definition: search.cc:2195
OptimizeVar * MakeOptimize(bool maximize, IntVar *const v, int64 step)
Creates a objective with a given sense (true = maximization).
Definition: search.cc:2857
T * RevAlloc(T *object)
Registers the given object as being reversible.
A symmetry breaker is an object that will visit a decision and create the 'symmetrical' decision in r...
void AddIntegerVariableEqualValueClause(IntVar *const var, int64 value)
Definition: search.cc:4789
void AddIntegerVariableLessOrEqualValueClause(IntVar *const var, int64 value)
Definition: search.cc:4805
void AddIntegerVariableGreaterOrEqualValueClause(IntVar *const var, int64 value)
Definition: search.cc:4797
void AddTermToClause(SymmetryBreaker *const visitor, IntVar *const term)
Definition: search.cc:4774
void EndNextDecision(DecisionBuilder *const db, Decision *const d) override
After calling DecisionBuilder::Next, along with the returned decision.
Definition: search.cc:4713
void RefuteDecision(Decision *d) override
Before refuting the decision.
Definition: search.cc:4727
SymmetryManager(Solver *const s, const std::vector< SymmetryBreaker * > &visitors)
Definition: search.cc:4699
std::string DebugString() const override
Definition: search.cc:4778
std::vector< IntVarIterator * > iterators_
Block * next
SatParameters parameters
CpModelProto proto
const std::string name
const Constraint * ct
MPCallback * callback
static const int64 kint64max
int64_t int64
static const uint64 kuint64max
static const int32 kint32max
uint64_t uint64
static const int64 kint64min
const int64 offset_
Definition: interval.cc:2076
const int INFO
Definition: log_severity.h:31
const int FATAL
Definition: log_severity.h:32
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
Definition: cleanup.h:22
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:26
void STLDeleteElements(T *container)
Definition: stl_util.h:372
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition: map_util.h:155
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1487
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
std::pair< int64, int64 > Arc
Definition: search.cc:3361
BaseAssignVariables::Mode ChooseMode(Solver::IntValueStrategy val_str)
Definition: search.cc:1998
bool AcceptDelta(Search *const search, Assignment *delta, Assignment *deltadelta)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:45
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
Definition: utilities.cc:822
void AcceptNeighbor(Search *const search)
STL namespace.
int index
Definition: pack.cc:508
int64 time
Definition: resource.cc:1683
int64 delta
Definition: resource.cc:1684
int64 bound
int64 step_
Definition: search.cc:2952
std::unique_ptr< int64[]> delta_cache_
Definition: search.cc:3496
const double penalty_factor_
Definition: search.cc:3493
const int64 stamp_
Definition: search.cc:3039
std::vector< DecisionBuilder * > builders_
Definition: search.cc:476
int64 assignment_penalized_value_
Definition: search.cc:3489
int64 value
Definition: search.cc:1354
int64 old_penalized_value_
Definition: search.cc:3490
BaseVariableAssignmentSelector *const selector_
Definition: search.cc:1856
std::function< int64(int64, int64)> evaluator_
Definition: search.cc:1361
int64 best_
Definition: search.cc:2500
Rev< int64 > first_unbound_
Definition: search.cc:787
const int solution_count_
Definition: search.cc:2578
ABSL_FLAG(bool, cp_use_sparse_gls_penalties, false, "Use sparse implementation to store Guided Local Search penalties")
IntVar * penalized_objective_
Definition: search.cc:3487
int64 current_
Definition: search.cc:2953
const bool maximize_
Definition: search.cc:2499
std::vector< IntVar * > vars_
Definition: search.cc:786
int64 var
Definition: search.cc:1353
IntVar *const objective_
Definition: search.cc:2951
std::priority_queue< std::pair< int64, SolutionData > > solutions_pq_
Definition: search.cc:2577
Rev< int64 > last_unbound_
Definition: search.cc:788
Solver *const solver_
Definition: search.cc:785
absl::flat_hash_map< const IntVar *, int64 > indices_
Definition: search.cc:3492
std::unique_ptr< int64[]> current_penalized_values_
Definition: search.cc:3495
bool incremental_
Definition: search.cc:3497
const Mode mode_
Definition: search.cc:1857
Creates a search monitor from logging parameters.