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"
42#include "ortools/constraint_solver/search_limit.pb.h"
46 "Use sparse implementation to store Guided Local Search penalties");
48 "Whether search related logging should be "
51 "Size limit to allow holes in variables from the strategy.");
57 double scaling_factor,
double offset,
58 std::function<std::string()> display_callback,
59 bool display_on_new_solutions_only,
int period)
65 scaling_factor_(scaling_factor),
67 display_callback_(
std::move(display_callback)),
68 display_on_new_solutions_only_(display_on_new_solutions_only),
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.";
86 const std::string buffer =
87 absl::StrFormat(
"Start search (%s)", MemoryUsage());
95 int64 ms = timer_->GetInMs();
99 const std::string buffer = absl::StrFormat(
100 "End search (time = %d ms, branches = %d, failures = %d, %s, speed = %d "
102 ms, branches,
solver()->failures(), MemoryUsage(), branches * 1000 / ms);
109 std::string obj_str =
"";
111 bool objective_updated =
false;
113 if (scaling_factor_ != 1.0 || offset_ != 0.0) {
114 return absl::StrFormat(
"%d (%.8lf)",
value,
115 scaling_factor_ * (
value + offset_));
117 return absl::StrCat(
value);
120 if (obj_ !=
nullptr && obj_->
Var()->
Bound()) {
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;
130 absl::StrAppend(&obj_str, scaled_str(current),
", ");
131 objective_updated =
true;
133 if (objective_updated) {
134 if (current > objective_min_) {
135 absl::StrAppend(&obj_str,
136 "objective minimum = ", scaled_str(objective_min_),
", ");
138 objective_min_ = current;
140 if (current < objective_max_) {
141 absl::StrAppend(&obj_str,
142 "objective maximum = ", scaled_str(objective_max_),
", ");
144 objective_max_ = current;
148 absl::StrAppendFormat(&log,
149 "Solution #%d (%stime = %d ms, branches = %d,"
150 " failures = %d, depth = %d",
151 nsol_++, obj_str, timer_->GetInMs(),
153 if (!
solver()->SearchContext().empty()) {
154 absl::StrAppendFormat(&log,
", %s",
solver()->SearchContext());
156 if (
solver()->neighbors() != 0) {
157 absl::StrAppendFormat(&log,
158 ", neighbors = %d, filtered neighbors = %d,"
159 " accepted neighbors = %d",
161 solver()->accepted_neighbors());
163 absl::StrAppendFormat(&log,
", %s", MemoryUsage());
166 absl::StrAppendFormat(&log,
", limit = %d%%", progress);
168 if (display_callback_) {
169 absl::StrAppendFormat(&log,
", %s", display_callback_());
181 std::string buffer = absl::StrFormat(
182 "Finished search tree (time = %d ms, branches = %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",
190 solver()->accepted_neighbors());
192 absl::StrAppendFormat(&buffer,
", %s", MemoryUsage());
193 if (!display_on_new_solutions_only_ && display_callback_) {
194 absl::StrAppendFormat(&buffer,
", %s", display_callback_());
203 if (
b % period_ == 0 &&
b > 0) {
209 min_right_depth_ =
std::min(min_right_depth_,
solver()->SearchDepth());
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) {
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;
225 if (obj_ !=
nullptr && objective_min_ !=
kint64max &&
227 absl::StrAppendFormat(&buffer,
228 ", objective minimum = %d"
229 ", objective maximum = %d",
230 objective_min_, objective_max_);
234 absl::StrAppendFormat(&buffer,
", limit = %d%%", progress);
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_);
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());
257 if (absl::GetFlag(FLAGS_cp_log_to_vlog)) {
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;
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);
280 return absl::StrFormat(
"memory used = %d", memory_usage);
293 int branch_period, std::function<std::string()> display_callback) {
295 std::move(display_callback));
300 std::function<std::string()> display_callback) {
302 std::move(display_callback),
true,
313 std::function<std::string()> display_callback) {
315 std::move(display_callback),
true,
331 SearchTrace(
Solver*
const s,
const std::string& prefix)
333 ~SearchTrace()
override {}
335 void EnterSearch()
override {
336 LOG(
INFO) << prefix_ <<
" EnterSearch(" << solver()->SolveDepth() <<
")";
338 void RestartSearch()
override {
339 LOG(
INFO) << prefix_ <<
" RestartSearch(" << solver()->SolveDepth() <<
")";
341 void ExitSearch()
override {
342 LOG(
INFO) << prefix_ <<
" ExitSearch(" << solver()->SolveDepth() <<
")";
344 void BeginNextDecision(DecisionBuilder*
const b)
override {
345 LOG(
INFO) << prefix_ <<
" BeginNextDecision(" <<
b <<
") ";
347 void EndNextDecision(DecisionBuilder*
const b, Decision*
const d)
override {
349 LOG(
INFO) << prefix_ <<
" EndNextDecision(" <<
b <<
", " << d <<
") ";
351 LOG(
INFO) << prefix_ <<
" EndNextDecision(" <<
b <<
") ";
354 void ApplyDecision(Decision*
const d)
override {
355 LOG(
INFO) << prefix_ <<
" ApplyDecision(" << d <<
") ";
357 void RefuteDecision(Decision*
const d)
override {
358 LOG(
INFO) << prefix_ <<
" RefuteDecision(" << d <<
") ";
360 void AfterDecision(Decision*
const d,
bool apply)
override {
361 LOG(
INFO) << prefix_ <<
" AfterDecision(" << d <<
", " << apply <<
") ";
363 void BeginFail()
override {
364 LOG(
INFO) << prefix_ <<
" BeginFail(" << solver()->SearchDepth() <<
")";
366 void EndFail()
override {
367 LOG(
INFO) << prefix_ <<
" EndFail(" << solver()->SearchDepth() <<
")";
369 void BeginInitialPropagation()
override {
370 LOG(
INFO) << prefix_ <<
" BeginInitialPropagation()";
372 void EndInitialPropagation()
override {
373 LOG(
INFO) << prefix_ <<
" EndInitialPropagation()";
375 bool AtSolution()
override {
376 LOG(
INFO) << prefix_ <<
" AtSolution()";
379 bool AcceptSolution()
override {
380 LOG(
INFO) << prefix_ <<
" AcceptSolution()";
383 void NoMoreSolutions()
override {
384 LOG(
INFO) << prefix_ <<
" NoMoreSolutions()";
387 std::string DebugString()
const override {
return "SearchTrace"; }
390 const std::string prefix_;
395 return RevAlloc(
new SearchTrace(
this, prefix));
402 AtSolutionCallback(
Solver*
const solver, std::function<
void()>
callback)
404 ~AtSolutionCallback()
override {}
405 bool AtSolution()
override;
408 const std::function<void()> callback_;
411bool AtSolutionCallback::AtSolution() {
425 EnterSearchCallback(
Solver*
const solver, std::function<
void()>
callback)
427 ~EnterSearchCallback()
override {}
428 void EnterSearch()
override;
431 const std::function<void()> callback_;
434void EnterSearchCallback::EnterSearch() { callback_(); }
445 ExitSearchCallback(
Solver*
const solver, std::function<
void()>
callback)
447 ~ExitSearchCallback()
override {}
448 void ExitSearch()
override;
451 const std::function<void()> callback_;
454void ExitSearchCallback::ExitSearch() { callback_(); }
467 CompositeDecisionBuilder();
468 explicit CompositeDecisionBuilder(
const std::vector<DecisionBuilder*>& dbs);
469 ~CompositeDecisionBuilder()
override;
471 void AppendMonitors(
Solver*
const solver,
472 std::vector<SearchMonitor*>*
const monitors)
override;
473 void Accept(
ModelVisitor*
const visitor)
const override;
479CompositeDecisionBuilder::CompositeDecisionBuilder() {}
481CompositeDecisionBuilder::CompositeDecisionBuilder(
482 const std::vector<DecisionBuilder*>& dbs) {
483 for (
int i = 0; i < dbs.size(); ++i) {
488CompositeDecisionBuilder::~CompositeDecisionBuilder() {}
490void CompositeDecisionBuilder::Add(DecisionBuilder*
const db) {
496void CompositeDecisionBuilder::AppendMonitors(
497 Solver*
const solver, std::vector<SearchMonitor*>*
const monitors) {
498 for (DecisionBuilder*
const db :
builders_) {
499 db->AppendMonitors(solver, monitors);
503void CompositeDecisionBuilder::Accept(ModelVisitor*
const visitor)
const {
504 for (DecisionBuilder*
const db :
builders_) {
513class ComposeDecisionBuilder :
public CompositeDecisionBuilder {
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;
525ComposeDecisionBuilder::ComposeDecisionBuilder() : start_index_(0) {}
527ComposeDecisionBuilder::ComposeDecisionBuilder(
528 const std::vector<DecisionBuilder*>& dbs)
529 : CompositeDecisionBuilder(dbs), start_index_(0) {}
531ComposeDecisionBuilder::~ComposeDecisionBuilder() {}
533Decision* ComposeDecisionBuilder::Next(Solver*
const s) {
535 for (
int i = start_index_; i < size; ++i) {
538 s->SaveAndSetValue(&start_index_, i);
542 s->SaveAndSetValue(&start_index_, size);
546std::string ComposeDecisionBuilder::DebugString()
const {
547 return absl::StrFormat(
"ComposeDecisionBuilder(%s)",
554 ComposeDecisionBuilder* c = RevAlloc(
new ComposeDecisionBuilder());
563 ComposeDecisionBuilder* c = RevAlloc(
new ComposeDecisionBuilder());
574 ComposeDecisionBuilder* c = RevAlloc(
new ComposeDecisionBuilder());
583 if (dbs.size() == 1) {
586 return RevAlloc(
new ComposeDecisionBuilder(dbs));
592class ClosureDecision :
public Decision {
595 : apply_(
std::move(apply)), refute_(
std::move(refute)) {}
596 ~ClosureDecision()
override {}
598 void Apply(Solver*
const s)
override { apply_(s); }
600 void Refute(Solver*
const s)
override { refute_(s); }
602 std::string
DebugString()
const override {
return "ClosureDecision"; }
605 Solver::Action apply_;
606 Solver::Action refute_;
611 return RevAlloc(
new ClosureDecision(std::move(apply), std::move(refute)));
618class TryDecisionBuilder;
620class TryDecision :
public Decision {
622 explicit TryDecision(TryDecisionBuilder*
const try_builder);
623 ~TryDecision()
override;
626 std::string
DebugString()
const override {
return "TryDecision"; }
629 TryDecisionBuilder*
const try_builder_;
632class TryDecisionBuilder :
public CompositeDecisionBuilder {
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);
642 TryDecision try_decision_;
643 int current_builder_;
644 bool start_new_builder_;
647TryDecision::TryDecision(TryDecisionBuilder*
const try_builder)
648 : try_builder_(try_builder) {}
650TryDecision::~TryDecision() {}
652void TryDecision::Apply(Solver*
const solver) {}
654void TryDecision::Refute(Solver*
const solver) {
655 try_builder_->AdvanceToNextBuilder(solver);
658TryDecisionBuilder::TryDecisionBuilder()
659 : CompositeDecisionBuilder(),
661 current_builder_(-1),
662 start_new_builder_(true) {}
664TryDecisionBuilder::TryDecisionBuilder(
const std::vector<DecisionBuilder*>& dbs)
665 : CompositeDecisionBuilder(dbs),
667 current_builder_(-1),
668 start_new_builder_(true) {}
670TryDecisionBuilder::~TryDecisionBuilder() {}
672Decision* TryDecisionBuilder::Next(Solver*
const solver) {
673 if (current_builder_ < 0) {
674 solver->SaveAndSetValue(¤t_builder_, 0);
675 start_new_builder_ =
true;
677 if (start_new_builder_) {
678 start_new_builder_ =
false;
679 return &try_decision_;
681 return builders_[current_builder_]->Next(solver);
685std::string TryDecisionBuilder::DebugString()
const {
686 return absl::StrFormat(
"TryDecisionBuilder(%s)",
690void TryDecisionBuilder::AdvanceToNextBuilder(Solver*
const solver) {
692 start_new_builder_ =
true;
693 if (current_builder_ >=
builders_.size()) {
702 TryDecisionBuilder* try_db =
RevAlloc(
new TryDecisionBuilder());
711 TryDecisionBuilder* try_db =
RevAlloc(
new TryDecisionBuilder());
722 TryDecisionBuilder* try_db =
RevAlloc(
new TryDecisionBuilder());
731 return RevAlloc(
new TryDecisionBuilder(dbs));
739class BaseVariableAssignmentSelector :
public BaseObject {
741 BaseVariableAssignmentSelector(
Solver* solver,
742 const std::vector<IntVar*>& vars)
748 ~BaseVariableAssignmentSelector()
override {}
750 virtual int64 SelectValue(
const IntVar* v,
int64 id) = 0;
753 virtual int64 ChooseVariable() = 0;
755 int64 ChooseVariableWrapper() {
758 if (!
vars_[i]->Bound()) {
767 if (!
vars_[i]->Bound()) {
772 return ChooseVariable();
775 void Accept(ModelVisitor*
const visitor)
const {
782 const std::vector<IntVar*>& vars()
const {
return vars_; }
793int64 ChooseFirstUnbound(Solver* solver,
const std::vector<IntVar*>& vars,
795 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
796 if (!vars[i]->Bound()) {
805int64 ChooseMinSizeLowestMin(Solver* solver,
const std::vector<IntVar*>& vars,
809 int64 best_index = -1;
810 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
811 IntVar*
const var = vars[i];
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();
826int64 ChooseMinSizeHighestMin(Solver* solver,
const std::vector<IntVar*>& vars,
830 int64 best_index = -1;
831 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
832 IntVar*
const var = vars[i];
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();
847int64 ChooseMinSizeLowestMax(Solver* solver,
const std::vector<IntVar*>& vars,
851 int64 best_index = -1;
852 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
853 IntVar*
const var = vars[i];
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();
868int64 ChooseMinSizeHighestMax(Solver* solver,
const std::vector<IntVar*>& vars,
872 int64 best_index = -1;
873 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
874 IntVar*
const var = vars[i];
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();
889int64 ChooseLowestMin(Solver* solver,
const std::vector<IntVar*>& vars,
892 int64 best_index = -1;
893 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
894 IntVar*
const var = vars[i];
896 if (
var->Min() < best_min) {
897 best_min =
var->Min();
907int64 ChooseHighestMax(Solver* solver,
const std::vector<IntVar*>& vars,
910 int64 best_index = -1;
911 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
912 IntVar*
const var = vars[i];
914 if (
var->Max() > best_max) {
915 best_max =
var->Max();
925int64 ChooseMinSize(Solver* solver,
const std::vector<IntVar*>& vars,
928 int64 best_index = -1;
929 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
930 IntVar*
const var = vars[i];
932 if (
var->Size() < best_size) {
933 best_size =
var->Size();
943int64 ChooseMaxSize(Solver* solver,
const std::vector<IntVar*>& vars,
946 int64 best_index = -1;
947 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
948 IntVar*
const var = vars[i];
950 if (
var->Size() > best_size) {
951 best_size =
var->Size();
961class HighestRegretSelectorOnMin :
public BaseObject {
963 explicit HighestRegretSelectorOnMin(
const std::vector<IntVar*>& vars)
965 for (
int64 i = 0; i < vars.size(); ++i) {
966 iterators_[i] = vars[i]->MakeDomainIterator(
true);
969 ~HighestRegretSelectorOnMin()
override {}
970 int64 Choose(Solver*
const s,
const std::vector<IntVar*>& vars,
972 std::string DebugString()
const override {
return "MaxRegretSelector"; }
980 return iterator->Value() - vmin;
987int64 HighestRegretSelectorOnMin::Choose(Solver*
const s,
988 const std::vector<IntVar*>& vars,
990 int64 last_unbound) {
991 int64 best_regret = 0;
993 for (
int64 i = first_unbound; i <= last_unbound; ++i) {
994 IntVar*
const var = vars[i];
996 const int64 regret = ComputeRegret(
var, i);
997 if (regret > best_regret) {
998 best_regret = regret;
1008int64 ChooseRandom(Solver* solver,
const std::vector<IntVar*>& vars,
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()) {
1023class CheapestVarSelector :
public BaseObject {
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,
1030 std::string DebugString()
const override {
return "CheapestVarSelector"; }
1036int64 CheapestVarSelector::Choose(Solver*
const s,
1037 const std::vector<IntVar*>& vars,
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) {
1056class PathSelector :
public BaseObject {
1059 ~PathSelector()
override {}
1060 int64 Choose(Solver*
const s,
const std::vector<IntVar*>& vars,
1062 std::string DebugString()
const override {
return "ChooseNextOnPath"; }
1065 bool UpdateIndex(
const std::vector<IntVar*>& vars,
int64*
index)
const;
1066 bool FindPathStart(
const std::vector<IntVar*>& vars,
int64*
index)
const;
1071int64 PathSelector::Choose(Solver*
const s,
const std::vector<IntVar*>& vars,
1074 if (!UpdateIndex(vars, &
index)) {
1078 while (vars[
index]->Bound()) {
1080 if (!UpdateIndex(vars, &
index)) {
1084 if (count >= vars.size() &&
1085 !FindPathStart(vars, &
index)) {
1089 first_.SetValue(s,
index);
1093bool PathSelector::UpdateIndex(
const std::vector<IntVar*>& vars,
1095 if (*
index >= vars.size()) {
1096 if (!FindPathStart(vars,
index)) {
1109bool PathSelector::FindPathStart(
const std::vector<IntVar*>& vars,
1112 for (
int64 i = vars.size() - 1; i >= 0; --i) {
1113 if (vars[i]->Bound()) {
1115 if (
next < vars.size() && !vars[
next]->Bound()) {
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;
1131 if (!has_possible_prev) {
1138 for (
int64 i = 0; i < vars.size(); ++i) {
1139 if (!vars[i]->Bound()) {
1149int64 SelectMinValue(
const IntVar* v,
int64 id) {
return v->Min(); }
1153int64 SelectMaxValue(
const IntVar* v,
int64 id) {
return v->Max(); }
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)) {
1163 const uint64 size = v->Size();
1164 Solver*
const s = v->solver();
1165 if (size > span / 4) {
1168 const int64 value = v->Min() + s->Rand64(span);
1169 if (v->Contains(
value)) {
1175 if (
index <= size / 2) {
1176 for (
int64 i = v->Min(); i <= v->Max(); ++i) {
1177 if (v->Contains(i)) {
1185 for (
int64 i = v->Max(); i > v->Min(); --i) {
1186 if (v->Contains(i)) {
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)) {
1207 const int64 mid = (vmin + vmax) / 2;
1208 if (v->Contains(mid)) {
1211 const int64 diameter = vmax - mid;
1212 for (
int64 i = 1; i <= diameter; ++i) {
1213 if (v->Contains(mid - i)) {
1216 if (v->Contains(mid + i)) {
1225int64 SelectSplitValue(
const IntVar* v,
int64 id) {
1226 const int64 vmin = v->Min();
1227 const int64 vmax = v->Max();
1235class CheapestValueSelector :
public BaseObject {
1239 : eval_(
std::move(eval)), tie_breaker_(
std::move(tie_breaker)) {}
1240 ~CheapestValueSelector()
override {}
1242 std::string DebugString()
const override {
return "CheapestValue"; }
1247 std::vector<int64> cache_;
1250int64 CheapestValueSelector::Select(
const IntVar* v,
int64 id) {
1253 std::unique_ptr<IntVarIterator> it(v->MakeDomainIterator(
false));
1254 for (
const int64 i : InitAndGetValues(it.get())) {
1255 int64 eval = eval_(
id, i);
1259 cache_.push_back(i);
1260 }
else if (eval == best) {
1261 cache_.push_back(i);
1265 if (tie_breaker_ ==
nullptr || cache_.size() == 1) {
1266 return cache_.back();
1268 return cache_[tie_breaker_(cache_.size())];
1280class BestValueByComparisonSelector :
public BaseObject {
1282 explicit BestValueByComparisonSelector(
1284 : comparator_(
std::move(comparator)) {}
1285 ~BestValueByComparisonSelector()
override {}
1287 std::string DebugString()
const override {
1288 return "BestValueByComparisonSelector";
1295int64 BestValueByComparisonSelector::Select(
const IntVar* v,
int64 id) {
1296 std::unique_ptr<IntVarIterator> it(v->MakeDomainIterator(
false));
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;
1311class VariableAssignmentSelector :
public BaseVariableAssignmentSelector {
1313 VariableAssignmentSelector(Solver* solver,
const std::vector<IntVar*>& vars,
1316 const std::string&
name)
1317 : BaseVariableAssignmentSelector(solver, vars),
1318 var_selector_(
std::move(var_selector)),
1319 value_selector_(
std::move(value_selector)),
1321 ~VariableAssignmentSelector()
override {}
1323 return value_selector_(
var,
id);
1325 int64 ChooseVariable()
override {
1329 std::string DebugString()
const override;
1334 const std::string name_;
1337std::string VariableAssignmentSelector::DebugString()
const {
1343class BaseEvaluatorSelector :
public BaseVariableAssignmentSelector {
1345 BaseEvaluatorSelector(Solver* solver,
const std::vector<IntVar*>& vars,
1347 ~BaseEvaluatorSelector()
override {}
1357 std::string DebugStringInternal(
const std::string&
name)
const {
1364BaseEvaluatorSelector::BaseEvaluatorSelector(
1365 Solver* solver,
const std::vector<IntVar*>& vars,
1367 : BaseVariableAssignmentSelector(solver, vars),
1372class DynamicEvaluatorSelector :
public BaseEvaluatorSelector {
1374 DynamicEvaluatorSelector(Solver* solver,
const std::vector<IntVar*>& vars,
1377 ~DynamicEvaluatorSelector()
override {}
1379 int64 ChooseVariable()
override;
1380 std::string DebugString()
const override;
1385 std::vector<Element> cache_;
1388DynamicEvaluatorSelector::DynamicEvaluatorSelector(
1389 Solver* solver,
const std::vector<IntVar*>& vars,
1392 : BaseEvaluatorSelector(solver, vars,
std::move(evaluator)),
1394 tie_breaker_(
std::move(tie_breaker)) {}
1396int64 DynamicEvaluatorSelector::SelectValue(
const IntVar*
var,
int64 id) {
1397 return cache_[first_].value;
1400int64 DynamicEvaluatorSelector::ChooseVariable() {
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())) {
1409 if (
value < best_evaluation) {
1410 best_evaluation =
value;
1412 cache_.push_back(Element(i, j));
1413 }
else if (
value == best_evaluation && tie_breaker_) {
1414 cache_.push_back(Element(i, j));
1420 if (cache_.empty()) {
1424 if (tie_breaker_ ==
nullptr || cache_.size() == 1) {
1426 return cache_.front().var;
1428 first_ = tie_breaker_(cache_.size());
1429 return cache_[first_].var;
1433std::string DynamicEvaluatorSelector::DebugString()
const {
1434 return DebugStringInternal(
"AssignVariablesOnDynamicEvaluator");
1439class StaticEvaluatorSelector :
public BaseEvaluatorSelector {
1441 StaticEvaluatorSelector(Solver* solver,
const std::vector<IntVar*>& vars,
1443 ~StaticEvaluatorSelector()
override {}
1445 int64 ChooseVariable()
override;
1446 std::string DebugString()
const override;
1453 bool operator()(
const Element& lhs,
const Element& rhs)
const {
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)));
1462 return evaluator_(element.var, element.value);
1470 std::vector<Element> elements_;
1474StaticEvaluatorSelector::StaticEvaluatorSelector(
1475 Solver* solver,
const std::vector<IntVar*>& vars,
1477 : BaseEvaluatorSelector(solver, vars, evaluator),
1481int64 StaticEvaluatorSelector::SelectValue(
const IntVar*
var,
int64 id) {
1482 return elements_[first_].value;
1485int64 StaticEvaluatorSelector::ChooseVariable() {
1488 int64 element_size = 0;
1490 if (!
vars_[i]->Bound()) {
1491 element_size +=
vars_[i]->Size();
1494 elements_.resize(element_size);
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);
1506 std::sort(elements_.begin(), elements_.end(), comp_);
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);
1517 solver_->SaveAndSetValue(&first_,
static_cast<int64>(elements_.size()));
1521std::string StaticEvaluatorSelector::DebugString()
const {
1522 return DebugStringInternal(
"AssignVariablesOnStaticEvaluator");
1527class AssignOneVariableValue :
public Decision {
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_);
1543AssignOneVariableValue::AssignOneVariableValue(IntVar*
const v,
int64 val)
1544 : var_(v), value_(val) {}
1546std::string AssignOneVariableValue::DebugString()
const {
1547 return absl::StrFormat(
"[%s == %d] or [%s != %d]", var_->DebugString(),
1548 value_, var_->DebugString(), value_);
1551void AssignOneVariableValue::Apply(Solver*
const s) { var_->SetValue(value_); }
1553void AssignOneVariableValue::Refute(Solver*
const s) {
1554 var_->RemoveValue(value_);
1559 return RevAlloc(
new AssignOneVariableValue(
var, val));
1565class AssignOneVariableValueOrFail :
public Decision {
1568 ~AssignOneVariableValueOrFail()
override {}
1569 void Apply(Solver*
const s)
override;
1570 void Refute(Solver*
const s)
override;
1572 void Accept(DecisionVisitor*
const visitor)
const override {
1573 visitor->VisitSetVariableValue(var_, value_);
1581AssignOneVariableValueOrFail::AssignOneVariableValueOrFail(IntVar*
const v,
1583 : var_(v), value_(
value) {}
1585std::string AssignOneVariableValueOrFail::DebugString()
const {
1586 return absl::StrFormat(
"[%s == %d] or fail", var_->
DebugString(), value_);
1589void AssignOneVariableValueOrFail::Apply(Solver*
const s) {
1593void AssignOneVariableValueOrFail::Refute(Solver*
const s) { s->Fail(); }
1604class AssignOneVariableValueDoNothing :
public Decision {
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_);
1614 void Accept(DecisionVisitor*
const visitor)
const override {
1615 visitor->VisitSetVariableValue(var_, value_);
1633class SplitOneVariable :
public Decision {
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_);
1647 const bool start_with_lower_half_;
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) {}
1654std::string SplitOneVariable::DebugString()
const {
1655 if (start_with_lower_half_) {
1656 return absl::StrFormat(
"[%s <= %d]", var_->
DebugString(), value_);
1658 return absl::StrFormat(
"[%s >= %d]", var_->
DebugString(), value_);
1662void SplitOneVariable::Apply(Solver*
const s) {
1663 if (start_with_lower_half_) {
1666 var_->
SetMin(value_ + 1);
1670void SplitOneVariable::Refute(Solver*
const s) {
1671 if (start_with_lower_half_) {
1672 var_->
SetMin(value_ + 1);
1680 bool start_with_lower_half) {
1681 return RevAlloc(
new SplitOneVariable(
var, val, start_with_lower_half));
1696class AssignVariablesValues :
public Decision {
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]);
1710 virtual void Accept(ModelVisitor*
const visitor)
const {
1718 const std::vector<IntVar*>
vars_;
1719 const std::vector<int64> values_;
1722AssignVariablesValues::AssignVariablesValues(
const std::vector<IntVar*>& vars,
1723 const std::vector<int64>& values)
1724 :
vars_(vars), values_(values) {}
1726std::string AssignVariablesValues::DebugString()
const {
1728 for (
int i = 0; i <
vars_.size(); ++i) {
1729 absl::StrAppendFormat(&out,
"[%s == %d]",
vars_[i]->DebugString(),
1735void AssignVariablesValues::Apply(Solver*
const s) {
1736 for (
int i = 0; i <
vars_.size(); ++i) {
1737 vars_[i]->SetValue(values_[i]);
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);
1748 s->AddConstraint(s->MakeSumGreaterOrEqual(terms, 1));
1753 const std::vector<int64>& values) {
1754 CHECK_EQ(vars.size(), values.size());
1755 return RevAlloc(
new AssignVariablesValues(vars, values));
1769 BaseAssignVariables(BaseVariableAssignmentSelector*
const selector, Mode mode)
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,
1779 const std::string& value_selector_name, BaseAssignVariables::Mode mode);
1782 Solver*
const s,
const std::vector<IntVar*>& vars,
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);
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);
1823 LOG(
FATAL) <<
"Unknown int var strategy " << str;
1834 return SelectMinValue;
1836 return SelectMaxValue;
1838 return SelectRandomValue;
1840 return SelectCenterValue;
1842 return SelectSplitValue;
1844 return SelectSplitValue;
1846 LOG(
FATAL) <<
"Unknown int value strategy " << val_str;
1851 void Accept(ModelVisitor*
const visitor)
const override {
1860BaseAssignVariables::~BaseAssignVariables() {}
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];
1870 return s->RevAlloc(
new AssignOneVariableValue(
var,
value));
1872 return s->RevAlloc(
new SplitOneVariable(
var,
value,
true));
1874 return s->RevAlloc(
new SplitOneVariable(
var,
value,
false));
1880std::string BaseAssignVariables::DebugString()
const {
1884BaseAssignVariables* BaseAssignVariables::MakePhase(
1885 Solver*
const s,
const std::vector<IntVar*>& vars,
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));
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";
1925 LOG(
FATAL) <<
"Unknown int var strategy " << var_str;
1935 return "SelectMinValue";
1937 return "SelectMaxValue";
1939 return "SelectRandomValue";
1941 return "SelectCenterValue";
1943 return "SelectSplitValue";
1945 return "SelectSplitValue";
1947 LOG(
FATAL) <<
"Unknown int value strategy " << val_str;
1954 return ChooseVariableName(var_str) +
"_" + SelectValueName(val_str);
1961 std::vector<IntVar*> vars(1);
1963 return MakePhase(vars, var_str, val_str);
1969 std::vector<IntVar*> vars(2);
1972 return MakePhase(vars, var_str, val_str);
1979 std::vector<IntVar*> vars(3);
1983 return MakePhase(vars, var_str, val_str);
1990 std::vector<IntVar*> vars(4);
1995 return MakePhase(vars, var_str, val_str);
1999 BaseAssignVariables::Mode mode = BaseAssignVariables::ASSIGN;
2001 mode = BaseAssignVariables::SPLIT_LOWER;
2003 mode = BaseAssignVariables::SPLIT_UPPER;
2012 BaseAssignVariables::MakeVariableSelector(
this, vars, var_str);
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));
2023 CHECK(var_evaluator !=
nullptr);
2024 CheapestVarSelector*
const var_selector =
2025 RevAlloc(
new CheapestVarSelector(std::move(var_evaluator)));
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);
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));
2042 BaseAssignVariables::MakeVariableSelector(
this, vars, var_str);
2043 CheapestValueSelector*
const value_selector =
2044 RevAlloc(
new CheapestValueSelector(std::move(value_evaluator),
nullptr));
2047 return value_selector->Select(
var,
id);
2049 const std::string
name = ChooseVariableName(var_str) +
"_SelectCheapestValue";
2050 return BaseAssignVariables::MakePhase(
this, vars, choose_variable,
2052 BaseAssignVariables::ASSIGN);
2059 BaseAssignVariables::MakeVariableSelector(
this, vars, var_str);
2060 BestValueByComparisonSelector*
const value_selector =
RevAlloc(
2061 new BestValueByComparisonSelector(std::move(var_val1_val2_comparator)));
2064 return value_selector->Select(
var,
id);
2066 return BaseAssignVariables::MakePhase(
this, vars, choose_variable,
2067 select_value,
"CheapestValue",
2068 BaseAssignVariables::ASSIGN);
2074 CheapestVarSelector*
const var_selector =
2075 RevAlloc(
new CheapestVarSelector(std::move(var_evaluator)));
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);
2081 CheapestValueSelector* value_selector =
2082 RevAlloc(
new CheapestValueSelector(std::move(value_evaluator),
nullptr));
2085 return value_selector->Select(
var,
id);
2087 return BaseAssignVariables::MakePhase(
this, vars, choose_variable,
2088 select_value,
"CheapestValue",
2089 BaseAssignVariables::ASSIGN);
2097 BaseAssignVariables::MakeVariableSelector(
this, vars, var_str);
2098 CheapestValueSelector* value_selector =
RevAlloc(
new CheapestValueSelector(
2099 std::move(value_evaluator), std::move(tie_breaker)));
2102 return value_selector->Select(
var,
id);
2104 return BaseAssignVariables::MakePhase(
this, vars, choose_variable,
2105 select_value,
"CheapestValue",
2106 BaseAssignVariables::ASSIGN);
2113 CheapestVarSelector*
const var_selector =
2114 RevAlloc(
new CheapestVarSelector(std::move(var_evaluator)));
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);
2120 CheapestValueSelector* value_selector =
RevAlloc(
new CheapestValueSelector(
2121 std::move(value_evaluator), std::move(tie_breaker)));
2124 return value_selector->Select(
var,
id);
2126 return BaseAssignVariables::MakePhase(
this, vars, choose_variable,
2127 select_value,
"CheapestValue",
2128 BaseAssignVariables::ASSIGN);
2134 return MakePhase(vars, std::move(eval),
nullptr, str);
2141 BaseVariableAssignmentSelector* selector =
nullptr;
2145 selector =
RevAlloc(
new StaticEvaluatorSelector(
this, vars, eval));
2149 selector =
RevAlloc(
new DynamicEvaluatorSelector(
this, vars, eval,
2150 std::move(tie_breaker)));
2155 new BaseAssignVariables(selector, BaseAssignVariables::ASSIGN));
2163 AssignVariablesFromAssignment(
const Assignment*
const assignment,
2165 const std::vector<IntVar*>& vars)
2166 : assignment_(assignment), db_(db),
vars_(vars), iter_(0) {}
2168 ~AssignVariablesFromAssignment()
override {}
2170 Decision* Next(Solver*
const s)
override {
2171 if (iter_ <
vars_.size()) {
2172 IntVar*
const var =
vars_[iter_++];
2174 new AssignOneVariableValue(
var, assignment_->Value(
var)));
2176 return db_->Next(s);
2180 void Accept(ModelVisitor*
const visitor)
const override {
2188 const Assignment*
const assignment_;
2189 DecisionBuilder*
const db_;
2190 const std::vector<IntVar*>
vars_;
2197 const std::vector<IntVar*>& vars) {
2198 return RevAlloc(
new AssignVariablesFromAssignment(assignment, db, vars));
2208 prototype_(assignment == nullptr ? nullptr : new
Assignment(assignment)) {
2216 delete data.solution;
2258 if (
prototype_ !=
nullptr && objective !=
nullptr) {
2265 delete data.solution;
2316 CHECK_GE(n, 0) <<
"wrong index in solution getter";
2389 explicit FirstSolutionCollector(
Solver*
const s);
2390 ~FirstSolutionCollector()
override;
2391 void EnterSearch()
override;
2392 bool AtSolution()
override;
2393 std::string DebugString()
const override;
2399FirstSolutionCollector::FirstSolutionCollector(Solver*
const s,
2400 const Assignment*
const a)
2401 : SolutionCollector(s,
a), done_(false) {}
2403FirstSolutionCollector::FirstSolutionCollector(Solver*
const s)
2404 : SolutionCollector(s), done_(false) {}
2406FirstSolutionCollector::~FirstSolutionCollector() {}
2408void FirstSolutionCollector::EnterSearch() {
2413bool FirstSolutionCollector::AtSolution() {
2421std::string FirstSolutionCollector::DebugString()
const {
2422 if (prototype_ ==
nullptr) {
2423 return "FirstSolutionCollector()";
2425 return "FirstSolutionCollector(" + prototype_->DebugString() +
")";
2432 return RevAlloc(
new FirstSolutionCollector(
this, assignment));
2436 return RevAlloc(
new FirstSolutionCollector(
this));
2446 explicit LastSolutionCollector(
Solver*
const s);
2447 ~LastSolutionCollector()
override;
2448 bool AtSolution()
override;
2449 std::string DebugString()
const override;
2452LastSolutionCollector::LastSolutionCollector(Solver*
const s,
2453 const Assignment*
const a)
2454 : SolutionCollector(s,
a) {}
2456LastSolutionCollector::LastSolutionCollector(Solver*
const s)
2457 : SolutionCollector(s) {}
2459LastSolutionCollector::~LastSolutionCollector() {}
2461bool LastSolutionCollector::AtSolution() {
2467std::string LastSolutionCollector::DebugString()
const {
2468 if (prototype_ ==
nullptr) {
2469 return "LastSolutionCollector()";
2471 return "LastSolutionCollector(" + prototype_->DebugString() +
")";
2478 return RevAlloc(
new LastSolutionCollector(
this, assignment));
2482 return RevAlloc(
new LastSolutionCollector(
this));
2492 BestValueSolutionCollector(
Solver*
const s,
bool maximize);
2493 ~BestValueSolutionCollector()
override {}
2494 void EnterSearch()
override;
2495 bool AtSolution()
override;
2496 std::string DebugString()
const override;
2503BestValueSolutionCollector::BestValueSolutionCollector(
2504 Solver*
const s,
const Assignment*
const a,
bool maximize)
2505 : SolutionCollector(s,
a),
2509BestValueSolutionCollector::BestValueSolutionCollector(Solver*
const s,
2511 : SolutionCollector(s),
2515void BestValueSolutionCollector::EnterSearch() {
2516 SolutionCollector::EnterSearch();
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_)) {
2527 best_ = objective->Max();
2529 (solution_count() == 0 || objective->Min() <
best_)) {
2532 best_ = objective->Min();
2539std::string BestValueSolutionCollector::DebugString()
const {
2540 if (prototype_ ==
nullptr) {
2541 return "BestValueSolutionCollector()";
2543 return "BestValueSolutionCollector(" + prototype_->DebugString() +
")";
2549 const Assignment*
const assignment,
bool maximize) {
2550 return RevAlloc(
new BestValueSolutionCollector(
this, assignment, maximize));
2554 return RevAlloc(
new BestValueSolutionCollector(
this, maximize));
2562 NBestValueSolutionCollector(
Solver*
const solver,
2564 int solution_count,
bool maximize);
2565 NBestValueSolutionCollector(
Solver*
const solver,
int solution_count,
2567 ~NBestValueSolutionCollector()
override { Clear(); }
2581NBestValueSolutionCollector::NBestValueSolutionCollector(
2582 Solver*
const solver,
const Assignment*
const assignment,
2583 int solution_count,
bool maximize)
2584 : SolutionCollector(solver, assignment),
2588NBestValueSolutionCollector::NBestValueSolutionCollector(Solver*
const solver,
2591 : SolutionCollector(solver),
2595void NBestValueSolutionCollector::EnterSearch() {
2596 SolutionCollector::EnterSearch();
2600 solver()->SetUseFastLocalSearch(
false);
2605void NBestValueSolutionCollector::ExitSearch() {
2612bool NBestValueSolutionCollector::AtSolution() {
2613 if (prototype_ !=
nullptr) {
2614 const IntVar* objective = prototype_->Objective();
2615 if (objective !=
nullptr) {
2616 const int64 objective_value =
2620 {objective_value, BuildSolutionDataForCurrentState()});
2623 if (top.first > objective_value) {
2627 {objective_value, BuildSolutionDataForCurrentState()});
2635std::string NBestValueSolutionCollector::DebugString()
const {
2636 if (prototype_ ==
nullptr) {
2637 return "NBestValueSolutionCollector()";
2639 return "NBestValueSolutionCollector(" + prototype_->DebugString() +
")";
2643void NBestValueSolutionCollector::Clear() {
2653 const Assignment*
const assignment,
int solution_count,
bool maximize) {
2654 if (solution_count == 1) {
2655 return MakeBestValueSolutionCollector(assignment, maximize);
2657 return RevAlloc(
new NBestValueSolutionCollector(
this, assignment,
2658 solution_count, maximize));
2663 if (solution_count == 1) {
2664 return MakeBestValueSolutionCollector(maximize);
2667 new NBestValueSolutionCollector(
this, solution_count, maximize));
2677 explicit AllSolutionCollector(
Solver*
const s);
2678 ~AllSolutionCollector()
override;
2683AllSolutionCollector::AllSolutionCollector(Solver*
const s,
2684 const Assignment*
const a)
2685 : SolutionCollector(s,
a) {}
2687AllSolutionCollector::AllSolutionCollector(Solver*
const s)
2688 : SolutionCollector(s) {}
2690AllSolutionCollector::~AllSolutionCollector() {}
2692bool AllSolutionCollector::AtSolution() {
2697std::string AllSolutionCollector::DebugString()
const {
2698 if (prototype_ ==
nullptr) {
2699 return "AllSolutionCollector()";
2701 return "AllSolutionCollector(" + prototype_->DebugString() +
")";
2708 return RevAlloc(
new AllSolutionCollector(
this, assignment));
2712 return RevAlloc(
new AllSolutionCollector(
this));
2724 found_initial_solution_(false) {
2748 if (
solver()->SearchDepth() == 0) {
2791 if (
delta !=
nullptr) {
2792 const bool delta_has_objective =
delta->HasObjective();
2793 if (!delta_has_objective) {
2800 const int64 delta_min_objective =
2802 const int64 min_objective =
2806 delta->SetObjectiveMin(
2810 const int64 delta_max_objective =
2812 const int64 max_objective =
2816 delta->SetObjectiveMax(
2825 return absl::StrFormat(
"objective value = %d, ",
var_->
Value());
2831 out =
"MaximizeVar(";
2833 out =
"MinimizeVar(";
2835 absl::StrAppendFormat(&out,
"%s, step = %d, best = %d)",
var_->
DebugString(),
2864 WeightedOptimizeVar(
Solver* solver,
bool maximize,
2865 const std::vector<IntVar*>& sub_objectives,
2866 const std::vector<int64>& weights,
int64 step)
2868 solver->MakeScalProd(sub_objectives, weights)->Var(), step),
2869 sub_objectives_(sub_objectives),
2871 CHECK_EQ(sub_objectives.size(), weights.size());
2874 ~WeightedOptimizeVar()
override {}
2875 std::string Print()
const override;
2878 const std::vector<IntVar*> sub_objectives_;
2879 const std::vector<int64> weights_;
2884std::string WeightedOptimizeVar::Print()
const {
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]);
2897 bool maximize,
const std::vector<IntVar*>& sub_objectives,
2898 const std::vector<int64>& weights,
int64 step) {
2900 new WeightedOptimizeVar(
this, maximize, sub_objectives, weights, step));
2904 const std::vector<IntVar*>& sub_objectives,
2905 const std::vector<int64>& weights,
int64 step) {
2907 new WeightedOptimizeVar(
this,
false, sub_objectives, weights, step));
2911 const std::vector<IntVar*>& sub_objectives,
2912 const std::vector<int64>& weights,
int64 step) {
2914 new WeightedOptimizeVar(
this,
true, sub_objectives, weights, step));
2918 bool maximize,
const std::vector<IntVar*>& sub_objectives,
2919 const std::vector<int>& weights,
int64 step) {
2925 const std::vector<IntVar*>& sub_objectives,
const std::vector<int>& weights,
2931 const std::vector<IntVar*>& sub_objectives,
const std::vector<int>& weights,
2941 Metaheuristic(
Solver*
const solver,
bool maximize,
IntVar* objective,
2943 ~Metaheuristic()
override {}
2945 bool AtSolution()
override;
2946 void EnterSearch()
override;
2947 void RefuteDecision(Decision*
const d)
override;
2958Metaheuristic::Metaheuristic(Solver*
const solver,
bool maximize,
2959 IntVar* objective,
int64 step)
2960 : SearchMonitor(solver),
2967bool Metaheuristic::AtSolution() {
2977void Metaheuristic::EnterSearch() {
2980 solver()->SetUseFastLocalSearch(
false);
2990void Metaheuristic::RefuteDecision(Decision* d) {
3001 if (
delta !=
nullptr) {
3002 if (!
delta->HasObjective()) {
3007 delta->SetObjectiveMin(
3010 delta->SetObjectiveMax(
3020class TabuSearch :
public Metaheuristic {
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;
3031 std::string DebugString()
const override {
return "Tabu Search"; }
3041 typedef std::list<VarValue> TabuList;
3043 virtual std::vector<IntVar*> CreateTabuVars();
3044 const TabuList& forbid_tabu_list() {
return forbid_tabu_list_; }
3047 void AgeList(
int64 tenure, TabuList* list);
3050 const std::vector<IntVar*>
vars_;
3051 Assignment assignment_;
3053 TabuList keep_tabu_list_;
3055 TabuList forbid_tabu_list_;
3056 int64 forbid_tenure_;
3057 double tabu_factor_;
3059 bool found_initial_solution_;
3064TabuSearch::TabuSearch(Solver*
const s,
bool maximize, IntVar* objective,
3065 int64 step,
const std::vector<IntVar*>& vars,
3068 : Metaheuristic(s, maximize, objective, step),
3072 keep_tenure_(keep_tenure),
3073 forbid_tenure_(forbid_tenure),
3074 tabu_factor_(tabu_factor),
3076 found_initial_solution_(false) {
3077 assignment_.Add(
vars_);
3080void TabuSearch::EnterSearch() {
3081 Metaheuristic::EnterSearch();
3082 found_initial_solution_ =
false;
3085void TabuSearch::ApplyDecision(Decision*
const d) {
3086 Solver*
const s = solver();
3087 if (d == s->balancing_decision()) {
3092 IntVar* aspiration = s->MakeBoolVar();
3094 s->AddConstraint(s->MakeIsGreaterOrEqualCstCt(
3101 IntVar* tabu_var =
nullptr;
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_);
3112 if (tabu_var !=
nullptr) {
3114 s->MakeGreaterOrEqual(s->MakeSum(aspiration, tabu_var),
int64{1}));
3127 if (found_initial_solution_) {
3128 s->AddConstraint(s->MakeNonEquality(
objective_, last_));
3132std::vector<IntVar*> TabuSearch::CreateTabuVars() {
3133 Solver*
const s = solver();
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_));
3145 for (
const VarValue& vv : forbid_tabu_list_) {
3146 tabu_vars.push_back(s->MakeIsDifferentCstVar(vv.var_, vv.value_));
3151bool TabuSearch::AtSolution() {
3152 if (!Metaheuristic::AtSolution()) {
3155 found_initial_solution_ =
true;
3161 for (
int i = 0; i <
vars_.size(); ++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);
3170 if (forbid_tenure_ > 0) {
3171 VarValue forbid_value(
var, old_value,
stamp_);
3172 forbid_tabu_list_.push_front(forbid_value);
3177 assignment_.Store();
3182bool TabuSearch::LocalOptimum() {
3189 return found_initial_solution_;
3198void TabuSearch::AgeList(
int64 tenure, TabuList* list) {
3199 while (!list->empty() && list->back().stamp_ <
stamp_ - tenure) {
3204void TabuSearch::AgeLists() {
3205 AgeList(keep_tenure_, &keep_tabu_list_);
3206 AgeList(forbid_tenure_, &forbid_tabu_list_);
3210class GenericTabuSearch :
public TabuSearch {
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"; }
3219 std::vector<IntVar*> CreateTabuVars()
override;
3222std::vector<IntVar*> GenericTabuSearch::CreateTabuVars() {
3223 Solver*
const s = solver();
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_));
3231 std::vector<IntVar*> tabu_vars;
3232 if (!forbid_values.empty()) {
3233 tabu_vars.push_back(s->MakeIsGreaterCstVar(s->MakeSum(forbid_values), 0));
3242 const std::vector<IntVar*>& vars,
3244 double tabu_factor) {
3245 return RevAlloc(
new TabuSearch(
this, maximize, v, step, vars, keep_tenure,
3246 forbid_tenure, tabu_factor));
3251 const std::vector<IntVar*>& tabu_vars,
int64 forbid_tenure) {
3253 new GenericTabuSearch(
this, maximize, v, step, tabu_vars, forbid_tenure));
3259class SimulatedAnnealing :
public Metaheuristic {
3261 SimulatedAnnealing(
Solver*
const s,
bool maximize,
IntVar* objective,
3263 ~SimulatedAnnealing()
override {}
3264 void EnterSearch()
override;
3265 void ApplyDecision(Decision* d)
override;
3266 bool AtSolution()
override;
3267 bool LocalOptimum()
override;
3269 std::string DebugString()
const override {
return "Simulated Annealing"; }
3272 double Temperature()
const;
3274 const int64 temperature0_;
3277 bool found_initial_solution_;
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),
3289 found_initial_solution_(false) {}
3291void SimulatedAnnealing::EnterSearch() {
3292 Metaheuristic::EnterSearch();
3293 found_initial_solution_ =
false;
3296void SimulatedAnnealing::ApplyDecision(Decision*
const d) {
3297 Solver*
const s = solver();
3298 if (d == s->balancing_decision()) {
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);
3305 const double rand_log2_double = log2(rand_double);
3307 const int64 energy_bound = Temperature() * rand_log2_double;
3319bool SimulatedAnnealing::AtSolution() {
3320 if (!Metaheuristic::AtSolution()) {
3323 found_initial_solution_ =
true;
3327bool SimulatedAnnealing::LocalOptimum() {
3334 return found_initial_solution_ && Temperature() > 0;
3338 if (iteration_ > 0) {
3343double SimulatedAnnealing::Temperature()
const {
3344 if (iteration_ > 0) {
3345 return (1.0 * temperature0_) / iteration_;
3354 int64 initial_temperature) {
3356 new SimulatedAnnealing(
this, maximize, v, step, initial_temperature));
3361typedef std::pair<int64, int64>
Arc;
3366class GuidedLocalSearchPenalties {
3368 virtual ~GuidedLocalSearchPenalties() {}
3369 virtual bool HasValues()
const = 0;
3370 virtual void Increment(
const Arc& arc) = 0;
3372 virtual void Reset() = 0;
3376class GuidedLocalSearchPenaltiesTable :
public GuidedLocalSearchPenalties {
3378 explicit GuidedLocalSearchPenaltiesTable(
int size);
3379 ~GuidedLocalSearchPenaltiesTable()
override {}
3380 bool HasValues()
const override {
return has_values_; }
3381 void Increment(
const Arc& arc)
override;
3383 void Reset()
override;
3386 std::vector<std::vector<int64>> penalties_;
3390GuidedLocalSearchPenaltiesTable::GuidedLocalSearchPenaltiesTable(
int size)
3391 : penalties_(size), has_values_(
false) {}
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);
3399 ++first_penalties[second];
3403void GuidedLocalSearchPenaltiesTable::Reset() {
3404 has_values_ =
false;
3405 for (
int i = 0; i < penalties_.size(); ++i) {
3406 penalties_[i].clear();
3411 const std::vector<int64>& first_penalties = penalties_[arc.first];
3412 const int64 second = arc.second;
3413 if (second >= first_penalties.size()) {
3416 return first_penalties[second];
3421class GuidedLocalSearchPenaltiesMap :
public GuidedLocalSearchPenalties {
3423 explicit GuidedLocalSearchPenaltiesMap(
int size);
3424 ~GuidedLocalSearchPenaltiesMap()
override {}
3425 bool HasValues()
const override {
return (!penalties_.empty()); }
3426 void Increment(
const Arc& arc)
override;
3428 void Reset()
override;
3432 absl::flat_hash_map<Arc, int64> penalties_;
3435GuidedLocalSearchPenaltiesMap::GuidedLocalSearchPenaltiesMap(
int size)
3436 : penalized_(size,
false) {}
3438void GuidedLocalSearchPenaltiesMap::Increment(
const Arc& arc) {
3440 penalized_.
Set(arc.first,
true);
3443void GuidedLocalSearchPenaltiesMap::Reset() {
3449 if (penalized_.
Get(arc.first)) {
3455class GuidedLocalSearch :
public Metaheuristic {
3457 GuidedLocalSearch(
Solver*
const s,
IntVar* objective,
bool maximize,
3458 int64 step,
const std::vector<IntVar*>& vars,
3459 double penalty_factor);
3460 ~GuidedLocalSearch()
override {}
3462 void ApplyDecision(
Decision* d)
override;
3463 bool AtSolution()
override;
3464 void EnterSearch()
override;
3465 bool LocalOptimum()
override;
3472 int64* penalty) = 0;
3474 std::string DebugString()
const override {
return "Guided Local Search"; }
3478 bool operator()(
const std::pair<Arc, double>& i,
3479 const std::pair<Arc, double>& j) {
3480 return i.second > j.second;
3485 const int64*
const out_values,
bool cache_delta_values);
3488 Assignment assignment_;
3491 const std::vector<IntVar*>
vars_;
3494 std::unique_ptr<GuidedLocalSearchPenalties> penalties_;
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),
3512 if (!vars.empty()) {
3514 assignment_.Add(
vars_);
3520 for (
int i = 0; i <
vars_.size(); ++i) {
3523 if (absl::GetFlag(FLAGS_cp_use_sparse_gls_penalties)) {
3524 penalties_ = absl::make_unique<GuidedLocalSearchPenaltiesMap>(
vars_.size());
3527 absl::make_unique<GuidedLocalSearchPenaltiesTable>(
vars_.size());
3538void GuidedLocalSearch::ApplyDecision(Decision*
const d) {
3539 if (d == solver()->balancing_decision()) {
3543 if (penalties_->HasValues()) {
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);
3561 IntExpr* min_pen_exp =
3563 IntVar* min_exp = solver()->MakeMin(min_pen_exp,
best_ +
step_)->Var();
3564 solver()->AddConstraint(
3565 solver()->MakeGreaterOrEqual(
objective_, min_exp));
3567 IntExpr* max_pen_exp =
3569 IntVar* max_exp = solver()->MakeMax(max_pen_exp,
best_ -
step_)->Var();
3570 solver()->AddConstraint(solver()->MakeLessOrEqual(
objective_, max_exp));
3584bool GuidedLocalSearch::AtSolution() {
3585 if (!Metaheuristic::AtSolution()) {
3591 assignment_.Store();
3595void GuidedLocalSearch::EnterSearch() {
3596 Metaheuristic::EnterSearch();
3602 penalties_->Reset();
3608 if (
delta !=
nullptr || deltadelta !=
nullptr) {
3609 if (!penalties_->HasValues()) {
3613 if (!deltadelta->Empty()) {
3624 for (
int i = 0; i <
vars_.size(); ++i) {
3634 if (!
delta->HasObjective()) {
3639 delta->SetObjectiveMin(
3642 delta->ObjectiveMin()));
3644 delta->SetObjectiveMax(
3647 delta->ObjectiveMax()));
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();
3667 int64 new_penalty = 0;
3668 if (EvaluateElementValue(container,
index, &i, &new_penalty)) {
3669 penalty =
CapAdd(penalty, new_penalty);
3670 if (cache_delta_values) {
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])) {
3688 const int64 var_value = assignment_.Value(
vars_[i]);
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));
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;
3701 penalties_->Increment(utility[i].first);
3711class BinaryGuidedLocalSearch :
public GuidedLocalSearch {
3713 BinaryGuidedLocalSearch(Solver*
const solver, IntVar*
const objective,
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,
3724 bool EvaluateElementValue(
const Assignment::IntContainer& container,
3726 int64* penalty)
override;
3733BinaryGuidedLocalSearch::BinaryGuidedLocalSearch(
3734 Solver*
const solver, IntVar*
const objective,
3736 int64 step,
const std::vector<IntVar*>& vars,
double penalty_factor)
3737 : GuidedLocalSearch(solver, objective, maximize, step, vars,
3739 objective_function_(
std::move(objective_function)) {}
3741IntExpr* BinaryGuidedLocalSearch::MakeElementPenalty(
int index) {
3742 return solver()->MakeElement(
3747int64 BinaryGuidedLocalSearch::AssignmentElementPenalty(
3748 const Assignment& assignment,
int index) {
3752int64 BinaryGuidedLocalSearch::AssignmentPenalty(
const Assignment& assignment,
3754 return objective_function_(
index,
next);
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());
3770 const Arc arc(i, j);
3771 const int64 penalty = penalties_->Value(arc);
3773 const double penalized_value_fp =
3776 ?
static_cast<int64>(penalized_value_fp)
3779 return -penalized_value;
3781 return penalized_value;
3788class TernaryGuidedLocalSearch :
public GuidedLocalSearch {
3790 TernaryGuidedLocalSearch(
3791 Solver*
const solver, IntVar*
const objective,
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,
3801 bool EvaluateElementValue(
const Assignment::IntContainer& container,
3803 int64* penalty)
override;
3807 int64 GetAssignmentSecondaryValue(
const Assignment::IntContainer& container,
3808 int index,
int* container_index)
const;
3810 const std::vector<IntVar*> secondary_vars_;
3814TernaryGuidedLocalSearch::TernaryGuidedLocalSearch(
3815 Solver*
const solver, IntVar*
const objective,
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,
3821 secondary_vars_(secondary_vars),
3822 objective_function_(
std::move(objective_function)) {
3823 if (!secondary_vars.empty()) {
3824 assignment_.Add(secondary_vars);
3828IntExpr* TernaryGuidedLocalSearch::MakeElementPenalty(
int index) {
3829 return solver()->MakeElement(
3834int64 TernaryGuidedLocalSearch::AssignmentElementPenalty(
3835 const Assignment& assignment,
int index) {
3837 assignment.Value(secondary_vars_[
index]));
3840int64 TernaryGuidedLocalSearch::AssignmentPenalty(
const Assignment& assignment,
3843 assignment.Value(secondary_vars_[
index]));
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));
3861 const Arc arc(i, j);
3862 const int64 penalty = penalties_->Value(arc);
3864 const double penalized_value_fp =
3867 ?
static_cast<int64>(penalized_value_fp)
3870 return -penalized_value;
3872 return penalized_value;
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();
3889 return container.Element(secondary_var).Value();
3895 bool maximize,
IntVar*
const objective,
3897 const std::vector<IntVar*>& vars,
double penalty_factor) {
3898 return RevAlloc(
new BinaryGuidedLocalSearch(
3899 this, objective, std::move(objective_function), maximize, step, vars,
3904 bool maximize,
IntVar*
const objective,
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));
3917SearchLimit::~SearchLimit() {}
3919void SearchLimit::EnterSearch() {
3934void SearchLimit::PeriodicCheck() {
3935 if (crossed_ || Check()) {
3941void SearchLimit::TopPeriodicCheck() {
3942 if (solver()->TopLevelSearch() != solver()->ActiveSearch()) {
3943 solver()->TopPeriodicCheck();
3951 bool smart_time_check,
bool cumulative)
3953 duration_limit_(
time),
3954 solver_time_at_limit_start_(s->Now()),
3955 last_time_elapsed_(
absl::ZeroDuration()),
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) {}
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_;
3991 return s->
branches() - branches_offset_ >= branches_ ||
3992 s->
failures() - failures_offset_ >= failures_ || CheckTime() ||
3993 s->
solutions() - solutions_offset_ >= solutions_;
3998 int64 progress = GetPercent(s->
branches(), branches_offset_, branches_);
4000 GetPercent(s->
failures(), failures_offset_, failures_));
4002 progress, GetPercent(s->
solutions(), solutions_offset_, solutions_));
4013 solver_time_at_limit_start_ = s->
Now();
4014 last_time_elapsed_ = absl::ZeroDuration();
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_;
4033 duration_limit_ =
time;
4046 return absl::StrFormat(
4047 "RegularLimit(crossed = %i, duration_limit = %s, "
4048 "branches = %d, failures = %d, solutions = %d cumulative = %s",
4050 solutions_, (cumulative_ ?
"true" :
"false"));
4068bool RegularLimit::CheckTime() {
return TimeElapsed() >=
duration_limit(); }
4070absl::Duration RegularLimit::TimeElapsed() {
4071 const int64 kMaxSkip = 100;
4072 const int64 kCheckWarmupIterations = 100;
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()) {
4081 check_count_ * absl::FDivDuration(duration_limit_, elapsed));
4083 std::min(check_count_ + kMaxSkip, estimated_check_count_at_limit);
4085 last_time_elapsed_ = elapsed;
4087 return last_time_elapsed_;
4111 int64 solutions,
bool smart_time_check,
4114 smart_time_check, cumulative);
4119 bool smart_time_check,
bool cumulative) {
4121 smart_time_check, cumulative));
4126 : absl::Milliseconds(
proto.time()),
4128 proto.smart_time_check(),
proto.cumulative());
4132 RegularLimitParameters
proto;
4137 proto.set_smart_time_check(
false);
4138 proto.set_cumulative(
false);
4146 double objective_scaling_factor,
double objective_offset,
4147 double improvement_rate_coefficient,
4148 int improvement_rate_solutions_distance)
4150 objective_var_(objective_var),
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) {
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;
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_;
4190 objective_var_, maximize_, objective_scaling_factor_, objective_offset_,
4191 improvement_rate_coefficient_, improvement_rate_solutions_distance_);
4195 if (!objective_updated_) {
4198 objective_updated_ =
false;
4200 if (improvements_.size() <= improvement_rate_solutions_distance_) {
4204 const std::pair<double, int64> cur = improvements_.back();
4205 const std::pair<double, int64> prev = improvements_.front();
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_) {
4219 const int64 new_objective =
4220 objective_var_ !=
nullptr && objective_var_->
Bound()
4221 ? objective_var_->
Value()
4226 const double scaled_new_objective =
4227 objective_scaling_factor_ * (new_objective + objective_offset_);
4229 const bool is_improvement = maximize_
4230 ? scaled_new_objective > best_objective_
4231 : scaled_new_objective < best_objective_;
4233 if (gradient_stage_ && !is_improvement) {
4234 gradient_stage_ =
false;
4237 if (threshold_ == std::numeric_limits<double>::infinity()) {
4242 if (is_improvement) {
4243 best_objective_ = scaled_new_objective;
4244 objective_updated_ =
true;
4245 improvements_.push_back(
4250 if (improvements_.size() - 1 > improvement_rate_solutions_distance_) {
4251 improvements_.pop_front();
4253 DCHECK_LE(improvements_.size() - 1, improvement_rate_solutions_distance_);
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));
4273 :
SearchLimit(limit_1->solver()), limit_1_(limit_1), limit_2_(limit_2) {
4274 CHECK(limit_1 !=
nullptr);
4275 CHECK(limit_2 !=
nullptr);
4277 <<
"Illegal arguments: cannot combines limits that belong to different "
4278 <<
"solvers, because the reversible allocations could delete one and "
4279 <<
"not the other.";
4282 bool Check()
override {
4285 const bool check_1 = limit_1_->Check();
4286 const bool check_2 = limit_2_->Check();
4287 return check_1 || check_2;
4290 void Init()
override {
4295 void Copy(
const SearchLimit*
const limit)
override {
4299 SearchLimit* MakeClone()
const override {
4301 return solver()->MakeLimit(limit_1_->MakeClone(), limit_2_->MakeClone());
4304 void EnterSearch()
override {
4305 limit_1_->EnterSearch();
4306 limit_2_->EnterSearch();
4308 void BeginNextDecision(DecisionBuilder*
const b)
override {
4309 limit_1_->BeginNextDecision(
b);
4310 limit_2_->BeginNextDecision(
b);
4312 void PeriodicCheck()
override {
4313 limit_1_->PeriodicCheck();
4314 limit_2_->PeriodicCheck();
4316 void RefuteDecision(Decision*
const d)
override {
4317 limit_1_->RefuteDecision(d);
4318 limit_2_->RefuteDecision(d);
4320 std::string DebugString()
const override {
4321 return absl::StrCat(
"OR limit (", limit_1_->DebugString(),
" OR ",
4322 limit_2_->DebugString(),
")");
4326 SearchLimit*
const limit_1_;
4327 SearchLimit*
const limit_2_;
4333 return RevAlloc(
new ORLimit(limit_1, limit_2));
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;
4346 std::function<bool()> limiter_;
4349CustomLimit::CustomLimit(Solver*
const s, std::function<
bool()> limiter)
4350 : SearchLimit(s), limiter_(
std::move(limiter)) {}
4352bool CustomLimit::Check() {
4353 if (limiter_)
return limiter_();
4357void CustomLimit::Init() {}
4359void CustomLimit::Copy(
const SearchLimit*
const limit) {
4360 const CustomLimit*
const custom =
4361 reinterpret_cast<const CustomLimit* const
>(limit);
4362 limiter_ = custom->limiter_;
4365SearchLimit* CustomLimit::MakeClone()
const {
4366 return solver()->RevAlloc(
new CustomLimit(solver(), limiter_));
4371 return RevAlloc(
new CustomLimit(
this, std::move(limiter)));
4380 CHECK(db !=
nullptr);
4383 SolveOnce(DecisionBuilder*
const db,
4384 const std::vector<SearchMonitor*>& monitors)
4385 : db_(db), monitors_(monitors) {
4386 CHECK(db !=
nullptr);
4389 ~SolveOnce()
override {}
4391 Decision* Next(Solver* s)
override {
4392 bool res = s->SolveAndCommit(db_, monitors_);
4399 std::string DebugString()
const override {
4400 return absl::StrFormat(
"SolveOnce(%s)", db_->DebugString());
4403 void Accept(ModelVisitor*
const visitor)
const override {
4404 db_->Accept(visitor);
4408 DecisionBuilder*
const db_;
4409 std::vector<SearchMonitor*> monitors_;
4414 return RevAlloc(
new SolveOnce(db));
4419 std::vector<SearchMonitor*> monitors;
4420 monitors.push_back(monitor1);
4421 return RevAlloc(
new SolveOnce(db, monitors));
4427 std::vector<SearchMonitor*> monitors;
4428 monitors.push_back(monitor1);
4429 monitors.push_back(monitor2);
4430 return RevAlloc(
new SolveOnce(db, monitors));
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));
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));
4458 DecisionBuilder*
const db,
const std::vector<SearchMonitor*>& monitors) {
4459 return RevAlloc(
new SolveOnce(db, monitors));
4468 bool maximize,
int64 step)
4470 solution_(solution),
4473 collector_(nullptr) {
4474 CHECK(db !=
nullptr);
4475 CHECK(solution !=
nullptr);
4480 NestedOptimize(DecisionBuilder*
const db, Assignment*
const solution,
4481 bool maximize,
int64 step,
4482 const std::vector<SearchMonitor*>& monitors)
4484 solution_(solution),
4487 monitors_(monitors),
4488 collector_(nullptr) {
4489 CHECK(db !=
nullptr);
4490 CHECK(solution !=
nullptr);
4491 CHECK(solution->HasObjective());
4495 void AddMonitors() {
4496 Solver*
const solver = solution_->solver();
4497 collector_ = solver->MakeLastSolutionCollector(solution_);
4498 monitors_.push_back(collector_);
4499 OptimizeVar*
const optimize =
4501 monitors_.push_back(optimize);
4504 Decision* Next(Solver* solver)
override {
4505 solver->Solve(db_, monitors_);
4506 if (collector_->solution_count() == 0) {
4509 collector_->solution(0)->Restore();
4513 std::string DebugString()
const override {
4514 return absl::StrFormat(
"NestedOptimize(db = %s, maximize = %d, step = %d)",
4518 void Accept(ModelVisitor*
const visitor)
const override {
4519 db_->Accept(visitor);
4523 DecisionBuilder*
const db_;
4524 Assignment*
const solution_;
4527 std::vector<SearchMonitor*> monitors_;
4528 SolutionCollector* collector_;
4534 bool maximize,
int64 step) {
4535 return RevAlloc(
new NestedOptimize(db, solution, maximize, step));
4540 bool maximize,
int64 step,
4542 std::vector<SearchMonitor*> monitors;
4543 monitors.push_back(monitor1);
4544 return RevAlloc(
new NestedOptimize(db, solution, maximize, step, monitors));
4549 bool maximize,
int64 step,
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));
4560 bool maximize,
int64 step,
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));
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));
4585 int64 step,
const std::vector<SearchMonitor*>& monitors) {
4586 return RevAlloc(
new NestedOptimize(db, solution, maximize, step, monitors));
4593int64 NextLuby(
int i) {
4601 while (power < (i + 1)) {
4604 if (power == i + 1) {
4607 return NextLuby(i - (power / 2) + 1);
4610class LubyRestart :
public SearchMonitor {
4612 LubyRestart(Solver*
const s,
int scale_factor)
4614 scale_factor_(scale_factor),
4617 next_step_(scale_factor) {
4621 ~LubyRestart()
override {}
4623 void BeginFail()
override {
4624 if (++current_fails_ >= next_step_) {
4626 next_step_ = NextLuby(++iteration_) * scale_factor_;
4627 solver()->RestartCurrentSearch();
4631 std::string DebugString()
const override {
4632 return absl::StrFormat(
"LubyRestart(%i)", scale_factor_);
4636 const int scale_factor_;
4638 int64 current_fails_;
4644 return RevAlloc(
new LubyRestart(
this, scale_factor));
4652 ConstantRestart(
Solver*
const s,
int frequency)
4653 :
SearchMonitor(s), frequency_(frequency), current_fails_(0) {
4657 ~ConstantRestart()
override {}
4659 void BeginFail()
override {
4660 if (++current_fails_ >= frequency_) {
4662 solver()->RestartCurrentSearch();
4666 std::string DebugString()
const override {
4667 return absl::StrFormat(
"ConstantRestart(%i)", frequency_);
4671 const int frequency_;
4672 int64 current_fails_;
4677 return RevAlloc(
new ConstantRestart(
this, frequency));
4700 const std::vector<SymmetryBreaker*>& visitors)
4702 visitors_(visitors),
4703 clauses_(visitors.size()),
4704 decisions_(visitors.size()),
4705 directions_(visitors.size()) {
4706 for (
int i = 0; i < visitors_.size(); ++i) {
4707 visitors_[i]->set_symmetry_manager_and_index(
this, i);
4715 for (
int i = 0; i < visitors_.size(); ++i) {
4716 const void*
const last = clauses_[i].Last();
4718 if (last != clauses_[i].Last()) {
4720 decisions_[i].Push(
solver(), d);
4721 directions_[i].Push(
solver(),
false);
4728 for (
int i = 0; i < visitors_.size(); ++i) {
4729 if (decisions_[i].Last() !=
nullptr && decisions_[i].LastValue() == d) {
4742 std::vector<IntVar*> guard;
4747 IntVar*
const term = *tmp;
4749 if (term->
Max() == 0) {
4753 if (term->
Min() == 0) {
4756 guard.push_back(term);
4762 guard.push_back(clauses_[
index].LastValue());
4763 directions_[
index].SetLastValue(
true);
4775 clauses_[visitor->index_in_symmetry_manager()].Push(
solver(), term);
4778 std::string
DebugString()
const override {
return "SymmetryManager"; }
4781 const std::vector<SymmetryBreaker*> visitors_;
4782 std::vector<SimpleRevFIFO<IntVar*>> clauses_;
4783 std::vector<SimpleRevFIFO<Decision*>> decisions_;
4784 std::vector<SimpleRevFIFO<bool>> directions_;
4816 const std::vector<SymmetryBreaker*>& visitors) {
4821 std::vector<SymmetryBreaker*> visitors;
4822 visitors.push_back(v1);
4828 std::vector<SymmetryBreaker*> visitors;
4829 visitors.push_back(v1);
4830 visitors.push_back(v2);
4837 std::vector<SymmetryBreaker*> visitors;
4838 visitors.push_back(v1);
4839 visitors.push_back(v2);
4840 visitors.push_back(v3);
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);
#define DCHECK_LE(val1, val2)
#define CHECK_LT(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define CHECK_LE(val1, val2)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
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 ObjectiveMin() const
int64 StartValue(const IntervalVar *const var) const
const std::vector< int > & ForwardSequence(const SequenceVar *const var) const
bool HasObjective() const
int64 ObjectiveValue() const
int64 DurationValue(const IntervalVar *const var) const
int64 ObjectiveMax() 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
void Set(uint32 index, bool value)
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.
void Init() override
This method is called when the search limit is initialized.
~ImprovementSearchLimit() override
void Copy(const SearchLimit *const limit) override
Copy a limit.
bool AtSolution() override
This method is called when a valid solution is found.
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)
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
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)
static const char kSolutionLimitArgument[]
static const char kObjectiveExtension[]
static const char kMaximizeArgument[]
static const char kTimeLimitArgument[]
static const char kBranchesLimitArgument[]
static const char kSmartTimeCheckArgument[]
virtual void BeginVisitExtension(const std::string &type)
virtual void EndVisitExtension(const std::string &type)
static const char kCumulativeArgument[]
static const char kStepArgument[]
virtual void VisitIntegerArgument(const std::string &arg_name, int64 value)
Visit integer arguments.
static const char kVarsArgument[]
static const char kVariableGroupExtension[]
static const char kExpressionArgument[]
static const char kFailuresLimitArgument[]
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *const argument)
Visit integer expression argument.
static const char kSearchLimitExtension[]
This class encapsulates an objective.
void EnterSearch() override
Beginning of the search.
void BeginNextDecision(DecisionBuilder *const db) override
Before calling DecisionBuilder::Next.
bool found_initial_solution_
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
bool AcceptSolution() override
This method is called when a solution is found.
virtual std::string Print() const
bool AtSolution() override
This method is called when a valid solution is found.
void RefuteDecision(Decision *const d) override
Before refuting the decision.
IntVar * Var() const
Returns the variable that is optimized.
OptimizeVar(Solver *const s, bool maximize, IntVar *const a, int64 step)
bool AcceptDelta(Assignment *delta, Assignment *deltadelta) override
Internal methods.
std::string DebugString() const override
std::string DebugString() const override
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.
absl::Duration duration_limit() const
bool IsUncheckedSolutionLimitReached() override
Returns true if the limit of solutions has been reached including unchecked solutions.
void Init() override
This method is called when the search limit is initialized.
void ExitSearch() override
End of the search.
int ProgressPercent() override
Returns a percentage representing the propress of the search before reaching limits.
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
void Copy(const SearchLimit *const limit) override
Copy a limit.
void UpdateLimits(absl::Duration time, int64 branches, int64 failures, int64 solutions)
RegularLimit * MakeIdenticalClone() const
std::string DebugString() const override
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
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.
virtual void OutputLine(const std::string &line)
void EnterSearch() override
Beginning of the search.
void RefuteDecision(Decision *const decision) override
Before refuting the decision.
void ExitSearch() override
End of the search.
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)
void BeginInitialPropagation() override
Before the initial propagation.
void NoMoreSolutions() override
When the search tree is finished.
void ApplyDecision(Decision *const decision) override
Before applying the decision.
bool AtSolution() override
This method is called when a valid solution is found.
std::string DebugString() const override
void AcceptUncheckedNeighbor() override
After accepting an unchecked neighbor during local search.
void EndInitialPropagation() override
After the initial propagation.
A search monitor is a simple set of callbacks to monitor all search events.
virtual void ExitSearch()
End of the search.
static constexpr int kNoProgress
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 check_index(int n) const
void EnterSearch() override
Beginning of the search.
int64 Value(int n, IntVar *const var) const
This is a shortcut to get the Value of 'var' in the nth solution.
int64 failures(int n) const
Returns the number of failures encountered at the time of the nth solution.
~SolutionCollector() override
void Push(const SolutionData &data)
void PushSolution()
Push the current state as a new solution.
void AddObjective(IntVar *const objective)
std::vector< Assignment * > recycle_solutions_
std::vector< SolutionData > solution_data_
void Add(IntVar *const var)
Add API.
int solution_count() const
Returns how many solutions were stored during the search.
int64 DurationValue(int n, IntervalVar *const var) const
This is a shortcut to get the DurationValue of 'var' in the nth solution.
int64 PerformedValue(int n, IntervalVar *const var) const
This is a shortcut to get the PerformedValue of 'var' in the nth solution.
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.
SolutionData BuildSolutionDataForCurrentState()
Assignment * solution(int n) const
Returns the nth solution.
int64 wall_time(int n) const
Returns the wall time in ms for the nth solution.
int64 EndValue(int n, IntervalVar *const var) const
This is a shortcut to get the EndValue of 'var' in the nth solution.
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.
int64 objective_value(int n) const
Returns the objective value of the nth solution.
void FreeSolution(Assignment *solution)
std::unique_ptr< Assignment > prototype_
SolutionCollector(Solver *const solver, const Assignment *assignment)
int64 branches(int n) const
Returns the number of branches when the nth solution was found.
void PopSolution()
Remove and delete the last popped solution.
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.
int64 StartValue(int n, IntervalVar *const var) const
This is a shortcut to get the StartValue of 'var' in the nth solution.
SearchMonitor * MakeLubyRestart(int scale_factor)
This search monitor will restart the search periodically.
SolutionCollector * MakeAllSolutionCollector()
Collect all solutions of the search.
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.
Decision * MakeSplitVariableDomain(IntVar *const var, int64 val, bool start_with_lower_half)
OptimizeVar * MakeWeightedMaximize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a maximization weigthed objective.
SolutionCollector * MakeLastSolutionCollector()
Collect the last solution of the search.
RegularLimit * MakeSolutionsLimit(int64 solutions)
Creates a search limit that constrains the number of solutions found during the search.
SearchMonitor * MakeAtSolutionCallback(std::function< void()> callback)
IntVar * MakeIsGreaterOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var >= value)
SearchLimit * MakeCustomLimit(std::function< bool()> limiter)
Callback-based search limit.
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
int64 solutions() const
The number of solutions found since the start of the search.
Decision * MakeAssignVariableValueOrFail(IntVar *const var, int64 value)
OptimizeVar * MakeMaximize(IntVar *const v, int64 step)
Creates a maximization objective.
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.
std::function< bool(int64, int64, int64)> VariableValueComparator
SearchMonitor * MakeSimulatedAnnealing(bool maximize, IntVar *const v, int64 step, int64 initial_temperature)
Creates a Simulated Annealing monitor.
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...
RegularLimit * MakeFailuresLimit(int64 failures)
Creates a search limit that constrains the number of failures that can happen when exploring the sear...
SearchMonitor * MakeSearchLog(int branch_period)
The SearchMonitors below will display a periodic search log on LOG(INFO) every branch_period branches...
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)
Decision * MakeAssignVariableValueOrDoNothing(IntVar *const var, int64 value)
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 ...
Decision * MakeVariableLessOrEqualValue(IntVar *const var, int64 value)
int SearchDepth() const
Gets the search depth of the current active search.
IntVar * MakeIsEqualCstVar(IntExpr *const var, int64 value)
status var of (var == value)
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).
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.
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'.
SearchMonitor * MakeConstantRestart(int frequency)
This search monitor will restart the search periodically after 'frequency' failures.
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.
RegularLimit * MakeTimeLimit(absl::Duration time)
Creates a search limit that constrains the running time.
Decision * MakeVariableGreaterOrEqualValue(IntVar *const var, int64 value)
SearchMonitor * MakeSearchTrace(const std::string &prefix)
Creates a search monitor that will trace precisely the behavior of the search.
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.
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...
int64 unchecked_solutions() const
The number of unchecked solutions found by local search.
SearchMonitor * MakeEnterSearchCallback(std::function< void()> callback)
--— Callback-based search monitors --—
OptimizeVar * MakeWeightedMinimize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a minimization weighted objective.
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.
IntVar * MakeIsLessOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var <= value)
OptimizeVar * MakeMinimize(IntVar *const v, int64 step)
Creates a minimization objective.
std::function< int64(const IntVar *v, int64 id)> VariableValueSelector
SearchMonitor * MakeExitSearchCallback(std::function< void()> callback)
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,...
OptimizeVar * MakeOptimize(bool maximize, IntVar *const v, int64 step)
Creates a objective with a given sense (true = maximization).
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)
void AddIntegerVariableLessOrEqualValueClause(IntVar *const var, int64 value)
void AddIntegerVariableGreaterOrEqualValueClause(IntVar *const var, int64 value)
void AddTermToClause(SymmetryBreaker *const visitor, IntVar *const term)
~SymmetryManager() override
void EndNextDecision(DecisionBuilder *const db, Decision *const d) override
After calling DecisionBuilder::Next, along with the returned decision.
void CheckSymmetries(int index)
void RefuteDecision(Decision *d) override
Before refuting the decision.
SymmetryManager(Solver *const s, const std::vector< SymmetryBreaker * > &visitors)
std::string DebugString() const override
std::vector< IntVarIterator * > iterators_
static const int64 kint64max
static const uint64 kuint64max
static const int32 kint32max
static const int64 kint64min
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
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)
void STLDeleteElements(T *container)
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
std::function< int64(const Model &)> Value(IntegerVariable v)
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
BaseAssignVariables::Mode ChooseMode(Solver::IntValueStrategy val_str)
bool AcceptDelta(Search *const search, Assignment *delta, Assignment *deltadelta)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
void AcceptNeighbor(Search *const search)
std::unique_ptr< int64[]> delta_cache_
const double penalty_factor_
std::vector< DecisionBuilder * > builders_
int64 assignment_penalized_value_
int64 old_penalized_value_
BaseVariableAssignmentSelector *const selector_
std::function< int64(int64, int64)> evaluator_
Rev< int64 > first_unbound_
const int solution_count_
ABSL_FLAG(bool, cp_use_sparse_gls_penalties, false, "Use sparse implementation to store Guided Local Search penalties")
IntVar * penalized_objective_
std::vector< IntVar * > vars_
std::priority_queue< std::pair< int64, SolutionData > > solutions_pq_
Rev< int64 > last_unbound_
absl::flat_hash_map< const IntVar *, int64 > indices_
std::unique_ptr< int64[]> current_penalized_values_
Creates a search monitor from logging parameters.