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