27#include "absl/algorithm/container.h"
28#include "absl/container/flat_hash_map.h"
29#include "absl/container/flat_hash_set.h"
30#include "absl/flags/flag.h"
31#include "absl/log/check.h"
32#include "absl/random/distributions.h"
33#include "absl/random/random.h"
34#include "absl/strings/str_cat.h"
35#include "absl/strings/str_format.h"
36#include "absl/strings/string_view.h"
37#include "absl/time/time.h"
38#include "absl/types/span.h"
53 "Frequency of checks for better solutions in the solution pool.");
56 "Size of TSPs solved in the TSPOpt operator.");
59 "Size of TSPs solved in the TSPLns operator.");
71bool AcceptDelta(Search* search, Assignment* delta, Assignment* deltadelta);
81 CHECK(delta !=
nullptr);
82 VLOG(2) <<
DebugString() <<
"::MakeNextNeighbor(delta=("
84 << (deltadelta ? deltadelta->
DebugString() : std::string(
"nullptr"))
113 for (
int candidate : fragment_) {
126 if (index >= 0 && index <
Size()) {
127 fragment_.push_back(index);
138class SimpleLns :
public BaseLns {
140 SimpleLns(
const std::vector<IntVar*>& vars,
int number_of_variables)
141 :
BaseLns(vars), index_(0), number_of_variables_(number_of_variables) {
142 CHECK_GT(number_of_variables_, 0);
144 ~SimpleLns()
override {}
145 void InitFragments()
override { index_ = 0; }
146 bool NextFragment()
override;
147 std::string DebugString()
const override {
return "SimpleLns"; }
151 const int number_of_variables_;
154bool SimpleLns::NextFragment() {
155 const int size = Size();
157 for (
int i = index_;
i < index_ + number_of_variables_; ++
i) {
158 AppendToFragment(i % size);
170class RandomLns :
public BaseLns {
172 RandomLns(
const std::vector<IntVar*>& vars,
int number_of_variables,
174 : BaseLns(vars), rand_(seed), number_of_variables_(number_of_variables) {
175 CHECK_GT(number_of_variables_, 0);
176 CHECK_LE(number_of_variables_, Size());
178 ~RandomLns()
override {}
179 bool NextFragment()
override;
181 std::string DebugString()
const override {
return "RandomLns"; }
185 const int number_of_variables_;
188bool RandomLns::NextFragment() {
189 DCHECK_GT(Size(), 0);
190 for (
int i = 0;
i < number_of_variables_; ++
i) {
191 AppendToFragment(absl::Uniform<int>(rand_, 0, Size()));
198 const std::vector<IntVar*>& vars,
int number_of_variables) {
203 const std::vector<IntVar*>& vars,
int number_of_variables, int32_t seed) {
204 return RevAlloc(
new RandomLns(vars, number_of_variables, seed));
215 MoveTowardTargetLS(
const std::vector<IntVar*>& variables,
216 const std::vector<int64_t>& target_values)
218 target_(target_values),
222 variable_index_(Size() - 1) {
223 CHECK_EQ(target_values.size(), variables.size()) <<
"Illegal arguments.";
226 ~MoveTowardTargetLS()
override {}
228 std::string DebugString()
const override {
return "MoveTowardTargetLS"; }
232 bool MakeOneNeighbor()
override {
233 while (num_var_since_last_start_ < Size()) {
234 ++num_var_since_last_start_;
235 variable_index_ = (variable_index_ + 1) % Size();
236 const int64_t target_value = target_.at(variable_index_);
237 const int64_t current_value = OldValue(variable_index_);
238 if (current_value != target_value) {
239 SetValue(variable_index_, target_value);
247 void OnStart()
override {
259 CHECK_GE(variable_index_, 0);
260 CHECK_LT(variable_index_, Size());
261 num_var_since_last_start_ = 0;
265 const std::vector<int64_t> target_;
268 int64_t variable_index_;
271 int64_t num_var_since_last_start_;
277 typedef std::vector<IntVarElement> Elements;
280 std::vector<IntVar*> vars;
281 std::vector<int64_t> values;
284 for (
const auto& it : elements) {
285 vars.push_back(it.Var());
286 values.push_back(it.Value());
292 const std::vector<IntVar*>& variables,
293 const std::vector<int64_t>& target_values) {
294 return RevAlloc(
new MoveTowardTargetLS(variables, target_values));
305 const int size =
Size();
306 while (index_ < size) {
315void ChangeValue::OnStart() { index_ = 0; }
320class IncrementValue :
public ChangeValue {
322 explicit IncrementValue(
const std::vector<IntVar*>& vars)
323 : ChangeValue(vars) {}
324 ~IncrementValue()
override {}
325 int64_t ModifyValue(int64_t, int64_t value)
override {
return value + 1; }
327 std::string DebugString()
const override {
return "IncrementValue"; }
334 explicit DecrementValue(
const std::vector<IntVar*>& vars)
335 : ChangeValue(vars) {}
336 ~DecrementValue()
override {}
337 int64_t ModifyValue(int64_t, int64_t value)
override {
return value - 1; }
339 std::string DebugString()
const override {
return "DecrementValue"; }
346 std::function<const std::vector<int>&(int, int)>;
350template <
bool ignore_path_vars>
354 const std::vector<IntVar*>& secondary_vars,
355 std::function<
int(int64_t)> start_empty_path_class,
359 (get_incoming_neighbors == nullptr &&
360 get_outgoing_neighbors == nullptr)
365 std::move(start_empty_path_class),
366 std::move(get_incoming_neighbors),
367 std::move(get_outgoing_neighbors)),
387 void OnNodeInitialization()
override { last_ = -1; }
393template <
bool ignore_path_vars>
395 const int64_t node0 = this->
BaseNode(0);
396 int64_t before_chain = node0;
397 int64_t after_chain = -1;
400 if (neighbor < 0 || this->
IsInactive(neighbor))
return false;
406 if (this->
IsPathEnd(neighbor))
return false;
408 after_chain = this->
Next(neighbor);
412 before_chain = this->
Prev(neighbor);
420 if (last_base_ != node0 || last_ == -1 || this->
HasNeighbors()) {
427 last_ = this->
Next(before_chain);
429 if (this->
ReverseChain(before_chain, after_chain, &chain_last)
432 && last_ != chain_last) {
438 DCHECK_EQ(before_chain, node0);
439 const int64_t to_move = this->
Next(last_);
440 DCHECK_EQ(this->
Next(to_move), after_chain);
441 return this->
MoveChain(last_, to_move, before_chain);
445 Solver* solver,
const std::vector<IntVar*>& vars,
446 const std::vector<IntVar*>& secondary_vars,
447 std::function<
int(int64_t)> start_empty_path_class,
450 if (secondary_vars.empty()) {
452 vars, secondary_vars, std::move(start_empty_path_class),
453 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));
456 vars, secondary_vars, std::move(start_empty_path_class),
457 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));
462template <
bool ignore_path_vars>
466 const std::vector<IntVar*>& secondary_vars, absl::string_view name,
467 std::function<
int(int64_t)> start_empty_path_class,
470 bool single_path =
false)
472 vars, secondary_vars,
473 (get_incoming_neighbors == nullptr &&
474 get_outgoing_neighbors == nullptr)
478 false,
std::move(start_empty_path_class),
479 chain_length == 1 ?
std::move(get_incoming_neighbors) : nullptr,
480 std::move(get_outgoing_neighbors)),
481 chain_length_(chain_length),
482 single_path_(single_path),
483 name_(
absl::StrCat(name,
"<", chain_length,
">")) {
484 CHECK_GT(chain_length_, 0);
499 const int64_t chain_length_;
500 const bool single_path_;
501 const std::string name_;
504template <
bool ignore_path_vars>
506 const auto do_move = [
this](int64_t before_chain, int64_t destination) {
508 int64_t chain_end = before_chain;
509 for (
int i = 0; i < chain_length_; ++i) {
510 if (this->
IsPathEnd(chain_end) || chain_end == destination)
return false;
511 chain_end = this->
Next(chain_end);
514 this->
MoveChain(before_chain, chain_end, destination);
516 const int64_t node0 = this->
BaseNode(0);
519 if (neighbor < 0 || this->
IsInactive(neighbor))
return false;
521 return do_move(this->
Prev(neighbor),
524 DCHECK_EQ(chain_length_, 1);
529 <<
"Path starts have no incoming neighbors.";
530 return do_move(this->
Prev(neighbor),
534 return do_move(node0, this->
BaseNode(1));
538 Solver* solver,
const std::vector<IntVar*>& vars,
539 const std::vector<IntVar*>& secondary_vars,
540 std::function<
int(int64_t)> start_empty_path_class,
543 bool single_path,
const std::string& name) {
544 if (secondary_vars.empty()) {
546 vars, secondary_vars, name, std::move(start_empty_path_class),
547 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors),
548 chain_length, single_path));
551 vars, secondary_vars, name, std::move(start_empty_path_class),
552 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors),
553 chain_length, single_path));
558template <
bool ignore_path_vars>
562 const std::vector<IntVar*>& secondary_vars,
563 std::function<
int(int64_t)> start_empty_path_class,
567 (get_incoming_neighbors == nullptr &&
568 get_outgoing_neighbors == nullptr)
573 std::move(start_empty_path_class),
574 std::move(get_incoming_neighbors),
575 std::move(get_outgoing_neighbors)) {}
582template <
bool ignore_path_vars>
584 const int64_t node0 = this->
BaseNode(0);
587 if (neighbor < 0 || this->
IsInactive(neighbor))
return false;
593 <<
"Path starts have no incoming neighbors.";
601 Solver* solver,
const std::vector<IntVar*>& vars,
602 const std::vector<IntVar*>& secondary_vars,
603 std::function<
int(int64_t)> start_empty_path_class,
606 if (secondary_vars.empty()) {
608 vars, secondary_vars, std::move(start_empty_path_class),
609 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));
612 vars, secondary_vars, std::move(start_empty_path_class),
613 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));
618template <
bool ignore_path_vars>
621 Cross(
const std::vector<IntVar*>& vars,
622 const std::vector<IntVar*>& secondary_vars,
623 std::function<
int(int64_t)> start_empty_path_class,
627 (get_incoming_neighbors == nullptr &&
628 get_outgoing_neighbors == nullptr)
633 std::move(start_empty_path_class),
634 std::move(get_incoming_neighbors),
635 std::move(get_outgoing_neighbors)) {}
642template <
bool ignore_path_vars>
644 const int64_t start0 = this->
StartNode(0);
646 const int64_t node0 = this->
BaseNode(0);
648 if (node0 == start0)
return false;
649 bool cross_path_starts =
false;
652 if (neighbor < 0)
return false;
653 cross_path_starts = outgoing;
664 node1 = cross_path_starts ? this->
Prev(neighbor) : this->
Next(neighbor);
668 cross_path_starts = start0 < start1;
670 if (start1 == start0 || node1 == start1)
return false;
673 if (cross_path_starts) {
682 const int first1 = this->
Next(start1);
684 moved |= this->
MoveChain(start0, node0, start1);
717 Solver* solver,
const std::vector<IntVar*>& vars,
718 const std::vector<IntVar*>& secondary_vars,
719 std::function<
int(int64_t)> start_empty_path_class,
722 if (secondary_vars.empty()) {
724 vars, secondary_vars, std::move(start_empty_path_class),
725 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));
728 vars, secondary_vars, std::move(start_empty_path_class),
729 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));
735template <
bool ignore_path_vars>
739 const std::vector<IntVar*>& vars,
740 const std::vector<IntVar*>& secondary_vars,
int number_of_base_nodes,
741 std::function<
int(int64_t)> start_empty_path_class,
745 number_of_base_nodes, false, false,
746 std::move(start_empty_path_class),
747 std::move(get_incoming_neighbors),
748 std::move(get_outgoing_neighbors)),
759 void OnNodeInitialization()
override;
764template <
bool ignore_path_vars>
765void BaseInactiveNodeToPathOperator<ignore_path_vars>::OnNodeInitialization() {
766 for (
int i = 0; i < this->Size(); ++i) {
767 if (this->IsInactive(i)) {
772 inactive_node_ = this->Size();
775template <
bool ignore_path_vars>
777 while (inactive_node_ < this->
Size()) {
791template <
bool ignore_path_vars>
796 const std::vector<IntVar*>& secondary_vars,
797 std::function<
int(int64_t)> start_empty_path_class,
801 vars, secondary_vars, 1,
std::move(start_empty_path_class),
802 std::move(get_incoming_neighbors),
803 std::move(get_outgoing_neighbors)) {}
807 std::string
DebugString()
const override {
return "MakeActiveOperator"; }
810template <
bool ignore_path_vars>
818 Solver* solver,
const std::vector<IntVar*>& vars,
819 const std::vector<IntVar*>& secondary_vars,
820 std::function<
int(int64_t)> start_empty_path_class,
823 if (secondary_vars.empty()) {
825 vars, secondary_vars, std::move(start_empty_path_class),
826 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));
829 vars, secondary_vars, std::move(start_empty_path_class),
830 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));
835template <
bool ignore_path_vars>
840 const std::vector<IntVar*>& vars,
841 const std::vector<IntVar*>& secondary_vars,
842 std::function<
int(int64_t)> start_empty_path_class)
844 vars, secondary_vars, 2,
std::move(start_empty_path_class)) {}
847 const int64_t before_node_to_move = this->
BaseNode(1);
848 const int64_t node = this->
Next(before_node_to_move);
855 return "RelocateAndMakeActiveOperator";
860 Solver* solver,
const std::vector<IntVar*>& vars,
861 const std::vector<IntVar*>& secondary_vars,
862 std::function<
int(int64_t)> start_empty_path_class) {
863 if (secondary_vars.empty()) {
865 vars, secondary_vars, std::move(start_empty_path_class)));
868 vars, secondary_vars, std::move(start_empty_path_class)));
873template <
bool ignore_path_vars>
878 const std::vector<IntVar*>& vars,
879 const std::vector<IntVar*>& secondary_vars,
880 std::function<
int(int64_t)> start_empty_path_class)
882 vars, secondary_vars, 3,
std::move(start_empty_path_class)) {}
890 return "ExchangeAndMakeActiveOperator";
895 return base_index == 2;
900 Solver* solver,
const std::vector<IntVar*>& vars,
901 const std::vector<IntVar*>& secondary_vars,
902 std::function<
int(int64_t)> start_empty_path_class) {
903 if (secondary_vars.empty()) {
905 vars, secondary_vars, std::move(start_empty_path_class)));
908 vars, secondary_vars, std::move(start_empty_path_class)));
913template <
bool ignore_path_vars>
918 const std::vector<IntVar*>& vars,
919 const std::vector<IntVar*>& secondary_vars,
920 std::function<
int(int64_t)> start_empty_path_class)
922 vars, secondary_vars, 2,
std::move(start_empty_path_class)) {}
925 return (base_index == 1) ? this->
Prev(this->
EndNode(1))
929 const int64_t end_node0 = this->
Prev(this->
EndNode(0));
930 const int64_t end_node1 = this->
BaseNode(1);
931 if (end_node0 == end_node1 || end_node1 != this->
Prev(this->
EndNode(1))) {
936 DCHECK_NE(start_node0, start_node1);
937 return this->
SwapNodes(end_node0, end_node1) &&
938 this->
SwapNodes(start_node0, start_node1) &&
942 return "ExchangePathEndsAndMakeActiveOperator";
947 Solver* solver,
const std::vector<IntVar*>& vars,
948 const std::vector<IntVar*>& secondary_vars,
949 std::function<
int(int64_t)> start_empty_path_class) {
950 if (secondary_vars.empty()) {
953 vars, secondary_vars, std::move(start_empty_path_class)));
956 vars, secondary_vars, std::move(start_empty_path_class)));
961template <
bool ignore_path_vars>
966 const std::vector<IntVar*>& vars,
967 const std::vector<IntVar*>& secondary_vars,
968 std::function<
int(int64_t)> start_empty_path_class)
970 vars, secondary_vars, 2,
std::move(start_empty_path_class)) {}
975 return "MakeActiveAndRelocateOperator";
979template <
bool ignore_path_vars>
981 const int64_t before_chain = this->
BaseNode(1);
982 const int64_t chain_end = this->
Next(before_chain);
983 const int64_t destination = this->
BaseNode(0);
985 this->
MoveChain(before_chain, chain_end, destination) &&
990 Solver* solver,
const std::vector<IntVar*>& vars,
991 const std::vector<IntVar*>& secondary_vars,
992 std::function<
int(int64_t)> start_empty_path_class) {
993 if (secondary_vars.empty()) {
995 vars, secondary_vars, std::move(start_empty_path_class)));
998 vars, secondary_vars, std::move(start_empty_path_class)));
1003template <
bool ignore_path_vars>
1007 const std::vector<IntVar*>& secondary_vars,
1008 std::function<
int(int64_t)> start_empty_path_class)
1009 :
PathOperator<ignore_path_vars>(vars, secondary_vars, 1, true, false,
1010 std::move(start_empty_path_class),
1011 nullptr, nullptr) {}
1018 std::string
DebugString()
const override {
return "MakeInactiveOperator"; }
1022 Solver* solver,
const std::vector<IntVar*>& vars,
1023 const std::vector<IntVar*>& secondary_vars,
1024 std::function<
int(int64_t)> start_empty_path_class) {
1025 if (secondary_vars.empty()) {
1027 vars, secondary_vars, std::move(start_empty_path_class)));
1030 vars, secondary_vars, std::move(start_empty_path_class)));
1035template <
bool ignore_path_vars>
1039 const std::vector<IntVar*>& vars,
1040 const std::vector<IntVar*>& secondary_vars,
1041 std::function<
int(int64_t)> start_empty_path_class)
1042 :
PathOperator<ignore_path_vars>(vars, secondary_vars, 2, true, false,
1043 std::move(start_empty_path_class),
1044 nullptr, nullptr) {}
1047 const int64_t destination = this->
BaseNode(1);
1048 const int64_t before_to_move = this->
BaseNode(0);
1049 const int64_t node_to_inactivate = this->
Next(destination);
1050 if (node_to_inactivate == before_to_move ||
1055 const int64_t node = this->
Next(before_to_move);
1057 this->
MoveChain(before_to_move, node, destination);
1061 return "RelocateAndMakeInactiveOperator";
1066 Solver* solver,
const std::vector<IntVar*>& vars,
1067 const std::vector<IntVar*>& secondary_vars,
1068 std::function<
int(int64_t)> start_empty_path_class) {
1069 if (secondary_vars.empty()) {
1071 vars, secondary_vars, std::move(start_empty_path_class)));
1074 vars, secondary_vars, std::move(start_empty_path_class)));
1079template <
bool ignore_path_vars>
1083 const std::vector<IntVar*>& secondary_vars,
1084 std::function<
int(int64_t)> start_empty_path_class)
1085 :
PathOperator<ignore_path_vars>(vars, secondary_vars, 2,
1088 std::move(start_empty_path_class),
1089 nullptr, nullptr) {}
1092 const int64_t chain_end = this->
BaseNode(1);
1094 !this->
Var(chain_end)->Contains(chain_end)) {
1104 return "MakeChainInactiveOperator";
1116 return (base_index == 0) ? this->
StartNode(base_index)
1122 Solver* solver,
const std::vector<IntVar*>& vars,
1123 const std::vector<IntVar*>& secondary_vars,
1124 std::function<
int(int64_t)> start_empty_path_class) {
1125 if (secondary_vars.empty()) {
1127 vars, secondary_vars, std::move(start_empty_path_class)));
1130 vars, secondary_vars, std::move(start_empty_path_class)));
1135template <
bool ignore_path_vars>
1140 const std::vector<IntVar*>& secondary_vars,
1141 std::function<
int(int64_t)> start_empty_path_class)
1143 vars, secondary_vars, 1,
std::move(start_empty_path_class)) {}
1151 std::string
DebugString()
const override {
return "SwapActiveOperator"; }
1155 Solver* solver,
const std::vector<IntVar*>& vars,
1156 const std::vector<IntVar*>& secondary_vars,
1157 std::function<
int(int64_t)> start_empty_path_class) {
1158 if (secondary_vars.empty()) {
1160 vars, secondary_vars, std::move(start_empty_path_class)));
1163 vars, secondary_vars, std::move(start_empty_path_class)));
1168template <
bool ignore_path_vars>
1173 const std::vector<IntVar*>& secondary_vars,
1174 std::function<
int(int64_t)> start_empty_path_class,
1177 vars, secondary_vars, 2,
std::move(start_empty_path_class)),
1178 last_before_chain_(-1),
1179 last_chain_end_(-1),
1180 current_chain_size_(0),
1181 max_chain_size_(max_chain_size) {
1182 DCHECK_GE(max_chain_size_, 1);
1190 last_chain_end_ = -1;
1191 current_chain_size_ = 0;
1206 std::string
DebugString()
const override {
return "SwapActiveChainOperator"; }
1209 void OnNodeInitialization()
override {
1210 last_chain_end_ = -1;
1211 current_chain_size_ = 0;
1214 int64_t last_before_chain_;
1215 int64_t last_chain_end_;
1216 int current_chain_size_;
1217 const int max_chain_size_;
1220template <
bool ignore_path_vars>
1222 const int64_t before_chain = this->
BaseNode(0);
1223 const int64_t chain_end = this->
BaseNode(1);
1224 if (last_before_chain_ != before_chain || last_chain_end_ == -1) {
1226 last_before_chain_ = before_chain;
1228 if (!this->
IsPathEnd(chain_end) && before_chain != chain_end &&
1231 ++current_chain_size_;
1234 last_chain_end_ = -1;
1235 current_chain_size_ = 0;
1239 if (current_chain_size_ >= max_chain_size_) {
1242 current_chain_size_ = 0;
1245 if (!this->
IsPathEnd(last_chain_end_) &&
1247 ++current_chain_size_;
1250 last_chain_end_ = -1;
1251 current_chain_size_ = 0;
1256 Solver* solver,
const std::vector<IntVar*>& vars,
1257 const std::vector<IntVar*>& secondary_vars,
1258 std::function<
int(int64_t)> start_empty_path_class,
int max_chain_size) {
1259 if (secondary_vars.empty()) {
1261 vars, secondary_vars, std::move(start_empty_path_class),
1265 vars, secondary_vars, std::move(start_empty_path_class), max_chain_size));
1270template <
bool ignore_path_vars>
1275 const std::vector<IntVar*>& secondary_vars,
1276 std::function<
int(int64_t)> start_empty_path_class)
1278 vars, secondary_vars, 2,
std::move(start_empty_path_class)) {}
1281 const int64_t base0 = this->
BaseNode(0);
1282 const int64_t base1 = this->
BaseNode(1);
1283 if (this->
Next(base0) == base1) {
1291 return "ExtendedSwapActiveOperator";
1296 Solver* solver,
const std::vector<IntVar*>& vars,
1297 const std::vector<IntVar*>& secondary_vars,
1298 std::function<
int(int64_t)> start_empty_path_class) {
1299 if (secondary_vars.empty()) {
1301 vars, secondary_vars, std::move(start_empty_path_class)));
1304 vars, secondary_vars, std::move(start_empty_path_class)));
1309template <
bool ignore_path_vars>
1312 TSPOpt(
const std::vector<IntVar*>& vars,
1313 const std::vector<IntVar*>& secondary_vars,
1321 std::vector<std::vector<int64_t>> cost_;
1323 hamiltonian_path_solver_;
1325 const int chain_length_;
1328template <
bool ignore_path_vars>
1330 const std::vector<IntVar*>& secondary_vars,
1333 :
PathOperator<ignore_path_vars>(vars, secondary_vars, 1, true, false,
1334 nullptr, nullptr, nullptr),
1335 hamiltonian_path_solver_(cost_),
1336 evaluator_(
std::move(evaluator)),
1337 chain_length_(chain_length) {}
1339template <
bool ignore_path_vars>
1341 std::vector<int64_t> nodes;
1342 int64_t chain_end = this->
BaseNode(0);
1343 for (
int i = 0; i < chain_length_ + 1; ++i) {
1344 nodes.push_back(chain_end);
1348 chain_end = this->
Next(chain_end);
1350 if (nodes.size() <= 3) {
1354 const int size = nodes.size() - 1;
1356 for (
int i = 0; i < size; ++i) {
1357 cost_[i].resize(size);
1358 cost_[i][0] = evaluator_(nodes[i], nodes[size], chain_path);
1359 for (
int j = 1; j < size; ++j) {
1360 cost_[i][j] = evaluator_(nodes[i], nodes[j], chain_path);
1363 hamiltonian_path_solver_.ChangeCostMatrix(cost_);
1364 std::vector<PathNodeIndex> path;
1365 hamiltonian_path_solver_.TravelingSalesmanPath(&path);
1366 CHECK_EQ(size + 1, path.size());
1367 for (
int i = 0; i < size - 1; ++i) {
1368 this->
SetNext(nodes[path[i]], nodes[path[i + 1]], chain_path);
1370 this->
SetNext(nodes[path[size - 1]], nodes[size], chain_path);
1375 const std::vector<IntVar*>& vars,
1376 const std::vector<IntVar*>& secondary_vars,
1379 if (secondary_vars.empty()) {
1381 vars, secondary_vars, std::move(evaluator), chain_length));
1384 vars, secondary_vars, std::move(evaluator), chain_length));
1387template <
bool ignore_path_vars>
1390 TSPLns(
const std::vector<IntVar*>& vars,
1391 const std::vector<IntVar*>& secondary_vars,
1402 void OnNodeInitialization()
override {
1404 has_long_enough_paths_ = this->
Size() != 0;
1407 std::vector<std::vector<int64_t>> cost_;
1408 HamiltonianPathSolver<int64_t, std::vector<std::vector<int64_t>>>
1409 hamiltonian_path_solver_;
1411 const int tsp_size_;
1413 bool has_long_enough_paths_;
1416template <
bool ignore_path_vars>
1418 const std::vector<IntVar*>& secondary_vars,
1421 :
PathOperator<ignore_path_vars>(vars, secondary_vars, 1, true, false,
1422 nullptr, nullptr, nullptr),
1423 hamiltonian_path_solver_(cost_),
1424 evaluator_(
std::move(evaluator)),
1425 tsp_size_(tsp_size),
1427 has_long_enough_paths_(true) {
1428 CHECK_GE(tsp_size_, 0);
1429 cost_.resize(tsp_size_);
1430 for (
int i = 0; i < tsp_size_; ++i) {
1431 cost_[i].resize(tsp_size_);
1435template <
bool ignore_path_vars>
1437 while (has_long_enough_paths_) {
1438 has_long_enough_paths_ =
false;
1442 this->
Var(0)->solver()->TopPeriodicCheck();
1447template <
bool ignore_path_vars>
1449 const int64_t base_node = this->
BaseNode(0);
1450 std::vector<int64_t> nodes;
1452 node = this->
Next(node)) {
1453 nodes.push_back(node);
1455 if (nodes.size() <= tsp_size_) {
1458 has_long_enough_paths_ =
true;
1461 absl::flat_hash_set<int64_t> breaks_set;
1463 breaks_set.insert(base_node);
1464 CHECK(!nodes.empty());
1465 while (breaks_set.size() < tsp_size_) {
1466 breaks_set.insert(nodes[absl::Uniform<int>(rand_, 0, nodes.size())]);
1468 CHECK_EQ(breaks_set.size(), tsp_size_);
1473 std::vector<int> breaks;
1474 std::vector<int64_t> meta_node_costs;
1477 int64_t node_path = this->
Path(node);
1479 int64_t next = this->
Next(node);
1480 if (breaks_set.contains(node)) {
1481 breaks.push_back(node);
1482 meta_node_costs.push_back(cost);
1485 cost =
CapAdd(cost, evaluator_(node, next, node_path));
1489 meta_node_costs[0] += cost;
1490 CHECK_EQ(breaks.size(), tsp_size_);
1492 CHECK_EQ(meta_node_costs.size(), tsp_size_);
1493 for (
int i = 0; i < tsp_size_; ++i) {
1496 evaluator_(breaks[i], this->
Next(breaks[tsp_size_ - 1]), node_path));
1497 for (
int j = 1; j < tsp_size_; ++j) {
1499 CapAdd(meta_node_costs[i],
1500 evaluator_(breaks[i], this->
Next(breaks[j - 1]), node_path));
1505 hamiltonian_path_solver_.ChangeCostMatrix(cost_);
1506 std::vector<PathNodeIndex> path;
1507 hamiltonian_path_solver_.TravelingSalesmanPath(&path);
1508 bool nochange =
true;
1509 for (
int i = 0; i < path.size() - 1; ++i) {
1518 CHECK_EQ(0, path[path.size() - 1]);
1519 for (
int i = 0; i < tsp_size_ - 1; ++i) {
1520 this->
SetNext(breaks[path[i]], this->
OldNext(breaks[path[i + 1] - 1]),
1523 this->
SetNext(breaks[path[tsp_size_ - 1]],
1524 this->
OldNext(breaks[tsp_size_ - 1]), node_path);
1529 const std::vector<IntVar*>& vars,
1530 const std::vector<IntVar*>& secondary_vars,
1533 if (secondary_vars.empty()) {
1535 new TSPLns<true>(vars, secondary_vars, std::move(evaluator), tsp_size));
1538 new TSPLns<false>(vars, secondary_vars, std::move(evaluator), tsp_size));
1549template <
bool ignore_path_vars>
1562 const std::vector<int>&
Neighbors(
int index)
const;
1564 virtual std::string
DebugString()
const {
return "NearestNeighbors"; }
1567 void ComputeNearest(
int row, absl::Span<const int> path);
1569 std::vector<std::vector<int>> neighbors_;
1575template <
bool ignore_path_vars>
1579 : neighbors_(path_operator.number_of_nexts()),
1580 evaluator_(
std::move(evaluator)),
1581 path_operator_(path_operator),
1584template <
bool ignore_path_vars>
1586 absl::Span<const int> path) {
1587 for (
int node : path) {
1588 if (node < path_operator_.number_of_nexts()) ComputeNearest(node, path);
1592template <
bool ignore_path_vars>
1595 return neighbors_[index];
1598template <
bool ignore_path_vars>
1599void NearestNeighbors<ignore_path_vars>::ComputeNearest(
1600 int row, absl::Span<const int> path_nodes) {
1602 const int path = path_operator_.Path(row);
1603 const IntVar* var = path_operator_.
Var(row);
1604 using ValuedIndex = std::pair<int64_t ,
int >;
1605 std::vector<ValuedIndex> neighbors;
1606 for (
int index : path_nodes) {
1607 if (!var->
Contains(index))
continue;
1608 neighbors.push_back({evaluator_(row, index, path), index});
1610 const int neighbors_size = neighbors.size();
1611 if (neighbors_size > size_) {
1612 std::nth_element(neighbors.begin(), neighbors.begin() + size_ - 1,
1617 neighbors_[row].clear();
1618 for (
int i = 0;
i < std::min(size_, neighbors_size); ++
i) {
1619 neighbors_[row].push_back(neighbors[i].second);
1621 std::sort(neighbors_[row].begin(), neighbors_[row].end());
1624template <
bool ignore_path_vars>
1628 const std::vector<IntVar*>& secondary_vars,
1636 void OnNodeInitialization()
override;
1638 bool GetBestOut(int64_t in_i, int64_t in_j, int64_t* out, int64_t* gain);
1642 absl::flat_hash_set<int64_t> marked_;
1644 std::vector<int> old_path_starts_;
1651template <
bool ignore_path_vars>
1653 const std::vector<IntVar*>& vars,
1654 const std::vector<IntVar*>& secondary_vars,
1656 :
PathOperator<ignore_path_vars>(vars, secondary_vars, 1, true, false,
1657 nullptr, nullptr, nullptr),
1658 evaluator_(evaluator),
1659 neighbors_(evaluator, *this, 5 + 1),
1664template <
bool ignore_path_vars>
1665void LinKernighan<ignore_path_vars>::OnNodeInitialization() {
1666 absl::flat_hash_set<int> touched_paths;
1667 for (
int i = 0; i < this->number_of_nexts(); ++i) {
1668 if (this->IsPathStart(i)) {
1669 for (
int node = i; !this->IsPathEnd(node); node = this->
Next(node)) {
1670 if (i != old_path_starts_[node]) {
1671 touched_paths.insert(old_path_starts_[node]);
1672 touched_paths.insert(i);
1673 old_path_starts_[node] = i;
1676 }
else if (this->
Next(i) == i) {
1677 touched_paths.insert(old_path_starts_[i]);
1678 old_path_starts_[
i] = -1;
1681 for (
int touched_path_start : touched_paths) {
1682 if (touched_path_start == -1)
continue;
1683 std::vector<int> path;
1684 int node = touched_path_start;
1685 while (!this->IsPathEnd(node)) {
1686 path.push_back(node);
1687 node = this->
Next(node);
1689 path.push_back(node);
1690 neighbors_.Initialize(path);
1694template <
bool ignore_path_vars>
1698 int64_t path = this->
Path(node);
1699 int64_t
base = node;
1700 int64_t next = this->
Next(node);
1701 if (this->
IsPathEnd(next))
return false;
1704 marked_.insert(node);
1706 if (!GetBestOut(node, next, &out, &gain))
return false;
1707 marked_.insert(next);
1708 marked_.insert(out);
1709 const int64_t node1 = out;
1710 if (this->
IsPathEnd(node1))
return false;
1711 const int64_t next1 = this->
Next(node1);
1712 if (this->
IsPathEnd(next1))
return false;
1713 if (!GetBestOut(node1, next1, &out, &gain))
return false;
1714 marked_.insert(next1);
1715 marked_.insert(out);
1720 const int64_t next_out = this->
Next(out);
1721 const int64_t in_cost = evaluator_(node, next_out, path);
1722 const int64_t out_cost = evaluator_(out, next_out, path);
1723 if (
CapAdd(
CapSub(gain, in_cost), out_cost) > 0)
return true;
1725 if (this->
IsPathEnd(node))
return false;
1727 if (this->
IsPathEnd(next))
return false;
1730 while (GetBestOut(node, next, &out, &gain)) {
1731 marked_.insert(next);
1732 marked_.insert(out);
1734 if (this->
Next(base) == out ||
1742 LOG(ERROR) <<
"ReverseChain failed: " <<
base <<
" " << out;
1744 node = this->
Next(node)) {
1745 LOG(ERROR) <<
"node: " << node;
1747 LOG(ERROR) <<
"node: " << node;
1751 const int64_t in_cost = evaluator_(
base, chain_last, path);
1752 const int64_t out_cost = evaluator_(chain_last, out, path);
1768template <
bool ignore_path_vars>
1769bool LinKernighan<ignore_path_vars>::GetBestOut(int64_t in_i, int64_t in_j,
1770 int64_t* out, int64_t* gain) {
1771 int64_t best_gain = std::numeric_limits<int64_t>::min();
1772 const int64_t path = this->Path(in_i);
1773 const int64_t out_cost = evaluator_(in_i, in_j, path);
1774 const int64_t current_gain =
CapAdd(*gain, out_cost);
1775 for (
int next : neighbors_.Neighbors(in_j)) {
1776 if (next != in_j && next != this->
Next(in_j) && !marked_.contains(in_j) &&
1777 !marked_.contains(next)) {
1778 const int64_t in_cost = evaluator_(in_j, next, path);
1779 const int64_t new_gain =
CapSub(current_gain, in_cost);
1780 if (new_gain > 0 && best_gain < new_gain) {
1782 best_gain = new_gain;
1787 return (best_gain > std::numeric_limits<int64_t>::min());
1791 Solver* solver,
const std::vector<IntVar*>& vars,
1792 const std::vector<IntVar*>& secondary_vars,
1794 if (secondary_vars.empty()) {
1796 std::move(evaluator), topt));
1799 std::move(evaluator), topt));
1804template <
bool ignore_path_vars>
1808 const std::vector<IntVar*>& secondary_vars,
int number_of_chunks,
1809 int chunk_size,
bool unactive_fragments)
1810 :
PathOperator<ignore_path_vars>(vars, secondary_vars, number_of_chunks,
1811 true, true, nullptr, nullptr, nullptr),
1812 number_of_chunks_(number_of_chunks),
1813 chunk_size_(chunk_size),
1814 unactive_fragments_(unactive_fragments) {
1815 CHECK_GE(chunk_size_, 0);
1824 inline bool ChainsAreFullPaths()
const {
return chunk_size_ == 0; }
1825 void DeactivateChain(int64_t node);
1826 void DeactivateUnactives();
1828 const int number_of_chunks_;
1829 const int chunk_size_;
1830 const bool unactive_fragments_;
1833template <
bool ignore_path_vars>
1835 if (ChainsAreFullPaths()) {
1839 for (
int i = 0; i < number_of_chunks_; ++i) {
1843 for (
int i = 0; i < number_of_chunks_; ++i) {
1844 DeactivateChain(this->
BaseNode(i));
1846 DeactivateUnactives();
1850template <
bool ignore_path_vars>
1851void PathLns<ignore_path_vars>::DeactivateChain(int64_t node) {
1852 for (
int i = 0, current = node;
1853 (ChainsAreFullPaths() || i < chunk_size_) && !this->IsPathEnd(current);
1854 ++i, current = this->
Next(current)) {
1855 this->Deactivate(current);
1856 if constexpr (!ignore_path_vars) {
1857 this->Deactivate(this->number_of_nexts_ + current);
1862template <
bool ignore_path_vars>
1863void PathLns<ignore_path_vars>::DeactivateUnactives() {
1864 if (unactive_fragments_) {
1865 for (
int i = 0;
i < this->Size(); ++
i) {
1866 if (this->IsInactive(i)) {
1867 this->Deactivate(i);
1868 if constexpr (!ignore_path_vars) {
1869 this->Deactivate(this->number_of_nexts_ + i);
1877 const std::vector<IntVar*>& vars,
1878 const std::vector<IntVar*>& secondary_vars,
1879 int number_of_chunks,
int chunk_size,
1880 bool unactive_fragments) {
1881 if (secondary_vars.empty()) {
1883 number_of_chunks, chunk_size,
1884 unactive_fragments));
1887 vars, secondary_vars, number_of_chunks, chunk_size, unactive_fragments));
1895 : operator_(op), limit_(limit), next_neighborhood_calls_(0) {
1896 CHECK(op !=
nullptr);
1901 next_neighborhood_calls_ = 0;
1902 operator_->Start(assignment);
1906 if (next_neighborhood_calls_ >= limit_) {
1909 ++next_neighborhood_calls_;
1910 return operator_->MakeNextNeighbor(delta, deltadelta);
1913 bool HoldsDelta()
const override {
return operator_->HoldsDelta(); }
1915 std::string
DebugString()
const override {
return "NeighborhoodLimit"; }
1919 const int64_t limit_;
1920 int64_t next_neighborhood_calls_;
1933 CompoundOperator(std::vector<LocalSearchOperator*> operators,
1934 std::function<int64_t(
int,
int)> evaluator);
1935 ~CompoundOperator()
override {}
1936 void EnterSearch()
override;
1937 void Reset()
override;
1938 void Start(
const Assignment* assignment)
override;
1939 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta)
override;
1940 bool HasFragments()
const override {
return has_fragments_; }
1941 bool HoldsDelta()
const override {
return true; }
1943 std::string DebugString()
const override {
1944 return operators_.empty()
1946 : operators_[operator_indices_[index_]]->DebugString();
1948 const LocalSearchOperator* Self()
const override {
1949 return operators_.empty() ? this
1950 : operators_[operator_indices_[index_]]->Self();
1954 class OperatorComparator {
1956 OperatorComparator(std::function<int64_t(
int,
int)> evaluator,
1957 int active_operator)
1958 : evaluator_(std::move(evaluator)), active_operator_(active_operator) {}
1959 bool operator()(
int lhs,
int rhs)
const {
1960 const int64_t lhs_value = Evaluate(lhs);
1961 const int64_t rhs_value = Evaluate(rhs);
1962 return lhs_value < rhs_value || (lhs_value == rhs_value && lhs < rhs);
1966 int64_t Evaluate(
int operator_index)
const {
1967 return evaluator_(active_operator_, operator_index);
1970 std::function<int64_t(
int,
int)> evaluator_;
1971 const int active_operator_;
1975 std::vector<LocalSearchOperator*> operators_;
1976 std::vector<int> operator_indices_;
1977 std::function<int64_t(
int,
int)> evaluator_;
1978 Bitset64<> started_;
1979 const Assignment* start_assignment_;
1980 bool has_fragments_;
1983CompoundOperator::CompoundOperator(std::vector<LocalSearchOperator*> operators,
1984 std::function<int64_t(
int,
int)> evaluator)
1986 operators_(std::move(operators)),
1987 evaluator_(std::move(evaluator)),
1988 started_(operators_.size()),
1989 start_assignment_(nullptr),
1990 has_fragments_(
false) {
1991 operators_.erase(std::remove(operators_.begin(), operators_.end(),
nullptr),
1993 operator_indices_.resize(operators_.size());
1994 absl::c_iota(operator_indices_, 0);
1995 for (LocalSearchOperator*
const op : operators_) {
1996 if (op->HasFragments()) {
1997 has_fragments_ =
true;
2003void CompoundOperator::EnterSearch() {
2004 absl::c_iota(operator_indices_, 0);
2006 for (LocalSearchOperator*
const op : operators_) {
2011void CompoundOperator::Reset() {
2012 for (LocalSearchOperator*
const op : operators_) {
2017void CompoundOperator::Start(
const Assignment* assignment) {
2018 start_assignment_ = assignment;
2020 if (!operators_.empty()) {
2021 std::sort(operator_indices_.begin(), operator_indices_.end(),
2022 OperatorComparator(evaluator_, operator_indices_[index_]));
2027bool CompoundOperator::MakeNextNeighbor(Assignment* delta,
2028 Assignment* deltadelta) {
2029 const auto is_leaf = [](
const LocalSearchOperator* op) {
2030 return op == op->Self();
2032 if (!operators_.empty()) {
2033 Solver* solver = delta->solver();
2037 const int64_t operator_index = operator_indices_[index_];
2038 LocalSearchOperator* op = operators_[operator_index];
2039 if (!started_[operator_index]) {
2040 op->Start(start_assignment_);
2041 started_.
Set(operator_index);
2043 if (!op->HoldsDelta()) {
2047 solver->GetLocalSearchMonitor()->BeginMakeNextNeighbor(op);
2049 if (op->MakeNextNeighbor(delta, deltadelta))
return true;
2051 solver->GetLocalSearchMonitor()->EndMakeNextNeighbor(
2052 op,
false, delta, deltadelta);
2056 if (index_ == operators_.size()) {
2059 }
while (index_ != 0);
2064int64_t CompoundOperatorNoRestart(
int size,
int active_index,
2065 int operator_index) {
2066 return (operator_index < active_index) ? size + operator_index - active_index
2067 : operator_index - active_index;
2072 const std::vector<LocalSearchOperator*>& ops) {
2077 const std::vector<LocalSearchOperator*>& ops,
bool restart) {
2080 ops, std::function<int64_t(
int,
int)>([](
int,
int) {
return 0; }));
2082 const int size = ops.size();
2084 return CompoundOperatorNoRestart(size, i, j);
2089 const std::vector<LocalSearchOperator*>& ops,
2090 std::function<int64_t(
int,
int)> evaluator) {
2091 return RevAlloc(
new CompoundOperator(ops, std::move(evaluator)));
2097 explicit RandomCompoundOperator(std::vector<LocalSearchOperator*> operators);
2098 RandomCompoundOperator(std::vector<LocalSearchOperator*> operators,
2100 ~RandomCompoundOperator()
override {}
2101 void EnterSearch()
override;
2102 void Reset()
override;
2103 void Start(
const Assignment* assignment)
override;
2104 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta)
override;
2105 bool HoldsDelta()
const override {
return true; }
2107 std::string DebugString()
const override {
return "RandomCompoundOperator"; }
2112 const std::vector<LocalSearchOperator*> operators_;
2113 bool has_fragments_;
2116void RandomCompoundOperator::Start(
const Assignment* assignment) {
2117 for (LocalSearchOperator*
const op : operators_) {
2118 op->Start(assignment);
2122RandomCompoundOperator::RandomCompoundOperator(
2123 std::vector<LocalSearchOperator*> operators)
2124 : RandomCompoundOperator(std::move(operators),
CpRandomSeed()) {}
2126RandomCompoundOperator::RandomCompoundOperator(
2127 std::vector<LocalSearchOperator*> operators, int32_t seed)
2128 : rand_(seed), operators_(std::move(operators)), has_fragments_(
false) {
2129 for (LocalSearchOperator*
const op : operators_) {
2130 if (op->HasFragments()) {
2131 has_fragments_ =
true;
2137void RandomCompoundOperator::EnterSearch() {
2138 for (LocalSearchOperator*
const op : operators_) {
2143void RandomCompoundOperator::Reset() {
2144 for (LocalSearchOperator*
const op : operators_) {
2149bool RandomCompoundOperator::MakeNextNeighbor(Assignment* delta,
2150 Assignment* deltadelta) {
2151 const int size = operators_.size();
2152 std::vector<int> indices(size);
2153 absl::c_iota(indices, 0);
2154 std::shuffle(indices.begin(), indices.end(), rand_);
2155 for (
int index : indices) {
2156 if (!operators_[index]->HoldsDelta()) {
2159 if (operators_[index]->MakeNextNeighbor(delta, deltadelta)) {
2169 const std::vector<LocalSearchOperator*>& ops) {
2170 return RevAlloc(
new RandomCompoundOperator(ops));
2174 const std::vector<LocalSearchOperator*>& ops, int32_t seed) {
2175 return RevAlloc(
new RandomCompoundOperator(ops, seed));
2181 explicit MultiArmedBanditCompoundOperator(
2182 std::vector<LocalSearchOperator*> operators,
double memory_coefficient,
2183 double exploration_coefficient,
bool maximize);
2184 ~MultiArmedBanditCompoundOperator()
override {}
2185 void EnterSearch()
override;
2186 void Reset()
override;
2187 void Start(
const Assignment* assignment)
override;
2188 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta)
override;
2189 bool HoldsDelta()
const override {
return true; }
2191 std::string DebugString()
const override {
2192 return operators_.empty()
2194 : operators_[operator_indices_[index_]]->DebugString();
2196 const LocalSearchOperator* Self()
const override {
2197 return operators_.empty() ? this
2198 : operators_[operator_indices_[index_]]->Self();
2202 double Score(
int index);
2204 std::vector<LocalSearchOperator*> operators_;
2205 Bitset64<> started_;
2206 const Assignment* start_assignment_;
2207 bool has_fragments_;
2208 std::vector<int> operator_indices_;
2209 int64_t last_objective_;
2210 std::vector<double> avg_improvement_;
2212 std::vector<double> num_neighbors_per_operator_;
2213 const bool maximize_;
2218 const double memory_coefficient_;
2225 const double exploration_coefficient_;
2228MultiArmedBanditCompoundOperator::MultiArmedBanditCompoundOperator(
2229 std::vector<LocalSearchOperator*> operators,
double memory_coefficient,
2230 double exploration_coefficient,
bool maximize)
2232 operators_(std::move(operators)),
2233 started_(operators_.size()),
2234 start_assignment_(nullptr),
2235 has_fragments_(
false),
2236 last_objective_(std::numeric_limits<int64_t>::max()),
2238 maximize_(maximize),
2239 memory_coefficient_(memory_coefficient),
2240 exploration_coefficient_(exploration_coefficient) {
2241 DCHECK_GE(memory_coefficient_, 0);
2242 DCHECK_LE(memory_coefficient_, 1);
2243 DCHECK_GE(exploration_coefficient_, 0);
2244 operators_.erase(std::remove(operators_.begin(), operators_.end(),
nullptr),
2246 operator_indices_.resize(operators_.size());
2247 absl::c_iota(operator_indices_, 0);
2248 num_neighbors_per_operator_.resize(operators_.size(), 0);
2249 avg_improvement_.resize(operators_.size(), 0);
2250 for (LocalSearchOperator*
const op : operators_) {
2251 if (op->HasFragments()) {
2252 has_fragments_ =
true;
2258void MultiArmedBanditCompoundOperator::EnterSearch() {
2259 last_objective_ = std::numeric_limits<int64_t>::max();
2261 absl::c_iota(operator_indices_, 0);
2263 num_neighbors_per_operator_.resize(operators_.size(), 0);
2264 avg_improvement_.resize(operators_.size(), 0);
2265 for (LocalSearchOperator*
const op : operators_) {
2270void MultiArmedBanditCompoundOperator::Reset() {
2271 for (LocalSearchOperator*
const op : operators_) {
2276double MultiArmedBanditCompoundOperator::Score(
int index) {
2277 return avg_improvement_[index] +
2278 exploration_coefficient_ *
2279 sqrt(2 * log(1 + num_neighbors_) /
2280 (1 + num_neighbors_per_operator_[index]));
2283void MultiArmedBanditCompoundOperator::Start(
const Assignment* assignment) {
2284 start_assignment_ = assignment;
2286 if (operators_.empty())
return;
2288 const double objective = assignment->ObjectiveValue();
2290 if (objective == last_objective_)
return;
2292 if (last_objective_ == std::numeric_limits<int64_t>::max()) {
2293 last_objective_ = objective;
2297 const double improvement =
2298 maximize_ ? objective - last_objective_ : last_objective_ - objective;
2299 if (improvement < 0) {
2302 last_objective_ = objective;
2303 avg_improvement_[operator_indices_[index_]] +=
2304 memory_coefficient_ *
2305 (improvement - avg_improvement_[operator_indices_[index_]]);
2307 std::sort(operator_indices_.begin(), operator_indices_.end(),
2308 [
this](
int lhs,
int rhs) {
2309 const double lhs_score = Score(lhs);
2310 const double rhs_score = Score(rhs);
2311 return lhs_score > rhs_score ||
2312 (lhs_score == rhs_score && lhs < rhs);
2318bool MultiArmedBanditCompoundOperator::MakeNextNeighbor(
2319 Assignment* delta, Assignment* deltadelta) {
2320 if (operators_.empty())
return false;
2322 const int operator_index = operator_indices_[index_];
2323 if (!started_[operator_index]) {
2324 operators_[operator_index]->Start(start_assignment_);
2325 started_.
Set(operator_index);
2327 if (!operators_[operator_index]->HoldsDelta()) {
2330 if (operators_[operator_index]->MakeNextNeighbor(delta, deltadelta)) {
2332 ++num_neighbors_per_operator_[operator_index];
2337 if (index_ == operators_.size()) {
2340 }
while (index_ != 0);
2346 const std::vector<LocalSearchOperator*>& ops,
double memory_coefficient,
2347 double exploration_coefficient,
bool maximize) {
2348 return RevAlloc(
new MultiArmedBanditCompoundOperator(
2349 ops, memory_coefficient, exploration_coefficient, maximize));
2358 return MakeOperator(vars, std::vector<IntVar*>(), op,
2359 std::move(get_incoming_neighbors),
2360 std::move(get_outgoing_neighbors));
2364 const std::vector<IntVar*>& vars,
2370 return MakeTwoOpt(
this, vars, secondary_vars,
nullptr,
2371 std::move(get_incoming_neighbors),
2372 std::move(get_outgoing_neighbors));
2375 std::vector<LocalSearchOperator*> operators;
2376 for (
int i = 1;
i < 4; ++
i) {
2377 operators.push_back(
MakeRelocate(
this, vars, secondary_vars,
2385 return ConcatenateOperators(operators);
2389 this, vars, secondary_vars,
nullptr,
2390 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors));
2393 return MakeExchange(
this, vars, secondary_vars,
nullptr,
2394 std::move(get_incoming_neighbors),
2395 std::move(get_outgoing_neighbors));
2398 return MakeCross(
this, vars, secondary_vars,
nullptr,
2399 std::move(get_incoming_neighbors),
2400 std::move(get_outgoing_neighbors));
2403 return MakeActive(
this, vars, secondary_vars,
nullptr);
2406 return MakeInactive(
this, vars, secondary_vars,
nullptr);
2436 if (!secondary_vars.empty()) {
2437 LOG(FATAL) <<
"Operator " << op
2438 <<
" does not support secondary variables";
2440 return RevAlloc(
new IncrementValue(vars));
2443 if (!secondary_vars.empty()) {
2444 LOG(FATAL) <<
"Operator " << op
2445 <<
" does not support secondary variables";
2447 return RevAlloc(
new DecrementValue(vars));
2450 if (!secondary_vars.empty()) {
2451 LOG(FATAL) <<
"Operator " << op
2452 <<
" does not support secondary variables";
2454 return RevAlloc(
new SimpleLns(vars, 1));
2457 LOG(FATAL) <<
"Unknown operator " << op;
2465 return MakeOperator(vars, std::vector<IntVar*>(), std::move(evaluator), op);
2469 const std::vector<IntVar*>& vars,
2470 const std::vector<IntVar*>& secondary_vars,
2475 std::vector<LocalSearchOperator*> operators;
2483 return MakeTSPOpt(
this, vars, secondary_vars, std::move(evaluator),
2484 absl::GetFlag(FLAGS_cp_local_search_tsp_opt_size));
2487 return MakeTSPLns(
this, vars, secondary_vars, std::move(evaluator),
2488 absl::GetFlag(FLAGS_cp_local_search_tsp_lns_size));
2491 LOG(FATAL) <<
"Unknown operator " << op;
2500 std::string DebugString()
const override {
return "AcceptFilter"; }
2501 bool Accept(
const Assignment*,
const Assignment*, int64_t, int64_t)
override {
2504 void Synchronize(
const Assignment*,
const Assignment*)
override {}
2509 return RevAlloc(
new AcceptFilter());
2516 std::string DebugString()
const override {
return "RejectFilter"; }
2517 bool Accept(
const Assignment*,
const Assignment*, int64_t, int64_t)
override {
2520 void Synchronize(
const Assignment*,
const Assignment*)
override {}
2525 return RevAlloc(
new RejectFilter());
2534 VariableDomainFilter() {}
2535 ~VariableDomainFilter()
override {}
2536 bool Accept(
const Assignment* delta,
const Assignment* deltadelta,
2537 int64_t objective_min, int64_t objective_max)
override;
2538 void Synchronize(
const Assignment*,
const Assignment*)
override {}
2540 std::string DebugString()
const override {
return "VariableDomainFilter"; }
2543bool VariableDomainFilter::Accept(
const Assignment* delta,
const Assignment*,
2545 const Assignment::IntContainer& container = delta->IntVarContainer();
2546 const int size = container.Size();
2547 for (
int i = 0;
i < size; ++
i) {
2548 const IntVarElement& element = container.Element(i);
2549 if (element.Activated() && !element.Var()->Contains(element.Value())) {
2558 return RevAlloc(
new VariableDomainFilter());
2563const int IntVarLocalSearchFilter::kUnassigned = -1;
2566 const std::vector<IntVar*>& vars) {
2571 if (!vars.empty()) {
2572 for (
int i = 0; i < vars.size(); ++i) {
2573 const int index = vars[i]->index();
2574 if (index >= var_index_to_index_.size()) {
2575 var_index_to_index_.resize(index + 1, kUnassigned);
2577 var_index_to_index_[index] = i + vars_.size();
2579 vars_.insert(vars_.end(), vars.begin(), vars.end());
2580 values_.resize(vars_.size(), 0);
2581 var_synced_.resize(vars_.size(),
false);
2589 if (delta ==
nullptr || delta->
Empty()) {
2590 var_synced_.assign(var_synced_.size(),
false);
2601 const int size = container.
Size();
2602 for (
int i = 0; i < size; ++i) {
2605 if (var !=
nullptr) {
2606 if (i < vars_.size() && vars_[i] == var) {
2607 values_[i] = element.
Value();
2608 var_synced_[i] =
true;
2610 const int64_t kUnallocated = -1;
2611 int64_t index = kUnallocated;
2613 values_[index] = element.
Value();
2614 var_synced_[index] =
true;
2631template <
typename Filter>
2634 SumObjectiveFilter(
const std::vector<IntVar*>& vars, Filter filter)
2636 primary_vars_size_(vars.size()),
2637 synchronized_costs_(vars.size()),
2638 delta_costs_(vars.size()),
2639 filter_(
std::move(filter)),
2640 synchronized_sum_(
std::numeric_limits<int64_t>::min()),
2641 delta_sum_(
std::numeric_limits<int64_t>::min()),
2642 incremental_(false) {}
2643 ~SumObjectiveFilter()
override {}
2644 bool Accept(
const Assignment* delta,
const Assignment* deltadelta,
2645 int64_t objective_min, int64_t objective_max)
override {
2646 if (delta ==
nullptr)
return false;
2647 if (deltadelta->Empty()) {
2649 for (
int i = 0;
i < primary_vars_size_; ++
i) {
2650 delta_costs_[
i] = synchronized_costs_[
i];
2653 incremental_ =
false;
2654 delta_sum_ =
CapAdd(synchronized_sum_, CostOfChanges(delta,
false));
2657 delta_sum_ =
CapAdd(delta_sum_, CostOfChanges(deltadelta,
true));
2659 delta_sum_ =
CapAdd(synchronized_sum_, CostOfChanges(delta,
true));
2661 incremental_ =
true;
2663 return filter_(delta_sum_, objective_min, objective_max);
2667 virtual int64_t CostOfSynchronizedVariable(int64_t index) = 0;
2669 virtual int64_t CostOfChanges(
const Assignment* changes,
2670 bool incremental) = 0;
2671 bool IsIncremental()
const override {
return true; }
2673 std::string DebugString()
const override {
return "SumObjectiveFilter"; }
2675 int64_t GetSynchronizedObjectiveValue()
const override {
2676 return synchronized_sum_;
2678 int64_t GetAcceptedObjectiveValue()
const override {
return delta_sum_; }
2681 const int primary_vars_size_;
2682 std::vector<int64_t> synchronized_costs_;
2683 std::vector<int64_t> delta_costs_;
2685 int64_t synchronized_sum_;
2690 void OnSynchronize(
const Assignment*)
override {
2691 synchronized_sum_ = 0;
2692 for (
int i = 0;
i < primary_vars_size_; ++
i) {
2693 const int64_t cost = CostOfSynchronizedVariable(i);
2694 synchronized_costs_[
i] = cost;
2695 delta_costs_[
i] = cost;
2696 synchronized_sum_ =
CapAdd(synchronized_sum_, cost);
2698 delta_sum_ = synchronized_sum_;
2699 incremental_ =
false;
2703template <
typename Filter>
2704class BinaryObjectiveFilter :
public SumObjectiveFilter<Filter> {
2706 BinaryObjectiveFilter(
const std::vector<IntVar*>& vars,
2707 Solver::IndexEvaluator2 value_evaluator, Filter filter)
2708 : SumObjectiveFilter<Filter>(vars, std::move(filter)),
2709 value_evaluator_(std::move(value_evaluator)) {}
2710 ~BinaryObjectiveFilter()
override {}
2711 int64_t CostOfSynchronizedVariable(int64_t index)
override {
2712 return IntVarLocalSearchFilter::IsVarSynced(index)
2713 ? value_evaluator_(index, IntVarLocalSearchFilter::Value(index))
2716 int64_t CostOfChanges(
const Assignment* changes,
bool incremental)
override {
2717 int64_t total_cost = 0;
2718 const Assignment::IntContainer& container = changes->IntVarContainer();
2719 for (
const IntVarElement& new_element : container.elements()) {
2720 IntVar*
const var = new_element.
Var();
2722 if (this->FindIndex(var, &index)) {
2723 total_cost =
CapSub(total_cost, this->delta_costs_[index]);
2724 int64_t new_cost = 0LL;
2725 if (new_element.Activated()) {
2726 new_cost = value_evaluator_(index, new_element.Value());
2727 }
else if (var->Bound()) {
2728 new_cost = value_evaluator_(index, var->Min());
2730 total_cost =
CapAdd(total_cost, new_cost);
2732 this->delta_costs_[index] = new_cost;
2740 Solver::IndexEvaluator2 value_evaluator_;
2743template <
typename Filter>
2744class TernaryObjectiveFilter :
public SumObjectiveFilter<Filter> {
2746 TernaryObjectiveFilter(
const std::vector<IntVar*>& vars,
2747 const std::vector<IntVar*>& secondary_vars,
2748 Solver::IndexEvaluator3 value_evaluator, Filter filter)
2749 : SumObjectiveFilter<Filter>(vars, std::move(filter)),
2750 secondary_vars_offset_(vars.size()),
2751 secondary_values_(vars.size(), -1),
2752 value_evaluator_(std::move(value_evaluator)) {
2753 IntVarLocalSearchFilter::AddVars(secondary_vars);
2754 CHECK_GE(IntVarLocalSearchFilter::Size(), 0);
2756 ~TernaryObjectiveFilter()
override {}
2757 int64_t CostOfSynchronizedVariable(int64_t index)
override {
2758 DCHECK_LT(index, secondary_vars_offset_);
2759 return IntVarLocalSearchFilter::IsVarSynced(index)
2760 ? value_evaluator_(index, IntVarLocalSearchFilter::Value(index),
2761 IntVarLocalSearchFilter::Value(
2762 index + secondary_vars_offset_))
2765 int64_t CostOfChanges(
const Assignment* changes,
bool incremental)
override {
2766 int64_t total_cost = 0;
2767 const Assignment::IntContainer& container = changes->IntVarContainer();
2768 for (
const IntVarElement& new_element : container.elements()) {
2769 IntVar*
const var = new_element.Var();
2771 if (this->FindIndex(var, &index) && index < secondary_vars_offset_) {
2772 secondary_values_[index] = -1;
2778 const int max_secondary_index = 2 * secondary_vars_offset_;
2779 for (
const IntVarElement& new_element : container.elements()) {
2780 IntVar*
const var = new_element.Var();
2782 if (new_element.Activated() && this->FindIndex(var, &index) &&
2783 index >= secondary_vars_offset_ &&
2785 index < max_secondary_index) {
2786 secondary_values_[index - secondary_vars_offset_] = new_element.Value();
2789 for (
const IntVarElement& new_element : container.elements()) {
2790 IntVar*
const var = new_element.Var();
2792 if (this->FindIndex(var, &index) && index < secondary_vars_offset_) {
2793 total_cost =
CapSub(total_cost, this->delta_costs_[index]);
2794 int64_t new_cost = 0LL;
2795 if (new_element.Activated()) {
2796 new_cost = value_evaluator_(index, new_element.Value(),
2797 secondary_values_[index]);
2798 }
else if (var->Bound() &&
2799 IntVarLocalSearchFilter::Var(index + secondary_vars_offset_)
2801 new_cost = value_evaluator_(
2803 IntVarLocalSearchFilter::Var(index + secondary_vars_offset_)
2806 total_cost =
CapAdd(total_cost, new_cost);
2808 this->delta_costs_[index] = new_cost;
2816 int secondary_vars_offset_;
2817 std::vector<int64_t> secondary_values_;
2818 Solver::IndexEvaluator3 value_evaluator_;
2825 switch (filter_enum) {
2827 auto filter = [](int64_t value, int64_t, int64_t max_value) {
2828 return value <= max_value;
2830 return RevAlloc(
new BinaryObjectiveFilter<
decltype(filter)>(
2831 vars, std::move(values), std::move(filter)));
2834 auto filter = [](int64_t value, int64_t min_value, int64_t) {
2835 return value >= min_value;
2837 return RevAlloc(
new BinaryObjectiveFilter<
decltype(filter)>(
2838 vars, std::move(values), std::move(filter)));
2841 auto filter = [](int64_t value, int64_t min_value, int64_t max_value) {
2842 return min_value <= value && value <= max_value;
2844 return RevAlloc(
new BinaryObjectiveFilter<
decltype(filter)>(
2845 vars, std::move(values), std::move(filter)));
2848 LOG(ERROR) <<
"Unknown local search filter enum value";
2855 const std::vector<IntVar*>& vars,
2858 switch (filter_enum) {
2860 auto filter = [](int64_t value, int64_t, int64_t max_value) {
2861 return value <= max_value;
2863 return RevAlloc(
new TernaryObjectiveFilter<
decltype(filter)>(
2864 vars, secondary_vars, std::move(values), std::move(filter)));
2867 auto filter = [](int64_t value, int64_t min_value, int64_t) {
2868 return value >= min_value;
2870 return RevAlloc(
new TernaryObjectiveFilter<
decltype(filter)>(
2871 vars, secondary_vars, std::move(values), std::move(filter)));
2874 auto filter = [](int64_t value, int64_t min_value, int64_t max_value) {
2875 return min_value <= value && value <= max_value;
2877 return RevAlloc(
new TernaryObjectiveFilter<
decltype(filter)>(
2878 vars, secondary_vars, std::move(values), std::move(filter)));
2881 LOG(ERROR) <<
"Unknown local search filter enum value";
2888 DCHECK_GE(num_nodes, num_nodes_);
2889 DCHECK(!graph_was_built_);
2890 graph_was_built_ =
true;
2891 std::sort(arcs_.begin(), arcs_.end());
2892 arcs_of_node_.clear();
2894 for (
int a = 0; a < arcs_.size(); ++a) {
2895 const NodeId tail = arcs_[a].tail;
2896 if (tail != prev_tail) {
2898 arcs_of_node_.resize(tail.value() + 1, a);
2901 num_nodes_ = std::max(num_nodes_, num_nodes);
2902 arcs_of_node_.resize(num_nodes_ + 1, arcs_.size());
2903 DCHECK(!HasDirectedCycle()) <<
"Graph has a directed cycle";
2906bool SubDagComputer::HasDirectedCycle()
const {
2907 DCHECK(graph_was_built_);
2916 std::vector<DFSEvent> event_stack;
2918 for (
NodeId node(0); node.value() < num_nodes_; ++node) {
2919 if (node_was_visited[node])
continue;
2920 event_stack.push_back({node,
true});
2921 while (!event_stack.empty()) {
2922 const auto [node, to_open] = event_stack.back();
2923 event_stack.pop_back();
2924 if (node_was_visited[node])
continue;
2926 if (node_is_open[node])
return true;
2927 node_is_open[node] =
true;
2928 event_stack.push_back({node,
false});
2929 for (
int a = arcs_of_node_[node];
2930 a < arcs_of_node_[
NodeId(node.value() + 1)]; ++a) {
2931 const NodeId head = arcs_[a].head;
2932 if (node_was_visited[head])
continue;
2933 event_stack.push_back({head,
true});
2936 node_was_visited[node] =
true;
2937 node_is_open[node] =
false;
2944const std::vector<SubDagComputer::ArcId>&
2946 DCHECK_LT(node.value(), num_nodes_);
2947 DCHECK(graph_was_built_);
2948 if (indegree_of_node_.size() < num_nodes_) {
2949 indegree_of_node_.resize(num_nodes_, 0);
2952 nodes_to_visit_.clear();
2953 nodes_to_visit_.push_back(node);
2954 while (!nodes_to_visit_.empty()) {
2955 const NodeId node = nodes_to_visit_.back();
2956 nodes_to_visit_.pop_back();
2957 const NodeId next(node.value() + 1);
2958 for (
int a = arcs_of_node_[node]; a < arcs_of_node_[next]; ++a) {
2959 const NodeId head = arcs_[a].head;
2960 if (indegree_of_node_[head] == 0) {
2961 nodes_to_visit_.push_back(head);
2963 ++indegree_of_node_[head];
2967 sorted_arcs_.clear();
2968 nodes_to_visit_.push_back(node);
2969 while (!nodes_to_visit_.empty()) {
2970 const NodeId node = nodes_to_visit_.back();
2971 nodes_to_visit_.pop_back();
2972 const NodeId next(node.value() + 1);
2973 for (
int a = arcs_of_node_[node]; a < arcs_of_node_[next]; ++a) {
2974 const NodeId head = arcs_[a].head;
2975 --indegree_of_node_[head];
2976 if (indegree_of_node_[head] == 0) {
2977 nodes_to_visit_.push_back(head);
2979 sorted_arcs_.push_back(arcs_[a].arc_id);
2983 DCHECK(absl::c_all_of(indegree_of_node_, [](
int x) {
return x == 0; }));
2984 return sorted_arcs_;
2989 int64_t relaxed_max) {
2990 DCHECK(state_domains_are_all_nonempty_);
2991 DCHECK_LE(relaxed_min, relaxed_max);
2992 relaxed_domains_.push_back({relaxed_min, relaxed_max});
2993 current_domains_.push_back({relaxed_min, relaxed_max});
2994 domain_is_trailed_.push_back(
false);
3000 return {
this, domain_id};
3004 int64_t min, int64_t max) {
3006 return {
this, domain_id};
3014 DCHECK(state_domains_are_all_nonempty_);
3015 if (!state_has_relaxed_domains_) {
3016 trailed_num_committed_empty_domains_ = num_committed_empty_domains_;
3018 state_has_relaxed_domains_ =
true;
3019 if (!domain_is_trailed_[domain_id]) {
3020 domain_is_trailed_[domain_id] =
true;
3021 trailed_domains_.push_back({current_domains_[domain_id], domain_id});
3022 if (IntersectionIsEmpty(relaxed_domains_[domain_id],
3023 current_domains_[domain_id])) {
3024 DCHECK_GT(num_committed_empty_domains_, 0);
3025 --num_committed_empty_domains_;
3027 current_domains_[domain_id] = relaxed_domains_[domain_id];
3034 DCHECK(state_domains_are_all_nonempty_);
3035 return current_domains_[domain_id].min;
3039 DCHECK(state_domains_are_all_nonempty_);
3040 return current_domains_[domain_id].max;
3044 int64_t min_value) {
3045 DCHECK(state_domains_are_all_nonempty_);
3046 DCHECK(domain_is_trailed_[domain_id]);
3047 VariableDomain& domain = current_domains_[domain_id];
3048 if (domain.max < min_value) {
3049 state_domains_are_all_nonempty_ =
false;
3051 domain.min = std::max(domain.min, min_value);
3052 return state_domains_are_all_nonempty_;
3056 int64_t max_value) {
3057 DCHECK(state_domains_are_all_nonempty_);
3058 DCHECK(domain_is_trailed_[domain_id]);
3059 VariableDomain& domain = current_domains_[domain_id];
3060 if (domain.min > max_value) {
3061 state_domains_are_all_nonempty_ =
false;
3063 domain.max = std::min(domain.max, max_value);
3064 return state_domains_are_all_nonempty_;
3068 int64_t min, int64_t max) {
3069 DCHECK(state_domains_are_all_nonempty_);
3070 DCHECK(!domain_is_trailed_[domain_id]);
3071 const bool domain_was_empty = IntersectionIsEmpty(
3072 relaxed_domains_[domain_id], current_domains_[domain_id]);
3073 relaxed_domains_[domain_id] = {min, max};
3074 const bool domain_is_empty =
3075 IntersectionIsEmpty({min, max}, current_domains_[domain_id]);
3077 if (!domain_was_empty && domain_is_empty) {
3078 num_committed_empty_domains_++;
3079 }
else if (domain_was_empty && !domain_is_empty) {
3080 num_committed_empty_domains_--;
3090 state_has_relaxed_domains_ =
false;
3091 trailed_domains_.clear();
3092 domain_is_trailed_.assign(domain_is_trailed_.size(),
false);
3094 for (Constraint* constraint : trailed_constraints_) {
3095 constraint->Commit();
3097 trailed_constraints_.clear();
3102 for (
const auto& [domain,
id] : trailed_domains_) {
3103 DCHECK(domain_is_trailed_[
id]);
3104 current_domains_[id] = domain;
3106 trailed_domains_.clear();
3107 state_has_relaxed_domains_ =
false;
3108 domain_is_trailed_.assign(domain_is_trailed_.size(),
false);
3109 state_domains_are_all_nonempty_ =
true;
3110 num_committed_empty_domains_ = trailed_num_committed_empty_domains_;
3112 for (Constraint* constraint : trailed_constraints_) {
3113 constraint->Revert();
3115 trailed_constraints_.clear();
3119NodeId LocalSearchState::DependencyGraph::GetOrCreateNodeOfDomainId(
3121 if (domain_id.value() >= dag_node_of_domain_.size()) {
3122 dag_node_of_domain_.resize(domain_id.value() + 1,
NodeId(0));
3124 if (dag_node_of_domain_[domain_id] ==
NodeId(0)) {
3125 dag_node_of_domain_[domain_id] =
NodeId(num_dag_nodes_++);
3127 return dag_node_of_domain_[domain_id];
3130NodeId LocalSearchState::DependencyGraph::GetOrCreateNodeOfConstraintId(
3131 ConstraintId constraint_id) {
3132 if (constraint_id.value() >= dag_node_of_constraint_.size()) {
3133 dag_node_of_constraint_.resize(constraint_id.value() + 1,
NodeId(0));
3135 if (dag_node_of_constraint_[constraint_id] ==
NodeId(0)) {
3136 dag_node_of_constraint_[constraint_id] =
NodeId(num_dag_nodes_++);
3138 return dag_node_of_constraint_[constraint_id];
3141void LocalSearchState::DependencyGraph::AddDomainsConstraintDependencies(
3142 const std::vector<VariableDomainId>& domain_ids,
3143 ConstraintId constraint_id) {
3144 const NodeId cnode = GetOrCreateNodeOfConstraintId(constraint_id);
3145 for (
int i = 0;
i < domain_ids.size(); ++
i) {
3146 const NodeId dnode = GetOrCreateNodeOfDomainId(domain_ids[i]);
3147 dag_.AddArc(dnode, cnode);
3148 dependency_of_dag_arc_.push_back({.domain_id = domain_ids[
i],
3150 .constraint_id = constraint_id});
3154void LocalSearchState::DependencyGraph::AddConstraintDomainDependency(
3156 const NodeId cnode = GetOrCreateNodeOfConstraintId(constraint_id);
3157 const NodeId dnode = GetOrCreateNodeOfDomainId(domain_id);
3158 dag_.AddArc(cnode, dnode);
3159 dependency_of_dag_arc_.push_back({.domain_id = domain_id,
3161 .constraint_id = constraint_id});
3165const std::vector<LocalSearchState::DependencyGraph::Dependency>&
3166LocalSearchState::DependencyGraph::ComputeSortedDependencies(
3168 sorted_dependencies_.clear();
3169 const NodeId node = dag_node_of_domain_[domain_id];
3170 for (
const ArcId a : dag_.ComputeSortedSubDagArcs(node)) {
3171 if (dependency_of_dag_arc_[a].input_index == -1)
continue;
3172 sorted_dependencies_.push_back(dependency_of_dag_arc_[a]);
3174 return sorted_dependencies_;
3178 const std::vector<VariableDomainId>& input_domain_ids,
3179 const std::vector<int64_t>& input_weights, int64_t input_offset,
3181 DCHECK_EQ(input_domain_ids.size(), input_weights.size());
3183 const ConstraintId constraint_id(constraints_.size());
3184 dependency_graph_.AddDomainsConstraintDependencies(input_domain_ids,
3186 dependency_graph_.AddConstraintDomainDependency(constraint_id,
3189 auto constraint = std::make_unique<WeightedSum>(
3190 this, input_domain_ids, input_weights, input_offset, output_domain_id);
3191 constraints_.push_back(std::move(constraint));
3194void LocalSearchState::DependencyGraph::BuildDependencyDAG(
int num_domains) {
3195 dag_.BuildGraph(num_dag_nodes_);
3197 const int num_assigned_nodes = dag_node_of_domain_.size();
3198 DCHECK_GE(num_domains, num_assigned_nodes);
3199 num_domains = std::max(num_domains, num_assigned_nodes);
3200 dag_node_of_domain_.resize(num_domains,
NodeId(0));
3205 triggers_of_domain_.clear();
3206 const int num_domains = current_domains_.size();
3207 dependency_graph_.BuildDependencyDAG(num_domains);
3208 for (
int vid = 0; vid < num_domains; ++vid) {
3209 triggers_of_domain_.push_back(triggers_.size());
3210 for (
const auto& [domain_id, input_index, constraint_id] :
3212 triggers_.push_back({.constraint = constraints_[constraint_id].get(),
3213 .input_index = input_index});
3216 triggers_of_domain_.push_back(triggers_.size());
3219LocalSearchState::WeightedSum::WeightedSum(
3221 const std::vector<VariableDomainId>& input_domain_ids,
3222 const std::vector<int64_t>& input_weights, int64_t input_offset,
3224 : output_(output), state_(state) {
3227 invariants_.num_neg_inf = 0;
3228 invariants_.num_pos_inf = 0;
3229 invariants_.wsum_mins = input_offset;
3230 invariants_.wsum_maxs = input_offset;
3231 for (
int i = 0; i < input_domain_ids.size(); ++i) {
3233 const int64_t weight = input_weights[i];
3236 inputs_.push_back({.min = min,
3238 .committed_min = min,
3239 .committed_max = max,
3241 .domain = domain_id,
3242 .is_trailed =
false});
3246 ++invariants_.num_neg_inf;
3248 invariants_.wsum_mins =
3252 ++invariants_.num_pos_inf;
3254 invariants_.wsum_maxs =
3259 ++invariants_.num_pos_inf;
3261 invariants_.wsum_maxs =
3265 ++invariants_.num_neg_inf;
3267 invariants_.wsum_mins =
3272 committed_invariants_ = invariants_;
3275LocalSearchState::VariableDomain LocalSearchState::WeightedSum::Propagate(
3277 if (!constraint_is_trailed_) {
3278 constraint_is_trailed_ =
true;
3279 state_->TrailConstraint(
this);
3281 WeightedVariable&
input = inputs_[input_index];
3282 if (!
input.is_trailed) {
3283 input.is_trailed =
true;
3284 trailed_inputs_.push_back(&
input);
3286 const int64_t new_min = state_->VariableDomainMin(
input.domain);
3287 const int64_t new_max = state_->VariableDomainMax(
input.domain);
3288 const int64_t weight =
input.weight;
3290 if (
input.min != new_min) {
3293 --invariants_.num_neg_inf;
3295 invariants_.wsum_mins =
3300 ++invariants_.num_neg_inf;
3302 invariants_.wsum_mins =
3305 input.min = new_min;
3307 if (
input.max != new_max) {
3310 --invariants_.num_pos_inf;
3312 invariants_.wsum_maxs =
3317 ++invariants_.num_pos_inf;
3319 invariants_.wsum_maxs =
3322 input.max = new_max;
3325 if (
input.min != new_min) {
3328 --invariants_.num_pos_inf;
3330 invariants_.wsum_maxs =
3335 ++invariants_.num_pos_inf;
3337 invariants_.wsum_maxs =
3340 input.min = new_min;
3342 if (
input.max != new_max) {
3345 --invariants_.num_neg_inf;
3347 invariants_.wsum_mins =
3352 ++invariants_.num_neg_inf;
3354 invariants_.wsum_mins =
3357 input.max = new_max;
3360 return {invariants_.num_neg_inf == 0 ? invariants_.wsum_mins :
kint64min,
3361 invariants_.num_pos_inf == 0 ? invariants_.wsum_maxs :
kint64max};
3364void LocalSearchState::WeightedSum::Commit() {
3365 committed_invariants_ = invariants_;
3366 constraint_is_trailed_ =
false;
3367 for (WeightedVariable* wv : trailed_inputs_) wv->Commit();
3368 trailed_inputs_.clear();
3371void LocalSearchState::WeightedSum::Revert() {
3372 invariants_ = committed_invariants_;
3373 constraint_is_trailed_ =
false;
3374 for (WeightedVariable* wv : trailed_inputs_) wv->Revert();
3375 trailed_inputs_.clear();
3380 for (
int t = triggers_of_domain_[domain_id]; t < triggers_of_domain_[next_id];
3382 const auto& [constraint, input_index] = triggers_[t];
3383 constraint->Propagate(input_index);
3390 for (
int t = triggers_of_domain_[domain_id]; t < triggers_of_domain_[next_id];
3392 const auto& [constraint, input_index] = triggers_[t];
3393 const auto [output_min, output_max] = constraint->Propagate(input_index);
3411 std::string
DebugString()
const override {
return "LocalSearchProfiler"; }
3413 operator_stats_.clear();
3414 filter_stats_per_context_.clear();
3415 last_operator_ =
nullptr;
3420 last_operator_ =
nullptr;
3422 template <
typename Callback>
3425 if (db->seconds() == 0)
continue;
3426 callback(db->name(), db->seconds());
3430 template <
typename Callback>
3432 std::vector<const LocalSearchOperator*> operators;
3433 for (
const auto& stat : operator_stats_) {
3434 operators.push_back(stat.first);
3437 operators.begin(), operators.end(),
3439 return gtl::FindOrDie(operator_stats_, op1).neighbors >
3440 gtl::FindOrDie(operator_stats_, op2).neighbors;
3443 const OperatorStats& stats =
gtl::FindOrDie(operator_stats_, op);
3444 const std::string& label = op->DebugString();
3446 if (label.empty() &&
3447 dynamic_cast<const CompoundOperator*
>(op) !=
nullptr) {
3450 callback(label, stats.neighbors, stats.filtered_neighbors,
3451 stats.accepted_neighbors, stats.seconds,
3452 stats.make_next_neighbor_seconds, stats.accept_neighbor_seconds);
3456 template <
typename Callback>
3458 for (
const auto& [context, filter_stats] : filter_stats_per_context_) {
3459 std::vector<const LocalSearchFilter*> filters;
3460 for (
const auto& [filter, stats] : filter_stats) {
3461 filters.push_back(filter);
3464 filters.begin(), filters.end(),
3467 return gtl::FindOrDie(*filter_stats_ptr, filter1).calls >
3468 gtl::FindOrDie(*filter_stats_ptr, filter2).calls;
3472 callback(context, filter->DebugString(), stats.calls, stats.rejects,
3478 LocalSearchStatistics statistics_proto;
3480 [&statistics_proto](absl::string_view name,
double duration_seconds) {
3481 LocalSearchStatistics::FirstSolutionStatistics*
const
3482 first_solution_statistics =
3483 statistics_proto.add_first_solution_statistics();
3484 first_solution_statistics->set_strategy(name);
3485 first_solution_statistics->set_duration_seconds(duration_seconds);
3488 [&statistics_proto](
3489 absl::string_view name, int64_t num_neighbors,
3490 int64_t num_filtered_neighbors, int64_t num_accepted_neighbors,
3491 double duration_seconds,
double make_next_neighbor_duration_seconds,
3492 double accept_neighbor_duration_seconds) {
3493 LocalSearchStatistics::LocalSearchOperatorStatistics*
const
3494 local_search_operator_statistics =
3495 statistics_proto.add_local_search_operator_statistics();
3496 local_search_operator_statistics->set_local_search_operator(name);
3497 local_search_operator_statistics->set_num_neighbors(num_neighbors);
3498 local_search_operator_statistics->set_num_filtered_neighbors(
3499 num_filtered_neighbors);
3500 local_search_operator_statistics->set_num_accepted_neighbors(
3501 num_accepted_neighbors);
3502 local_search_operator_statistics->set_duration_seconds(
3504 local_search_operator_statistics
3505 ->set_make_next_neighbor_duration_seconds(
3506 make_next_neighbor_duration_seconds);
3507 local_search_operator_statistics
3508 ->set_accept_neighbor_duration_seconds(
3509 accept_neighbor_duration_seconds);
3512 absl::string_view context,
3513 absl::string_view name,
3514 int64_t num_calls, int64_t num_rejects,
3515 double duration_seconds) {
3516 LocalSearchStatistics::LocalSearchFilterStatistics*
const
3517 local_search_filter_statistics =
3518 statistics_proto.add_local_search_filter_statistics();
3519 local_search_filter_statistics->set_local_search_filter(name);
3520 local_search_filter_statistics->set_num_calls(num_calls);
3521 local_search_filter_statistics->set_num_rejects(num_rejects);
3522 local_search_filter_statistics->set_duration_seconds(duration_seconds);
3523 local_search_filter_statistics->set_num_rejects_per_second(
3524 num_rejects / duration_seconds);
3525 local_search_filter_statistics->set_context(context);
3527 statistics_proto.set_total_num_neighbors(
solver()->neighbors());
3528 statistics_proto.set_total_num_filtered_neighbors(
3529 solver()->filtered_neighbors());
3530 statistics_proto.set_total_num_accepted_neighbors(
3531 solver()->accepted_neighbors());
3532 return statistics_proto;
3535 std::string overview;
3536 size_t max_name_size = 0;
3538 [&max_name_size](absl::string_view name,
double) {
3539 max_name_size = std::max(max_name_size, name.length());
3541 if (max_name_size > 0) {
3542 absl::StrAppendFormat(&overview,
3543 "First solution statistics:\n%*s | Time (s)\n",
3546 [&overview, max_name_size](absl::string_view name,
3547 double duration_seconds) {
3548 absl::StrAppendFormat(&overview,
"%*s | %7.2g\n", max_name_size,
3549 name, duration_seconds);
3554 [&max_name_size](absl::string_view name, int64_t, int64_t, int64_t,
3555 double,
double,
double) {
3556 max_name_size = std::max(max_name_size, name.length());
3558 if (max_name_size > 0) {
3559 absl::StrAppendFormat(
3561 "Local search operator statistics:\n%*s | Neighbors | Filtered "
3562 "| Accepted | Time (s)\n",
3564 OperatorStats total_stats;
3566 [&overview, &total_stats, max_name_size](
3567 absl::string_view name, int64_t num_neighbors,
3568 int64_t num_filtered_neighbors, int64_t num_accepted_neighbors,
3569 double duration_seconds,
3574 absl::StrAppendFormat(
3575 &overview,
"%*s | %9ld | %8ld | %8ld | %7.2g\n", max_name_size,
3576 name, num_neighbors, num_filtered_neighbors,
3577 num_accepted_neighbors, duration_seconds);
3578 total_stats.neighbors += num_neighbors;
3579 total_stats.filtered_neighbors += num_filtered_neighbors;
3580 total_stats.accepted_neighbors += num_accepted_neighbors;
3581 total_stats.seconds += duration_seconds;
3583 absl::StrAppendFormat(
3584 &overview,
"%*s | %9ld | %8ld | %8ld | %7.2g\n", max_name_size,
3585 "Total", total_stats.neighbors, total_stats.filtered_neighbors,
3586 total_stats.accepted_neighbors, total_stats.seconds);
3590 [&max_name_size](absl::string_view, absl::string_view name, int64_t,
3592 max_name_size = std::max(max_name_size, name.length());
3594 if (max_name_size > 0) {
3595 std::optional<std::string> filter_context;
3596 FilterStats total_filter_stats;
3598 [&overview, &filter_context, &total_filter_stats, max_name_size](
3599 const std::string& context,
const std::string& name,
3600 int64_t num_calls, int64_t num_rejects,
double duration_seconds) {
3601 if (!filter_context.has_value() ||
3602 filter_context.value() != context) {
3603 if (filter_context.has_value()) {
3604 absl::StrAppendFormat(
3605 &overview,
"%*s | %9ld | %9ld | %7.2g | %7.2g\n",
3606 max_name_size,
"Total", total_filter_stats.calls,
3607 total_filter_stats.rejects, total_filter_stats.seconds,
3608 total_filter_stats.rejects / total_filter_stats.seconds);
3609 total_filter_stats = {};
3611 filter_context = context;
3612 absl::StrAppendFormat(
3614 "Local search filter statistics%s:\n%*s | Calls | "
3615 " Rejects | Time (s) | Rejects/s\n",
3616 context.empty() ?
"" :
" (" + context +
")", max_name_size,
3619 absl::StrAppendFormat(
3620 &overview,
"%*s | %9ld | %9ld | %7.2g | %7.2g\n",
3621 max_name_size, name, num_calls, num_rejects, duration_seconds,
3622 num_rejects / duration_seconds);
3623 total_filter_stats.calls += num_calls;
3624 total_filter_stats.rejects += num_rejects;
3625 total_filter_stats.seconds += duration_seconds;
3627 absl::StrAppendFormat(
3628 &overview,
"%*s | %9ld | %9ld | %7.2g | %7.2g\n", max_name_size,
3629 "Total", total_filter_stats.calls, total_filter_stats.rejects,
3630 total_filter_stats.seconds,
3631 total_filter_stats.rejects / total_filter_stats.seconds);
3638 if (last_operator_ != op->
Self()) {
3640 last_operator_ = op->
Self();
3642 make_next_neighbor_timer_.Start();
3648 if (!make_next_neighbor_timer_.IsRunning())
return;
3649 make_next_neighbor_timer_.Stop();
3650 operator_stats_[op->
Self()].make_next_neighbor_seconds +=
3651 make_next_neighbor_timer_.Get();
3652 if (neighbor_found) {
3653 operator_stats_[op->
Self()].neighbors++;
3658 bool neighbor_found)
override {
3659 if (neighbor_found) {
3660 operator_stats_[op->
Self()].filtered_neighbors++;
3664 accept_neighbor_timer_.Start();
3667 bool neighbor_found)
override {
3668 accept_neighbor_timer_.Stop();
3669 operator_stats_[op->
Self()].accept_neighbor_seconds +=
3670 accept_neighbor_timer_.Get();
3671 if (neighbor_found) {
3672 operator_stats_[op->
Self()].accepted_neighbors++;
3676 FilterStats& filter_stats =
3677 filter_stats_per_context_[
solver()->context()][filter];
3678 filter_stats.calls++;
3679 filter_timer_.Start();
3682 filter_timer_.Stop();
3683 auto& stats = filter_stats_per_context_[
solver()->context()][filter];
3684 stats.seconds += filter_timer_.Get();
3691 profiled_decision_builders_.push_back(profiled_db);
3698 if (last_operator_ !=
nullptr) {
3700 operator_stats_[last_operator_].seconds += timer_.Get();
3705 struct OperatorStats {
3706 int64_t neighbors = 0;
3707 int64_t filtered_neighbors = 0;
3708 int64_t accepted_neighbors = 0;
3710 double make_next_neighbor_seconds = 0;
3711 double accept_neighbor_seconds = 0;
3714 struct FilterStats {
3716 int64_t rejects = 0;
3720 WallTimer make_next_neighbor_timer_;
3721 WallTimer accept_neighbor_timer_;
3722 WallTimer filter_timer_;
3723 const LocalSearchOperator* last_operator_ =
nullptr;
3724 absl::flat_hash_map<const LocalSearchOperator*, OperatorStats>
3726 absl::flat_hash_map<
3727 std::string, absl::flat_hash_map<const LocalSearchFilter*, FilterStats>>
3728 filter_stats_per_context_;
3730 std::vector<ProfiledDecisionBuilder*> profiled_decision_builders_;
3738 local_search_profiler_->AddFirstSolutionProfiledDecisionBuilder(
3759 if (local_search_profiler_ !=
nullptr) {
3760 return local_search_profiler_->PrintOverview();
3766 if (local_search_profiler_ !=
nullptr) {
3767 return local_search_profiler_->ExportToLocalSearchStatistics();
3769 return LocalSearchStatistics();
3772void LocalSearchFilterManager::FindIncrementalEventEnd() {
3773 const int num_events = events_.size();
3774 incremental_events_end_ = num_events;
3775 int last_priority = -1;
3776 for (
int e = num_events - 1; e >= 0; --e) {
3777 const auto& [filter, event_type, priority] = events_[e];
3778 if (priority != last_priority) {
3779 incremental_events_end_ = e + 1;
3780 last_priority = priority;
3782 if (filter->IsIncremental())
break;
3787 std::vector<LocalSearchFilter*> filters)
3788 : synchronized_value_(
std::numeric_limits<int64_t>::min()),
3789 accepted_value_(
std::numeric_limits<int64_t>::min()) {
3790 events_.reserve(2 * filters.size());
3798 FindIncrementalEventEnd();
3802 std::vector<FilterEvent> filter_events)
3803 : events_(
std::move(filter_events)),
3804 synchronized_value_(
std::numeric_limits<int64_t>::min()),
3805 accepted_value_(
std::numeric_limits<int64_t>::min()) {
3806 std::sort(events_.begin(), events_.end(),
3808 return e1.priority < e2.priority;
3810 FindIncrementalEventEnd();
3816 for (
int e = last_event_called_; e >= 0; --e) {
3817 const auto [filter, event_type, _priority] = events_[e];
3820 last_event_called_ = -1;
3829 int64_t objective_min,
3830 int64_t objective_max) {
3832 accepted_value_ = 0;
3833 bool feasible =
true;
3834 bool reordered =
false;
3835 int events_end = events_.size();
3836 for (
int e = 0; e < events_end; ++e) {
3837 last_event_called_ = e;
3838 const auto [filter, event_type, priority] = events_[e];
3839 switch (event_type) {
3841 if (!feasible && !filter->IsIncremental())
continue;
3843 const bool accept = filter->Accept(
3844 delta, deltadelta,
CapSub(objective_min, accepted_value_),
3845 CapSub(objective_max, accepted_value_));
3847 if (monitor !=
nullptr) monitor->
EndFiltering(filter, !accept);
3850 CapAdd(accepted_value_, filter->GetAcceptedObjectiveValue());
3852 feasible = accepted_value_ <= objective_max;
3855 events_end = incremental_events_end_;
3860 int to_move = e - 1;
3861 if (to_move >= 0 && events_[to_move].filter == filter) --to_move;
3862 if (to_move >= 0 && events_[to_move].priority == priority) {
3863 std::rotate(events_.begin() + to_move,
3864 events_.begin() + to_move + 1,
3865 events_.begin() + e + 1);
3872 filter->Relax(delta, deltadelta);
3876 LOG(FATAL) <<
"Unknown filter event type.";
3887 const bool reset_to_assignment = delta ==
nullptr || delta->
Empty();
3889 for (
auto [filter, event_type, unused_priority] : events_) {
3890 switch (event_type) {
3895 if (reset_to_assignment) {
3897 filter->Relax(assignment,
nullptr);
3899 filter->Relax(delta,
nullptr);
3904 LOG(FATAL) <<
"Unknown filter event type.";
3909 synchronized_value_ = 0;
3911 switch (event_type) {
3913 filter->Synchronize(assignment, delta);
3914 synchronized_value_ =
CapAdd(synchronized_value_,
3915 filter->GetSynchronizedObjectiveValue());
3919 filter->Commit(assignment, delta);
3923 LOG(FATAL) <<
"Unknown filter event type.";
3940 std::string
DebugString()
const override {
return "FindOneNeighbor"; }
3944 int64_t objective_min, int64_t objective_max);
3945 void SynchronizeAll(
Solver* solver);
3948 IntVar*
const objective_;
3949 std::unique_ptr<Assignment> reference_assignment_;
3950 std::unique_ptr<Assignment> last_synchronized_assignment_;
3957 bool neighbor_found_;
3959 int64_t solutions_since_last_check_;
3960 int64_t check_period_;
3962 bool has_checked_assignment_ =
false;
3977 : assignment_(assignment),
3978 objective_(objective),
3979 reference_assignment_(new
Assignment(assignment_)),
3980 filter_assignment_delta_(assignment->solver()->MakeAssignment()),
3982 ls_operator_(ls_operator),
3983 sub_decision_builder_(sub_decision_builder),
3985 original_limit_(limit),
3986 neighbor_found_(false),
3987 filter_manager_(filter_manager),
3988 solutions_since_last_check_(0),
3990 assignment_->solver()->parameters().check_solution_period()),
3991 last_checked_assignment_(assignment) {
3992 CHECK(
nullptr != assignment);
3993 CHECK(
nullptr != ls_operator);
3995 Solver*
const solver = assignment_->solver();
3997 if (
nullptr == limit) {
4004 if (limit_->solutions() != 1) {
4005 VLOG(1) <<
"Disabling neighbor-check skipping outside of first accept.";
4012 VLOG(1) <<
"Disabling neighbor-check skipping for LNS.";
4016 if (!reference_assignment_->HasObjective()) {
4017 reference_assignment_->AddObjective(objective_);
4024 neighbor_found_ =
false;
4025 last_synchronized_assignment_.reset();
4029 CHECK(
nullptr != solver);
4031 if (original_limit_ !=
nullptr) {
4032 limit_->Copy(original_limit_);
4035 if (!last_checked_assignment_.HasObjective()) {
4036 last_checked_assignment_.AddObjective(assignment_->Objective());
4039 if (!neighbor_found_) {
4046 pool_->Initialize(assignment_);
4047 SynchronizeAll(solver);
4057 if (sub_decision_builder_) {
4058 restore = solver->
Compose(restore, sub_decision_builder_);
4063 if (!ls_operator_->HoldsDelta()) {
4067 deltadelta->
Clear();
4069 if (++counter >= absl::GetFlag(FLAGS_cp_local_search_sync_frequency) &&
4070 pool_->SyncNeeded(reference_assignment_.get())) {
4073 SynchronizeAll(solver);
4076 bool has_neighbor =
false;
4077 if (!limit_->Check()) {
4079 has_neighbor = ls_operator_->MakeNextNeighbor(delta, deltadelta);
4081 ls_operator_, has_neighbor, delta, deltadelta);
4084 if (has_neighbor && !solver->IsUncheckedSolutionLimitReached()) {
4085 solver->neighbors_ += 1;
4092 const bool mh_filter =
4093 AcceptDelta(solver->ParentSearch(), delta, deltadelta);
4094 int64_t objective_min = std::numeric_limits<int64_t>::min();
4095 int64_t objective_max = std::numeric_limits<int64_t>::max();
4097 objective_min = objective_->Min();
4098 objective_max = objective_->Max();
4101 objective_min = std::max(objective_min, delta->
ObjectiveMin());
4102 objective_max = std::min(objective_max, delta->
ObjectiveMax());
4104 const bool move_filter = FilterAccept(solver, delta, deltadelta,
4105 objective_min, objective_max);
4107 ls_operator_, mh_filter && move_filter);
4108 if (!mh_filter || !move_filter) {
4109 if (filter_manager_ !=
nullptr) filter_manager_->Revert();
4112 solver->filtered_neighbors_ += 1;
4117 if (!assignment_->HasObjective()) {
4118 assignment_->AddObjective(delta->
Objective());
4119 last_checked_assignment_.AddObjective(delta->
Objective());
4125 const bool check_solution = (solutions_since_last_check_ == 0) ||
4129 if (has_checked_assignment_) solutions_since_last_check_++;
4130 if (solutions_since_last_check_ >= check_period_) {
4131 solutions_since_last_check_ = 0;
4133 const bool accept = !check_solution || solver->
SolveAndCommit(restore);
4137 solver->accepted_neighbors_ += 1;
4138 if (check_solution) {
4140 ls_operator_->DebugString());
4141 assignment_->Store();
4142 last_checked_assignment_.CopyIntersection(assignment_);
4143 neighbor_found_ =
true;
4144 has_checked_assignment_ =
true;
4148 ls_operator_->DebugString());
4149 assignment_->CopyIntersection(assignment_copy);
4150 assignment_->SetObjectiveValue(
4151 filter_manager_ ? filter_manager_->GetAcceptedObjectiveValue()
4158 solver->IncrementUncheckedSolutionCounter();
4159 pool_->RegisterNewSolution(assignment_);
4160 SynchronizeAll(solver);
4163 neighbor_found_ =
true;
4165 if (filter_manager_ !=
nullptr) filter_manager_->Revert();
4166 if (check_period_ > 1 && has_checked_assignment_) {
4172 VLOG(1) <<
"Imperfect filtering detected, backtracking to last "
4173 "checked solution and checking all solutions.";
4175 solutions_since_last_check_ = 0;
4176 pool_->RegisterNewSolution(&last_checked_assignment_);
4177 SynchronizeAll(solver);
4178 assignment_->CopyIntersection(&last_checked_assignment_);
4184 last_synchronized_assignment_.reset();
4185 if (neighbor_found_) {
4190 if (last_checked_assignment_.ObjectiveValue() !=
4191 assignment_->ObjectiveValue()) {
4196 last_checked_assignment_.CopyIntersection(assignment_);
4197 has_checked_assignment_ =
true;
4204 pool_->RegisterNewSolution(assignment_);
4205 SynchronizeAll(solver);
4215 last_synchronized_assignment_.reset();
4222 int64_t objective_min,
4223 int64_t objective_max) {
4224 if (filter_manager_ ==
nullptr)
return true;
4226 return filter_manager_->
Accept(monitor, delta, deltadelta, objective_min,
4232template <
typename Container>
4233void AddDeltaElements(
const Container& old_container,
4234 const Container& new_container, Assignment* delta) {
4235 for (
const auto& new_element : new_container.elements()) {
4236 const auto var = new_element.Var();
4237 const auto old_element_ptr = old_container.ElementPtrOrNull(var);
4238 if (old_element_ptr ==
nullptr || *old_element_ptr != new_element) {
4239 delta->FastAdd(var)->Copy(new_element);
4244void MakeDelta(
const Assignment* old_assignment,
4246 DCHECK_NE(delta,
nullptr);
4248 AddDeltaElements(old_assignment->IntVarContainer(),
4249 new_assignment->IntVarContainer(), delta);
4250 AddDeltaElements(old_assignment->IntervalVarContainer(),
4251 new_assignment->IntervalVarContainer(), delta);
4252 AddDeltaElements(old_assignment->SequenceVarContainer(),
4253 new_assignment->SequenceVarContainer(), delta);
4257void FindOneNeighbor::SynchronizeAll(
Solver* solver) {
4258 Assignment*
const reference_assignment = reference_assignment_.get();
4259 pool_->GetNextSolution(reference_assignment);
4260 neighbor_found_ =
false;
4262 solver->GetLocalSearchMonitor()->BeginOperatorStart();
4263 ls_operator_->Start(reference_assignment);
4264 if (filter_manager_ !=
nullptr) {
4265 Assignment* delta =
nullptr;
4266 if (last_synchronized_assignment_ ==
nullptr) {
4267 last_synchronized_assignment_ =
4268 std::make_unique<Assignment>(reference_assignment);
4270 MakeDelta(last_synchronized_assignment_.get(), reference_assignment,
4271 filter_assignment_delta_);
4272 delta = filter_assignment_delta_;
4273 last_synchronized_assignment_->Copy(reference_assignment);
4275 filter_manager_->Synchronize(reference_assignment_.get(), delta);
4277 solver->GetLocalSearchMonitor()->EndOperatorStart();
4290 solution_pool_(pool),
4297 return "LocalSearchPhaseParameters";
4304 return sub_decision_builder_;
4310 IntVar*
const objective_;
4322 ls_operator, sub_decision_builder,
4330 ls_operator, sub_decision_builder,
4339 ls_operator, sub_decision_builder,
4340 limit, filter_manager);
4348 sub_decision_builder,
nullptr,
nullptr);
4356 sub_decision_builder, limit,
nullptr);
4365 sub_decision_builder, limit,
4379class NestedSolveDecision :
public Decision {
4382 enum StateType { DECISION_PENDING, DECISION_FAILED, DECISION_FOUND };
4384 NestedSolveDecision(DecisionBuilder* db,
bool restore,
4385 const std::vector<SearchMonitor*>& monitors);
4386 NestedSolveDecision(DecisionBuilder* db,
bool restore);
4387 ~NestedSolveDecision()
override {}
4388 void Apply(Solver* solver)
override;
4389 void Refute(Solver* solver)
override;
4390 std::string DebugString()
const override {
return "NestedSolveDecision"; }
4391 int state()
const {
return state_; }
4394 DecisionBuilder*
const db_;
4396 std::vector<SearchMonitor*> monitors_;
4400NestedSolveDecision::NestedSolveDecision(
4402 const std::vector<SearchMonitor*>& monitors)
4405 monitors_(monitors),
4406 state_(DECISION_PENDING) {
4407 CHECK(
nullptr != db);
4412 : db_(db), restore_(restore), state_(DECISION_PENDING) {
4413 CHECK(
nullptr != db);
4416void NestedSolveDecision::Apply(
Solver*
const solver) {
4417 CHECK(
nullptr != solver);
4419 if (solver->Solve(db_, monitors_)) {
4420 solver->SaveAndSetValue(&state_,
static_cast<int>(DECISION_FOUND));
4422 solver->SaveAndSetValue(&state_,
static_cast<int>(DECISION_FAILED));
4425 if (solver->SolveAndCommit(db_, monitors_)) {
4426 solver->SaveAndSetValue(&state_,
static_cast<int>(DECISION_FOUND));
4428 solver->SaveAndSetValue(&state_,
static_cast<int>(DECISION_FAILED));
4433void NestedSolveDecision::Refute(Solver*
const) {}
4476 void PushLocalSearchDecision();
4480 IntVar*
const objective_ =
nullptr;
4486 std::vector<NestedSolveDecision*> nested_decisions_;
4487 int nested_decision_index_;
4499 : assignment_(nullptr),
4500 objective_(objective),
4502 ls_operator_(ls_operator),
4503 first_solution_sub_decision_builder_(sub_decision_builder),
4504 sub_decision_builder_(sub_decision_builder),
4505 nested_decision_index_(0),
4507 filter_manager_(filter_manager),
4508 has_started_(false) {
4509 CHECK(
nullptr != assignment);
4510 CHECK(
nullptr != ls_operator);
4513 assignment_->
Copy(assignment);
4526 : assignment_(nullptr),
4527 objective_(objective),
4529 ls_operator_(ls_operator),
4530 first_solution_sub_decision_builder_(sub_decision_builder),
4531 sub_decision_builder_(sub_decision_builder),
4532 nested_decision_index_(0),
4534 filter_manager_(filter_manager),
4535 has_started_(false) {
4536 CHECK(
nullptr != first_solution);
4537 CHECK(
nullptr != ls_operator);
4538 CHECK(!vars.empty());
4539 Solver*
const solver = vars[0]->solver();
4541 assignment_->
Add(vars);
4547 const std::vector<IntVar*>& vars,
IntVar* objective,
4553 : assignment_(nullptr),
4554 objective_(objective),
4556 ls_operator_(ls_operator),
4557 first_solution_sub_decision_builder_(first_solution_sub_decision_builder),
4558 sub_decision_builder_(sub_decision_builder),
4559 nested_decision_index_(0),
4561 filter_manager_(filter_manager),
4562 has_started_(false) {
4563 CHECK(
nullptr != first_solution);
4564 CHECK(
nullptr != ls_operator);
4565 CHECK(!vars.empty());
4566 Solver*
const solver = vars[0]->solver();
4568 assignment_->
Add(vars);
4580 : assignment_(nullptr),
4581 objective_(objective),
4583 ls_operator_(ls_operator),
4584 first_solution_sub_decision_builder_(sub_decision_builder),
4585 sub_decision_builder_(sub_decision_builder),
4586 nested_decision_index_(0),
4588 filter_manager_(filter_manager),
4589 has_started_(false) {
4590 CHECK(
nullptr != first_solution);
4591 CHECK(
nullptr != ls_operator);
4592 CHECK(!vars.empty());
4593 Solver*
const solver = vars[0]->solver();
4595 assignment_->
Add(vars);
4604 DCHECK(assignment_ !=
nullptr);
4607 const std::vector<IntVarElement>& elements =
4608 assignment_->IntVarContainer().elements();
4609 if (!elements.empty()) {
4610 std::vector<IntVar*> vars;
4612 vars.push_back(elem.Var());
4617 const std::vector<IntervalVarElement>& interval_elements =
4618 assignment_->IntervalVarContainer().elements();
4619 if (!interval_elements.empty()) {
4620 std::vector<IntervalVar*> interval_vars;
4622 interval_vars.push_back(elem.Var());
4636 CHECK(
nullptr != solver);
4637 CHECK_LT(0, nested_decisions_.size());
4638 if (!has_started_) {
4639 nested_decision_index_ = 0;
4641 find_neighbors_db_->EnterSearch();
4642 ls_operator_->EnterSearch();
4643 }
else if (nested_decision_index_ < 0) {
4646 NestedSolveDecision* decision = nested_decisions_[nested_decision_index_];
4647 const int state = decision->state();
4649 case NestedSolveDecision::DECISION_FAILED: {
4650 const bool local_optimum_reached =
4652 if (local_optimum_reached) {
4656 ls_operator_->Reset();
4658 if (!local_optimum_reached || solver->IsUncheckedSolutionLimitReached()) {
4659 nested_decision_index_ = -1;
4664 case NestedSolveDecision::DECISION_PENDING: {
4667 const int32_t kLocalSearchBalancedTreeDepth = 32;
4669 if (depth < kLocalSearchBalancedTreeDepth) {
4672 if (depth > kLocalSearchBalancedTreeDepth) {
4677 case NestedSolveDecision::DECISION_FOUND: {
4679 if (nested_decision_index_ + 1 < nested_decisions_.size()) {
4680 ++nested_decision_index_;
4685 LOG(ERROR) <<
"Unknown local search state";
4693 CHECK(first_solution);
4694 Solver*
const solver = assignment_->solver();
4698 first_solution_sub_decision_builder_, store);
4699 std::vector<SearchMonitor*> monitor;
4700 monitor.push_back(limit_);
4701 nested_decisions_.push_back(solver->
RevAlloc(
4702 new NestedSolveDecision(first_solution_and_store,
false, monitor)));
4706 Solver*
const solver = assignment_->solver();
4707 find_neighbors_db_ = solver->
RevAlloc(
4709 sub_decision_builder_, limit_, filter_manager_));
4710 nested_decisions_.push_back(
4711 solver->
RevAlloc(
new NestedSolveDecision(find_neighbors_db_,
false)));
4721 reference_assignment_ = std::make_unique<Assignment>(assignment);
4725 reference_assignment_->CopyIntersection(assignment);
4734 std::string
DebugString()
const override {
return "DefaultSolutionPool"; }
4737 std::unique_ptr<Assignment> reference_assignment_;
4768 first_solution, first_solution_sub_decision_builder,
4774 const std::vector<SequenceVar*>& vars,
DecisionBuilder* first_solution,
4783template <
bool is_profile_active>
4784Assignment* Solver::RunUncheckedLocalSearchInternal(
4787 const std::vector<SearchMonitor*>& monitors,
RegularLimit* limit,
4788 absl::flat_hash_set<IntVar*>* touched) {
4789 DCHECK(initial_solution !=
nullptr);
4790 DCHECK(initial_solution->
Objective() !=
nullptr);
4791 DCHECK(filter_manager !=
nullptr);
4792 if (limit !=
nullptr) limit->
Init();
4796 current_solution->
Copy(initial_solution);
4801 const auto sync_with_solution =
4802 [
this, ls_monitor, ls_operator,
4804 filter_manager, current_solution](
Assignment* delta) {
4805 IncrementUncheckedSolutionCounter();
4806 if constexpr (is_profile_active) {
4809 ls_operator->Start(current_solution);
4810 filter_manager->Synchronize(current_solution, delta);
4811 if constexpr (is_profile_active) {
4815 sync_with_solution(
nullptr);
4817 if (!ls_operator->HoldsDelta()) {
4820 delta.ClearObjective();
4822 if (limit !=
nullptr && (limit->
CheckWithOffset(absl::ZeroDuration()) ||
4826 if constexpr (is_profile_active) {
4829 const bool has_neighbor =
4830 ls_operator->MakeNextNeighbor(&delta, &deltadelta);
4831 if constexpr (is_profile_active) {
4835 if (!has_neighbor) {
4838 if constexpr (is_profile_active) {
4842 const bool mh_accept = monitor->
AcceptDelta(&delta, &deltadelta);
4845 const bool filter_accept =
4846 filter_manager->Accept(ls_monitor, &delta, &deltadelta,
4847 delta.ObjectiveMin(), delta.ObjectiveMax());
4848 if constexpr (is_profile_active) {
4853 if (!filter_accept) {
4854 filter_manager->Revert();
4857 filtered_neighbors_ += 1;
4860 filter_manager->GetAcceptedObjectiveValue());
4861 DCHECK(delta.AreAllElementsBound());
4862 accepted_neighbors_ += 1;
4867 if (touched !=
nullptr) {
4868 for (
const auto& element : delta.IntVarContainer().elements()) {
4869 touched->insert(element.Var());
4873 sync_with_solution(&delta);
4875 if (parameters_.print_local_search_profile()) {
4877 if (!profile.empty()) LOG(INFO) << profile;
4885 const std::vector<SearchMonitor*>& monitors,
RegularLimit* limit,
4886 absl::flat_hash_set<IntVar*>* touched) {
4888 return RunUncheckedLocalSearchInternal<true>(initial_solution,
4889 filter_manager, ls_operator,
4890 monitors, limit, touched);
4892 return RunUncheckedLocalSearchInternal<false>(initial_solution,
4893 filter_manager, ls_operator,
4894 monitors, limit, touched);
const E & Element(const V *const var) const
const std::vector< E > & elements() const
bool HasObjective() const
void SetObjectiveValue(int64_t value)
IntVarElement * Add(IntVar *var)
std::string DebugString() const override
bool AreAllElementsBound() const
void Copy(const Assignment *assignment)
int64_t ObjectiveMin() const
AssignmentContainer< IntVar, IntVarElement > IntContainer
IntVar * Objective() const
int64_t ObjectiveMax() const
const IntContainer & IntVarContainer() const
void CopyIntersection(const Assignment *assignment)
void AddObjective(IntVar *const v)
BaseInactiveNodeToPathOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_base_nodes, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors=nullptr, NeighborAccessor get_outgoing_neighbors=nullptr)
~BaseInactiveNodeToPathOperator() override=default
int64_t GetInactiveNode() const
bool MakeOneNeighbor() override
void AppendToFragment(int index)
virtual void InitFragments()
BaseLns(const std::vector< IntVar * > &vars)
--— Base Large Neighborhood Search operator --—
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
virtual bool NextFragment()=0
virtual std::string DebugString() const
void ClearAll()
Sets all bits to 0.
void Set(IndexType i)
Sets the bit at position i to 1.
virtual int64_t ModifyValue(int64_t index, int64_t value)=0
bool MakeOneNeighbor() override
This method should not be overridden. Override ModifyValue() instead.
ChangeValue(const std::vector< IntVar * > &vars)
--— ChangeValue Operators --—
bool MakeNeighbor() override
std::string DebugString() const override
Cross(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)
~Cross() override=default
void GetNextSolution(Assignment *const assignment) override
std::string DebugString() const override
bool SyncNeeded(Assignment *const) override
~DefaultSolutionPool() override
void Initialize(Assignment *const assignment) override
void RegisterNewSolution(Assignment *const assignment) override
--— ExchangeAndMakeActiveOperator --—
bool MakeNeighbor() override
ExchangeAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
bool OnSamePathAsPreviousBase(int64_t base_index) override
std::string DebugString() const override
~ExchangeAndMakeActiveOperator() override
--— ExchangePathEndsAndMakeActiveOperator --—
ExchangePathStartEndsAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
int64_t GetBaseNodeRestartPosition(int base_index) override
std::string DebugString() const override
~ExchangePathStartEndsAndMakeActiveOperator() override=default
bool MakeNeighbor() override
bool MakeNeighbor() override
~Exchange() override=default
Exchange(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)
std::string DebugString() const override
--— ExtendedSwapActiveOperator --—
std::string DebugString() const override
ExtendedSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
bool MakeNeighbor() override
~ExtendedSwapActiveOperator() override=default
--— Finds a neighbor of the assignment passed --—
std::string DebugString() const override
-------— Decision Builder -------—
Decision * Next(Solver *solver) override
~FindOneNeighbor() override
FindOneNeighbor(Assignment *assignment, IntVar *objective, SolutionPool *pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, const RegularLimit *limit, LocalSearchFilterManager *filter_manager)
IntVarLocalSearchFilter(const std::vector< IntVar * > &vars)
bool FindIndex(IntVar *const var, int64_t *index) const
virtual void OnSynchronize(const Assignment *)
void SynchronizeOnAssignment(const Assignment *assignment)
void AddVars(const std::vector< IntVar * > &vars)
Add variables to "track" to the filter.
void Synchronize(const Assignment *assignment, const Assignment *delta) override
~IntVarLocalSearchFilter() override
void SetValue(int64_t index, int64_t value)
void RevertChanges(bool change_was_incremental)
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
--— Base operator class for operators manipulating IntVars --—
void Deactivate(int64_t index)
IntVar * Var(int64_t index) const
Returns the variable of given index.
int64_t Value(int64_t index) const
bool ApplyChanges(Assignment *delta, Assignment *deltadelta) const
IntVarLocalSearchOperator(const std::vector< IntVar * > &vars, bool keep_inverse_values=false)
virtual bool MakeOneNeighbor()
IntVar * Var() override
Creates a variable from the expression.
virtual bool Contains(int64_t v) const =0
std::string DebugString() const override
~LinKernighan() override=default
LinKernighan(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)
bool MakeNeighbor() override
LocalSearchFilterManager(std::vector< FilterEvent > filter_events)
void Revert()
Calls Revert() of filters, in reverse order of Relax events.
void Synchronize(const Assignment *assignment, const Assignment *delta)
Synchronizes all filters to assignment.
bool Accept(LocalSearchMonitor *monitor, const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max)
LocalSearchMonitor(Solver *solver)
-------— Local Search Monitor --------—
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0
virtual void BeginOperatorStart()=0
Local search operator events.
virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void EndOperatorStart()=0
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
virtual const LocalSearchOperator * Self() const
virtual bool HasFragments() const
-------— Local Search Phase Parameters -------—
SolutionPool * solution_pool() const
~LocalSearchPhaseParameters() override
LocalSearchFilterManager * filter_manager() const
IntVar * objective() const
LocalSearchPhaseParameters(IntVar *objective, SolutionPool *const pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, RegularLimit *const limit, LocalSearchFilterManager *filter_manager)
LocalSearchOperator * ls_operator() const
RegularLimit * limit() const
std::string DebugString() const override
DecisionBuilder * sub_decision_builder() const
--— LocalSearchProfiler --—
void BeginOperatorStart() override
Local search operator events.
void EndFiltering(const LocalSearchFilter *filter, bool reject) override
void BeginMakeNextNeighbor(const LocalSearchOperator *op) override
std::string DebugString() const override
LocalSearchProfiler(Solver *solver)
void BeginFiltering(const LocalSearchFilter *filter) override
LocalSearchStatistics ExportToLocalSearchStatistics() const
void ExitSearch() override
End of the search.
void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
void EndOperatorStart() override
void ParseLocalSearchOperatorStatistics(const Callback &callback) const
std::string PrintOverview() const
void ParseLocalSearchFilterStatistics(const Callback &callback) const
void AddFirstSolutionProfiledDecisionBuilder(ProfiledDecisionBuilder *profiled_db)
void BeginAcceptNeighbor(const LocalSearchOperator *) override
bool IsActive() const override
void Install() override
Install itself on the solver.
void BeginFilterNeighbor(const LocalSearchOperator *) override
void ParseFirstSolutionStatistics(const Callback &callback) const
void RestartSearch() override
Restart the search.
void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *, const Assignment *) override
void AddWeightedSumConstraint(const std::vector< VariableDomainId > &input_domain_ids, const std::vector< int64_t > &input_weights, int64_t input_offset, VariableDomainId output_domain_id)
Adds a constraint that output = input_offset + sum_i weight_i * input_i.
bool StateIsFeasible() const
int64_t VariableDomainMin(VariableDomainId domain_id) const
VariableDomainId AddVariableDomain(int64_t relaxed_min, int64_t relaxed_max)
Adds a variable domain to this state, returns a handler to the new domain.
bool TightenVariableDomainMin(VariableDomainId domain_id, int64_t value)
void ChangeRelaxedVariableDomain(VariableDomainId domain_id, int64_t min, int64_t max)
void PropagateRelax(VariableDomainId domain_id)
Propagation of all events.
static Variable DummyVariable()
Makes a variable with no state, this is meant as a placeholder.
Variable MakeVariable(VariableDomainId domain_id)
Variable MakeVariableWithRelaxedDomain(int64_t min, int64_t max)
bool TightenVariableDomainMax(VariableDomainId domain_id, int64_t value)
void CompileConstraints()
int64_t VariableDomainMax(VariableDomainId domain_id) const
bool PropagateTighten(VariableDomainId domain_id)
bool RelaxVariableDomain(VariableDomainId domain_id)
Relaxes the domain, returns false iff the domain was already relaxed.
void PushFirstSolutionDecision(DecisionBuilder *first_solution)
std::string DebugString() const override
-------— Decision Builder -------—
LocalSearch(Assignment *assignment, IntVar *objective, SolutionPool *pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, RegularLimit *limit, LocalSearchFilterManager *filter_manager)
void Accept(ModelVisitor *visitor) const override
Model Visitor support.
Decision * Next(Solver *solver) override
void PushLocalSearchDecision()
--— MakeActiveAndRelocate --—
bool MakeNeighbor() override
~MakeActiveAndRelocateOperator() override=default
std::string DebugString() const override
MakeActiveAndRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeActiveOperator --—
~MakeActiveOperator() override=default
bool MakeNeighbor() override
std::string DebugString() const override
MakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)
--— MakeChainInactiveOperator --—
bool OnSamePathAsPreviousBase(int64_t) override
MakeChainInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
std::string DebugString() const override
int64_t GetBaseNodeRestartPosition(int base_index) override
bool MakeNeighbor() override
~MakeChainInactiveOperator() override=default
--— MakeInactiveOperator --—
std::string DebugString() const override
MakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
bool MakeNeighbor() override
~MakeInactiveOperator() override=default
virtual void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments)
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
static const char kVariableGroupExtension[]
static const char kVarsArgument[]
virtual void EndVisitExtension(const std::string &type)
virtual void BeginVisitExtension(const std::string &type)
static const char kIntervalsArgument[]
const std::vector< int > & Neighbors(int index) const
virtual ~NearestNeighbors()=default
NearestNeighbors & operator=(const NearestNeighbors &)=delete
virtual std::string DebugString() const
NearestNeighbors(const NearestNeighbors &)=delete
This type is neither copyable nor movable.
NearestNeighbors(Solver::IndexEvaluator3 evaluator, const PathOperator< ignore_path_vars > &path_operator, int size)
void Initialize(absl::Span< const int > path)
--— Limit the number of neighborhoods explored --—
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
NeighborhoodLimit(LocalSearchOperator *const op, int64_t limit)
std::string DebugString() const override
void Start(const Assignment *assignment) override
bool HoldsDelta() const override
--— Path-based Large Neighborhood Search --—
bool HasFragments() const override
std::string DebugString() const override
PathLns(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments)
bool MakeNeighbor() override
~PathLns() override=default
bool HasNeighbors() const
int number_of_nexts() const
Number of next variables.
bool MakeChainInactive(int64_t before_chain, int64_t chain_end)
int64_t Prev(int64_t node) const
Returns the node before node in the current delta.
int PathClassFromStartNode(int64_t start_node) const
int64_t Path(int64_t node) const
bool MakeActive(int64_t node, int64_t destination)
Insert the inactive node after destination.
int64_t OldNext(int64_t node) const
bool SwapNodes(int64_t node1, int64_t node2)
Swaps the nodes node1 and node2.
void SetNext(int64_t from, int64_t to, int64_t path)
Sets 'to' to be the node after 'from' on the given path.
int CurrentNodePathStart(int64_t node) const
bool IsPathStart(int64_t node) const
Returns true if node is the first node on the path.
bool MoveChain(int64_t before_chain, int64_t chain_end, int64_t destination)
bool IsPathEnd(int64_t node) const
int64_t EndNode(int i) const
Returns the end node of the ith base node.
PathOperator(const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, IterationParameters iteration_parameters)
Builds an instance of PathOperator from next and path variables.
bool IsInactive(int64_t node) const
Returns true if node is inactive.
bool CheckChainValidity(int64_t before_chain, int64_t chain_end, int64_t exclude) const
bool ReverseChain(int64_t before_chain, int64_t after_chain, int64_t *chain_last)
virtual void SetNextBaseToIncrement(int64_t base_index)
Neighbor GetNeighborForBaseNode(int64_t base_index) const
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
int64_t StartNode(int i) const
Returns the start node of the ith base node.
int64_t BaseNode(int i) const
Returns the ith base node of the operator.
int CurrentNodePathEnd(int64_t node) const
bool IsUncheckedSolutionLimitReached() override
bool CheckWithOffset(absl::Duration offset) override
void Init() override
This method is called when the search limit is initialized.
RegularLimit * MakeIdenticalClone() const
-— RelocateAndMakeActiveOperator --—
std::string DebugString() const override
bool MakeNeighbor() override
RelocateAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
~RelocateAndMakeActiveOperator() override=default
--— RelocateAndMakeInactiveOperator --—
std::string DebugString() const override
RelocateAndMakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
~RelocateAndMakeInactiveOperator() override=default
bool MakeNeighbor() override
bool OnSamePathAsPreviousBase(int64_t) override
std::string DebugString() const override
~Relocate() override=default
bool MakeNeighbor() override
Relocate(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, absl::string_view name, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors, int64_t chain_length=1LL, bool single_path=false)
virtual void Install()
A search monitors adds itself on the active search.
virtual bool AtSolution()
virtual bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
For the time being, Solver is neither MT_SAFE nor MT_HOT.
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)
LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
LocalSearchFilter * MakeVariableDomainFilter()
ABSL_MUST_USE_RESULT RegularLimit * MakeSolutionsLimit(int64_t solutions)
LocalSearchPhaseParameters * MakeLocalSearchPhaseParameters(IntVar *objective, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder)
Local Search Phase Parameters.
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
Decision * balancing_decision() const
IntVarLocalSearchFilter * MakeSumObjectiveFilter(const std::vector< IntVar * > &vars, IndexEvaluator2 values, Solver::LocalSearchFilterBound filter_enum)
DecisionBuilder * MakeProfiledDecisionBuilderWrapper(DecisionBuilder *db)
Activates profiling on a decision builder.
bool UseFastLocalSearch() const
Returns true if fast local search is enabled.
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
Assignment * RunUncheckedLocalSearch(const Assignment *initial_solution, LocalSearchFilterManager *filter_manager, LocalSearchOperator *ls_operator, const std::vector< SearchMonitor * > &monitors, RegularLimit *limit, absl::flat_hash_set< IntVar * > *touched=nullptr)
std::function< int64_t(int64_t, int64_t, int64_t)> IndexEvaluator3
LocalSearchStatistics GetLocalSearchStatistics() const
Returns detailed local search statistics.
DecisionBuilder * Compose(DecisionBuilder *db1, DecisionBuilder *db2)
std::string LocalSearchProfile() const
LocalSearchOperator * RandomConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
LocalSearchFilter * MakeAcceptFilter()
Local Search Filters.
SolutionPool * MakeDefaultSolutionPool()
Solution Pool.
LocalSearchOperator * MakeNeighborhoodLimit(LocalSearchOperator *op, int64_t limit)
DecisionBuilder * MakeLocalSearchPhase(Assignment *assignment, LocalSearchPhaseParameters *parameters)
LocalSearchOperator * MakeOperator(const std::vector< IntVar * > &vars, LocalSearchOperators op, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
Local Search Operators.
@ LE
Move is accepted when the current objective value <= objective.Max.
@ GE
Move is accepted when the current objective value >= objective.Min.
std::function< int64_t(int64_t, int64_t)> IndexEvaluator2
LocalSearchFilter * MakeRejectFilter()
friend class SearchMonitor
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
LocalSearchOperator * MultiArmedBanditConcatenateOperators(const std::vector< LocalSearchOperator * > &ops, double memory_coefficient, double exploration_coefficient, bool maximize)
Assignment * MakeAssignment()
This method creates an empty assignment.
EvaluatorLocalSearchOperators
@ RELOCATE
Relocate neighborhood with length of 1 (see OROPT comment).
void SetSearchContext(Search *search, absl::string_view search_context)
ConstraintSolverParameters parameters() const
Stored Parameters.
Assignment * GetOrCreateLocalSearchState()
LocalSearchOperator * MakeRandomLnsOperator(const std::vector< IntVar * > &vars, int number_of_variables)
bool SolveAndCommit(DecisionBuilder *db, const std::vector< SearchMonitor * > &monitors)
const std::vector< ArcId > & ComputeSortedSubDagArcs(NodeId node)
void BuildGraph(int num_nodes)
--— SwapActiveChainOperator --—
bool MakeNeighbor() override
void ResetIncrementalism() override
~SwapActiveChainOperator() override=default
SwapActiveChainOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int max_chain_size)
bool OnSamePathAsPreviousBase(int64_t) override
std::string DebugString() const override
bool IsIncremental() const override
--— SwapActiveOperator --—
~SwapActiveOperator() override=default
SwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
bool MakeNeighbor() override
std::string DebugString() const override
~TSPLns() override=default
std::string DebugString() const override
bool MakeNeighbor() override
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
TSPLns(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)
--— TSP-based operators --—
TSPOpt(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)
~TSPOpt() override=default
std::string DebugString() const override
bool MakeNeighbor() override
bool IsIncremental() const override
void ResetIncrementalism() override
bool OnSamePathAsPreviousBase(int64_t) override
int64_t GetBaseNodeRestartPosition(int base_index) override
~TwoOpt() override=default
std::string DebugString() const override
TwoOpt(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)
bool MakeNeighbor() override
ABSL_FLAG(int, cp_local_search_sync_frequency, 16, "Frequency of checks for better solutions in the solution pool.")
ReverseView< Container > reversed_view(const Container &c)
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
For infeasible and unbounded see Not checked if options check_solutions_if_inf_or_unbounded and the If options first_solution_only is false
problem is infeasible or unbounded (default).
In SWIG mode, we don't want anything besides these top-level includes.
std::function< const std::vector< int > &(int, int)> NeighborAccessor
--— Path-based Operators --—
void DeleteLocalSearchProfiler(LocalSearchProfiler *monitor)
LocalSearchOperator * MakeExtendedSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExtendedSwapActive --—
int64_t CapAdd(int64_t x, int64_t y)
LocalSearchOperator * RelocateAndMakeInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— RelocateAndMakeInactive --—
LocalSearchOperator * MakeTSPOpt(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)
--— TSP-based operators --—
LocalSearchOperator * MakeCross(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— Cross --—
SubDagComputer::ArcId ArcId
LocalSearchOperator * MakeSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— SwapActive --—
LocalSearchOperator * ExchangeAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExchangeAndMakeActive --—
void AcceptNeighbor(Search *search)
Notifies the search that a neighbor has been accepted by local search.
LocalSearchOperator * MakeExchange(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— Exchange --—
void AcceptUncheckedNeighbor(Search *search)
int64_t CapSub(int64_t x, int64_t y)
LocalSearchOperator * MakeActiveAndRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeActiveAndRelocate --—
LocalSearchOperator * MakeTSPLns(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)
LocalSearchOperator * MakeRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr, int64_t chain_length=1LL, bool single_path=false, const std::string &name="Relocate")
--— Relocate --—
bool LocalOptimumReached(Search *search)
Returns true if a local optimum has been reached and cannot be improved.
LocalSearchOperator * RelocateAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
-— RelocateAndMakeActive --—
LocalSearchOperator * MakePathLns(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments)
--— Path-based Large Neighborhood Search --—
LocalSearchOperator * MakeInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeInactive --—
LocalSearchOperator * MakeTwoOpt(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— 2Opt --—
LocalSearchOperator * MakeChainInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeChainInactive --—
void InstallLocalSearchProfiler(LocalSearchProfiler *monitor)
int64_t CapProd(int64_t x, int64_t y)
LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)
LocalSearchOperator * ExchangePathStartEndsAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExchangePathEndsAndMakeActive --—
LocalSearchOperator * MakeSwapActiveChain(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int max_chain_size)
--— SwapActiveChain --—
LocalSearchOperator * MakeLinKernighan(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)
--— Lin-Kernighan --—
LocalSearchState::VariableDomainId VariableDomainId
LocalSearchOperator * MakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— MakeActive --—
bool AcceptDelta(Search *search, Assignment *delta, Assignment *deltadelta)
SubDagComputer::NodeId NodeId
static int input(yyscan_t yyscanner)
static const int64_t kint64max
static const int32_t kint32max
static const int64_t kint64min