 |
OR-Tools
8.1
|
Go to the documentation of this file.
27 #include "absl/memory/memory.h"
28 #include "absl/time/clock.h"
29 #include "absl/time/time.h"
44 "Trace propagation events (constraint and demon executions,"
45 " variable modifications).");
46 ABSL_FLAG(
bool, cp_trace_search,
false,
"Trace search events");
48 "show all constraints added to the solver.");
50 "use PrintModelVisitor on model before solving.");
52 "use StatisticsModelVisitor on model before solving.");
54 "Force failure at the beginning of a search.");
56 "Export profiling overview to file.");
57 ABSL_FLAG(
bool, cp_print_local_search_profile,
false,
58 "Print local search profiling data after solving.");
59 ABSL_FLAG(
bool, cp_name_variables,
false,
"Force all variables to have names.");
61 "Name variables casted from expressions");
63 "Use small compact table constraint when possible.");
64 ABSL_FLAG(
bool, cp_use_cumulative_edge_finder,
true,
65 "Use the O(n log n) cumulative edge finding algorithm described "
66 "in 'Edge Finding Filtering Algorithm for Discrete Cumulative "
67 "Resources in O(kn log n)' by Petr Vilim, CP 2009.");
69 "Use a O(n^2) cumulative time table propagation algorithm.");
70 ABSL_FLAG(
bool, cp_use_cumulative_time_table_sync,
false,
71 "Use a synchronized O(n^2 log n) cumulative time table propagation "
73 ABSL_FLAG(
bool, cp_use_sequence_high_demand_tasks,
true,
74 "Use a sequence constraints for cumulative tasks that have a "
75 "demand greater than half of the capacity of the resource.");
76 ABSL_FLAG(
bool, cp_use_all_possible_disjunctions,
true,
77 "Post temporal disjunctions for all pairs of tasks sharing a "
78 "cumulative resource and that cannot overlap because the sum of "
79 "their demand exceeds the capacity.");
81 "Do not post the edge finder in the cumulative constraints if "
82 "it contains more than this number of tasks");
84 "Diffn constraint adds redundant cumulative constraint");
86 "If true, rmq's will be used in element expressions.");
88 "Number of solutions explored between two solution checks during "
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.");
97 #if defined(_MSC_VER) // WINDOWS
98 #pragma warning(disable : 4351 4355)
106 template <
typename T,
typename MethodPointer,
typename... Args>
107 void ForAll(
const std::vector<T*>& objects, MethodPointer method,
108 const Args&... args) {
109 for (T*
const object : objects) {
110 DCHECK(
object !=
nullptr);
111 (
object->*method)(args...);
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));
174 return parameters_.profile_propagation() ||
175 !parameters_.profile_file().empty();
179 return parameters_.profile_local_search() ||
180 parameters_.print_local_search_profile();
184 return parameters_.trace_propagation();
188 return parameters_.name_all_variables();
224 clean_action_(nullptr),
225 clean_variable_(nullptr),
227 instruments_demons_(s->InstrumentsDemons()) {}
237 if (--freeze_level_ == 0) {
243 demon->set_stamp(stamp_ - 1);
244 if (!instruments_demons_) {
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();
270 DCHECK(!delayed_queue_.empty());
271 Demon*
const demon = delayed_queue_.front();
272 delayed_queue_.pop_front();
281 if (!instruments_demons_) {
283 Demon*
const demon = *it;
284 if (demon->stamp() < stamp_) {
296 Demon*
const demon = *it;
297 if (demon->stamp() < stamp_) {
320 if (demon->stamp() < stamp_) {
321 demon->set_stamp(stamp_);
322 var_queue_.push_back(demon);
323 if (freeze_level_ == 0) {
331 if (demon->stamp() < stamp_) {
332 demon->set_stamp(stamp_);
333 delayed_queue_.push_back(demon);
340 delayed_queue_.clear();
343 if (clean_action_ !=
nullptr) {
344 clean_action_(solver_);
345 clean_action_ =
nullptr;
346 }
else if (clean_variable_ !=
nullptr) {
348 clean_variable_ =
nullptr;
362 DCHECK(clean_variable_ ==
nullptr);
363 clean_action_ = std::move(
a);
367 DCHECK(clean_action_ ==
nullptr);
368 clean_variable_ =
var;
372 DCHECK(clean_variable_ ==
nullptr);
373 clean_action_ =
nullptr;
377 to_add_.push_back(c);
387 for (
int counter = 0; counter < to_add_.size(); ++counter) {
388 Constraint*
const constraint = to_add_[counter];
399 std::deque<Demon*> var_queue_;
400 std::deque<Demon*> delayed_queue_;
408 std::vector<Constraint*> to_add_;
410 const bool instruments_demons_;
459 int rev_int64_index_;
460 int rev_uint64_index_;
461 int rev_double_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_;
479 rev_uint64_index_(0),
480 rev_double_index_(0),
482 rev_boolvar_list_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),
501 addrval() : address_(nullptr) {}
502 explicit addrval(T* adr) : address_(adr), old_value_(*adr) {}
503 void restore()
const { (*address_) = old_value_; }
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;
525 const int block_size_;
530 class NoCompressionTrailPacker :
public TrailPacker<T> {
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 {
537 DCHECK(packed_block !=
nullptr);
538 absl::string_view block_str(
reinterpret_cast<const char*
>(block),
540 packed_block->assign(block_str.data(), block_str.size());
542 void Unpack(
const std::string& packed_block, addrval<T>* block)
override {
544 memcpy(block, packed_block.c_str(), packed_block.size());
552 class ZlibTrailPacker :
public TrailPacker<T> {
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_]) {}
559 ~ZlibTrailPacker()
override {}
561 void Pack(
const addrval<T>* block, std::string* packed_block)
override {
563 DCHECK(packed_block !=
nullptr);
564 uLongf size = tmp_size_;
566 compress(
reinterpret_cast<Bytef*
>(tmp_block_.get()), &size,
567 reinterpret_cast<const Bytef*
>(block), this->input_size());
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());
574 void Unpack(
const std::string& packed_block, addrval<T>* block)
override {
576 uLongf size = this->input_size();
578 uncompress(
reinterpret_cast<Bytef*
>(block), &size,
579 reinterpret_cast<const Bytef*
>(packed_block.c_str()),
580 packed_block.size());
586 std::unique_ptr<char[]> tmp_block_;
591 class CompressedTrail {
595 ConstraintSolverParameters::TrailCompression compression_level)
596 : block_size_(block_size),
598 free_blocks_(nullptr),
599 data_(new addrval<T>[block_size]),
600 buffer_(new addrval<T>[block_size]),
604 switch (compression_level) {
605 case ConstraintSolverParameters::NO_COMPRESSION: {
606 packer_.reset(
new NoCompressionTrailPacker<T>(block_size));
609 case ConstraintSolverParameters::COMPRESS_WITH_ZLIB: {
610 packer_.reset(
new ZlibTrailPacker<T>(block_size));
623 memset(data_.get(), 0,
sizeof(*data_.get()) * block_size);
624 memset(buffer_.get(), 0,
sizeof(*buffer_.get()) * block_size);
628 FreeBlocks(free_blocks_);
630 const addrval<T>& Back()
const {
642 buffer_used_ =
false;
643 }
else if (blocks_ !=
nullptr) {
644 packer_->Unpack(blocks_->compressed, data_.get());
652 void PushBack(
const addrval<T>& addr_val) {
656 packer_->Pack(buffer_.get(), &blocks_->compressed);
669 int64 size()
const {
return size_; }
677 void FreeTopBlock() {
678 Block* block = blocks_;
679 blocks_ = block->next;
680 block->compressed.clear();
681 block->next = free_blocks_;
682 free_blocks_ = block;
685 Block* block =
nullptr;
686 if (free_blocks_ !=
nullptr) {
687 block = free_blocks_;
688 free_blocks_ = block->next;
692 block->next = blocks_;
695 void FreeBlocks(Block* blocks) {
696 while (
nullptr != blocks) {
697 Block*
next = blocks->next;
703 std::unique_ptr<TrailPacker<T> > packer_;
704 const int block_size_;
707 std::unique_ptr<addrval<T>[]> data_;
708 std::unique_ptr<addrval<T>[]> buffer_;
741 ConstraintSolverParameters::TrailCompression compression_level)
742 :
rev_ints_(block_size, compression_level),
746 rev_ptrs_(block_size, compression_level) {}
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();
757 target = m->rev_int64_index_;
758 for (
int curr =
rev_int64s_.size(); curr > target; --curr) {
765 target = m->rev_uint64_index_;
766 for (
int curr =
rev_uint64s_.size(); curr > target; --curr) {
773 target = m->rev_double_index_;
774 for (
int curr =
rev_doubles_.size(); curr > target; --curr) {
781 target = m->rev_ptr_index_;
782 for (
int curr =
rev_ptrs_.size(); curr > target; --curr) {
783 const addrval<void*>& cell =
rev_ptrs_.Back();
789 target = m->rev_boolvar_list_index_;
797 target = m->rev_bools_index_;
798 for (
int curr =
rev_bools_.size() - 1; curr >= target; --curr) {
804 target = m->rev_int_memory_index_;
810 target = m->rev_int64_memory_index_;
816 target = m->rev_double_memory_index_;
822 target = m->rev_object_memory_index_;
828 target = m->rev_object_array_memory_index_;
835 target = m->rev_memory_index_;
836 for (
int curr =
rev_memory_.size() - 1; curr >= target; --curr) {
838 ::operator
delete(
reinterpret_cast<char*
>(
rev_memory_[curr]));
847 target = m->rev_memory_array_index_;
856 void Solver::InternalSaveValue(
int* valptr) {
857 trail_->rev_ints_.PushBack(addrval<int>(valptr));
860 void Solver::InternalSaveValue(
int64* valptr) {
861 trail_->rev_int64s_.PushBack(addrval<int64>(valptr));
864 void Solver::InternalSaveValue(
uint64* valptr) {
865 trail_->rev_uint64s_.PushBack(addrval<uint64>(valptr));
868 void Solver::InternalSaveValue(
double* valptr) {
869 trail_->rev_doubles_.PushBack(addrval<double>(valptr));
872 void Solver::InternalSaveValue(
void** valptr) {
873 trail_->rev_ptrs_.PushBack(addrval<void*>(valptr));
879 void Solver::InternalSaveValue(
bool* valptr) {
880 trail_->rev_bools_.push_back(valptr);
881 trail_->rev_bool_value_.push_back(*valptr);
884 BaseObject* Solver::SafeRevAlloc(BaseObject* ptr) {
886 trail_->rev_object_memory_.push_back(ptr);
890 int* Solver::SafeRevAllocArray(
int* ptr) {
892 trail_->rev_int_memory_.push_back(ptr);
896 int64* Solver::SafeRevAllocArray(
int64* ptr) {
898 trail_->rev_int64_memory_.push_back(ptr);
902 double* Solver::SafeRevAllocArray(
double* ptr) {
904 trail_->rev_double_memory_.push_back(ptr);
910 trail_->rev_int64_memory_.push_back(
reinterpret_cast<int64*
>(ptr));
914 BaseObject** Solver::SafeRevAllocArray(BaseObject** ptr) {
916 trail_->rev_object_array_memory_.push_back(ptr);
920 IntVar** Solver::SafeRevAllocArray(IntVar** ptr) {
921 BaseObject** in = SafeRevAllocArray(
reinterpret_cast<BaseObject**
>(ptr));
922 return reinterpret_cast<IntVar**
>(in);
925 IntExpr** Solver::SafeRevAllocArray(IntExpr** ptr) {
926 BaseObject** in = SafeRevAllocArray(
reinterpret_cast<BaseObject**
>(ptr));
927 return reinterpret_cast<IntExpr**
>(in);
930 Constraint** Solver::SafeRevAllocArray(Constraint** ptr) {
931 BaseObject** in = SafeRevAllocArray(
reinterpret_cast<BaseObject**
>(ptr));
935 void* Solver::UnsafeRevAllocAux(
void* ptr) {
937 trail_->rev_memory_.push_back(ptr);
941 void** Solver::UnsafeRevAllocArrayAux(
void** ptr) {
943 trail_->rev_memory_array_.push_back(ptr);
948 solver->trail_->rev_boolvar_list_.push_back(
var);
959 solution_counter_(0),
960 unchecked_solution_counter_(0),
961 decision_builder_(nullptr),
962 created_by_solve_(false),
964 left_search_depth_(0),
965 should_restart_(false),
966 should_finish_(false),
968 jmpbuf_filled_(false),
969 backtrack_at_the_end_of_the_search_(true) {}
978 solution_counter_(0),
979 unchecked_solution_counter_(0),
980 decision_builder_(nullptr),
981 created_by_solve_(false),
983 left_search_depth_(-1),
984 should_restart_(false),
985 should_finish_(false),
987 jmpbuf_filled_(false),
988 backtrack_at_the_end_of_the_search_(true) {}
1021 return unchecked_solution_counter_;
1024 decision_builder_ = db;
1033 left_search_depth_++;
1037 return backtrack_at_the_end_of_the_search_;
1040 backtrack_at_the_end_of_the_search_ = restore;
1051 if (should_finish_ || should_restart_) {
1064 void ClearBuffer() {
1065 CHECK(jmpbuf_filled_) <<
"Internal error in backtracking";
1066 jmpbuf_filled_ =
false;
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_;
1076 bool created_by_solve_;
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_;
1098 #ifndef CP_USE_EXCEPTIONS_FOR_BACKTRACK
1101 #define CP_TRY(search) \
1102 CHECK(!search->jmpbuf_filled_) << "Fail() called outside search"; \
1103 search->jmpbuf_filled_ = true; \
1104 if (setjmp(search->fail_buffer_) == 0)
1105 #define CP_ON_FAIL else
1106 #define CP_DO_FAIL(search) longjmp(search->fail_buffer_, 1)
1107 #else // CP_USE_EXCEPTIONS_FOR_BACKTRACK
1108 class FailException {};
1109 #define CP_TRY(search) \
1110 CHECK(!search->jmpbuf_filled_) << "Fail() called outside search"; \
1111 search->jmpbuf_filled_ = true; \
1113 #define CP_ON_FAIL catch (FailException&)
1114 #define CP_DO_FAIL(search) throw FailException()
1115 #endif // CP_USE_EXCEPTIONS_FOR_BACKTRACK
1117 void Search::JumpBack() {
1118 if (jmpbuf_filled_) {
1119 jmpbuf_filled_ =
false;
1122 std::string explanation =
"Failure outside of search";
1134 ~ApplyBranchSelector()
override {}
1136 Decision* Next(Solver*
const s)
override {
1141 std::string DebugString()
const override {
return "Apply(BranchSelector)"; }
1149 selector_ = std::move(bs);
1158 [solve_depth](
Solver* s) {
1160 s->ActiveSearch()->SetBranchSelector(nullptr);
1164 searches_.back()->SetBranchSelector(std::move(bs));
1168 return RevAlloc(
new ApplyBranchSelector(std::move(bs)));
1178 return searches_.back()->left_search_depth();
1182 if (selector_ !=
nullptr) {
1190 monitors_.push_back(m);
1197 left_search_depth_ = 0;
1198 selector_ =
nullptr;
1199 backtrack_at_the_end_of_the_search_ =
true;
1206 solution_counter_ = 0;
1207 unchecked_solution_counter_ = 0;
1261 if (!monitor->AcceptSolution()) {
1272 bool should_continue =
false;
1274 if (monitor->AtSolution()) {
1278 should_continue =
true;
1281 return should_continue;
1291 if (monitor->LocalOptimum()) {
1301 if (!monitor->AcceptDelta(
delta, deltadelta)) {
1318 if (monitor->IsUncheckedSolutionLimitReached()) {
1332 progress =
std::max(progress, monitor->ProgressPercent());
1339 if (decision_builder_ !=
nullptr) {
1340 decision_builder_->
Accept(visitor);
1363 class FailDecision :
public Decision {
1365 void Apply(Solver*
const s)
override { s->Fail(); }
1366 void Refute(Solver*
const s)
override { s->Fail(); }
1371 class BalancingDecision :
public Decision {
1373 ~BalancingDecision()
override {}
1374 void Apply(Solver*
const s)
override {}
1375 void Refute(Solver*
const s)
override {}
1386 enum SentinelMarker {
1387 INITIAL_SEARCH_SENTINEL = 10000000,
1388 ROOT_NODE_SENTINEL = 20000000,
1389 SOLVER_CTOR_SENTINEL = 40000000
1393 extern PropagationMonitor*
BuildTrace(Solver*
const s);
1400 void CheckSolverParameters(
const ConstraintSolverParameters&
parameters) {
1402 <<
"Were parameters built using Solver::DefaultSolverParameters() ?";
1407 const ConstraintSolverParameters&
parameters)
1412 use_fast_local_search_(true),
1419 parameters_(DefaultSolverParameters()),
1422 use_fast_local_search_(true),
1427 void Solver::Init() {
1428 CheckSolverParameters(parameters_);
1429 queue_ = absl::make_unique<Queue>(
this);
1430 trail_ = absl::make_unique<Trail>(parameters_.trail_block_size(),
1431 parameters_.compress_trail());
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));
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;
1451 propagation_monitor_.reset(
BuildTrace(
this));
1453 print_trace_ =
nullptr;
1454 anonymous_variable_index_ = 0;
1455 should_fail_ =
false;
1460 searches_.push_back(
new Search(
this));
1461 PushSentinel(SOLVER_CTOR_SENTINEL);
1462 InitCachedIntConstants();
1463 InitCachedConstraint();
1468 reinterpret_cast<LocalSearchMonitor*
>(local_search_profiler_));
1474 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
1488 std::string out =
"Solver(name = \"" + name_ +
"\", state = ";
1491 out +=
"OUTSIDE_SEARCH";
1494 out +=
"IN_ROOT_NODE";
1500 out +=
"AT_SOLUTION";
1503 out +=
"NO_MORE_SOLUTIONS";
1506 out +=
"PROBLEM_INFEASIBLE";
1509 absl::StrAppendFormat(
1511 ", branches = %d, fails = %d, decisions = %d, delayed demon runs = %d, "
1512 "var demon runs = %d, normal demon runs = %d, Run time = %d ms)",
1521 return absl::ToInt64Milliseconds(timer_->GetDuration());
1525 return absl::FromUnixSeconds(0) + timer_->GetDuration();
1534 void Solver::IncrementUncheckedSolutionCounter() {
1538 bool Solver::IsUncheckedSolutionLimitReached() {
1547 ConstraintSolverStatistics stats;
1548 stats.set_num_branches(
branches());
1549 stats.set_num_failures(
failures());
1552 stats.set_duration_seconds(absl::ToDoubleSeconds(timer_->GetDuration()));
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();
1585 searches_.back()->marker_stack_.push_back(m);
1586 queue_->increase_stamp();
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();
1600 trail_->BacktrackTo(m);
1604 searches_.back()->marker_stack_.pop_back();
1606 queue_->increase_stamp();
1610 void Solver::check_alloc_state() {
1619 LOG(
FATAL) <<
"allocating at a leaf node";
1621 LOG(
FATAL) <<
"This switch was supposed to be exhaustive, but it is not!";
1625 void Solver::FreezeQueue() { queue_->Freeze(); }
1627 void Solver::UnfreezeQueue() { queue_->Unfreeze(); }
1629 void Solver::EnqueueVar(Demon*
const d) { queue_->EnqueueVar(d); }
1631 void Solver::EnqueueDelayedDemon(Demon*
const d) {
1632 queue_->EnqueueDelayedDemon(d);
1635 void Solver::ExecuteAll(
const SimpleRevFIFO<Demon*>& demons) {
1636 queue_->ExecuteAll(demons);
1639 void Solver::EnqueueAll(
const SimpleRevFIFO<Demon*>& demons) {
1640 queue_->EnqueueAll(demons);
1647 void Solver::set_action_on_fail(Action
a) {
1648 queue_->set_action_on_fail(std::move(
a));
1651 void Solver::set_variable_to_clean_on_fail(IntVar* v) {
1652 queue_->set_variable_to_clean_on_fail(v);
1655 void Solver::reset_action_on_fail() { queue_->reset_action_on_fail(); }
1659 if (c == true_constraint_) {
1663 queue_->AddConstraint(c);
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);
1674 if (parameters_.print_added_constraints()) {
1677 constraints_list_.push_back(c);
1683 if (constraint !=
nullptr) {
1685 cast_constraints_.insert(constraint);
1686 cast_information_[target_var] =
1699 void Solver::ProcessConstraints() {
1702 if (parameters_.print_model()) {
1706 if (parameters_.print_model_stats()) {
1711 if (parameters_.disable_solve()) {
1712 LOG(
INFO) <<
"Forcing early failure";
1717 const int constraints_size = constraints_list_.size();
1718 additional_constraints_list_.clear();
1719 additional_constraints_parent_list_.clear();
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);
1728 CHECK_EQ(constraints_list_.size(), constraints_size);
1731 for (
int additional_constraint_index_ = 0;
1732 additional_constraint_index_ < additional_constraints_list_.size();
1733 ++additional_constraint_index_) {
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,
1741 nested->PostAndPropagate();
1742 propagation_monitor_->EndNestedConstraintInitialPropagation(parent, nested);
1748 DCHECK(searches_.back() !=
nullptr);
1749 return searches_.back()->created_by_solve();
1753 std::vector<SearchMonitor*> monitors;
1754 monitors.push_back(m1);
1755 return Solve(db, monitors);
1759 std::vector<SearchMonitor*> monitors;
1760 return Solve(db, monitors);
1765 std::vector<SearchMonitor*> monitors;
1766 monitors.push_back(m1);
1767 monitors.push_back(m2);
1768 return Solve(db, monitors);
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);
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);
1792 const std::vector<SearchMonitor*>& monitors) {
1794 searches_.back()->set_created_by_solve(
true);
1796 const bool solution_found = searches_.back()->solution_counter() > 0;
1798 return solution_found;
1802 std::vector<SearchMonitor*> monitors;
1803 monitors.push_back(m1);
1808 std::vector<SearchMonitor*> monitors;
1814 std::vector<SearchMonitor*> monitors;
1815 monitors.push_back(m1);
1816 monitors.push_back(m2);
1822 std::vector<SearchMonitor*> monitors;
1823 monitors.push_back(m1);
1824 monitors.push_back(m2);
1825 monitors.push_back(m3);
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);
1844 const std::vector<SearchMonitor*>& monitors) {
1847 CHECK(db !=
nullptr);
1848 const bool nested = state_ ==
IN_SEARCH;
1851 LOG(
FATAL) <<
"Cannot start new searches here.";
1854 Search*
const search = nested ?
new Search(
this) : searches_.back();
1862 searches_.push_back(search);
1868 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
1875 propagation_monitor_->Install();
1876 if (demon_profiler_ !=
nullptr) {
1879 local_search_monitor_->Install();
1880 if (local_search_profiler_ !=
nullptr) {
1886 if (monitor !=
nullptr) {
1890 std::vector<SearchMonitor*> extras;
1893 if (monitor !=
nullptr) {
1900 if (print_trace_ !=
nullptr) {
1904 print_trace_ =
nullptr;
1905 if (parameters_.trace_propagation()) {
1908 }
else if (parameters_.trace_search()) {
1923 PushSentinel(INITIAL_SEARCH_SENTINEL);
1929 bool Solver::BacktrackOneLevel(
Decision**
const fail_decision) {
1930 bool no_more_solutions =
false;
1931 bool end_loop =
false;
1940 searches_.back()->sentinel_pushed_--;
1941 no_more_solutions =
true;
1945 LOG(
ERROR) <<
"Simple markers should not be encountered during search";
1951 searches_.back()->set_search_depth(info.
depth);
1952 searches_.back()->set_search_left_depth(info.
left_depth);
1963 Search*
const search = searches_.back();
1966 if (no_more_solutions) {
1967 search->NoMoreSolutions();
1969 return no_more_solutions;
1972 void Solver::PushSentinel(
int magic_code) {
1973 StateInfo info(
this, magic_code);
1976 if (magic_code != SOLVER_CTOR_SENTINEL) {
1977 searches_.back()->sentinel_pushed_++;
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));
1986 Search*
const search = searches_.back();
1987 CHECK_NE(0, search->sentinel_pushed_);
1989 if (search->sentinel_pushed_ > 1) {
1990 BacktrackToSentinel(ROOT_NODE_SENTINEL);
1992 CHECK_EQ(1, search->sentinel_pushed_);
1993 PushSentinel(ROOT_NODE_SENTINEL);
1997 if (search->sentinel_pushed_ > 0) {
1998 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2000 CHECK_EQ(0, search->sentinel_pushed_);
2001 PushSentinel(INITIAL_SEARCH_SENTINEL);
2009 void Solver::BacktrackToSentinel(
int magic_code) {
2010 Search*
const search = searches_.back();
2011 bool end_loop = search->sentinel_pushed_ == 0;
2018 CHECK_GE(--search->sentinel_pushed_, 0);
2041 void Solver::JumpToSentinelWhenNested() {
2043 Search* c = searches_.back();
2044 Search* p = ParentSearch();
2046 while (!c->marker_stack_.empty()) {
2047 StateMarker*
const m = c->marker_stack_.back();
2049 p->marker_stack_.push_back(m);
2052 CHECK_EQ(c->marker_stack_.size(), 1) <<
"Sentinel found too early";
2057 c->marker_stack_.pop_back();
2059 c->set_search_depth(0);
2060 c->set_search_left_depth(0);
2061 CHECK_EQ(found,
true) <<
"Sentinel not found";
2065 class ReverseDecision :
public Decision {
2067 explicit ReverseDecision(Decision*
const d) : decision_(d) {
2068 CHECK(d !=
nullptr);
2070 ~ReverseDecision()
override {}
2072 void Apply(Solver*
const s)
override { decision_->Refute(s); }
2074 void Refute(Solver*
const s)
override { decision_->Apply(s); }
2076 void Accept(DecisionVisitor*
const visitor)
const override {
2077 decision_->Accept(visitor);
2080 std::string DebugString()
const override {
2081 std::string str =
"Reverse(";
2082 str += decision_->DebugString();
2088 Decision*
const decision_;
2094 Search*
const search = searches_.back();
2097 const bool top_level = solve_depth <= 1;
2100 LOG(
WARNING) <<
"NextSolution() called without a NewSearch before";
2111 if (BacktrackOneLevel(&fd)) {
2122 ProcessConstraints();
2124 PushSentinel(ROOT_NODE_SENTINEL);
2126 search->ClearBuffer();
2129 queue_->AfterFailure();
2130 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2144 volatile bool finish =
false;
2145 volatile bool result =
false;
2150 if (fd !=
nullptr) {
2169 if (d == fail_decision_.get()) {
2174 switch (modification) {
2176 d =
RevAlloc(
new ReverseDecision(d));
2178 ABSL_FALLTHROUGH_INTENDED;
2228 queue_->AfterFailure();
2231 BacktrackToSentinel(top_level ? ROOT_NODE_SENTINEL
2232 : INITIAL_SEARCH_SENTINEL);
2240 BacktrackToSentinel(top_level ? ROOT_NODE_SENTINEL
2241 : INITIAL_SEARCH_SENTINEL);
2244 PushSentinel(top_level ? ROOT_NODE_SENTINEL : INITIAL_SEARCH_SENTINEL);
2247 if (BacktrackOneLevel(&fd)) {
2255 search->ClearBuffer();
2264 Search*
const search = searches_.back();
2266 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2269 if (search->sentinel_pushed_ > 0) {
2270 JumpToSentinelWhenNested();
2275 if (2 == searches_.size()) {
2279 if (!parameters_.profile_file().empty()) {
2280 const std::string& file_name = parameters_.profile_file();
2281 LOG(
INFO) <<
"Exporting profile to " << file_name;
2284 if (parameters_.print_local_search_profile()) {
2289 searches_.pop_back();
2296 LOG(
FATAL) <<
"CheckAssignment is only available at the top level.";
2299 Search*
const search = searches_.back();
2302 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2311 PushSentinel(INITIAL_SEARCH_SENTINEL);
2316 restore->
Next(
this);
2317 ProcessConstraints();
2319 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2320 search->ClearBuffer();
2326 constraint_index_ < constraints_list_.size()
2328 : additional_constraints_parent_list_[additional_constraint_index_];
2330 if (
ct->name().empty()) {
2331 LOG(
INFO) <<
"Failing constraint = " <<
ct->DebugString();
2333 LOG(
INFO) <<
"Failing constraint = " <<
ct->name() <<
":"
2334 <<
ct->DebugString();
2336 queue_->AfterFailure();
2337 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);
2346 explicit AddConstraintDecisionBuilder(
Constraint*
const ct)
2351 ~AddConstraintDecisionBuilder()
override {}
2353 Decision* Next(Solver*
const solver)
override {
2354 solver->AddConstraint(constraint_);
2358 std::string DebugString()
const override {
2359 return absl::StrFormat(
"AddConstraintDecisionBuilder(%s)",
2360 constraint_->DebugString());
2364 Constraint*
const constraint_;
2369 return RevAlloc(
new AddConstraintDecisionBuilder(
ct));
2378 std::vector<SearchMonitor*> monitors;
2379 monitors.push_back(m1);
2384 std::vector<SearchMonitor*> monitors;
2390 std::vector<SearchMonitor*> monitors;
2391 monitors.push_back(m1);
2392 monitors.push_back(m2);
2398 std::vector<SearchMonitor*> monitors;
2399 monitors.push_back(m1);
2400 monitors.push_back(m2);
2401 monitors.push_back(m3);
2406 const std::vector<SearchMonitor*>& monitors) {
2408 searches_.back()->set_created_by_solve(
true);
2409 searches_.back()->set_backtrack_at_the_end_of_the_search(
false);
2411 const bool solution_found = searches_.back()->solution_counter() > 0;
2413 return solution_found;
2417 if (fail_intercept_) {
2423 searches_.back()->BeginFail();
2424 searches_.back()->JumpBack();
2428 searches_.back()->set_should_finish(
true);
2432 searches_.back()->set_should_restart(
true);
2440 if (cast_info !=
nullptr) {
2450 if (
name !=
nullptr) {
2453 const IntegerCastInfo*
const cast_info =
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());
2461 const std::string new_name =
2462 absl::StrFormat(
"CastVar<%d>", anonymous_variable_index_++);
2463 propagation_object_names_[object] = new_name;
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;
2477 void Solver::SetName(
const PropagationBaseObject*
object,
2478 const std::string&
name) {
2479 if (parameters_.store_names() &&
2480 GetName(
object) !=
name) {
2481 propagation_object_names_[object] =
name;
2488 (!
object->BaseName().empty() && parameters_.name_all_variables());
2506 return solver_->GetName(
this);
2510 solver_->SetName(
this,
name);
2518 solver_->ExecuteAll(demons);
2522 solver_->EnqueueAll(demons);
2530 Solver*
const solver, std::vector<SearchMonitor*>*
const extras) {}
2625 "ScalarProductGreaterOrEqual";
2653 "VariableUsageLessConstant";
2655 "WeightedSumOfAssignedEqualVariable";
2752 if (delegate !=
nullptr) {
2758 const std::string& operation,
2760 if (delegate !=
nullptr) {
2766 const std::string& operation,
2769 if (delegate !=
nullptr) {
2775 for (
int i = 0; i < variable->
size(); ++i) {
2784 const std::vector<int64>& values) {
2799 const std::string& arg_name,
const std::vector<IntVar*>& arguments) {
2809 const std::string& arg_name,
const std::vector<IntervalVar*>& arguments) {
2819 const std::string& arg_name,
const std::vector<SequenceVar*>& arguments) {
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));
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));
2855 const std::string& arg_name,
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));
2893 solver()->searches_.back()->push_monitor(
this);
2985 monitor->SetMin(expr, new_min);
2991 monitor->SetMax(expr, new_max);
2997 monitor->SetRange(expr, new_min, new_max);
3004 monitor->SetMin(
var, new_min);
3010 monitor->SetMax(
var, new_max);
3016 monitor->SetRange(
var, new_min, new_max);
3037 const std::vector<int64>& values)
override {
3051 int64 new_max)
override {
3065 int64 new_max)
override {
3078 int64 new_max)
override {
3104 const std::vector<int>& rank_last,
3105 const std::vector<int>& unperformed)
override {
3107 rank_last, unperformed);
3112 if (monitor !=
nullptr) {
3113 monitors_.push_back(monitor);
3124 std::vector<PropagationMonitor*> monitors_;
3131 reinterpret_cast<class
Trace*
>(propagation_monitor_.get())->Add(monitor);
3135 return propagation_monitor_.get();
3158 neighbor_found,
delta, deltadelta);
3164 bool neighbor_found)
override {
3172 bool neighbor_found)
override {
3185 if (monitor !=
nullptr) {
3186 monitors_.push_back(monitor);
3195 return "LocalSearchMonitorMaster";
3199 std::vector<LocalSearchMonitor*> monitors_;
3212 return local_search_monitor_.get();
3216 const std::string& search_context) {
3229 if (local_search_state_ ==
nullptr) {
3230 local_search_state_ = absl::make_unique<Assignment>(
this);
3232 return local_search_state_.get();
3267 #undef CP_TRY // We no longer need those.
@ KILL_BOTH
Backtracks to the previous decisions, i.e.
ABSL_FLAG(bool, cp_trace_propagation, false, "Trace propagation events (constraint and demon executions," " variable modifications).")
The class IntVar is a subset of IntExpr.
static const char kEquality[]
std::vector< void ** > rev_memory_array_
static const char kIsGreater[]
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
Solver::Action reversible_action
static const char kLinkExprVar[]
void UnfreezeQueue()
This method unfreezes the propagation queue.
void InstallDemonProfiler(DemonProfiler *const monitor)
static const char kIntervalDisjunction[]
void PushState()
The PushState and PopState methods manipulates the states of the reversible objects.
bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
virtual void SetEndRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
virtual void EndFail()
After completing the backtrack.
void SetPerformed(IntervalVar *const var, bool value) override
virtual void VisitIntervalArgument(const std::string &arg_name, IntervalVar *const argument)
Visit interval argument.
static const char kDivide[]
CompressedTrail< int > rev_ints_
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...
void SetMin(IntExpr *const expr, int64 new_min) override
IntExpr modifiers.
virtual void RankNotFirst(SequenceVar *const var, int index)=0
LocalSearchMonitorMaster(Solver *solver)
virtual void Run(Solver *const s)=0
This is the main callback of the demon.
std::vector< double * > rev_double_memory_
static const char kSequenceArgument[]
static const char kNotBetween[]
void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
static const char kSumLessOrEqual[]
static const char kIntegerVariable[]
virtual void VisitRankLastInterval(SequenceVar *const sequence, int index)
std::vector< bool * > rev_bools_
static const char kAllDifferent[]
virtual void SetDurationMin(IntervalVar *const var, int64 new_min)=0
void SetMax(IntExpr *const expr, int64 new_max) override
static const char kSemiContinuous[]
@ IN_SEARCH
Executing the search code.
#define VLOG(verboselevel)
virtual std::string name() const
Object naming.
bool IsUncheckedSolutionLimitReached()
void BeginNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested) override
void SetBranchSelector(Solver::BranchSelector bs)
void set_created_by_solve(bool c)
std::string DebugString() const override
virtual void BeginNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
virtual Decision * Next(Solver *const s)=0
This is the main method of the decision builder class.
std::vector< IntVar * > rev_boolvar_list_
static const char kDemandsArgument[]
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed) override
bool Solve(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
static const char kCountUsedBinsExtension[]
static const char kAtMost[]
void Install() override
Registers itself on the solver such that it gets notified of the search and propagation events.
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 Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
Constraint * MakeFalseConstraint()
This constraint always fails.
virtual void RankLast(SequenceVar *const var, int index)=0
static const char kStartExpr[]
static const char kStartsArgument[]
virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0
bool CheckConstraint(Constraint *const ct)
Checks whether adding this constraint will lead to an immediate failure.
void AddConstraint(Constraint *const c)
Adds the constraint 'c' to the model.
StateInfo(Solver::Action a, bool fast)
virtual void SetDurationRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
CompressedTrail< int64 > rev_int64s_
static const char kVariableUsageLessConstantExtension[]
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
static const char kCumulsArgument[]
virtual void StartProcessingIntegerVariable(IntVar *const var)=0
void EndProcessingIntegerVariable(IntVar *const var) override
virtual void BeginFail()
Just when the failure occurs.
StateMarker(Solver::MarkerType t, const StateInfo &info)
void BacktrackTo(StateMarker *m)
virtual void SetValue(IntVar *const var, int64 value)=0
void AddLocalSearchMonitor(LocalSearchMonitor *monitor)
Adds the local search monitor to the solver.
int SearchDepth() const
Gets the search depth of the current active search.
void RankNotFirst(SequenceVar *const var, int index) override
virtual void EndConstraintInitialPropagation(Constraint *const constraint)=0
virtual void VisitIntegerArgument(const std::string &arg_name, int64 value)
Visit integer arguments.
virtual void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64 > &values)
static const char kCardsArgument[]
virtual void RestartSearch()
Restart the search.
void Install() override
Install itself on the solver.
#define CHECK_GE(val1, val2)
bool NameAllVariables() const
Returns whether all variables should be named.
static const char kVarsArgument[]
int64 solution_counter() const
bool backtrack_at_the_end_of_the_search() const
@ OUTSIDE_SEARCH
Before search, after search.
T * RevAlloc(T *object)
Registers the given object as being reversible.
void set_decision_builder(DecisionBuilder *const db)
static const char kScalProdLessOrEqual[]
static const char kDifferenceOperation[]
void RestartCurrentSearch()
uint64 fail_stamp() const
The fail_stamp() is incremented after each backtrack.
static const char kAllowedAssignments[]
static const char kConvexPiecewise[]
void EndNextDecision(DecisionBuilder *const db, Decision *const d)
static const char kTimeLimitArgument[]
static const char kUsageLessConstantExtension[]
virtual void PeriodicCheck()
Periodic call to check limits in long running methods.
static const char kOptionalArgument[]
virtual void ApplyDecision(Decision *const d)
Before applying the decision.
static const char kStartSyncOnEndOperation[]
#define DCHECK_GT(val1, val2)
void inhibit(Solver *const s)
This method inhibits the demon in the search tree below the current position.
static const char kInversePermutation[]
void PostAndPropagate()
Calls Post and then Propagate to initialize the constraints.
void SetEndRange(IntervalVar *const var, int64 new_min, int64 new_max) override
DecisionBuilder * MakeApplyBranchSelector(BranchSelector bs)
Creates a decision builder that will set the branch selector.
void CleanVariableOnFail(IntVar *const var)
#define CHECK_GT(val1, val2)
void BeginDemonRun(Demon *const demon) override
static const char kNonEqual[]
void SetSearchContext(Search *search, const std::string &search_context)
std::string DebugString() const override
static const char kSmartTimeCheckArgument[]
static const uint64 kuint64max
StateInfo(void *pinfo, int iinfo, int d, int ld)
MarkerType
This enum is used internally in private methods Solver::PushState and Solver::PopState to tag states ...
PropagationMonitor * GetPropagationMonitor() const
Returns the propagation monitor.
void AcceptNeighbor(Search *const search)
virtual void RemoveValue(IntVar *const var, int64 value)=0
static const char kTransition[]
void DeleteDemonProfiler(DemonProfiler *const monitor)
static const char kCountAssignedItemsExtension[]
Extension names:
int64 wall_time() const
DEPRECATED: Use Now() instead.
void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
A search monitor is a simple set of callbacks to monitor all search events.
static const char kLateDateArgument[]
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
ModelCache * BuildModelCache(Solver *const solver)
static const char kSortingConstraint[]
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
virtual void Apply(Solver *const s)=0
Apply will be called first when the decision is executed.
static const char kIsEqual[]
std::string DebugString() const override
void SetValues(IntVar *const var, const std::vector< int64 > &values) override
void PopContext() override
static const char kWeightedSumOfAssignedEqualVariableExtension[]
static const char kSizeXArgument[]
static const char kEndExpr[]
static const char kOpposite[]
static const char kMinArgument[]
int SolveDepth() const
Gets the number of nested searches.
void InternalSaveBooleanVarValue(Solver *const solver, IntVar *const var)
virtual void VisitIntegerVariableEvaluatorArgument(const std::string &arg_name, const Solver::Int64ToIntVar &arguments)
Helpers.
virtual void BeginVisitModel(const std::string &type_name)
--— Virtual methods for visitors --—
static const char kBranchesLimitArgument[]
Holds semantic information stating that the 'expression' has been cast into 'variable' using the Var(...
virtual void BeginVisitExtension(const std::string &type)
static const char kAbs[]
Constraint and Expression types.
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *const argument)
Visit integer expression argument.
static const char kNotMember[]
void set_search_context(const std::string &search_context)
#define CP_DO_FAIL(search)
virtual void VisitSequenceArgument(const std::string &arg_name, SequenceVar *const argument)
Visit sequence argument.
static const char kTargetArgument[]
virtual void EndNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
void NewSearch(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
void DeleteLocalSearchProfiler(LocalSearchProfiler *monitor)
static const char kCover[]
std::string DebugString() const
!defined(SWIG)
void set_should_restart(bool s)
void EndInitialPropagation()
static const char kCountArgument[]
virtual void RegisterDemon(Demon *const demon)=0
static const char kSumGreaterOrEqual[]
uint64 stamp() const
The stamp indicates how many moves in the search tree we have performed.
void RankFirst(SequenceVar *const var, int index) override
SequenceVar modifiers.
static const char kFalseConstraint[]
static const char kCumulativeArgument[]
virtual void SetStartMax(IntervalVar *const var, int64 new_max)=0
static const char kMapDomain[]
Solver::DecisionModification ModifyDecision()
@ PROBLEM_INFEASIBLE
After search, the model is infeasible.
~PropagationMonitor() override
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
bool CurrentlyInSolve() const
Returns true whether the current search has been created using a Solve() call instead of a NewSearch ...
virtual std::string DebugString() const
virtual void Accept(ModelVisitor *const visitor) const
static const char kSumOperation[]
static const char kScalProd[]
static const char kElementEqual[]
static const char kTraceOperation[]
static const char kCapacityArgument[]
void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
ConstraintSolverStatistics GetConstraintSolverStatistics() const
Returns detailed cp search statistics.
void IncrementSolutionCounter()
void BeginMakeNextNeighbor(const LocalSearchOperator *op) override
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
A BaseObject is the root of all reversibly allocated objects.
GurobiMPCallbackContext * context
virtual void RankNotLast(SequenceVar *const var, int index)=0
std::string DebugString() const override
Decision * MakeFailDecision()
static const char kSquare[]
static const char kBetween[]
static const char kInitialState[]
void SetStartRange(IntervalVar *const var, int64 new_min, int64 new_max) override
bool should_finish() const
static const char kVarValueWatcher[]
static const char kModuloArgument[]
static int64 MemoryUsage()
Current memory usage in bytes.
@ NO_CHANGE
Keeps the default behavior, i.e.
void EndNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested) override
@ SWITCH_BRANCHES
Applies right branch first.
static const char kDurationMaxArgument[]
std::vector< BaseObject ** > rev_object_array_memory_
void reset_action_on_fail()
void SetMax(IntVar *const var, int64 new_max) override
void RemoveValue(IntVar *const var, int64 value) override
@ NO_MORE_SOLUTIONS
After failed NextSolution and before EndSearch.
bool HasName(const PropagationBaseObject *object) const
Returns whether the object has been named or not.
void set_variable_to_clean_on_fail(IntVar *var)
static const char kPerformedExpr[]
virtual void Accept(DecisionVisitor *const visitor) const
Accepts the given visitor.
virtual IntVar * Var()
Creates a Boolean variable representing the status of the constraint (false = constraint is violated,...
static const char kNoCycle[]
std::function< IntVar *(int64)> Int64ToIntVar
Local Search Filters are used for fast neighbor pruning.
void ConstraintSolverFailsHere()
void SetRange(IntVar *const var, int64 new_min, int64 new_max) override
DemonProfiler * BuildDemonProfiler(Solver *const solver)
bool HasName() const
Returns whether the object has been named or not.
void PushContext(const std::string &context) override
void RestoreBoolValue(IntVar *const var)
static const char kEarlyDateArgument[]
static const char kTrueConstraint[]
void set_backtrack_at_the_end_of_the_search(bool restore)
static const char kSolutionLimitArgument[]
static const char kActiveArgument[]
argument names:
virtual void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &tuples)
static const char kSizeArgument[]
static const char kEarlyCostArgument[]
virtual std::string BaseName() const
Returns a base name for automatic naming.
static const char kEndsArgument[]
void BeginFiltering(const LocalSearchFilter *filter) override
static const char kElement[]
virtual void EndVisitModel(const std::string &type_name)
std::function< bool(int64)> IndexFilter1
static const char kIndexArgument[]
bool CheckAssignment(Assignment *const solution)
Checks whether the given assignment satisfies all relevant constraints.
This class represent a reversible FIFO structure.
static const char kFinalStatesArgument[]
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...
virtual void VisitSequenceVariable(const SequenceVar *const variable)
static const char kProductOperation[]
An Assignment is a variable -> domains mapping, used to report solutions to the user.
int64 GetProcessMemoryUsage()
void push_monitor(SearchMonitor *const m)
virtual void BeginConstraintInitialPropagation(Constraint *const constraint)=0
Propagation events.
virtual void EndOperatorStart()=0
static const char kCircuit[]
virtual void VisitUnknownDecision()
LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)
ModelVisitor * MakePrintModelVisitor()
Prints the model.
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
virtual void Accept(ModelVisitor *const visitor) const =0
Accepts the given visitor.
CompressedTrail< double > rev_doubles_
void RegisterDemon(Demon *const demon) override
static const char kVariableGroupExtension[]
void InstallLocalSearchProfiler(LocalSearchProfiler *monitor)
static const char kScalProdEqual[]
static const char kInt64ToBoolExtension[]
void SetValue(IntVar *const var, int64 value) override
Cast constraints are special channeling constraints designed to keep a variable in sync with an expre...
void BeginInitialPropagation()
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *const constraint)
std::function< DecisionModification()> BranchSelector
virtual void VisitSetVariableValue(IntVar *const var, int64 value)
virtual void BeginOperatorStart()=0
Local search operator events.
static const char kVariableArgument[]
virtual void SetEndMin(IntervalVar *const var, int64 new_min)=0
virtual void EnterSearch()
Beginning of the search.
static const char kValueArgument[]
static const char kPositionXArgument[]
virtual void SetStartRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
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...
static const char kIntervalArgument[]
static constexpr int64 kTestPeriod
LocalSearchMonitor(Solver *const solver)
std::string DebugString() const override
void SetStartMax(IntervalVar *const var, int64 new_max) override
static const char kEndMaxArgument[]
virtual void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
void RefuteDecision(Decision *const d)
void EndOperatorStart() override
#define CHECK_EQ(val1, val2)
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
virtual void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
static const char kIsMember[]
virtual void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments)
virtual void EndVisitExtension(const std::string &type)
void StartProcessingIntegerVariable(IntVar *const var) override
void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta) override
int64 size() const
Returns the number of interval vars in the sequence.
static const char kIntervalVariable[]
static const char kNullIntersect[]
virtual void InitialPropagate()=0
This method performs the initial propagation of the constraint.
static const char kAssumePathsArgument[]
static const char kInt64ToInt64Extension[]
LocalSearchMonitor * BuildLocalSearchMonitorMaster(Solver *const s)
static const char kTuplesArgument[]
This iterator is not stable with respect to deletion.
virtual void SetEndMax(IntervalVar *const var, int64 new_max)=0
A DecisionBuilder is responsible for creating the search tree.
int64 unchecked_solutions() const
The number of unchecked solutions found by local search.
virtual void VisitSplitVariableDomain(IntVar *const var, int64 value, bool start_with_lower_half)
IntExpr * CastExpression(const IntVar *const var) const
!defined(SWIG)
static const char kPartialArgument[]
static const char kScalProdGreaterOrEqual[]
virtual void SetStartMin(IntervalVar *const var, int64 new_min)=0
IntervalVar modifiers.
static const char kRelaxedMinOperation[]
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
virtual void BeginNextDecision(DecisionBuilder *const b)
Before calling DecisionBuilder::Next.
static const char kValuesArgument[]
static const char kLess[]
static const char kIndex2Argument[]
static constexpr int kNoProgress
static const char kIsBetween[]
virtual void PushContext(const std::string &context)=0
virtual void RemoveValues(IntVar *const var, const std::vector< int64 > &values)=0
int64 unchecked_solution_counter() const
int64 failures() const
The number of failures encountered since the creation of the solver.
static const char kIndexOf[]
bool AcceptDelta(Search *const search, Assignment *delta, Assignment *deltadelta)
static const char kDisjunctive[]
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
absl::Time Now() const
The 'absolute time' as seen by the solver.
void Install() override
Registers itself on the solver such that it gets notified of the search and propagation events.
std::function< void(Solver *)> Action
void EndFiltering(const LocalSearchFilter *filter, bool reject) override
CompressedTrail< uint64 > rev_uint64s_
virtual void EndDemonRun(Demon *const demon)=0
Trail(int block_size, ConstraintSolverParameters::TrailCompression compression_level)
virtual void Post()=0
This method is called when the constraint is processed by the solver.
static const char kCumulative[]
DecisionBuilder * MakeConstraintAdder(Constraint *const ct)
Returns a decision builder that will add the given constraint to the model.
#define DCHECK(condition)
static const char kPower[]
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64 index_min, int64 index_max)
static const char kIntervalsArgument[]
std::string model_name() const
Returns the name of the model.
static const char kIntervalBinaryRelation[]
Interval variables are often used in scheduling.
void SetEndMax(IntervalVar *const var, int64 new_max) override
A DecisionVisitor is used to inspect a decision.
virtual void AfterDecision(Decision *const d, bool apply)
Just after refuting or applying the decision, apply is true after Apply.
virtual void SetValues(IntVar *const var, const std::vector< int64 > &values)=0
void BeginAcceptNeighbor(const LocalSearchOperator *op) override
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
static const char kSearchLimitExtension[]
void SetDurationMax(IntervalVar *const var, int64 new_max) override
void ApplyDecision(Decision *const d)
virtual void VisitRankFirstInterval(SequenceVar *const sequence, int index)
static const char kObjectiveExtension[]
static const char kSizeYArgument[]
int left_search_depth() const
static const char kRelationArgument[]
void AcceptUncheckedNeighbor(Search *const search)
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
void BeginFilterNeighbor(const LocalSearchOperator *op) override
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
virtual void AppendMonitors(Solver *const solver, std::vector< SearchMonitor * > *const extras)
This method will be called at the start of the search.
void BeginOperatorStart() override
Local search operator events.
void Accept(ModelVisitor *const visitor) const
int SearchLeftDepth() const
Gets the search left depth of the current active search.
std::vector< BaseObject * > rev_object_memory_
#define DCHECK_GE(val1, val2)
virtual void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments)
virtual bool LocalOptimum()
When a local optimum is reached.
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
void SetRange(IntExpr *const expr, int64 new_min, int64 new_max) override
A constraint is the main modeling object.
std::vector< bool > rev_bool_value_
void set_action_on_fail(Solver::Action a)
static const char kLeftArgument[]
void EnqueueVar(Demon *const demon)
static const char kStartMaxArgument[]
void SetDurationMin(IntervalVar *const var, int64 new_min) override
static const char kConditionalExpr[]
static const char kAbsEqual[]
@ KEEP_LEFT
Right branches are ignored.
void SetMin(IntVar *const var, int64 new_min) override
IntVar modifiers.
void ProcessConstraints()
void RemoveValues(IntVar *const var, const std::vector< int64 > &values) override
static const char kDurationMinArgument[]
static const char kPathCumul[]
static const char kExpressionArgument[]
Search(Solver *const s, int)
virtual void NoMoreSolutions()
When the search tree is finished.
virtual bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
static const char kCountEqual[]
static const char kEndMinArgument[]
A Demon is the base element of a propagation queue.
void RankNotLast(SequenceVar *const var, int index) override
static const char kFailuresLimitArgument[]
void desinhibit(Solver *const s)
This method un-inhibits the demon that was previously inhibited.
std::function< int64(int64)> IndexEvaluator1
Callback typedefs.
Solver(const std::string &name)
Solver API.
static const char kUsageEqualVariableExtension[]
static const char kModulo[]
static const char kRightArgument[]
void AddPropagationMonitor(PropagationMonitor *const monitor)
Adds the propagation monitor to the solver.
static const char kDistribute[]
bool IsProfilingEnabled() const
Returns whether we are profiling the solver.
virtual void RankFirst(SequenceVar *const var, int index)=0
SequenceVar modifiers.
void SetDurationRange(IntervalVar *const var, int64 new_min, int64 new_max) override
SearchMonitor * MakeSearchTrace(const std::string &prefix)
Creates a search monitor that will trace precisely the behavior of the search.
virtual void RefuteDecision(Decision *const d)
Before refuting the decision.
static const char kIsGreaterOrEqual[]
void SetEndMin(IntervalVar *const var, int64 new_min) override
PropagationMonitor * BuildTrace(Solver *const s)
void IncrementUncheckedSolutionCounter()
virtual bool AtSolution()
This method is called when a valid solution is found.
bool created_by_solve() const
virtual bool AcceptSolution()
This method is called when a solution is found.
virtual void VisitScheduleOrExpedite(IntervalVar *const var, int64 est)
static const char kIsLess[]
void RemoveInterval(IntVar *const var, int64 imin, int64 imax) override
void BeginNextDecision(DecisionBuilder *const db)
static const char kDeviation[]
static const char kSequenceVariable[]
static const char kPack[]
virtual void AcceptNeighbor()
After accepting a neighbor during local search.
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
std::vector< int * > rev_int_memory_
@ IN_ROOT_NODE
Executing the root node.
void FreezeQueue()
This method freezes the propagation queue.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
bool should_restart() const
void FinishCurrentSearch()
Tells the solver to kill or restart the current search.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
static const char kIsLessOrEqual[]
static const char kSequencesArgument[]
bool InstrumentsVariables() const
Returns whether we are tracing variables.
void SetBranchSelector(BranchSelector bs)
Sets the given branch selector on the current active search.
IntervalVar * Interval(int index) const
Returns the index_th interval of the sequence.
std::string search_context() const
void RankLast(SequenceVar *const var, int index) override
virtual void EndProcessingIntegerVariable(IntVar *const var)=0
#define DCHECK_EQ(val1, val2)
virtual void RemoveInterval(IntVar *const var, int64 imin, int64 imax)=0
static const char kGlobalCardinality[]
static const char kMaxArgument[]
static const char kSumEqual[]
void Add(LocalSearchMonitor *monitor)
static constexpr int kNumPriorities
Number of priorities for demons.
static const char kDelayedPathCumul[]
void ExportProfilingOverview(const std::string &filename)
Exports the profiling information in a human readable overview.
virtual void EndNextDecision(DecisionBuilder *const b, Decision *const d)
After calling DecisionBuilder::Next, along with the returned decision.
@ NORMAL_PRIORITY
NORMAL_PRIORITY is the highest priority: Demons will be processed first.
virtual void SetPerformed(IntervalVar *const var, bool value)=0
void set_name(const std::string &name)
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
void EndConstraintInitialPropagation(Constraint *const constraint) override
The class IntExpr is the base of all integer expressions in constraint programming.
static const char kGreater[]
DecisionModification
The Solver is responsible for creating the search tree.
int64 solutions() const
The number of solutions found since the start of the search.
std::vector< void * > rev_memory_
void EnqueueDelayedDemon(Demon *const demon)
std::vector< int64 * > rev_int64_memory_
virtual void VisitIntervalVariable(const IntervalVar *const variable, const std::string &operation, int64 value, IntervalVar *const delegate)
The base class for all local search operators.
static const char kRangeArgument[]
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
static const char kFixedChargeArgument[]
virtual void SetDurationMax(IntervalVar *const var, int64 new_max)=0
BaseVariableAssignmentSelector *const selector_
static const char kLexLess[]
void ProcessOneDemon(Demon *const demon)
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0
void STLDeleteElements(T *container)
@ AT_SOLUTION
After successful NextSolution and before EndSearch.
static const char kMaxEqual[]
#define CHECK_NE(val1, val2)
static const char kProduct[]
void AddConstraint(Constraint *const c)
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
DecisionBuilder * decision_builder() const
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
bool LocalOptimumReached(Search *const search)
virtual void AcceptUncheckedNeighbor()
After accepting an unchecked neighbor during local search.
std::string LocalSearchProfile() const
Returns local search profiling information in a human readable format.
static const char kDurationExpr[]
static const char kDifference[]
CompressedTrail< void * > rev_ptrs_
void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1 &eval, const std::string &arg_name, int64 index_max)
Expands function as array when index min is 0.
virtual void Refute(Solver *const s)=0
Refute will be called after a backtrack.
virtual void VisitScheduleOrPostpone(IntervalVar *const var, int64 est)
std::string DebugString() const override
~LocalSearchMonitor() override
void set_search_left_depth(int d)
virtual Solver::DemonPriority priority() const
This method returns the priority of the demon.
static const char kMinEqual[]
virtual void PopContext()=0
virtual void ExitSearch()
End of the search.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
#define DCHECK_LE(val1, val2)
static const char kNextsArgument[]
static const char kMirrorOperation[]
Operations.
static const char kLateCostArgument[]
static const char kIntervalUnaryRelation[]
static const char kStartMinArgument[]
static const char kStartSyncOnStartOperation[]
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
Assignment * GetOrCreateLocalSearchState()
Returns (or creates) an assignment representing the state of local search.
virtual void EndInitialPropagation()
After the initial propagation.
static const char kMaximizeArgument[]
void Add(PropagationMonitor *const monitor)
void AcceptUncheckedNeighbor()
static const char kEvaluatorArgument[]
int64 branches() const
The number of branches explored since the creation of the solver.
void SetStartMin(IntervalVar *const var, int64 new_min) override
IntervalVar modifiers.
void Install() override
Install itself on the solver.
static const char kGreaterOrEqual[]
PropagationMonitor * BuildPrintTrace(Solver *const s)
static const char kTrace[]
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
static const char kIsDifferent[]
@ KEEP_RIGHT
Left branches are ignored.
void AfterDecision(Decision *const d, bool apply)
bool IsCastConstraint() const
Is the constraint created by a cast from expression to integer variable?
void EndDemonRun(Demon *const demon) override
virtual void VisitIntegerVariable(const IntVar *const variable, IntExpr *const delegate)
static const char kRelaxedMaxOperation[]
static const char kStepArgument[]
static const char kPositionYArgument[]
PropagationMonitor(Solver *const solver)
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *const constraint)
static const char kMember[]
virtual void BeginInitialPropagation()
Before the initial propagation.
static const char kVarBoundWatcher[]
void set_search_depth(int d)
int TopProgressPercent()
Returns a percentage representing the propress of the search before reaching the limits of the top-le...
StateInfo(void *pinfo, int iinfo)
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
bool ContainsKey(const Collection &collection, const Key &key)
void set_should_finish(bool s)
bool InstrumentsDemons() const
Returns whether we are instrumenting demons.
void BeginConstraintInitialPropagation(Constraint *const constraint) override
Propagation events.
static const char kCoefficientsArgument[]
static const char kLessOrEqual[]
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.
virtual void BeginDemonRun(Demon *const demon)=0
std::string SearchContext() const
static const char kTransitsArgument[]
A Decision represents a choice point in the search tree.