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