OR-Tools  8.2
constraint_solver.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 //
15 // This file implements the core objects of the constraint solver:
16 // Solver, Search, Queue, ... along with the main resolution loop.
17 
19 
20 #include <csetjmp>
21 #include <deque>
22 #include <iosfwd>
23 #include <memory>
24 #include <string>
25 #include <utility>
26 
27 #include "absl/memory/memory.h"
28 #include "absl/time/clock.h"
29 #include "absl/time/time.h"
31 #include "ortools/base/file.h"
33 #include "ortools/base/logging.h"
34 #include "ortools/base/macros.h"
35 #include "ortools/base/map_util.h"
36 #include "ortools/base/recordio.h"
37 #include "ortools/base/stl_util.h"
39 #include "ortools/util/tuple_set.h"
40 #include "zlib.h"
41 
42 // These flags are used to set the fields in the DefaultSolverParameters proto.
43 ABSL_FLAG(bool, cp_trace_propagation, false,
44  "Trace propagation events (constraint and demon executions,"
45  " variable modifications).");
46 ABSL_FLAG(bool, cp_trace_search, false, "Trace search events");
47 ABSL_FLAG(bool, cp_print_added_constraints, false,
48  "show all constraints added to the solver.");
49 ABSL_FLAG(bool, cp_print_model, false,
50  "use PrintModelVisitor on model before solving.");
51 ABSL_FLAG(bool, cp_model_stats, false,
52  "use StatisticsModelVisitor on model before solving.");
53 ABSL_FLAG(bool, cp_disable_solve, false,
54  "Force failure at the beginning of a search.");
55 ABSL_FLAG(std::string, cp_profile_file, "",
56  "Export profiling overview to file.");
57 ABSL_FLAG(bool, cp_print_local_search_profile, false,
58  "Print local search profiling data after solving.");
59 ABSL_FLAG(bool, cp_name_variables, false, "Force all variables to have names.");
60 ABSL_FLAG(bool, cp_name_cast_variables, false,
61  "Name variables casted from expressions");
62 ABSL_FLAG(bool, cp_use_small_table, true,
63  "Use small compact table constraint when possible.");
64 ABSL_FLAG(bool, cp_use_cumulative_edge_finder, true,
65  "Use the O(n log n) cumulative edge finding algorithm described "
66  "in 'Edge Finding Filtering Algorithm for Discrete Cumulative "
67  "Resources in O(kn log n)' by Petr Vilim, CP 2009.");
68 ABSL_FLAG(bool, cp_use_cumulative_time_table, true,
69  "Use a O(n^2) cumulative time table propagation algorithm.");
70 ABSL_FLAG(bool, cp_use_cumulative_time_table_sync, false,
71  "Use a synchronized O(n^2 log n) cumulative time table propagation "
72  "algorithm.");
73 ABSL_FLAG(bool, cp_use_sequence_high_demand_tasks, true,
74  "Use a sequence constraints for cumulative tasks that have a "
75  "demand greater than half of the capacity of the resource.");
76 ABSL_FLAG(bool, cp_use_all_possible_disjunctions, true,
77  "Post temporal disjunctions for all pairs of tasks sharing a "
78  "cumulative resource and that cannot overlap because the sum of "
79  "their demand exceeds the capacity.");
80 ABSL_FLAG(int, cp_max_edge_finder_size, 50,
81  "Do not post the edge finder in the cumulative constraints if "
82  "it contains more than this number of tasks");
83 ABSL_FLAG(bool, cp_diffn_use_cumulative, true,
84  "Diffn constraint adds redundant cumulative constraint");
85 ABSL_FLAG(bool, cp_use_element_rmq, true,
86  "If true, rmq's will be used in element expressions.");
87 ABSL_FLAG(int, cp_check_solution_period, 1,
88  "Number of solutions explored between two solution checks during "
89  "local search.");
90 ABSL_FLAG(int64, cp_random_seed, 12345,
91  "Random seed used in several (but not all) random number "
92  "generators used by the CP solver. Use -1 to auto-generate an"
93  "undeterministic random seed.");
94 
95 void ConstraintSolverFailsHere() { VLOG(3) << "Fail"; }
96 
97 #if defined(_MSC_VER) // WINDOWS
98 #pragma warning(disable : 4351 4355)
99 #endif
100 
101 namespace operations_research {
102 
103 namespace {
104 // Calls the given method with the provided arguments on all objects in the
105 // collection.
106 template <typename T, typename MethodPointer, typename... Args>
107 void ForAll(const std::vector<T*>& objects, MethodPointer method,
108  const Args&... args) {
109  for (T* const object : objects) {
110  DCHECK(object != nullptr);
111  (object->*method)(args...);
112  }
113 }
114 } // namespace
115 
116 // ----- ConstraintSolverParameters -----
117 
118 ConstraintSolverParameters Solver::DefaultSolverParameters() {
119  ConstraintSolverParameters params;
120  params.set_compress_trail(ConstraintSolverParameters::NO_COMPRESSION);
121  params.set_trail_block_size(8000);
122  params.set_array_split_size(16);
123  params.set_store_names(true);
124  params.set_profile_propagation(!absl::GetFlag(FLAGS_cp_profile_file).empty());
125  params.set_trace_propagation(absl::GetFlag(FLAGS_cp_trace_propagation));
126  params.set_trace_search(absl::GetFlag(FLAGS_cp_trace_search));
127  params.set_name_all_variables(absl::GetFlag(FLAGS_cp_name_variables));
128  params.set_profile_file(absl::GetFlag(FLAGS_cp_profile_file));
129  params.set_profile_local_search(
130  absl::GetFlag(FLAGS_cp_print_local_search_profile));
131  params.set_print_local_search_profile(
132  absl::GetFlag(FLAGS_cp_print_local_search_profile));
133  params.set_print_model(absl::GetFlag(FLAGS_cp_print_model));
134  params.set_print_model_stats(absl::GetFlag(FLAGS_cp_model_stats));
135  params.set_disable_solve(absl::GetFlag(FLAGS_cp_disable_solve));
136  params.set_name_cast_variables(absl::GetFlag(FLAGS_cp_name_cast_variables));
137  params.set_print_added_constraints(
138  absl::GetFlag(FLAGS_cp_print_added_constraints));
139  params.set_use_small_table(absl::GetFlag(FLAGS_cp_use_small_table));
140  params.set_use_cumulative_edge_finder(
141  absl::GetFlag(FLAGS_cp_use_cumulative_edge_finder));
142  params.set_use_cumulative_time_table(
143  absl::GetFlag(FLAGS_cp_use_cumulative_time_table));
144  params.set_use_cumulative_time_table_sync(
145  absl::GetFlag(FLAGS_cp_use_cumulative_time_table_sync));
146  params.set_use_sequence_high_demand_tasks(
147  absl::GetFlag(FLAGS_cp_use_sequence_high_demand_tasks));
148  params.set_use_all_possible_disjunctions(
149  absl::GetFlag(FLAGS_cp_use_all_possible_disjunctions));
150  params.set_max_edge_finder_size(absl::GetFlag(FLAGS_cp_max_edge_finder_size));
151  params.set_diffn_use_cumulative(absl::GetFlag(FLAGS_cp_diffn_use_cumulative));
152  params.set_use_element_rmq(absl::GetFlag(FLAGS_cp_use_element_rmq));
153  params.set_check_solution_period(
154  absl::GetFlag(FLAGS_cp_check_solution_period));
155  return params;
156 }
157 
158 // ----- Forward Declarations and Profiling Support -----
159 extern DemonProfiler* BuildDemonProfiler(Solver* const solver);
160 extern void DeleteDemonProfiler(DemonProfiler* const monitor);
161 extern void InstallDemonProfiler(DemonProfiler* const monitor);
163 extern void DeleteLocalSearchProfiler(LocalSearchProfiler* monitor);
164 extern void InstallLocalSearchProfiler(LocalSearchProfiler* monitor);
165 
166 // TODO(user): remove this complex logic.
167 // We need the double test because parameters are set too late when using
168 // python in the open source. This is the cheapest work-around.
171 }
172 
174  return parameters_.profile_propagation() ||
175  !parameters_.profile_file().empty();
176 }
177 
179  return parameters_.profile_local_search() ||
180  parameters_.print_local_search_profile();
181 }
182 
184  return parameters_.trace_propagation();
185 }
186 
188  return parameters_.name_all_variables();
189 }
190 
191 // ------------------ Demon class ----------------
192 
195 }
196 
197 std::string Demon::DebugString() const { return "Demon"; }
198 
199 void Demon::inhibit(Solver* const s) {
200  if (stamp_ < kuint64max) {
201  s->SaveAndSetValue(&stamp_, kuint64max);
202  }
203 }
204 
205 void Demon::desinhibit(Solver* const s) {
206  if (stamp_ == kuint64max) {
207  s->SaveAndSetValue(&stamp_, s->stamp() - 1);
208  }
209 }
210 
211 // ------------------ Queue class ------------------
212 
213 extern void CleanVariableOnFail(IntVar* const var);
214 
215 class Queue {
216  public:
217  static constexpr int64 kTestPeriod = 10000;
218 
219  explicit Queue(Solver* const s)
220  : solver_(s),
221  stamp_(1),
222  freeze_level_(0),
223  in_process_(false),
224  clean_action_(nullptr),
225  clean_variable_(nullptr),
226  in_add_(false),
227  instruments_demons_(s->InstrumentsDemons()) {}
228 
229  ~Queue() {}
230 
231  void Freeze() {
232  freeze_level_++;
233  stamp_++;
234  }
235 
236  void Unfreeze() {
237  if (--freeze_level_ == 0) {
238  Process();
239  }
240  }
241 
242  void ProcessOneDemon(Demon* const demon) {
243  demon->set_stamp(stamp_ - 1);
244  if (!instruments_demons_) {
245  if (++solver_->demon_runs_[demon->priority()] % kTestPeriod == 0) {
246  solver_->TopPeriodicCheck();
247  }
248  demon->Run(solver_);
249  solver_->CheckFail();
250  } else {
251  solver_->GetPropagationMonitor()->BeginDemonRun(demon);
252  if (++solver_->demon_runs_[demon->priority()] % kTestPeriod == 0) {
253  solver_->TopPeriodicCheck();
254  }
255  demon->Run(solver_);
256  solver_->CheckFail();
257  solver_->GetPropagationMonitor()->EndDemonRun(demon);
258  }
259  }
260 
261  void Process() {
262  if (!in_process_) {
263  in_process_ = true;
264  while (!var_queue_.empty() || !delayed_queue_.empty()) {
265  if (!var_queue_.empty()) {
266  Demon* const demon = var_queue_.front();
267  var_queue_.pop_front();
268  ProcessOneDemon(demon);
269  } else {
270  DCHECK(!delayed_queue_.empty());
271  Demon* const demon = delayed_queue_.front();
272  delayed_queue_.pop_front();
273  ProcessOneDemon(demon);
274  }
275  }
276  in_process_ = false;
277  }
278  }
279 
280  void ExecuteAll(const SimpleRevFIFO<Demon*>& demons) {
281  if (!instruments_demons_) {
282  for (SimpleRevFIFO<Demon*>::Iterator it(&demons); it.ok(); ++it) {
283  Demon* const demon = *it;
284  if (demon->stamp() < stamp_) {
286  if (++solver_->demon_runs_[Solver::NORMAL_PRIORITY] % kTestPeriod ==
287  0) {
288  solver_->TopPeriodicCheck();
289  }
290  demon->Run(solver_);
291  solver_->CheckFail();
292  }
293  }
294  } else {
295  for (SimpleRevFIFO<Demon*>::Iterator it(&demons); it.ok(); ++it) {
296  Demon* const demon = *it;
297  if (demon->stamp() < stamp_) {
299  solver_->GetPropagationMonitor()->BeginDemonRun(demon);
300  if (++solver_->demon_runs_[Solver::NORMAL_PRIORITY] % kTestPeriod ==
301  0) {
302  solver_->TopPeriodicCheck();
303  }
304  demon->Run(solver_);
305  solver_->CheckFail();
306  solver_->GetPropagationMonitor()->EndDemonRun(demon);
307  }
308  }
309  }
310  }
311 
312  void EnqueueAll(const SimpleRevFIFO<Demon*>& demons) {
313  for (SimpleRevFIFO<Demon*>::Iterator it(&demons); it.ok(); ++it) {
314  EnqueueDelayedDemon(*it);
315  }
316  }
317 
318  void EnqueueVar(Demon* const demon) {
319  DCHECK(demon->priority() == Solver::VAR_PRIORITY);
320  if (demon->stamp() < stamp_) {
321  demon->set_stamp(stamp_);
322  var_queue_.push_back(demon);
323  if (freeze_level_ == 0) {
324  Process();
325  }
326  }
327  }
328 
329  void EnqueueDelayedDemon(Demon* const demon) {
331  if (demon->stamp() < stamp_) {
332  demon->set_stamp(stamp_);
333  delayed_queue_.push_back(demon);
334  }
335  }
336 
337  void AfterFailure() {
338  // Clean queue.
339  var_queue_.clear();
340  delayed_queue_.clear();
341 
342  // Call cleaning actions on variables.
343  if (clean_action_ != nullptr) {
344  clean_action_(solver_);
345  clean_action_ = nullptr;
346  } else if (clean_variable_ != nullptr) {
347  CleanVariableOnFail(clean_variable_);
348  clean_variable_ = nullptr;
349  }
350 
351  freeze_level_ = 0;
352  in_process_ = false;
353  in_add_ = false;
354  to_add_.clear();
355  }
356 
357  void increase_stamp() { stamp_++; }
358 
359  uint64 stamp() const { return stamp_; }
360 
362  DCHECK(clean_variable_ == nullptr);
363  clean_action_ = std::move(a);
364  }
365 
367  DCHECK(clean_action_ == nullptr);
368  clean_variable_ = var;
369  }
370 
372  DCHECK(clean_variable_ == nullptr);
373  clean_action_ = nullptr;
374  }
375 
376  void AddConstraint(Constraint* const c) {
377  to_add_.push_back(c);
379  }
380 
382  if (!in_add_) {
383  in_add_ = true;
384  // We cannot store to_add_.size() as constraints can add other
385  // constraints. For the same reason a range-based for loop cannot be used.
386  // TODO(user): Make to_add_ a queue to make the behavior more obvious.
387  for (int counter = 0; counter < to_add_.size(); ++counter) {
388  Constraint* const constraint = to_add_[counter];
389  // TODO(user): Add profiling to initial propagation
390  constraint->PostAndPropagate();
391  }
392  in_add_ = false;
393  to_add_.clear();
394  }
395  }
396 
397  private:
398  Solver* const solver_;
399  std::deque<Demon*> var_queue_;
400  std::deque<Demon*> delayed_queue_;
401  uint64 stamp_;
402  // The number of nested freeze levels. The queue is frozen if and only if
403  // freeze_level_ > 0.
404  uint32 freeze_level_;
405  bool in_process_;
406  Solver::Action clean_action_;
407  IntVar* clean_variable_;
408  std::vector<Constraint*> to_add_;
409  bool in_add_;
410  const bool instruments_demons_;
411 };
412 
413 // ------------------ StateMarker / StateInfo struct -----------
414 
415 struct StateInfo { // This is an internal structure to store
416  // additional information on the choice point.
417  public:
419  : ptr_info(nullptr),
420  int_info(0),
421  depth(0),
422  left_depth(0),
423  reversible_action(nullptr) {}
424  StateInfo(void* pinfo, int iinfo)
425  : ptr_info(pinfo),
426  int_info(iinfo),
427  depth(0),
428  left_depth(0),
429  reversible_action(nullptr) {}
430  StateInfo(void* pinfo, int iinfo, int d, int ld)
431  : ptr_info(pinfo),
432  int_info(iinfo),
433  depth(d),
434  left_depth(ld),
435  reversible_action(nullptr) {}
437  : ptr_info(nullptr),
438  int_info(static_cast<int>(fast)),
439  depth(0),
440  left_depth(0),
441  reversible_action(std::move(a)) {}
442 
443  void* ptr_info;
444  int int_info;
445  int depth;
448 };
449 
450 struct StateMarker {
451  public:
452  StateMarker(Solver::MarkerType t, const StateInfo& info);
453  friend class Solver;
454  friend struct Trail;
455 
456  private:
457  Solver::MarkerType type_;
458  int rev_int_index_;
459  int rev_int64_index_;
460  int rev_uint64_index_;
461  int rev_double_index_;
462  int rev_ptr_index_;
463  int rev_boolvar_list_index_;
464  int rev_bools_index_;
465  int rev_int_memory_index_;
466  int rev_int64_memory_index_;
467  int rev_double_memory_index_;
468  int rev_object_memory_index_;
469  int rev_object_array_memory_index_;
470  int rev_memory_index_;
471  int rev_memory_array_index_;
472  StateInfo info_;
473 };
474 
476  : type_(t),
477  rev_int_index_(0),
478  rev_int64_index_(0),
479  rev_uint64_index_(0),
480  rev_double_index_(0),
481  rev_ptr_index_(0),
482  rev_boolvar_list_index_(0),
483  rev_bools_index_(0),
484  rev_int_memory_index_(0),
485  rev_int64_memory_index_(0),
486  rev_double_memory_index_(0),
487  rev_object_memory_index_(0),
488  rev_object_array_memory_index_(0),
489  info_(info) {}
490 
491 // ---------- Trail and Reversibility ----------
492 
493 namespace {
494 // ----- addrval struct -----
495 
496 // This template class is used internally to implement reversibility.
497 // It stores an address and the value that was at the address.
498 template <class T>
499 struct addrval {
500  public:
501  addrval() : address_(nullptr) {}
502  explicit addrval(T* adr) : address_(adr), old_value_(*adr) {}
503  void restore() const { (*address_) = old_value_; }
504 
505  private:
506  T* address_;
507  T old_value_;
508 };
509 
510 // ----- Compressed trail -----
511 
512 // ---------- Trail Packer ---------
513 // Abstract class to pack trail blocks.
514 
515 template <class T>
516 class TrailPacker {
517  public:
518  explicit TrailPacker(int block_size) : block_size_(block_size) {}
519  virtual ~TrailPacker() {}
520  int input_size() const { return block_size_ * sizeof(addrval<T>); }
521  virtual void Pack(const addrval<T>* block, std::string* packed_block) = 0;
522  virtual void Unpack(const std::string& packed_block, addrval<T>* block) = 0;
523 
524  private:
525  const int block_size_;
526  DISALLOW_COPY_AND_ASSIGN(TrailPacker);
527 };
528 
529 template <class T>
530 class NoCompressionTrailPacker : public TrailPacker<T> {
531  public:
532  explicit NoCompressionTrailPacker(int block_size)
533  : TrailPacker<T>(block_size) {}
534  ~NoCompressionTrailPacker() override {}
535  void Pack(const addrval<T>* block, std::string* packed_block) override {
536  DCHECK(block != nullptr);
537  DCHECK(packed_block != nullptr);
538  absl::string_view block_str(reinterpret_cast<const char*>(block),
539  this->input_size());
540  packed_block->assign(block_str.data(), block_str.size());
541  }
542  void Unpack(const std::string& packed_block, addrval<T>* block) override {
543  DCHECK(block != nullptr);
544  memcpy(block, packed_block.c_str(), packed_block.size());
545  }
546 
547  private:
548  DISALLOW_COPY_AND_ASSIGN(NoCompressionTrailPacker<T>);
549 };
550 
551 template <class T>
552 class ZlibTrailPacker : public TrailPacker<T> {
553  public:
554  explicit ZlibTrailPacker(int block_size)
555  : TrailPacker<T>(block_size),
556  tmp_size_(compressBound(this->input_size())),
557  tmp_block_(new char[tmp_size_]) {}
558 
559  ~ZlibTrailPacker() override {}
560 
561  void Pack(const addrval<T>* block, std::string* packed_block) override {
562  DCHECK(block != nullptr);
563  DCHECK(packed_block != nullptr);
564  uLongf size = tmp_size_;
565  const int result =
566  compress(reinterpret_cast<Bytef*>(tmp_block_.get()), &size,
567  reinterpret_cast<const Bytef*>(block), this->input_size());
568  CHECK_EQ(Z_OK, result);
569  absl::string_view block_str;
570  block_str = absl::string_view(tmp_block_.get(), size);
571  packed_block->assign(block_str.data(), block_str.size());
572  }
573 
574  void Unpack(const std::string& packed_block, addrval<T>* block) override {
575  DCHECK(block != nullptr);
576  uLongf size = this->input_size();
577  const int result =
578  uncompress(reinterpret_cast<Bytef*>(block), &size,
579  reinterpret_cast<const Bytef*>(packed_block.c_str()),
580  packed_block.size());
581  CHECK_EQ(Z_OK, result);
582  }
583 
584  private:
585  const uint64 tmp_size_;
586  std::unique_ptr<char[]> tmp_block_;
587  DISALLOW_COPY_AND_ASSIGN(ZlibTrailPacker<T>);
588 };
589 
590 template <class T>
591 class CompressedTrail {
592  public:
593  CompressedTrail(
594  int block_size,
595  ConstraintSolverParameters::TrailCompression compression_level)
596  : block_size_(block_size),
597  blocks_(nullptr),
598  free_blocks_(nullptr),
599  data_(new addrval<T>[block_size]),
600  buffer_(new addrval<T>[block_size]),
601  buffer_used_(false),
602  current_(0),
603  size_(0) {
604  switch (compression_level) {
605  case ConstraintSolverParameters::NO_COMPRESSION: {
606  packer_.reset(new NoCompressionTrailPacker<T>(block_size));
607  break;
608  }
609  case ConstraintSolverParameters::COMPRESS_WITH_ZLIB: {
610  packer_.reset(new ZlibTrailPacker<T>(block_size));
611  break;
612  }
613  default: {
614  LOG(ERROR) << "Should not be here";
615  }
616  }
617 
618  // We zero all memory used by addrval arrays.
619  // Because of padding, all bytes may not be initialized, while compression
620  // will read them all, even if the uninitialized bytes are never used.
621  // This makes valgrind happy.
622 
623  memset(data_.get(), 0, sizeof(*data_.get()) * block_size);
624  memset(buffer_.get(), 0, sizeof(*buffer_.get()) * block_size);
625  }
626  ~CompressedTrail() {
627  FreeBlocks(blocks_);
628  FreeBlocks(free_blocks_);
629  }
630  const addrval<T>& Back() const {
631  // Back of empty trail.
632  DCHECK_GT(current_, 0);
633  return data_[current_ - 1];
634  }
635  void PopBack() {
636  if (size_ > 0) {
637  --current_;
638  if (current_ <= 0) {
639  if (buffer_used_) {
640  data_.swap(buffer_);
641  current_ = block_size_;
642  buffer_used_ = false;
643  } else if (blocks_ != nullptr) {
644  packer_->Unpack(blocks_->compressed, data_.get());
645  FreeTopBlock();
646  current_ = block_size_;
647  }
648  }
649  --size_;
650  }
651  }
652  void PushBack(const addrval<T>& addr_val) {
653  if (current_ >= block_size_) {
654  if (buffer_used_) { // Buffer is used.
655  NewTopBlock();
656  packer_->Pack(buffer_.get(), &blocks_->compressed);
657  // O(1) operation.
658  data_.swap(buffer_);
659  } else {
660  data_.swap(buffer_);
661  buffer_used_ = true;
662  }
663  current_ = 0;
664  }
665  data_[current_] = addr_val;
666  ++current_;
667  ++size_;
668  }
669  int64 size() const { return size_; }
670 
671  private:
672  struct Block {
673  std::string compressed;
674  Block* next;
675  };
676 
677  void FreeTopBlock() {
678  Block* block = blocks_;
679  blocks_ = block->next;
680  block->compressed.clear();
681  block->next = free_blocks_;
682  free_blocks_ = block;
683  }
684  void NewTopBlock() {
685  Block* block = nullptr;
686  if (free_blocks_ != nullptr) {
687  block = free_blocks_;
688  free_blocks_ = block->next;
689  } else {
690  block = new Block;
691  }
692  block->next = blocks_;
693  blocks_ = block;
694  }
695  void FreeBlocks(Block* blocks) {
696  while (nullptr != blocks) {
697  Block* next = blocks->next;
698  delete blocks;
699  blocks = next;
700  }
701  }
702 
703  std::unique_ptr<TrailPacker<T> > packer_;
704  const int block_size_;
705  Block* blocks_;
706  Block* free_blocks_;
707  std::unique_ptr<addrval<T>[]> data_;
708  std::unique_ptr<addrval<T>[]> buffer_;
709  bool buffer_used_;
710  int current_;
711  int size_;
712 };
713 } // namespace
714 
715 // ----- Trail -----
716 
717 // Object are explicitly copied using the copy ctor instead of
718 // passing and storing a pointer. As objects are small, copying is
719 // much faster than allocating (around 35% on a complete solve).
720 
721 extern void RestoreBoolValue(IntVar* const var);
722 
723 struct Trail {
724  CompressedTrail<int> rev_ints_;
725  CompressedTrail<int64> rev_int64s_;
726  CompressedTrail<uint64> rev_uint64s_;
727  CompressedTrail<double> rev_doubles_;
728  CompressedTrail<void*> rev_ptrs_;
729  std::vector<IntVar*> rev_boolvar_list_;
730  std::vector<bool*> rev_bools_;
731  std::vector<bool> rev_bool_value_;
732  std::vector<int*> rev_int_memory_;
733  std::vector<int64*> rev_int64_memory_;
734  std::vector<double*> rev_double_memory_;
735  std::vector<BaseObject*> rev_object_memory_;
736  std::vector<BaseObject**> rev_object_array_memory_;
737  std::vector<void*> rev_memory_;
738  std::vector<void**> rev_memory_array_;
739 
740  Trail(int block_size,
741  ConstraintSolverParameters::TrailCompression compression_level)
742  : rev_ints_(block_size, compression_level),
743  rev_int64s_(block_size, compression_level),
744  rev_uint64s_(block_size, compression_level),
745  rev_doubles_(block_size, compression_level),
746  rev_ptrs_(block_size, compression_level) {}
747 
749  int target = m->rev_int_index_;
750  for (int curr = rev_ints_.size(); curr > target; --curr) {
751  const addrval<int>& cell = rev_ints_.Back();
752  cell.restore();
753  rev_ints_.PopBack();
754  }
755  DCHECK_EQ(rev_ints_.size(), target);
756  // Incorrect trail size after backtrack.
757  target = m->rev_int64_index_;
758  for (int curr = rev_int64s_.size(); curr > target; --curr) {
759  const addrval<int64>& cell = rev_int64s_.Back();
760  cell.restore();
761  rev_int64s_.PopBack();
762  }
763  DCHECK_EQ(rev_int64s_.size(), target);
764  // Incorrect trail size after backtrack.
765  target = m->rev_uint64_index_;
766  for (int curr = rev_uint64s_.size(); curr > target; --curr) {
767  const addrval<uint64>& cell = rev_uint64s_.Back();
768  cell.restore();
769  rev_uint64s_.PopBack();
770  }
771  DCHECK_EQ(rev_uint64s_.size(), target);
772  // Incorrect trail size after backtrack.
773  target = m->rev_double_index_;
774  for (int curr = rev_doubles_.size(); curr > target; --curr) {
775  const addrval<double>& cell = rev_doubles_.Back();
776  cell.restore();
777  rev_doubles_.PopBack();
778  }
779  DCHECK_EQ(rev_doubles_.size(), target);
780  // Incorrect trail size after backtrack.
781  target = m->rev_ptr_index_;
782  for (int curr = rev_ptrs_.size(); curr > target; --curr) {
783  const addrval<void*>& cell = rev_ptrs_.Back();
784  cell.restore();
785  rev_ptrs_.PopBack();
786  }
787  DCHECK_EQ(rev_ptrs_.size(), target);
788  // Incorrect trail size after backtrack.
789  target = m->rev_boolvar_list_index_;
790  for (int curr = rev_boolvar_list_.size() - 1; curr >= target; --curr) {
791  IntVar* const var = rev_boolvar_list_[curr];
793  }
794  rev_boolvar_list_.resize(target);
795 
796  DCHECK_EQ(rev_bools_.size(), rev_bool_value_.size());
797  target = m->rev_bools_index_;
798  for (int curr = rev_bools_.size() - 1; curr >= target; --curr) {
799  *(rev_bools_[curr]) = rev_bool_value_[curr];
800  }
801  rev_bools_.resize(target);
802  rev_bool_value_.resize(target);
803 
804  target = m->rev_int_memory_index_;
805  for (int curr = rev_int_memory_.size() - 1; curr >= target; --curr) {
806  delete[] rev_int_memory_[curr];
807  }
808  rev_int_memory_.resize(target);
809 
810  target = m->rev_int64_memory_index_;
811  for (int curr = rev_int64_memory_.size() - 1; curr >= target; --curr) {
812  delete[] rev_int64_memory_[curr];
813  }
814  rev_int64_memory_.resize(target);
815 
816  target = m->rev_double_memory_index_;
817  for (int curr = rev_double_memory_.size() - 1; curr >= target; --curr) {
818  delete[] rev_double_memory_[curr];
819  }
820  rev_double_memory_.resize(target);
821 
822  target = m->rev_object_memory_index_;
823  for (int curr = rev_object_memory_.size() - 1; curr >= target; --curr) {
824  delete rev_object_memory_[curr];
825  }
826  rev_object_memory_.resize(target);
827 
828  target = m->rev_object_array_memory_index_;
829  for (int curr = rev_object_array_memory_.size() - 1; curr >= target;
830  --curr) {
831  delete[] rev_object_array_memory_[curr];
832  }
833  rev_object_array_memory_.resize(target);
834 
835  target = m->rev_memory_index_;
836  for (int curr = rev_memory_.size() - 1; curr >= target; --curr) {
837  // Explicitly call unsized delete
838  ::operator delete(reinterpret_cast<char*>(rev_memory_[curr]));
839  // The previous cast is necessary to deallocate generic memory
840  // described by a void* when passed to the RevAlloc procedure
841  // We cannot do a delete[] there
842  // This is useful for cells of RevFIFO and should not be used outside
843  // of the product
844  }
845  rev_memory_.resize(target);
846 
847  target = m->rev_memory_array_index_;
848  for (int curr = rev_memory_array_.size() - 1; curr >= target; --curr) {
849  delete[] rev_memory_array_[curr];
850  // delete [] version of the previous unsafe case.
851  }
852  rev_memory_array_.resize(target);
853  }
854 };
855 
856 void Solver::InternalSaveValue(int* valptr) {
857  trail_->rev_ints_.PushBack(addrval<int>(valptr));
858 }
859 
860 void Solver::InternalSaveValue(int64* valptr) {
861  trail_->rev_int64s_.PushBack(addrval<int64>(valptr));
862 }
863 
864 void Solver::InternalSaveValue(uint64* valptr) {
865  trail_->rev_uint64s_.PushBack(addrval<uint64>(valptr));
866 }
867 
868 void Solver::InternalSaveValue(double* valptr) {
869  trail_->rev_doubles_.PushBack(addrval<double>(valptr));
870 }
871 
872 void Solver::InternalSaveValue(void** valptr) {
873  trail_->rev_ptrs_.PushBack(addrval<void*>(valptr));
874 }
875 
876 // TODO(user) : this code is unsafe if you save the same alternating
877 // bool multiple times.
878 // The correct code should use a bitset and a single list.
879 void Solver::InternalSaveValue(bool* valptr) {
880  trail_->rev_bools_.push_back(valptr);
881  trail_->rev_bool_value_.push_back(*valptr);
882 }
883 
884 BaseObject* Solver::SafeRevAlloc(BaseObject* ptr) {
885  check_alloc_state();
886  trail_->rev_object_memory_.push_back(ptr);
887  return ptr;
888 }
889 
890 int* Solver::SafeRevAllocArray(int* ptr) {
891  check_alloc_state();
892  trail_->rev_int_memory_.push_back(ptr);
893  return ptr;
894 }
895 
896 int64* Solver::SafeRevAllocArray(int64* ptr) {
897  check_alloc_state();
898  trail_->rev_int64_memory_.push_back(ptr);
899  return ptr;
900 }
901 
902 double* Solver::SafeRevAllocArray(double* ptr) {
903  check_alloc_state();
904  trail_->rev_double_memory_.push_back(ptr);
905  return ptr;
906 }
907 
908 uint64* Solver::SafeRevAllocArray(uint64* ptr) {
909  check_alloc_state();
910  trail_->rev_int64_memory_.push_back(reinterpret_cast<int64*>(ptr));
911  return ptr;
912 }
913 
914 BaseObject** Solver::SafeRevAllocArray(BaseObject** ptr) {
915  check_alloc_state();
916  trail_->rev_object_array_memory_.push_back(ptr);
917  return ptr;
918 }
919 
920 IntVar** Solver::SafeRevAllocArray(IntVar** ptr) {
921  BaseObject** in = SafeRevAllocArray(reinterpret_cast<BaseObject**>(ptr));
922  return reinterpret_cast<IntVar**>(in);
923 }
924 
925 IntExpr** Solver::SafeRevAllocArray(IntExpr** ptr) {
926  BaseObject** in = SafeRevAllocArray(reinterpret_cast<BaseObject**>(ptr));
927  return reinterpret_cast<IntExpr**>(in);
928 }
929 
930 Constraint** Solver::SafeRevAllocArray(Constraint** ptr) {
931  BaseObject** in = SafeRevAllocArray(reinterpret_cast<BaseObject**>(ptr));
932  return reinterpret_cast<Constraint**>(in);
933 }
934 
935 void* Solver::UnsafeRevAllocAux(void* ptr) {
936  check_alloc_state();
937  trail_->rev_memory_.push_back(ptr);
938  return ptr;
939 }
940 
941 void** Solver::UnsafeRevAllocArrayAux(void** ptr) {
942  check_alloc_state();
943  trail_->rev_memory_array_.push_back(ptr);
944  return ptr;
945 }
946 
947 void InternalSaveBooleanVarValue(Solver* const solver, IntVar* const var) {
948  solver->trail_->rev_boolvar_list_.push_back(var);
949 }
950 
951 // ------------------ Search class -----------------
952 
953 class Search {
954  public:
955  explicit Search(Solver* const s)
956  : solver_(s),
957  marker_stack_(),
958  fail_buffer_(),
959  solution_counter_(0),
960  unchecked_solution_counter_(0),
961  decision_builder_(nullptr),
962  created_by_solve_(false),
963  search_depth_(0),
964  left_search_depth_(0),
965  should_restart_(false),
966  should_finish_(false),
967  sentinel_pushed_(0),
968  jmpbuf_filled_(false),
969  backtrack_at_the_end_of_the_search_(true) {}
970 
971  // Constructor for a dummy search. The only difference between a dummy search
972  // and a regular one is that the search depth and left search depth is
973  // initialized to -1 instead of zero.
974  Search(Solver* const s, int /* dummy_argument */)
975  : solver_(s),
976  marker_stack_(),
977  fail_buffer_(),
978  solution_counter_(0),
979  unchecked_solution_counter_(0),
980  decision_builder_(nullptr),
981  created_by_solve_(false),
982  search_depth_(-1),
983  left_search_depth_(-1),
984  should_restart_(false),
985  should_finish_(false),
986  sentinel_pushed_(0),
987  jmpbuf_filled_(false),
988  backtrack_at_the_end_of_the_search_(true) {}
989 
990  ~Search() { gtl::STLDeleteElements(&marker_stack_); }
991 
992  void EnterSearch();
993  void RestartSearch();
994  void ExitSearch();
995  void BeginNextDecision(DecisionBuilder* const db);
996  void EndNextDecision(DecisionBuilder* const db, Decision* const d);
997  void ApplyDecision(Decision* const d);
998  void AfterDecision(Decision* const d, bool apply);
999  void RefuteDecision(Decision* const d);
1000  void BeginFail();
1001  void EndFail();
1002  void BeginInitialPropagation();
1003  void EndInitialPropagation();
1004  bool AtSolution();
1005  bool AcceptSolution();
1006  void NoMoreSolutions();
1007  bool LocalOptimum();
1008  bool AcceptDelta(Assignment* delta, Assignment* deltadelta);
1009  void AcceptNeighbor();
1010  void AcceptUncheckedNeighbor();
1012  void PeriodicCheck();
1013  int ProgressPercent();
1014  void Accept(ModelVisitor* const visitor) const;
1015  void push_monitor(SearchMonitor* const m);
1016  void Clear();
1017  void IncrementSolutionCounter() { ++solution_counter_; }
1018  int64 solution_counter() const { return solution_counter_; }
1019  void IncrementUncheckedSolutionCounter() { ++unchecked_solution_counter_; }
1021  return unchecked_solution_counter_;
1022  }
1024  decision_builder_ = db;
1025  }
1026  DecisionBuilder* decision_builder() const { return decision_builder_; }
1027  void set_created_by_solve(bool c) { created_by_solve_ = c; }
1028  bool created_by_solve() const { return created_by_solve_; }
1031  void LeftMove() {
1032  search_depth_++;
1033  left_search_depth_++;
1034  }
1035  void RightMove() { search_depth_++; }
1037  return backtrack_at_the_end_of_the_search_;
1038  }
1040  backtrack_at_the_end_of_the_search_ = restore;
1041  }
1042  int search_depth() const { return search_depth_; }
1043  void set_search_depth(int d) { search_depth_ = d; }
1044  int left_search_depth() const { return left_search_depth_; }
1045  void set_search_left_depth(int d) { left_search_depth_ = d; }
1046  void set_should_restart(bool s) { should_restart_ = s; }
1047  bool should_restart() const { return should_restart_; }
1048  void set_should_finish(bool s) { should_finish_ = s; }
1049  bool should_finish() const { return should_finish_; }
1050  void CheckFail() {
1051  if (should_finish_ || should_restart_) {
1052  solver_->Fail();
1053  }
1054  }
1055  void set_search_context(const std::string& search_context) {
1056  search_context_ = search_context;
1057  }
1058  std::string search_context() const { return search_context_; }
1059  friend class Solver;
1060 
1061  private:
1062  // Jumps back to the previous choice point, Checks if it was correctly set.
1063  void JumpBack();
1064  void ClearBuffer() {
1065  CHECK(jmpbuf_filled_) << "Internal error in backtracking";
1066  jmpbuf_filled_ = false;
1067  }
1068 
1069  Solver* const solver_;
1070  std::vector<StateMarker*> marker_stack_;
1071  std::vector<SearchMonitor*> monitors_;
1072  jmp_buf fail_buffer_;
1073  int64 solution_counter_;
1074  int64 unchecked_solution_counter_;
1075  DecisionBuilder* decision_builder_;
1076  bool created_by_solve_;
1078  int search_depth_;
1079  int left_search_depth_;
1080  bool should_restart_;
1081  bool should_finish_;
1082  int sentinel_pushed_;
1083  bool jmpbuf_filled_;
1084  bool backtrack_at_the_end_of_the_search_;
1085  std::string search_context_;
1086 };
1087 
1088 // Backtrack is implemented using 3 primitives:
1089 // CP_TRY to start searching
1090 // CP_DO_FAIL to signal a failure. The program will continue on the CP_ON_FAIL
1091 // primitive.
1092 // Implementation of backtrack using setjmp/longjmp.
1093 // The clean portable way is to use exceptions, unfortunately, it can be much
1094 // slower. Thus we use ideas from Prolog, CP/CLP implementations,
1095 // continuations in C and implement the default failing and backtracking
1096 // using setjmp/longjmp. You can still use exceptions by defining
1097 // CP_USE_EXCEPTIONS_FOR_BACKTRACK
1098 #ifndef CP_USE_EXCEPTIONS_FOR_BACKTRACK
1099 // We cannot use a method/function for this as we would lose the
1100 // context in the setjmp implementation.
1101 #define CP_TRY(search) \
1102  CHECK(!search->jmpbuf_filled_) << "Fail() called outside search"; \
1103  search->jmpbuf_filled_ = true; \
1104  if (setjmp(search->fail_buffer_) == 0)
1105 #define CP_ON_FAIL else
1106 #define CP_DO_FAIL(search) longjmp(search->fail_buffer_, 1)
1107 #else // CP_USE_EXCEPTIONS_FOR_BACKTRACK
1108 class FailException {};
1109 #define CP_TRY(search) \
1110  CHECK(!search->jmpbuf_filled_) << "Fail() called outside search"; \
1111  search->jmpbuf_filled_ = true; \
1112  try
1113 #define CP_ON_FAIL catch (FailException&)
1114 #define CP_DO_FAIL(search) throw FailException()
1115 #endif // CP_USE_EXCEPTIONS_FOR_BACKTRACK
1116 
1117 void Search::JumpBack() {
1118  if (jmpbuf_filled_) {
1119  jmpbuf_filled_ = false;
1120  CP_DO_FAIL(this);
1121  } else {
1122  std::string explanation = "Failure outside of search";
1123  solver_->AddConstraint(solver_->MakeFalseConstraint(explanation));
1124  }
1125 }
1126 
1127 Search* Solver::ActiveSearch() const { return searches_.back(); }
1128 
1129 namespace {
1130 class ApplyBranchSelector : public DecisionBuilder {
1131  public:
1132  explicit ApplyBranchSelector(Solver::BranchSelector bs)
1133  : selector_(std::move(bs)) {}
1134  ~ApplyBranchSelector() override {}
1135 
1136  Decision* Next(Solver* const s) override {
1137  s->SetBranchSelector(selector_);
1138  return nullptr;
1139  }
1140 
1141  std::string DebugString() const override { return "Apply(BranchSelector)"; }
1142 
1143  private:
1145 };
1146 } // namespace
1147 
1149  selector_ = std::move(bs);
1150 }
1151 
1153  // We cannot use the trail as the search can be nested and thus
1154  // deleted upon backtrack. Thus we guard the undo action by a
1155  // check on the number of nesting of solve().
1156  const int solve_depth = SolveDepth();
1158  [solve_depth](Solver* s) {
1159  if (s->SolveDepth() == solve_depth) {
1160  s->ActiveSearch()->SetBranchSelector(nullptr);
1161  }
1162  },
1163  false);
1164  searches_.back()->SetBranchSelector(std::move(bs));
1165 }
1166 
1168  return RevAlloc(new ApplyBranchSelector(std::move(bs)));
1169 }
1170 
1171 int Solver::SolveDepth() const {
1172  return state_ == OUTSIDE_SEARCH ? 0 : searches_.size() - 1;
1173 }
1174 
1175 int Solver::SearchDepth() const { return searches_.back()->search_depth(); }
1176 
1178  return searches_.back()->left_search_depth();
1179 }
1180 
1182  if (selector_ != nullptr) {
1183  return selector_();
1184  }
1185  return Solver::NO_CHANGE;
1186 }
1187 
1189  if (m) {
1190  monitors_.push_back(m);
1191  }
1192 }
1193 
1195  monitors_.clear();
1196  search_depth_ = 0;
1197  left_search_depth_ = 0;
1198  selector_ = nullptr;
1199  backtrack_at_the_end_of_the_search_ = true;
1200 }
1201 
1203  // The solution counter is reset when entering search and not when
1204  // leaving search. This enables the information to persist outside of
1205  // top-level search.
1206  solution_counter_ = 0;
1207  unchecked_solution_counter_ = 0;
1208 
1209  ForAll(monitors_, &SearchMonitor::EnterSearch);
1210 }
1211 
1213  // Backtrack to the correct state.
1214  ForAll(monitors_, &SearchMonitor::ExitSearch);
1215 }
1216 
1218  ForAll(monitors_, &SearchMonitor::RestartSearch);
1219 }
1220 
1222  ForAll(monitors_, &SearchMonitor::BeginNextDecision, db);
1223  CheckFail();
1224 }
1225 
1227  ForAll(monitors_, &SearchMonitor::EndNextDecision, db, d);
1228  CheckFail();
1229 }
1230 
1232  ForAll(monitors_, &SearchMonitor::ApplyDecision, d);
1233  CheckFail();
1234 }
1235 
1236 void Search::AfterDecision(Decision* const d, bool apply) {
1237  ForAll(monitors_, &SearchMonitor::AfterDecision, d, apply);
1238  CheckFail();
1239 }
1240 
1242  ForAll(monitors_, &SearchMonitor::RefuteDecision, d);
1243  CheckFail();
1244 }
1245 
1246 void Search::BeginFail() { ForAll(monitors_, &SearchMonitor::BeginFail); }
1247 
1248 void Search::EndFail() { ForAll(monitors_, &SearchMonitor::EndFail); }
1249 
1251  ForAll(monitors_, &SearchMonitor::BeginInitialPropagation);
1252 }
1253 
1255  ForAll(monitors_, &SearchMonitor::EndInitialPropagation);
1256 }
1257 
1259  bool valid = true;
1260  for (SearchMonitor* const monitor : monitors_) {
1261  if (!monitor->AcceptSolution()) {
1262  // Even though we know the return value, we cannot return yet: this would
1263  // break the contract we have with solution monitors. They all deserve
1264  // a chance to look at the solution.
1265  valid = false;
1266  }
1267  }
1268  return valid;
1269 }
1270 
1272  bool should_continue = false;
1273  for (SearchMonitor* const monitor : monitors_) {
1274  if (monitor->AtSolution()) {
1275  // Even though we know the return value, we cannot return yet: this would
1276  // break the contract we have with solution monitors. They all deserve
1277  // a chance to look at the solution.
1278  should_continue = true;
1279  }
1280  }
1281  return should_continue;
1282 }
1283 
1285  ForAll(monitors_, &SearchMonitor::NoMoreSolutions);
1286 }
1287 
1289  bool res = false;
1290  for (SearchMonitor* const monitor : monitors_) {
1291  if (monitor->LocalOptimum()) {
1292  res = true;
1293  }
1294  }
1295  return res;
1296 }
1297 
1299  bool accept = true;
1300  for (SearchMonitor* const monitor : monitors_) {
1301  if (!monitor->AcceptDelta(delta, deltadelta)) {
1302  accept = false;
1303  }
1304  }
1305  return accept;
1306 }
1307 
1309  ForAll(monitors_, &SearchMonitor::AcceptNeighbor);
1310 }
1311 
1313  ForAll(monitors_, &SearchMonitor::AcceptUncheckedNeighbor);
1314 }
1315 
1317  for (SearchMonitor* const monitor : monitors_) {
1318  if (monitor->IsUncheckedSolutionLimitReached()) {
1319  return true;
1320  }
1321  }
1322  return false;
1323 }
1324 
1326  ForAll(monitors_, &SearchMonitor::PeriodicCheck);
1327 }
1328 
1330  int progress = SearchMonitor::kNoProgress;
1331  for (SearchMonitor* const monitor : monitors_) {
1332  progress = std::max(progress, monitor->ProgressPercent());
1333  }
1334  return progress;
1335 }
1336 
1337 void Search::Accept(ModelVisitor* const visitor) const {
1338  ForAll(monitors_, &SearchMonitor::Accept, visitor);
1339  if (decision_builder_ != nullptr) {
1340  decision_builder_->Accept(visitor);
1341  }
1342 }
1343 
1344 bool LocalOptimumReached(Search* const search) {
1345  return search->LocalOptimum();
1346 }
1347 
1348 bool AcceptDelta(Search* const search, Assignment* delta,
1349  Assignment* deltadelta) {
1350  return search->AcceptDelta(delta, deltadelta);
1351 }
1352 
1353 void AcceptNeighbor(Search* const search) { search->AcceptNeighbor(); }
1354 
1355 void AcceptUncheckedNeighbor(Search* const search) {
1356  search->AcceptUncheckedNeighbor();
1357 }
1358 
1359 namespace {
1360 
1361 // ---------- Fail Decision ----------
1362 
1363 class FailDecision : public Decision {
1364  public:
1365  void Apply(Solver* const s) override { s->Fail(); }
1366  void Refute(Solver* const s) override { s->Fail(); }
1367 };
1368 
1369 // Balancing decision
1370 
1371 class BalancingDecision : public Decision {
1372  public:
1373  ~BalancingDecision() override {}
1374  void Apply(Solver* const s) override {}
1375  void Refute(Solver* const s) override {}
1376 };
1377 } // namespace
1378 
1379 Decision* Solver::MakeFailDecision() { return fail_decision_.get(); }
1380 
1381 // ------------------ Solver class -----------------
1382 
1383 // These magic numbers are there to make sure we pop the correct
1384 // sentinels throughout the search.
1385 namespace {
1386 enum SentinelMarker {
1387  INITIAL_SEARCH_SENTINEL = 10000000,
1388  ROOT_NODE_SENTINEL = 20000000,
1389  SOLVER_CTOR_SENTINEL = 40000000
1390 };
1391 } // namespace
1392 
1393 extern PropagationMonitor* BuildTrace(Solver* const s);
1394 extern LocalSearchMonitor* BuildLocalSearchMonitorMaster(Solver* const s);
1395 extern ModelCache* BuildModelCache(Solver* const solver);
1396 
1397 std::string Solver::model_name() const { return name_; }
1398 
1399 namespace {
1400 void CheckSolverParameters(const ConstraintSolverParameters& parameters) {
1401  CHECK_GT(parameters.array_split_size(), 0)
1402  << "Were parameters built using Solver::DefaultSolverParameters() ?";
1403 }
1404 } // namespace
1405 
1406 Solver::Solver(const std::string& name,
1407  const ConstraintSolverParameters& parameters)
1408  : name_(name),
1409  parameters_(parameters),
1410  random_(CpRandomSeed()),
1411  demon_profiler_(BuildDemonProfiler(this)),
1412  use_fast_local_search_(true),
1413  local_search_profiler_(BuildLocalSearchProfiler(this)) {
1414  Init();
1415 }
1416 
1417 Solver::Solver(const std::string& name)
1418  : name_(name),
1419  parameters_(DefaultSolverParameters()),
1420  random_(CpRandomSeed()),
1421  demon_profiler_(BuildDemonProfiler(this)),
1422  use_fast_local_search_(true),
1423  local_search_profiler_(BuildLocalSearchProfiler(this)) {
1424  Init();
1425 }
1426 
1427 void Solver::Init() {
1428  CheckSolverParameters(parameters_);
1429  queue_ = absl::make_unique<Queue>(this);
1430  trail_ = absl::make_unique<Trail>(parameters_.trail_block_size(),
1431  parameters_.compress_trail());
1432  state_ = OUTSIDE_SEARCH;
1433  branches_ = 0;
1434  fails_ = 0;
1435  decisions_ = 0;
1436  neighbors_ = 0;
1437  filtered_neighbors_ = 0;
1438  accepted_neighbors_ = 0;
1439  optimization_direction_ = NOT_SET;
1440  timer_ = absl::make_unique<ClockTimer>();
1441  searches_.assign(1, new Search(this, 0));
1442  fail_stamp_ = uint64_t{1};
1443  balancing_decision_ = absl::make_unique<BalancingDecision>();
1444  fail_intercept_ = nullptr;
1445  true_constraint_ = nullptr;
1446  false_constraint_ = nullptr;
1447  fail_decision_ = absl::make_unique<FailDecision>();
1448  constraint_index_ = 0;
1449  additional_constraint_index_ = 0;
1450  num_int_vars_ = 0;
1451  propagation_monitor_.reset(BuildTrace(this));
1452  local_search_monitor_.reset(BuildLocalSearchMonitorMaster(this));
1453  print_trace_ = nullptr;
1454  anonymous_variable_index_ = 0;
1455  should_fail_ = false;
1456 
1457  for (int i = 0; i < kNumPriorities; ++i) {
1458  demon_runs_[i] = 0;
1459  }
1460  searches_.push_back(new Search(this));
1461  PushSentinel(SOLVER_CTOR_SENTINEL);
1462  InitCachedIntConstants(); // to be called after the SENTINEL is set.
1463  InitCachedConstraint(); // Cache the true constraint.
1464  timer_->Restart();
1465  model_cache_.reset(BuildModelCache(this));
1466  AddPropagationMonitor(reinterpret_cast<PropagationMonitor*>(demon_profiler_));
1468  reinterpret_cast<LocalSearchMonitor*>(local_search_profiler_));
1469 }
1470 
1472  // solver destructor called with searches open.
1473  CHECK_EQ(2, searches_.size());
1474  BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
1475 
1476  StateInfo info;
1477  Solver::MarkerType finalType = PopState(&info);
1478  // Not popping a SENTINEL in Solver destructor.
1479  DCHECK_EQ(finalType, SENTINEL);
1480  // Not popping initial SENTINEL in Solver destructor.
1481  DCHECK_EQ(info.int_info, SOLVER_CTOR_SENTINEL);
1482  gtl::STLDeleteElements(&searches_);
1483  DeleteDemonProfiler(demon_profiler_);
1484  DeleteLocalSearchProfiler(local_search_profiler_);
1485 }
1486 
1487 std::string Solver::DebugString() const {
1488  std::string out = "Solver(name = \"" + name_ + "\", state = ";
1489  switch (state_) {
1490  case OUTSIDE_SEARCH:
1491  out += "OUTSIDE_SEARCH";
1492  break;
1493  case IN_ROOT_NODE:
1494  out += "IN_ROOT_NODE";
1495  break;
1496  case IN_SEARCH:
1497  out += "IN_SEARCH";
1498  break;
1499  case AT_SOLUTION:
1500  out += "AT_SOLUTION";
1501  break;
1502  case NO_MORE_SOLUTIONS:
1503  out += "NO_MORE_SOLUTIONS";
1504  break;
1505  case PROBLEM_INFEASIBLE:
1506  out += "PROBLEM_INFEASIBLE";
1507  break;
1508  }
1509  absl::StrAppendFormat(
1510  &out,
1511  ", branches = %d, fails = %d, decisions = %d, delayed demon runs = %d, "
1512  "var demon runs = %d, normal demon runs = %d, Run time = %d ms)",
1513  branches_, fails_, decisions_, demon_runs_[DELAYED_PRIORITY],
1514  demon_runs_[VAR_PRIORITY], demon_runs_[NORMAL_PRIORITY], wall_time());
1515  return out;
1516 }
1517 
1519 
1521  return absl::ToInt64Milliseconds(timer_->GetDuration());
1522 }
1523 
1524 absl::Time Solver::Now() const {
1525  return absl::FromUnixSeconds(0) + timer_->GetDuration();
1526 }
1527 
1528 int64 Solver::solutions() const { return TopLevelSearch()->solution_counter(); }
1529 
1531  return TopLevelSearch()->unchecked_solution_counter();
1532 }
1533 
1534 void Solver::IncrementUncheckedSolutionCounter() {
1535  TopLevelSearch()->IncrementUncheckedSolutionCounter();
1536 }
1537 
1538 bool Solver::IsUncheckedSolutionLimitReached() {
1539  return TopLevelSearch()->IsUncheckedSolutionLimitReached();
1540 }
1541 
1542 void Solver::TopPeriodicCheck() { TopLevelSearch()->PeriodicCheck(); }
1543 
1544 int Solver::TopProgressPercent() { return TopLevelSearch()->ProgressPercent(); }
1545 
1546 ConstraintSolverStatistics Solver::GetConstraintSolverStatistics() const {
1547  ConstraintSolverStatistics stats;
1548  stats.set_num_branches(branches());
1549  stats.set_num_failures(failures());
1550  stats.set_num_solutions(solutions());
1551  stats.set_bytes_used(MemoryUsage());
1552  stats.set_duration_seconds(absl::ToDoubleSeconds(timer_->GetDuration()));
1553  return stats;
1554 }
1555 
1557  StateInfo info;
1558  PushState(SIMPLE_MARKER, info);
1559 }
1560 
1562  StateInfo info;
1563  Solver::MarkerType t = PopState(&info);
1564  CHECK_EQ(SIMPLE_MARKER, t);
1565 }
1566 
1567 void Solver::PushState(Solver::MarkerType t, const StateInfo& info) {
1568  StateMarker* m = new StateMarker(t, info);
1569  if (t != REVERSIBLE_ACTION || info.int_info == 0) {
1570  m->rev_int_index_ = trail_->rev_ints_.size();
1571  m->rev_int64_index_ = trail_->rev_int64s_.size();
1572  m->rev_uint64_index_ = trail_->rev_uint64s_.size();
1573  m->rev_double_index_ = trail_->rev_doubles_.size();
1574  m->rev_ptr_index_ = trail_->rev_ptrs_.size();
1575  m->rev_boolvar_list_index_ = trail_->rev_boolvar_list_.size();
1576  m->rev_bools_index_ = trail_->rev_bools_.size();
1577  m->rev_int_memory_index_ = trail_->rev_int_memory_.size();
1578  m->rev_int64_memory_index_ = trail_->rev_int64_memory_.size();
1579  m->rev_double_memory_index_ = trail_->rev_double_memory_.size();
1580  m->rev_object_memory_index_ = trail_->rev_object_memory_.size();
1581  m->rev_object_array_memory_index_ = trail_->rev_object_array_memory_.size();
1582  m->rev_memory_index_ = trail_->rev_memory_.size();
1583  m->rev_memory_array_index_ = trail_->rev_memory_array_.size();
1584  }
1585  searches_.back()->marker_stack_.push_back(m);
1586  queue_->increase_stamp();
1587 }
1588 
1590  StateInfo info(std::move(a), fast);
1592 }
1593 
1595  CHECK(!searches_.back()->marker_stack_.empty())
1596  << "PopState() on an empty stack";
1597  CHECK(info != nullptr);
1598  StateMarker* const m = searches_.back()->marker_stack_.back();
1599  if (m->type_ != REVERSIBLE_ACTION || m->info_.int_info == 0) {
1600  trail_->BacktrackTo(m);
1601  }
1602  Solver::MarkerType t = m->type_;
1603  (*info) = m->info_;
1604  searches_.back()->marker_stack_.pop_back();
1605  delete m;
1606  queue_->increase_stamp();
1607  return t;
1608 }
1609 
1610 void Solver::check_alloc_state() {
1611  switch (state_) {
1612  case OUTSIDE_SEARCH:
1613  case IN_ROOT_NODE:
1614  case IN_SEARCH:
1615  case NO_MORE_SOLUTIONS:
1616  case PROBLEM_INFEASIBLE:
1617  break;
1618  case AT_SOLUTION:
1619  LOG(FATAL) << "allocating at a leaf node";
1620  default:
1621  LOG(FATAL) << "This switch was supposed to be exhaustive, but it is not!";
1622  }
1623 }
1624 
1625 void Solver::FreezeQueue() { queue_->Freeze(); }
1626 
1627 void Solver::UnfreezeQueue() { queue_->Unfreeze(); }
1628 
1629 void Solver::EnqueueVar(Demon* const d) { queue_->EnqueueVar(d); }
1630 
1631 void Solver::EnqueueDelayedDemon(Demon* const d) {
1632  queue_->EnqueueDelayedDemon(d);
1633 }
1634 
1635 void Solver::ExecuteAll(const SimpleRevFIFO<Demon*>& demons) {
1636  queue_->ExecuteAll(demons);
1637 }
1638 
1639 void Solver::EnqueueAll(const SimpleRevFIFO<Demon*>& demons) {
1640  queue_->EnqueueAll(demons);
1641 }
1642 
1643 uint64 Solver::stamp() const { return queue_->stamp(); }
1644 
1645 uint64 Solver::fail_stamp() const { return fail_stamp_; }
1646 
1647 void Solver::set_action_on_fail(Action a) {
1648  queue_->set_action_on_fail(std::move(a));
1649 }
1650 
1651 void Solver::set_variable_to_clean_on_fail(IntVar* v) {
1652  queue_->set_variable_to_clean_on_fail(v);
1653 }
1654 
1655 void Solver::reset_action_on_fail() { queue_->reset_action_on_fail(); }
1656 
1658  DCHECK(c != nullptr);
1659  if (c == true_constraint_) {
1660  return;
1661  }
1662  if (state_ == IN_SEARCH) {
1663  queue_->AddConstraint(c);
1664  } else if (state_ == IN_ROOT_NODE) {
1665  DCHECK_GE(constraint_index_, 0);
1666  DCHECK_LE(constraint_index_, constraints_list_.size());
1667  const int constraint_parent =
1668  constraint_index_ == constraints_list_.size()
1669  ? additional_constraints_parent_list_[additional_constraint_index_]
1670  : constraint_index_;
1671  additional_constraints_list_.push_back(c);
1672  additional_constraints_parent_list_.push_back(constraint_parent);
1673  } else {
1674  if (parameters_.print_added_constraints()) {
1675  LOG(INFO) << c->DebugString();
1676  }
1677  constraints_list_.push_back(c);
1678  }
1679 }
1680 
1682  IntVar* const target_var, IntExpr* const expr) {
1683  if (constraint != nullptr) {
1684  if (state_ != IN_SEARCH) {
1685  cast_constraints_.insert(constraint);
1686  cast_information_[target_var] =
1687  Solver::IntegerCastInfo(target_var, expr, constraint);
1688  }
1689  AddConstraint(constraint);
1690  }
1691 }
1692 
1693 void Solver::Accept(ModelVisitor* const visitor) const {
1694  visitor->BeginVisitModel(name_);
1695  ForAll(constraints_list_, &Constraint::Accept, visitor);
1696  visitor->EndVisitModel(name_);
1697 }
1698 
1699 void Solver::ProcessConstraints() {
1700  // Both constraints_list_ and additional_constraints_list_ are used in
1701  // a FIFO way.
1702  if (parameters_.print_model()) {
1703  ModelVisitor* const visitor = MakePrintModelVisitor();
1704  Accept(visitor);
1705  }
1706  if (parameters_.print_model_stats()) {
1707  ModelVisitor* const visitor = MakeStatisticsModelVisitor();
1708  Accept(visitor);
1709  }
1710 
1711  if (parameters_.disable_solve()) {
1712  LOG(INFO) << "Forcing early failure";
1713  Fail();
1714  }
1715 
1716  // Clear state before processing constraints.
1717  const int constraints_size = constraints_list_.size();
1718  additional_constraints_list_.clear();
1719  additional_constraints_parent_list_.clear();
1720 
1721  for (constraint_index_ = 0; constraint_index_ < constraints_size;
1722  ++constraint_index_) {
1723  Constraint* const constraint = constraints_list_[constraint_index_];
1724  propagation_monitor_->BeginConstraintInitialPropagation(constraint);
1725  constraint->PostAndPropagate();
1726  propagation_monitor_->EndConstraintInitialPropagation(constraint);
1727  }
1728  CHECK_EQ(constraints_list_.size(), constraints_size);
1729 
1730  // Process nested constraints added during the previous step.
1731  for (int additional_constraint_index_ = 0;
1732  additional_constraint_index_ < additional_constraints_list_.size();
1733  ++additional_constraint_index_) {
1734  Constraint* const nested =
1735  additional_constraints_list_[additional_constraint_index_];
1736  const int parent_index =
1737  additional_constraints_parent_list_[additional_constraint_index_];
1738  Constraint* const parent = constraints_list_[parent_index];
1739  propagation_monitor_->BeginNestedConstraintInitialPropagation(parent,
1740  nested);
1741  nested->PostAndPropagate();
1742  propagation_monitor_->EndNestedConstraintInitialPropagation(parent, nested);
1743  }
1744 }
1745 
1747  DCHECK_GT(SolveDepth(), 0);
1748  DCHECK(searches_.back() != nullptr);
1749  return searches_.back()->created_by_solve();
1750 }
1751 
1752 bool Solver::Solve(DecisionBuilder* const db, SearchMonitor* const m1) {
1753  std::vector<SearchMonitor*> monitors;
1754  monitors.push_back(m1);
1755  return Solve(db, monitors);
1756 }
1757 
1759  std::vector<SearchMonitor*> monitors;
1760  return Solve(db, monitors);
1761 }
1762 
1763 bool Solver::Solve(DecisionBuilder* const db, SearchMonitor* const m1,
1764  SearchMonitor* const m2) {
1765  std::vector<SearchMonitor*> monitors;
1766  monitors.push_back(m1);
1767  monitors.push_back(m2);
1768  return Solve(db, monitors);
1769 }
1770 
1771 bool Solver::Solve(DecisionBuilder* const db, SearchMonitor* const m1,
1772  SearchMonitor* const m2, SearchMonitor* const m3) {
1773  std::vector<SearchMonitor*> monitors;
1774  monitors.push_back(m1);
1775  monitors.push_back(m2);
1776  monitors.push_back(m3);
1777  return Solve(db, monitors);
1778 }
1779 
1780 bool Solver::Solve(DecisionBuilder* const db, SearchMonitor* const m1,
1781  SearchMonitor* const m2, SearchMonitor* const m3,
1782  SearchMonitor* const m4) {
1783  std::vector<SearchMonitor*> monitors;
1784  monitors.push_back(m1);
1785  monitors.push_back(m2);
1786  monitors.push_back(m3);
1787  monitors.push_back(m4);
1788  return Solve(db, monitors);
1789 }
1790 
1792  const std::vector<SearchMonitor*>& monitors) {
1793  NewSearch(db, monitors);
1794  searches_.back()->set_created_by_solve(true); // Overwrites default.
1795  NextSolution();
1796  const bool solution_found = searches_.back()->solution_counter() > 0;
1797  EndSearch();
1798  return solution_found;
1799 }
1800 
1802  std::vector<SearchMonitor*> monitors;
1803  monitors.push_back(m1);
1804  return NewSearch(db, monitors);
1805 }
1806 
1808  std::vector<SearchMonitor*> monitors;
1809  return NewSearch(db, monitors);
1810 }
1811 
1813  SearchMonitor* const m2) {
1814  std::vector<SearchMonitor*> monitors;
1815  monitors.push_back(m1);
1816  monitors.push_back(m2);
1817  return NewSearch(db, monitors);
1818 }
1819 
1821  SearchMonitor* const m2, SearchMonitor* const m3) {
1822  std::vector<SearchMonitor*> monitors;
1823  monitors.push_back(m1);
1824  monitors.push_back(m2);
1825  monitors.push_back(m3);
1826  return NewSearch(db, monitors);
1827 }
1828 
1830  SearchMonitor* const m2, SearchMonitor* const m3,
1831  SearchMonitor* const m4) {
1832  std::vector<SearchMonitor*> monitors;
1833  monitors.push_back(m1);
1834  monitors.push_back(m2);
1835  monitors.push_back(m3);
1836  monitors.push_back(m4);
1837  return NewSearch(db, monitors);
1838 }
1839 
1840 extern PropagationMonitor* BuildPrintTrace(Solver* const s);
1841 
1842 // Opens a new top level search.
1844  const std::vector<SearchMonitor*>& monitors) {
1845  // TODO(user) : reset statistics
1846 
1847  CHECK(db != nullptr);
1848  const bool nested = state_ == IN_SEARCH;
1849 
1850  if (state_ == IN_ROOT_NODE) {
1851  LOG(FATAL) << "Cannot start new searches here.";
1852  }
1853 
1854  Search* const search = nested ? new Search(this) : searches_.back();
1855  search->set_created_by_solve(false); // default behavior.
1856 
1857  // ----- jumps to correct state -----
1858 
1859  if (nested) {
1860  // Nested searches are created on demand, and deleted afterwards.
1861  DCHECK_GE(searches_.size(), 2);
1862  searches_.push_back(search);
1863  } else {
1864  // Top level search is persistent.
1865  // TODO(user): delete top level search after EndSearch().
1866  DCHECK_EQ(2, searches_.size());
1867  // TODO(user): Check if these two lines are still necessary.
1868  BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
1869  state_ = OUTSIDE_SEARCH;
1870  }
1871 
1872  // ----- manages all monitors -----
1873 
1874  // Always install the main propagation and local search monitors.
1875  propagation_monitor_->Install();
1876  if (demon_profiler_ != nullptr) {
1877  InstallDemonProfiler(demon_profiler_);
1878  }
1879  local_search_monitor_->Install();
1880  if (local_search_profiler_ != nullptr) {
1881  InstallLocalSearchProfiler(local_search_profiler_);
1882  }
1883 
1884  // Push monitors and enter search.
1885  for (SearchMonitor* const monitor : monitors) {
1886  if (monitor != nullptr) {
1887  monitor->Install();
1888  }
1889  }
1890  std::vector<SearchMonitor*> extras;
1891  db->AppendMonitors(this, &extras);
1892  for (SearchMonitor* const monitor : extras) {
1893  if (monitor != nullptr) {
1894  monitor->Install();
1895  }
1896  }
1897  // Install the print trace if needed.
1898  // The print_trace needs to be last to detect propagation from the objective.
1899  if (nested) {
1900  if (print_trace_ != nullptr) { // Was installed at the top level?
1901  print_trace_->Install(); // Propagates to nested search.
1902  }
1903  } else { // Top level search
1904  print_trace_ = nullptr; // Clears it first.
1905  if (parameters_.trace_propagation()) {
1906  print_trace_ = BuildPrintTrace(this);
1907  print_trace_->Install();
1908  } else if (parameters_.trace_search()) {
1909  // This is useful to trace the exact behavior of the search.
1910  // The '######## ' prefix is the same as the progagation trace.
1911  // Search trace is subsumed by propagation trace, thus only one
1912  // is necessary.
1913  SearchMonitor* const trace = MakeSearchTrace("######## ");
1914  trace->Install();
1915  }
1916  }
1917 
1918  // ----- enters search -----
1919 
1920  search->EnterSearch();
1921 
1922  // Push sentinel and set decision builder.
1923  PushSentinel(INITIAL_SEARCH_SENTINEL);
1924  search->set_decision_builder(db);
1925 }
1926 
1927 // Backtrack to the last open right branch in the search tree.
1928 // It returns true in case the search tree has been completely explored.
1929 bool Solver::BacktrackOneLevel(Decision** const fail_decision) {
1930  bool no_more_solutions = false;
1931  bool end_loop = false;
1932  while (!end_loop) {
1933  StateInfo info;
1934  Solver::MarkerType t = PopState(&info);
1935  switch (t) {
1936  case SENTINEL:
1937  CHECK_EQ(info.ptr_info, this) << "Wrong sentinel found";
1938  CHECK((info.int_info == ROOT_NODE_SENTINEL && SolveDepth() == 1) ||
1939  (info.int_info == INITIAL_SEARCH_SENTINEL && SolveDepth() > 1));
1940  searches_.back()->sentinel_pushed_--;
1941  no_more_solutions = true;
1942  end_loop = true;
1943  break;
1944  case SIMPLE_MARKER:
1945  LOG(ERROR) << "Simple markers should not be encountered during search";
1946  break;
1947  case CHOICE_POINT:
1948  if (info.int_info == 0) { // was left branch
1949  (*fail_decision) = reinterpret_cast<Decision*>(info.ptr_info);
1950  end_loop = true;
1951  searches_.back()->set_search_depth(info.depth);
1952  searches_.back()->set_search_left_depth(info.left_depth);
1953  }
1954  break;
1955  case REVERSIBLE_ACTION: {
1956  if (info.reversible_action != nullptr) {
1957  info.reversible_action(this);
1958  }
1959  break;
1960  }
1961  }
1962  }
1963  Search* const search = searches_.back();
1964  search->EndFail();
1965  fail_stamp_++;
1966  if (no_more_solutions) {
1967  search->NoMoreSolutions();
1968  }
1969  return no_more_solutions;
1970 }
1971 
1972 void Solver::PushSentinel(int magic_code) {
1973  StateInfo info(this, magic_code);
1974  PushState(SENTINEL, info);
1975  // We do not count the sentinel pushed in the ctor.
1976  if (magic_code != SOLVER_CTOR_SENTINEL) {
1977  searches_.back()->sentinel_pushed_++;
1978  }
1979  const int pushed = searches_.back()->sentinel_pushed_;
1980  DCHECK((magic_code == SOLVER_CTOR_SENTINEL) ||
1981  (magic_code == INITIAL_SEARCH_SENTINEL && pushed == 1) ||
1982  (magic_code == ROOT_NODE_SENTINEL && pushed == 2));
1983 }
1984 
1986  Search* const search = searches_.back();
1987  CHECK_NE(0, search->sentinel_pushed_);
1988  if (SolveDepth() == 1) { // top level.
1989  if (search->sentinel_pushed_ > 1) {
1990  BacktrackToSentinel(ROOT_NODE_SENTINEL);
1991  }
1992  CHECK_EQ(1, search->sentinel_pushed_);
1993  PushSentinel(ROOT_NODE_SENTINEL);
1994  state_ = IN_SEARCH;
1995  } else {
1996  CHECK_EQ(IN_SEARCH, state_);
1997  if (search->sentinel_pushed_ > 0) {
1998  BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
1999  }
2000  CHECK_EQ(0, search->sentinel_pushed_);
2001  PushSentinel(INITIAL_SEARCH_SENTINEL);
2002  }
2003 
2004  search->RestartSearch();
2005 }
2006 
2007 // Backtrack to the initial search sentinel.
2008 // Does not change the state, this should be done by the caller.
2009 void Solver::BacktrackToSentinel(int magic_code) {
2010  Search* const search = searches_.back();
2011  bool end_loop = search->sentinel_pushed_ == 0;
2012  while (!end_loop) {
2013  StateInfo info;
2014  Solver::MarkerType t = PopState(&info);
2015  switch (t) {
2016  case SENTINEL: {
2017  CHECK_EQ(info.ptr_info, this) << "Wrong sentinel found";
2018  CHECK_GE(--search->sentinel_pushed_, 0);
2019  search->set_search_depth(0);
2020  search->set_search_left_depth(0);
2021 
2022  if (info.int_info == magic_code) {
2023  end_loop = true;
2024  }
2025  break;
2026  }
2027  case SIMPLE_MARKER:
2028  break;
2029  case CHOICE_POINT:
2030  break;
2031  case REVERSIBLE_ACTION: {
2032  info.reversible_action(this);
2033  break;
2034  }
2035  }
2036  }
2037  fail_stamp_++;
2038 }
2039 
2040 // Closes the current search without backtrack.
2041 void Solver::JumpToSentinelWhenNested() {
2042  CHECK_GT(SolveDepth(), 1) << "calling JumpToSentinel from top level";
2043  Search* c = searches_.back();
2044  Search* p = ParentSearch();
2045  bool found = false;
2046  while (!c->marker_stack_.empty()) {
2047  StateMarker* const m = c->marker_stack_.back();
2048  if (m->type_ == REVERSIBLE_ACTION) {
2049  p->marker_stack_.push_back(m);
2050  } else {
2051  if (m->type_ == SENTINEL) {
2052  CHECK_EQ(c->marker_stack_.size(), 1) << "Sentinel found too early";
2053  found = true;
2054  }
2055  delete m;
2056  }
2057  c->marker_stack_.pop_back();
2058  }
2059  c->set_search_depth(0);
2060  c->set_search_left_depth(0);
2061  CHECK_EQ(found, true) << "Sentinel not found";
2062 }
2063 
2064 namespace {
2065 class ReverseDecision : public Decision {
2066  public:
2067  explicit ReverseDecision(Decision* const d) : decision_(d) {
2068  CHECK(d != nullptr);
2069  }
2070  ~ReverseDecision() override {}
2071 
2072  void Apply(Solver* const s) override { decision_->Refute(s); }
2073 
2074  void Refute(Solver* const s) override { decision_->Apply(s); }
2075 
2076  void Accept(DecisionVisitor* const visitor) const override {
2077  decision_->Accept(visitor);
2078  }
2079 
2080  std::string DebugString() const override {
2081  std::string str = "Reverse(";
2082  str += decision_->DebugString();
2083  str += ")";
2084  return str;
2085  }
2086 
2087  private:
2088  Decision* const decision_;
2089 };
2090 } // namespace
2091 
2092 // Search for the next solution in the search tree.
2094  Search* const search = searches_.back();
2095  Decision* fd = nullptr;
2096  const int solve_depth = SolveDepth();
2097  const bool top_level = solve_depth <= 1;
2098 
2099  if (solve_depth == 0 && !search->decision_builder()) {
2100  LOG(WARNING) << "NextSolution() called without a NewSearch before";
2101  return false;
2102  }
2103 
2104  if (top_level) { // Manage top level state.
2105  switch (state_) {
2106  case PROBLEM_INFEASIBLE:
2107  return false;
2108  case NO_MORE_SOLUTIONS:
2109  return false;
2110  case AT_SOLUTION: {
2111  if (BacktrackOneLevel(&fd)) { // No more solutions.
2112  state_ = NO_MORE_SOLUTIONS;
2113  return false;
2114  }
2115  state_ = IN_SEARCH;
2116  break;
2117  }
2118  case OUTSIDE_SEARCH: {
2119  state_ = IN_ROOT_NODE;
2120  search->BeginInitialPropagation();
2121  CP_TRY(search) {
2122  ProcessConstraints();
2123  search->EndInitialPropagation();
2124  PushSentinel(ROOT_NODE_SENTINEL);
2125  state_ = IN_SEARCH;
2126  search->ClearBuffer();
2127  }
2128  CP_ON_FAIL {
2129  queue_->AfterFailure();
2130  BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2131  state_ = PROBLEM_INFEASIBLE;
2132  return false;
2133  }
2134  break;
2135  }
2136  case IN_SEARCH: // Usually after a RestartSearch
2137  break;
2138  case IN_ROOT_NODE:
2139  LOG(FATAL) << "Should not happen";
2140  break;
2141  }
2142  }
2143 
2144  volatile bool finish = false;
2145  volatile bool result = false;
2146  DecisionBuilder* const db = search->decision_builder();
2147 
2148  while (!finish) {
2149  CP_TRY(search) {
2150  if (fd != nullptr) {
2151  StateInfo i1(fd, 1, search->search_depth(),
2152  search->left_search_depth()); // 1 for right branch
2153  PushState(CHOICE_POINT, i1);
2154  search->RefuteDecision(fd);
2155  branches_++;
2156  fd->Refute(this);
2157  // Check the fail state that could have been set in the python/java/C#
2158  // layer.
2159  CheckFail();
2160  search->AfterDecision(fd, false);
2161  search->RightMove();
2162  fd = nullptr;
2163  }
2164  Decision* d = nullptr;
2165  for (;;) {
2166  search->BeginNextDecision(db);
2167  d = db->Next(this);
2168  search->EndNextDecision(db, d);
2169  if (d == fail_decision_.get()) {
2170  Fail(); // fail now instead of after 2 branches.
2171  }
2172  if (d != nullptr) {
2173  DecisionModification modification = search->ModifyDecision();
2174  switch (modification) {
2175  case SWITCH_BRANCHES: {
2176  d = RevAlloc(new ReverseDecision(d));
2177  // We reverse the decision and fall through the normal code.
2178  ABSL_FALLTHROUGH_INTENDED;
2179  }
2180  case NO_CHANGE: {
2181  decisions_++;
2182  StateInfo i2(d, 0, search->search_depth(),
2183  search->left_search_depth()); // 0 for left branch
2184  PushState(CHOICE_POINT, i2);
2185  search->ApplyDecision(d);
2186  branches_++;
2187  d->Apply(this);
2188  CheckFail();
2189  search->AfterDecision(d, true);
2190  search->LeftMove();
2191  break;
2192  }
2193  case KEEP_LEFT: {
2194  search->ApplyDecision(d);
2195  d->Apply(this);
2196  CheckFail();
2197  search->AfterDecision(d, true);
2198  break;
2199  }
2200  case KEEP_RIGHT: {
2201  search->RefuteDecision(d);
2202  d->Refute(this);
2203  CheckFail();
2204  search->AfterDecision(d, false);
2205  break;
2206  }
2207  case KILL_BOTH: {
2208  Fail();
2209  }
2210  }
2211  } else {
2212  break;
2213  }
2214  }
2215  if (search->AcceptSolution()) {
2216  search->IncrementSolutionCounter();
2217  if (!search->AtSolution() || !CurrentlyInSolve()) {
2218  result = true;
2219  finish = true;
2220  } else {
2221  Fail();
2222  }
2223  } else {
2224  Fail();
2225  }
2226  }
2227  CP_ON_FAIL {
2228  queue_->AfterFailure();
2229  if (search->should_finish()) {
2230  fd = nullptr;
2231  BacktrackToSentinel(top_level ? ROOT_NODE_SENTINEL
2232  : INITIAL_SEARCH_SENTINEL);
2233  result = false;
2234  finish = true;
2235  search->set_should_finish(false);
2236  search->set_should_restart(false);
2237  // We do not need to push back the sentinel as we are exiting anyway.
2238  } else if (search->should_restart()) {
2239  fd = nullptr;
2240  BacktrackToSentinel(top_level ? ROOT_NODE_SENTINEL
2241  : INITIAL_SEARCH_SENTINEL);
2242  search->set_should_finish(false);
2243  search->set_should_restart(false);
2244  PushSentinel(top_level ? ROOT_NODE_SENTINEL : INITIAL_SEARCH_SENTINEL);
2245  search->RestartSearch();
2246  } else {
2247  if (BacktrackOneLevel(&fd)) { // no more solutions.
2248  result = false;
2249  finish = true;
2250  }
2251  }
2252  }
2253  }
2254  if (result) {
2255  search->ClearBuffer();
2256  }
2257  if (top_level) { // Manage state after NextSolution().
2258  state_ = (result ? AT_SOLUTION : NO_MORE_SOLUTIONS);
2259  }
2260  return result;
2261 }
2262 
2264  Search* const search = searches_.back();
2265  if (search->backtrack_at_the_end_of_the_search()) {
2266  BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2267  } else {
2268  CHECK_GT(searches_.size(), 2);
2269  if (search->sentinel_pushed_ > 0) {
2270  JumpToSentinelWhenNested();
2271  }
2272  }
2273  search->ExitSearch();
2274  search->Clear();
2275  if (2 == searches_.size()) { // Ending top level search.
2276  // Restores the state.
2277  state_ = OUTSIDE_SEARCH;
2278  // Checks if we want to export the profile info.
2279  if (!parameters_.profile_file().empty()) {
2280  const std::string& file_name = parameters_.profile_file();
2281  LOG(INFO) << "Exporting profile to " << file_name;
2282  ExportProfilingOverview(file_name);
2283  }
2284  if (parameters_.print_local_search_profile()) {
2285  LOG(INFO) << LocalSearchProfile();
2286  }
2287  } else { // We clean the nested Search.
2288  delete search;
2289  searches_.pop_back();
2290  }
2291 }
2292 
2293 bool Solver::CheckAssignment(Assignment* const solution) {
2294  CHECK(solution);
2295  if (state_ == IN_SEARCH || state_ == IN_ROOT_NODE) {
2296  LOG(FATAL) << "CheckAssignment is only available at the top level.";
2297  }
2298  // Check state and go to OUTSIDE_SEARCH.
2299  Search* const search = searches_.back();
2300  search->set_created_by_solve(false); // default behavior.
2301 
2302  BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2303  state_ = OUTSIDE_SEARCH;
2304 
2305  // Push monitors and enter search.
2306  search->EnterSearch();
2307 
2308  // Push sentinel and set decision builder.
2309  DCHECK_EQ(0, SolveDepth());
2310  DCHECK_EQ(2, searches_.size());
2311  PushSentinel(INITIAL_SEARCH_SENTINEL);
2312  search->BeginInitialPropagation();
2313  CP_TRY(search) {
2314  state_ = IN_ROOT_NODE;
2315  DecisionBuilder* const restore = MakeRestoreAssignment(solution);
2316  restore->Next(this);
2317  ProcessConstraints();
2318  search->EndInitialPropagation();
2319  BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2320  search->ClearBuffer();
2321  state_ = OUTSIDE_SEARCH;
2322  return true;
2323  }
2324  CP_ON_FAIL {
2325  const int index =
2326  constraint_index_ < constraints_list_.size()
2327  ? constraint_index_
2328  : additional_constraints_parent_list_[additional_constraint_index_];
2329  Constraint* const ct = constraints_list_[index];
2330  if (ct->name().empty()) {
2331  LOG(INFO) << "Failing constraint = " << ct->DebugString();
2332  } else {
2333  LOG(INFO) << "Failing constraint = " << ct->name() << ":"
2334  << ct->DebugString();
2335  }
2336  queue_->AfterFailure();
2337  BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2338  state_ = PROBLEM_INFEASIBLE;
2339  return false;
2340  }
2341 }
2342 
2343 namespace {
2344 class AddConstraintDecisionBuilder : public DecisionBuilder {
2345  public:
2346  explicit AddConstraintDecisionBuilder(Constraint* const ct)
2347  : constraint_(ct) {
2348  CHECK(ct != nullptr);
2349  }
2350 
2351  ~AddConstraintDecisionBuilder() override {}
2352 
2353  Decision* Next(Solver* const solver) override {
2354  solver->AddConstraint(constraint_);
2355  return nullptr;
2356  }
2357 
2358  std::string DebugString() const override {
2359  return absl::StrFormat("AddConstraintDecisionBuilder(%s)",
2360  constraint_->DebugString());
2361  }
2362 
2363  private:
2364  Constraint* const constraint_;
2365 };
2366 } // namespace
2367 
2369  return RevAlloc(new AddConstraintDecisionBuilder(ct));
2370 }
2371 
2373  return Solve(MakeConstraintAdder(ct));
2374 }
2375 
2377  SearchMonitor* const m1) {
2378  std::vector<SearchMonitor*> monitors;
2379  monitors.push_back(m1);
2380  return SolveAndCommit(db, monitors);
2381 }
2382 
2384  std::vector<SearchMonitor*> monitors;
2385  return SolveAndCommit(db, monitors);
2386 }
2387 
2389  SearchMonitor* const m2) {
2390  std::vector<SearchMonitor*> monitors;
2391  monitors.push_back(m1);
2392  monitors.push_back(m2);
2393  return SolveAndCommit(db, monitors);
2394 }
2395 
2397  SearchMonitor* const m2, SearchMonitor* const m3) {
2398  std::vector<SearchMonitor*> monitors;
2399  monitors.push_back(m1);
2400  monitors.push_back(m2);
2401  monitors.push_back(m3);
2402  return SolveAndCommit(db, monitors);
2403 }
2404 
2406  const std::vector<SearchMonitor*>& monitors) {
2407  NewSearch(db, monitors);
2408  searches_.back()->set_created_by_solve(true); // Overwrites default.
2409  searches_.back()->set_backtrack_at_the_end_of_the_search(false);
2410  NextSolution();
2411  const bool solution_found = searches_.back()->solution_counter() > 0;
2412  EndSearch();
2413  return solution_found;
2414 }
2415 
2417  if (fail_intercept_) {
2418  fail_intercept_();
2419  return;
2420  }
2422  fails_++;
2423  searches_.back()->BeginFail();
2424  searches_.back()->JumpBack();
2425 }
2426 
2428  searches_.back()->set_should_finish(true);
2429 }
2430 
2432  searches_.back()->set_should_restart(true);
2433 }
2434 
2435 // ----- Cast Expression -----
2436 
2438  const IntegerCastInfo* const cast_info =
2439  gtl::FindOrNull(cast_information_, var);
2440  if (cast_info != nullptr) {
2441  return cast_info->expression;
2442  }
2443  return nullptr;
2444 }
2445 
2446 // --- Propagation object names ---
2447 
2448 std::string Solver::GetName(const PropagationBaseObject* object) {
2449  const std::string* name = gtl::FindOrNull(propagation_object_names_, object);
2450  if (name != nullptr) {
2451  return *name;
2452  }
2453  const IntegerCastInfo* const cast_info =
2454  gtl::FindOrNull(cast_information_, object);
2455  if (cast_info != nullptr && cast_info->expression != nullptr) {
2456  if (cast_info->expression->HasName()) {
2457  return absl::StrFormat("Var<%s>", cast_info->expression->name());
2458  } else if (parameters_.name_cast_variables()) {
2459  return absl::StrFormat("Var<%s>", cast_info->expression->DebugString());
2460  } else {
2461  const std::string new_name =
2462  absl::StrFormat("CastVar<%d>", anonymous_variable_index_++);
2463  propagation_object_names_[object] = new_name;
2464  return new_name;
2465  }
2466  }
2467  const std::string base_name = object->BaseName();
2468  if (parameters_.name_all_variables() && !base_name.empty()) {
2469  const std::string new_name =
2470  absl::StrFormat("%s_%d", base_name, anonymous_variable_index_++);
2471  propagation_object_names_[object] = new_name;
2472  return new_name;
2473  }
2474  return empty_name_;
2475 }
2476 
2477 void Solver::SetName(const PropagationBaseObject* object,
2478  const std::string& name) {
2479  if (parameters_.store_names() &&
2480  GetName(object) != name) { // in particular if name.empty()
2481  propagation_object_names_[object] = name;
2482  }
2483 }
2484 
2485 bool Solver::HasName(const PropagationBaseObject* const object) const {
2486  return gtl::ContainsKey(propagation_object_names_,
2487  const_cast<PropagationBaseObject*>(object)) ||
2488  (!object->BaseName().empty() && parameters_.name_all_variables());
2489 }
2490 
2491 // ------------------ Useful Operators ------------------
2492 
2493 std::ostream& operator<<(std::ostream& out, const Solver* const s) {
2494  out << s->DebugString();
2495  return out;
2496 }
2497 
2498 std::ostream& operator<<(std::ostream& out, const BaseObject* const o) {
2499  out << o->DebugString();
2500  return out;
2501 }
2502 
2503 // ---------- PropagationBaseObject ---------
2504 
2505 std::string PropagationBaseObject::name() const {
2506  return solver_->GetName(this);
2507 }
2508 
2509 void PropagationBaseObject::set_name(const std::string& name) {
2510  solver_->SetName(this, name);
2511 }
2512 
2513 bool PropagationBaseObject::HasName() const { return solver_->HasName(this); }
2514 
2515 std::string PropagationBaseObject::BaseName() const { return ""; }
2516 
2518  solver_->ExecuteAll(demons);
2519 }
2520 
2522  solver_->EnqueueAll(demons);
2523 }
2524 
2525 // ---------- Decision Builder ----------
2526 
2527 std::string DecisionBuilder::DebugString() const { return "DecisionBuilder"; }
2528 
2530  Solver* const solver, std::vector<SearchMonitor*>* const extras) {}
2531 
2532 void DecisionBuilder::Accept(ModelVisitor* const visitor) const {}
2533 
2534 // ---------- Decision and DecisionVisitor ----------
2535 
2536 void Decision::Accept(DecisionVisitor* const visitor) const {
2537  visitor->VisitUnknownDecision();
2538 }
2539 
2542  bool lower) {}
2545  int64 est) {}
2547  int64 est) {}
2549  int index) {}
2550 
2552  int index) {}
2553 
2554 // ---------- ModelVisitor ----------
2555 
2556 // Tags for constraints, arguments, extensions.
2557 
2558 const char ModelVisitor::kAbs[] = "Abs";
2559 const char ModelVisitor::kAbsEqual[] = "AbsEqual";
2560 const char ModelVisitor::kAllDifferent[] = "AllDifferent";
2561 const char ModelVisitor::kAllowedAssignments[] = "AllowedAssignments";
2562 const char ModelVisitor::kAtMost[] = "AtMost";
2563 const char ModelVisitor::kBetween[] = "Between";
2564 const char ModelVisitor::kConditionalExpr[] = "ConditionalExpr";
2565 const char ModelVisitor::kCircuit[] = "Circuit";
2566 const char ModelVisitor::kConvexPiecewise[] = "ConvexPiecewise";
2567 const char ModelVisitor::kCountEqual[] = "CountEqual";
2568 const char ModelVisitor::kCover[] = "Cover";
2569 const char ModelVisitor::kCumulative[] = "Cumulative";
2570 const char ModelVisitor::kDeviation[] = "Deviation";
2571 const char ModelVisitor::kDifference[] = "Difference";
2572 const char ModelVisitor::kDisjunctive[] = "Disjunctive";
2573 const char ModelVisitor::kDistribute[] = "Distribute";
2574 const char ModelVisitor::kDivide[] = "Divide";
2575 const char ModelVisitor::kDurationExpr[] = "DurationExpression";
2576 const char ModelVisitor::kElement[] = "Element";
2577 const char ModelVisitor::kElementEqual[] = "ElementEqual";
2578 const char ModelVisitor::kEndExpr[] = "EndExpression";
2579 const char ModelVisitor::kEquality[] = "Equal";
2580 const char ModelVisitor::kFalseConstraint[] = "FalseConstraint";
2581 const char ModelVisitor::kGlobalCardinality[] = "GlobalCardinality";
2582 const char ModelVisitor::kGreater[] = "Greater";
2583 const char ModelVisitor::kGreaterOrEqual[] = "GreaterOrEqual";
2584 const char ModelVisitor::kIndexOf[] = "IndexOf";
2585 const char ModelVisitor::kIntegerVariable[] = "IntegerVariable";
2586 const char ModelVisitor::kIntervalBinaryRelation[] = "IntervalBinaryRelation";
2587 const char ModelVisitor::kIntervalDisjunction[] = "IntervalDisjunction";
2588 const char ModelVisitor::kIntervalUnaryRelation[] = "IntervalUnaryRelation";
2589 const char ModelVisitor::kIntervalVariable[] = "IntervalVariable";
2590 const char ModelVisitor::kInversePermutation[] = "InversePermutation";
2591 const char ModelVisitor::kIsBetween[] = "IsBetween;";
2592 const char ModelVisitor::kIsDifferent[] = "IsDifferent";
2593 const char ModelVisitor::kIsEqual[] = "IsEqual";
2594 const char ModelVisitor::kIsGreater[] = "IsGreater";
2595 const char ModelVisitor::kIsGreaterOrEqual[] = "IsGreaterOrEqual";
2596 const char ModelVisitor::kIsLess[] = "IsLess";
2597 const char ModelVisitor::kIsLessOrEqual[] = "IsLessOrEqual";
2598 const char ModelVisitor::kIsMember[] = "IsMember;";
2599 const char ModelVisitor::kLess[] = "Less";
2600 const char ModelVisitor::kLessOrEqual[] = "LessOrEqual";
2601 const char ModelVisitor::kLexLess[] = "LexLess";
2602 const char ModelVisitor::kLinkExprVar[] = "CastExpressionIntoVariable";
2603 const char ModelVisitor::kMapDomain[] = "MapDomain";
2604 const char ModelVisitor::kMax[] = "Max";
2605 const char ModelVisitor::kMaxEqual[] = "MaxEqual";
2606 const char ModelVisitor::kMember[] = "Member";
2607 const char ModelVisitor::kMin[] = "Min";
2608 const char ModelVisitor::kMinEqual[] = "MinEqual";
2609 const char ModelVisitor::kModulo[] = "Modulo";
2610 const char ModelVisitor::kNoCycle[] = "NoCycle";
2611 const char ModelVisitor::kNonEqual[] = "NonEqual";
2612 const char ModelVisitor::kNotBetween[] = "NotBetween";
2613 const char ModelVisitor::kNotMember[] = "NotMember";
2614 const char ModelVisitor::kNullIntersect[] = "NullIntersect";
2615 const char ModelVisitor::kOpposite[] = "Opposite";
2616 const char ModelVisitor::kPack[] = "Pack";
2617 const char ModelVisitor::kPathCumul[] = "PathCumul";
2618 const char ModelVisitor::kDelayedPathCumul[] = "DelayedPathCumul";
2619 const char ModelVisitor::kPerformedExpr[] = "PerformedExpression";
2620 const char ModelVisitor::kPower[] = "Power";
2621 const char ModelVisitor::kProduct[] = "Product";
2622 const char ModelVisitor::kScalProd[] = "ScalarProduct";
2623 const char ModelVisitor::kScalProdEqual[] = "ScalarProductEqual";
2625  "ScalarProductGreaterOrEqual";
2626 const char ModelVisitor::kScalProdLessOrEqual[] = "ScalarProductLessOrEqual";
2627 const char ModelVisitor::kSemiContinuous[] = "SemiContinuous";
2628 const char ModelVisitor::kSequenceVariable[] = "SequenceVariable";
2629 const char ModelVisitor::kSortingConstraint[] = "SortingConstraint";
2630 const char ModelVisitor::kSquare[] = "Square";
2631 const char ModelVisitor::kStartExpr[] = "StartExpression";
2632 const char ModelVisitor::kSum[] = "Sum";
2633 const char ModelVisitor::kSumEqual[] = "SumEqual";
2634 const char ModelVisitor::kSumGreaterOrEqual[] = "SumGreaterOrEqual";
2635 const char ModelVisitor::kSumLessOrEqual[] = "SumLessOrEqual";
2636 const char ModelVisitor::kTransition[] = "Transition";
2637 const char ModelVisitor::kTrace[] = "Trace";
2638 const char ModelVisitor::kTrueConstraint[] = "TrueConstraint";
2639 const char ModelVisitor::kVarBoundWatcher[] = "VarBoundWatcher";
2640 const char ModelVisitor::kVarValueWatcher[] = "VarValueWatcher";
2641 
2642 const char ModelVisitor::kCountAssignedItemsExtension[] = "CountAssignedItems";
2643 const char ModelVisitor::kCountUsedBinsExtension[] = "CountUsedBins";
2644 const char ModelVisitor::kInt64ToBoolExtension[] = "Int64ToBoolFunction";
2645 const char ModelVisitor::kInt64ToInt64Extension[] = "Int64ToInt64Function";
2646 const char ModelVisitor::kObjectiveExtension[] = "Objective";
2647 const char ModelVisitor::kSearchLimitExtension[] = "SearchLimit";
2648 const char ModelVisitor::kUsageEqualVariableExtension[] = "UsageEqualVariable";
2649 
2650 const char ModelVisitor::kUsageLessConstantExtension[] = "UsageLessConstant";
2651 const char ModelVisitor::kVariableGroupExtension[] = "VariableGroup";
2653  "VariableUsageLessConstant";
2655  "WeightedSumOfAssignedEqualVariable";
2656 
2657 const char ModelVisitor::kActiveArgument[] = "active";
2658 const char ModelVisitor::kAssumePathsArgument[] = "assume_paths";
2659 const char ModelVisitor::kBranchesLimitArgument[] = "branches_limit";
2660 const char ModelVisitor::kCapacityArgument[] = "capacity";
2661 const char ModelVisitor::kCardsArgument[] = "cardinalities";
2662 const char ModelVisitor::kCoefficientsArgument[] = "coefficients";
2663 const char ModelVisitor::kCountArgument[] = "count";
2664 const char ModelVisitor::kCumulativeArgument[] = "cumulative";
2665 const char ModelVisitor::kCumulsArgument[] = "cumuls";
2666 const char ModelVisitor::kDemandsArgument[] = "demands";
2667 const char ModelVisitor::kDurationMinArgument[] = "duration_min";
2668 const char ModelVisitor::kDurationMaxArgument[] = "duration_max";
2669 const char ModelVisitor::kEarlyCostArgument[] = "early_cost";
2670 const char ModelVisitor::kEarlyDateArgument[] = "early_date";
2671 const char ModelVisitor::kEndMinArgument[] = "end_min";
2672 const char ModelVisitor::kEndMaxArgument[] = "end_max";
2673 const char ModelVisitor::kEndsArgument[] = "ends";
2674 const char ModelVisitor::kExpressionArgument[] = "expression";
2675 const char ModelVisitor::kFailuresLimitArgument[] = "failures_limit";
2676 const char ModelVisitor::kFinalStatesArgument[] = "final_states";
2677 const char ModelVisitor::kFixedChargeArgument[] = "fixed_charge";
2678 const char ModelVisitor::kIndex2Argument[] = "index2";
2679 const char ModelVisitor::kIndexArgument[] = "index";
2680 const char ModelVisitor::kInitialState[] = "initial_state";
2681 const char ModelVisitor::kIntervalArgument[] = "interval";
2682 const char ModelVisitor::kIntervalsArgument[] = "intervals";
2683 const char ModelVisitor::kLateCostArgument[] = "late_cost";
2684 const char ModelVisitor::kLateDateArgument[] = "late_date";
2685 const char ModelVisitor::kLeftArgument[] = "left";
2686 const char ModelVisitor::kMaxArgument[] = "max_value";
2687 const char ModelVisitor::kMaximizeArgument[] = "maximize";
2688 const char ModelVisitor::kMinArgument[] = "min_value";
2689 const char ModelVisitor::kModuloArgument[] = "modulo";
2690 const char ModelVisitor::kNextsArgument[] = "nexts";
2691 const char ModelVisitor::kOptionalArgument[] = "optional";
2692 const char ModelVisitor::kPartialArgument[] = "partial";
2693 const char ModelVisitor::kPositionXArgument[] = "position_x";
2694 const char ModelVisitor::kPositionYArgument[] = "position_y";
2695 const char ModelVisitor::kRangeArgument[] = "range";
2696 const char ModelVisitor::kRelationArgument[] = "relation";
2697 const char ModelVisitor::kRightArgument[] = "right";
2698 const char ModelVisitor::kSequenceArgument[] = "sequence";
2699 const char ModelVisitor::kSequencesArgument[] = "sequences";
2700 const char ModelVisitor::kSmartTimeCheckArgument[] = "smart_time_check";
2701 const char ModelVisitor::kSizeArgument[] = "size";
2702 const char ModelVisitor::kSizeXArgument[] = "size_x";
2703 const char ModelVisitor::kSizeYArgument[] = "size_y";
2704 const char ModelVisitor::kSolutionLimitArgument[] = "solutions_limit";
2705 const char ModelVisitor::kStartMinArgument[] = "start_min";
2706 const char ModelVisitor::kStartMaxArgument[] = "start_max";
2707 const char ModelVisitor::kStartsArgument[] = "starts";
2708 const char ModelVisitor::kStepArgument[] = "step";
2709 const char ModelVisitor::kTargetArgument[] = "target_variable";
2710 const char ModelVisitor::kTimeLimitArgument[] = "time_limit";
2711 const char ModelVisitor::kTransitsArgument[] = "transits";
2712 const char ModelVisitor::kTuplesArgument[] = "tuples";
2713 const char ModelVisitor::kValueArgument[] = "value";
2714 const char ModelVisitor::kValuesArgument[] = "values";
2715 const char ModelVisitor::kVarsArgument[] = "variables";
2716 const char ModelVisitor::kEvaluatorArgument[] = "evaluator";
2717 
2718 const char ModelVisitor::kVariableArgument[] = "variable";
2719 
2720 const char ModelVisitor::kMirrorOperation[] = "mirror";
2721 const char ModelVisitor::kRelaxedMaxOperation[] = "relaxed_max";
2722 const char ModelVisitor::kRelaxedMinOperation[] = "relaxed_min";
2723 const char ModelVisitor::kSumOperation[] = "sum";
2724 const char ModelVisitor::kDifferenceOperation[] = "difference";
2725 const char ModelVisitor::kProductOperation[] = "product";
2726 const char ModelVisitor::kStartSyncOnStartOperation[] = "start_synced_on_start";
2727 const char ModelVisitor::kStartSyncOnEndOperation[] = "start_synced_on_end";
2728 const char ModelVisitor::kTraceOperation[] = "trace";
2729 
2730 // Methods
2731 
2733 
2734 void ModelVisitor::BeginVisitModel(const std::string& type_name) {}
2735 void ModelVisitor::EndVisitModel(const std::string& type_name) {}
2736 
2737 void ModelVisitor::BeginVisitConstraint(const std::string& type_name,
2738  const Constraint* const constraint) {}
2739 void ModelVisitor::EndVisitConstraint(const std::string& type_name,
2740  const Constraint* const constraint) {}
2741 
2742 void ModelVisitor::BeginVisitExtension(const std::string& type) {}
2743 void ModelVisitor::EndVisitExtension(const std::string& type) {}
2744 
2745 void ModelVisitor::BeginVisitIntegerExpression(const std::string& type_name,
2746  const IntExpr* const expr) {}
2747 void ModelVisitor::EndVisitIntegerExpression(const std::string& type_name,
2748  const IntExpr* const expr) {}
2749 
2750 void ModelVisitor::VisitIntegerVariable(const IntVar* const variable,
2751  IntExpr* const delegate) {
2752  if (delegate != nullptr) {
2753  delegate->Accept(this);
2754  }
2755 }
2756 
2757 void ModelVisitor::VisitIntegerVariable(const IntVar* const variable,
2758  const std::string& operation,
2759  int64 value, IntVar* const delegate) {
2760  if (delegate != nullptr) {
2761  delegate->Accept(this);
2762  }
2763 }
2764 
2766  const std::string& operation,
2767  int64 value,
2768  IntervalVar* const delegate) {
2769  if (delegate != nullptr) {
2770  delegate->Accept(this);
2771  }
2772 }
2773 
2775  for (int i = 0; i < variable->size(); ++i) {
2776  variable->Interval(i)->Accept(this);
2777  }
2778 }
2779 
2780 void ModelVisitor::VisitIntegerArgument(const std::string& arg_name,
2781  int64 value) {}
2782 
2783 void ModelVisitor::VisitIntegerArrayArgument(const std::string& arg_name,
2784  const std::vector<int64>& values) {
2785 }
2786 
2787 void ModelVisitor::VisitIntegerMatrixArgument(const std::string& arg_name,
2788  const IntTupleSet& tuples) {}
2789 
2790 void ModelVisitor::VisitIntegerExpressionArgument(const std::string& arg_name,
2791  IntExpr* const argument) {
2792  argument->Accept(this);
2793 }
2794 
2796  const std::string& arg_name, const Solver::Int64ToIntVar& arguments) {}
2797 
2799  const std::string& arg_name, const std::vector<IntVar*>& arguments) {
2800  ForAll(arguments, &IntVar::Accept, this);
2801 }
2802 
2803 void ModelVisitor::VisitIntervalArgument(const std::string& arg_name,
2804  IntervalVar* const argument) {
2805  argument->Accept(this);
2806 }
2807 
2809  const std::string& arg_name, const std::vector<IntervalVar*>& arguments) {
2810  ForAll(arguments, &IntervalVar::Accept, this);
2811 }
2812 
2813 void ModelVisitor::VisitSequenceArgument(const std::string& arg_name,
2814  SequenceVar* const argument) {
2815  argument->Accept(this);
2816 }
2817 
2819  const std::string& arg_name, const std::vector<SequenceVar*>& arguments) {
2820  ForAll(arguments, &SequenceVar::Accept, this);
2821 }
2822 
2823 // ----- Helpers -----
2824 
2826  int64 index_min, int64 index_max) {
2827  if (filter != nullptr) {
2828  std::vector<int64> cached_results;
2829  for (int i = index_min; i <= index_max; ++i) {
2830  cached_results.push_back(filter(i));
2831  }
2833  VisitIntegerArgument(kMinArgument, index_min);
2834  VisitIntegerArgument(kMaxArgument, index_max);
2835  VisitIntegerArrayArgument(kValuesArgument, cached_results);
2837  }
2838 }
2839 
2841  const Solver::IndexEvaluator1& eval, int64 index_min, int64 index_max) {
2842  CHECK(eval != nullptr);
2843  std::vector<int64> cached_results;
2844  for (int i = index_min; i <= index_max; ++i) {
2845  cached_results.push_back(eval(i));
2846  }
2848  VisitIntegerArgument(kMinArgument, index_min);
2849  VisitIntegerArgument(kMaxArgument, index_max);
2850  VisitIntegerArrayArgument(kValuesArgument, cached_results);
2852 }
2853 
2855  const std::string& arg_name,
2856  int64 index_max) {
2857  CHECK(eval != nullptr);
2858  std::vector<int64> cached_results;
2859  for (int i = 0; i <= index_max; ++i) {
2860  cached_results.push_back(eval(i));
2861  }
2862  VisitIntegerArrayArgument(arg_name, cached_results);
2863 }
2864 
2865 // ---------- Search Monitor ----------
2866 
2872  Decision* const d) {}
2875 void SearchMonitor::AfterDecision(Decision* const d, bool apply) {}
2880 bool SearchMonitor::AcceptSolution() { return true; }
2881 bool SearchMonitor::AtSolution() { return false; }
2883 bool SearchMonitor::LocalOptimum() { return false; }
2885  return true;
2886 }
2890 void SearchMonitor::Accept(ModelVisitor* const visitor) const {}
2891 // A search monitors adds itself on the active search.
2893  solver()->searches_.back()->push_monitor(this);
2894 }
2895 
2896 // ---------- Propagation Monitor -----------
2898  : SearchMonitor(solver) {}
2899 
2901 
2902 // A propagation monitor listens to search events as well as propagation events.
2905  solver()->AddPropagationMonitor(this);
2906 }
2907 
2908 // ---------- Local Search Monitor -----------
2910  : SearchMonitor(solver) {}
2911 
2913 
2914 // A local search monitor listens to search events as well as local search
2915 // events.
2918  solver()->AddLocalSearchMonitor(this);
2919 }
2920 
2921 // ---------- Trace ----------
2922 
2923 class Trace : public PropagationMonitor {
2924  public:
2925  explicit Trace(Solver* const s) : PropagationMonitor(s) {}
2926 
2927  ~Trace() override {}
2928 
2930  Constraint* const constraint) override {
2932  constraint);
2933  }
2934 
2935  void EndConstraintInitialPropagation(Constraint* const constraint) override {
2937  constraint);
2938  }
2939 
2941  Constraint* const parent, Constraint* const nested) override {
2942  ForAll(monitors_,
2944  nested);
2945  }
2946 
2948  Constraint* const parent, Constraint* const nested) override {
2949  ForAll(monitors_,
2951  nested);
2952  }
2953 
2954  void RegisterDemon(Demon* const demon) override {
2955  ForAll(monitors_, &PropagationMonitor::RegisterDemon, demon);
2956  }
2957 
2958  void BeginDemonRun(Demon* const demon) override {
2959  ForAll(monitors_, &PropagationMonitor::BeginDemonRun, demon);
2960  }
2961 
2962  void EndDemonRun(Demon* const demon) override {
2963  ForAll(monitors_, &PropagationMonitor::EndDemonRun, demon);
2964  }
2965 
2968  }
2969 
2970  void EndProcessingIntegerVariable(IntVar* const var) override {
2972  }
2973 
2974  void PushContext(const std::string& context) override {
2975  ForAll(monitors_, &PropagationMonitor::PushContext, context);
2976  }
2977 
2978  void PopContext() override {
2979  ForAll(monitors_, &PropagationMonitor::PopContext);
2980  }
2981 
2982  // IntExpr modifiers.
2983  void SetMin(IntExpr* const expr, int64 new_min) override {
2984  for (PropagationMonitor* const monitor : monitors_) {
2985  monitor->SetMin(expr, new_min);
2986  }
2987  }
2988 
2989  void SetMax(IntExpr* const expr, int64 new_max) override {
2990  for (PropagationMonitor* const monitor : monitors_) {
2991  monitor->SetMax(expr, new_max);
2992  }
2993  }
2994 
2995  void SetRange(IntExpr* const expr, int64 new_min, int64 new_max) override {
2996  for (PropagationMonitor* const monitor : monitors_) {
2997  monitor->SetRange(expr, new_min, new_max);
2998  }
2999  }
3000 
3001  // IntVar modifiers.
3002  void SetMin(IntVar* const var, int64 new_min) override {
3003  for (PropagationMonitor* const monitor : monitors_) {
3004  monitor->SetMin(var, new_min);
3005  }
3006  }
3007 
3008  void SetMax(IntVar* const var, int64 new_max) override {
3009  for (PropagationMonitor* const monitor : monitors_) {
3010  monitor->SetMax(var, new_max);
3011  }
3012  }
3013 
3014  void SetRange(IntVar* const var, int64 new_min, int64 new_max) override {
3015  for (PropagationMonitor* const monitor : monitors_) {
3016  monitor->SetRange(var, new_min, new_max);
3017  }
3018  }
3019 
3020  void RemoveValue(IntVar* const var, int64 value) override {
3021  ForAll(monitors_, &PropagationMonitor::RemoveValue, var, value);
3022  }
3023 
3024  void SetValue(IntVar* const var, int64 value) override {
3025  ForAll(monitors_, &PropagationMonitor::SetValue, var, value);
3026  }
3027 
3028  void RemoveInterval(IntVar* const var, int64 imin, int64 imax) override {
3029  ForAll(monitors_, &PropagationMonitor::RemoveInterval, var, imin, imax);
3030  }
3031 
3032  void SetValues(IntVar* const var, const std::vector<int64>& values) override {
3033  ForAll(monitors_, &PropagationMonitor::SetValues, var, values);
3034  }
3035 
3036  void RemoveValues(IntVar* const var,
3037  const std::vector<int64>& values) override {
3038  ForAll(monitors_, &PropagationMonitor::RemoveValues, var, values);
3039  }
3040 
3041  // IntervalVar modifiers.
3042  void SetStartMin(IntervalVar* const var, int64 new_min) override {
3043  ForAll(monitors_, &PropagationMonitor::SetStartMin, var, new_min);
3044  }
3045 
3046  void SetStartMax(IntervalVar* const var, int64 new_max) override {
3047  ForAll(monitors_, &PropagationMonitor::SetStartMax, var, new_max);
3048  }
3049 
3050  void SetStartRange(IntervalVar* const var, int64 new_min,
3051  int64 new_max) override {
3052  ForAll(monitors_, &PropagationMonitor::SetStartRange, var, new_min,
3053  new_max);
3054  }
3055 
3056  void SetEndMin(IntervalVar* const var, int64 new_min) override {
3057  ForAll(monitors_, &PropagationMonitor::SetEndMin, var, new_min);
3058  }
3059 
3060  void SetEndMax(IntervalVar* const var, int64 new_max) override {
3061  ForAll(monitors_, &PropagationMonitor::SetEndMax, var, new_max);
3062  }
3063 
3064  void SetEndRange(IntervalVar* const var, int64 new_min,
3065  int64 new_max) override {
3066  ForAll(monitors_, &PropagationMonitor::SetEndRange, var, new_min, new_max);
3067  }
3068 
3069  void SetDurationMin(IntervalVar* const var, int64 new_min) override {
3070  ForAll(monitors_, &PropagationMonitor::SetDurationMin, var, new_min);
3071  }
3072 
3073  void SetDurationMax(IntervalVar* const var, int64 new_max) override {
3074  ForAll(monitors_, &PropagationMonitor::SetDurationMax, var, new_max);
3075  }
3076 
3077  void SetDurationRange(IntervalVar* const var, int64 new_min,
3078  int64 new_max) override {
3079  ForAll(monitors_, &PropagationMonitor::SetDurationRange, var, new_min,
3080  new_max);
3081  }
3082 
3083  void SetPerformed(IntervalVar* const var, bool value) override {
3084  ForAll(monitors_, &PropagationMonitor::SetPerformed, var, value);
3085  }
3086 
3087  void RankFirst(SequenceVar* const var, int index) override {
3088  ForAll(monitors_, &PropagationMonitor::RankFirst, var, index);
3089  }
3090 
3091  void RankNotFirst(SequenceVar* const var, int index) override {
3092  ForAll(monitors_, &PropagationMonitor::RankNotFirst, var, index);
3093  }
3094 
3095  void RankLast(SequenceVar* const var, int index) override {
3096  ForAll(monitors_, &PropagationMonitor::RankLast, var, index);
3097  }
3098 
3099  void RankNotLast(SequenceVar* const var, int index) override {
3100  ForAll(monitors_, &PropagationMonitor::RankNotLast, var, index);
3101  }
3102 
3103  void RankSequence(SequenceVar* const var, const std::vector<int>& rank_first,
3104  const std::vector<int>& rank_last,
3105  const std::vector<int>& unperformed) override {
3106  ForAll(monitors_, &PropagationMonitor::RankSequence, var, rank_first,
3107  rank_last, unperformed);
3108  }
3109 
3110  // Does not take ownership of monitor.
3111  void Add(PropagationMonitor* const monitor) {
3112  if (monitor != nullptr) {
3113  monitors_.push_back(monitor);
3114  }
3115  }
3116 
3117  // The trace will dispatch propagation events. It needs to listen to search
3118  // events.
3119  void Install() override { SearchMonitor::Install(); }
3120 
3121  std::string DebugString() const override { return "Trace"; }
3122 
3123  private:
3124  std::vector<PropagationMonitor*> monitors_;
3125 };
3126 
3127 PropagationMonitor* BuildTrace(Solver* const s) { return new Trace(s); }
3128 
3130  // TODO(user): Check solver state?
3131  reinterpret_cast<class Trace*>(propagation_monitor_.get())->Add(monitor);
3132 }
3133 
3135  return propagation_monitor_.get();
3136 }
3137 
3138 // ---------- Local Search Monitor Master ----------
3139 
3141  public:
3144 
3145  void BeginOperatorStart() override {
3146  ForAll(monitors_, &LocalSearchMonitor::BeginOperatorStart);
3147  }
3148  void EndOperatorStart() override {
3149  ForAll(monitors_, &LocalSearchMonitor::EndOperatorStart);
3150  }
3151  void BeginMakeNextNeighbor(const LocalSearchOperator* op) override {
3152  ForAll(monitors_, &LocalSearchMonitor::BeginMakeNextNeighbor, op);
3153  }
3154  void EndMakeNextNeighbor(const LocalSearchOperator* op, bool neighbor_found,
3155  const Assignment* delta,
3156  const Assignment* deltadelta) override {
3157  ForAll(monitors_, &LocalSearchMonitor::EndMakeNextNeighbor, op,
3158  neighbor_found, delta, deltadelta);
3159  }
3160  void BeginFilterNeighbor(const LocalSearchOperator* op) override {
3161  ForAll(monitors_, &LocalSearchMonitor::BeginFilterNeighbor, op);
3162  }
3164  bool neighbor_found) override {
3165  ForAll(monitors_, &LocalSearchMonitor::EndFilterNeighbor, op,
3166  neighbor_found);
3167  }
3168  void BeginAcceptNeighbor(const LocalSearchOperator* op) override {
3169  ForAll(monitors_, &LocalSearchMonitor::BeginAcceptNeighbor, op);
3170  }
3172  bool neighbor_found) override {
3173  ForAll(monitors_, &LocalSearchMonitor::EndAcceptNeighbor, op,
3174  neighbor_found);
3175  }
3176  void BeginFiltering(const LocalSearchFilter* filter) override {
3177  ForAll(monitors_, &LocalSearchMonitor::BeginFiltering, filter);
3178  }
3179  void EndFiltering(const LocalSearchFilter* filter, bool reject) override {
3180  ForAll(monitors_, &LocalSearchMonitor::EndFiltering, filter, reject);
3181  }
3182 
3183  // Does not take ownership of monitor.
3184  void Add(LocalSearchMonitor* monitor) {
3185  if (monitor != nullptr) {
3186  monitors_.push_back(monitor);
3187  }
3188  }
3189 
3190  // The trace will dispatch propagation events. It needs to listen to search
3191  // events.
3192  void Install() override { SearchMonitor::Install(); }
3193 
3194  std::string DebugString() const override {
3195  return "LocalSearchMonitorMaster";
3196  }
3197 
3198  private:
3199  std::vector<LocalSearchMonitor*> monitors_;
3200 };
3201 
3203  return new LocalSearchMonitorMaster(s);
3204 }
3205 
3207  reinterpret_cast<class LocalSearchMonitorMaster*>(local_search_monitor_.get())
3208  ->Add(monitor);
3209 }
3210 
3212  return local_search_monitor_.get();
3213 }
3214 
3216  const std::string& search_context) {
3217  search->set_search_context(search_context);
3218 }
3219 
3220 std::string Solver::SearchContext() const {
3221  return ActiveSearch()->search_context();
3222 }
3223 
3224 std::string Solver::SearchContext(const Search* search) const {
3225  return search->search_context();
3226 }
3227 
3229  if (local_search_state_ == nullptr) {
3230  local_search_state_ = absl::make_unique<Assignment>(this);
3231  }
3232  return local_search_state_.get();
3233 }
3234 
3235 // ----------------- Constraint class -------------------
3236 
3237 std::string Constraint::DebugString() const { return "Constraint"; }
3238 
3240  FreezeQueue();
3241  Post();
3242  InitialPropagate();
3243  solver()->CheckFail();
3244  UnfreezeQueue();
3245 }
3246 
3247 void Constraint::Accept(ModelVisitor* const visitor) const {
3248  visitor->BeginVisitConstraint("unknown", this);
3249  VLOG(3) << "Unknown constraint " << DebugString();
3250  visitor->EndVisitConstraint("unknown", this);
3251 }
3252 
3254  return gtl::ContainsKey(solver()->cast_constraints_, this);
3255 }
3256 
3257 IntVar* Constraint::Var() { return nullptr; }
3258 
3259 // ----- Class IntExpr -----
3260 
3261 void IntExpr::Accept(ModelVisitor* const visitor) const {
3262  visitor->BeginVisitIntegerExpression("unknown", this);
3263  VLOG(3) << "Unknown expression " << DebugString();
3264  visitor->EndVisitIntegerExpression("unknown", this);
3265 }
3266 
3267 #undef CP_TRY // We no longer need those.
3268 #undef CP_ON_FAIL
3269 #undef CP_DO_FAIL
3270 
3271 } // namespace operations_research
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_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_GE(val1, val2)
Definition: base/logging.h:889
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#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.
A BaseObject is the root of all reversibly allocated objects.
virtual std::string DebugString() const
Cast constraints are special channeling constraints designed to keep a variable in sync with an expre...
A constraint is the main modeling object.
void PostAndPropagate()
Calls Post and then Propagate to initialize the constraints.
bool IsCastConstraint() const
Is the constraint created by a cast from expression to integer variable?
virtual void InitialPropagate()=0
This method performs the initial propagation of the constraint.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
virtual IntVar * Var()
Creates a Boolean variable representing the status of the constraint (false = constraint is violated,...
std::string DebugString() const override
virtual void Post()=0
This method is called when the constraint is processed by the solver.
A DecisionBuilder is responsible for creating the search tree.
virtual Decision * Next(Solver *const s)=0
This is the main method of the decision builder class.
virtual void Accept(ModelVisitor *const visitor) const
virtual void AppendMonitors(Solver *const solver, std::vector< SearchMonitor * > *const extras)
This method will be called at the start of the search.
std::string DebugString() const override
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.
A DecisionVisitor is used to inspect a decision.
virtual void VisitSplitVariableDomain(IntVar *const var, int64 value, bool start_with_lower_half)
virtual void VisitRankFirstInterval(SequenceVar *const sequence, int index)
virtual void VisitScheduleOrPostpone(IntervalVar *const var, int64 est)
virtual void VisitScheduleOrExpedite(IntervalVar *const var, int64 est)
virtual void VisitRankLastInterval(SequenceVar *const sequence, int index)
virtual void VisitSetVariableValue(IntVar *const var, int64 value)
A Demon is the base element of a propagation queue.
void inhibit(Solver *const s)
This method inhibits the demon in the search tree below the current position.
void desinhibit(Solver *const s)
This method un-inhibits the demon that was previously inhibited.
virtual Solver::DemonPriority priority() const
This method returns the priority of the demon.
std::string DebugString() const override
virtual void Run(Solver *const s)=0
This is the main callback of the demon.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
The class IntVar is a subset of IntExpr.
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
Interval variables are often used in scheduling.
virtual void Accept(ModelVisitor *const visitor) const =0
Accepts the given visitor.
Local Search Filters are used for fast neighbor pruning.
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
void Install() override
Install itself on the solver.
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0
virtual void BeginOperatorStart()=0
Local search operator events.
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
void BeginFiltering(const LocalSearchFilter *filter) override
void Install() override
Registers itself on the solver such that it gets notified of the search and propagation events.
void BeginOperatorStart() override
Local search operator events.
void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta) override
void BeginMakeNextNeighbor(const LocalSearchOperator *op) override
void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
void BeginAcceptNeighbor(const LocalSearchOperator *op) override
void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
void EndFiltering(const LocalSearchFilter *filter, bool reject) override
void BeginFilterNeighbor(const LocalSearchOperator *op) override
The base class for all local search operators.
virtual void VisitIntervalVariable(const IntervalVar *const variable, const std::string &operation, int64 value, IntervalVar *const delegate)
static const char kSolutionLimitArgument[]
static const char kCountUsedBinsExtension[]
static const char kMirrorOperation[]
Operations.
static const char kAbs[]
Constraint and Expression types.
virtual void VisitSequenceVariable(const SequenceVar *const variable)
static const char kVariableUsageLessConstantExtension[]
virtual void VisitIntegerVariable(const IntVar *const variable, IntExpr *const delegate)
static const char kActiveArgument[]
argument names:
virtual void VisitIntervalArgument(const std::string &arg_name, IntervalVar *const argument)
Visit interval argument.
static const char kBranchesLimitArgument[]
static const char kIntervalUnaryRelation[]
virtual void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
virtual void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64 index_min, int64 index_max)
static const char kWeightedSumOfAssignedEqualVariableExtension[]
virtual void VisitIntegerVariableEvaluatorArgument(const std::string &arg_name, const Solver::Int64ToIntVar &arguments)
Helpers.
static const char kSmartTimeCheckArgument[]
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *const constraint)
virtual void BeginVisitExtension(const std::string &type)
static const char kStartSyncOnStartOperation[]
static const char kUsageLessConstantExtension[]
virtual void EndVisitExtension(const std::string &type)
virtual void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64 > &values)
static const char kUsageEqualVariableExtension[]
virtual void VisitIntegerArgument(const std::string &arg_name, int64 value)
Visit integer arguments.
virtual void EndVisitModel(const std::string &type_name)
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
static const char kVariableGroupExtension[]
static const char kFailuresLimitArgument[]
static const char kScalProdGreaterOrEqual[]
virtual void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments)
static const char kIntervalBinaryRelation[]
virtual void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &tuples)
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *const argument)
Visit integer expression argument.
virtual void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments)
void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64 index_min, int64 index_max)
Using SWIG on callbacks is troublesome, so we hide these methods during the wrapping.
static const char kInt64ToInt64Extension[]
void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1 &eval, const std::string &arg_name, int64 index_max)
Expands function as array when index min is 0.
static const char kStartSyncOnEndOperation[]
virtual void VisitSequenceArgument(const std::string &arg_name, SequenceVar *const argument)
Visit sequence argument.
virtual void BeginVisitModel(const std::string &type_name)
--— Virtual methods for visitors --—
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *const constraint)
static const char kCountAssignedItemsExtension[]
Extension names:
virtual std::string name() const
Object naming.
bool HasName() const
Returns whether the object has been named or not.
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
void FreezeQueue()
This method freezes the propagation queue.
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
virtual std::string BaseName() const
Returns a base name for automatic naming.
void UnfreezeQueue()
This method unfreezes the propagation queue.
void Install() override
Install itself on the solver.
virtual void RankLast(SequenceVar *const var, int index)=0
virtual void SetEndMin(IntervalVar *const var, int64 new_min)=0
virtual void EndConstraintInitialPropagation(Constraint *const constraint)=0
virtual void SetValues(IntVar *const var, const std::vector< int64 > &values)=0
virtual void RemoveValue(IntVar *const var, int64 value)=0
virtual void SetEndMax(IntervalVar *const var, int64 new_max)=0
virtual void RankNotLast(SequenceVar *const var, int index)=0
virtual void RankNotFirst(SequenceVar *const var, int index)=0
virtual void BeginDemonRun(Demon *const demon)=0
virtual void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)=0
virtual void PushContext(const std::string &context)=0
virtual void RemoveInterval(IntVar *const var, int64 imin, int64 imax)=0
virtual void RemoveValues(IntVar *const var, const std::vector< int64 > &values)=0
virtual void SetStartMin(IntervalVar *const var, int64 new_min)=0
IntervalVar modifiers.
virtual void SetValue(IntVar *const var, int64 value)=0
virtual void SetStartRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
virtual void BeginNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
virtual void EndNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
virtual void SetPerformed(IntervalVar *const var, bool value)=0
virtual void StartProcessingIntegerVariable(IntVar *const var)=0
virtual void SetDurationRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
virtual void BeginConstraintInitialPropagation(Constraint *const constraint)=0
Propagation events.
virtual void SetDurationMin(IntervalVar *const var, int64 new_min)=0
virtual void SetStartMax(IntervalVar *const var, int64 new_max)=0
virtual void EndDemonRun(Demon *const demon)=0
virtual void RegisterDemon(Demon *const demon)=0
virtual void EndProcessingIntegerVariable(IntVar *const var)=0
virtual void SetDurationMax(IntervalVar *const var, int64 new_max)=0
virtual void RankFirst(SequenceVar *const var, int index)=0
SequenceVar modifiers.
virtual void SetEndRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
void EnqueueDelayedDemon(Demon *const demon)
void set_action_on_fail(Solver::Action a)
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
void EnqueueVar(Demon *const demon)
void AddConstraint(Constraint *const c)
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
void set_variable_to_clean_on_fail(IntVar *var)
static constexpr int64 kTestPeriod
void ProcessOneDemon(Demon *const demon)
void RefuteDecision(Decision *const d)
void ApplyDecision(Decision *const d)
void BeginNextDecision(DecisionBuilder *const db)
Search(Solver *const s, int)
std::string search_context() const
void SetBranchSelector(Solver::BranchSelector bs)
bool backtrack_at_the_end_of_the_search() const
void AfterDecision(Decision *const d, bool apply)
void set_backtrack_at_the_end_of_the_search(bool restore)
Solver::DecisionModification ModifyDecision()
void push_monitor(SearchMonitor *const m)
void set_decision_builder(DecisionBuilder *const db)
bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
void Accept(ModelVisitor *const visitor) const
DecisionBuilder * decision_builder() const
void EndNextDecision(DecisionBuilder *const db, Decision *const d)
void set_search_context(const std::string &search_context)
A search monitor is a simple set of callbacks to monitor all search events.
virtual void RefuteDecision(Decision *const d)
Before refuting the decision.
virtual void ApplyDecision(Decision *const d)
Before applying the decision.
virtual void RestartSearch()
Restart the search.
virtual void ExitSearch()
End of the search.
virtual bool LocalOptimum()
When a local optimum is reached.
virtual void NoMoreSolutions()
When the search tree is finished.
virtual void BeginFail()
Just when the failure occurs.
virtual void AfterDecision(Decision *const d, bool apply)
Just after refuting or applying the decision, apply is true after Apply.
virtual void BeginInitialPropagation()
Before the initial propagation.
virtual void BeginNextDecision(DecisionBuilder *const b)
Before calling DecisionBuilder::Next.
virtual void PeriodicCheck()
Periodic call to check limits in long running methods.
virtual void EnterSearch()
Beginning of the search.
virtual void EndNextDecision(DecisionBuilder *const b, Decision *const d)
After calling DecisionBuilder::Next, along with the returned decision.
virtual void EndFail()
After completing the backtrack.
virtual void EndInitialPropagation()
After the initial propagation.
virtual void AcceptUncheckedNeighbor()
After accepting an unchecked neighbor during local search.
virtual bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
virtual bool AtSolution()
This method is called when a valid solution is found.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
virtual void AcceptNeighbor()
After accepting a neighbor during local search.
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
virtual bool AcceptSolution()
This method is called when a solution is found.
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
int64 size() const
Returns the number of interval vars in the sequence.
IntervalVar * Interval(int index) const
Returns the index_th interval of the sequence.
Definition: sched_search.cc:50
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
Definition: sched_search.cc:71
This iterator is not stable with respect to deletion.
This class represent a reversible FIFO structure.
std::function< bool(int64)> IndexFilter1
DecisionModification
The Solver is responsible for creating the search tree.
@ NO_CHANGE
Keeps the default behavior, i.e.
@ SWITCH_BRANCHES
Applies right branch first.
@ KEEP_RIGHT
Left branches are ignored.
@ KEEP_LEFT
Right branches are ignored.
@ KILL_BOTH
Backtracks to the previous decisions, i.e.
bool HasName(const PropagationBaseObject *object) const
Returns whether the object has been named or not.
bool SolveAndCommit(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolveAndCommit using a decision builder and up to three search monitors, usually one for the objectiv...
Constraint * MakeFalseConstraint()
This constraint always fails.
Definition: constraints.cc:520
int64 solutions() const
The number of solutions found since the start of the search.
ConstraintSolverStatistics GetConstraintSolverStatistics() const
Returns detailed cp search statistics.
static constexpr int kNumPriorities
Number of priorities for demons.
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
@ NORMAL_PRIORITY
NORMAL_PRIORITY is the highest priority: Demons will be processed first.
int64 failures() const
The number of failures encountered since the creation of the solver.
@ AT_SOLUTION
After successful NextSolution and before EndSearch.
@ PROBLEM_INFEASIBLE
After search, the model is infeasible.
@ OUTSIDE_SEARCH
Before search, after search.
@ IN_ROOT_NODE
Executing the root node.
@ NO_MORE_SOLUTIONS
After failed NextSolution and before EndSearch.
@ IN_SEARCH
Executing the search code.
std::string SearchContext() const
bool CheckAssignment(Assignment *const solution)
Checks whether the given assignment satisfies all relevant constraints.
absl::Time Now() const
The 'absolute time' as seen by the solver.
DecisionBuilder * MakeConstraintAdder(Constraint *const ct)
Returns a decision builder that will add the given constraint to the model.
Assignment * GetOrCreateLocalSearchState()
Returns (or creates) an assignment representing the state of local search.
bool IsProfilingEnabled() const
Returns whether we are profiling the solver.
uint64 fail_stamp() const
The fail_stamp() is incremented after each backtrack.
void AddPropagationMonitor(PropagationMonitor *const monitor)
Adds the propagation monitor to the solver.
bool CheckConstraint(Constraint *const ct)
Checks whether adding this constraint will lead to an immediate failure.
void SetSearchContext(Search *search, const std::string &search_context)
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
DecisionBuilder * MakeApplyBranchSelector(BranchSelector bs)
Creates a decision builder that will set the branch selector.
void AddConstraint(Constraint *const c)
Adds the constraint 'c' to the model.
int SearchDepth() const
Gets the search depth of the current active search.
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
void AddLocalSearchMonitor(LocalSearchMonitor *monitor)
Adds the local search monitor to the solver.
void PushState()
The PushState and PopState methods manipulates the states of the reversible objects.
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
std::string DebugString() const
!defined(SWIG)
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
int64 wall_time() const
DEPRECATED: Use Now() instead.
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
int SolveDepth() const
Gets the number of nested searches.
PropagationMonitor * GetPropagationMonitor() const
Returns the propagation monitor.
bool Solve(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
std::string model_name() const
Returns the name of the model.
bool InstrumentsVariables() const
Returns whether we are tracing variables.
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.
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
std::string LocalSearchProfile() const
Returns local search profiling information in a human readable format.
void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
int SearchLeftDepth() const
Gets the search left depth of the current active search.
void AddBacktrackAction(Action a, bool fast)
When SaveValue() is not the best way to go, one can create a reversible action that will be called up...
int TopProgressPercent()
Returns a percentage representing the propress of the search before reaching the limits of the top-le...
bool CurrentlyInSolve() const
Returns true whether the current search has been created using a Solve() call instead of a NewSearch ...
T * RevAlloc(T *object)
Registers the given object as being reversible.
Solver(const std::string &name)
Solver API.
bool NameAllVariables() const
Returns whether all variables should be named.
int64 unchecked_solutions() const
The number of unchecked solutions found by local search.
IntExpr * CastExpression(const IntVar *const var) const
!defined(SWIG)
void SetBranchSelector(BranchSelector bs)
Sets the given branch selector on the current active search.
int64 branches() const
The number of branches explored since the creation of the solver.
uint64 stamp() const
The stamp indicates how many moves in the search tree we have performed.
ModelVisitor * MakePrintModelVisitor()
Prints the model.
Definition: utilities.cc:807
std::function< void(Solver *)> Action
void ExportProfilingOverview(const std::string &filename)
Exports the profiling information in a human readable overview.
std::function< IntVar *(int64)> Int64ToIntVar
MarkerType
This enum is used internally in private methods Solver::PushState and Solver::PopState to tag states ...
void AddCastConstraint(CastConstraint *const constraint, IntVar *const target_var, IntExpr *const expr)
Adds 'constraint' to the solver and marks it as a cast constraint, that is, a constraint created call...
std::function< DecisionModification()> BranchSelector
bool InstrumentsDemons() const
Returns whether we are instrumenting demons.
static int64 MemoryUsage()
Current memory usage in bytes.
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
void FinishCurrentSearch()
Tells the solver to kill or restart the current search.
void NewSearch(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
Definition: utilities.cc:811
void SetStartMin(IntervalVar *const var, int64 new_min) override
IntervalVar modifiers.
void Install() override
Registers itself on the solver such that it gets notified of the search and propagation events.
void SetRange(IntVar *const var, int64 new_min, int64 new_max) override
void SetEndMin(IntervalVar *const var, int64 new_min) override
void SetDurationMax(IntervalVar *const var, int64 new_max) override
void EndProcessingIntegerVariable(IntVar *const var) override
void SetDurationRange(IntervalVar *const var, int64 new_min, int64 new_max) override
void SetPerformed(IntervalVar *const var, bool value) override
void BeginConstraintInitialPropagation(Constraint *const constraint) override
Propagation events.
void EndNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested) override
void EndConstraintInitialPropagation(Constraint *const constraint) override
void SetValues(IntVar *const var, const std::vector< int64 > &values) override
void RemoveInterval(IntVar *const var, int64 imin, int64 imax) override
void StartProcessingIntegerVariable(IntVar *const var) override
void RemoveValues(IntVar *const var, const std::vector< int64 > &values) override
void SetEndMax(IntervalVar *const var, int64 new_max) override
void RegisterDemon(Demon *const demon) override
void EndDemonRun(Demon *const demon) override
void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed) override
void SetRange(IntExpr *const expr, int64 new_min, int64 new_max) override
void BeginDemonRun(Demon *const demon) override
void SetMax(IntVar *const var, int64 new_max) override
void RemoveValue(IntVar *const var, int64 value) override
void SetValue(IntVar *const var, int64 value) override
void SetMin(IntExpr *const expr, int64 new_min) override
IntExpr modifiers.
void SetEndRange(IntervalVar *const var, int64 new_min, int64 new_max) override
void RankLast(SequenceVar *const var, int index) override
void PushContext(const std::string &context) override
void Add(PropagationMonitor *const monitor)
void RankNotLast(SequenceVar *const var, int index) override
void SetMin(IntVar *const var, int64 new_min) override
IntVar modifiers.
void SetStartMax(IntervalVar *const var, int64 new_max) override
void SetStartRange(IntervalVar *const var, int64 new_min, int64 new_max) override
void BeginNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested) override
void SetMax(IntExpr *const expr, int64 new_max) override
void RankFirst(SequenceVar *const var, int index) override
SequenceVar modifiers.
std::string DebugString() const override
void RankNotFirst(SequenceVar *const var, int index) override
void SetDurationMin(IntervalVar *const var, int64 new_min) override
Block * next
#define CP_ON_FAIL
#define CP_TRY(search)
#define CP_DO_FAIL(search)
ABSL_FLAG(bool, cp_trace_propagation, false, "Trace propagation events (constraint and demon executions," " variable modifications).")
void ConstraintSolverFailsHere()
std::string compressed
SatParameters parameters
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
GurobiMPCallbackContext * context
unsigned int uint32
int64_t int64
static const uint64 kuint64max
uint64_t uint64
const int WARNING
Definition: log_severity.h:31
const int INFO
Definition: log_severity.h:31
const int ERROR
Definition: log_severity.h:32
const int FATAL
Definition: log_severity.h:32
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
void STLDeleteElements(T *container)
Definition: stl_util.h:372
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:41
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
PropagationMonitor * BuildPrintTrace(Solver *const s)
Definition: trace.cc:873
void InternalSaveBooleanVarValue(Solver *const solver, IntVar *const var)
void InstallDemonProfiler(DemonProfiler *const monitor)
void InstallLocalSearchProfiler(LocalSearchProfiler *monitor)
void CleanVariableOnFail(IntVar *const var)
ModelCache * BuildModelCache(Solver *const solver)
Definition: model_cache.cc:845
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
void DeleteLocalSearchProfiler(LocalSearchProfiler *monitor)
void RestoreBoolValue(IntVar *const var)
int64 GetProcessMemoryUsage()
Definition: sysinfo.cc:85
DemonProfiler * BuildDemonProfiler(Solver *const solver)
bool AcceptDelta(Search *const search, Assignment *delta, Assignment *deltadelta)
void AcceptNeighbor(Search *const search)
LocalSearchMonitor * BuildLocalSearchMonitorMaster(Solver *const s)
PropagationMonitor * BuildTrace(Solver *const s)
void DeleteDemonProfiler(DemonProfiler *const monitor)
bool LocalOptimumReached(Search *const search)
void AcceptUncheckedNeighbor(Search *const search)
LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)
int index
Definition: pack.cc:508
int64 delta
Definition: resource.cc:1684
BaseVariableAssignmentSelector *const selector_
Definition: search.cc:1856
int64 current_
Definition: search.cc:2953
Holds semantic information stating that the 'expression' has been cast into 'variable' using the Var(...
StateInfo(Solver::Action a, bool fast)
StateInfo(void *pinfo, int iinfo, int d, int ld)
StateInfo(void *pinfo, int iinfo)
StateMarker(Solver::MarkerType t, const StateInfo &info)
CompressedTrail< uint64 > rev_uint64s_
CompressedTrail< void * > rev_ptrs_
std::vector< double * > rev_double_memory_
std::vector< int * > rev_int_memory_
std::vector< BaseObject * > rev_object_memory_
std::vector< IntVar * > rev_boolvar_list_
std::vector< void * > rev_memory_
Trail(int block_size, ConstraintSolverParameters::TrailCompression compression_level)
std::vector< bool > rev_bool_value_
CompressedTrail< int64 > rev_int64s_
void BacktrackTo(StateMarker *m)
std::vector< bool * > rev_bools_
std::vector< int64 * > rev_int64_memory_
std::vector< void ** > rev_memory_array_
CompressedTrail< double > rev_doubles_
std::vector< BaseObject ** > rev_object_array_memory_
CompressedTrail< int > rev_ints_