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