OR-Tools  8.1
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_ = GG_ULONGLONG(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
operations_research::Solver::KILL_BOTH
@ KILL_BOTH
Backtracks to the previous decisions, i.e.
Definition: constraint_solver.h:707
ABSL_FLAG
ABSL_FLAG(bool, cp_trace_propagation, false, "Trace propagation events (constraint and demon executions," " variable modifications).")
operations_research::IntVar
The class IntVar is a subset of IntExpr.
Definition: constraint_solver.h:3992
operations_research::ModelVisitor::kEquality
static const char kEquality[]
Definition: constraint_solver.h:3354
operations_research::Trail::rev_memory_array_
std::vector< void ** > rev_memory_array_
Definition: constraint_solver.cc:738
operations_research::ModelVisitor::kIsGreater
static const char kIsGreater[]
Definition: constraint_solver.h:3368
operations_research::LocalSearchMonitor::BeginAcceptNeighbor
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
operations_research::StateInfo::reversible_action
Solver::Action reversible_action
Definition: constraint_solver.cc:447
operations_research::ModelVisitor::kMax
static const char kMax[]
Definition: constraint_solver.h:3378
operations_research::ModelVisitor::kLinkExprVar
static const char kLinkExprVar[]
Definition: constraint_solver.h:3376
operations_research::PropagationBaseObject::UnfreezeQueue
void UnfreezeQueue()
This method unfreezes the propagation queue.
Definition: constraint_solver.h:3182
var
IntVar * var
Definition: expr_array.cc:1858
operations_research::InstallDemonProfiler
void InstallDemonProfiler(DemonProfiler *const monitor)
Definition: demon_profiler.cc:438
operations_research::ModelVisitor::kIntervalDisjunction
static const char kIntervalDisjunction[]
Definition: constraint_solver.h:3361
operations_research::Solver::PushState
void PushState()
The PushState and PopState methods manipulates the states of the reversible objects.
Definition: constraint_solver.cc:1556
operations_research::Search::AcceptDelta
bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
Definition: constraint_solver.cc:1298
operations_research::PropagationMonitor::SetEndRange
virtual void SetEndRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
operations_research::SearchMonitor::EndFail
virtual void EndFail()
After completing the backtrack.
Definition: constraint_solver.cc:2877
operations_research::Trace::SetPerformed
void SetPerformed(IntervalVar *const var, bool value) override
Definition: constraint_solver.cc:3083
operations_research::ModelVisitor::VisitIntervalArgument
virtual void VisitIntervalArgument(const std::string &arg_name, IntervalVar *const argument)
Visit interval argument.
Definition: constraint_solver.cc:2803
operations_research::StateInfo
Definition: constraint_solver.cc:415
operations_research::ModelVisitor::kDivide
static const char kDivide[]
Definition: constraint_solver.h:3349
operations_research::Trail::rev_ints_
CompressedTrail< int > rev_ints_
Definition: constraint_solver.cc:724
compressed
std::string compressed
Definition: constraint_solver.cc:673
operations_research::Solver::SolveAndCommit
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...
Definition: constraint_solver.cc:2405
INFO
const int INFO
Definition: log_severity.h:31
operations_research::Trace::SetMin
void SetMin(IntExpr *const expr, int64 new_min) override
IntExpr modifiers.
Definition: constraint_solver.cc:2983
operations_research::PropagationMonitor::RankNotFirst
virtual void RankNotFirst(SequenceVar *const var, int index)=0
operations_research::LocalSearchMonitorMaster::LocalSearchMonitorMaster
LocalSearchMonitorMaster(Solver *solver)
Definition: constraint_solver.cc:3142
operations_research::Demon::Run
virtual void Run(Solver *const s)=0
This is the main callback of the demon.
operations_research::Trail::rev_double_memory_
std::vector< double * > rev_double_memory_
Definition: constraint_solver.cc:734
operations_research::ModelVisitor::kSequenceArgument
static const char kSequenceArgument[]
Definition: constraint_solver.h:3471
operations_research::ModelVisitor::kNotBetween
static const char kNotBetween[]
Definition: constraint_solver.h:3386
operations_research::Search
Definition: constraint_solver.cc:953
operations_research::LocalSearchMonitorMaster::EndFilterNeighbor
void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
Definition: constraint_solver.cc:3163
operations_research::ModelVisitor::kSumLessOrEqual
static const char kSumLessOrEqual[]
Definition: constraint_solver.h:3408
operations_research::CpRandomSeed
int64 CpRandomSeed()
Definition: constraint_solver.h:163
operations_research::ModelVisitor::kIntegerVariable
static const char kIntegerVariable[]
Definition: constraint_solver.h:3359
operations_research::DecisionVisitor::VisitRankLastInterval
virtual void VisitRankLastInterval(SequenceVar *const sequence, int index)
Definition: constraint_solver.cc:2551
operations_research::Trail::rev_bools_
std::vector< bool * > rev_bools_
Definition: constraint_solver.cc:730
operations_research::ModelVisitor::kAllDifferent
static const char kAllDifferent[]
Definition: constraint_solver.h:3334
integral_types.h
map_util.h
operations_research::PropagationMonitor::SetDurationMin
virtual void SetDurationMin(IntervalVar *const var, int64 new_min)=0
operations_research::Trace::SetMax
void SetMax(IntExpr *const expr, int64 new_max) override
Definition: constraint_solver.cc:2989
operations_research::ModelVisitor::kSemiContinuous
static const char kSemiContinuous[]
Definition: constraint_solver.h:3400
operations_research::Solver::IN_SEARCH
@ IN_SEARCH
Executing the search code.
Definition: constraint_solver.h:725
VLOG
#define VLOG(verboselevel)
Definition: base/logging.h:978
operations_research::PropagationBaseObject::name
virtual std::string name() const
Object naming.
Definition: constraint_solver.cc:2505
operations_research::Search::IsUncheckedSolutionLimitReached
bool IsUncheckedSolutionLimitReached()
Definition: constraint_solver.cc:1316
operations_research::ModelVisitor
Model visitor.
Definition: constraint_solver.h:3329
operations_research::Trace::BeginNestedConstraintInitialPropagation
void BeginNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested) override
Definition: constraint_solver.cc:2940
operations_research::Search::SetBranchSelector
void SetBranchSelector(Solver::BranchSelector bs)
Definition: constraint_solver.cc:1148
operations_research::Search::set_created_by_solve
void set_created_by_solve(bool c)
Definition: constraint_solver.cc:1027
max
int64 max
Definition: alldiff_cst.cc:139
operations_research::ModelVisitor::kMin
static const char kMin[]
Definition: constraint_solver.h:3381
current_
int64 current_
Definition: search.cc:2953
operations_research::Constraint::DebugString
std::string DebugString() const override
Definition: constraint_solver.cc:3237
operations_research::PropagationMonitor::BeginNestedConstraintInitialPropagation
virtual void BeginNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
operations_research::DecisionBuilder::Next
virtual Decision * Next(Solver *const s)=0
This is the main method of the decision builder class.
operations_research::Trail::rev_boolvar_list_
std::vector< IntVar * > rev_boolvar_list_
Definition: constraint_solver.cc:729
operations_research::ModelVisitor::kDemandsArgument
static const char kDemandsArgument[]
Definition: constraint_solver.h:3439
operations_research::Solver::SaveAndSetValue
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
Definition: constraint_solver.h:2806
operations_research::Trace::RankSequence
void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed) override
Definition: constraint_solver.cc:3103
operations_research::Solver::Solve
bool Solve(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
Definition: constraint_solver.cc:1791
operations_research::ModelVisitor::kCountUsedBinsExtension
static const char kCountUsedBinsExtension[]
Definition: constraint_solver.h:3417
operations_research::ModelVisitor::kAtMost
static const char kAtMost[]
Definition: constraint_solver.h:3336
operations_research::Trace::Install
void Install() override
Registers itself on the solver such that it gets notified of the search and propagation events.
Definition: constraint_solver.cc:3119
operations_research::PropagationMonitor::RankSequence
virtual void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)=0
operations_research::SequenceVar::Accept
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
Definition: sched_search.cc:71
operations_research::Solver::MakeFalseConstraint
Constraint * MakeFalseConstraint()
This constraint always fails.
Definition: constraints.cc:520
operations_research::PropagationMonitor::RankLast
virtual void RankLast(SequenceVar *const var, int index)=0
operations_research::Solver::Constraint
friend class Constraint
Definition: constraint_solver.h:2938
operations_research::ModelVisitor::kStartExpr
static const char kStartExpr[]
Definition: constraint_solver.h:3404
operations_research::ModelVisitor::kStartsArgument
static const char kStartsArgument[]
Definition: constraint_solver.h:3480
operations_research::LocalSearchMonitor::BeginMakeNextNeighbor
virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0
LOG
#define LOG(severity)
Definition: base/logging.h:420
ERROR
const int ERROR
Definition: log_severity.h:32
operations_research::Solver::CheckConstraint
bool CheckConstraint(Constraint *const ct)
Checks whether adding this constraint will lead to an immediate failure.
Definition: constraint_solver.cc:2372
operations_research::Solver::AddConstraint
void AddConstraint(Constraint *const c)
Adds the constraint 'c' to the model.
Definition: constraint_solver.cc:1657
recordio.h
operations_research::StateInfo::StateInfo
StateInfo(Solver::Action a, bool fast)
Definition: constraint_solver.cc:436
operations_research::PropagationMonitor::SetDurationRange
virtual void SetDurationRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
operations_research::Trail::rev_int64s_
CompressedTrail< int64 > rev_int64s_
Definition: constraint_solver.cc:725
operations_research::ModelVisitor::kVariableUsageLessConstantExtension
static const char kVariableUsageLessConstantExtension[]
Definition: constraint_solver.h:3426
operations_research::Solver::DELAYED_PRIORITY
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
Definition: constraint_solver.h:611
operations_research::ModelVisitor::kCumulsArgument
static const char kCumulsArgument[]
Definition: constraint_solver.h:3438
operations_research::PropagationMonitor::StartProcessingIntegerVariable
virtual void StartProcessingIntegerVariable(IntVar *const var)=0
operations_research::Trace::EndProcessingIntegerVariable
void EndProcessingIntegerVariable(IntVar *const var) override
Definition: constraint_solver.cc:2970
operations_research::StateInfo::int_info
int int_info
Definition: constraint_solver.cc:444
operations_research::SearchMonitor::BeginFail
virtual void BeginFail()
Just when the failure occurs.
Definition: constraint_solver.cc:2876
operations_research::StateMarker::StateMarker
StateMarker(Solver::MarkerType t, const StateInfo &info)
Definition: constraint_solver.cc:475
operations_research::Trail::BacktrackTo
void BacktrackTo(StateMarker *m)
Definition: constraint_solver.cc:748
operations_research::PropagationMonitor::SetValue
virtual void SetValue(IntVar *const var, int64 value)=0
operations_research::Solver::AddLocalSearchMonitor
void AddLocalSearchMonitor(LocalSearchMonitor *monitor)
Adds the local search monitor to the solver.
Definition: constraint_solver.cc:3206
operations_research::Solver::SearchDepth
int SearchDepth() const
Gets the search depth of the current active search.
Definition: constraint_solver.cc:1175
FATAL
const int FATAL
Definition: log_severity.h:32
operations_research::Trace::RankNotFirst
void RankNotFirst(SequenceVar *const var, int index) override
Definition: constraint_solver.cc:3091
operations_research::PropagationMonitor::EndConstraintInitialPropagation
virtual void EndConstraintInitialPropagation(Constraint *const constraint)=0
operations_research::ModelVisitor::VisitIntegerArgument
virtual void VisitIntegerArgument(const std::string &arg_name, int64 value)
Visit integer arguments.
Definition: constraint_solver.cc:2780
operations_research::StateInfo::depth
int depth
Definition: constraint_solver.cc:445
operations_research::ModelVisitor::VisitIntegerArrayArgument
virtual void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64 > &values)
Definition: constraint_solver.cc:2783
operations_research::SearchMonitor::solver
Solver * solver() const
Definition: constraint_solver.h:3703
operations_research::ModelVisitor::kCardsArgument
static const char kCardsArgument[]
Definition: constraint_solver.h:3434
operations_research::Search::EndFail
void EndFail()
Definition: constraint_solver.cc:1248
operations_research::SearchMonitor::RestartSearch
virtual void RestartSearch()
Restart the search.
Definition: constraint_solver.cc:2868
operations_research::PropagationMonitor::Install
void Install() override
Install itself on the solver.
Definition: constraint_solver.cc:2903
CHECK_GE
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
operations_research::Solver::NameAllVariables
bool NameAllVariables() const
Returns whether all variables should be named.
Definition: constraint_solver.cc:187
operations_research::ModelVisitor::kVarsArgument
static const char kVarsArgument[]
Definition: constraint_solver.h:3489
operations_research::Search::solution_counter
int64 solution_counter() const
Definition: constraint_solver.cc:1018
operations_research::Search::backtrack_at_the_end_of_the_search
bool backtrack_at_the_end_of_the_search() const
Definition: constraint_solver.cc:1036
operations_research::Solver::OUTSIDE_SEARCH
@ OUTSIDE_SEARCH
Before search, after search.
Definition: constraint_solver.h:721
operations_research::Search::CheckFail
void CheckFail()
Definition: constraint_solver.cc:1050
operations_research::Solver::RevAlloc
T * RevAlloc(T *object)
Registers the given object as being reversible.
Definition: constraint_solver.h:791
operations_research::Search::set_decision_builder
void set_decision_builder(DecisionBuilder *const db)
Definition: constraint_solver.cc:1023
operations_research::ModelVisitor::kScalProdLessOrEqual
static const char kScalProdLessOrEqual[]
Definition: constraint_solver.h:3399
GG_ULONGLONG
#define GG_ULONGLONG(x)
Definition: integral_types.h:47
operations_research::ModelVisitor::kDifferenceOperation
static const char kDifferenceOperation[]
Definition: constraint_solver.h:3497
logging.h
operations_research::Solver::RestartCurrentSearch
void RestartCurrentSearch()
Definition: constraint_solver.cc:2431
operations_research::Solver::fail_stamp
uint64 fail_stamp() const
The fail_stamp() is incremented after each backtrack.
Definition: constraint_solver.cc:1645
operations_research::ModelVisitor::kAllowedAssignments
static const char kAllowedAssignments[]
Definition: constraint_solver.h:3335
operations_research::ModelVisitor::~ModelVisitor
~ModelVisitor() override
Definition: constraint_solver.cc:2732
operations_research::Search::ProgressPercent
int ProgressPercent()
Definition: constraint_solver.cc:1329
operations_research::ModelVisitor::kConvexPiecewise
static const char kConvexPiecewise[]
Definition: constraint_solver.h:3341
operations_research::Search::EndNextDecision
void EndNextDecision(DecisionBuilder *const db, Decision *const d)
Definition: constraint_solver.cc:1226
operations_research::ModelVisitor::kTimeLimitArgument
static const char kTimeLimitArgument[]
Definition: constraint_solver.h:3483
operations_research::ModelVisitor::kUsageLessConstantExtension
static const char kUsageLessConstantExtension[]
Definition: constraint_solver.h:3424
operations_research::Search::~Search
~Search()
Definition: constraint_solver.cc:990
operations_research::SearchMonitor::PeriodicCheck
virtual void PeriodicCheck()
Periodic call to check limits in long running methods.
Definition: constraint_solver.cc:2889
operations_research::ModelVisitor::kOptionalArgument
static const char kOptionalArgument[]
Definition: constraint_solver.h:3464
operations_research::SearchMonitor::ApplyDecision
virtual void ApplyDecision(Decision *const d)
Before applying the decision.
Definition: constraint_solver.cc:2873
operations_research::ModelVisitor::kStartSyncOnEndOperation
static const char kStartSyncOnEndOperation[]
Definition: constraint_solver.h:3500
DCHECK_GT
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
operations_research::Demon::inhibit
void inhibit(Solver *const s)
This method inhibits the demon in the search tree below the current position.
Definition: constraint_solver.cc:199
operations_research::ModelVisitor::kInversePermutation
static const char kInversePermutation[]
Definition: constraint_solver.h:3364
operations_research::Constraint::PostAndPropagate
void PostAndPropagate()
Calls Post and then Propagate to initialize the constraints.
Definition: constraint_solver.cc:3239
operations_research::Trace::SetEndRange
void SetEndRange(IntervalVar *const var, int64 new_min, int64 new_max) override
Definition: constraint_solver.cc:3064
operations_research::Solver::MakeApplyBranchSelector
DecisionBuilder * MakeApplyBranchSelector(BranchSelector bs)
Creates a decision builder that will set the branch selector.
Definition: constraint_solver.cc:1167
operations_research::CleanVariableOnFail
void CleanVariableOnFail(IntVar *const var)
Definition: expressions.cc:6326
value
int64 value
Definition: demon_profiler.cc:43
CHECK_GT
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
operations_research::Trace::BeginDemonRun
void BeginDemonRun(Demon *const demon) override
Definition: constraint_solver.cc:2958
operations_research::ModelVisitor::kNonEqual
static const char kNonEqual[]
Definition: constraint_solver.h:3385
operations_research::Solver::SetSearchContext
void SetSearchContext(Search *search, const std::string &search_context)
Definition: constraint_solver.cc:3215
operations_research::DecisionBuilder::DebugString
std::string DebugString() const override
Definition: constraint_solver.cc:2527
operations_research::ModelVisitor::kSmartTimeCheckArgument
static const char kSmartTimeCheckArgument[]
Definition: constraint_solver.h:3476
operations_research::ModelVisitor::kSum
static const char kSum[]
Definition: constraint_solver.h:3405
kuint64max
static const uint64 kuint64max
Definition: integral_types.h:52
operations_research::StateInfo::StateInfo
StateInfo(void *pinfo, int iinfo, int d, int ld)
Definition: constraint_solver.cc:430
operations_research::Solver::MarkerType
MarkerType
This enum is used internally in private methods Solver::PushState and Solver::PopState to tag states ...
Definition: constraint_solver.h:716
operations_research::Solver::GetPropagationMonitor
PropagationMonitor * GetPropagationMonitor() const
Returns the propagation monitor.
Definition: constraint_solver.cc:3134
operations_research::AcceptNeighbor
void AcceptNeighbor(Search *const search)
Definition: constraint_solver.cc:1353
operations_research::PropagationMonitor::RemoveValue
virtual void RemoveValue(IntVar *const var, int64 value)=0
operations_research::ModelVisitor::kTransition
static const char kTransition[]
Definition: constraint_solver.h:3410
operations_research::DeleteDemonProfiler
void DeleteDemonProfiler(DemonProfiler *const monitor)
Definition: demon_profiler.cc:448
operations_research::ModelVisitor::kCountAssignedItemsExtension
static const char kCountAssignedItemsExtension[]
Extension names:
Definition: constraint_solver.h:3416
operations_research::Solver::wall_time
int64 wall_time() const
DEPRECATED: Use Now() instead.
Definition: constraint_solver.cc:1520
operations_research::LocalSearchMonitorMaster::EndAcceptNeighbor
void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
Definition: constraint_solver.cc:3171
operations_research::SequenceVar
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
Definition: constraint_solver.h:4543
operations_research::SearchMonitor
A search monitor is a simple set of callbacks to monitor all search events.
Definition: constraint_solver.h:3630
operations_research::ModelVisitor::kLateDateArgument
static const char kLateDateArgument[]
Definition: constraint_solver.h:3457
operations_research::SearchMonitor::Install
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
Definition: constraint_solver.cc:2892
macros.h
operations_research::BuildModelCache
ModelCache * BuildModelCache(Solver *const solver)
Definition: model_cache.cc:845
operations_research::ModelVisitor::kSortingConstraint
static const char kSortingConstraint[]
Definition: constraint_solver.h:3402
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::Decision::Apply
virtual void Apply(Solver *const s)=0
Apply will be called first when the decision is executed.
operations_research::Search::RightMove
void RightMove()
Definition: constraint_solver.cc:1035
operations_research::ModelVisitor::kIsEqual
static const char kIsEqual[]
Definition: constraint_solver.h:3367
operations_research::Search::Clear
void Clear()
Definition: constraint_solver.cc:1194
operations_research::Demon::DebugString
std::string DebugString() const override
Definition: constraint_solver.cc:197
operations_research::Trace::SetValues
void SetValues(IntVar *const var, const std::vector< int64 > &values) override
Definition: constraint_solver.cc:3032
operations_research::Trace::PopContext
void PopContext() override
Definition: constraint_solver.cc:2978
operations_research::ModelVisitor::kWeightedSumOfAssignedEqualVariableExtension
static const char kWeightedSumOfAssignedEqualVariableExtension[]
Definition: constraint_solver.h:3427
operations_research::ModelVisitor::kSizeXArgument
static const char kSizeXArgument[]
Definition: constraint_solver.h:3474
operations_research::ModelVisitor::kEndExpr
static const char kEndExpr[]
Definition: constraint_solver.h:3353
operations_research::ModelVisitor::kOpposite
static const char kOpposite[]
Definition: constraint_solver.h:3389
operations_research::ModelVisitor::kMinArgument
static const char kMinArgument[]
Definition: constraint_solver.h:3461
tuple_set.h
operations_research::Solver::SolveDepth
int SolveDepth() const
Gets the number of nested searches.
Definition: constraint_solver.cc:1171
operations_research::InternalSaveBooleanVarValue
void InternalSaveBooleanVarValue(Solver *const solver, IntVar *const var)
Definition: constraint_solver.cc:947
operations_research::ModelVisitor::VisitIntegerVariableEvaluatorArgument
virtual void VisitIntegerVariableEvaluatorArgument(const std::string &arg_name, const Solver::Int64ToIntVar &arguments)
Helpers.
Definition: constraint_solver.cc:2795
operations_research::ModelVisitor::BeginVisitModel
virtual void BeginVisitModel(const std::string &type_name)
--— Virtual methods for visitors --—
Definition: constraint_solver.cc:2734
WARNING
const int WARNING
Definition: log_severity.h:31
operations_research::ModelVisitor::kBranchesLimitArgument
static const char kBranchesLimitArgument[]
Definition: constraint_solver.h:3432
operations_research::Solver::IntegerCastInfo
Holds semantic information stating that the 'expression' has been cast into 'variable' using the Var(...
Definition: constraint_solver.h:254
operations_research::ModelVisitor::BeginVisitExtension
virtual void BeginVisitExtension(const std::string &type)
Definition: constraint_solver.cc:2742
operations_research::ModelVisitor::kAbs
static const char kAbs[]
Constraint and Expression types.
Definition: constraint_solver.h:3332
operations_research::ModelVisitor::VisitIntegerExpressionArgument
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *const argument)
Visit integer expression argument.
Definition: constraint_solver.cc:2790
operations_research::Queue::Freeze
void Freeze()
Definition: constraint_solver.cc:231
operations_research::ModelVisitor::kNotMember
static const char kNotMember[]
Definition: constraint_solver.h:3387
operations_research::Search::set_search_context
void set_search_context(const std::string &search_context)
Definition: constraint_solver.cc:1055
CP_DO_FAIL
#define CP_DO_FAIL(search)
Definition: constraint_solver.cc:1106
operations_research::ModelVisitor::VisitSequenceArgument
virtual void VisitSequenceArgument(const std::string &arg_name, SequenceVar *const argument)
Visit sequence argument.
Definition: constraint_solver.cc:2813
operations_research::ModelVisitor::kTargetArgument
static const char kTargetArgument[]
Definition: constraint_solver.h:3482
operations_research::PropagationMonitor::EndNestedConstraintInitialPropagation
virtual void EndNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
operations_research::Solver::NewSearch
void NewSearch(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
Definition: constraint_solver.cc:1843
operations_research::DeleteLocalSearchProfiler
void DeleteLocalSearchProfiler(LocalSearchProfiler *monitor)
Definition: local_search.cc:3841
operations_research::ModelVisitor::kCover
static const char kCover[]
Definition: constraint_solver.h:3343
operations_research::Solver::DebugString
std::string DebugString() const
!defined(SWIG)
Definition: constraint_solver.cc:1487
operations_research::Search::set_should_restart
void set_should_restart(bool s)
Definition: constraint_solver.cc:1046
operations_research::Solver::IntegerCastInfo::expression
IntExpr * expression
Definition: constraint_solver.h:260
operations_research::Search::EndInitialPropagation
void EndInitialPropagation()
Definition: constraint_solver.cc:1254
operations_research::ModelVisitor::kCountArgument
static const char kCountArgument[]
Definition: constraint_solver.h:3436
operations_research::PropagationMonitor::RegisterDemon
virtual void RegisterDemon(Demon *const demon)=0
operations_research::Queue::~Queue
~Queue()
Definition: constraint_solver.cc:229
operations_research::Solver::NextSolution
bool NextSolution()
Definition: constraint_solver.cc:2093
operations_research::ModelVisitor::kSumGreaterOrEqual
static const char kSumGreaterOrEqual[]
Definition: constraint_solver.h:3407
operations_research::Solver::stamp
uint64 stamp() const
The stamp indicates how many moves in the search tree we have performed.
Definition: constraint_solver.cc:1643
operations_research::Trace::RankFirst
void RankFirst(SequenceVar *const var, int index) override
SequenceVar modifiers.
Definition: constraint_solver.cc:3087
operations_research::ModelVisitor::kFalseConstraint
static const char kFalseConstraint[]
Definition: constraint_solver.h:3355
operations_research::ModelVisitor::kCumulativeArgument
static const char kCumulativeArgument[]
Definition: constraint_solver.h:3437
int64
int64_t int64
Definition: integral_types.h:34
operations_research::PropagationMonitor::SetStartMax
virtual void SetStartMax(IntervalVar *const var, int64 new_max)=0
operations_research::ModelVisitor::kMapDomain
static const char kMapDomain[]
Definition: constraint_solver.h:3377
operations_research::Search::ModifyDecision
Solver::DecisionModification ModifyDecision()
Definition: constraint_solver.cc:1181
constraint_solveri.h
operations_research::Solver::PROBLEM_INFEASIBLE
@ PROBLEM_INFEASIBLE
After search, the model is infeasible.
Definition: constraint_solver.h:731
operations_research::Solver::~Solver
~Solver()
Definition: constraint_solver.cc:1471
operations_research::PropagationMonitor::~PropagationMonitor
~PropagationMonitor() override
Definition: constraint_solver.cc:2900
operations_research::Queue::ExecuteAll
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
Definition: constraint_solver.cc:280
operations_research::StateInfo::left_depth
int left_depth
Definition: constraint_solver.cc:446
operations_research::Solver::CurrentlyInSolve
bool CurrentlyInSolve() const
Returns true whether the current search has been created using a Solve() call instead of a NewSearch ...
Definition: constraint_solver.cc:1746
operations_research::BaseObject::DebugString
virtual std::string DebugString() const
Definition: constraint_solver.h:3151
operations_research::DecisionBuilder::Accept
virtual void Accept(ModelVisitor *const visitor) const
Definition: constraint_solver.cc:2532
operations_research::ModelVisitor::kSumOperation
static const char kSumOperation[]
Definition: constraint_solver.h:3496
operations_research::ModelVisitor::kScalProd
static const char kScalProd[]
Definition: constraint_solver.h:3396
operations_research::ModelVisitor::kElementEqual
static const char kElementEqual[]
Definition: constraint_solver.h:3352
operations_research::ModelVisitor::kTraceOperation
static const char kTraceOperation[]
Definition: constraint_solver.h:3501
operations_research::ModelVisitor::kCapacityArgument
static const char kCapacityArgument[]
Definition: constraint_solver.h:3433
operations_research::Solver::Accept
void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
Definition: constraint_solver.cc:1693
index
int index
Definition: pack.cc:508
operations_research::Solver::GetConstraintSolverStatistics
ConstraintSolverStatistics GetConstraintSolverStatistics() const
Returns detailed cp search statistics.
Definition: constraint_solver.cc:1546
operations_research::Search::IncrementSolutionCounter
void IncrementSolutionCounter()
Definition: constraint_solver.cc:1017
operations_research::LocalSearchMonitorMaster::BeginMakeNextNeighbor
void BeginMakeNextNeighbor(const LocalSearchOperator *op) override
Definition: constraint_solver.cc:3151
operations_research::LocalSearchMonitor::EndFilterNeighbor
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
operations_research::BaseObject
A BaseObject is the root of all reversibly allocated objects.
Definition: constraint_solver.h:3147
context
GurobiMPCallbackContext * context
Definition: gurobi_interface.cc:509
operations_research::PropagationMonitor::RankNotLast
virtual void RankNotLast(SequenceVar *const var, int index)=0
operations_research::Trace::DebugString
std::string DebugString() const override
Definition: constraint_solver.cc:3121
operations_research::Solver::MakeFailDecision
Decision * MakeFailDecision()
Definition: constraint_solver.cc:1379
operations_research::ModelVisitor::kSquare
static const char kSquare[]
Definition: constraint_solver.h:3403
operations_research::ModelVisitor::kBetween
static const char kBetween[]
Definition: constraint_solver.h:3338
operations_research::ModelVisitor::kInitialState
static const char kInitialState[]
Definition: constraint_solver.h:3453
operations_research::Solver::SIMPLE_MARKER
@ SIMPLE_MARKER
Definition: constraint_solver.h:716
operations_research::Trace
Definition: constraint_solver.cc:2923
operations_research::Trace::SetStartRange
void SetStartRange(IntervalVar *const var, int64 new_min, int64 new_max) override
Definition: constraint_solver.cc:3050
operations_research::Search::should_finish
bool should_finish() const
Definition: constraint_solver.cc:1049
operations_research::Search::BeginFail
void BeginFail()
Definition: constraint_solver.cc:1246
operations_research::ModelVisitor::kVarValueWatcher
static const char kVarValueWatcher[]
Definition: constraint_solver.h:3413
operations_research::ModelVisitor::kModuloArgument
static const char kModuloArgument[]
Definition: constraint_solver.h:3462
operations_research::Solver::MemoryUsage
static int64 MemoryUsage()
Current memory usage in bytes.
Definition: constraint_solver.cc:1518
operations_research::Solver::NO_CHANGE
@ NO_CHANGE
Keeps the default behavior, i.e.
Definition: constraint_solver.h:693
operations_research::Trace::EndNestedConstraintInitialPropagation
void EndNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested) override
Definition: constraint_solver.cc:2947
operations_research::Solver::SWITCH_BRANCHES
@ SWITCH_BRANCHES
Applies right branch first.
Definition: constraint_solver.h:711
operations_research::ModelVisitor::kDurationMaxArgument
static const char kDurationMaxArgument[]
Definition: constraint_solver.h:3440
operations_research::Trail::rev_object_array_memory_
std::vector< BaseObject ** > rev_object_array_memory_
Definition: constraint_solver.cc:736
operations_research::Queue::reset_action_on_fail
void reset_action_on_fail()
Definition: constraint_solver.cc:371
operations_research::Trace::SetMax
void SetMax(IntVar *const var, int64 new_max) override
Definition: constraint_solver.cc:3008
operations_research::Trace::RemoveValue
void RemoveValue(IntVar *const var, int64 value) override
Definition: constraint_solver.cc:3020
operations_research::Solver::NO_MORE_SOLUTIONS
@ NO_MORE_SOLUTIONS
After failed NextSolution and before EndSearch.
Definition: constraint_solver.h:729
operations_research::Search::search_depth
int search_depth() const
Definition: constraint_solver.cc:1042
operations_research::Solver::HasName
bool HasName(const PropagationBaseObject *object) const
Returns whether the object has been named or not.
Definition: constraint_solver.cc:2485
operations_research::Queue::set_variable_to_clean_on_fail
void set_variable_to_clean_on_fail(IntVar *var)
Definition: constraint_solver.cc:366
operations_research::ModelVisitor::kPerformedExpr
static const char kPerformedExpr[]
Definition: constraint_solver.h:3393
operations_research::Decision::Accept
virtual void Accept(DecisionVisitor *const visitor) const
Accepts the given visitor.
Definition: constraint_solver.cc:2536
operations_research::Constraint::Var
virtual IntVar * Var()
Creates a Boolean variable representing the status of the constraint (false = constraint is violated,...
Definition: constraint_solver.cc:3257
operations_research::ModelVisitor::kNoCycle
static const char kNoCycle[]
Definition: constraint_solver.h:3384
operations_research::Solver::Int64ToIntVar
std::function< IntVar *(int64)> Int64ToIntVar
Definition: constraint_solver.h:744
operations_research::LocalSearchFilter
Local Search Filters are used for fast neighbor pruning.
Definition: constraint_solveri.h:1719
ConstraintSolverFailsHere
void ConstraintSolverFailsHere()
Definition: constraint_solver.cc:95
operations_research::Trace::SetRange
void SetRange(IntVar *const var, int64 new_min, int64 new_max) override
Definition: constraint_solver.cc:3014
operations_research::Queue::Queue
Queue(Solver *const s)
Definition: constraint_solver.cc:219
operations_research::BuildDemonProfiler
DemonProfiler * BuildDemonProfiler(Solver *const solver)
Definition: demon_profiler.cc:440
operations_research::PropagationBaseObject::HasName
bool HasName() const
Returns whether the object has been named or not.
Definition: constraint_solver.cc:2513
operations_research::Trace::PushContext
void PushContext(const std::string &context) override
Definition: constraint_solver.cc:2974
operations_research::Solver::PopState
void PopState()
Definition: constraint_solver.cc:1561
file.h
operations_research::RestoreBoolValue
void RestoreBoolValue(IntVar *const var)
Definition: expressions.cc:6347
operations_research::ModelVisitor::kEarlyDateArgument
static const char kEarlyDateArgument[]
Definition: constraint_solver.h:3443
operations_research::ModelVisitor::kTrueConstraint
static const char kTrueConstraint[]
Definition: constraint_solver.h:3411
operations_research::Search::set_backtrack_at_the_end_of_the_search
void set_backtrack_at_the_end_of_the_search(bool restore)
Definition: constraint_solver.cc:1039
operations_research::ModelVisitor::kSolutionLimitArgument
static const char kSolutionLimitArgument[]
Definition: constraint_solver.h:3477
operations_research::ModelVisitor::kActiveArgument
static const char kActiveArgument[]
argument names:
Definition: constraint_solver.h:3430
operations_research::ModelVisitor::VisitIntegerMatrixArgument
virtual void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &tuples)
Definition: constraint_solver.cc:2787
operations_research::LocalSearchMonitorMaster
Definition: constraint_solver.cc:3140
a
int64 a
Definition: constraint_solver/table.cc:42
operations_research::ModelVisitor::kSizeArgument
static const char kSizeArgument[]
Definition: constraint_solver.h:3473
operations_research::ModelVisitor::kEarlyCostArgument
static const char kEarlyCostArgument[]
Definition: constraint_solver.h:3442
operations_research::PropagationBaseObject::BaseName
virtual std::string BaseName() const
Returns a base name for automatic naming.
Definition: constraint_solver.cc:2515
constraint_solver.h
operations_research::Solver::RestartSearch
void RestartSearch()
Definition: constraint_solver.cc:1985
operations_research::ModelVisitor::kEndsArgument
static const char kEndsArgument[]
Definition: constraint_solver.h:3446
operations_research::LocalSearchMonitorMaster::BeginFiltering
void BeginFiltering(const LocalSearchFilter *filter) override
Definition: constraint_solver.cc:3176
operations_research::Solver::REVERSIBLE_ACTION
@ REVERSIBLE_ACTION
Definition: constraint_solver.h:716
operations_research::ModelVisitor::kElement
static const char kElement[]
Definition: constraint_solver.h:3351
operations_research::ModelVisitor::EndVisitModel
virtual void EndVisitModel(const std::string &type_name)
Definition: constraint_solver.cc:2735
operations_research::Solver::IndexFilter1
std::function< bool(int64)> IndexFilter1
Definition: constraint_solver.h:742
operations_research::ModelVisitor::kIndexArgument
static const char kIndexArgument[]
Definition: constraint_solver.h:3452
operations_research::Solver::IntVar
friend class IntVar
Definition: constraint_solver.h:2941
operations_research::Solver::CheckAssignment
bool CheckAssignment(Assignment *const solution)
Checks whether the given assignment satisfies all relevant constraints.
Definition: constraint_solver.cc:2293
operations_research::SimpleRevFIFO
This class represent a reversible FIFO structure.
Definition: constraint_solveri.h:145
operations_research::ModelVisitor::kFinalStatesArgument
static const char kFinalStatesArgument[]
Definition: constraint_solver.h:3449
operations_research::Solver::AddCastConstraint
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...
Definition: constraint_solver.cc:1681
operations_research::ModelVisitor::VisitSequenceVariable
virtual void VisitSequenceVariable(const SequenceVar *const variable)
Definition: constraint_solver.cc:2774
operations_research::LocalSearchMonitor
Definition: constraint_solveri.h:1915
operations_research::ModelVisitor::kProductOperation
static const char kProductOperation[]
Definition: constraint_solver.h:3498
operations_research::Assignment
An Assignment is a variable -> domains mapping, used to report solutions to the user.
Definition: constraint_solver.h:5033
operations_research::GetProcessMemoryUsage
int64 GetProcessMemoryUsage()
Definition: sysinfo.cc:85
operations_research::Search::push_monitor
void push_monitor(SearchMonitor *const m)
Definition: constraint_solver.cc:1188
operations_research::PropagationMonitor::BeginConstraintInitialPropagation
virtual void BeginConstraintInitialPropagation(Constraint *const constraint)=0
Propagation events.
operations_research::LocalSearchMonitor::EndOperatorStart
virtual void EndOperatorStart()=0
operations_research::ModelVisitor::kCircuit
static const char kCircuit[]
Definition: constraint_solver.h:3340
operations_research::DecisionVisitor::VisitUnknownDecision
virtual void VisitUnknownDecision()
Definition: constraint_solver.cc:2543
operations_research::BuildLocalSearchProfiler
LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)
Definition: local_search.cc:3834
operations_research::Solver::MakePrintModelVisitor
ModelVisitor * MakePrintModelVisitor()
Prints the model.
Definition: utilities.cc:807
gtl::FindOrNull
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:41
operations_research::IntervalVar::Accept
virtual void Accept(ModelVisitor *const visitor) const =0
Accepts the given visitor.
operations_research::Trail::rev_doubles_
CompressedTrail< double > rev_doubles_
Definition: constraint_solver.cc:727
operations_research::Trace::RegisterDemon
void RegisterDemon(Demon *const demon) override
Definition: constraint_solver.cc:2954
operations_research::ModelVisitor::kVariableGroupExtension
static const char kVariableGroupExtension[]
Definition: constraint_solver.h:3425
operations_research::InstallLocalSearchProfiler
void InstallLocalSearchProfiler(LocalSearchProfiler *monitor)
Definition: local_search.cc:3830
operations_research::ModelVisitor::kScalProdEqual
static const char kScalProdEqual[]
Definition: constraint_solver.h:3397
operations_research::Queue
Definition: constraint_solver.cc:215
operations_research::ModelVisitor::kInt64ToBoolExtension
static const char kInt64ToBoolExtension[]
Definition: constraint_solver.h:3418
operations_research::Trace::SetValue
void SetValue(IntVar *const var, int64 value) override
Definition: constraint_solver.cc:3024
uint32
unsigned int uint32
Definition: integral_types.h:38
operations_research::CastConstraint
Cast constraints are special channeling constraints designed to keep a variable in sync with an expre...
Definition: constraint_solver.h:3615
operations_research::Search::BeginInitialPropagation
void BeginInitialPropagation()
Definition: constraint_solver.cc:1250
operations_research::PropagationBaseObject
NOLINT.
Definition: constraint_solver.h:3162
operations_research::ModelVisitor::EndVisitConstraint
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *const constraint)
Definition: constraint_solver.cc:2739
operations_research::Solver::BranchSelector
std::function< DecisionModification()> BranchSelector
Definition: constraint_solver.h:752
CP_TRY
#define CP_TRY(search)
Definition: constraint_solver.cc:1101
operations_research::DecisionVisitor::VisitSetVariableValue
virtual void VisitSetVariableValue(IntVar *const var, int64 value)
Definition: constraint_solver.cc:2540
operations_research::LocalSearchMonitor::BeginOperatorStart
virtual void BeginOperatorStart()=0
Local search operator events.
operations_research::ModelVisitor::kVariableArgument
static const char kVariableArgument[]
Definition: constraint_solver.h:3488
operations_research::PropagationMonitor::SetEndMin
virtual void SetEndMin(IntervalVar *const var, int64 new_min)=0
operations_research::SearchMonitor::EnterSearch
virtual void EnterSearch()
Beginning of the search.
Definition: constraint_solver.cc:2867
operations_research::ModelVisitor::kValueArgument
static const char kValueArgument[]
Definition: constraint_solver.h:3486
operations_research::ModelVisitor::kPositionXArgument
static const char kPositionXArgument[]
Definition: constraint_solver.h:3466
operations_research::PropagationMonitor::SetStartRange
virtual void SetStartRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
operations_research::Solver::NOT_SET
@ NOT_SET
Definition: constraint_solver.h:735
operations_research::Solver::AddBacktrackAction
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...
Definition: constraint_solver.cc:1589
operations_research::ModelVisitor::kIntervalArgument
static const char kIntervalArgument[]
Definition: constraint_solver.h:3454
operations_research::Queue::kTestPeriod
static constexpr int64 kTestPeriod
Definition: constraint_solver.cc:217
operations_research::LocalSearchMonitor::LocalSearchMonitor
LocalSearchMonitor(Solver *const solver)
Definition: constraint_solver.cc:2909
operations_research::PropagationBaseObject::DebugString
std::string DebugString() const override
Definition: constraint_solver.h:3167
operations_research::Trace::SetStartMax
void SetStartMax(IntervalVar *const var, int64 new_max) override
Definition: constraint_solver.cc:3046
operations_research::ModelVisitor::kEndMaxArgument
static const char kEndMaxArgument[]
Definition: constraint_solver.h:3444
operations_research::Queue::AfterFailure
void AfterFailure()
Definition: constraint_solver.cc:337
operations_research::ModelVisitor::EndVisitIntegerExpression
virtual void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
Definition: constraint_solver.cc:2747
operations_research::Search::RefuteDecision
void RefuteDecision(Decision *const d)
Definition: constraint_solver.cc:1241
operations_research::LocalSearchMonitorMaster::EndOperatorStart
void EndOperatorStart() override
Definition: constraint_solver.cc:3148
CHECK_EQ
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
operations_research::LocalSearchMonitor::EndMakeNextNeighbor
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
operations_research::ModelVisitor::BeginVisitIntegerExpression
virtual void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
Definition: constraint_solver.cc:2745
operations_research::ModelVisitor::kIsMember
static const char kIsMember[]
Definition: constraint_solver.h:3372
operations_research::ModelVisitor::VisitIntervalArrayArgument
virtual void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments)
Definition: constraint_solver.cc:2808
operations_research::ModelVisitor::EndVisitExtension
virtual void EndVisitExtension(const std::string &type)
Definition: constraint_solver.cc:2743
operations_research::Trace::StartProcessingIntegerVariable
void StartProcessingIntegerVariable(IntVar *const var) override
Definition: constraint_solver.cc:2966
operations_research::LocalSearchMonitorMaster::EndMakeNextNeighbor
void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta) override
Definition: constraint_solver.cc:3154
operations_research::SequenceVar::size
int64 size() const
Returns the number of interval vars in the sequence.
Definition: constraint_solver.h:4619
operations_research::ModelVisitor::kIntervalVariable
static const char kIntervalVariable[]
Definition: constraint_solver.h:3363
operations_research::ModelVisitor::kNullIntersect
static const char kNullIntersect[]
Definition: constraint_solver.h:3388
operations_research::Constraint::InitialPropagate
virtual void InitialPropagate()=0
This method performs the initial propagation of the constraint.
operations_research::ModelVisitor::kAssumePathsArgument
static const char kAssumePathsArgument[]
Definition: constraint_solver.h:3431
operations_research::ModelVisitor::kInt64ToInt64Extension
static const char kInt64ToInt64Extension[]
Definition: constraint_solver.h:3419
operations_research::BuildLocalSearchMonitorMaster
LocalSearchMonitor * BuildLocalSearchMonitorMaster(Solver *const s)
Definition: constraint_solver.cc:3202
operations_research::Trace::Trace
Trace(Solver *const s)
Definition: constraint_solver.cc:2925
operations_research::ModelVisitor::kTuplesArgument
static const char kTuplesArgument[]
Definition: constraint_solver.h:3485
operations_research::SimpleRevFIFO::Iterator
This iterator is not stable with respect to deletion.
Definition: constraint_solveri.h:156
operations_research::PropagationMonitor::SetEndMax
virtual void SetEndMax(IntervalVar *const var, int64 new_max)=0
operations_research::Solver::CheckFail
void CheckFail()
Definition: constraint_solver.h:2981
operations_research::DecisionBuilder
A DecisionBuilder is responsible for creating the search tree.
Definition: constraint_solver.h:3263
operations_research::Solver::unchecked_solutions
int64 unchecked_solutions() const
The number of unchecked solutions found by local search.
Definition: constraint_solver.cc:1530
operations_research::DecisionVisitor::VisitSplitVariableDomain
virtual void VisitSplitVariableDomain(IntVar *const var, int64 value, bool start_with_lower_half)
Definition: constraint_solver.cc:2541
operations_research::Solver::CastExpression
IntExpr * CastExpression(const IntVar *const var) const
!defined(SWIG)
Definition: constraint_solver.cc:2437
operations_research::ModelVisitor::kPartialArgument
static const char kPartialArgument[]
Definition: constraint_solver.h:3465
operations_research::ModelVisitor::kScalProdGreaterOrEqual
static const char kScalProdGreaterOrEqual[]
Definition: constraint_solver.h:3398
operations_research::PropagationMonitor::SetStartMin
virtual void SetStartMin(IntervalVar *const var, int64 new_min)=0
IntervalVar modifiers.
operations_research::ModelVisitor::kRelaxedMinOperation
static const char kRelaxedMinOperation[]
Definition: constraint_solver.h:3495
operations_research::operator<<
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
Definition: constraint_solver/assignment.cc:1089
operations_research::LocalSearchMonitor::BeginFiltering
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
operations_research::SearchMonitor::BeginNextDecision
virtual void BeginNextDecision(DecisionBuilder *const b)
Before calling DecisionBuilder::Next.
Definition: constraint_solver.cc:2870
operations_research::ModelVisitor::kValuesArgument
static const char kValuesArgument[]
Definition: constraint_solver.h:3487
operations_research::ModelVisitor::kLess
static const char kLess[]
Definition: constraint_solver.h:3373
ct
const Constraint * ct
Definition: demon_profiler.cc:42
operations_research::ModelVisitor::kIndex2Argument
static const char kIndex2Argument[]
Definition: constraint_solver.h:3451
operations_research::SearchMonitor::kNoProgress
static constexpr int kNoProgress
Definition: constraint_solver.h:3632
operations_research::ModelVisitor::kIsBetween
static const char kIsBetween[]
Definition: constraint_solver.h:3365
operations_research::PropagationMonitor::PushContext
virtual void PushContext(const std::string &context)=0
operations_research::PropagationMonitor::RemoveValues
virtual void RemoveValues(IntVar *const var, const std::vector< int64 > &values)=0
operations_research::Search::unchecked_solution_counter
int64 unchecked_solution_counter() const
Definition: constraint_solver.cc:1020
operations_research::Solver::failures
int64 failures() const
The number of failures encountered since the creation of the solver.
Definition: constraint_solver.h:994
operations_research::ModelVisitor::kIndexOf
static const char kIndexOf[]
Definition: constraint_solver.h:3337
operations_research::AcceptDelta
bool AcceptDelta(Search *const search, Assignment *delta, Assignment *deltadelta)
Definition: constraint_solver.cc:1348
operations_research::ModelVisitor::kDisjunctive
static const char kDisjunctive[]
Definition: constraint_solver.h:3347
operations_research::LocalSearchMonitor::EndFiltering
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
uint64
uint64_t uint64
Definition: integral_types.h:39
operations_research::Solver::Now
absl::Time Now() const
The 'absolute time' as seen by the solver.
Definition: constraint_solver.cc:1524
operations_research::LocalSearchMonitorMaster::Install
void Install() override
Registers itself on the solver such that it gets notified of the search and propagation events.
Definition: constraint_solver.cc:3192
operations_research::Solver::Action
std::function< void(Solver *)> Action
Definition: constraint_solver.h:754
operations_research::LocalSearchMonitorMaster::EndFiltering
void EndFiltering(const LocalSearchFilter *filter, bool reject) override
Definition: constraint_solver.cc:3179
operations_research::Trail::rev_uint64s_
CompressedTrail< uint64 > rev_uint64s_
Definition: constraint_solver.cc:726
operations_research::PropagationMonitor::EndDemonRun
virtual void EndDemonRun(Demon *const demon)=0
operations_research::Trail::Trail
Trail(int block_size, ConstraintSolverParameters::TrailCompression compression_level)
Definition: constraint_solver.cc:740
CP_ON_FAIL
#define CP_ON_FAIL
Definition: constraint_solver.cc:1105
operations_research::Constraint::Post
virtual void Post()=0
This method is called when the constraint is processed by the solver.
operations_research::ModelVisitor::kCumulative
static const char kCumulative[]
Definition: constraint_solver.h:3344
operations_research::Solver::MakeConstraintAdder
DecisionBuilder * MakeConstraintAdder(Constraint *const ct)
Returns a decision builder that will add the given constraint to the model.
Definition: constraint_solver.cc:2368
DCHECK
#define DCHECK(condition)
Definition: base/logging.h:884
operations_research::ModelVisitor::kPower
static const char kPower[]
Definition: constraint_solver.h:3394
operations_research::ModelVisitor::VisitInt64ToInt64Extension
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64 index_min, int64 index_max)
Definition: constraint_solver.cc:2840
operations_research::ModelVisitor::kIntervalsArgument
static const char kIntervalsArgument[]
Definition: constraint_solver.h:3455
operations_research::Solver::model_name
std::string model_name() const
Returns the name of the model.
Definition: constraint_solver.cc:1397
operations_research::ModelVisitor::kIntervalBinaryRelation
static const char kIntervalBinaryRelation[]
Definition: constraint_solver.h:3360
operations_research::IntervalVar
Interval variables are often used in scheduling.
Definition: constraint_solver.h:4389
operations_research::Trace::SetEndMax
void SetEndMax(IntervalVar *const var, int64 new_max) override
Definition: constraint_solver.cc:3060
operations_research::DecisionVisitor
A DecisionVisitor is used to inspect a decision.
Definition: constraint_solver.h:3244
operations_research::SearchMonitor::AfterDecision
virtual void AfterDecision(Decision *const d, bool apply)
Just after refuting or applying the decision, apply is true after Apply.
Definition: constraint_solver.cc:2875
operations_research::PropagationMonitor::SetValues
virtual void SetValues(IntVar *const var, const std::vector< int64 > &values)=0
operations_research::LocalSearchMonitorMaster::BeginAcceptNeighbor
void BeginAcceptNeighbor(const LocalSearchOperator *op) override
Definition: constraint_solver.cc:3168
operations_research::Solver::GetLocalSearchMonitor
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
Definition: constraint_solver.cc:3211
operations_research::ModelVisitor::kSearchLimitExtension
static const char kSearchLimitExtension[]
Definition: constraint_solver.h:3421
operations_research::Trace::SetDurationMax
void SetDurationMax(IntervalVar *const var, int64 new_max) override
Definition: constraint_solver.cc:3073
operations_research::Search::ApplyDecision
void ApplyDecision(Decision *const d)
Definition: constraint_solver.cc:1231
operations_research::DecisionVisitor::VisitRankFirstInterval
virtual void VisitRankFirstInterval(SequenceVar *const sequence, int index)
Definition: constraint_solver.cc:2548
operations_research::ModelVisitor::kObjectiveExtension
static const char kObjectiveExtension[]
Definition: constraint_solver.h:3420
operations_research::Queue::increase_stamp
void increase_stamp()
Definition: constraint_solver.cc:357
operations_research::ModelVisitor::kSizeYArgument
static const char kSizeYArgument[]
Definition: constraint_solver.h:3475
operations_research::Search::left_search_depth
int left_search_depth() const
Definition: constraint_solver.cc:1044
operations_research::ModelVisitor::kRelationArgument
static const char kRelationArgument[]
Definition: constraint_solver.h:3469
operations_research::AcceptUncheckedNeighbor
void AcceptUncheckedNeighbor(Search *const search)
Definition: constraint_solver.cc:1355
operations_research::Solver::Fail
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
Definition: constraint_solver.cc:2416
operations_research::Trace::~Trace
~Trace() override
Definition: constraint_solver.cc:2927
operations_research::LocalSearchMonitorMaster::BeginFilterNeighbor
void BeginFilterNeighbor(const LocalSearchOperator *op) override
Definition: constraint_solver.cc:3160
operations_research::IntVar::Accept
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
Definition: expressions.cc:7318
operations_research::DecisionBuilder::AppendMonitors
virtual void AppendMonitors(Solver *const solver, std::vector< SearchMonitor * > *const extras)
This method will be called at the start of the search.
Definition: constraint_solver.cc:2529
operations_research::LocalSearchMonitorMaster::BeginOperatorStart
void BeginOperatorStart() override
Local search operator events.
Definition: constraint_solver.cc:3145
operations_research::Search::Accept
void Accept(ModelVisitor *const visitor) const
Definition: constraint_solver.cc:1337
operations_research::Solver::SearchLeftDepth
int SearchLeftDepth() const
Gets the search left depth of the current active search.
Definition: constraint_solver.cc:1177
operations_research::Trail::rev_object_memory_
std::vector< BaseObject * > rev_object_memory_
Definition: constraint_solver.cc:735
DCHECK_GE
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
operations_research::ModelVisitor::VisitSequenceArrayArgument
virtual void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments)
Definition: constraint_solver.cc:2818
operations_research::SearchMonitor::LocalOptimum
virtual bool LocalOptimum()
When a local optimum is reached.
Definition: constraint_solver.cc:2883
operations_research::ModelVisitor::VisitIntegerVariableArrayArgument
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
Definition: constraint_solver.cc:2798
operations_research::Trace::SetRange
void SetRange(IntExpr *const expr, int64 new_min, int64 new_max) override
Definition: constraint_solver.cc:2995
operations_research::Constraint
A constraint is the main modeling object.
Definition: constraint_solver.h:3579
operations_research::Search::AcceptSolution
bool AcceptSolution()
Definition: constraint_solver.cc:1258
operations_research::Trail::rev_bool_value_
std::vector< bool > rev_bool_value_
Definition: constraint_solver.cc:731
operations_research::Queue::set_action_on_fail
void set_action_on_fail(Solver::Action a)
Definition: constraint_solver.cc:361
operations_research::Solver
Solver Class.
Definition: constraint_solver.h:248
operations_research::ModelVisitor::kLeftArgument
static const char kLeftArgument[]
Definition: constraint_solver.h:3458
operations_research::Queue::EnqueueVar
void EnqueueVar(Demon *const demon)
Definition: constraint_solver.cc:318
operations_research::ModelVisitor::kStartMaxArgument
static const char kStartMaxArgument[]
Definition: constraint_solver.h:3478
operations_research::Trace::SetDurationMin
void SetDurationMin(IntervalVar *const var, int64 new_min) override
Definition: constraint_solver.cc:3069
operations_research::Solver::SENTINEL
@ SENTINEL
Definition: constraint_solver.h:716
operations_research::ModelVisitor::kConditionalExpr
static const char kConditionalExpr[]
Definition: constraint_solver.h:3339
operations_research::ModelVisitor::kAbsEqual
static const char kAbsEqual[]
Definition: constraint_solver.h:3333
operations_research::Solver::KEEP_LEFT
@ KEEP_LEFT
Right branches are ignored.
Definition: constraint_solver.h:698
operations_research::Trace::SetMin
void SetMin(IntVar *const var, int64 new_min) override
IntVar modifiers.
Definition: constraint_solver.cc:3002
operations_research::Queue::ProcessConstraints
void ProcessConstraints()
Definition: constraint_solver.cc:381
operations_research::PropagationMonitor
Definition: constraint_solveri.h:1851
operations_research::Trace::RemoveValues
void RemoveValues(IntVar *const var, const std::vector< int64 > &values) override
Definition: constraint_solver.cc:3036
operations_research::ModelVisitor::kDurationMinArgument
static const char kDurationMinArgument[]
Definition: constraint_solver.h:3441
operations_research::ModelVisitor::kPathCumul
static const char kPathCumul[]
Definition: constraint_solver.h:3391
operations_research::ModelVisitor::kExpressionArgument
static const char kExpressionArgument[]
Definition: constraint_solver.h:3447
operations_research::Search::Search
Search(Solver *const s, int)
Definition: constraint_solver.cc:974
operations_research::SearchMonitor::NoMoreSolutions
virtual void NoMoreSolutions()
When the search tree is finished.
Definition: constraint_solver.cc:2882
operations_research::SearchMonitor::AcceptDelta
virtual bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
Definition: constraint_solver.cc:2884
operations_research::StateInfo::ptr_info
void * ptr_info
Definition: constraint_solver.cc:443
operations_research::ModelVisitor::kCountEqual
static const char kCountEqual[]
Definition: constraint_solver.h:3342
operations_research::ModelVisitor::kEndMinArgument
static const char kEndMinArgument[]
Definition: constraint_solver.h:3445
operations_research::Demon
A Demon is the base element of a propagation queue.
Definition: constraint_solver.h:3296
operations_research::Search::RestartSearch
void RestartSearch()
Definition: constraint_solver.cc:1217
operations_research::Trace::RankNotLast
void RankNotLast(SequenceVar *const var, int index) override
Definition: constraint_solver.cc:3099
operations_research::ModelVisitor::kFailuresLimitArgument
static const char kFailuresLimitArgument[]
Definition: constraint_solver.h:3448
operations_research::Demon::desinhibit
void desinhibit(Solver *const s)
This method un-inhibits the demon that was previously inhibited.
Definition: constraint_solver.cc:205
operations_research::Solver::IndexEvaluator1
std::function< int64(int64)> IndexEvaluator1
Callback typedefs.
Definition: constraint_solver.h:738
operations_research::Solver::Solver
Solver(const std::string &name)
Solver API.
Definition: constraint_solver.cc:1417
operations_research::ModelVisitor::kUsageEqualVariableExtension
static const char kUsageEqualVariableExtension[]
Definition: constraint_solver.h:3422
operations_research::ModelVisitor::kModulo
static const char kModulo[]
Definition: constraint_solver.h:3383
operations_research::ModelVisitor::kRightArgument
static const char kRightArgument[]
Definition: constraint_solver.h:3470
operations_research::Search::AtSolution
bool AtSolution()
Definition: constraint_solver.cc:1271
operations_research::Solver::AddPropagationMonitor
void AddPropagationMonitor(PropagationMonitor *const monitor)
Adds the propagation monitor to the solver.
Definition: constraint_solver.cc:3129
operations_research::ModelVisitor::kDistribute
static const char kDistribute[]
Definition: constraint_solver.h:3348
operations_research::Solver::IsProfilingEnabled
bool IsProfilingEnabled() const
Returns whether we are profiling the solver.
Definition: constraint_solver.cc:173
operations_research::Search::PeriodicCheck
void PeriodicCheck()
Definition: constraint_solver.cc:1325
operations_research::PropagationMonitor::RankFirst
virtual void RankFirst(SequenceVar *const var, int index)=0
SequenceVar modifiers.
stl_util.h
operations_research::Trace::SetDurationRange
void SetDurationRange(IntervalVar *const var, int64 new_min, int64 new_max) override
Definition: constraint_solver.cc:3077
operations_research::Solver::MakeSearchTrace
SearchMonitor * MakeSearchTrace(const std::string &prefix)
Creates a search monitor that will trace precisely the behavior of the search.
Definition: search.cc:394
operations_research::SearchMonitor::RefuteDecision
virtual void RefuteDecision(Decision *const d)
Before refuting the decision.
Definition: constraint_solver.cc:2874
operations_research::Search::Search
Search(Solver *const s)
Definition: constraint_solver.cc:955
operations_research::Search::ExitSearch
void ExitSearch()
Definition: constraint_solver.cc:1212
operations_research::ModelVisitor::kIsGreaterOrEqual
static const char kIsGreaterOrEqual[]
Definition: constraint_solver.h:3369
operations_research::Trace::SetEndMin
void SetEndMin(IntervalVar *const var, int64 new_min) override
Definition: constraint_solver.cc:3056
operations_research::BuildTrace
PropagationMonitor * BuildTrace(Solver *const s)
Definition: constraint_solver.cc:3127
operations_research::Trail
Definition: constraint_solver.cc:723
operations_research::Search::IncrementUncheckedSolutionCounter
void IncrementUncheckedSolutionCounter()
Definition: constraint_solver.cc:1019
operations_research::SearchMonitor::AtSolution
virtual bool AtSolution()
This method is called when a valid solution is found.
Definition: constraint_solver.cc:2881
operations_research::Search::created_by_solve
bool created_by_solve() const
Definition: constraint_solver.cc:1028
operations_research::SearchMonitor::AcceptSolution
virtual bool AcceptSolution()
This method is called when a solution is found.
Definition: constraint_solver.cc:2880
operations_research::DecisionVisitor::VisitScheduleOrExpedite
virtual void VisitScheduleOrExpedite(IntervalVar *const var, int64 est)
Definition: constraint_solver.cc:2546
operations_research::ModelVisitor::kIsLess
static const char kIsLess[]
Definition: constraint_solver.h:3370
operations_research::Trace::RemoveInterval
void RemoveInterval(IntVar *const var, int64 imin, int64 imax) override
Definition: constraint_solver.cc:3028
operations_research::Search::BeginNextDecision
void BeginNextDecision(DecisionBuilder *const db)
Definition: constraint_solver.cc:1221
operations_research::ModelVisitor::kDeviation
static const char kDeviation[]
Definition: constraint_solver.h:3345
operations_research::ModelVisitor::kSequenceVariable
static const char kSequenceVariable[]
Definition: constraint_solver.h:3401
operations_research::ModelVisitor::kPack
static const char kPack[]
Definition: constraint_solver.h:3390
operations_research::SearchMonitor::AcceptNeighbor
virtual void AcceptNeighbor()
After accepting a neighbor during local search.
Definition: constraint_solver.cc:2887
operations_research::Solver::VAR_PRIORITY
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
Definition: constraint_solver.h:614
operations_research::Trail::rev_int_memory_
std::vector< int * > rev_int_memory_
Definition: constraint_solver.cc:732
operations_research::Solver::IN_ROOT_NODE
@ IN_ROOT_NODE
Executing the root node.
Definition: constraint_solver.h:723
operations_research::Search::EnterSearch
void EnterSearch()
Definition: constraint_solver.cc:1202
operations_research::PropagationBaseObject::FreezeQueue
void FreezeQueue()
This method freezes the propagation queue.
Definition: constraint_solver.h:3178
operations_research::Constraint::Accept
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
Definition: constraint_solver.cc:3247
operations_research::Search::should_restart
bool should_restart() const
Definition: constraint_solver.cc:1047
operations_research::Search::LocalOptimum
bool LocalOptimum()
Definition: constraint_solver.cc:1288
operations_research::Solver::FinishCurrentSearch
void FinishCurrentSearch()
Tells the solver to kill or restart the current search.
Definition: constraint_solver.cc:2427
operations_research::IntExpr::Accept
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
Definition: constraint_solver.cc:3261
operations_research::ModelVisitor::kIsLessOrEqual
static const char kIsLessOrEqual[]
Definition: constraint_solver.h:3371
operations_research::ModelVisitor::kSequencesArgument
static const char kSequencesArgument[]
Definition: constraint_solver.h:3472
operations_research::Solver::InstrumentsVariables
bool InstrumentsVariables() const
Returns whether we are tracing variables.
Definition: constraint_solver.cc:183
operations_research::Solver::SetBranchSelector
void SetBranchSelector(BranchSelector bs)
Sets the given branch selector on the current active search.
Definition: constraint_solver.cc:1152
operations_research::SequenceVar::Interval
IntervalVar * Interval(int index) const
Returns the index_th interval of the sequence.
Definition: sched_search.cc:50
operations_research::Search::search_context
std::string search_context() const
Definition: constraint_solver.cc:1058
operations_research::Trace::RankLast
void RankLast(SequenceVar *const var, int index) override
Definition: constraint_solver.cc:3095
operations_research::PropagationMonitor::EndProcessingIntegerVariable
virtual void EndProcessingIntegerVariable(IntVar *const var)=0
DCHECK_EQ
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
operations_research::PropagationMonitor::RemoveInterval
virtual void RemoveInterval(IntVar *const var, int64 imin, int64 imax)=0
operations_research::ModelVisitor::kGlobalCardinality
static const char kGlobalCardinality[]
Definition: constraint_solver.h:3356
operations_research::ModelVisitor::kMaxArgument
static const char kMaxArgument[]
Definition: constraint_solver.h:3459
operations_research::ModelVisitor::kSumEqual
static const char kSumEqual[]
Definition: constraint_solver.h:3406
operations_research::LocalSearchMonitorMaster::Add
void Add(LocalSearchMonitor *monitor)
Definition: constraint_solver.cc:3184
operations_research::Solver::kNumPriorities
static constexpr int kNumPriorities
Number of priorities for demons.
Definition: constraint_solver.h:265
operations_research::ModelVisitor::kDelayedPathCumul
static const char kDelayedPathCumul[]
Definition: constraint_solver.h:3392
delta
int64 delta
Definition: resource.cc:1684
operations_research::Search::LeftMove
void LeftMove()
Definition: constraint_solver.cc:1031
operations_research::Solver::ExportProfilingOverview
void ExportProfilingOverview(const std::string &filename)
Exports the profiling information in a human readable overview.
Definition: demon_profiler.cc:430
operations_research::SearchMonitor::EndNextDecision
virtual void EndNextDecision(DecisionBuilder *const b, Decision *const d)
After calling DecisionBuilder::Next, along with the returned decision.
Definition: constraint_solver.cc:2871
operations_research::LocalSearchProfiler
Definition: local_search.cc:3619
operations_research::Solver::NORMAL_PRIORITY
@ NORMAL_PRIORITY
NORMAL_PRIORITY is the highest priority: Demons will be processed first.
Definition: constraint_solver.h:617
operations_research::PropagationMonitor::SetPerformed
virtual void SetPerformed(IntervalVar *const var, bool value)=0
b
int64 b
Definition: constraint_solver/table.cc:43
operations_research::PropagationBaseObject::set_name
void set_name(const std::string &name)
Definition: constraint_solver.cc:2509
DISALLOW_COPY_AND_ASSIGN
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
operations_research::Trace::EndConstraintInitialPropagation
void EndConstraintInitialPropagation(Constraint *const constraint) override
Definition: constraint_solver.cc:2935
operations_research::IntExpr
The class IntExpr is the base of all integer expressions in constraint programming.
Definition: constraint_solver.h:3831
operations_research::ModelVisitor::kGreater
static const char kGreater[]
Definition: constraint_solver.h:3357
operations_research::Solver::DecisionModification
DecisionModification
The Solver is responsible for creating the search tree.
Definition: constraint_solver.h:690
operations_research::Solver::solutions
int64 solutions() const
The number of solutions found since the start of the search.
Definition: constraint_solver.cc:1528
operations_research::Trail::rev_memory_
std::vector< void * > rev_memory_
Definition: constraint_solver.cc:737
operations_research::Queue::EnqueueDelayedDemon
void EnqueueDelayedDemon(Demon *const demon)
Definition: constraint_solver.cc:329
operations_research::Trail::rev_int64_memory_
std::vector< int64 * > rev_int64_memory_
Definition: constraint_solver.cc:733
operations_research::ModelVisitor::VisitIntervalVariable
virtual void VisitIntervalVariable(const IntervalVar *const variable, const std::string &operation, int64 value, IntervalVar *const delegate)
Definition: constraint_solver.cc:2765
operations_research::LocalSearchOperator
The base class for all local search operators.
Definition: constraint_solveri.h:798
operations_research::ModelVisitor::kRangeArgument
static const char kRangeArgument[]
Definition: constraint_solver.h:3468
operations_research::PropagationBaseObject::EnqueueAll
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
Definition: constraint_solver.cc:2521
operations_research::ModelVisitor::kFixedChargeArgument
static const char kFixedChargeArgument[]
Definition: constraint_solver.h:3450
operations_research::PropagationMonitor::SetDurationMax
virtual void SetDurationMax(IntervalVar *const var, int64 new_max)=0
next
Block * next
Definition: constraint_solver.cc:674
selector_
BaseVariableAssignmentSelector *const selector_
Definition: search.cc:1856
operations_research::IntTupleSet
Definition: tuple_set.h:49
operations_research::ModelVisitor::kLexLess
static const char kLexLess[]
Definition: constraint_solver.h:3375
operations_research::Queue::ProcessOneDemon
void ProcessOneDemon(Demon *const demon)
Definition: constraint_solver.cc:242
operations_research::Solver::DefaultSolverParameters
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
Definition: constraint_solver.cc:118
operations_research::Queue::EnqueueAll
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
Definition: constraint_solver.cc:312
operations_research::LocalSearchMonitor::BeginFilterNeighbor
virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0
gtl::STLDeleteElements
void STLDeleteElements(T *container)
Definition: stl_util.h:372
operations_research::Solver::AT_SOLUTION
@ AT_SOLUTION
After successful NextSolution and before EndSearch.
Definition: constraint_solver.h:727
operations_research::Search::AcceptNeighbor
void AcceptNeighbor()
Definition: constraint_solver.cc:1308
operations_research::ModelVisitor::kMaxEqual
static const char kMaxEqual[]
Definition: constraint_solver.h:3379
CHECK_NE
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
operations_research::ModelVisitor::kProduct
static const char kProduct[]
Definition: constraint_solver.h:3395
operations_research::Queue::AddConstraint
void AddConstraint(Constraint *const c)
Definition: constraint_solver.cc:376
operations_research::StateInfo::StateInfo
StateInfo()
Definition: constraint_solver.cc:418
operations_research::LocalSearchMonitor::EndAcceptNeighbor
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
operations_research::Search::decision_builder
DecisionBuilder * decision_builder() const
Definition: constraint_solver.cc:1026
operations_research::Queue::Unfreeze
void Unfreeze()
Definition: constraint_solver.cc:236
operations_research::Solver::TopPeriodicCheck
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
Definition: constraint_solver.cc:1542
operations_research::LocalOptimumReached
bool LocalOptimumReached(Search *const search)
Definition: constraint_solver.cc:1344
operations_research::SearchMonitor::AcceptUncheckedNeighbor
virtual void AcceptUncheckedNeighbor()
After accepting an unchecked neighbor during local search.
Definition: constraint_solver.cc:2888
operations_research::Solver::LocalSearchProfile
std::string LocalSearchProfile() const
Returns local search profiling information in a human readable format.
Definition: local_search.cc:3843
operations_research::ModelVisitor::kDurationExpr
static const char kDurationExpr[]
Definition: constraint_solver.h:3350
operations_research::ModelVisitor::kDifference
static const char kDifference[]
Definition: constraint_solver.h:3346
operations_research::Trail::rev_ptrs_
CompressedTrail< void * > rev_ptrs_
Definition: constraint_solver.cc:728
operations_research::ModelVisitor::VisitInt64ToInt64AsArray
void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1 &eval, const std::string &arg_name, int64 index_max)
Expands function as array when index min is 0.
Definition: constraint_solver.cc:2854
operations_research::Decision::Refute
virtual void Refute(Solver *const s)=0
Refute will be called after a backtrack.
operations_research::DecisionVisitor::VisitScheduleOrPostpone
virtual void VisitScheduleOrPostpone(IntervalVar *const var, int64 est)
Definition: constraint_solver.cc:2544
operations_research::LocalSearchMonitorMaster::DebugString
std::string DebugString() const override
Definition: constraint_solver.cc:3194
operations_research::LocalSearchMonitor::~LocalSearchMonitor
~LocalSearchMonitor() override
Definition: constraint_solver.cc:2912
operations_research::Search::set_search_left_depth
void set_search_left_depth(int d)
Definition: constraint_solver.cc:1045
operations_research::Demon::priority
virtual Solver::DemonPriority priority() const
This method returns the priority of the demon.
Definition: constraint_solver.cc:193
operations_research::ModelVisitor::kMinEqual
static const char kMinEqual[]
Definition: constraint_solver.h:3382
operations_research::PropagationMonitor::PopContext
virtual void PopContext()=0
operations_research::Queue::stamp
uint64 stamp() const
Definition: constraint_solver.cc:359
operations_research::SearchMonitor::ExitSearch
virtual void ExitSearch()
End of the search.
Definition: constraint_solver.cc:2869
operations_research::SearchMonitor::Accept
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
Definition: constraint_solver.cc:2890
operations_research::PropagationBaseObject::solver
Solver * solver() const
Definition: constraint_solver.h:3174
operations_research::Solver::EndSearch
void EndSearch()
Definition: constraint_solver.cc:2263
operations_research::Solver::IsLocalSearchProfilingEnabled
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
Definition: constraint_solver.cc:178
DCHECK_LE
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
operations_research::ModelVisitor::kNextsArgument
static const char kNextsArgument[]
Definition: constraint_solver.h:3463
operations_research::ModelVisitor::kMirrorOperation
static const char kMirrorOperation[]
Operations.
Definition: constraint_solver.h:3493
operations_research::ModelVisitor::kLateCostArgument
static const char kLateCostArgument[]
Definition: constraint_solver.h:3456
operations_research::ModelVisitor::kIntervalUnaryRelation
static const char kIntervalUnaryRelation[]
Definition: constraint_solver.h:3362
operations_research::ModelVisitor::kStartMinArgument
static const char kStartMinArgument[]
Definition: constraint_solver.h:3479
operations_research::ModelVisitor::kStartSyncOnStartOperation
static const char kStartSyncOnStartOperation[]
Definition: constraint_solver.h:3499
operations_research::Solver::MakeStatisticsModelVisitor
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
Definition: utilities.cc:811
operations_research::Solver::DemonPriority
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
Definition: constraint_solver.h:608
operations_research::Solver::GetOrCreateLocalSearchState
Assignment * GetOrCreateLocalSearchState()
Returns (or creates) an assignment representing the state of local search.
Definition: constraint_solver.cc:3228
operations_research::SearchMonitor::EndInitialPropagation
virtual void EndInitialPropagation()
After the initial propagation.
Definition: constraint_solver.cc:2879
operations_research::ModelVisitor::kMaximizeArgument
static const char kMaximizeArgument[]
Definition: constraint_solver.h:3460
operations_research::Trace::Add
void Add(PropagationMonitor *const monitor)
Definition: constraint_solver.cc:3111
operations_research::Search::AcceptUncheckedNeighbor
void AcceptUncheckedNeighbor()
Definition: constraint_solver.cc:1312
operations_research::ModelVisitor::kEvaluatorArgument
static const char kEvaluatorArgument[]
Definition: constraint_solver.h:3490
operations_research::Solver::branches
int64 branches() const
The number of branches explored since the creation of the solver.
Definition: constraint_solver.h:982
operations_research::Trace::SetStartMin
void SetStartMin(IntervalVar *const var, int64 new_min) override
IntervalVar modifiers.
Definition: constraint_solver.cc:3042
CHECK
#define CHECK(condition)
Definition: base/logging.h:495
operations_research::LocalSearchMonitor::Install
void Install() override
Install itself on the solver.
Definition: constraint_solver.cc:2916
commandlineflags.h
operations_research::ModelVisitor::kGreaterOrEqual
static const char kGreaterOrEqual[]
Definition: constraint_solver.h:3358
operations_research::BuildPrintTrace
PropagationMonitor * BuildPrintTrace(Solver *const s)
Definition: trace.cc:873
parameters
SatParameters parameters
Definition: cp_model_fz_solver.cc:108
operations_research::ModelVisitor::kTrace
static const char kTrace[]
Definition: constraint_solver.h:3409
operations_research::Solver::ActiveSearch
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
Definition: constraint_solver.cc:1127
name
const std::string name
Definition: default_search.cc:808
operations_research::ModelVisitor::kIsDifferent
static const char kIsDifferent[]
Definition: constraint_solver.h:3366
operations_research::Solver::KEEP_RIGHT
@ KEEP_RIGHT
Left branches are ignored.
Definition: constraint_solver.h:703
operations_research::Solver::CHOICE_POINT
@ CHOICE_POINT
Definition: constraint_solver.h:716
operations_research::Search::AfterDecision
void AfterDecision(Decision *const d, bool apply)
Definition: constraint_solver.cc:1236
operations_research::Constraint::IsCastConstraint
bool IsCastConstraint() const
Is the constraint created by a cast from expression to integer variable?
Definition: constraint_solver.cc:3253
operations_research::Trace::EndDemonRun
void EndDemonRun(Demon *const demon) override
Definition: constraint_solver.cc:2962
operations_research::ModelVisitor::VisitIntegerVariable
virtual void VisitIntegerVariable(const IntVar *const variable, IntExpr *const delegate)
Definition: constraint_solver.cc:2750
operations_research::ModelVisitor::kRelaxedMaxOperation
static const char kRelaxedMaxOperation[]
Definition: constraint_solver.h:3494
operations_research::ModelVisitor::kStepArgument
static const char kStepArgument[]
Definition: constraint_solver.h:3481
operations_research::ModelVisitor::kPositionYArgument
static const char kPositionYArgument[]
Definition: constraint_solver.h:3467
operations_research::PropagationMonitor::PropagationMonitor
PropagationMonitor(Solver *const solver)
Definition: constraint_solver.cc:2897
operations_research::ModelVisitor::BeginVisitConstraint
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *const constraint)
Definition: constraint_solver.cc:2737
operations_research::ModelVisitor::kMember
static const char kMember[]
Definition: constraint_solver.h:3380
operations_research::SearchMonitor::BeginInitialPropagation
virtual void BeginInitialPropagation()
Before the initial propagation.
Definition: constraint_solver.cc:2878
operations_research::ModelVisitor::kVarBoundWatcher
static const char kVarBoundWatcher[]
Definition: constraint_solver.h:3412
operations_research::Search::set_search_depth
void set_search_depth(int d)
Definition: constraint_solver.cc:1043
operations_research::Solver::TopProgressPercent
int TopProgressPercent()
Returns a percentage representing the propress of the search before reaching the limits of the top-le...
Definition: constraint_solver.cc:1544
operations_research::Queue::Process
void Process()
Definition: constraint_solver.cc:261
operations_research::StateInfo::StateInfo
StateInfo(void *pinfo, int iinfo)
Definition: constraint_solver.cc:424
operations_research::PropagationBaseObject::ExecuteAll
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
Definition: constraint_solver.cc:2517
operations_research::StateMarker
Definition: constraint_solver.cc:450
operations_research::Solver::MakeRestoreAssignment
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
Definition: constraint_solver/assignment.cc:1081
gtl::ContainsKey
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
operations_research::Search::set_should_finish
void set_should_finish(bool s)
Definition: constraint_solver.cc:1048
operations_research::Solver::InstrumentsDemons
bool InstrumentsDemons() const
Returns whether we are instrumenting demons.
Definition: constraint_solver.cc:169
operations_research::Search::NoMoreSolutions
void NoMoreSolutions()
Definition: constraint_solver.cc:1284
operations_research::Trace::BeginConstraintInitialPropagation
void BeginConstraintInitialPropagation(Constraint *const constraint) override
Propagation events.
Definition: constraint_solver.cc:2929
operations_research::SimpleRevFIFO::Iterator::ok
bool ok() const
Definition: constraint_solveri.h:160
operations_research::ModelVisitor::kCoefficientsArgument
static const char kCoefficientsArgument[]
Definition: constraint_solver.h:3435
operations_research::ModelVisitor::kLessOrEqual
static const char kLessOrEqual[]
Definition: constraint_solver.h:3374
operations_research::DemonProfiler
Definition: demon_profiler.cc:50
operations_research::ModelVisitor::VisitInt64ToBoolExtension
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.
Definition: constraint_solver.cc:2825
operations_research::PropagationMonitor::BeginDemonRun
virtual void BeginDemonRun(Demon *const demon)=0
operations_research::Solver::SearchContext
std::string SearchContext() const
Definition: constraint_solver.cc:3220
operations_research::ModelVisitor::kTransitsArgument
static const char kTransitsArgument[]
Definition: constraint_solver.h:3484
operations_research::Decision
A Decision represents a choice point in the search tree.
Definition: constraint_solver.h:3223