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,