24 #include "absl/container/flat_hash_map.h"
25 #include "absl/container/flat_hash_set.h"
26 #include "absl/memory/memory.h"
27 #include "absl/random/distributions.h"
28 #include "absl/random/random.h"
29 #include "absl/strings/str_cat.h"
43 "Frequency of checks for better solutions in the solution pool.");
46 "Size of TSPs solved in the TSPOpt operator.");
49 "Size of TSPs solved in the TSPLns operator.");
51 ABSL_FLAG(
bool, cp_use_empty_path_symmetry_breaker,
true,
52 "If true, equivalent empty paths are removed from the neighborhood "
66 Assignment* deltadelta);
78 <<
delta->DebugString() <<
"), deltadelta=("
79 << (deltadelta ? deltadelta->
DebugString() : std::string(
"nullptr"));
107 for (
int candidate : fragment_) {
121 fragment_.push_back(
index);
132 class SimpleLns :
public BaseLns {
134 SimpleLns(
const std::vector<IntVar*>& vars,
int number_of_variables)
135 :
BaseLns(vars), index_(0), number_of_variables_(number_of_variables) {
138 ~SimpleLns()
override {}
139 void InitFragments()
override { index_ = 0; }
140 bool NextFragment()
override;
141 std::string DebugString()
const override {
return "SimpleLns"; }
145 const int number_of_variables_;
148 bool SimpleLns::NextFragment() {
149 const int size = Size();
151 for (
int i = index_; i < index_ + number_of_variables_; ++i) {
152 AppendToFragment(i % size);
164 class RandomLns :
public BaseLns {
166 RandomLns(
const std::vector<IntVar*>& vars,
int number_of_variables,
168 : BaseLns(vars), rand_(seed), number_of_variables_(number_of_variables) {
170 CHECK_LE(number_of_variables_, Size());
172 ~RandomLns()
override {}
173 bool NextFragment()
override;
175 std::string DebugString()
const override {
return "RandomLns"; }
179 const int number_of_variables_;
182 bool RandomLns::NextFragment() {
184 for (
int i = 0; i < number_of_variables_; ++i) {
185 AppendToFragment(absl::Uniform<int>(rand_, 0, Size()));
192 const std::vector<IntVar*>& vars,
int number_of_variables) {
197 const std::vector<IntVar*>& vars,
int number_of_variables,
int32 seed) {
198 return RevAlloc(
new RandomLns(vars, number_of_variables, seed));
209 MoveTowardTargetLS(
const std::vector<IntVar*>& variables,
210 const std::vector<int64>& target_values)
212 target_(target_values),
216 variable_index_(Size() - 1) {
217 CHECK_EQ(target_values.size(), variables.size()) <<
"Illegal arguments.";
220 ~MoveTowardTargetLS()
override {}
222 std::string DebugString()
const override {
return "MoveTowardTargetLS"; }
226 bool MakeOneNeighbor()
override {
227 while (num_var_since_last_start_ < Size()) {
228 ++num_var_since_last_start_;
229 variable_index_ = (variable_index_ + 1) % Size();
230 const int64 target_value = target_.at(variable_index_);
231 const int64 current_value = OldValue(variable_index_);
232 if (current_value != target_value) {
233 SetValue(variable_index_, target_value);
241 void OnStart()
override {
255 num_var_since_last_start_ = 0;
259 const std::vector<int64> target_;
262 int64 variable_index_;
265 int64 num_var_since_last_start_;
271 typedef std::vector<IntVarElement> Elements;
274 std::vector<IntVar*> vars;
275 std::vector<int64> values;
278 for (
const auto& it : elements) {
279 vars.push_back(it.Var());
280 values.push_back(it.Value());
286 const std::vector<IntVar*>& variables,
287 const std::vector<int64>& target_values) {
288 return RevAlloc(
new MoveTowardTargetLS(variables, target_values));
299 const int size =
Size();
300 while (index_ < size) {
309 void ChangeValue::OnStart() { index_ = 0; }
314 class IncrementValue :
public ChangeValue {
316 explicit IncrementValue(
const std::vector<IntVar*>& vars)
317 : ChangeValue(vars) {}
318 ~IncrementValue()
override {}
321 std::string DebugString()
const override {
return "IncrementValue"; }
326 class DecrementValue :
public ChangeValue {
328 explicit DecrementValue(
const std::vector<IntVar*>& vars)
329 : ChangeValue(vars) {}
330 ~DecrementValue()
override {}
333 std::string DebugString()
const override {
return "DecrementValue"; }
340 const std::vector<IntVar*>& path_vars,
341 int number_of_base_nodes,
342 bool skip_locally_optimal_paths,
343 bool accept_path_end_base,
344 std::function<
int(
int64)> start_empty_path_class)
346 number_of_nexts_(next_vars.size()),
347 ignore_path_vars_(path_vars.empty()),
348 next_base_to_increment_(number_of_base_nodes),
349 base_nodes_(number_of_base_nodes),
350 base_alternatives_(number_of_base_nodes),
351 base_sibling_alternatives_(number_of_base_nodes),
352 end_nodes_(number_of_base_nodes),
353 base_paths_(number_of_base_nodes),
354 just_started_(false),
356 accept_path_end_base_(accept_path_end_base),
357 start_empty_path_class_(std::move(start_empty_path_class)),
358 skip_locally_optimal_paths_(skip_locally_optimal_paths),
359 optimal_paths_enabled_(false),
360 alternative_index_(next_vars.size(), -1) {
365 path_basis_.push_back(0);
366 for (
int i = 1; i < base_nodes_.size(); ++i) {
369 if ((path_basis_.size() > 2) ||
370 (!next_vars.empty() && !next_vars.back()
373 .skip_locally_optimal_paths())) {
374 skip_locally_optimal_paths_ =
false;
380 void PathOperator::OnStart() {
381 optimal_paths_enabled_ =
false;
382 InitializeBaseNodes();
383 InitializeAlternatives();
388 while (IncrementPosition()) {
413 if (destination == before_chain || destination == chain_end)
return false;
416 const int64 destination_path =
Path(destination);
417 const int64 after_chain =
Next(chain_end);
418 SetNext(chain_end,
Next(destination), destination_path);
420 int current = destination;
422 while (current != chain_end) {
428 SetNext(destination,
Next(before_chain), destination_path);
430 SetNext(before_chain, after_chain,
Path(before_chain));
439 if (current == after_chain) {
443 SetNext(current, after_chain, path);
444 while (current_next != after_chain) {
446 SetNext(current_next, current, path);
447 current = current_next;
450 SetNext(before_chain, current, path);
451 *chain_last = current;
459 int64 destination_path =
Path(destination);
460 SetNext(node,
Next(destination), destination_path);
461 SetNext(destination, node, destination_path);
468 const int64 kNoPath = -1;
471 const int64 after_chain =
Next(chain_end);
473 while (current != after_chain) {
475 SetNext(current, current, kNoPath);
478 SetNext(before_chain, after_chain,
Path(before_chain));
485 if (active == inactive)
return false;
490 bool PathOperator::IncrementPosition() {
491 const int base_node_size = base_nodes_.size();
493 if (!just_started_) {
494 const int number_of_paths = path_starts_.size();
500 int last_restarted = base_node_size;
501 for (
int i = base_node_size - 1; i >= 0; --i) {
505 const int sibling_alternative_index =
507 if (sibling_alternative_index >= 0) {
508 if (base_sibling_alternatives_[i] <
509 alternative_sets_[sibling_alternative_index].size() - 1) {
510 ++base_sibling_alternatives_[i];
513 base_sibling_alternatives_[i] = 0;
516 const int alternative_index = alternative_index_[base_nodes_[i]];
517 if (alternative_index >= 0) {
518 if (base_alternatives_[i] <
519 alternative_sets_[alternative_index].size() - 1) {
520 ++base_alternatives_[i];
523 base_alternatives_[i] = 0;
524 base_sibling_alternatives_[i] = 0;
527 base_alternatives_[i] = 0;
528 base_sibling_alternatives_[i] = 0;
529 base_nodes_[i] =
OldNext(base_nodes_[i]);
530 if (accept_path_end_base_ || !
IsPathEnd(base_nodes_[i]))
break;
532 base_alternatives_[i] = 0;
533 base_sibling_alternatives_[i] = 0;
547 for (
int i = last_restarted; i < base_node_size; ++i) {
548 base_alternatives_[i] = 0;
549 base_sibling_alternatives_[i] = 0;
552 if (last_restarted > 0) {
558 if (optimal_paths_enabled_ && skip_locally_optimal_paths_) {
559 if (path_basis_.size() > 1) {
560 for (
int i = 1; i < path_basis_.size(); ++i) {
570 std::vector<int> current_starts(base_node_size);
571 for (
int i = 0; i < base_node_size; ++i) {
576 optimal_paths_enabled_ =
true;
578 for (
int i = base_node_size - 1; i >= 0; --i) {
579 const int next_path_index = base_paths_[i] + 1;
580 if (next_path_index < number_of_paths) {
581 base_paths_[i] = next_path_index;
582 base_alternatives_[i] = 0;
583 base_sibling_alternatives_[i] = 0;
584 base_nodes_[i] = path_starts_[next_path_index];
590 base_alternatives_[i] = 0;
591 base_sibling_alternatives_[i] = 0;
592 base_nodes_[i] = path_starts_[0];
595 if (!skip_locally_optimal_paths_)
return CheckEnds();
598 if (path_basis_.size() > 1) {
599 for (
int j = 1; j < path_basis_.size(); ++j) {
601 path_basis_[j - 1])] +
615 if (!CheckEnds())
return false;
617 for (
int i = 0; i < base_node_size; ++i) {
623 if (stop)
return false;
626 just_started_ =
false;
632 void PathOperator::InitializePathStarts() {
640 has_prevs[
next] =
true;
645 if (optimal_paths_.empty() && skip_locally_optimal_paths_) {
657 if (skip_locally_optimal_paths_) {
677 std::vector<int64> new_path_starts;
678 const bool use_empty_path_symmetry_breaker =
679 absl::GetFlag(FLAGS_cp_use_empty_path_symmetry_breaker);
683 if (start_empty_path_class_ !=
nullptr) {
684 if (empty_found[start_empty_path_class_(i)])
continue;
685 empty_found[start_empty_path_class_(i)] =
true;
688 new_path_starts.push_back(i);
696 std::vector<int> node_paths(max_next + 1, -1);
697 for (
int i = 0; i < path_starts_.size(); ++i) {
698 int node = path_starts_[i];
700 node_paths[node] = i;
703 node_paths[node] = i;
705 for (
int j = 0; j < base_nodes_.size(); ++j) {
707 base_alternatives_[j] = 0;
708 base_sibling_alternatives_[j] = 0;
709 if (
IsInactive(base_nodes_[j]) || node_paths[base_nodes_[j]] == -1) {
712 base_nodes_[j] = path_starts_[base_paths_[j]];
714 base_paths_[j] = node_paths[base_nodes_[j]];
721 absl::flat_hash_set<int> found_bases;
722 for (
int i = 0; i < path_starts_.size(); ++i) {
723 int index = new_index;
725 while (
index < new_path_starts.size() &&
726 new_path_starts[
index] < path_starts_[i]) {
729 const bool found = (
index < new_path_starts.size() &&
730 new_path_starts[
index] == path_starts_[i]);
734 for (
int j = 0; j < base_nodes_.size(); ++j) {
736 found_bases.insert(j);
737 base_paths_[j] = new_index;
741 base_nodes_[j] = new_path_starts[new_index];
747 path_starts_.swap(new_path_starts);
750 void PathOperator::InitializeInactives() {
753 inactives_.push_back(
OldNext(i) == i);
757 void PathOperator::InitializeBaseNodes() {
759 InitializeInactives();
760 InitializePathStarts();
764 for (
int i = 0; i < base_nodes_.size(); ++i) {
766 base_nodes_[i] = path_starts_[0];
768 first_start_ =
false;
770 for (
int i = 0; i < base_nodes_.size(); ++i) {
772 int64 base_node = base_nodes_[i];
774 base_node = path_starts_[base_paths_[i]];
775 base_nodes_[i] = base_node;
777 end_nodes_[i] = base_node;
781 for (
int i = 1; i < base_nodes_.size(); ++i) {
783 !OnSamePath(base_nodes_[i - 1], base_nodes_[i])) {
784 const int64 base_node = base_nodes_[i - 1];
785 base_nodes_[i] = base_node;
786 end_nodes_[i] = base_node;
787 base_paths_[i] = base_paths_[i - 1];
790 for (
int i = 0; i < base_nodes_.size(); ++i) {
791 base_alternatives_[i] = 0;
792 base_sibling_alternatives_[i] = 0;
794 just_started_ =
true;
797 void PathOperator::InitializeAlternatives() {
798 active_in_alternative_set_.resize(alternative_sets_.size(), -1);
799 for (
int i = 0; i < alternative_sets_.size(); ++i) {
800 const int64 current_active = active_in_alternative_set_[i];
801 if (current_active >= 0 && !
IsInactive(current_active))
continue;
804 active_in_alternative_set_[i] =
index;
811 bool PathOperator::OnSamePath(
int64 node1,
int64 node2)
const {
834 int64 exclude)
const {
835 if (before_chain == chain_end || before_chain == exclude)
return false;
836 int64 current = before_chain;
838 while (current != chain_end) {
845 current =
Next(current);
847 if (current == exclude) {
867 const std::vector<IntVar*>& secondary_vars,
868 std::function<
int(
int64)> start_empty_path_class)
870 std::move(start_empty_path_class)),
889 void OnNodeInitialization()
override { last_ = -1; }
897 if (last_base_ !=
BaseNode(0) || last_ == -1) {
909 && last_ != chain_last) {
938 const std::vector<IntVar*>& secondary_vars,
const std::string&
name,
939 std::function<
int(
int64)> start_empty_path_class,
940 int64 chain_length = 1LL,
bool single_path =
false)
942 std::move(start_empty_path_class)),
943 chain_length_(chain_length),
944 single_path_(single_path),
949 const std::vector<IntVar*>& secondary_vars,
950 std::function<
int(
int64)> start_empty_path_class,
951 int64 chain_length = 1LL,
bool single_path =
false)
953 absl::StrCat(
"Relocate<", chain_length,
">"),
954 std::move(start_empty_path_class), chain_length, single_path) {
969 const int64 chain_length_;
970 const bool single_path_;
971 const std::string name_;
979 int64 chain_end = before_chain;
980 for (
int i = 0; i < chain_length_; ++i) {
981 if (
IsPathEnd(chain_end) || chain_end == destination) {
984 chain_end =
Next(chain_end);
987 MoveChain(before_chain, chain_end, destination);
1003 const std::vector<IntVar*>& secondary_vars,
1004 std::function<
int(
int64)> start_empty_path_class)
1006 std::move(start_empty_path_class)) {}
1020 const bool ok =
MoveChain(prev_node0, node0, prev_node1);
1039 const std::vector<IntVar*>& secondary_vars,
1040 std::function<
int(
int64)> start_empty_path_class)
1042 std::move(start_empty_path_class)) {}
1052 if (start1 == start0)
return false;
1054 if (node0 == start0)
return false;
1056 if (node1 == start1)
return false;
1076 const std::vector<IntVar*>& vars,
1077 const std::vector<IntVar*>& secondary_vars,
int number_of_base_nodes,
1078 std::function<
int(
int64)> start_empty_path_class)
1079 :
PathOperator(vars, secondary_vars, number_of_base_nodes, false, false,
1080 std::move(start_empty_path_class)),
1091 void OnNodeInitialization()
override;
1096 void BaseInactiveNodeToPathOperator::OnNodeInitialization() {
1097 for (
int i = 0; i <
Size(); ++i) {
1103 inactive_node_ =
Size();
1107 while (inactive_node_ <
Size()) {
1130 const std::vector<IntVar*>& secondary_vars,
1131 std::function<
int(
int64)> start_empty_path_class)
1133 std::move(start_empty_path_class)) {}
1137 std::string
DebugString()
const override {
return "MakeActiveOperator"; }
1156 const std::vector<IntVar*>& vars,
1157 const std::vector<IntVar*>& secondary_vars,
1158 std::function<
int(
int64)> start_empty_path_class)
1160 std::move(start_empty_path_class)) {}
1164 const int64 node =
Next(before_node_to_move);
1171 return "RelocateAndMakeActiveOpertor";
1184 const std::vector<IntVar*>& secondary_vars,
1185 std::function<
int(
int64)> start_empty_path_class)
1187 std::move(start_empty_path_class)) {}
1192 return "MakeActiveAndRelocateOperator";
1198 const int64 chain_end =
Next(before_chain);
1201 MoveChain(before_chain, chain_end, destination) &&
1216 const std::vector<IntVar*>& secondary_vars,
1217 std::function<
int(
int64)> start_empty_path_class)
1219 std::move(start_empty_path_class)) {}
1226 std::string
DebugString()
const override {
return "MakeInactiveOperator"; }
1240 const std::vector<IntVar*>& vars,
1241 const std::vector<IntVar*>& secondary_vars,
1242 std::function<
int(
int64)> start_empty_path_class)
1244 std::move(start_empty_path_class)) {}
1249 const int64 node_to_inactivate =
Next(destination);
1250 if (node_to_inactivate == before_to_move ||
IsPathEnd(node_to_inactivate) ||
1254 const int64 node =
Next(before_to_move);
1259 return "RelocateAndMakeInactiveOperator";
1275 const std::vector<IntVar*>& secondary_vars,
1276 std::function<
int(
int64)> start_empty_path_class)
1278 std::move(start_empty_path_class)) {}
1285 return "MakeChainInactiveOperator";
1312 const std::vector<IntVar*>& secondary_vars,
1313 std::function<
int(
int64)> start_empty_path_class)
1315 std::move(start_empty_path_class)) {}
1319 std::string
DebugString()
const override {
return "SwapActiveOperator"; }
1344 const std::vector<IntVar*>& secondary_vars,
1345 std::function<
int(
int64)> start_empty_path_class)
1347 std::move(start_empty_path_class)) {}
1352 return "ExtendedSwapActiveOperator";
1359 if (
Next(base0) == base1) {
1377 TSPOpt(
const std::vector<IntVar*>& vars,
1378 const std::vector<IntVar*>& secondary_vars,
1386 std::vector<std::vector<int64>> cost_;
1388 hamiltonian_path_solver_;
1390 const int chain_length_;
1394 const std::vector<IntVar*>& secondary_vars,
1396 :
PathOperator(vars, secondary_vars, 1, true, false, nullptr),
1397 hamiltonian_path_solver_(cost_),
1399 chain_length_(chain_length) {}
1402 std::vector<int64> nodes;
1404 for (
int i = 0; i < chain_length_ + 1; ++i) {
1405 nodes.push_back(chain_end);
1409 chain_end =
Next(chain_end);
1411 if (nodes.size() <= 3) {
1415 const int size = nodes.size() - 1;
1417 for (
int i = 0; i < size; ++i) {
1418 cost_[i].resize(size);
1419 cost_[i][0] = evaluator_(nodes[i], nodes[size], chain_path);
1420 for (
int j = 1; j < size; ++j) {
1421 cost_[i][j] = evaluator_(nodes[i], nodes[j], chain_path);
1425 std::vector<PathNodeIndex> path;
1428 for (
int i = 0; i < size - 1; ++i) {
1429 SetNext(nodes[path[i]], nodes[path[i + 1]], chain_path);
1431 SetNext(nodes[path[size - 1]], nodes[size], chain_path);
1445 TSPLns(
const std::vector<IntVar*>& vars,
1446 const std::vector<IntVar*>& secondary_vars,
1457 void OnNodeInitialization()
override {
1459 has_long_enough_paths_ =
Size() != 0;
1462 std::vector<std::vector<int64>> cost_;
1463 HamiltonianPathSolver<int64, std::vector<std::vector<int64>>>
1464 hamiltonian_path_solver_;
1466 const int tsp_size_;
1468 bool has_long_enough_paths_;
1472 const std::vector<IntVar*>& secondary_vars,
1474 :
PathOperator(vars, secondary_vars, 1, true, false, nullptr),
1475 hamiltonian_path_solver_(cost_),
1477 tsp_size_(tsp_size),
1479 has_long_enough_paths_(true) {
1481 cost_.resize(tsp_size_);
1482 for (
int i = 0; i < tsp_size_; ++i) {
1483 cost_[i].resize(tsp_size_);
1488 while (has_long_enough_paths_) {
1489 has_long_enough_paths_ =
false;
1500 std::vector<int64> nodes;
1502 nodes.push_back(node);
1504 if (nodes.size() <= tsp_size_) {
1507 has_long_enough_paths_ =
true;
1510 absl::flat_hash_set<int64> breaks_set;
1512 breaks_set.insert(base_node);
1513 CHECK(!nodes.empty());
1514 while (breaks_set.size() < tsp_size_) {
1515 breaks_set.insert(nodes[absl::Uniform<int>(rand_, 0, nodes.size())]);
1517 CHECK_EQ(breaks_set.size(), tsp_size_);
1522 std::vector<int> breaks;
1523 std::vector<int64> meta_node_costs;
1530 breaks.push_back(node);
1531 meta_node_costs.push_back(
cost);
1538 meta_node_costs[0] +=
cost;
1539 CHECK_EQ(breaks.size(), tsp_size_);
1541 CHECK_EQ(meta_node_costs.size(), tsp_size_);
1542 for (
int i = 0; i < tsp_size_; ++i) {
1544 CapAdd(meta_node_costs[i],
1545 evaluator_(breaks[i],
Next(breaks[tsp_size_ - 1]), node_path));
1546 for (
int j = 1; j < tsp_size_; ++j) {
1548 CapAdd(meta_node_costs[i],
1549 evaluator_(breaks[i],
Next(breaks[j - 1]), node_path));
1555 std::vector<PathNodeIndex> path;
1557 bool nochange =
true;
1558 for (
int i = 0; i < path.size() - 1; ++i) {
1567 CHECK_EQ(0, path[path.size() - 1]);
1568 for (
int i = 0; i < tsp_size_ - 1; ++i) {
1569 SetNext(breaks[path[i]],
OldNext(breaks[path[i + 1] - 1]), node_path);
1571 SetNext(breaks[path[tsp_size_ - 1]],
OldNext(breaks[tsp_size_ - 1]),
1592 virtual std::string
DebugString()
const {
return "NearestNeighbors"; }
1595 void ComputeNearest(
int row);
1597 std::vector<std::vector<int>> neighbors_;
1609 path_operator_(path_operator),
1611 initialized_(false) {}
1615 if (!initialized_) {
1616 initialized_ =
true;
1618 neighbors_.push_back(std::vector<int>());
1625 return neighbors_[
index];
1628 void NearestNeighbors::ComputeNearest(
int row) {
1630 const int path = path_operator_.
Path(
row);
1633 const int var_size =
var->Max() - var_min + 1;
1634 using ValuedIndex = std::pair<
int64 ,
int >;
1635 std::vector<ValuedIndex> neighbors(var_size);
1636 for (
int i = 0; i < var_size; ++i) {
1637 const int index = i + var_min;
1638 neighbors[i] = std::make_pair(evaluator_(
row,
index, path),
index);
1640 if (var_size > size_) {
1641 std::nth_element(neighbors.begin(), neighbors.begin() + size_ - 1,
1646 for (
int i = 0; i <
std::min(size_, var_size); ++i) {
1647 neighbors_[
row].push_back(neighbors[i].second);
1649 std::sort(neighbors_[
row].begin(), neighbors_[
row].end());
1655 const std::vector<IntVar*>& secondary_vars,
1663 void OnNodeInitialization()
override;
1665 static const int kNeighbors;
1671 absl::flat_hash_set<int64> marked_;
1680 const std::vector<IntVar*>& secondary_vars,
1682 :
PathOperator(vars, secondary_vars, 1, true, false, nullptr),
1684 neighbors_(evaluator, *this, kNeighbors),
1689 void LinKernighan::OnNodeInitialization() { neighbors_.
Initialize(); }
1700 marked_.insert(node);
1702 if (!InFromOut(node,
next, &out, &gain))
return false;
1703 marked_.insert(
next);
1704 marked_.insert(out);
1705 const int64 node1 = out;
1709 if (!InFromOut(node1, next1, &out, &gain))
return false;
1710 marked_.insert(next1);
1711 marked_.insert(out);
1716 const int64 in_cost = evaluator_(node, next_out, path);
1717 const int64 out_cost = evaluator_(out, next_out, path);
1718 if (
CapAdd(
CapSub(gain, in_cost), out_cost) > 0)
return true;
1725 while (InFromOut(node,
next, &out, &gain)) {
1726 marked_.insert(
next);
1727 marked_.insert(out);
1732 int64 in_cost = evaluator_(base, chain_last, path);
1733 int64 out_cost = evaluator_(chain_last, out, path);
1749 const int LinKernighan::kNeighbors = 5 + 1;
1752 const std::vector<int>& nexts = neighbors_.
Neighbors(in_j);
1755 int64 out_cost = evaluator_(in_i, in_j, path);
1756 const int64 current_gain =
CapAdd(*gain, out_cost);
1757 for (
int k = 0; k < nexts.size(); ++k) {
1760 int64 in_cost = evaluator_(in_j,
next, path);
1762 if (new_gain > 0 &&
next !=
Next(in_j) && marked_.count(in_j) == 0 &&
1763 marked_.count(
next) == 0) {
1764 if (best_gain < new_gain) {
1766 best_gain = new_gain;
1784 const std::vector<IntVar*>& secondary_vars,
int number_of_chunks,
1785 int chunk_size,
bool unactive_fragments)
1786 :
PathOperator(vars, secondary_vars, number_of_chunks, true, true,
1788 number_of_chunks_(number_of_chunks),
1789 chunk_size_(chunk_size),
1790 unactive_fragments_(unactive_fragments) {
1800 inline bool ChainsAreFullPaths()
const {
return chunk_size_ == 0; }
1801 void DeactivateChain(
int64 node);
1802 void DeactivateUnactives();
1804 const int number_of_chunks_;
1805 const int chunk_size_;
1806 const bool unactive_fragments_;
1810 if (ChainsAreFullPaths()) {
1814 for (
int i = 0; i < number_of_chunks_; ++i) {
1818 for (
int i = 0; i < number_of_chunks_; ++i) {
1821 DeactivateUnactives();
1825 void PathLns::DeactivateChain(
int64 node) {
1826 for (
int i = 0, current = node;
1827 (ChainsAreFullPaths() || i < chunk_size_) && !
IsPathEnd(current);
1828 ++i, current =
Next(current)) {
1836 void PathLns::DeactivateUnactives() {
1837 if (unactive_fragments_) {
1838 for (
int i = 0; i <
Size(); ++i) {
1854 : operator_(op), limit_(limit), next_neighborhood_calls_(0) {
1855 CHECK(op !=
nullptr);
1860 next_neighborhood_calls_ = 0;
1861 operator_->
Start(assignment);
1865 if (next_neighborhood_calls_ >= limit_) {
1868 ++next_neighborhood_calls_;
1874 std::string
DebugString()
const override {
return "NeighborhoodLimit"; }
1879 int64 next_neighborhood_calls_;
1892 CompoundOperator(std::vector<LocalSearchOperator*> operators,
1893 std::function<
int64(
int,
int)> evaluator);
1894 ~CompoundOperator()
override {}
1895 void Reset()
override;
1896 void Start(
const Assignment* assignment)
override;
1897 bool MakeNextNeighbor(Assignment*
delta, Assignment* deltadelta)
override;
1898 bool HasFragments()
const override {
return has_fragments_; }
1899 bool HoldsDelta()
const override {
return true; }
1901 std::string DebugString()
const override {
1902 return operators_.empty()
1904 : operators_[operator_indices_[index_]]->DebugString();
1906 const LocalSearchOperator* Self()
const override {
1907 return operators_.empty() ? this
1908 : operators_[operator_indices_[index_]]->Self();
1912 class OperatorComparator {
1914 OperatorComparator(std::function<
int64(
int,
int)> evaluator,
1915 int active_operator)
1916 :
evaluator_(std::move(evaluator)), active_operator_(active_operator) {}
1917 bool operator()(
int lhs,
int rhs)
const {
1918 const int64 lhs_value = Evaluate(lhs);
1919 const int64 rhs_value = Evaluate(rhs);
1920 return lhs_value < rhs_value || (lhs_value == rhs_value && lhs < rhs);
1924 int64 Evaluate(
int operator_index)
const {
1925 return evaluator_(active_operator_, operator_index);
1929 const int active_operator_;
1933 std::vector<LocalSearchOperator*> operators_;
1934 std::vector<int> operator_indices_;
1936 Bitset64<> started_;
1937 const Assignment* start_assignment_;
1938 bool has_fragments_;
1941 CompoundOperator::CompoundOperator(std::vector<LocalSearchOperator*> operators,
1942 std::function<
int64(
int,
int)> evaluator)
1944 operators_(std::move(operators)),
1946 started_(operators_.size()),
1947 start_assignment_(nullptr),
1948 has_fragments_(false) {
1949 operators_.erase(std::remove(operators_.begin(), operators_.end(),
nullptr),
1951 operator_indices_.resize(operators_.size());
1952 std::iota(operator_indices_.begin(), operator_indices_.end(), 0);
1953 for (LocalSearchOperator*
const op : operators_) {
1954 if (op->HasFragments()) {
1955 has_fragments_ =
true;
1961 void CompoundOperator::Reset() {
1962 for (LocalSearchOperator*
const op : operators_) {
1967 void CompoundOperator::Start(
const Assignment* assignment) {
1968 start_assignment_ = assignment;
1970 if (!operators_.empty()) {
1971 OperatorComparator comparator(
evaluator_, operator_indices_[index_]);
1972 std::sort(operator_indices_.begin(), operator_indices_.end(), comparator);
1977 bool CompoundOperator::MakeNextNeighbor(Assignment*
delta,
1978 Assignment* deltadelta) {
1979 if (!operators_.empty()) {
1983 const int64 operator_index = operator_indices_[index_];
1984 if (!started_[operator_index]) {
1985 operators_[operator_index]->Start(start_assignment_);
1986 started_.
Set(operator_index);
1988 if (!operators_[operator_index]->HoldsDelta()) {
1991 if (operators_[operator_index]->MakeNextNeighbor(
delta, deltadelta)) {
1996 if (index_ == operators_.size()) {
1999 }
while (index_ != 0);
2004 int64 CompoundOperatorNoRestart(
int size,
int active_index,
2005 int operator_index) {
2006 return (operator_index < active_index) ? size + operator_index - active_index
2007 : operator_index - active_index;
2010 int64 CompoundOperatorRestart(
int active_index,
int operator_index) {
2016 const std::vector<LocalSearchOperator*>& ops) {
2021 const std::vector<LocalSearchOperator*>& ops,
bool restart) {
2023 std::function<
int64(
int,
int)> eval = CompoundOperatorRestart;
2026 const int size = ops.size();
2028 return CompoundOperatorNoRestart(size, i, j);
2033 const std::vector<LocalSearchOperator*>& ops,
2034 std::function<
int64(
int,
int)> evaluator) {
2035 return RevAlloc(
new CompoundOperator(ops, std::move(evaluator)));
2041 explicit RandomCompoundOperator(std::vector<LocalSearchOperator*> operators);
2042 RandomCompoundOperator(std::vector<LocalSearchOperator*> operators,
2044 ~RandomCompoundOperator()
override {}
2045 void Reset()
override;
2046 void Start(
const Assignment* assignment)
override;
2047 bool MakeNextNeighbor(Assignment*
delta, Assignment* deltadelta)
override;
2048 bool HoldsDelta()
const override {
return true; }
2050 std::string DebugString()
const override {
return "RandomCompoundOperator"; }
2055 const std::vector<LocalSearchOperator*> operators_;
2056 bool has_fragments_;
2059 void RandomCompoundOperator::Start(
const Assignment* assignment) {
2060 for (LocalSearchOperator*
const op : operators_) {
2061 op->Start(assignment);
2065 RandomCompoundOperator::RandomCompoundOperator(
2066 std::vector<LocalSearchOperator*> operators)
2067 : RandomCompoundOperator(std::move(operators),
CpRandomSeed()) {}
2069 RandomCompoundOperator::RandomCompoundOperator(
2070 std::vector<LocalSearchOperator*> operators,
int32 seed)
2071 : rand_(seed), operators_(std::move(operators)), has_fragments_(false) {
2072 for (LocalSearchOperator*
const op : operators_) {
2073 if (op->HasFragments()) {
2074 has_fragments_ =
true;
2080 void RandomCompoundOperator::Reset() {
2081 for (LocalSearchOperator*
const op : operators_) {
2086 bool RandomCompoundOperator::MakeNextNeighbor(Assignment*
delta,
2087 Assignment* deltadelta) {
2088 const int size = operators_.size();
2089 std::vector<int> indices(size);
2090 std::iota(indices.begin(), indices.end(), 0);
2091 std::shuffle(indices.begin(), indices.end(), rand_);
2092 for (
int index : indices) {
2093 if (!operators_[
index]->HoldsDelta()) {
2096 if (operators_[
index]->MakeNextNeighbor(
delta, deltadelta)) {
2106 const std::vector<LocalSearchOperator*>& ops) {
2107 return RevAlloc(
new RandomCompoundOperator(ops));
2111 const std::vector<LocalSearchOperator*>& ops,
int32 seed) {
2112 return RevAlloc(
new RandomCompoundOperator(ops, seed));
2118 explicit MultiArmedBanditCompoundOperator(
2119 std::vector<LocalSearchOperator*> operators,
double memory_coefficient,
2120 double exploration_coefficient,
bool maximize);
2121 ~MultiArmedBanditCompoundOperator()
override {}
2122 void Reset()
override;
2123 void Start(
const Assignment* assignment)
override;
2124 bool MakeNextNeighbor(Assignment*
delta, Assignment* deltadelta)
override;
2125 bool HoldsDelta()
const override {
return true; }
2127 std::string DebugString()
const override {
2128 return operators_.empty()
2130 : operators_[operator_indices_[index_]]->DebugString();
2132 const LocalSearchOperator* Self()
const override {
2133 return operators_.empty() ? this
2134 : operators_[operator_indices_[index_]]->Self();
2138 double Score(
int index);
2140 std::vector<LocalSearchOperator*> operators_;
2141 Bitset64<> started_;
2142 const Assignment* start_assignment_;
2143 bool has_fragments_;
2144 std::vector<int> operator_indices_;
2145 int64 last_objective_;
2146 std::vector<double> avg_improvement_;
2148 std::vector<double> num_neighbors_per_operator_;
2154 const double memory_coefficient_;
2159 const double exploration_coefficient_;
2162 MultiArmedBanditCompoundOperator::MultiArmedBanditCompoundOperator(
2163 std::vector<LocalSearchOperator*> operators,
double memory_coefficient,
2164 double exploration_coefficient,
bool maximize)
2166 operators_(std::move(operators)),
2167 started_(operators_.size()),
2168 start_assignment_(nullptr),
2169 has_fragments_(false),
2173 memory_coefficient_(memory_coefficient),
2174 exploration_coefficient_(exploration_coefficient) {
2178 operators_.erase(std::remove(operators_.begin(), operators_.end(),
nullptr),
2180 operator_indices_.resize(operators_.size());
2181 std::iota(operator_indices_.begin(), operator_indices_.end(), 0);
2182 num_neighbors_per_operator_.resize(operators_.size(), 0);
2183 avg_improvement_.resize(operators_.size(), 0);
2184 for (LocalSearchOperator*
const op : operators_) {
2185 if (op->HasFragments()) {
2186 has_fragments_ =
true;
2192 void MultiArmedBanditCompoundOperator::Reset() {
2193 for (LocalSearchOperator*
const op : operators_) {
2198 double MultiArmedBanditCompoundOperator::Score(
int index) {
2199 return avg_improvement_[
index] +
2200 exploration_coefficient_ *
2201 sqrt(2 * log(1 + num_neighbors_) /
2202 (1 + num_neighbors_per_operator_[
index]));
2205 void MultiArmedBanditCompoundOperator::Start(
const Assignment* assignment) {
2206 start_assignment_ = assignment;
2208 if (operators_.empty())
return;
2210 const double objective = assignment->ObjectiveValue();
2212 if (objective == last_objective_)
return;
2215 last_objective_ = objective;
2219 const double improvement =
2220 maximize_ ? objective - last_objective_ : last_objective_ - objective;
2221 if (improvement < 0) {
2224 last_objective_ = objective;
2225 avg_improvement_[operator_indices_[index_]] +=
2226 memory_coefficient_ *
2227 (improvement - avg_improvement_[operator_indices_[index_]]);
2229 std::sort(operator_indices_.begin(), operator_indices_.end(),
2230 [
this](
int lhs,
int rhs) {
2231 const double lhs_score = Score(lhs);
2232 const double rhs_score = Score(rhs);
2233 return lhs_score > rhs_score ||
2234 (lhs_score == rhs_score && lhs < rhs);
2240 bool MultiArmedBanditCompoundOperator::MakeNextNeighbor(
2241 Assignment*
delta, Assignment* deltadelta) {
2242 if (operators_.empty())
return false;
2244 const int operator_index = operator_indices_[index_];
2245 if (!started_[operator_index]) {
2246 operators_[operator_index]->Start(start_assignment_);
2247 started_.
Set(operator_index);
2249 if (!operators_[operator_index]->HoldsDelta()) {
2252 if (operators_[operator_index]->MakeNextNeighbor(
delta, deltadelta)) {
2254 ++num_neighbors_per_operator_[operator_index];
2259 if (index_ == operators_.size()) {
2262 }
while (index_ != 0);
2268 const std::vector<LocalSearchOperator*>& ops,
double memory_coefficient,
2269 double exploration_coefficient,
bool maximize) {
2270 return RevAlloc(
new MultiArmedBanditCompoundOperator(
2271 ops, memory_coefficient, exploration_coefficient, maximize));
2278 Solver* solver,
const std::vector<IntVar*>& vars,
2279 const std::vector<IntVar*>& secondary_vars,
2280 std::function<
int(
int64)> start_empty_path_class) {
2282 new T(vars, secondary_vars, std::move(start_empty_path_class)));
2285 #define MAKE_LOCAL_SEARCH_OPERATOR(OperatorClass) \
2287 LocalSearchOperator* MakeLocalSearchOperator<OperatorClass>( \
2288 Solver * solver, const std::vector<IntVar*>& vars, \
2289 const std::vector<IntVar*>& secondary_vars, \
2290 std::function<int(int64)> start_empty_path_class) { \
2291 return solver->RevAlloc(new OperatorClass( \
2292 vars, secondary_vars, std::move(start_empty_path_class))); \
2308 #undef MAKE_LOCAL_SEARCH_OPERATOR
2316 const std::vector<IntVar*>& vars,
2317 const std::vector<IntVar*>& secondary_vars,
2326 std::vector<LocalSearchOperator*> operators;
2327 for (
int i = 1; i < 4; ++i) {
2329 new Relocate(vars, secondary_vars, absl::StrCat(
"OrOpt<", i,
">"),
2330 nullptr, i,
true)));
2336 result = MakeLocalSearchOperator<Relocate>(
this, vars, secondary_vars,
2341 result = MakeLocalSearchOperator<Exchange>(
this, vars, secondary_vars,
2347 MakeLocalSearchOperator<Cross>(
this, vars, secondary_vars,
nullptr);
2351 result = MakeLocalSearchOperator<MakeActiveOperator>(
2352 this, vars, secondary_vars,
nullptr);
2356 result = MakeLocalSearchOperator<MakeInactiveOperator>(
2357 this, vars, secondary_vars,
nullptr);
2361 result = MakeLocalSearchOperator<MakeChainInactiveOperator>(
2362 this, vars, secondary_vars,
nullptr);
2366 result = MakeLocalSearchOperator<SwapActiveOperator>(
2367 this, vars, secondary_vars,
nullptr);
2371 result = MakeLocalSearchOperator<ExtendedSwapActiveOperator>(
2372 this, vars, secondary_vars,
nullptr);
2391 if (secondary_vars.empty()) {
2392 result =
RevAlloc(
new IncrementValue(vars));
2395 <<
" does not support secondary variables";
2400 if (secondary_vars.empty()) {
2401 result =
RevAlloc(
new DecrementValue(vars));
2404 <<
" does not support secondary variables";
2409 if (secondary_vars.empty()) {
2410 result =
RevAlloc(
new SimpleLns(vars, 1));
2413 <<
" does not support secondary variables";
2418 LOG(
FATAL) <<
"Unknown operator " << op;
2426 return MakeOperator(vars, std::vector<IntVar*>(), std::move(evaluator), op);
2430 const std::vector<IntVar*>& vars,
2431 const std::vector<IntVar*>& secondary_vars,
2437 std::vector<LocalSearchOperator*> operators;
2439 new LinKernighan(vars, secondary_vars, evaluator,
false)));
2441 new LinKernighan(vars, secondary_vars, evaluator,
true)));
2447 new TSPOpt(vars, secondary_vars, evaluator,
2448 absl::GetFlag(FLAGS_cp_local_search_tsp_opt_size)));
2453 new TSPLns(vars, secondary_vars, evaluator,
2454 absl::GetFlag(FLAGS_cp_local_search_tsp_lns_size)));
2458 LOG(
FATAL) <<
"Unknown operator " << op;
2466 class SumOperation {
2468 SumOperation() : value_(0) {}
2469 void Init() { value_ = 0; }
2470 void Update(
int64 update) { value_ =
CapAdd(value_, update); }
2471 void Remove(
int64 remove) { value_ =
CapSub(value_, remove); }
2473 void set_value(
int64 new_value) { value_ = new_value; }
2479 class ProductOperation {
2481 ProductOperation() : value_(1) {}
2482 void Init() { value_ = 1; }
2483 void Update(
int64 update) { value_ *= update; }
2484 void Remove(
int64 remove) {
2490 void set_value(
int64 new_value) { value_ = new_value; }
2496 class MinOperation {
2498 void Init() { values_set_.clear(); }
2499 void Update(
int64 update) { values_set_.insert(update); }
2500 void Remove(
int64 remove) { values_set_.erase(remove); }
2502 return (!values_set_.empty()) ? *values_set_.begin() : 0;
2504 void set_value(
int64 new_value) {}
2507 std::set<int64> values_set_;
2510 class MaxOperation {
2512 void Init() { values_set_.clear(); }
2513 void Update(
int64 update) { values_set_.insert(update); }
2514 void Remove(
int64 remove) { values_set_.erase(remove); }
2516 return (!values_set_.empty()) ? *values_set_.rbegin() : 0;
2518 void set_value(
int64 new_value) {}
2521 std::set<int64> values_set_;
2525 class AcceptFilter :
public LocalSearchFilter {
2527 std::string DebugString()
const override {
return "AcceptFilter"; }
2528 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
2532 void Synchronize(
const Assignment* assignment,
2533 const Assignment*
delta)
override {}
2538 return RevAlloc(
new AcceptFilter());
2545 std::string DebugString()
const override {
return "RejectFilter"; }
2546 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
2550 void Synchronize(
const Assignment* assignment,
2551 const Assignment*
delta)
override {}
2556 return RevAlloc(
new RejectFilter());
2560 std::vector<int> path_end)
2561 : num_nodes_(num_nodes),
2562 num_paths_(path_start.size()),
2563 num_nodes_threshold_(std::
max(16, 4 * num_nodes_))
2565 DCHECK_EQ(path_start.size(), num_paths_);
2567 for (
int p = 0; p < num_paths_; ++p) {
2568 path_start_end_.push_back({path_start[p], path_end[p]});
2571 committed_index_.assign(num_nodes_, -1);
2572 committed_nodes_.assign(2 * num_paths_, {-1, -1});
2573 chains_.assign(num_paths_ + 1, {-1, -1});
2574 paths_.assign(num_paths_, {-1, -1});
2575 for (
int path = 0; path < num_paths_; ++path) {
2576 const int index = 2 * path;
2577 const PathStartEnd start_end = path_start_end_[path];
2578 committed_index_[start_end.start] =
index;
2579 committed_index_[start_end.end] =
index + 1;
2581 committed_nodes_[
index] = {start_end.start, path};
2582 committed_nodes_[
index + 1] = {start_end.end, path};
2585 paths_[path] = {path, path + 1};
2587 chains_[num_paths_] = {0, 0};
2589 for (
int node = 0; node < num_nodes_; ++node) {
2590 if (committed_index_[node] != -1)
continue;
2591 committed_index_[node] = committed_nodes_.size();
2592 committed_nodes_.push_back({node, -1});
2594 path_has_changed_.assign(num_paths_,
false);
2598 const PathBounds
bounds = paths_[path];
2600 chains_.data() +
bounds.end_index,
2601 committed_nodes_.data());
2605 const PathBounds
bounds = paths_[path];
2607 chains_.data() +
bounds.end_index,
2608 committed_nodes_.data());
2611 void PathState::MakeChainsFromChangedPathsAndArcsWithSelectionAlgorithm() {
2612 int num_visited_changed_arcs = 0;
2613 const int num_changed_arcs = tail_head_indices_.size();
2614 const int num_committed_nodes = committed_nodes_.size();
2616 for (
const int path : changed_paths_) {
2617 const int old_chain_size = chains_.size();
2618 const ChainBounds
bounds = chains_[paths_[path].begin_index];
2619 const int start_index =
bounds.begin_index;
2620 const int end_index =
bounds.end_index - 1;
2621 int current_index = start_index;
2625 int selected_arc = -1;
2626 int selected_tail_index = num_committed_nodes;
2627 for (
int i = num_visited_changed_arcs; i < num_changed_arcs; ++i) {
2628 const int tail_index = tail_head_indices_[i].tail_index;
2629 if (current_index <= tail_index && tail_index < selected_tail_index) {
2631 selected_tail_index = tail_index;
2639 if (start_index <= current_index && current_index <= end_index &&
2640 end_index < selected_tail_index) {
2641 chains_.emplace_back(current_index, end_index + 1);
2644 chains_.emplace_back(current_index, selected_tail_index + 1);
2645 current_index = tail_head_indices_[selected_arc].head_index;
2646 std::swap(tail_head_indices_[num_visited_changed_arcs],
2647 tail_head_indices_[selected_arc]);
2648 ++num_visited_changed_arcs;
2651 const int new_chain_size = chains_.size();
2652 paths_[path] = {old_chain_size, new_chain_size};
2654 chains_.emplace_back(0, 0);
2657 void PathState::MakeChainsFromChangedPathsAndArcsWithGenericAlgorithm() {
2673 for (
const int path : changed_paths_) {
2674 const PathStartEnd start_end = path_start_end_[path];
2675 tail_head_indices_.push_back(
2676 {committed_index_[start_end.end], committed_index_[start_end.start]});
2681 const int num_arc_indices = tail_head_indices_.size();
2682 arcs_by_tail_index_.resize(num_arc_indices);
2683 arcs_by_head_index_.resize(num_arc_indices);
2684 for (
int i = 0; i < num_arc_indices; ++i) {
2685 arcs_by_tail_index_[i] = {tail_head_indices_[i].tail_index, i};
2686 arcs_by_head_index_[i] = {tail_head_indices_[i].head_index, i};
2688 std::sort(arcs_by_tail_index_.begin(), arcs_by_tail_index_.end());
2689 std::sort(arcs_by_head_index_.begin(), arcs_by_head_index_.end());
2691 next_arc_.resize(num_arc_indices);
2692 for (
int i = 0; i < num_arc_indices; ++i) {
2693 next_arc_[arcs_by_head_index_[i].arc] = arcs_by_tail_index_[i].arc;
2699 const int first_fake_arc = num_arc_indices - changed_paths_.size();
2700 for (
int fake_arc = first_fake_arc; fake_arc < num_arc_indices; ++fake_arc) {
2701 const int new_path_begin = chains_.size();
2702 int32 arc = fake_arc;
2704 const int chain_begin = tail_head_indices_[arc].head_index;
2705 arc = next_arc_[arc];
2706 const int chain_end = tail_head_indices_[arc].tail_index + 1;
2707 chains_.emplace_back(chain_begin, chain_end);
2708 }
while (arc != fake_arc);
2709 const int path = changed_paths_[fake_arc - first_fake_arc];
2710 const int new_path_end = chains_.size();
2711 paths_[path] = {new_path_begin, new_path_end};
2713 chains_.emplace_back(0, 0);
2717 if (is_invalid_)
return;
2721 DCHECK_EQ(chains_.size(), num_paths_ + 1);
2722 DCHECK(changed_paths_.empty());
2723 tail_head_indices_.clear();
2724 int num_changed_arcs = 0;
2725 for (
const auto& arc : changed_arcs_) {
2727 std::tie(node,
next) = arc;
2728 const int node_index = committed_index_[node];
2729 const int next_index = committed_index_[
next];
2730 const int node_path = committed_nodes_[node_index].path;
2732 (next_index != node_index + 1 || node_path == -1)) {
2733 tail_head_indices_.push_back({node_index, next_index});
2734 changed_arcs_[num_changed_arcs++] = {node,
next};
2735 if (node_path != -1 && !path_has_changed_[node_path]) {
2736 path_has_changed_[node_path] =
true;
2737 changed_paths_.push_back(node_path);
2739 }
else if (node ==
next && node_path != -1) {
2740 changed_arcs_[num_changed_arcs++] = {node, node};
2743 changed_arcs_.resize(num_changed_arcs);
2745 if (tail_head_indices_.size() + changed_paths_.size() <= 8) {
2746 MakeChainsFromChangedPathsAndArcsWithSelectionAlgorithm();
2748 MakeChainsFromChangedPathsAndArcsWithGenericAlgorithm();
2754 if (committed_nodes_.size() < num_nodes_threshold_) {
2755 IncrementalCommit();
2762 is_invalid_ =
false;
2763 chains_.resize(num_paths_ + 1);
2764 for (
const int path : changed_paths_) {
2765 paths_[path] = {path, path + 1};
2766 path_has_changed_[path] =
false;
2768 changed_paths_.clear();
2769 changed_arcs_.clear();
2772 void PathState::CopyNewPathAtEndOfNodes(
int path) {
2774 const int new_path_begin_index = committed_nodes_.size();
2775 const PathBounds path_bounds = paths_[path];
2776 for (
int i = path_bounds.begin_index; i < path_bounds.end_index; ++i) {
2777 const ChainBounds chain_bounds = chains_[i];
2778 committed_nodes_.insert(committed_nodes_.end(),
2779 committed_nodes_.data() + chain_bounds.begin_index,
2780 committed_nodes_.data() + chain_bounds.end_index);
2782 const int new_path_end_index = committed_nodes_.size();
2784 for (
int i = new_path_begin_index; i < new_path_end_index; ++i) {
2785 committed_nodes_[i].path = path;
2791 void PathState::IncrementalCommit() {
2792 const int new_nodes_begin = committed_nodes_.size();
2794 const int chain_begin = committed_nodes_.size();
2795 CopyNewPathAtEndOfNodes(path);
2796 const int chain_end = committed_nodes_.size();
2797 chains_[path] = {chain_begin, chain_end};
2800 const int new_nodes_end = committed_nodes_.size();
2801 for (
int i = new_nodes_begin; i < new_nodes_end; ++i) {
2802 committed_index_[committed_nodes_[i].node] = i;
2808 std::tie(node,
next) = arc;
2809 if (node !=
next)
continue;
2810 const int index = committed_index_[node];
2811 committed_nodes_[
index].path = -1;
2817 void PathState::FullCommit() {
2820 const int old_num_nodes = committed_nodes_.size();
2821 for (
int path = 0; path < num_paths_; ++path) {
2822 const int new_path_begin = committed_nodes_.size() - old_num_nodes;
2823 CopyNewPathAtEndOfNodes(path);
2824 const int new_path_end = committed_nodes_.size() - old_num_nodes;
2825 chains_[path] = {new_path_begin, new_path_end};
2827 committed_nodes_.erase(committed_nodes_.begin(),
2828 committed_nodes_.begin() + old_num_nodes);
2831 constexpr
int kUnindexed = -1;
2832 committed_index_.assign(num_nodes_, kUnindexed);
2834 for (
const CommittedNode committed_node : committed_nodes_) {
2835 committed_index_[committed_node.node] =
index++;
2837 for (
int node = 0; node < num_nodes_; ++node) {
2838 if (committed_index_[node] != kUnindexed)
continue;
2839 committed_index_[node] =
index++;
2840 committed_nodes_.push_back({node, -1});
2848 class PathStateFilter :
public LocalSearchFilter {
2850 std::string DebugString()
const override {
return "PathStateFilter"; }
2851 PathStateFilter(std::unique_ptr<PathState> path_state,
2852 const std::vector<IntVar*>& nexts);
2853 void Relax(
const Assignment*
delta,
const Assignment* deltadelta)
override;
2854 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
2855 int64 objective_min,
int64 objective_max)
override {
2858 void Synchronize(
const Assignment*
delta,
2859 const Assignment* deltadelta)
override{};
2860 void Commit(
const Assignment* assignment,
const Assignment*
delta)
override;
2861 void Revert()
override;
2862 void Reset()
override;
2865 const std::unique_ptr<PathState> path_state_;
2867 std::vector<int> variable_index_to_node_;
2870 std::vector<bool> node_is_assigned_;
2873 PathStateFilter::PathStateFilter(std::unique_ptr<PathState> path_state,
2874 const std::vector<IntVar*>& nexts)
2875 : path_state_(std::move(path_state)) {
2879 for (
const IntVar*
next : nexts) {
2881 min_index = std::min<int>(min_index,
index);
2882 max_index = std::max<int>(max_index,
index);
2884 variable_index_to_node_.resize(max_index - min_index + 1, -1);
2885 index_offset_ = min_index;
2888 for (
int node = 0; node < nexts.size(); ++node) {
2889 const int index = nexts[node]->index() - index_offset_;
2890 variable_index_to_node_[
index] = node;
2894 void PathStateFilter::Relax(
const Assignment*
delta,
2895 const Assignment* deltadelta) {
2896 path_state_->Revert();
2897 for (
const IntVarElement& var_value :
delta->IntVarContainer().elements()) {
2898 if (var_value.Var() ==
nullptr)
continue;
2899 const int index = var_value.Var()->index() - index_offset_;
2900 if (
index < 0 || variable_index_to_node_.size() <=
index)
continue;
2901 const int node = variable_index_to_node_[
index];
2902 if (node == -1)
continue;
2903 if (var_value.Bound()) {
2904 path_state_->ChangeNext(node, var_value.Value());
2906 path_state_->Revert();
2907 path_state_->SetInvalid();
2911 path_state_->CutChains();
2914 void PathStateFilter::Reset() {
2915 path_state_->Revert();
2918 const int num_nodes = path_state_->NumNodes();
2919 node_is_assigned_.assign(num_nodes,
false);
2920 const int num_paths = path_state_->NumPaths();
2921 for (
int path = 0; path < num_paths; ++path) {
2922 const int start = path_state_->Start(path);
2923 const int end = path_state_->End(path);
2924 path_state_->ChangeNext(start, end);
2925 node_is_assigned_[start] =
true;
2926 node_is_assigned_[end] =
true;
2928 for (
int node = 0; node < num_nodes; ++node) {
2929 if (!node_is_assigned_[node]) path_state_->ChangeNext(node, node);
2931 path_state_->CutChains();
2932 path_state_->Commit();
2938 void PathStateFilter::Commit(
const Assignment* assignment,
2939 const Assignment*
delta) {
2940 path_state_->Revert();
2942 Relax(assignment,
nullptr);
2944 Relax(
delta,
nullptr);
2946 path_state_->Commit();
2949 void PathStateFilter::Revert() { path_state_->Revert(); }
2954 std::unique_ptr<PathState> path_state,
2955 const std::vector<IntVar*>& nexts) {
2956 PathStateFilter* filter =
new PathStateFilter(std::move(path_state), nexts);
2961 const PathState* path_state, std::vector<Interval> path_capacity,
2962 std::vector<int> path_class, std::vector<std::vector<Interval>>
demand,
2963 std::vector<Interval> node_capacity)
2964 : path_state_(path_state),
2965 path_capacity_(std::move(path_capacity)),
2966 path_class_(std::move(path_class)),
2967 demand_(std::move(
demand)),
2968 node_capacity_(std::move(node_capacity)),
2969 index_(path_state_->NumNodes(), 0),
2970 maximum_partial_demand_layer_size_(
2971 std::
max(16, 4 * path_state_->NumNodes()))
2973 const int num_nodes = path_state_->
NumNodes();
2974 const int num_paths = path_state_->
NumPaths();
2975 DCHECK_EQ(num_paths, path_capacity_.size());
2976 DCHECK_EQ(num_paths, path_class_.size());
2978 partial_demand_sums_rmq_.resize(maximum_rmq_exponent + 1);
2979 previous_nontrivial_index_.reserve(maximum_partial_demand_layer_size_);
2984 if (path_state_->
IsInvalid())
return true;
2986 const Interval path_capacity = path_capacity_[path];
2990 const int path_class = path_class_[path];
2992 Interval capacity_used = node_capacity_[path_state_->
Start(path)];
2995 if (capacity_used.
min > capacity_used.
max)
return false;
2997 for (
const auto chain : path_state_->
Chains(path)) {
2998 const int first_node = chain.First();
2999 const int last_node = chain.Last();
3001 const int first_index = index_[first_node];
3002 const int last_index = index_[last_node];
3004 const int chain_path = path_state_->
Path(first_node);
3005 const int chain_path_class =
3006 chain_path == -1 ? -1 : path_class_[chain_path];
3010 constexpr
int kMinRangeSizeForRMQ = 4;
3011 if (last_index - first_index > kMinRangeSizeForRMQ &&
3012 path_class == chain_path_class &&
3013 SubpathOnlyHasTrivialNodes(first_index, last_index)) {
3018 GetMinMaxPartialDemandSum(first_index, last_index);
3019 const Interval prev_sum = partial_demand_sums_rmq_[0][first_index - 1];
3027 if (capacity_used.
min > capacity_used.
max)
return false;
3029 const Interval last_sum = partial_demand_sums_rmq_[0][last_index];
3034 for (
const int node : chain) {
3035 const Interval node_capacity = node_capacity_[node];
3038 if (capacity_used.
min > capacity_used.
max)
return false;
3056 const int current_layer_size = partial_demand_sums_rmq_[0].size();
3059 for (
const auto chain : path_state_->
Chains(path)) {
3060 change_size += chain.NumNodes();
3063 if (current_layer_size + change_size <= maximum_partial_demand_layer_size_) {
3064 IncrementalCommit();
3070 void UnaryDimensionChecker::IncrementalCommit() {
3072 const int begin_index = partial_demand_sums_rmq_[0].size();
3073 AppendPathDemandsToSums(path);
3074 UpdateRMQStructure(begin_index, partial_demand_sums_rmq_[0].size());
3078 void UnaryDimensionChecker::FullCommit() {
3080 previous_nontrivial_index_.clear();
3081 for (
auto& sums : partial_demand_sums_rmq_) sums.clear();
3083 const int num_paths = path_state_->
NumPaths();
3084 for (
int path = 0; path < num_paths; ++path) {
3085 const int begin_index = partial_demand_sums_rmq_[0].size();
3086 AppendPathDemandsToSums(path);
3087 UpdateRMQStructure(begin_index, partial_demand_sums_rmq_[0].size());
3091 void UnaryDimensionChecker::AppendPathDemandsToSums(
int path) {
3092 const int path_class = path_class_[path];
3093 Interval demand_sum = {0, 0};
3094 int previous_nontrivial_index = -1;
3095 int index = partial_demand_sums_rmq_[0].size();
3098 partial_demand_sums_rmq_[0].push_back(demand_sum);
3099 previous_nontrivial_index_.push_back(-1);
3102 for (
const int node : path_state_->
Nodes(path)) {
3103 index_[node] =
index;
3104 const Interval
demand = demand_[path_class][node];
3107 partial_demand_sums_rmq_[0].push_back(demand_sum);
3109 const Interval node_capacity = node_capacity_[node];
3112 previous_nontrivial_index =
index;
3114 previous_nontrivial_index_.push_back(previous_nontrivial_index);
3119 void UnaryDimensionChecker::UpdateRMQStructure(
int begin_index,
int end_index) {
3122 const int maximum_rmq_exponent =
3124 for (
int layer = 1, window_size = 1; layer <= maximum_rmq_exponent;
3125 ++layer, window_size *= 2) {
3126 partial_demand_sums_rmq_[layer].resize(end_index);
3127 for (
int i = begin_index; i < end_index - window_size; ++i) {
3128 const Interval i1 = partial_demand_sums_rmq_[layer - 1][i];
3129 const Interval i2 = partial_demand_sums_rmq_[layer - 1][i + window_size];
3130 partial_demand_sums_rmq_[layer][i] = {
std::min(i1.min, i2.min),
3134 partial_demand_sums_rmq_[layer - 1].begin() + end_index - window_size,
3135 partial_demand_sums_rmq_[layer - 1].begin() + end_index,
3136 partial_demand_sums_rmq_[layer].begin() + end_index - window_size);
3146 UnaryDimensionChecker::Interval
3147 UnaryDimensionChecker::GetMinMaxPartialDemandSum(
int first_node_index,
3148 int last_node_index)
const {
3150 DCHECK_LT(first_node_index, last_node_index);
3151 DCHECK_LT(last_node_index, partial_demand_sums_rmq_[0].size());
3156 const int window_size = 1 << layer;
3158 const Interval i1 = partial_demand_sums_rmq_[layer][first_node_index];
3160 partial_demand_sums_rmq_[layer][last_node_index - window_size + 1];
3164 bool UnaryDimensionChecker::SubpathOnlyHasTrivialNodes(
3165 int first_node_index,
int last_node_index)
const {
3167 DCHECK_LT(first_node_index, last_node_index);
3168 DCHECK_LT(last_node_index, previous_nontrivial_index_.size());
3169 return first_node_index > previous_nontrivial_index_[last_node_index];
3174 class UnaryDimensionFilter :
public LocalSearchFilter {
3176 std::string DebugString()
const override {
return "UnaryDimensionFilter"; }
3177 explicit UnaryDimensionFilter(std::unique_ptr<UnaryDimensionChecker> checker)
3178 : checker_(std::move(checker)) {}
3180 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
3181 int64 objective_min,
int64 objective_max)
override {
3182 return checker_->Check();
3185 void Synchronize(
const Assignment* assignment,
3186 const Assignment*
delta)
override {
3191 std::unique_ptr<UnaryDimensionChecker> checker_;
3197 Solver* solver, std::unique_ptr<UnaryDimensionChecker> checker) {
3198 UnaryDimensionFilter* filter =
new UnaryDimensionFilter(std::move(checker));
3206 class VariableDomainFilter :
public LocalSearchFilter {
3208 VariableDomainFilter() {}
3209 ~VariableDomainFilter()
override {}
3210 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
3211 int64 objective_min,
int64 objective_max)
override;
3212 void Synchronize(
const Assignment* assignment,
3213 const Assignment*
delta)
override {}
3215 std::string DebugString()
const override {
return "VariableDomainFilter"; }
3218 bool VariableDomainFilter::Accept(
const Assignment*
delta,
3219 const Assignment* deltadelta,
3222 const int size = container.Size();
3223 for (
int i = 0; i < size; ++i) {
3224 const IntVarElement& element = container.Element(i);
3225 if (element.Activated() && !element.Var()->Contains(element.Value())) {
3234 return RevAlloc(
new VariableDomainFilter());
3239 const int IntVarLocalSearchFilter::kUnassigned = -1;
3242 const std::vector<IntVar*>& vars) {
3247 if (!vars.empty()) {
3248 for (
int i = 0; i < vars.size(); ++i) {
3249 const int index = vars[i]->index();
3250 if (
index >= var_index_to_index_.size()) {
3251 var_index_to_index_.resize(
index + 1, kUnassigned);
3253 var_index_to_index_[
index] = i + vars_.size();
3255 vars_.insert(vars_.end(), vars.begin(), vars.end());
3256 values_.resize(vars_.size(), 0);
3257 var_synced_.resize(vars_.size(),
false);
3266 var_synced_.assign(var_synced_.size(),
false);
3277 const int size = container.
Size();
3278 for (
int i = 0; i < size; ++i) {
3281 if (
var !=
nullptr) {
3282 if (i < vars_.size() && vars_[i] ==
var) {
3283 values_[i] = element.
Value();
3284 var_synced_[i] =
true;
3286 const int64 kUnallocated = -1;
3290 var_synced_[
index] =
true;
3309 SumObjectiveFilter(
const std::vector<IntVar*>& vars,
3319 for (
int i = 0; i < vars.size(); ++i) {
3324 ~SumObjectiveFilter()
override {
3328 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
3329 int64 objective_min,
int64 objective_max)
override {
3330 if (
delta ==
nullptr) {
3333 if (deltadelta->Empty()) {
3364 LOG(
ERROR) <<
"Unknown local search filter enum value";
3375 virtual bool FillCostOfBoundDeltaVariable(
3377 int* container_index,
int64* new_cost) = 0;
3378 bool IsIncremental()
const override {
return true; }
3380 std::string DebugString()
const override {
return "SumObjectiveFilter"; }
3382 int64 GetSynchronizedObjectiveValue()
const override {
3385 int64 GetAcceptedObjectiveValue()
const override {
return delta_sum_; }
3397 void OnSynchronize(
const Assignment*
delta)
override {
3400 const int64 cost = CostOfSynchronizedVariable(i);
3408 int64 CostOfChanges(
const Assignment* changes,
const int64*
const old_costs,
3409 bool cache_delta_values) {
3410 int64 total_cost = 0;
3412 const int size = container.
Size();
3413 for (
int i = 0; i < size; ++i) {
3414 const IntVarElement& new_element = container.Element(i);
3415 IntVar*
const var = new_element.Var();
3418 total_cost =
CapSub(total_cost, old_costs[
index]);
3419 int64 new_cost = 0LL;
3420 if (FillCostOfBoundDeltaVariable(container,
index, &i, &new_cost)) {
3421 total_cost =
CapAdd(total_cost, new_cost);
3423 if (cache_delta_values) {
3432 class BinaryObjectiveFilter :
public SumObjectiveFilter {
3434 BinaryObjectiveFilter(
const std::vector<IntVar*>& vars,
3437 : SumObjectiveFilter(vars, filter_enum),
3438 value_evaluator_(std::move(value_evaluator)) {}
3439 ~BinaryObjectiveFilter()
override {}
3446 int index,
int* container_index,
3447 int64* new_cost)
override {
3448 const IntVarElement& element = container.Element(*container_index);
3449 if (element.Activated()) {
3450 *new_cost = value_evaluator_(
index, element.Value());
3453 const IntVar*
var = element.Var();
3455 *new_cost = value_evaluator_(
index,
var->Min());
3466 class TernaryObjectiveFilter :
public SumObjectiveFilter {
3468 TernaryObjectiveFilter(
const std::vector<IntVar*>& vars,
3469 const std::vector<IntVar*>& secondary_vars,
3472 : SumObjectiveFilter(vars, filter_enum),
3473 secondary_vars_offset_(vars.size()),
3474 value_evaluator_(std::move(value_evaluator)) {
3478 ~TernaryObjectiveFilter()
override {}
3484 index + secondary_vars_offset_))
3488 int index,
int* container_index,
3489 int64* new_cost)
override {
3492 const IntVarElement& element = container.Element(*container_index);
3493 const IntVar* secondary_var =
3495 if (element.Activated()) {
3497 int hint_index = *container_index + 1;
3498 if (hint_index < container.Size() &&
3499 secondary_var == container.Element(hint_index).Var()) {
3501 container.Element(hint_index).Value());
3502 *container_index = hint_index;
3505 container.Element(secondary_var).Value());
3509 const IntVar*
var = element.Var();
3510 if (
var->Bound() && secondary_var->Bound()) {
3511 *new_cost = value_evaluator_(
index,
var->Min(), secondary_var->Min());
3519 int secondary_vars_offset_;
3528 new BinaryObjectiveFilter(vars, std::move(values), filter_enum));
3532 const std::vector<IntVar*>& vars,
3535 return RevAlloc(
new TernaryObjectiveFilter(vars, secondary_vars,
3536 std::move(values), filter_enum));
3540 int64 initial_max) {
3543 initial_variable_bounds_.push_back({initial_min, initial_max});
3544 variable_bounds_.push_back({initial_min, initial_max});
3545 variable_is_relaxed_.push_back(
false);
3547 const int variable_index = variable_bounds_.size() - 1;
3548 return {
this, variable_index};
3551 void LocalSearchState::RelaxVariableBounds(
int variable_index) {
3553 DCHECK(0 <= variable_index && variable_index < variable_is_relaxed_.size());
3554 if (!variable_is_relaxed_[variable_index]) {
3555 variable_is_relaxed_[variable_index] =
true;
3556 saved_variable_bounds_trail_.emplace_back(variable_bounds_[variable_index],
3558 variable_bounds_[variable_index] = initial_variable_bounds_[variable_index];
3562 int64 LocalSearchState::VariableMin(
int variable_index)
const {
3564 DCHECK(0 <= variable_index && variable_index < variable_bounds_.size());
3565 return variable_bounds_[variable_index].min;
3568 int64 LocalSearchState::VariableMax(
int variable_index)
const {
3570 DCHECK(0 <= variable_index && variable_index < variable_bounds_.size());
3571 return variable_bounds_[variable_index].max;
3574 bool LocalSearchState::TightenVariableMin(
int variable_index,
int64 min_value) {
3576 DCHECK(variable_is_relaxed_[variable_index]);
3577 DCHECK(0 <= variable_index && variable_index < variable_bounds_.size());
3578 Bounds&
bounds = variable_bounds_[variable_index];
3579 if (
bounds.max < min_value) {
3580 state_is_valid_ =
false;
3583 return state_is_valid_;
3586 bool LocalSearchState::TightenVariableMax(
int variable_index,
int64 max_value) {
3588 DCHECK(variable_is_relaxed_[variable_index]);
3589 DCHECK(0 <= variable_index && variable_index < variable_bounds_.size());
3590 Bounds&
bounds = variable_bounds_[variable_index];
3591 if (
bounds.min > max_value) {
3592 state_is_valid_ =
false;
3595 return state_is_valid_;
3603 saved_variable_bounds_trail_.clear();
3604 variable_is_relaxed_.assign(variable_is_relaxed_.size(),
false);
3608 for (
const auto& bounds_index : saved_variable_bounds_trail_) {
3609 DCHECK(variable_is_relaxed_[bounds_index.second]);
3610 variable_bounds_[bounds_index.second] = bounds_index.first;
3612 saved_variable_bounds_trail_.clear();
3613 variable_is_relaxed_.assign(variable_is_relaxed_.size(),
false);
3614 state_is_valid_ =
true;
3622 std::string
DebugString()
const override {
return "LocalSearchProfiler"; }
3624 operator_stats_.clear();
3625 filter_stats_.clear();
3629 if (
solver()->TopLevelSearch() ==
solver()->ActiveSearch()) {
3634 LocalSearchStatistics statistics_proto;
3635 std::vector<const LocalSearchOperator*> operators;
3636 for (
const auto& stat : operator_stats_) {
3637 operators.push_back(stat.first);
3640 operators.begin(), operators.end(),
3642 return gtl::FindOrDie(operator_stats_, op1).neighbors >
3643 gtl::FindOrDie(operator_stats_, op2).neighbors;
3646 const OperatorStats& stats =
gtl::FindOrDie(operator_stats_, op);
3647 LocalSearchStatistics::LocalSearchOperatorStatistics*
const
3648 local_search_operator_statistics =
3649 statistics_proto.add_local_search_operator_statistics();
3650 local_search_operator_statistics->set_local_search_operator(
3652 local_search_operator_statistics->set_num_neighbors(stats.neighbors);
3653 local_search_operator_statistics->set_num_filtered_neighbors(
3654 stats.filtered_neighbors);
3655 local_search_operator_statistics->set_num_accepted_neighbors(
3656 stats.accepted_neighbors);
3657 local_search_operator_statistics->set_duration_seconds(stats.seconds);
3659 std::vector<const LocalSearchFilter*> filters;
3660 for (
const auto& stat : filter_stats_) {
3661 filters.push_back(stat.first);
3663 std::sort(filters.begin(), filters.end(),
3666 return gtl::FindOrDie(filter_stats_, filter1).calls >
3667 gtl::FindOrDie(filter_stats_, filter2).calls;
3670 const FilterStats& stats =
gtl::FindOrDie(filter_stats_, filter);
3671 LocalSearchStatistics::LocalSearchFilterStatistics*
const
3672 local_search_filter_statistics =
3673 statistics_proto.add_local_search_filter_statistics();
3674 local_search_filter_statistics->set_local_search_filter(
3675 filter->DebugString());
3676 local_search_filter_statistics->set_num_calls(stats.calls);
3677 local_search_filter_statistics->set_num_rejects(stats.rejects);
3678 local_search_filter_statistics->set_duration_seconds(stats.seconds);
3680 statistics_proto.set_total_num_neighbors(
solver()->neighbors());
3681 statistics_proto.set_total_num_filtered_neighbors(
3682 solver()->filtered_neighbors());
3683 statistics_proto.set_total_num_accepted_neighbors(
3684 solver()->accepted_neighbors());
3685 return statistics_proto;
3688 size_t max_name_size = 0;
3689 std::vector<const LocalSearchOperator*> operators;
3690 for (
const auto& stat : operator_stats_) {
3691 operators.push_back(stat.first);
3693 std::max(max_name_size, stat.first->DebugString().length());
3696 operators.begin(), operators.end(),
3698 return gtl::FindOrDie(operator_stats_, op1).neighbors >
3699 gtl::FindOrDie(operator_stats_, op2).neighbors;
3701 std::string overview =
"Local search operator statistics:\n";
3702 absl::StrAppendFormat(&overview,
3703 "%*s | Neighbors | Filtered | Accepted | Time (s)\n",
3705 OperatorStats total_stats;
3707 const OperatorStats& stats =
gtl::FindOrDie(operator_stats_, op);
3708 const std::string&
name = op->DebugString();
3709 absl::StrAppendFormat(&overview,
"%*s | %9ld | %8ld | %8ld | %7.2g\n",
3710 max_name_size,
name, stats.neighbors,
3711 stats.filtered_neighbors, stats.accepted_neighbors,
3713 total_stats.neighbors += stats.neighbors;
3714 total_stats.filtered_neighbors += stats.filtered_neighbors;
3715 total_stats.accepted_neighbors += stats.accepted_neighbors;
3716 total_stats.seconds += stats.seconds;
3718 absl::StrAppendFormat(&overview,
"%*s | %9ld | %8ld | %8ld | %7.2g\n",
3719 max_name_size,
"Total", total_stats.neighbors,
3720 total_stats.filtered_neighbors,
3721 total_stats.accepted_neighbors, total_stats.seconds);
3723 std::vector<const LocalSearchFilter*> filters;
3724 for (
const auto& stat : filter_stats_) {
3725 filters.push_back(stat.first);
3727 std::max(max_name_size, stat.first->DebugString().length());
3729 std::sort(filters.begin(), filters.end(),
3732 return gtl::FindOrDie(filter_stats_, filter1).calls >
3733 gtl::FindOrDie(filter_stats_, filter2).calls;
3735 absl::StrAppendFormat(&overview,
3736 "Local search filter statistics:\n%*s | Calls | "
3737 " Rejects | Time (s) "
3740 FilterStats total_filter_stats;
3742 const FilterStats& stats =
gtl::FindOrDie(filter_stats_, filter);
3743 const std::string&
name = filter->DebugString();
3744 absl::StrAppendFormat(&overview,
"%*s | %9ld | %9ld | %7.2g | %7.2g\n",
3745 max_name_size,
name, stats.calls, stats.rejects,
3746 stats.seconds, stats.rejects / stats.seconds);
3747 total_filter_stats.calls += stats.calls;
3748 total_filter_stats.rejects += stats.rejects;
3749 total_filter_stats.seconds += stats.seconds;
3751 absl::StrAppendFormat(
3752 &overview,
"%*s | %9ld | %9ld | %7.2g | %7.2g\n", max_name_size,
3753 "Total", total_filter_stats.calls, total_filter_stats.rejects,
3754 total_filter_stats.seconds,
3755 total_filter_stats.rejects / total_filter_stats.seconds);
3761 if (last_operator_ != op->
Self()) {
3763 last_operator_ = op->
Self();
3769 if (neighbor_found) {
3770 operator_stats_[op->
Self()].neighbors++;
3775 bool neighbor_found)
override {
3776 if (neighbor_found) {
3777 operator_stats_[op->
Self()].filtered_neighbors++;
3782 bool neighbor_found)
override {
3783 if (neighbor_found) {
3784 operator_stats_[op->
Self()].accepted_neighbors++;
3788 filter_stats_[filter].calls++;
3789 filter_timer_.
Start();
3792 filter_timer_.
Stop();
3793 auto& stats = filter_stats_[filter];
3794 stats.seconds += filter_timer_.
Get();
3803 if (last_operator_ !=
nullptr) {
3805 operator_stats_[last_operator_].seconds += timer_.
Get();
3810 struct OperatorStats {
3811 int64 neighbors = 0;
3812 int64 filtered_neighbors = 0;
3813 int64 accepted_neighbors = 0;
3817 struct FilterStats {
3824 const LocalSearchOperator* last_operator_ =
nullptr;
3825 absl::flat_hash_map<const LocalSearchOperator*, OperatorStats>
3827 absl::flat_hash_map<const LocalSearchFilter*, FilterStats> filter_stats_;
3844 if (local_search_profiler_ !=
nullptr) {
3851 if (local_search_profiler_ !=
nullptr) {
3854 return LocalSearchStatistics();
3857 void LocalSearchFilterManager::InitializeForcedEvents() {
3858 const int num_events = filter_events_.size();
3859 int next_forced_event = num_events;
3860 next_forced_events_.resize(num_events);
3861 for (
int i = num_events - 1; i >= 0; --i) {
3862 next_forced_events_[i] = next_forced_event;
3863 if (filter_events_[i].filter->IsIncremental() ||
3864 (filter_events_[i].event_type == FilterEventType::kRelax &&
3865 next_forced_event != num_events)) {
3866 next_forced_event = i;
3872 std::vector<LocalSearchFilter*> filters)
3874 filter_events_.reserve(2 * filters.size());
3876 filter_events_.push_back({filter, FilterEventType::kRelax});
3879 filter_events_.push_back({filter, FilterEventType::kAccept});
3881 InitializeForcedEvents();
3885 std::vector<FilterEvent> filter_events)
3886 : filter_events_(std::move(filter_events)),
3889 InitializeForcedEvents();
3895 for (
int i = last_event_called_; i >= 0; --i) {
3896 auto [filter, event_type] = filter_events_[i];
3897 if (event_type == FilterEventType::kRelax) filter->Revert();
3899 last_event_called_ = -1;
3908 int64 objective_min,
3909 int64 objective_max) {
3911 accepted_value_ = 0;
3913 const int num_events = filter_events_.size();
3914 for (
int i = 0; i < num_events;) {
3915 last_event_called_ = i;
3916 auto [filter, event_type] = filter_events_[last_event_called_];
3917 switch (event_type) {
3918 case FilterEventType::kAccept: {
3920 const bool accept = filter->Accept(
3921 delta, deltadelta,
CapSub(objective_min, accepted_value_),
3922 CapSub(objective_max, accepted_value_));
3924 if (monitor !=
nullptr) monitor->
EndFiltering(filter, !accept);
3927 CapAdd(accepted_value_, filter->GetAcceptedObjectiveValue());
3929 ok = accepted_value_ <= objective_max;
3933 case FilterEventType::kRelax: {
3934 filter->Relax(
delta, deltadelta);
3938 LOG(
FATAL) <<
"Unknown filter event type.";
3944 i = next_forced_events_[i];
3955 const bool reset_to_assignment =
delta ==
nullptr ||
delta->Empty();
3957 for (
auto [filter, event_type] : filter_events_) {
3958 switch (event_type) {
3959 case FilterEventType::kAccept: {
3962 case FilterEventType::kRelax: {
3963 if (reset_to_assignment) {
3965 filter->Relax(assignment,
nullptr);
3967 filter->Relax(
delta,
nullptr);
3972 LOG(
FATAL) <<
"Unknown filter event type.";
3977 synchronized_value_ = 0;
3979 switch (event_type) {
3980 case FilterEventType::kAccept: {
3981 filter->Synchronize(assignment,
delta);
3982 synchronized_value_ =
CapAdd(synchronized_value_,
3983 filter->GetSynchronizedObjectiveValue());
3986 case FilterEventType::kRelax: {
3987 filter->Commit(assignment,
delta);
3991 LOG(
FATAL) <<
"Unknown filter event type.";
4008 std::string
DebugString()
const override {
return "FindOneNeighbor"; }
4013 void SynchronizeAll(
Solver* solver,
bool synchronize_filters =
true);
4016 IntVar*
const objective_;
4017 std::unique_ptr<Assignment> reference_assignment_;
4023 bool neighbor_found_;
4025 int64 solutions_since_last_check_;
4026 int64 check_period_;
4028 bool has_checked_assignment_ =
false;
4040 : assignment_(assignment),
4042 reference_assignment_(new
Assignment(assignment_)),
4044 ls_operator_(ls_operator),
4045 sub_decision_builder_(sub_decision_builder),
4047 original_limit_(limit),
4048 neighbor_found_(false),
4049 filter_manager_(filter_manager),
4050 solutions_since_last_check_(0),
4052 assignment_->solver()->
parameters().check_solution_period()),
4053 last_checked_assignment_(assignment) {
4054 CHECK(
nullptr != assignment);
4055 CHECK(
nullptr != ls_operator);
4059 if (
nullptr == limit) {
4067 VLOG(1) <<
"Disabling neighbor-check skipping outside of first accept.";
4074 VLOG(1) <<
"Disabling neighbor-check skipping for LNS.";
4078 if (!reference_assignment_->HasObjective()) {
4079 reference_assignment_->AddObjective(objective_);
4084 CHECK(
nullptr != solver);
4086 if (original_limit_ !=
nullptr) {
4087 limit_->
Copy(original_limit_);
4094 if (!neighbor_found_) {
4102 SynchronizeAll(solver,
false);
4112 if (sub_decision_builder_) {
4113 restore = solver->
Compose(restore, sub_decision_builder_);
4121 delta->ClearObjective();
4122 deltadelta->
Clear();
4124 if (++counter >= absl::GetFlag(FLAGS_cp_local_search_sync_frequency) &&
4125 pool_->
SyncNeeded(reference_assignment_.get())) {
4128 SynchronizeAll(solver);
4131 bool has_neighbor =
false;
4132 if (!limit_->
Check()) {
4136 ls_operator_, has_neighbor,
delta, deltadelta);
4139 if (has_neighbor && !solver->IsUncheckedSolutionLimitReached()) {
4140 solver->neighbors_ += 1;
4147 const bool mh_filter =
4152 objective_min = objective_->
Min();
4153 objective_max = objective_->
Max();
4155 if (
delta->HasObjective() &&
delta->Objective() == objective_) {
4156 objective_min =
std::max(objective_min,
delta->ObjectiveMin());
4157 objective_max =
std::min(objective_max,
delta->ObjectiveMax());
4159 const bool move_filter = FilterAccept(solver,
delta, deltadelta,
4160 objective_min, objective_max);
4162 ls_operator_, mh_filter && move_filter);
4163 if (!mh_filter || !move_filter) {
4164 if (filter_manager_ !=
nullptr) filter_manager_->
Revert();
4167 solver->filtered_neighbors_ += 1;
4168 if (
delta->HasObjective()) {
4180 const bool check_solution = (solutions_since_last_check_ == 0) ||
4183 !
delta->AreAllElementsBound();
4184 if (has_checked_assignment_) solutions_since_last_check_++;
4185 if (solutions_since_last_check_ >= check_period_) {
4186 solutions_since_last_check_ = 0;
4188 const bool accept = !check_solution || solver->
SolveAndCommit(restore);
4192 solver->accepted_neighbors_ += 1;
4193 if (check_solution) {
4196 assignment_->
Store();
4198 neighbor_found_ =
true;
4199 has_checked_assignment_ =
true;
4213 solver->IncrementUncheckedSolutionCounter();
4215 SynchronizeAll(solver);
4218 neighbor_found_ =
true;
4220 if (filter_manager_ !=
nullptr) filter_manager_->
Revert();
4221 if (check_period_ > 1 && has_checked_assignment_) {
4227 VLOG(1) <<
"Imperfect filtering detected, backtracking to last "
4228 "checked solution and checking all solutions.";
4230 solutions_since_last_check_ = 0;
4232 SynchronizeAll(solver);
4237 if (neighbor_found_) {
4249 has_checked_assignment_ =
true;
4257 SynchronizeAll(solver);
4270 int64 objective_max) {
4271 if (filter_manager_ ==
nullptr)
return true;
4273 return filter_manager_->
Accept(monitor,
delta, deltadelta, objective_min,
4277 void FindOneNeighbor::SynchronizeAll(Solver* solver,
bool synchronize_filters) {
4279 neighbor_found_ =
false;
4281 solver->GetLocalSearchMonitor()->BeginOperatorStart();
4282 ls_operator_->
Start(reference_assignment_.get());
4283 if (synchronize_filters && filter_manager_ !=
nullptr) {
4284 filter_manager_->
Synchronize(reference_assignment_.get(),
nullptr);
4286 solver->GetLocalSearchMonitor()->EndOperatorStart();
4299 solution_pool_(pool),
4306 return "LocalSearchPhaseParameters";
4313 return sub_decision_builder_;
4317 return filter_manager_;
4321 IntVar*
const objective_;
4333 ls_operator, sub_decision_builder,
4341 ls_operator, sub_decision_builder,
4350 ls_operator, sub_decision_builder,
4351 limit, filter_manager);
4359 sub_decision_builder,
nullptr,
nullptr);
4367 sub_decision_builder, limit,
nullptr);
4376 sub_decision_builder, limit,
4390 class NestedSolveDecision :
public Decision {
4393 enum StateType { DECISION_PENDING, DECISION_FAILED, DECISION_FOUND };
4395 NestedSolveDecision(DecisionBuilder*
const db,
bool restore,
4396 const std::vector<SearchMonitor*>& monitors);
4397 NestedSolveDecision(DecisionBuilder*
const db,
bool restore);
4398 ~NestedSolveDecision()
override {}
4399 void Apply(Solver*
const solver)
override;
4400 void Refute(Solver*
const solver)
override;
4401 std::string DebugString()
const override {
return "NestedSolveDecision"; }
4402 int state()
const {
return state_; }
4405 DecisionBuilder*
const db_;
4407 std::vector<SearchMonitor*> monitors_;
4411 NestedSolveDecision::NestedSolveDecision(
4412 DecisionBuilder*
const db,
bool restore,
4413 const std::vector<SearchMonitor*>& monitors)
4416 monitors_(monitors),
4417 state_(DECISION_PENDING) {
4418 CHECK(
nullptr != db);
4421 NestedSolveDecision::NestedSolveDecision(DecisionBuilder*
const db,
4423 : db_(db), restore_(restore), state_(DECISION_PENDING) {
4424 CHECK(
nullptr != db);
4427 void NestedSolveDecision::Apply(Solver*
const solver) {
4428 CHECK(
nullptr != solver);
4430 if (solver->Solve(db_, monitors_)) {
4431 solver->SaveAndSetValue(&state_,
static_cast<int>(DECISION_FOUND));
4433 solver->SaveAndSetValue(&state_,
static_cast<int>(DECISION_FAILED));
4436 if (solver->SolveAndCommit(db_, monitors_)) {
4437 solver->SaveAndSetValue(&state_,
static_cast<int>(DECISION_FOUND));
4439 solver->SaveAndSetValue(&state_,
static_cast<int>(DECISION_FAILED));
4444 void NestedSolveDecision::Refute(Solver*
const solver) {}
4455 class LocalSearch :
public DecisionBuilder {
4457 LocalSearch(Assignment*
const assignment, IntVar* objective,
4458 SolutionPool*
const pool, LocalSearchOperator*
const ls_operator,
4459 DecisionBuilder*
const sub_decision_builder,
4460 RegularLimit*
const limit,
4461 LocalSearchFilterManager* filter_manager);
4464 LocalSearch(
const std::vector<IntVar*>& vars, IntVar* objective,
4465 SolutionPool*
const pool, DecisionBuilder*
const first_solution,
4466 LocalSearchOperator*
const ls_operator,
4467 DecisionBuilder*
const sub_decision_builder,
4468 RegularLimit*
const limit,
4469 LocalSearchFilterManager* filter_manager);
4470 LocalSearch(
const std::vector<IntVar*>& vars, IntVar* objective,
4471 SolutionPool*
const pool, DecisionBuilder*
const first_solution,
4472 DecisionBuilder*
const first_solution_sub_decision_builder,
4473 LocalSearchOperator*
const ls_operator,
4474 DecisionBuilder*
const sub_decision_builder,
4475 RegularLimit*
const limit,
4476 LocalSearchFilterManager* filter_manager);
4477 LocalSearch(
const std::vector<SequenceVar*>& vars, IntVar* objective,
4478 SolutionPool*
const pool, DecisionBuilder*
const first_solution,
4479 LocalSearchOperator*
const ls_operator,
4480 DecisionBuilder*
const sub_decision_builder,
4481 RegularLimit*
const limit,
4482 LocalSearchFilterManager* filter_manager);
4483 ~LocalSearch()
override;
4484 Decision* Next(Solver*
const solver)
override;
4485 std::string DebugString()
const override {
return "LocalSearch"; }
4486 void Accept(ModelVisitor*
const visitor)
const override;
4489 void PushFirstSolutionDecision(DecisionBuilder* first_solution);
4490 void PushLocalSearchDecision();
4493 Assignment* assignment_;
4495 SolutionPool*
const pool_;
4496 LocalSearchOperator*
const ls_operator_;
4497 DecisionBuilder*
const first_solution_sub_decision_builder_;
4498 DecisionBuilder*
const sub_decision_builder_;
4499 std::vector<NestedSolveDecision*> nested_decisions_;
4500 int nested_decision_index_;
4501 RegularLimit*
const limit_;
4502 LocalSearchFilterManager*
const filter_manager_;
4506 LocalSearch::LocalSearch(Assignment*
const assignment, IntVar* objective,
4507 SolutionPool*
const pool,
4508 LocalSearchOperator*
const ls_operator,
4509 DecisionBuilder*
const sub_decision_builder,
4510 RegularLimit*
const limit,
4511 LocalSearchFilterManager* filter_manager)
4512 : assignment_(nullptr),
4515 ls_operator_(ls_operator),
4516 first_solution_sub_decision_builder_(sub_decision_builder),
4517 sub_decision_builder_(sub_decision_builder),
4518 nested_decision_index_(0),
4520 filter_manager_(filter_manager),
4521 has_started_(false) {
4522 CHECK(
nullptr != assignment);
4523 CHECK(
nullptr != ls_operator);
4524 Solver*
const solver = assignment->solver();
4525 assignment_ = solver->GetOrCreateLocalSearchState();
4526 assignment_->Copy(assignment);
4527 DecisionBuilder* restore = solver->MakeRestoreAssignment(assignment);
4528 PushFirstSolutionDecision(restore);
4529 PushLocalSearchDecision();
4532 LocalSearch::LocalSearch(
const std::vector<IntVar*>& vars, IntVar* objective,
4533 SolutionPool*
const pool,
4534 DecisionBuilder*
const first_solution,
4535 LocalSearchOperator*
const ls_operator,
4536 DecisionBuilder*
const sub_decision_builder,
4537 RegularLimit*
const limit,
4538 LocalSearchFilterManager* filter_manager)
4539 : assignment_(nullptr),
4542 ls_operator_(ls_operator),
4543 first_solution_sub_decision_builder_(sub_decision_builder),
4544 sub_decision_builder_(sub_decision_builder),
4545 nested_decision_index_(0),
4547 filter_manager_(filter_manager),
4548 has_started_(false) {
4549 CHECK(
nullptr != first_solution);
4550 CHECK(
nullptr != ls_operator);
4551 CHECK(!vars.empty());
4552 Solver*
const solver = vars[0]->solver();
4553 assignment_ = solver->GetOrCreateLocalSearchState();
4554 assignment_->Add(vars);
4555 PushFirstSolutionDecision(first_solution);
4556 PushLocalSearchDecision();
4559 LocalSearch::LocalSearch(
4560 const std::vector<IntVar*>& vars, IntVar* objective,
4561 SolutionPool*
const pool, DecisionBuilder*
const first_solution,
4562 DecisionBuilder*
const first_solution_sub_decision_builder,
4563 LocalSearchOperator*
const ls_operator,
4564 DecisionBuilder*
const sub_decision_builder, RegularLimit*
const limit,
4565 LocalSearchFilterManager* filter_manager)
4566 : assignment_(nullptr),
4569 ls_operator_(ls_operator),
4570 first_solution_sub_decision_builder_(first_solution_sub_decision_builder),
4571 sub_decision_builder_(sub_decision_builder),
4572 nested_decision_index_(0),
4574 filter_manager_(filter_manager),
4575 has_started_(false) {
4576 CHECK(
nullptr != first_solution);
4577 CHECK(
nullptr != ls_operator);
4578 CHECK(!vars.empty());
4579 Solver*
const solver = vars[0]->solver();
4580 assignment_ = solver->GetOrCreateLocalSearchState();
4581 assignment_->Add(vars);
4582 PushFirstSolutionDecision(first_solution);
4583 PushLocalSearchDecision();
4586 LocalSearch::LocalSearch(
const std::vector<SequenceVar*>& vars,
4587 IntVar* objective, SolutionPool*
const pool,
4588 DecisionBuilder*
const first_solution,
4589 LocalSearchOperator*
const ls_operator,
4590 DecisionBuilder*
const sub_decision_builder,
4591 RegularLimit*
const limit,
4592 LocalSearchFilterManager* filter_manager)
4593 : assignment_(nullptr),
4596 ls_operator_(ls_operator),
4597 first_solution_sub_decision_builder_(sub_decision_builder),
4598 sub_decision_builder_(sub_decision_builder),
4599 nested_decision_index_(0),
4601 filter_manager_(filter_manager),
4602 has_started_(false) {
4603 CHECK(
nullptr != first_solution);
4604 CHECK(
nullptr != ls_operator);
4605 CHECK(!vars.empty());
4606 Solver*
const solver = vars[0]->solver();
4607 assignment_ = solver->GetOrCreateLocalSearchState();
4608 assignment_->Add(vars);
4609 PushFirstSolutionDecision(first_solution);
4610 PushLocalSearchDecision();
4613 LocalSearch::~LocalSearch() {}
4616 void LocalSearch::Accept(ModelVisitor*
const visitor)
const {
4617 DCHECK(assignment_ !=
nullptr);
4620 const std::vector<IntVarElement>& elements =
4622 if (!elements.empty()) {
4623 std::vector<IntVar*> vars;
4624 for (
const IntVarElement& elem : elements) {
4625 vars.push_back(elem.Var());
4630 const std::vector<IntervalVarElement>& interval_elements =
4632 if (!interval_elements.empty()) {
4633 std::vector<IntervalVar*> interval_vars;
4634 for (
const IntervalVarElement& elem : interval_elements) {
4635 interval_vars.push_back(elem.Var());
4648 Decision* LocalSearch::Next(Solver*
const solver) {
4649 CHECK(
nullptr != solver);
4650 CHECK_LT(0, nested_decisions_.size());
4651 if (!has_started_) {
4652 nested_decision_index_ = 0;
4653 solver->SaveAndSetValue(&has_started_,
true);
4654 }
else if (nested_decision_index_ < 0) {
4657 NestedSolveDecision* decision = nested_decisions_[nested_decision_index_];
4658 const int state = decision->state();
4660 case NestedSolveDecision::DECISION_FAILED: {
4664 ls_operator_->
Reset();
4666 nested_decision_index_ = -1;
4671 case NestedSolveDecision::DECISION_PENDING: {
4674 const int32 kLocalSearchBalancedTreeDepth = 32;
4675 const int depth = solver->SearchDepth();
4676 if (depth < kLocalSearchBalancedTreeDepth) {
4677 return solver->balancing_decision();
4679 if (depth > kLocalSearchBalancedTreeDepth) {
4684 case NestedSolveDecision::DECISION_FOUND: {
4686 if (nested_decision_index_ + 1 < nested_decisions_.size()) {
4687 ++nested_decision_index_;
4692 LOG(
ERROR) <<
"Unknown local search state";
4700 class SynchronizeFiltersDecisionBuilder :
public DecisionBuilder {
4702 SynchronizeFiltersDecisionBuilder(Assignment* assignment,
4703 LocalSearchFilterManager* filter_manager)
4704 : assignment_(assignment), filter_manager_(filter_manager) {}
4706 Decision* Next(Solver*
const solver)
override {
4707 if (filter_manager_ !=
nullptr) {
4708 filter_manager_->Synchronize(assignment_,
nullptr);
4714 Assignment*
const assignment_;
4715 LocalSearchFilterManager*
const filter_manager_;
4719 void LocalSearch::PushFirstSolutionDecision(DecisionBuilder* first_solution) {
4720 CHECK(first_solution);
4721 Solver*
const solver = assignment_->
solver();
4723 DecisionBuilder* synchronize = solver->RevAlloc(
4724 new SynchronizeFiltersDecisionBuilder(assignment_, filter_manager_));
4725 DecisionBuilder* first_solution_and_store = solver->Compose(
4726 first_solution, first_solution_sub_decision_builder_, store, synchronize);
4727 std::vector<SearchMonitor*> monitor;
4728 monitor.push_back(
limit_);
4729 nested_decisions_.push_back(solver->RevAlloc(
4730 new NestedSolveDecision(first_solution_and_store,
false, monitor)));
4733 void LocalSearch::PushLocalSearchDecision() {
4734 Solver*
const solver = assignment_->
solver();
4735 DecisionBuilder* find_neighbors = solver->
RevAlloc(
4736 new FindOneNeighbor(assignment_,
objective_, pool_, ls_operator_,
4737 sub_decision_builder_,
limit_, filter_manager_));
4738 nested_decisions_.push_back(
4739 solver->RevAlloc(
new NestedSolveDecision(find_neighbors,
false)));
4742 class DefaultSolutionPool :
public SolutionPool {
4744 DefaultSolutionPool() {}
4746 ~DefaultSolutionPool()
override {}
4748 void Initialize(Assignment*
const assignment)
override {
4749 reference_assignment_ = absl::make_unique<Assignment>(assignment);
4752 void RegisterNewSolution(Assignment*
const assignment)
override {
4753 reference_assignment_->CopyIntersection(assignment);
4756 void GetNextSolution(Assignment*
const assignment)
override {
4757 assignment->CopyIntersection(reference_assignment_.get());
4760 bool SyncNeeded(Assignment*
const local_assignment)
override {
return false; }
4762 std::string DebugString()
const override {
return "DefaultSolutionPool"; }
4765 std::unique_ptr<Assignment> reference_assignment_;
4770 return RevAlloc(
new DefaultSolutionPool());
4797 first_solution, first_solution_sub_decision_builder,
4803 const std::vector<SequenceVar*>& vars,
DecisionBuilder* first_solution,
#define DCHECK_LE(val1, val2)
#define CHECK_LT(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define CHECK_LE(val1, val2)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
const std::vector< E > & elements() const
const E & Element(const V *const var) const
An Assignment is a variable -> domains mapping, used to report solutions to the user.
const IntContainer & IntVarContainer() const
IntVar * Objective() const
bool HasObjective() const
void AddObjective(IntVar *const v)
int64 ObjectiveValue() const
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
AssignmentContainer< IntVar, IntVarElement > IntContainer
const IntervalContainer & IntervalVarContainer() const
std::string DebugString() const override
void SetObjectiveValue(int64 value)
~BaseInactiveNodeToPathOperator() override
BaseInactiveNodeToPathOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_base_nodes, std::function< int(int64)> start_empty_path_class)
int64 GetInactiveNode() const
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
This is the base class for building an Lns operator.
virtual bool NextFragment()=0
void AppendToFragment(int index)
BaseLns(const std::vector< IntVar * > &vars)
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
virtual void InitFragments()
A BaseObject is the root of all reversibly allocated objects.
virtual std::string DebugString() const
ChangeValue(const std::vector< IntVar * > &vars)
virtual int64 ModifyValue(int64 index, int64 value)=0
bool MakeOneNeighbor() override
This method should not be overridden. Override ModifyValue() instead.
bool MakeNeighbor() override
Cross(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
A DecisionBuilder is responsible for creating the search tree.
A Decision represents a choice point in the search tree.
bool MakeNeighbor() override
Exchange(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
bool MakeNeighbor() override
~ExtendedSwapActiveOperator() override
std::string DebugString() const override
ExtendedSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
~FindOneNeighbor() override
FindOneNeighbor(Assignment *const assignment, IntVar *objective, SolutionPool *const pool, LocalSearchOperator *const ls_operator, DecisionBuilder *const sub_decision_builder, const RegularLimit *const limit, LocalSearchFilterManager *filter_manager)
Decision * Next(Solver *const solver) override
This is the main method of the decision builder class.
std::string DebugString() const override
void ChangeCostMatrix(CostFunction cost)
std::vector< int > TravelingSalesmanPath()
virtual int64 Max() const =0
virtual int64 Min() const =0
The class IntVar is a subset of IntExpr.
void SynchronizeOnAssignment(const Assignment *assignment)
virtual void OnSynchronize(const Assignment *delta)
bool FindIndex(IntVar *const var, int64 *index) const
~IntVarLocalSearchFilter() override
void Synchronize(const Assignment *assignment, const Assignment *delta) override
This method should not be overridden.
IntVarLocalSearchFilter(const std::vector< IntVar * > &vars)
IntVar * Var(int index) const
int64 Value(int index) const
void AddVars(const std::vector< IntVar * > &vars)
Add variables to "track" to the filter.
bool IsVarSynced(int index) const
Specialization of LocalSearchOperator built from an array of IntVars which specifies the scope of the...
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
virtual bool MakeOneNeighbor()
Creates a new neighbor.
bool MakeNeighbor() override
LinKernighan(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)
std::string DebugString() const override
Local Search Filters are used for fast neighbor pruning.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
LocalSearchFilterManager(std::vector< FilterEvent > filter_events)
int64 GetAcceptedObjectiveValue() const
bool Accept(LocalSearchMonitor *const monitor, const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max)
Returns true iff all filters return true, and the sum of their accepted objectives is between objecti...
void Synchronize(const Assignment *assignment, const Assignment *delta)
Synchronizes all filters to assignment.
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
The base class for all local search operators.
virtual bool HasFragments() const
virtual bool HoldsDelta() const
virtual const LocalSearchOperator * Self() const
virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0
virtual void Start(const Assignment *assignment)=0
LocalSearchOperator * ls_operator() const
~LocalSearchPhaseParameters() override
SolutionPool * solution_pool() const
IntVar * objective() const
LocalSearchFilterManager *const filter_manager() const
RegularLimit * limit() const
LocalSearchPhaseParameters(IntVar *objective, SolutionPool *const pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, RegularLimit *const limit, LocalSearchFilterManager *filter_manager)
DecisionBuilder * sub_decision_builder() const
std::string DebugString() const override
void BeginFiltering(const LocalSearchFilter *filter) override
void Install() override
Install itself on the solver.
void BeginOperatorStart() override
Local search operator events.
void RestartSearch() override
Restart the search.
void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta) override
LocalSearchStatistics ExportToLocalSearchStatistics() const
void BeginMakeNextNeighbor(const LocalSearchOperator *op) override
void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
void BeginAcceptNeighbor(const LocalSearchOperator *op) override
void ExitSearch() override
End of the search.
LocalSearchProfiler(Solver *solver)
void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
void EndOperatorStart() override
std::string PrintOverview() const
void EndFiltering(const LocalSearchFilter *filter, bool reject) override
void BeginFilterNeighbor(const LocalSearchOperator *op) override
std::string DebugString() const override
LocalSearchVariable AddVariable(int64 initial_min, int64 initial_max)
MakeActiveAndRelocate(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
bool MakeNeighbor() override
~MakeActiveAndRelocate() override
std::string DebugString() const override
~MakeActiveOperator() override
bool MakeNeighbor() override
MakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
bool MakeNeighbor() override
~MakeChainInactiveOperator() override
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
std::string DebugString() const override
MakeChainInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
bool MakeNeighbor() override
MakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
~MakeInactiveOperator() override
std::string DebugString() const override
static const char kIntervalsArgument[]
static const char kVarsArgument[]
static const char kVariableGroupExtension[]
const std::vector< int > & Neighbors(int index) const
NearestNeighbors(Solver::IndexEvaluator3 evaluator, const PathOperator &path_operator, int size)
virtual std::string DebugString() const
virtual ~NearestNeighbors()
NeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
bool HoldsDelta() const override
void Start(const Assignment *assignment) 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
bool HasFragments() const override
std::string DebugString() const override
Base class of the local search operators dedicated to path modifications (a path is a set of nodes li...
virtual bool MakeNeighbor()=0
bool SwapActiveAndInactive(int64 active, int64 inactive)
Replaces active by inactive in the current path, making active inactive.
int PathClass(int i) const
Returns the class of the path of the ith base node.
virtual void OnNodeInitialization()
Called by OnStart() after initializing node information.
int64 BaseNode(int i) const
Returns the ith base node of the operator.
bool IsInactive(int64 node) const
Returns true if node is inactive.
int number_of_nexts() const
Number of next variables.
bool IsPathEnd(int64 node) const
Returns true if node is the last node on the path; defined by the fact that node is outside the range...
virtual bool ConsiderAlternatives(int64 base_index) const
Indicates if alternatives should be considered when iterating over base nodes.
virtual bool RestartAtPathStartOnSynchronize()
When the operator is being synchronized with a new solution (when Start() is called),...
std::vector< int64 > start_to_path_
bool ReverseChain(int64 before_chain, int64 after_chain, int64 *chain_last)
Reverses the chain starting after before_chain and ending before after_chain.
int64 OldNext(int64 node) const
void SetNext(int64 from, int64 to, int64 path)
Sets 'to' to be the node after 'from' on the given path.
bool MakeActive(int64 node, int64 destination)
Insert the inactive node after destination.
int64 Prev(int64 node) const
Returns the node before node in the current delta.
int64 StartNode(int i) const
Returns the start node of the ith base node.
bool SkipUnchanged(int index) const override
int64 Next(int64 node) const
Returns the node after node in the current delta.
const int number_of_nexts_
void ResetPosition()
Reset the position of the operator to its position when Start() was last called; this can be used to ...
int next_base_to_increment_
virtual int64 GetBaseNodeRestartPosition(int base_index)
Returns the index of the node to which the base node of index base_index must be set to when it reach...
int GetSiblingAlternativeIndex(int node) const
Returns the index of the alternative set of the sibling of node.
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
virtual bool OnSamePathAsPreviousBase(int64 base_index)
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
bool MakeChainInactive(int64 before_chain, int64 chain_end)
Makes the nodes on the chain starting after before_chain and ending at chain_end inactive.
virtual bool InitPosition() const
Returns true if the operator needs to restart its initial position at each call to Start()
int64 Path(int64 node) const
Returns the index of the path to which node belongs in the current delta.
const bool ignore_path_vars_
bool CheckChainValidity(int64 before_chain, int64 chain_end, int64 exclude) const
Returns true if the chain is a valid path without cycles from before_chain to chain_end and does not ...
PathOperator(const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, int number_of_base_nodes, bool skip_locally_optimal_paths, bool accept_path_end_base, std::function< int(int64)> start_empty_path_class)
Builds an instance of PathOperator from next and path variables.
bool MoveChain(int64 before_chain, int64 chain_end, int64 destination)
Moves the chain starting after the node before_chain and ending at the node chain_end after the node ...
const std::vector< int > & ChangedPaths() const
NodeRange Nodes(int path) const
ChainRange Chains(int path) const
int Start(int path) const
const std::vector< std::pair< int, int > > & ChangedArcs() const
PathState(int num_nodes, std::vector< int > path_start, std::vector< int > path_end)
Usual limit based on wall_time, number of explored branches and number of failures in the search tree...
bool Check() override
This method is called to check the status of the limit.
void Init() override
This method is called when the search limit is initialized.
void Copy(const SearchLimit *const limit) override
Copy a limit.
RegularLimit * MakeIdenticalClone() const
bool MakeNeighbor() override
~RelocateAndMakeActiveOperator() override
RelocateAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
bool MakeNeighbor() override
~RelocateAndMakeInactiveOperator() override
RelocateAndMakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
bool MakeNeighbor() override
Relocate(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const std::string &name, std::function< int(int64)> start_empty_path_class, int64 chain_length=1LL, bool single_path=false)
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
std::string DebugString() const override
Relocate(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, int64 chain_length=1LL, bool single_path=false)
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
This class is used to manage a pool of solutions.
virtual bool SyncNeeded(Assignment *const local_assignment)=0
This method checks if the local solution needs to be updated with an external one.
virtual void RegisterNewSolution(Assignment *const assignment)=0
This method is called when a new solution has been accepted by the local search.
virtual void GetNextSolution(Assignment *const assignment)=0
This method is called when the local search starts a new neighborhood to initialize the default assig...
virtual void Initialize(Assignment *const assignment)=0
This method is called to initialize the solution pool with the assignment from the local search.
LocalSearchFilter * MakeVariableDomainFilter()
RegularLimit * MakeSolutionsLimit(int64 solutions)
Creates a search limit that constrains the number of solutions found during the search.
bool SolveAndCommit(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolveAndCommit using a decision builder and up to three search monitors, usually one for the objectiv...
LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)
Creates a local search operator that tries to move the assignment of some variables toward a target.
LocalSearchStatistics GetLocalSearchStatistics() const
Returns detailed local search statistics.
ConstraintSolverParameters parameters() const
Stored Parameters.
void SetSearchContext(Search *search, const std::string &search_context)
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Creates a local search operator which concatenates a vector of operators.
LocalSearchFilter * MakeRejectFilter()
LocalSearchFilter * MakeAcceptFilter()
Local Search Filters.
LocalSearchOperator * MakeRandomLnsOperator(const std::vector< IntVar * > &vars, int number_of_variables)
Creates a large neighborhood search operator which creates fragments (set of relaxed variables) with ...
LocalSearchOperator * RandomConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Randomized version of local search concatenator; calls a random operator at each call to MakeNextNeig...
LocalSearchOperators
This enum is used in Solver::MakeOperator to specify the neighborhood to create.
@ EXCHANGE
Operator which exchanges the positions of two nodes.
@ MAKEINACTIVE
Operator which makes path nodes inactive.
@ RELOCATE
Relocate neighborhood with length of 1 (see OROPT comment).
@ SWAPACTIVE
Operator which replaces an active node by an inactive one.
@ SIMPLELNS
Operator which defines one neighbor per variable.
@ INCREMENT
Operator which defines one neighbor per variable.
@ MAKECHAININACTIVE
Operator which makes a "chain" of path nodes inactive.
@ TWOOPT
Operator which reverses a sub-chain of a path.
@ FULLPATHLNS
Operator which relaxes one entire path and all inactive nodes, thus defining num_paths neighbors.
@ EXTENDEDSWAPACTIVE
Operator which makes an inactive node active and an active one inactive.
@ OROPT
Relocate: OROPT and RELOCATE.
@ PATHLNS
Operator which relaxes two sub-chains of three consecutive arcs each.
@ UNACTIVELNS
Operator which relaxes all inactive nodes and one sub-chain of six consecutive arcs.
@ MAKEACTIVE
Operator which inserts an inactive node into a path.
@ DECREMENT
Operator which defines a neighborhood to decrement values.
@ CROSS
Operator which cross exchanges the starting chains of 2 paths, including exchanging the whole paths.
LocalSearchPhaseParameters * MakeLocalSearchPhaseParameters(IntVar *objective, LocalSearchOperator *const ls_operator, DecisionBuilder *const sub_decision_builder)
Local Search Phase Parameters.
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
IntVarLocalSearchFilter * MakeSumObjectiveFilter(const std::vector< IntVar * > &vars, IndexEvaluator2 values, Solver::LocalSearchFilterBound filter_enum)
LocalSearchOperator * MakeNeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
Creates a local search operator that wraps another local search operator and limits the number of nei...
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
std::function< int64(int64, int64, int64)> IndexEvaluator3
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
SolutionPool * MakeDefaultSolutionPool()
Solution Pool.
bool UseFastLocalSearch() const
Returns true if fast local search is enabled.
LocalSearchOperator * MakeOperator(const std::vector< IntVar * > &vars, LocalSearchOperators op)
Local Search Operators.
std::string LocalSearchProfile() const
Returns local search profiling information in a human readable format.
T * RevAlloc(T *object)
Registers the given object as being reversible.
Solver(const std::string &name)
Solver API.
std::function< int64(int64, int64)> IndexEvaluator2
DecisionBuilder * MakeLocalSearchPhase(Assignment *const assignment, LocalSearchPhaseParameters *const parameters)
Local Search decision builders factories.
LocalSearchOperator * MultiArmedBanditConcatenateOperators(const std::vector< LocalSearchOperator * > &ops, double memory_coefficient, double exploration_coefficient, bool maximize)
Creates a local search operator which concatenates a vector of operators.
Assignment * MakeAssignment()
This method creates an empty assignment.
DecisionBuilder * Compose(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which sequentially composes decision builders.
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which stores an Assignment (calls void Assignment::Store())
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
EvaluatorLocalSearchOperators
This enum is used in Solver::MakeOperator associated with an evaluator to specify the neighborhood to...
@ TSPOPT
Sliding TSP operator.
@ LK
Lin-Kernighan local search.
LocalSearchFilterBound
This enum is used in Solver::MakeLocalSearchObjectiveFilter.
@ GE
Move is accepted when the current objective value >= objective.Min.
@ LE
Move is accepted when the current objective value <= objective.Max.
@ EQ
Move is accepted when the current objective value is in the interval objective.Min .
~SwapActiveOperator() override
bool MakeNeighbor() override
SwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
bool MakeNeighbor() override
TSPLns(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
std::string DebugString() const override
bool MakeNeighbor() override
TSPOpt(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)
std::string DebugString() const override
bool MakeNeighbor() override
bool IsIncremental() const override
TwoOpt(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
std::string DebugString() const override
UnaryDimensionChecker(const PathState *path_state, std::vector< Interval > path_capacity, std::vector< int > path_class, std::vector< std::vector< Interval >> demand, std::vector< Interval > node_capacity)
void RevertChanges(bool incremental)
std::vector< int64 > prev_values_
IntVar * Var(int64 index) const
Returns the variable of given index.
const int64 & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
bool ApplyChanges(Assignment *delta, Assignment *deltadelta) const
void Deactivate(int64 index)
void AddVars(const std::vector< IntVar * > &vars)
const int64 & OldValue(int64 index) const
void SetValue(int64 index, const int64 &value)
SharedBoundsManager * bounds
static const int64 kint64max
static const int64 kint64min
ABSL_FLAG(int, cp_local_search_sync_frequency, 16, "Frequency of checks for better solutions in the solution pool.")
Solver::LocalSearchFilterBound filter_enum_
int64 *const delta_costs_
const int primary_vars_size_
#define MAKE_LOCAL_SEARCH_OPERATOR(OperatorClass)
int64 *const synchronized_costs_
bool ContainsKey(const Collection &collection, const Key &key)
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
ReverseView< Container > reversed_view(const Container &c)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void InstallLocalSearchProfiler(LocalSearchProfiler *monitor)
int64 CapSub(int64 x, int64 y)
void DeleteLocalSearchProfiler(LocalSearchProfiler *monitor)
int64 CapAdd(int64 x, int64 y)
bool AcceptDelta(Search *const search, Assignment *delta, Assignment *deltadelta)
void AcceptNeighbor(Search *const search)
LocalSearchFilter * MakeUnaryDimensionFilter(Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)
LocalSearchOperator * MakeLocalSearchOperator(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Operator Factories.
LocalSearchFilter * MakePathStateFilter(Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)
bool LocalOptimumReached(Search *const search)
void AcceptUncheckedNeighbor(Search *const search)
int MostSignificantBitPosition32(uint32 n)
LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)
std::function< int64(int64, int64)> evaluator_