OR-Tools  8.2
local_search.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #include <algorithm>
15 #include <iterator>
16 #include <map>
17 #include <memory>
18 #include <numeric>
19 #include <set>
20 #include <string>
21 #include <utility>
22 #include <vector>
23 
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"
31 #include "ortools/base/hash.h"
34 #include "ortools/base/logging.h"
35 #include "ortools/base/macros.h"
36 #include "ortools/base/map_util.h"
41 
42 ABSL_FLAG(int, cp_local_search_sync_frequency, 16,
43  "Frequency of checks for better solutions in the solution pool.");
44 
45 ABSL_FLAG(int, cp_local_search_tsp_opt_size, 13,
46  "Size of TSPs solved in the TSPOpt operator.");
47 
48 ABSL_FLAG(int, cp_local_search_tsp_lns_size, 10,
49  "Size of TSPs solved in the TSPLns operator.");
50 
51 ABSL_FLAG(bool, cp_use_empty_path_symmetry_breaker, true,
52  "If true, equivalent empty paths are removed from the neighborhood "
53  "of PathOperators");
54 
55 namespace operations_research {
56 
57 // Utility methods to ensure the communication between local search and the
58 // search.
59 
60 // Returns true if a local optimum has been reached and cannot be improved.
61 bool LocalOptimumReached(Search* const search);
62 
63 // Returns true if the search accepts the delta (actually checking this by
64 // calling AcceptDelta on the monitors of the search).
65 bool AcceptDelta(Search* const search, Assignment* delta,
66  Assignment* deltadelta);
67 
68 // Notifies the search that a neighbor has been accepted by local search.
69 void AcceptNeighbor(Search* const search);
70 void AcceptUncheckedNeighbor(Search* const search);
71 
72 // ----- Base operator class for operators manipulating IntVars -----
73 
75  Assignment* deltadelta) {
76  CHECK(delta != nullptr);
77  VLOG(2) << DebugString() << "::MakeNextNeighbor(delta=("
78  << delta->DebugString() << "), deltadelta=("
79  << (deltadelta ? deltadelta->DebugString() : std::string("nullptr"));
80  while (true) {
81  RevertChanges(true);
82 
83  if (!MakeOneNeighbor()) {
84  return false;
85  }
86 
87  if (ApplyChanges(delta, deltadelta)) {
88  VLOG(2) << "Delta (" << DebugString() << ") = " << delta->DebugString();
89  return true;
90  }
91  }
92  return false;
93 }
94 // TODO(user): Make this a pure virtual.
96 
97 // ----- Base Large Neighborhood Search operator -----
98 
99 BaseLns::BaseLns(const std::vector<IntVar*>& vars)
100  : IntVarLocalSearchOperator(vars) {}
101 
103 
105  fragment_.clear();
106  if (NextFragment()) {
107  for (int candidate : fragment_) {
108  Deactivate(candidate);
109  }
110  return true;
111  }
112  return false;
113 }
114 
115 void BaseLns::OnStart() { InitFragments(); }
116 
118 
120  if (index >= 0 && index < Size()) {
121  fragment_.push_back(index);
122  }
123 }
124 
125 int BaseLns::FragmentSize() const { return fragment_.size(); }
126 
127 // ----- Simple Large Neighborhood Search operator -----
128 
129 // Frees number_of_variables (contiguous in vars) variables.
130 
131 namespace {
132 class SimpleLns : public BaseLns {
133  public:
134  SimpleLns(const std::vector<IntVar*>& vars, int number_of_variables)
135  : BaseLns(vars), index_(0), number_of_variables_(number_of_variables) {
136  CHECK_GT(number_of_variables_, 0);
137  }
138  ~SimpleLns() override {}
139  void InitFragments() override { index_ = 0; }
140  bool NextFragment() override;
141  std::string DebugString() const override { return "SimpleLns"; }
142 
143  private:
144  int index_;
145  const int number_of_variables_;
146 };
147 
148 bool SimpleLns::NextFragment() {
149  const int size = Size();
150  if (index_ < size) {
151  for (int i = index_; i < index_ + number_of_variables_; ++i) {
152  AppendToFragment(i % size);
153  }
154  ++index_;
155  return true;
156  }
157  return false;
158 }
159 
160 // ----- Random Large Neighborhood Search operator -----
161 
162 // Frees up to number_of_variables random variables.
163 
164 class RandomLns : public BaseLns {
165  public:
166  RandomLns(const std::vector<IntVar*>& vars, int number_of_variables,
167  int32 seed)
168  : BaseLns(vars), rand_(seed), number_of_variables_(number_of_variables) {
169  CHECK_GT(number_of_variables_, 0);
170  CHECK_LE(number_of_variables_, Size());
171  }
172  ~RandomLns() override {}
173  bool NextFragment() override;
174 
175  std::string DebugString() const override { return "RandomLns"; }
176 
177  private:
178  std::mt19937 rand_;
179  const int number_of_variables_;
180 };
181 
182 bool RandomLns::NextFragment() {
183  DCHECK_GT(Size(), 0);
184  for (int i = 0; i < number_of_variables_; ++i) {
185  AppendToFragment(absl::Uniform<int>(rand_, 0, Size()));
186  }
187  return true;
188 }
189 } // namespace
190 
192  const std::vector<IntVar*>& vars, int number_of_variables) {
193  return MakeRandomLnsOperator(vars, number_of_variables, CpRandomSeed());
194 }
195 
197  const std::vector<IntVar*>& vars, int number_of_variables, int32 seed) {
198  return RevAlloc(new RandomLns(vars, number_of_variables, seed));
199 }
200 
201 // ----- Move Toward Target Local Search operator -----
202 
203 // A local search operator that compares the current assignment with a target
204 // one, and that generates neighbors corresponding to a single variable being
205 // changed from its current value to its target value.
206 namespace {
207 class MoveTowardTargetLS : public IntVarLocalSearchOperator {
208  public:
209  MoveTowardTargetLS(const std::vector<IntVar*>& variables,
210  const std::vector<int64>& target_values)
211  : IntVarLocalSearchOperator(variables),
212  target_(target_values),
213  // Initialize variable_index_ at the number of the of variables minus
214  // one, so that the first to be tried (after one increment) is the one
215  // of index 0.
216  variable_index_(Size() - 1) {
217  CHECK_EQ(target_values.size(), variables.size()) << "Illegal arguments.";
218  }
219 
220  ~MoveTowardTargetLS() override {}
221 
222  std::string DebugString() const override { return "MoveTowardTargetLS"; }
223 
224  protected:
225  // Make a neighbor assigning one variable to its target value.
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);
234  return true;
235  }
236  }
237  return false;
238  }
239 
240  private:
241  void OnStart() override {
242  // Do not change the value of variable_index_: this way, we keep going from
243  // where we last modified something. This is because we expect that most
244  // often, the variables we have just checked are less likely to be able
245  // to be changed to their target values than the ones we have not yet
246  // checked.
247  //
248  // Consider the case where oddly indexed variables can be assigned to their
249  // target values (no matter in what order they are considered), while even
250  // indexed ones cannot. Restarting at index 0 each time an odd-indexed
251  // variable is modified will cause a total of Theta(n^2) neighbors to be
252  // generated, while not restarting will produce only Theta(n) neighbors.
253  CHECK_GE(variable_index_, 0);
254  CHECK_LT(variable_index_, Size());
255  num_var_since_last_start_ = 0;
256  }
257 
258  // Target values
259  const std::vector<int64> target_;
260 
261  // Index of the next variable to try to restore
262  int64 variable_index_;
263 
264  // Number of variables checked since the last call to OnStart().
265  int64 num_var_since_last_start_;
266 };
267 } // namespace
268 
270  const Assignment& target) {
271  typedef std::vector<IntVarElement> Elements;
272  const Elements& elements = target.IntVarContainer().elements();
273  // Copy target values and construct the vector of variables
274  std::vector<IntVar*> vars;
275  std::vector<int64> values;
276  vars.reserve(target.NumIntVars());
277  values.reserve(target.NumIntVars());
278  for (const auto& it : elements) {
279  vars.push_back(it.Var());
280  values.push_back(it.Value());
281  }
282  return MakeMoveTowardTargetOperator(vars, values);
283 }
284 
286  const std::vector<IntVar*>& variables,
287  const std::vector<int64>& target_values) {
288  return RevAlloc(new MoveTowardTargetLS(variables, target_values));
289 }
290 
291 // ----- ChangeValue Operators -----
292 
293 ChangeValue::ChangeValue(const std::vector<IntVar*>& vars)
294  : IntVarLocalSearchOperator(vars), index_(0) {}
295 
297 
299  const int size = Size();
300  while (index_ < size) {
301  const int64 value = ModifyValue(index_, Value(index_));
302  SetValue(index_, value);
303  ++index_;
304  return true;
305  }
306  return false;
307 }
308 
309 void ChangeValue::OnStart() { index_ = 0; }
310 
311 // Increments the current value of variables.
312 
313 namespace {
314 class IncrementValue : public ChangeValue {
315  public:
316  explicit IncrementValue(const std::vector<IntVar*>& vars)
317  : ChangeValue(vars) {}
318  ~IncrementValue() override {}
319  int64 ModifyValue(int64 index, int64 value) override { return value + 1; }
320 
321  std::string DebugString() const override { return "IncrementValue"; }
322 };
323 
324 // Decrements the current value of variables.
325 
326 class DecrementValue : public ChangeValue {
327  public:
328  explicit DecrementValue(const std::vector<IntVar*>& vars)
329  : ChangeValue(vars) {}
330  ~DecrementValue() override {}
331  int64 ModifyValue(int64 index, int64 value) override { return value - 1; }
332 
333  std::string DebugString() const override { return "DecrementValue"; }
334 };
335 } // namespace
336 
337 // ----- Path-based Operators -----
338 
339 PathOperator::PathOperator(const std::vector<IntVar*>& next_vars,
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)
345  : IntVarLocalSearchOperator(next_vars, true),
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),
355  first_start_(true),
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) {
361  DCHECK_GT(number_of_base_nodes, 0);
362  if (!ignore_path_vars_) {
363  AddVars(path_vars);
364  }
365  path_basis_.push_back(0);
366  for (int i = 1; i < base_nodes_.size(); ++i) {
367  if (!OnSamePathAsPreviousBase(i)) path_basis_.push_back(i);
368  }
369  if ((path_basis_.size() > 2) ||
370  (!next_vars.empty() && !next_vars.back()
371  ->solver()
372  ->parameters()
373  .skip_locally_optimal_paths())) {
374  skip_locally_optimal_paths_ = false;
375  }
376 }
377 
378 void PathOperator::Reset() { optimal_paths_.clear(); }
379 
380 void PathOperator::OnStart() {
381  optimal_paths_enabled_ = false;
382  InitializeBaseNodes();
383  InitializeAlternatives();
385 }
386 
388  while (IncrementPosition()) {
389  // Need to revert changes here since MakeNeighbor might have returned false
390  // and have done changes in the previous iteration.
391  RevertChanges(true);
392  if (MakeNeighbor()) {
393  return true;
394  }
395  }
396  return false;
397 }
398 
400  if (ignore_path_vars_) {
401  return true;
402  }
403  if (index < number_of_nexts_) {
404  int path_index = index + number_of_nexts_;
405  return Value(path_index) == OldValue(path_index);
406  }
407  int next_index = index - number_of_nexts_;
408  return Value(next_index) == OldValue(next_index);
409 }
410 
411 bool PathOperator::MoveChain(int64 before_chain, int64 chain_end,
412  int64 destination) {
413  if (destination == before_chain || destination == chain_end) return false;
414  DCHECK(CheckChainValidity(before_chain, chain_end, destination) &&
415  !IsPathEnd(chain_end) && !IsPathEnd(destination));
416  const int64 destination_path = Path(destination);
417  const int64 after_chain = Next(chain_end);
418  SetNext(chain_end, Next(destination), destination_path);
419  if (!ignore_path_vars_) {
420  int current = destination;
421  int next = Next(before_chain);
422  while (current != chain_end) {
423  SetNext(current, next, destination_path);
424  current = next;
425  next = Next(next);
426  }
427  } else {
428  SetNext(destination, Next(before_chain), destination_path);
429  }
430  SetNext(before_chain, after_chain, Path(before_chain));
431  return true;
432 }
433 
434 bool PathOperator::ReverseChain(int64 before_chain, int64 after_chain,
435  int64* chain_last) {
436  if (CheckChainValidity(before_chain, after_chain, -1)) {
437  int64 path = Path(before_chain);
438  int64 current = Next(before_chain);
439  if (current == after_chain) {
440  return false;
441  }
442  int64 current_next = Next(current);
443  SetNext(current, after_chain, path);
444  while (current_next != after_chain) {
445  const int64 next = Next(current_next);
446  SetNext(current_next, current, path);
447  current = current_next;
448  current_next = next;
449  }
450  SetNext(before_chain, current, path);
451  *chain_last = current;
452  return true;
453  }
454  return false;
455 }
456 
457 bool PathOperator::MakeActive(int64 node, int64 destination) {
458  if (!IsPathEnd(destination)) {
459  int64 destination_path = Path(destination);
460  SetNext(node, Next(destination), destination_path);
461  SetNext(destination, node, destination_path);
462  return true;
463  }
464  return false;
465 }
466 
467 bool PathOperator::MakeChainInactive(int64 before_chain, int64 chain_end) {
468  const int64 kNoPath = -1;
469  if (CheckChainValidity(before_chain, chain_end, -1) &&
470  !IsPathEnd(chain_end)) {
471  const int64 after_chain = Next(chain_end);
472  int64 current = Next(before_chain);
473  while (current != after_chain) {
474  const int64 next = Next(current);
475  SetNext(current, current, kNoPath);
476  current = next;
477  }
478  SetNext(before_chain, after_chain, Path(before_chain));
479  return true;
480  }
481  return false;
482 }
483 
485  if (active == inactive) return false;
486  const int64 prev = Prev(active);
487  return MakeChainInactive(prev, active) && MakeActive(inactive, prev);
488 }
489 
490 bool PathOperator::IncrementPosition() {
491  const int base_node_size = base_nodes_.size();
492 
493  if (!just_started_) {
494  const int number_of_paths = path_starts_.size();
495  // Finding next base node positions.
496  // Increment the position of inner base nodes first (higher index nodes);
497  // if a base node is at the end of a path, reposition it at the start
498  // of the path and increment the position of the preceding base node (this
499  // action is called a restart).
500  int last_restarted = base_node_size;
501  for (int i = base_node_size - 1; i >= 0; --i) {
502  if (base_nodes_[i] < number_of_nexts_ && i <= next_base_to_increment_) {
503  if (ConsiderAlternatives(i)) {
504  // Iterate on sibling alternatives.
505  const int sibling_alternative_index =
506  GetSiblingAlternativeIndex(base_nodes_[i]);
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];
511  break;
512  }
513  base_sibling_alternatives_[i] = 0;
514  }
515  // Iterate on base alternatives.
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];
521  break;
522  }
523  base_alternatives_[i] = 0;
524  base_sibling_alternatives_[i] = 0;
525  }
526  }
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;
531  }
532  base_alternatives_[i] = 0;
533  base_sibling_alternatives_[i] = 0;
534  base_nodes_[i] = StartNode(i);
535  last_restarted = i;
536  }
537  next_base_to_increment_ = base_node_size;
538  // At the end of the loop, base nodes with indexes in
539  // [last_restarted, base_node_size[ have been restarted.
540  // Restarted base nodes are then repositioned by the virtual
541  // GetBaseNodeRestartPosition to reflect position constraints between
542  // base nodes (by default GetBaseNodeRestartPosition leaves the nodes
543  // at the start of the path).
544  // Base nodes are repositioned in ascending order to ensure that all
545  // base nodes "below" the node being repositioned have their final
546  // position.
547  for (int i = last_restarted; i < base_node_size; ++i) {
548  base_alternatives_[i] = 0;
549  base_sibling_alternatives_[i] = 0;
550  base_nodes_[i] = GetBaseNodeRestartPosition(i);
551  }
552  if (last_restarted > 0) {
553  return CheckEnds();
554  }
555  // If all base nodes have been restarted, base nodes are moved to new paths.
556  // First we mark the current paths as locally optimal if they have been
557  // completely explored.
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) {
561  optimal_paths_[num_paths_ *
562  start_to_path_[StartNode(path_basis_[i - 1])] +
563  start_to_path_[StartNode(path_basis_[i])]] = true;
564  }
565  } else {
566  optimal_paths_[num_paths_ * start_to_path_[StartNode(path_basis_[0])] +
567  start_to_path_[StartNode(path_basis_[0])]] = true;
568  }
569  }
570  std::vector<int> current_starts(base_node_size);
571  for (int i = 0; i < base_node_size; ++i) {
572  current_starts[i] = StartNode(i);
573  }
574  // Exploration of next paths can lead to locally optimal paths since we are
575  // exploring them from scratch.
576  optimal_paths_enabled_ = true;
577  while (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];
585  if (i == 0 || !OnSamePathAsPreviousBase(i)) {
586  break;
587  }
588  } else {
589  base_paths_[i] = 0;
590  base_alternatives_[i] = 0;
591  base_sibling_alternatives_[i] = 0;
592  base_nodes_[i] = path_starts_[0];
593  }
594  }
595  if (!skip_locally_optimal_paths_) return CheckEnds();
596  // If the new paths have already been completely explored, we can
597  // skip them from now on.
598  if (path_basis_.size() > 1) {
599  for (int j = 1; j < path_basis_.size(); ++j) {
600  if (!optimal_paths_[num_paths_ * start_to_path_[StartNode(
601  path_basis_[j - 1])] +
602  start_to_path_[StartNode(path_basis_[j])]]) {
603  return CheckEnds();
604  }
605  }
606  } else {
607  if (!optimal_paths_[num_paths_ *
608  start_to_path_[StartNode(path_basis_[0])] +
609  start_to_path_[StartNode(path_basis_[0])]]) {
610  return CheckEnds();
611  }
612  }
613  // If we are back to paths we just iterated on or have reached the end
614  // of the neighborhood search space, we can stop.
615  if (!CheckEnds()) return false;
616  bool stop = true;
617  for (int i = 0; i < base_node_size; ++i) {
618  if (StartNode(i) != current_starts[i]) {
619  stop = false;
620  break;
621  }
622  }
623  if (stop) return false;
624  }
625  } else {
626  just_started_ = false;
627  return true;
628  }
629  return CheckEnds();
630 }
631 
632 void PathOperator::InitializePathStarts() {
633  // Detect nodes which do not have any possible predecessor in a path; these
634  // nodes are path starts.
635  int max_next = -1;
636  std::vector<bool> has_prevs(number_of_nexts_, false);
637  for (int i = 0; i < number_of_nexts_; ++i) {
638  const int next = OldNext(i);
639  if (next < number_of_nexts_) {
640  has_prevs[next] = true;
641  }
642  max_next = std::max(max_next, next);
643  }
644  // Update locally optimal paths.
645  if (optimal_paths_.empty() && skip_locally_optimal_paths_) {
646  num_paths_ = 0;
647  start_to_path_.clear();
648  start_to_path_.resize(number_of_nexts_, -1);
649  for (int i = 0; i < number_of_nexts_; ++i) {
650  if (!has_prevs[i]) {
652  ++num_paths_;
653  }
654  }
655  optimal_paths_.resize(num_paths_ * num_paths_, false);
656  }
657  if (skip_locally_optimal_paths_) {
658  for (int i = 0; i < number_of_nexts_; ++i) {
659  if (!has_prevs[i]) {
660  int current = i;
661  while (!IsPathEnd(current)) {
662  if ((OldNext(current) != prev_values_[current])) {
663  for (int j = 0; j < num_paths_; ++j) {
664  optimal_paths_[num_paths_ * start_to_path_[i] + j] = false;
665  optimal_paths_[num_paths_ * j + start_to_path_[i]] = false;
666  }
667  break;
668  }
669  current = OldNext(current);
670  }
671  }
672  }
673  }
674  // Create a list of path starts, dropping equivalent path starts of
675  // currently empty paths.
676  std::vector<bool> empty_found(number_of_nexts_, false);
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);
680  for (int i = 0; i < number_of_nexts_; ++i) {
681  if (!has_prevs[i]) {
682  if (use_empty_path_symmetry_breaker && IsPathEnd(OldNext(i))) {
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;
686  }
687  }
688  new_path_starts.push_back(i);
689  }
690  }
691  if (!first_start_) {
692  // Synchronizing base_paths_ with base node positions. When the last move
693  // was performed a base node could have been moved to a new route in which
694  // case base_paths_ needs to be updated. This needs to be done on the path
695  // starts before we re-adjust base nodes for new path starts.
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];
699  while (!IsPathEnd(node)) {
700  node_paths[node] = i;
701  node = OldNext(node);
702  }
703  node_paths[node] = i;
704  }
705  for (int j = 0; j < base_nodes_.size(); ++j) {
706  // Always restart from first alternative.
707  base_alternatives_[j] = 0;
708  base_sibling_alternatives_[j] = 0;
709  if (IsInactive(base_nodes_[j]) || node_paths[base_nodes_[j]] == -1) {
710  // Base node was made inactive or was moved to a new path, reposition
711  // the base node to the start of the path on which it was.
712  base_nodes_[j] = path_starts_[base_paths_[j]];
713  } else {
714  base_paths_[j] = node_paths[base_nodes_[j]];
715  }
716  }
717  // Re-adjust current base_nodes and base_paths to take into account new
718  // path starts (there could be fewer if a new path was made empty, or more
719  // if nodes were added to a formerly empty path).
720  int new_index = 0;
721  absl::flat_hash_set<int> found_bases;
722  for (int i = 0; i < path_starts_.size(); ++i) {
723  int index = new_index;
724  // Note: old and new path starts are sorted by construction.
725  while (index < new_path_starts.size() &&
726  new_path_starts[index] < path_starts_[i]) {
727  ++index;
728  }
729  const bool found = (index < new_path_starts.size() &&
730  new_path_starts[index] == path_starts_[i]);
731  if (found) {
732  new_index = index;
733  }
734  for (int j = 0; j < base_nodes_.size(); ++j) {
735  if (base_paths_[j] == i && !gtl::ContainsKey(found_bases, j)) {
736  found_bases.insert(j);
737  base_paths_[j] = new_index;
738  // If the current position of the base node is a removed empty path,
739  // readjusting it to the last visited path start.
740  if (!found) {
741  base_nodes_[j] = new_path_starts[new_index];
742  }
743  }
744  }
745  }
746  }
747  path_starts_.swap(new_path_starts);
748 }
749 
750 void PathOperator::InitializeInactives() {
751  inactives_.clear();
752  for (int i = 0; i < number_of_nexts_; ++i) {
753  inactives_.push_back(OldNext(i) == i);
754  }
755 }
756 
757 void PathOperator::InitializeBaseNodes() {
758  // Inactive nodes must be detected before determining new path starts.
759  InitializeInactives();
760  InitializePathStarts();
761  if (first_start_ || InitPosition()) {
762  // Only do this once since the following starts will continue from the
763  // preceding position
764  for (int i = 0; i < base_nodes_.size(); ++i) {
765  base_paths_[i] = 0;
766  base_nodes_[i] = path_starts_[0];
767  }
768  first_start_ = false;
769  }
770  for (int i = 0; i < base_nodes_.size(); ++i) {
771  // If base node has been made inactive, restart from path start.
772  int64 base_node = base_nodes_[i];
773  if (RestartAtPathStartOnSynchronize() || IsInactive(base_node)) {
774  base_node = path_starts_[base_paths_[i]];
775  base_nodes_[i] = base_node;
776  }
777  end_nodes_[i] = base_node;
778  }
779  // Repair end_nodes_ in case some must be on the same path and are not anymore
780  // (due to other operators moving these nodes).
781  for (int i = 1; i < base_nodes_.size(); ++i) {
782  if (OnSamePathAsPreviousBase(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];
788  }
789  }
790  for (int i = 0; i < base_nodes_.size(); ++i) {
791  base_alternatives_[i] = 0;
792  base_sibling_alternatives_[i] = 0;
793  }
794  just_started_ = true;
795 }
796 
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;
802  for (int64 index : alternative_sets_[i]) {
803  if (!IsInactive(index)) {
804  active_in_alternative_set_[i] = index;
805  break;
806  }
807  }
808  }
809 }
810 
811 bool PathOperator::OnSamePath(int64 node1, int64 node2) const {
812  if (IsInactive(node1) != IsInactive(node2)) {
813  return false;
814  }
815  for (int node = node1; !IsPathEnd(node); node = OldNext(node)) {
816  if (node == node2) {
817  return true;
818  }
819  }
820  for (int node = node2; !IsPathEnd(node); node = OldNext(node)) {
821  if (node == node1) {
822  return true;
823  }
824  }
825  return false;
826 }
827 
828 // Rejects chain if chain_end is not after before_chain on the path or if
829 // the chain contains exclude. Given before_chain is the node before the
830 // chain, if before_chain and chain_end are the same the chain is rejected too.
831 // Also rejects cycles (cycle detection is detected through chain length
832 // overflow).
833 bool PathOperator::CheckChainValidity(int64 before_chain, int64 chain_end,
834  int64 exclude) const {
835  if (before_chain == chain_end || before_chain == exclude) return false;
836  int64 current = before_chain;
837  int chain_size = 0;
838  while (current != chain_end) {
839  if (chain_size > number_of_nexts_) {
840  return false;
841  }
842  if (IsPathEnd(current)) {
843  return false;
844  }
845  current = Next(current);
846  ++chain_size;
847  if (current == exclude) {
848  return false;
849  }
850  }
851  return true;
852 }
853 
854 // ----- 2Opt -----
855 
856 // Reverses a sub-chain of a path. It is called 2Opt because it breaks
857 // 2 arcs on the path; resulting paths are called 2-optimal.
858 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5
859 // (where (1, 5) are first and last nodes of the path and can therefore not be
860 // moved):
861 // 1 -> 3 -> 2 -> 4 -> 5
862 // 1 -> 4 -> 3 -> 2 -> 5
863 // 1 -> 2 -> 4 -> 3 -> 5
864 class TwoOpt : public PathOperator {
865  public:
866  TwoOpt(const std::vector<IntVar*>& vars,
867  const std::vector<IntVar*>& secondary_vars,
868  std::function<int(int64)> start_empty_path_class)
869  : PathOperator(vars, secondary_vars, 2, true, true,
870  std::move(start_empty_path_class)),
871  last_base_(-1),
872  last_(-1) {}
873  ~TwoOpt() override {}
874  bool MakeNeighbor() override;
875  bool IsIncremental() const override { return true; }
876 
877  std::string DebugString() const override { return "TwoOpt"; }
878 
879  protected:
880  bool OnSamePathAsPreviousBase(int64 base_index) override {
881  // Both base nodes have to be on the same path.
882  return true;
883  }
884  int64 GetBaseNodeRestartPosition(int base_index) override {
885  return (base_index == 0) ? StartNode(0) : BaseNode(0);
886  }
887 
888  private:
889  void OnNodeInitialization() override { last_ = -1; }
890 
891  int64 last_base_;
892  int64 last_;
893 };
894 
896  DCHECK_EQ(StartNode(0), StartNode(1));
897  if (last_base_ != BaseNode(0) || last_ == -1) {
898  RevertChanges(false);
899  if (IsPathEnd(BaseNode(0))) {
900  last_ = -1;
901  return false;
902  }
903  last_base_ = BaseNode(0);
904  last_ = Next(BaseNode(0));
905  int64 chain_last;
906  if (ReverseChain(BaseNode(0), BaseNode(1), &chain_last)
907  // Check there are more than one node in the chain (reversing a
908  // single node is a NOP).
909  && last_ != chain_last) {
910  return true;
911  }
912  last_ = -1;
913  return false;
914  }
915  const int64 to_move = Next(last_);
916  DCHECK_EQ(Next(to_move), BaseNode(1));
917  return MoveChain(last_, to_move, BaseNode(0));
918 }
919 
920 // ----- Relocate -----
921 
922 // Moves a sub-chain of a path to another position; the specified chain length
923 // is the fixed length of the chains being moved. When this length is 1 the
924 // operator simply moves a node to another position.
925 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5, for a chain length
926 // of 2 (where (1, 5) are first and last nodes of the path and can
927 // therefore not be moved):
928 // 1 -> 4 -> 2 -> 3 -> 5
929 // 1 -> 3 -> 4 -> 2 -> 5
930 //
931 // Using Relocate with chain lengths of 1, 2 and 3 together is equivalent to
932 // the OrOpt operator on a path. The OrOpt operator is a limited version of
933 // 3Opt (breaks 3 arcs on a path).
934 
935 class Relocate : public PathOperator {
936  public:
937  Relocate(const std::vector<IntVar*>& vars,
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)
941  : PathOperator(vars, secondary_vars, 2, true, false,
942  std::move(start_empty_path_class)),
943  chain_length_(chain_length),
944  single_path_(single_path),
945  name_(name) {
946  CHECK_GT(chain_length_, 0);
947  }
948  Relocate(const std::vector<IntVar*>& vars,
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)
952  : Relocate(vars, secondary_vars,
953  absl::StrCat("Relocate<", chain_length, ">"),
954  std::move(start_empty_path_class), chain_length, single_path) {
955  }
956  ~Relocate() override {}
957  bool MakeNeighbor() override;
958 
959  std::string DebugString() const override { return name_; }
960 
961  protected:
962  bool OnSamePathAsPreviousBase(int64 base_index) override {
963  // Both base nodes have to be on the same path when it's the single path
964  // version.
965  return single_path_;
966  }
967 
968  private:
969  const int64 chain_length_;
970  const bool single_path_;
971  const std::string name_;
972 };
973 
975  DCHECK(!single_path_ || StartNode(0) == StartNode(1));
976  const int64 destination = BaseNode(1);
977  DCHECK(!IsPathEnd(destination));
978  const int64 before_chain = BaseNode(0);
979  int64 chain_end = before_chain;
980  for (int i = 0; i < chain_length_; ++i) {
981  if (IsPathEnd(chain_end) || chain_end == destination) {
982  return false;
983  }
984  chain_end = Next(chain_end);
985  }
986  return !IsPathEnd(chain_end) &&
987  MoveChain(before_chain, chain_end, destination);
988 }
989 
990 // ----- Exchange -----
991 
992 // Exchanges the positions of two nodes.
993 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5
994 // (where (1, 5) are first and last nodes of the path and can therefore not
995 // be moved):
996 // 1 -> 3 -> 2 -> 4 -> 5
997 // 1 -> 4 -> 3 -> 2 -> 5
998 // 1 -> 2 -> 4 -> 3 -> 5
999 
1000 class Exchange : public PathOperator {
1001  public:
1002  Exchange(const std::vector<IntVar*>& vars,
1003  const std::vector<IntVar*>& secondary_vars,
1004  std::function<int(int64)> start_empty_path_class)
1005  : PathOperator(vars, secondary_vars, 2, true, false,
1006  std::move(start_empty_path_class)) {}
1007  ~Exchange() override {}
1008  bool MakeNeighbor() override;
1009 
1010  std::string DebugString() const override { return "Exchange"; }
1011 };
1012 
1014  const int64 prev_node0 = BaseNode(0);
1015  const int64 node0 = Next(prev_node0);
1016  if (IsPathEnd(node0)) return false;
1017  const int64 prev_node1 = BaseNode(1);
1018  const int64 node1 = Next(prev_node1);
1019  if (IsPathEnd(node1)) return false;
1020  const bool ok = MoveChain(prev_node0, node0, prev_node1);
1021  return MoveChain(Prev(node1), node1, prev_node0) || ok;
1022 }
1023 
1024 // ----- Cross -----
1025 
1026 // Cross echanges the starting chains of 2 paths, including exchanging the
1027 // whole paths.
1028 // First and last nodes are not moved.
1029 // Possible neighbors for the paths 1 -> 2 -> 3 -> 4 -> 5 and 6 -> 7 -> 8
1030 // (where (1, 5) and (6, 8) are first and last nodes of the paths and can
1031 // therefore not be moved):
1032 // 1 -> 7 -> 3 -> 4 -> 5 6 -> 2 -> 8
1033 // 1 -> 7 -> 4 -> 5 6 -> 2 -> 3 -> 8
1034 // 1 -> 7 -> 5 6 -> 2 -> 3 -> 4 -> 8
1035 
1036 class Cross : public PathOperator {
1037  public:
1038  Cross(const std::vector<IntVar*>& vars,
1039  const std::vector<IntVar*>& secondary_vars,
1040  std::function<int(int64)> start_empty_path_class)
1041  : PathOperator(vars, secondary_vars, 2, true, true,
1042  std::move(start_empty_path_class)) {}
1043  ~Cross() override {}
1044  bool MakeNeighbor() override;
1045 
1046  std::string DebugString() const override { return "Cross"; }
1047 };
1048 
1050  const int64 start0 = StartNode(0);
1051  const int64 start1 = StartNode(1);
1052  if (start1 == start0) return false;
1053  const int64 node0 = BaseNode(0);
1054  if (node0 == start0) return false;
1055  const int64 node1 = BaseNode(1);
1056  if (node1 == start1) return false;
1057  if (!IsPathEnd(node0) && !IsPathEnd(node1)) {
1058  // If two paths are equivalent don't exchange them.
1059  if (PathClass(0) == PathClass(1) && IsPathEnd(Next(node0)) &&
1060  IsPathEnd(Next(node1))) {
1061  return false;
1062  }
1063  return MoveChain(start0, node0, start1) && MoveChain(node0, node1, start0);
1064  }
1065  if (!IsPathEnd(node0)) return MoveChain(start0, node0, start1);
1066  if (!IsPathEnd(node1)) return MoveChain(start1, node1, start0);
1067  return false;
1068 }
1069 
1070 // ----- BaseInactiveNodeToPathOperator -----
1071 // Base class of path operators which make inactive nodes active.
1072 
1074  public:
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)),
1081  inactive_node_(0) {
1082  // TODO(user): Activate skipping optimal paths.
1083  }
1085 
1086  protected:
1087  bool MakeOneNeighbor() override;
1088  int64 GetInactiveNode() const { return inactive_node_; }
1089 
1090  private:
1091  void OnNodeInitialization() override;
1092 
1093  int inactive_node_;
1094 };
1095 
1096 void BaseInactiveNodeToPathOperator::OnNodeInitialization() {
1097  for (int i = 0; i < Size(); ++i) {
1098  if (IsInactive(i)) {
1099  inactive_node_ = i;
1100  return;
1101  }
1102  }
1103  inactive_node_ = Size();
1104 }
1105 
1107  while (inactive_node_ < Size()) {
1108  if (!IsInactive(inactive_node_) || !PathOperator::MakeOneNeighbor()) {
1109  ResetPosition();
1110  ++inactive_node_;
1111  } else {
1112  return true;
1113  }
1114  }
1115  return false;
1116 }
1117 
1118 // ----- MakeActiveOperator -----
1119 
1120 // MakeActiveOperator inserts an inactive node into a path.
1121 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive (where 1 and
1122 // 4 are first and last nodes of the path) are:
1123 // 1 -> 5 -> 2 -> 3 -> 4
1124 // 1 -> 2 -> 5 -> 3 -> 4
1125 // 1 -> 2 -> 3 -> 5 -> 4
1126 
1128  public:
1129  MakeActiveOperator(const std::vector<IntVar*>& vars,
1130  const std::vector<IntVar*>& secondary_vars,
1131  std::function<int(int64)> start_empty_path_class)
1132  : BaseInactiveNodeToPathOperator(vars, secondary_vars, 1,
1133  std::move(start_empty_path_class)) {}
1134  ~MakeActiveOperator() override {}
1135  bool MakeNeighbor() override;
1136 
1137  std::string DebugString() const override { return "MakeActiveOperator"; }
1138 };
1139 
1141  return MakeActive(GetInactiveNode(), BaseNode(0));
1142 }
1143 
1144 // ---- RelocateAndMakeActiveOperator -----
1145 
1146 // RelocateAndMakeActiveOperator relocates a node and replaces it by an inactive
1147 // node.
1148 // The idea is to make room for inactive nodes.
1149 // Possible neighbor for paths 0 -> 4, 1 -> 2 -> 5 and 3 inactive is:
1150 // 0 -> 2 -> 4, 1 -> 3 -> 5.
1151 // TODO(user): Naming is close to MakeActiveAndRelocate but this one is
1152 // correct; rename MakeActiveAndRelocate if it is actually used.
1154  public:
1156  const std::vector<IntVar*>& vars,
1157  const std::vector<IntVar*>& secondary_vars,
1158  std::function<int(int64)> start_empty_path_class)
1159  : BaseInactiveNodeToPathOperator(vars, secondary_vars, 2,
1160  std::move(start_empty_path_class)) {}
1162  bool MakeNeighbor() override {
1163  const int64 before_node_to_move = BaseNode(1);
1164  const int64 node = Next(before_node_to_move);
1165  return !IsPathEnd(node) &&
1166  MoveChain(before_node_to_move, node, BaseNode(0)) &&
1167  MakeActive(GetInactiveNode(), before_node_to_move);
1168  }
1169 
1170  std::string DebugString() const override {
1171  return "RelocateAndMakeActiveOpertor";
1172  }
1173 };
1174 
1175 // ----- MakeActiveAndRelocate -----
1176 
1177 // MakeActiveAndRelocate makes a node active next to a node being relocated.
1178 // Possible neighbor for paths 0 -> 4, 1 -> 2 -> 5 and 3 inactive is:
1179 // 0 -> 3 -> 2 -> 4, 1 -> 5.
1180 
1182  public:
1183  MakeActiveAndRelocate(const std::vector<IntVar*>& vars,
1184  const std::vector<IntVar*>& secondary_vars,
1185  std::function<int(int64)> start_empty_path_class)
1186  : BaseInactiveNodeToPathOperator(vars, secondary_vars, 2,
1187  std::move(start_empty_path_class)) {}
1189  bool MakeNeighbor() override;
1190 
1191  std::string DebugString() const override {
1192  return "MakeActiveAndRelocateOperator";
1193  }
1194 };
1195 
1197  const int64 before_chain = BaseNode(1);
1198  const int64 chain_end = Next(before_chain);
1199  const int64 destination = BaseNode(0);
1200  return !IsPathEnd(chain_end) &&
1201  MoveChain(before_chain, chain_end, destination) &&
1202  MakeActive(GetInactiveNode(), destination);
1203 }
1204 
1205 // ----- MakeInactiveOperator -----
1206 
1207 // MakeInactiveOperator makes path nodes inactive.
1208 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are first
1209 // and last nodes of the path) are:
1210 // 1 -> 3 -> 4 & 2 inactive
1211 // 1 -> 2 -> 4 & 3 inactive
1212 
1214  public:
1215  MakeInactiveOperator(const std::vector<IntVar*>& vars,
1216  const std::vector<IntVar*>& secondary_vars,
1217  std::function<int(int64)> start_empty_path_class)
1218  : PathOperator(vars, secondary_vars, 1, true, false,
1219  std::move(start_empty_path_class)) {}
1221  bool MakeNeighbor() override {
1222  const int64 base = BaseNode(0);
1223  return MakeChainInactive(base, Next(base));
1224  }
1225 
1226  std::string DebugString() const override { return "MakeInactiveOperator"; }
1227 };
1228 
1229 // ----- RelocateAndMakeInactiveOperator -----
1230 
1231 // RelocateAndMakeInactiveOperator relocates a node to a new position and makes
1232 // the node which was at that position inactive.
1233 // Possible neighbors for paths 0 -> 2 -> 4, 1 -> 3 -> 5 are:
1234 // 0 -> 3 -> 4, 1 -> 5 & 2 inactive
1235 // 0 -> 4, 1 -> 2 -> 5 & 3 inactive
1236 
1238  public:
1240  const std::vector<IntVar*>& vars,
1241  const std::vector<IntVar*>& secondary_vars,
1242  std::function<int(int64)> start_empty_path_class)
1243  : PathOperator(vars, secondary_vars, 2, true, false,
1244  std::move(start_empty_path_class)) {}
1246  bool MakeNeighbor() override {
1247  const int64 destination = BaseNode(1);
1248  const int64 before_to_move = BaseNode(0);
1249  const int64 node_to_inactivate = Next(destination);
1250  if (node_to_inactivate == before_to_move || IsPathEnd(node_to_inactivate) ||
1251  !MakeChainInactive(destination, node_to_inactivate)) {
1252  return false;
1253  }
1254  const int64 node = Next(before_to_move);
1255  return !IsPathEnd(node) && MoveChain(before_to_move, node, destination);
1256  }
1257 
1258  std::string DebugString() const override {
1259  return "RelocateAndMakeInactiveOperator";
1260  }
1261 };
1262 
1263 // ----- MakeChainInactiveOperator -----
1264 
1265 // Operator which makes a "chain" of path nodes inactive.
1266 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are first
1267 // and last nodes of the path) are:
1268 // 1 -> 3 -> 4 with 2 inactive
1269 // 1 -> 2 -> 4 with 3 inactive
1270 // 1 -> 4 with 2 and 3 inactive
1271 
1273  public:
1274  MakeChainInactiveOperator(const std::vector<IntVar*>& vars,
1275  const std::vector<IntVar*>& secondary_vars,
1276  std::function<int(int64)> start_empty_path_class)
1277  : PathOperator(vars, secondary_vars, 2, true, false,
1278  std::move(start_empty_path_class)) {}
1280  bool MakeNeighbor() override {
1281  return MakeChainInactive(BaseNode(0), BaseNode(1));
1282  }
1283 
1284  std::string DebugString() const override {
1285  return "MakeChainInactiveOperator";
1286  }
1287 
1288  protected:
1289  bool OnSamePathAsPreviousBase(int64 base_index) override {
1290  // Start and end of chain (defined by both base nodes) must be on the same
1291  // path.
1292  return true;
1293  }
1294 
1295  int64 GetBaseNodeRestartPosition(int base_index) override {
1296  // Base node 1 must be after base node 0.
1297  return (base_index == 0) ? StartNode(base_index) : BaseNode(base_index - 1);
1298  }
1299 };
1300 
1301 // ----- SwapActiveOperator -----
1302 
1303 // SwapActiveOperator replaces an active node by an inactive one.
1304 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive (where 1 and
1305 // 4 are first and last nodes of the path) are:
1306 // 1 -> 5 -> 3 -> 4 & 2 inactive
1307 // 1 -> 2 -> 5 -> 4 & 3 inactive
1308 
1310  public:
1311  SwapActiveOperator(const std::vector<IntVar*>& vars,
1312  const std::vector<IntVar*>& secondary_vars,
1313  std::function<int(int64)> start_empty_path_class)
1314  : BaseInactiveNodeToPathOperator(vars, secondary_vars, 1,
1315  std::move(start_empty_path_class)) {}
1316  ~SwapActiveOperator() override {}
1317  bool MakeNeighbor() override;
1318 
1319  std::string DebugString() const override { return "SwapActiveOperator"; }
1320 };
1321 
1323  const int64 base = BaseNode(0);
1324  return MakeChainInactive(base, Next(base)) &&
1325  MakeActive(GetInactiveNode(), base);
1326 }
1327 
1328 // ----- ExtendedSwapActiveOperator -----
1329 
1330 // ExtendedSwapActiveOperator makes an inactive node active and an active one
1331 // inactive. It is similar to SwapActiveOperator excepts that it tries to
1332 // insert the inactive node in all possible positions instead of just the
1333 // position of the node made inactive.
1334 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive (where 1 and
1335 // 4 are first and last nodes of the path) are:
1336 // 1 -> 5 -> 3 -> 4 & 2 inactive
1337 // 1 -> 3 -> 5 -> 4 & 2 inactive
1338 // 1 -> 5 -> 2 -> 4 & 3 inactive
1339 // 1 -> 2 -> 5 -> 4 & 3 inactive
1340 
1342  public:
1343  ExtendedSwapActiveOperator(const std::vector<IntVar*>& vars,
1344  const std::vector<IntVar*>& secondary_vars,
1345  std::function<int(int64)> start_empty_path_class)
1346  : BaseInactiveNodeToPathOperator(vars, secondary_vars, 2,
1347  std::move(start_empty_path_class)) {}
1349  bool MakeNeighbor() override;
1350 
1351  std::string DebugString() const override {
1352  return "ExtendedSwapActiveOperator";
1353  }
1354 };
1355 
1357  const int64 base0 = BaseNode(0);
1358  const int64 base1 = BaseNode(1);
1359  if (Next(base0) == base1) {
1360  return false;
1361  }
1362  return MakeChainInactive(base0, Next(base0)) &&
1363  MakeActive(GetInactiveNode(), base1);
1364 }
1365 
1366 // ----- TSP-based operators -----
1367 
1368 // Sliding TSP operator
1369 // Uses an exact dynamic programming algorithm to solve the TSP corresponding
1370 // to path sub-chains.
1371 // For a subchain 1 -> 2 -> 3 -> 4 -> 5 -> 6, solves the TSP on nodes A, 2, 3,
1372 // 4, 5, where A is a merger of nodes 1 and 6 such that cost(A,i) = cost(1,i)
1373 // and cost(i,A) = cost(i,6).
1374 
1375 class TSPOpt : public PathOperator {
1376  public:
1377  TSPOpt(const std::vector<IntVar*>& vars,
1378  const std::vector<IntVar*>& secondary_vars,
1379  Solver::IndexEvaluator3 evaluator, int chain_length);
1380  ~TSPOpt() override {}
1381  bool MakeNeighbor() override;
1382 
1383  std::string DebugString() const override { return "TSPOpt"; }
1384 
1385  private:
1386  std::vector<std::vector<int64>> cost_;
1388  hamiltonian_path_solver_;
1389  Solver::IndexEvaluator3 evaluator_;
1390  const int chain_length_;
1391 };
1392 
1393 TSPOpt::TSPOpt(const std::vector<IntVar*>& vars,
1394  const std::vector<IntVar*>& secondary_vars,
1395  Solver::IndexEvaluator3 evaluator, int chain_length)
1396  : PathOperator(vars, secondary_vars, 1, true, false, nullptr),
1397  hamiltonian_path_solver_(cost_),
1398  evaluator_(std::move(evaluator)),
1399  chain_length_(chain_length) {}
1400 
1402  std::vector<int64> nodes;
1403  int64 chain_end = BaseNode(0);
1404  for (int i = 0; i < chain_length_ + 1; ++i) {
1405  nodes.push_back(chain_end);
1406  if (IsPathEnd(chain_end)) {
1407  break;
1408  }
1409  chain_end = Next(chain_end);
1410  }
1411  if (nodes.size() <= 3) {
1412  return false;
1413  }
1414  int64 chain_path = Path(BaseNode(0));
1415  const int size = nodes.size() - 1;
1416  cost_.resize(size);
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);
1422  }
1423  }
1424  hamiltonian_path_solver_.ChangeCostMatrix(cost_);
1425  std::vector<PathNodeIndex> path;
1426  hamiltonian_path_solver_.TravelingSalesmanPath(&path);
1427  CHECK_EQ(size + 1, path.size());
1428  for (int i = 0; i < size - 1; ++i) {
1429  SetNext(nodes[path[i]], nodes[path[i + 1]], chain_path);
1430  }
1431  SetNext(nodes[path[size - 1]], nodes[size], chain_path);
1432  return true;
1433 }
1434 
1435 // TSP-base lns
1436 // Randomly merge consecutive nodes until n "meta"-nodes remain and solve the
1437 // corresponding TSP. This can be seen as a large neighborhood search operator
1438 // although decisions are taken with the operator.
1439 // This is an "unlimited" neighborhood which must be stopped by search limits.
1440 // To force diversification, the operator iteratively forces each node to serve
1441 // as base of a meta-node.
1442 
1443 class TSPLns : public PathOperator {
1444  public:
1445  TSPLns(const std::vector<IntVar*>& vars,
1446  const std::vector<IntVar*>& secondary_vars,
1447  Solver::IndexEvaluator3 evaluator, int tsp_size);
1448  ~TSPLns() override {}
1449  bool MakeNeighbor() override;
1450 
1451  std::string DebugString() const override { return "TSPLns"; }
1452 
1453  protected:
1454  bool MakeOneNeighbor() override;
1455 
1456  private:
1457  void OnNodeInitialization() override {
1458  // NOTE: Avoid any computations if there are no vars added.
1459  has_long_enough_paths_ = Size() != 0;
1460  }
1461 
1462  std::vector<std::vector<int64>> cost_;
1463  HamiltonianPathSolver<int64, std::vector<std::vector<int64>>>
1464  hamiltonian_path_solver_;
1465  Solver::IndexEvaluator3 evaluator_;
1466  const int tsp_size_;
1467  std::mt19937 rand_;
1468  bool has_long_enough_paths_;
1469 };
1470 
1471 TSPLns::TSPLns(const std::vector<IntVar*>& vars,
1472  const std::vector<IntVar*>& secondary_vars,
1473  Solver::IndexEvaluator3 evaluator, int tsp_size)
1474  : PathOperator(vars, secondary_vars, 1, true, false, nullptr),
1475  hamiltonian_path_solver_(cost_),
1476  evaluator_(std::move(evaluator)),
1477  tsp_size_(tsp_size),
1478  rand_(CpRandomSeed()),
1479  has_long_enough_paths_(true) {
1480  CHECK_GE(tsp_size_, 0);
1481  cost_.resize(tsp_size_);
1482  for (int i = 0; i < tsp_size_; ++i) {
1483  cost_[i].resize(tsp_size_);
1484  }
1485 }
1486 
1488  while (has_long_enough_paths_) {
1489  has_long_enough_paths_ = false;
1491  return true;
1492  }
1493  Var(0)->solver()->TopPeriodicCheck();
1494  }
1495  return false;
1496 }
1497 
1499  const int64 base_node = BaseNode(0);
1500  std::vector<int64> nodes;
1501  for (int64 node = StartNode(0); !IsPathEnd(node); node = Next(node)) {
1502  nodes.push_back(node);
1503  }
1504  if (nodes.size() <= tsp_size_) {
1505  return false;
1506  }
1507  has_long_enough_paths_ = true;
1508  // Randomly select break nodes (final nodes of a meta-node, after which
1509  // an arc is relaxed.
1510  absl::flat_hash_set<int64> breaks_set;
1511  // Always add base node to break nodes (diversification)
1512  breaks_set.insert(base_node);
1513  CHECK(!nodes.empty()); // Should have been caught earlier.
1514  while (breaks_set.size() < tsp_size_) {
1515  breaks_set.insert(nodes[absl::Uniform<int>(rand_, 0, nodes.size())]);
1516  }
1517  CHECK_EQ(breaks_set.size(), tsp_size_);
1518  // Setup break node indexing and internal meta-node cost (cost of partial
1519  // route starting at first node of the meta-node and ending at its last node);
1520  // this cost has to be added to the TSP matrix cost in order to respect the
1521  // triangle inequality.
1522  std::vector<int> breaks;
1523  std::vector<int64> meta_node_costs;
1524  int64 cost = 0;
1525  int64 node = StartNode(0);
1526  int64 node_path = Path(node);
1527  while (!IsPathEnd(node)) {
1528  int64 next = Next(node);
1529  if (gtl::ContainsKey(breaks_set, node)) {
1530  breaks.push_back(node);
1531  meta_node_costs.push_back(cost);
1532  cost = 0;
1533  } else {
1534  cost = CapAdd(cost, evaluator_(node, next, node_path));
1535  }
1536  node = next;
1537  }
1538  meta_node_costs[0] += cost;
1539  CHECK_EQ(breaks.size(), tsp_size_);
1540  // Setup TSP cost matrix
1541  CHECK_EQ(meta_node_costs.size(), tsp_size_);
1542  for (int i = 0; i < tsp_size_; ++i) {
1543  cost_[i][0] =
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) {
1547  cost_[i][j] =
1548  CapAdd(meta_node_costs[i],
1549  evaluator_(breaks[i], Next(breaks[j - 1]), node_path));
1550  }
1551  cost_[i][i] = 0;
1552  }
1553  // Solve TSP and inject solution in delta (only if it leads to a new solution)
1554  hamiltonian_path_solver_.ChangeCostMatrix(cost_);
1555  std::vector<PathNodeIndex> path;
1556  hamiltonian_path_solver_.TravelingSalesmanPath(&path);
1557  bool nochange = true;
1558  for (int i = 0; i < path.size() - 1; ++i) {
1559  if (path[i] != i) {
1560  nochange = false;
1561  break;
1562  }
1563  }
1564  if (nochange) {
1565  return false;
1566  }
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);
1570  }
1571  SetNext(breaks[path[tsp_size_ - 1]], OldNext(breaks[tsp_size_ - 1]),
1572  node_path);
1573  return true;
1574 }
1575 
1576 // ----- Lin Kernighan -----
1577 
1578 // For each variable in vars, stores the 'size' pairs(i,j) with the smallest
1579 // value according to evaluator, where i is the index of the variable in vars
1580 // and j is in the domain of the variable.
1581 // Note that the resulting pairs are sorted.
1582 // Works in O(size) per variable on average (same approach as qsort)
1583 
1585  public:
1587  const PathOperator& path_operator, int size);
1588  virtual ~NearestNeighbors() {}
1589  void Initialize();
1590  const std::vector<int>& Neighbors(int index) const;
1591 
1592  virtual std::string DebugString() const { return "NearestNeighbors"; }
1593 
1594  private:
1595  void ComputeNearest(int row);
1596 
1597  std::vector<std::vector<int>> neighbors_;
1598  Solver::IndexEvaluator3 evaluator_;
1599  const PathOperator& path_operator_;
1600  const int size_;
1601  bool initialized_;
1602 
1603  DISALLOW_COPY_AND_ASSIGN(NearestNeighbors);
1604 };
1605 
1607  const PathOperator& path_operator, int size)
1608  : evaluator_(std::move(evaluator)),
1609  path_operator_(path_operator),
1610  size_(size),
1611  initialized_(false) {}
1612 
1614  // TODO(user): recompute if node changes path ?
1615  if (!initialized_) {
1616  initialized_ = true;
1617  for (int i = 0; i < path_operator_.number_of_nexts(); ++i) {
1618  neighbors_.push_back(std::vector<int>());
1619  ComputeNearest(i);
1620  }
1621  }
1622 }
1623 
1624 const std::vector<int>& NearestNeighbors::Neighbors(int index) const {
1625  return neighbors_[index];
1626 }
1627 
1628 void NearestNeighbors::ComputeNearest(int row) {
1629  // Find size_ nearest neighbors for row of index 'row'.
1630  const int path = path_operator_.Path(row);
1631  const IntVar* var = path_operator_.Var(row);
1632  const int64 var_min = var->Min();
1633  const int var_size = var->Max() - var_min + 1;
1634  using ValuedIndex = std::pair<int64 /*value*/, int /*index*/>;
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);
1639  }
1640  if (var_size > size_) {
1641  std::nth_element(neighbors.begin(), neighbors.begin() + size_ - 1,
1642  neighbors.end());
1643  }
1644 
1645  // Setup global neighbor matrix for row row_index
1646  for (int i = 0; i < std::min(size_, var_size); ++i) {
1647  neighbors_[row].push_back(neighbors[i].second);
1648  }
1649  std::sort(neighbors_[row].begin(), neighbors_[row].end());
1650 }
1651 
1652 class LinKernighan : public PathOperator {
1653  public:
1654  LinKernighan(const std::vector<IntVar*>& vars,
1655  const std::vector<IntVar*>& secondary_vars,
1656  const Solver::IndexEvaluator3& evaluator, bool topt);
1657  ~LinKernighan() override;
1658  bool MakeNeighbor() override;
1659 
1660  std::string DebugString() const override { return "LinKernighan"; }
1661 
1662  private:
1663  void OnNodeInitialization() override;
1664 
1665  static const int kNeighbors;
1666 
1667  bool InFromOut(int64 in_i, int64 in_j, int64* out, int64* gain);
1668 
1669  Solver::IndexEvaluator3 const evaluator_;
1670  NearestNeighbors neighbors_;
1671  absl::flat_hash_set<int64> marked_;
1672  const bool topt_;
1673 };
1674 
1675 // While the accumulated local gain is positive, perform a 2opt or a 3opt move
1676 // followed by a series of 2opt moves. Return a neighbor for which the global
1677 // gain is positive.
1678 
1679 LinKernighan::LinKernighan(const std::vector<IntVar*>& vars,
1680  const std::vector<IntVar*>& secondary_vars,
1681  const Solver::IndexEvaluator3& evaluator, bool topt)
1682  : PathOperator(vars, secondary_vars, 1, true, false, nullptr),
1683  evaluator_(evaluator),
1684  neighbors_(evaluator, *this, kNeighbors),
1685  topt_(topt) {}
1686 
1688 
1689 void LinKernighan::OnNodeInitialization() { neighbors_.Initialize(); }
1690 
1692  marked_.clear();
1693  int64 node = BaseNode(0);
1694  int64 path = Path(node);
1695  int64 base = node;
1696  int64 next = Next(node);
1697  if (IsPathEnd(next)) return false;
1698  int64 out = -1;
1699  int64 gain = 0;
1700  marked_.insert(node);
1701  if (topt_) { // Try a 3opt first
1702  if (!InFromOut(node, next, &out, &gain)) return false;
1703  marked_.insert(next);
1704  marked_.insert(out);
1705  const int64 node1 = out;
1706  if (IsPathEnd(node1)) return false;
1707  const int64 next1 = Next(node1);
1708  if (IsPathEnd(next1)) return false;
1709  if (!InFromOut(node1, next1, &out, &gain)) return false;
1710  marked_.insert(next1);
1711  marked_.insert(out);
1712  if (!CheckChainValidity(out, node1, node) || !MoveChain(out, node1, node)) {
1713  return false;
1714  }
1715  const int64 next_out = Next(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;
1719  node = out;
1720  if (IsPathEnd(node)) return false;
1721  next = next_out;
1722  if (IsPathEnd(next)) return false;
1723  }
1724  // Try 2opts
1725  while (InFromOut(node, next, &out, &gain)) {
1726  marked_.insert(next);
1727  marked_.insert(out);
1728  int64 chain_last;
1729  if (!ReverseChain(node, out, &chain_last)) {
1730  return false;
1731  }
1732  int64 in_cost = evaluator_(base, chain_last, path);
1733  int64 out_cost = evaluator_(chain_last, out, path);
1734  if (CapAdd(CapSub(gain, in_cost), out_cost) > 0) {
1735  return true;
1736  }
1737  node = chain_last;
1738  if (IsPathEnd(node)) {
1739  return false;
1740  }
1741  next = out;
1742  if (IsPathEnd(next)) {
1743  return false;
1744  }
1745  }
1746  return false;
1747 }
1748 
1749 const int LinKernighan::kNeighbors = 5 + 1;
1750 
1751 bool LinKernighan::InFromOut(int64 in_i, int64 in_j, int64* out, int64* gain) {
1752  const std::vector<int>& nexts = neighbors_.Neighbors(in_j);
1753  int64 best_gain = kint64min;
1754  int64 path = Path(in_i);
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) {
1758  const int64 next = nexts[k];
1759  if (next != in_j) {
1760  int64 in_cost = evaluator_(in_j, next, path);
1761  int64 new_gain = CapSub(current_gain, in_cost);
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) {
1765  *out = next;
1766  best_gain = new_gain;
1767  }
1768  }
1769  }
1770  }
1771  *gain = best_gain;
1772  return (best_gain > kint64min);
1773 }
1774 
1775 // ----- Path-based Large Neighborhood Search -----
1776 
1777 // Breaks "number_of_chunks" chains of "chunk_size" arcs, and deactivate all
1778 // inactive nodes if "unactive_fragments" is true.
1779 // As a special case, if chunk_size=0, then we break full paths.
1780 
1781 class PathLns : public PathOperator {
1782  public:
1783  PathLns(const std::vector<IntVar*>& vars,
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,
1787  nullptr),
1788  number_of_chunks_(number_of_chunks),
1789  chunk_size_(chunk_size),
1790  unactive_fragments_(unactive_fragments) {
1791  CHECK_GE(chunk_size_, 0);
1792  }
1793  ~PathLns() override {}
1794  bool MakeNeighbor() override;
1795 
1796  std::string DebugString() const override { return "PathLns"; }
1797  bool HasFragments() const override { return true; }
1798 
1799  private:
1800  inline bool ChainsAreFullPaths() const { return chunk_size_ == 0; }
1801  void DeactivateChain(int64 node);
1802  void DeactivateUnactives();
1803 
1804  const int number_of_chunks_;
1805  const int chunk_size_;
1806  const bool unactive_fragments_;
1807 };
1808 
1810  if (ChainsAreFullPaths()) {
1811  // Reject the current position as a neighbor if any of its base node
1812  // isn't at the start of a path.
1813  // TODO(user): make this more efficient.
1814  for (int i = 0; i < number_of_chunks_; ++i) {
1815  if (BaseNode(i) != StartNode(i)) return false;
1816  }
1817  }
1818  for (int i = 0; i < number_of_chunks_; ++i) {
1819  DeactivateChain(BaseNode(i));
1820  }
1821  DeactivateUnactives();
1822  return true;
1823 }
1824 
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)) {
1829  Deactivate(current);
1830  if (!ignore_path_vars_) {
1831  Deactivate(number_of_nexts_ + current);
1832  }
1833  }
1834 }
1835 
1836 void PathLns::DeactivateUnactives() {
1837  if (unactive_fragments_) {
1838  for (int i = 0; i < Size(); ++i) {
1839  if (IsInactive(i)) {
1840  Deactivate(i);
1841  if (!ignore_path_vars_) {
1843  }
1844  }
1845  }
1846  }
1847 }
1848 
1849 // ----- Limit the number of neighborhoods explored -----
1850 
1852  public:
1854  : operator_(op), limit_(limit), next_neighborhood_calls_(0) {
1855  CHECK(op != nullptr);
1856  CHECK_GT(limit, 0);
1857  }
1858 
1859  void Start(const Assignment* assignment) override {
1860  next_neighborhood_calls_ = 0;
1861  operator_->Start(assignment);
1862  }
1863 
1864  bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override {
1865  if (next_neighborhood_calls_ >= limit_) {
1866  return false;
1867  }
1868  ++next_neighborhood_calls_;
1869  return operator_->MakeNextNeighbor(delta, deltadelta);
1870  }
1871 
1872  bool HoldsDelta() const override { return operator_->HoldsDelta(); }
1873 
1874  std::string DebugString() const override { return "NeighborhoodLimit"; }
1875 
1876  private:
1877  LocalSearchOperator* const operator_;
1878  const int64 limit_;
1879  int64 next_neighborhood_calls_;
1880 };
1881 
1883  LocalSearchOperator* const op, int64 limit) {
1884  return RevAlloc(new NeighborhoodLimit(op, limit));
1885 }
1886 
1887 // ----- Concatenation of operators -----
1888 
1889 namespace {
1890 class CompoundOperator : public LocalSearchOperator {
1891  public:
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; }
1900 
1901  std::string DebugString() const override {
1902  return operators_.empty()
1903  ? ""
1904  : operators_[operator_indices_[index_]]->DebugString();
1905  }
1906  const LocalSearchOperator* Self() const override {
1907  return operators_.empty() ? this
1908  : operators_[operator_indices_[index_]]->Self();
1909  }
1910 
1911  private:
1912  class OperatorComparator {
1913  public:
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);
1921  }
1922 
1923  private:
1924  int64 Evaluate(int operator_index) const {
1925  return evaluator_(active_operator_, operator_index);
1926  }
1927 
1928  std::function<int64(int, int)> evaluator_;
1929  const int active_operator_;
1930  };
1931 
1932  int64 index_;
1933  std::vector<LocalSearchOperator*> operators_;
1934  std::vector<int> operator_indices_;
1935  std::function<int64(int, int)> evaluator_;
1936  Bitset64<> started_;
1937  const Assignment* start_assignment_;
1938  bool has_fragments_;
1939 };
1940 
1941 CompoundOperator::CompoundOperator(std::vector<LocalSearchOperator*> operators,
1942  std::function<int64(int, int)> evaluator)
1943  : index_(0),
1944  operators_(std::move(operators)),
1945  evaluator_(std::move(evaluator)),
1946  started_(operators_.size()),
1947  start_assignment_(nullptr),
1948  has_fragments_(false) {
1949  operators_.erase(std::remove(operators_.begin(), operators_.end(), nullptr),
1950  operators_.end());
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;
1956  break;
1957  }
1958  }
1959 }
1960 
1961 void CompoundOperator::Reset() {
1962  for (LocalSearchOperator* const op : operators_) {
1963  op->Reset();
1964  }
1965 }
1966 
1967 void CompoundOperator::Start(const Assignment* assignment) {
1968  start_assignment_ = assignment;
1969  started_.ClearAll();
1970  if (!operators_.empty()) {
1971  OperatorComparator comparator(evaluator_, operator_indices_[index_]);
1972  std::sort(operator_indices_.begin(), operator_indices_.end(), comparator);
1973  index_ = 0;
1974  }
1975 }
1976 
1977 bool CompoundOperator::MakeNextNeighbor(Assignment* delta,
1978  Assignment* deltadelta) {
1979  if (!operators_.empty()) {
1980  do {
1981  // TODO(user): keep copy of delta in case MakeNextNeighbor
1982  // pollutes delta on a fail.
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);
1987  }
1988  if (!operators_[operator_index]->HoldsDelta()) {
1989  delta->Clear();
1990  }
1991  if (operators_[operator_index]->MakeNextNeighbor(delta, deltadelta)) {
1992  return true;
1993  }
1994  ++index_;
1995  delta->Clear();
1996  if (index_ == operators_.size()) {
1997  index_ = 0;
1998  }
1999  } while (index_ != 0);
2000  }
2001  return false;
2002 }
2003 
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;
2008 }
2009 
2010 int64 CompoundOperatorRestart(int active_index, int operator_index) {
2011  return 0;
2012 }
2013 } // namespace
2014 
2016  const std::vector<LocalSearchOperator*>& ops) {
2017  return ConcatenateOperators(ops, false);
2018 }
2019 
2021  const std::vector<LocalSearchOperator*>& ops, bool restart) {
2022  if (restart) {
2023  std::function<int64(int, int)> eval = CompoundOperatorRestart;
2024  return ConcatenateOperators(ops, eval);
2025  }
2026  const int size = ops.size();
2027  return ConcatenateOperators(ops, [size](int i, int j) {
2028  return CompoundOperatorNoRestart(size, i, j);
2029  });
2030 }
2031 
2033  const std::vector<LocalSearchOperator*>& ops,
2034  std::function<int64(int, int)> evaluator) {
2035  return RevAlloc(new CompoundOperator(ops, std::move(evaluator)));
2036 }
2037 
2038 namespace {
2039 class RandomCompoundOperator : public LocalSearchOperator {
2040  public:
2041  explicit RandomCompoundOperator(std::vector<LocalSearchOperator*> operators);
2042  RandomCompoundOperator(std::vector<LocalSearchOperator*> operators,
2043  int32 seed);
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; }
2049 
2050  std::string DebugString() const override { return "RandomCompoundOperator"; }
2051  // TODO(user): define Self method.
2052 
2053  private:
2054  std::mt19937 rand_;
2055  const std::vector<LocalSearchOperator*> operators_;
2056  bool has_fragments_;
2057 };
2058 
2059 void RandomCompoundOperator::Start(const Assignment* assignment) {
2060  for (LocalSearchOperator* const op : operators_) {
2061  op->Start(assignment);
2062  }
2063 }
2064 
2065 RandomCompoundOperator::RandomCompoundOperator(
2066  std::vector<LocalSearchOperator*> operators)
2067  : RandomCompoundOperator(std::move(operators), CpRandomSeed()) {}
2068 
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;
2075  break;
2076  }
2077  }
2078 }
2079 
2080 void RandomCompoundOperator::Reset() {
2081  for (LocalSearchOperator* const op : operators_) {
2082  op->Reset();
2083  }
2084 }
2085 
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()) {
2094  delta->Clear();
2095  }
2096  if (operators_[index]->MakeNextNeighbor(delta, deltadelta)) {
2097  return true;
2098  }
2099  delta->Clear();
2100  }
2101  return false;
2102 }
2103 } // namespace
2104 
2106  const std::vector<LocalSearchOperator*>& ops) {
2107  return RevAlloc(new RandomCompoundOperator(ops));
2108 }
2109 
2111  const std::vector<LocalSearchOperator*>& ops, int32 seed) {
2112  return RevAlloc(new RandomCompoundOperator(ops, seed));
2113 }
2114 
2115 namespace {
2116 class MultiArmedBanditCompoundOperator : public LocalSearchOperator {
2117  public:
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; }
2126 
2127  std::string DebugString() const override {
2128  return operators_.empty()
2129  ? ""
2130  : operators_[operator_indices_[index_]]->DebugString();
2131  }
2132  const LocalSearchOperator* Self() const override {
2133  return operators_.empty() ? this
2134  : operators_[operator_indices_[index_]]->Self();
2135  }
2136 
2137  private:
2138  double Score(int index);
2139  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_;
2147  int num_neighbors_;
2148  std::vector<double> num_neighbors_per_operator_;
2149  const bool maximize_;
2150  // Sets how much the objective improvement of previous accepted neighbors
2151  // influence the current average improvement. The formula is
2152  // avg_improvement +=
2153  // memory_coefficient * (current_improvement - avg_improvement).
2154  const double memory_coefficient_;
2155  // Sets how often we explore rarely used and unsuccessful in the past
2156  // operators. Operators are sorted by
2157  // avg_improvement_[i] + exploration_coefficient_ *
2158  // sqrt(2 * log(1 + num_neighbors_) / (1 + num_neighbors_per_operator_[i]));
2159  const double exploration_coefficient_;
2160 };
2161 
2162 MultiArmedBanditCompoundOperator::MultiArmedBanditCompoundOperator(
2163  std::vector<LocalSearchOperator*> operators, double memory_coefficient,
2164  double exploration_coefficient, bool maximize)
2165  : index_(0),
2166  operators_(std::move(operators)),
2167  started_(operators_.size()),
2168  start_assignment_(nullptr),
2169  has_fragments_(false),
2170  last_objective_(kint64max),
2171  num_neighbors_(0),
2172  maximize_(maximize),
2173  memory_coefficient_(memory_coefficient),
2174  exploration_coefficient_(exploration_coefficient) {
2175  DCHECK_GE(memory_coefficient_, 0);
2176  DCHECK_LE(memory_coefficient_, 1);
2177  DCHECK_GE(exploration_coefficient_, 0);
2178  operators_.erase(std::remove(operators_.begin(), operators_.end(), nullptr),
2179  operators_.end());
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;
2187  break;
2188  }
2189  }
2190 }
2191 
2192 void MultiArmedBanditCompoundOperator::Reset() {
2193  for (LocalSearchOperator* const op : operators_) {
2194  op->Reset();
2195  }
2196 }
2197 
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]));
2203 }
2204 
2205 void MultiArmedBanditCompoundOperator::Start(const Assignment* assignment) {
2206  start_assignment_ = assignment;
2207  started_.ClearAll();
2208  if (operators_.empty()) return;
2209 
2210  const double objective = assignment->ObjectiveValue();
2211 
2212  if (objective == last_objective_) return;
2213  // Skip a neighbor evaluation if last_objective_ hasn't been set yet.
2214  if (last_objective_ == kint64max) {
2215  last_objective_ = objective;
2216  return;
2217  }
2218 
2219  const double improvement =
2220  maximize_ ? objective - last_objective_ : last_objective_ - objective;
2221  if (improvement < 0) {
2222  return;
2223  }
2224  last_objective_ = objective;
2225  avg_improvement_[operator_indices_[index_]] +=
2226  memory_coefficient_ *
2227  (improvement - avg_improvement_[operator_indices_[index_]]);
2228 
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);
2235  });
2236 
2237  index_ = 0;
2238 }
2239 
2240 bool MultiArmedBanditCompoundOperator::MakeNextNeighbor(
2241  Assignment* delta, Assignment* deltadelta) {
2242  if (operators_.empty()) return false;
2243  do {
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);
2248  }
2249  if (!operators_[operator_index]->HoldsDelta()) {
2250  delta->Clear();
2251  }
2252  if (operators_[operator_index]->MakeNextNeighbor(delta, deltadelta)) {
2253  ++num_neighbors_;
2254  ++num_neighbors_per_operator_[operator_index];
2255  return true;
2256  }
2257  ++index_;
2258  delta->Clear();
2259  if (index_ == operators_.size()) {
2260  index_ = 0;
2261  }
2262  } while (index_ != 0);
2263  return false;
2264 }
2265 } // namespace
2266 
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));
2272 }
2273 
2274 // ----- Operator factory -----
2275 
2276 template <class T>
2278  Solver* solver, const std::vector<IntVar*>& vars,
2279  const std::vector<IntVar*>& secondary_vars,
2280  std::function<int(int64)> start_empty_path_class) {
2281  return solver->RevAlloc(
2282  new T(vars, secondary_vars, std::move(start_empty_path_class)));
2283 }
2284 
2285 #define MAKE_LOCAL_SEARCH_OPERATOR(OperatorClass) \
2286  template <> \
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))); \
2293  }
2294 
2299 MAKE_LOCAL_SEARCH_OPERATOR(MakeActiveOperator)
2300 MAKE_LOCAL_SEARCH_OPERATOR(MakeInactiveOperator)
2301 MAKE_LOCAL_SEARCH_OPERATOR(MakeChainInactiveOperator)
2302 MAKE_LOCAL_SEARCH_OPERATOR(SwapActiveOperator)
2303 MAKE_LOCAL_SEARCH_OPERATOR(ExtendedSwapActiveOperator)
2304 MAKE_LOCAL_SEARCH_OPERATOR(MakeActiveAndRelocate)
2305 MAKE_LOCAL_SEARCH_OPERATOR(RelocateAndMakeActiveOperator)
2306 MAKE_LOCAL_SEARCH_OPERATOR(RelocateAndMakeInactiveOperator)
2307 
2308 #undef MAKE_LOCAL_SEARCH_OPERATOR
2309 
2310 LocalSearchOperator* Solver::MakeOperator(const std::vector<IntVar*>& vars,
2312  return MakeOperator(vars, std::vector<IntVar*>(), op);
2313 }
2314 
2316  const std::vector<IntVar*>& vars,
2317  const std::vector<IntVar*>& secondary_vars,
2319  LocalSearchOperator* result = nullptr;
2320  switch (op) {
2321  case Solver::TWOOPT: {
2322  result = RevAlloc(new TwoOpt(vars, secondary_vars, nullptr));
2323  break;
2324  }
2325  case Solver::OROPT: {
2326  std::vector<LocalSearchOperator*> operators;
2327  for (int i = 1; i < 4; ++i) {
2328  operators.push_back(RevAlloc(
2329  new Relocate(vars, secondary_vars, absl::StrCat("OrOpt<", i, ">"),
2330  nullptr, i, true)));
2331  }
2332  result = ConcatenateOperators(operators);
2333  break;
2334  }
2335  case Solver::RELOCATE: {
2336  result = MakeLocalSearchOperator<Relocate>(this, vars, secondary_vars,
2337  nullptr);
2338  break;
2339  }
2340  case Solver::EXCHANGE: {
2341  result = MakeLocalSearchOperator<Exchange>(this, vars, secondary_vars,
2342  nullptr);
2343  break;
2344  }
2345  case Solver::CROSS: {
2346  result =
2347  MakeLocalSearchOperator<Cross>(this, vars, secondary_vars, nullptr);
2348  break;
2349  }
2350  case Solver::MAKEACTIVE: {
2351  result = MakeLocalSearchOperator<MakeActiveOperator>(
2352  this, vars, secondary_vars, nullptr);
2353  break;
2354  }
2355  case Solver::MAKEINACTIVE: {
2356  result = MakeLocalSearchOperator<MakeInactiveOperator>(
2357  this, vars, secondary_vars, nullptr);
2358  break;
2359  }
2361  result = MakeLocalSearchOperator<MakeChainInactiveOperator>(
2362  this, vars, secondary_vars, nullptr);
2363  break;
2364  }
2365  case Solver::SWAPACTIVE: {
2366  result = MakeLocalSearchOperator<SwapActiveOperator>(
2367  this, vars, secondary_vars, nullptr);
2368  break;
2369  }
2371  result = MakeLocalSearchOperator<ExtendedSwapActiveOperator>(
2372  this, vars, secondary_vars, nullptr);
2373  break;
2374  }
2375  case Solver::PATHLNS: {
2376  result = RevAlloc(new PathLns(vars, secondary_vars, 2, 3, false));
2377  break;
2378  }
2379  case Solver::FULLPATHLNS: {
2380  result = RevAlloc(new PathLns(vars, secondary_vars,
2381  /*number_of_chunks=*/1,
2382  /*chunk_size=*/0,
2383  /*unactive_fragments=*/true));
2384  break;
2385  }
2386  case Solver::UNACTIVELNS: {
2387  result = RevAlloc(new PathLns(vars, secondary_vars, 1, 6, true));
2388  break;
2389  }
2390  case Solver::INCREMENT: {
2391  if (secondary_vars.empty()) {
2392  result = RevAlloc(new IncrementValue(vars));
2393  } else {
2394  LOG(FATAL) << "Operator " << op
2395  << " does not support secondary variables";
2396  }
2397  break;
2398  }
2399  case Solver::DECREMENT: {
2400  if (secondary_vars.empty()) {
2401  result = RevAlloc(new DecrementValue(vars));
2402  } else {
2403  LOG(FATAL) << "Operator " << op
2404  << " does not support secondary variables";
2405  }
2406  break;
2407  }
2408  case Solver::SIMPLELNS: {
2409  if (secondary_vars.empty()) {
2410  result = RevAlloc(new SimpleLns(vars, 1));
2411  } else {
2412  LOG(FATAL) << "Operator " << op
2413  << " does not support secondary variables";
2414  }
2415  break;
2416  }
2417  default:
2418  LOG(FATAL) << "Unknown operator " << op;
2419  }
2420  return result;
2421 }
2422 
2424  const std::vector<IntVar*>& vars, Solver::IndexEvaluator3 evaluator,
2426  return MakeOperator(vars, std::vector<IntVar*>(), std::move(evaluator), op);
2427 }
2428 
2430  const std::vector<IntVar*>& vars,
2431  const std::vector<IntVar*>& secondary_vars,
2432  Solver::IndexEvaluator3 evaluator,
2434  LocalSearchOperator* result = nullptr;
2435  switch (op) {
2436  case Solver::LK: {
2437  std::vector<LocalSearchOperator*> operators;
2438  operators.push_back(RevAlloc(
2439  new LinKernighan(vars, secondary_vars, evaluator, /*topt=*/false)));
2440  operators.push_back(RevAlloc(
2441  new LinKernighan(vars, secondary_vars, evaluator, /*topt=*/true)));
2442  result = ConcatenateOperators(operators);
2443  break;
2444  }
2445  case Solver::TSPOPT: {
2446  result = RevAlloc(
2447  new TSPOpt(vars, secondary_vars, evaluator,
2448  absl::GetFlag(FLAGS_cp_local_search_tsp_opt_size)));
2449  break;
2450  }
2451  case Solver::TSPLNS: {
2452  result = RevAlloc(
2453  new TSPLns(vars, secondary_vars, evaluator,
2454  absl::GetFlag(FLAGS_cp_local_search_tsp_lns_size)));
2455  break;
2456  }
2457  default:
2458  LOG(FATAL) << "Unknown operator " << op;
2459  }
2460  return result;
2461 }
2462 
2463 namespace {
2464 // Classes for Local Search Operation used in Local Search filters.
2465 
2466 class SumOperation {
2467  public:
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); }
2472  int64 value() const { return value_; }
2473  void set_value(int64 new_value) { value_ = new_value; }
2474 
2475  private:
2476  int64 value_;
2477 };
2478 
2479 class ProductOperation {
2480  public:
2481  ProductOperation() : value_(1) {}
2482  void Init() { value_ = 1; }
2483  void Update(int64 update) { value_ *= update; }
2484  void Remove(int64 remove) {
2485  if (remove != 0) {
2486  value_ /= remove;
2487  }
2488  }
2489  int64 value() const { return value_; }
2490  void set_value(int64 new_value) { value_ = new_value; }
2491 
2492  private:
2493  int64 value_;
2494 };
2495 
2496 class MinOperation {
2497  public:
2498  void Init() { values_set_.clear(); }
2499  void Update(int64 update) { values_set_.insert(update); }
2500  void Remove(int64 remove) { values_set_.erase(remove); }
2501  int64 value() const {
2502  return (!values_set_.empty()) ? *values_set_.begin() : 0;
2503  }
2504  void set_value(int64 new_value) {}
2505 
2506  private:
2507  std::set<int64> values_set_;
2508 };
2509 
2510 class MaxOperation {
2511  public:
2512  void Init() { values_set_.clear(); }
2513  void Update(int64 update) { values_set_.insert(update); }
2514  void Remove(int64 remove) { values_set_.erase(remove); }
2515  int64 value() const {
2516  return (!values_set_.empty()) ? *values_set_.rbegin() : 0;
2517  }
2518  void set_value(int64 new_value) {}
2519 
2520  private:
2521  std::set<int64> values_set_;
2522 };
2523 
2524 // Always accepts deltas, cost 0.
2525 class AcceptFilter : public LocalSearchFilter {
2526  public:
2527  std::string DebugString() const override { return "AcceptFilter"; }
2528  bool Accept(const Assignment* delta, const Assignment* deltadelta,
2529  int64 obj_min, int64 obj_max) override {
2530  return true;
2531  }
2532  void Synchronize(const Assignment* assignment,
2533  const Assignment* delta) override {}
2534 };
2535 } // namespace
2536 
2538  return RevAlloc(new AcceptFilter());
2539 }
2540 
2541 namespace {
2542 // Never accepts deltas, cost 0.
2543 class RejectFilter : public LocalSearchFilter {
2544  public:
2545  std::string DebugString() const override { return "RejectFilter"; }
2546  bool Accept(const Assignment* delta, const Assignment* deltadelta,
2547  int64 obj_min, int64 obj_max) override {
2548  return false;
2549  }
2550  void Synchronize(const Assignment* assignment,
2551  const Assignment* delta) override {}
2552 };
2553 } // namespace
2554 
2556  return RevAlloc(new RejectFilter());
2557 }
2558 
2559 PathState::PathState(int num_nodes, std::vector<int> path_start,
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_)) // Arbitrary value.
2564 {
2565  DCHECK_EQ(path_start.size(), num_paths_);
2566  DCHECK_EQ(path_end.size(), num_paths_);
2567  for (int p = 0; p < num_paths_; ++p) {
2568  path_start_end_.push_back({path_start[p], path_end[p]});
2569  }
2570  // Initial state is all unperformed: paths go from start to end directly.
2571  committed_index_.assign(num_nodes_, -1);
2572  committed_nodes_.assign(2 * num_paths_, {-1, -1});
2573  chains_.assign(num_paths_ + 1, {-1, -1}); // Reserve 1 more for sentinel.
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;
2580 
2581  committed_nodes_[index] = {start_end.start, path};
2582  committed_nodes_[index + 1] = {start_end.end, path};
2583 
2584  chains_[path] = {index, index + 2};
2585  paths_[path] = {path, path + 1};
2586  }
2587  chains_[num_paths_] = {0, 0}; // Sentinel.
2588  // Nodes that are not starts or ends are loops.
2589  for (int node = 0; node < num_nodes_; ++node) {
2590  if (committed_index_[node] != -1) continue; // node is start or end.
2591  committed_index_[node] = committed_nodes_.size();
2592  committed_nodes_.push_back({node, -1});
2593  }
2594  path_has_changed_.assign(num_paths_, false);
2595 }
2596 
2598  const PathBounds bounds = paths_[path];
2599  return PathState::ChainRange(chains_.data() + bounds.begin_index,
2600  chains_.data() + bounds.end_index,
2601  committed_nodes_.data());
2602 }
2603 
2605  const PathBounds bounds = paths_[path];
2606  return PathState::NodeRange(chains_.data() + bounds.begin_index,
2607  chains_.data() + bounds.end_index,
2608  committed_nodes_.data());
2609 }
2610 
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();
2615  // For every path, find all its chains.
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;
2622  while (true) {
2623  // Look for smallest non-visited tail_index that is no smaller than
2624  // current_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) {
2630  selected_arc = i;
2631  selected_tail_index = tail_index;
2632  }
2633  }
2634  // If there is no such tail index, or more generally if the next chain
2635  // would be cut by end of path,
2636  // stack {current_index, end_index + 1} in chains_, and go to next path.
2637  // Otherwise, stack {current_index, tail_index+1} in chains_,
2638  // set current_index = head_index, set pair to visited.
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);
2642  break;
2643  } else {
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;
2649  }
2650  }
2651  const int new_chain_size = chains_.size();
2652  paths_[path] = {old_chain_size, new_chain_size};
2653  }
2654  chains_.emplace_back(0, 0); // Sentinel.
2655 }
2656 
2657 void PathState::MakeChainsFromChangedPathsAndArcsWithGenericAlgorithm() {
2658  // TRICKY: For each changed path, we want to generate a sequence of chains
2659  // that represents the path in the changed state.
2660  // First, notice that if we add a fake end->start arc for each changed path,
2661  // then all chains will be from the head of an arc to the tail of an arc.
2662  // A way to generate the changed chains and paths would be, for each path,
2663  // to start from a fake arc's head (the path start), go down the path until
2664  // the tail of an arc, and go to the next arc until we return on the fake arc,
2665  // enqueuing the [head, tail] chains as we go.
2666  // In turn, to do that, we need to know which arc to go to.
2667  // If we sort all heads and tails by index in two separate arrays,
2668  // the head_index and tail_index at the same rank are such that
2669  // [head_index, tail_index] is a chain. Moreover, the arc that must be visited
2670  // after head_index's arc is tail_index's arc.
2671 
2672  // Add a fake end->start arc for each path.
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]});
2677  }
2678 
2679  // Generate pairs (tail_index, arc) and (head_index, arc) for all arcs,
2680  // sort those pairs by index.
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};
2687  }
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());
2690  // Generate the map from arc to next arc in path.
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;
2694  }
2695 
2696  // Generate chains: for every changed path, start from its fake arc,
2697  // jump to next_arc_ until going back to fake arc,
2698  // enqueuing chains as we go.
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;
2703  do {
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};
2712  }
2713  chains_.emplace_back(0, 0); // Sentinel.
2714 }
2715 
2717  if (is_invalid_) return;
2718  // Filter out unchanged arcs from changed_arcs_,
2719  // translate changed arcs to changed arc indices.
2720  // Fill changed_paths_ while we hold node_path.
2721  DCHECK_EQ(chains_.size(), num_paths_ + 1); // One per path + sentinel.
2722  DCHECK(changed_paths_.empty());
2723  tail_head_indices_.clear();
2724  int num_changed_arcs = 0;
2725  for (const auto& arc : changed_arcs_) {
2726  int node, next;
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;
2731  if (next != node &&
2732  (next_index != node_index + 1 || node_path == -1)) { // New arc.
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);
2738  }
2739  } else if (node == next && node_path != -1) { // New loop.
2740  changed_arcs_[num_changed_arcs++] = {node, node};
2741  }
2742  }
2743  changed_arcs_.resize(num_changed_arcs);
2744 
2745  if (tail_head_indices_.size() + changed_paths_.size() <= 8) {
2746  MakeChainsFromChangedPathsAndArcsWithSelectionAlgorithm();
2747  } else {
2748  MakeChainsFromChangedPathsAndArcsWithGenericAlgorithm();
2749  }
2750 }
2751 
2753  DCHECK(!IsInvalid());
2754  if (committed_nodes_.size() < num_nodes_threshold_) {
2755  IncrementalCommit();
2756  } else {
2757  FullCommit();
2758  }
2759 }
2760 
2762  is_invalid_ = false;
2763  chains_.resize(num_paths_ + 1); // One per path + sentinel.
2764  for (const int path : changed_paths_) {
2765  paths_[path] = {path, path + 1};
2766  path_has_changed_[path] = false;
2767  }
2768  changed_paths_.clear();
2769  changed_arcs_.clear();
2770 }
2771 
2772 void PathState::CopyNewPathAtEndOfNodes(int path) {
2773  // Copy path's nodes, chain by chain.
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);
2781  }
2782  const int new_path_end_index = committed_nodes_.size();
2783  // Set new nodes' path member to path.
2784  for (int i = new_path_begin_index; i < new_path_end_index; ++i) {
2785  committed_nodes_[i].path = path;
2786  }
2787 }
2788 
2789 // TODO(user): Instead of copying paths at the end systematically,
2790 // reuse some of the memory when possible.
2791 void PathState::IncrementalCommit() {
2792  const int new_nodes_begin = committed_nodes_.size();
2793  for (const int path : ChangedPaths()) {
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};
2798  }
2799  // Re-index all copied nodes.
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;
2803  }
2804  // New loops stay in place: only change their path to -1,
2805  // committed_index_ does not change.
2806  for (const auto& arc : ChangedArcs()) {
2807  int node, next;
2808  std::tie(node, next) = arc;
2809  if (node != next) continue;
2810  const int index = committed_index_[node];
2811  committed_nodes_[index].path = -1;
2812  }
2813  // Committed part of the state is set up, erase incremental changes.
2814  Revert();
2815 }
2816 
2817 void PathState::FullCommit() {
2818  // Copy all paths at the end of committed_nodes_,
2819  // then remove all old committed_nodes_.
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};
2826  }
2827  committed_nodes_.erase(committed_nodes_.begin(),
2828  committed_nodes_.begin() + old_num_nodes);
2829 
2830  // Reindex path nodes, then loop nodes.
2831  constexpr int kUnindexed = -1;
2832  committed_index_.assign(num_nodes_, kUnindexed);
2833  int index = 0;
2834  for (const CommittedNode committed_node : committed_nodes_) {
2835  committed_index_[committed_node.node] = index++;
2836  }
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});
2841  }
2842  // Committed part of the state is set up, erase incremental changes.
2843  Revert();
2844 }
2845 
2846 namespace {
2847 
2848 class PathStateFilter : public LocalSearchFilter {
2849  public:
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 {
2856  return true;
2857  }
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;
2863 
2864  private:
2865  const std::unique_ptr<PathState> path_state_;
2866  // Map IntVar* index to node, offset by the min index in nexts.
2867  std::vector<int> variable_index_to_node_;
2868  int index_offset_;
2869  // Used only in Reset(), this is a member variable to avoid reallocation.
2870  std::vector<bool> node_is_assigned_;
2871 };
2872 
2873 PathStateFilter::PathStateFilter(std::unique_ptr<PathState> path_state,
2874  const std::vector<IntVar*>& nexts)
2875  : path_state_(std::move(path_state)) {
2876  {
2877  int min_index = std::numeric_limits<int>::max();
2878  int max_index = std::numeric_limits<int>::min();
2879  for (const IntVar* next : nexts) {
2880  const int index = next->index();
2881  min_index = std::min<int>(min_index, index);
2882  max_index = std::max<int>(max_index, index);
2883  }
2884  variable_index_to_node_.resize(max_index - min_index + 1, -1);
2885  index_offset_ = min_index;
2886  }
2887 
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;
2891  }
2892 }
2893 
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());
2905  } else {
2906  path_state_->Revert();
2907  path_state_->SetInvalid();
2908  break;
2909  }
2910  }
2911  path_state_->CutChains();
2912 }
2913 
2914 void PathStateFilter::Reset() {
2915  path_state_->Revert();
2916  // Set all paths of path state to empty start -> end paths,
2917  // and all nonstart/nonend nodes to node -> node loops.
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;
2927  }
2928  for (int node = 0; node < num_nodes; ++node) {
2929  if (!node_is_assigned_[node]) path_state_->ChangeNext(node, node);
2930  }
2931  path_state_->CutChains();
2932  path_state_->Commit();
2933 }
2934 
2935 // The solver does not guarantee that a given Commit() corresponds to
2936 // the previous Relax() (or that there has been a call to Relax()),
2937 // so we replay the full change call sequence.
2938 void PathStateFilter::Commit(const Assignment* assignment,
2939  const Assignment* delta) {
2940  path_state_->Revert();
2941  if (delta == nullptr || delta->Empty()) {
2942  Relax(assignment, nullptr);
2943  } else {
2944  Relax(delta, nullptr);
2945  }
2946  path_state_->Commit();
2947 }
2948 
2949 void PathStateFilter::Revert() { path_state_->Revert(); }
2950 
2951 } // namespace
2952 
2954  std::unique_ptr<PathState> path_state,
2955  const std::vector<IntVar*>& nexts) {
2956  PathStateFilter* filter = new PathStateFilter(std::move(path_state), nexts);
2957  return solver->RevAlloc(filter);
2958 }
2959 
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())) // 16 and 4 are arbitrary.
2972 {
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());
2977  const int maximum_rmq_exponent = MostSignificantBitPosition32(num_nodes);
2978  partial_demand_sums_rmq_.resize(maximum_rmq_exponent + 1);
2979  previous_nontrivial_index_.reserve(maximum_partial_demand_layer_size_);
2980  FullCommit();
2981 }
2982 
2984  if (path_state_->IsInvalid()) return true;
2985  for (const int path : path_state_->ChangedPaths()) {
2986  const Interval path_capacity = path_capacity_[path];
2987  if (path_capacity.min == kint64min && path_capacity.max == kint64max) {
2988  continue;
2989  }
2990  const int path_class = path_class_[path];
2991  // Loop invariant: capacity_used is nonempty and within path_capacity.
2992  Interval capacity_used = node_capacity_[path_state_->Start(path)];
2993  capacity_used = {std::max(capacity_used.min, path_capacity.min),
2994  std::min(capacity_used.max, path_capacity.max)};
2995  if (capacity_used.min > capacity_used.max) return false;
2996 
2997  for (const auto chain : path_state_->Chains(path)) {
2998  const int first_node = chain.First();
2999  const int last_node = chain.Last();
3000 
3001  const int first_index = index_[first_node];
3002  const int last_index = index_[last_node];
3003 
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];
3007  // Call the RMQ if the chain size is large enough;
3008  // the optimal value was found with the associated benchmark in tests,
3009  // in particular BM_UnaryDimensionChecker<ChangeSparsity::kSparse, *>.
3010  constexpr int kMinRangeSizeForRMQ = 4;
3011  if (last_index - first_index > kMinRangeSizeForRMQ &&
3012  path_class == chain_path_class &&
3013  SubpathOnlyHasTrivialNodes(first_index, last_index)) {
3014  // Compute feasible values of capacity_used that will not violate
3015  // path_capacity. This is done by considering the worst cases
3016  // using a range min/max query.
3017  const Interval min_max =
3018  GetMinMaxPartialDemandSum(first_index, last_index);
3019  const Interval prev_sum = partial_demand_sums_rmq_[0][first_index - 1];
3020  const Interval min_max_delta = {CapSub(min_max.min, prev_sum.min),
3021  CapSub(min_max.max, prev_sum.max)};
3022  capacity_used = {
3023  std::max(capacity_used.min,
3024  CapSub(path_capacity.min, min_max_delta.min)),
3025  std::min(capacity_used.max,
3026  CapSub(path_capacity.max, min_max_delta.max))};
3027  if (capacity_used.min > capacity_used.max) return false;
3028  // Move to last node's state, which is valid since we did not return.
3029  const Interval last_sum = partial_demand_sums_rmq_[0][last_index];
3030  capacity_used = {
3031  CapSub(CapAdd(capacity_used.min, last_sum.min), prev_sum.min),
3032  CapSub(CapAdd(capacity_used.max, last_sum.max), prev_sum.max)};
3033  } else {
3034  for (const int node : chain) {
3035  const Interval node_capacity = node_capacity_[node];
3036  capacity_used = {std::max(capacity_used.min, node_capacity.min),
3037  std::min(capacity_used.max, node_capacity.max)};
3038  if (capacity_used.min > capacity_used.max) return false;
3039  const Interval demand = demand_[path_class][node];
3040  capacity_used = {CapAdd(capacity_used.min, demand.min),
3041  CapAdd(capacity_used.max, demand.max)};
3042  capacity_used = {std::max(capacity_used.min, path_capacity.min),
3043  std::min(capacity_used.max, path_capacity.max)};
3044  }
3045  }
3046  }
3047  if (std::max(capacity_used.min, path_capacity.min) >
3048  std::min(capacity_used.max, path_capacity.max)) {
3049  return false;
3050  }
3051  }
3052  return true;
3053 }
3054 
3056  const int current_layer_size = partial_demand_sums_rmq_[0].size();
3057  int change_size = path_state_->ChangedPaths().size();
3058  for (const int path : path_state_->ChangedPaths()) {
3059  for (const auto chain : path_state_->Chains(path)) {
3060  change_size += chain.NumNodes();
3061  }
3062  }
3063  if (current_layer_size + change_size <= maximum_partial_demand_layer_size_) {
3064  IncrementalCommit();
3065  } else {
3066  FullCommit();
3067  }
3068 }
3069 
3070 void UnaryDimensionChecker::IncrementalCommit() {
3071  for (const int path : path_state_->ChangedPaths()) {
3072  const int begin_index = partial_demand_sums_rmq_[0].size();
3073  AppendPathDemandsToSums(path);
3074  UpdateRMQStructure(begin_index, partial_demand_sums_rmq_[0].size());
3075  }
3076 }
3077 
3078 void UnaryDimensionChecker::FullCommit() {
3079  // Clear all structures.
3080  previous_nontrivial_index_.clear();
3081  for (auto& sums : partial_demand_sums_rmq_) sums.clear();
3082  // Append all paths.
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());
3088  }
3089 }
3090 
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();
3096  // Value of partial_demand_sums_rmq_ at node_index-1 must be the sum
3097  // of all demands of nodes before node.
3098  partial_demand_sums_rmq_[0].push_back(demand_sum);
3099  previous_nontrivial_index_.push_back(-1);
3100  ++index;
3101 
3102  for (const int node : path_state_->Nodes(path)) {
3103  index_[node] = index;
3104  const Interval demand = demand_[path_class][node];
3105  demand_sum = {CapAdd(demand_sum.min, demand.min),
3106  CapAdd(demand_sum.max, demand.max)};
3107  partial_demand_sums_rmq_[0].push_back(demand_sum);
3108 
3109  const Interval node_capacity = node_capacity_[node];
3110  if (demand.min != demand.max || node_capacity.min != kint64min ||
3111  node_capacity.max != kint64max) {
3112  previous_nontrivial_index = index;
3113  }
3114  previous_nontrivial_index_.push_back(previous_nontrivial_index);
3115  ++index;
3116  }
3117 }
3118 
3119 void UnaryDimensionChecker::UpdateRMQStructure(int begin_index, int end_index) {
3120  // The max layer is the one used by
3121  // GetMinMaxPartialDemandSum(begin_index, end_index - 1).
3122  const int maximum_rmq_exponent =
3123  MostSignificantBitPosition32(end_index - 1 - begin_index);
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),
3131  std::max(i1.max, i2.max)};
3132  }
3133  std::copy(
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);
3137  }
3138 }
3139 
3140 // TODO(user): since this is called only when
3141 // last_node_index - first_node_index is large enough,
3142 // the lower layers of partial_demand_sums_rmq_ are never used.
3143 // For instance, if this is only called when the range size is > 4
3144 // and paths are <= 32 nodes long, then we only need layers 0, 2, 3, and 4.
3145 // To compare, on a 512 < #nodes <= 1024 problem, this uses layers in [0, 10].
3146 UnaryDimensionChecker::Interval
3147 UnaryDimensionChecker::GetMinMaxPartialDemandSum(int first_node_index,
3148  int last_node_index) const {
3149  DCHECK_LE(0, first_node_index);
3150  DCHECK_LT(first_node_index, last_node_index);
3151  DCHECK_LT(last_node_index, partial_demand_sums_rmq_[0].size());
3152  // Find largest window_size = 2^layer such that
3153  // first_node_index < last_node_index - window_size + 1.
3154  const int layer =
3155  MostSignificantBitPosition32(last_node_index - first_node_index);
3156  const int window_size = 1 << layer;
3157  // Classical range min/max query in O(1).
3158  const Interval i1 = partial_demand_sums_rmq_[layer][first_node_index];
3159  const Interval i2 =
3160  partial_demand_sums_rmq_[layer][last_node_index - window_size + 1];
3161  return {std::min(i1.min, i2.min), std::max(i1.max, i2.max)};
3162 }
3163 
3164 bool UnaryDimensionChecker::SubpathOnlyHasTrivialNodes(
3165  int first_node_index, int last_node_index) const {
3166  DCHECK_LE(0, first_node_index);
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];
3170 }
3171 
3172 namespace {
3173 
3174 class UnaryDimensionFilter : public LocalSearchFilter {
3175  public:
3176  std::string DebugString() const override { return "UnaryDimensionFilter"; }
3177  explicit UnaryDimensionFilter(std::unique_ptr<UnaryDimensionChecker> checker)
3178  : checker_(std::move(checker)) {}
3179 
3180  bool Accept(const Assignment* delta, const Assignment* deltadelta,
3181  int64 objective_min, int64 objective_max) override {
3182  return checker_->Check();
3183  }
3184 
3185  void Synchronize(const Assignment* assignment,
3186  const Assignment* delta) override {
3187  checker_->Commit();
3188  }
3189 
3190  private:
3191  std::unique_ptr<UnaryDimensionChecker> checker_;
3192 };
3193 
3194 } // namespace
3195 
3197  Solver* solver, std::unique_ptr<UnaryDimensionChecker> checker) {
3198  UnaryDimensionFilter* filter = new UnaryDimensionFilter(std::move(checker));
3199  return solver->RevAlloc(filter);
3200 }
3201 
3202 namespace {
3203 // ----- Variable domain filter -----
3204 // Rejects assignments to values outside the domain of variables
3205 
3206 class VariableDomainFilter : public LocalSearchFilter {
3207  public:
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 {}
3214 
3215  std::string DebugString() const override { return "VariableDomainFilter"; }
3216 };
3217 
3218 bool VariableDomainFilter::Accept(const Assignment* delta,
3219  const Assignment* deltadelta,
3220  int64 objective_min, int64 objective_max) {
3221  const Assignment::IntContainer& container = delta->IntVarContainer();
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())) {
3226  return false;
3227  }
3228  }
3229  return true;
3230 }
3231 } // namespace
3232 
3234  return RevAlloc(new VariableDomainFilter());
3235 }
3236 
3237 // ----- IntVarLocalSearchFilter -----
3238 
3239 const int IntVarLocalSearchFilter::kUnassigned = -1;
3240 
3242  const std::vector<IntVar*>& vars) {
3243  AddVars(vars);
3244 }
3245 
3246 void IntVarLocalSearchFilter::AddVars(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);
3252  }
3253  var_index_to_index_[index] = i + vars_.size();
3254  }
3255  vars_.insert(vars_.end(), vars.begin(), vars.end());
3256  values_.resize(vars_.size(), /*junk*/ 0);
3257  var_synced_.resize(vars_.size(), false);
3258  }
3259 }
3260 
3262 
3264  const Assignment* delta) {
3265  if (delta == nullptr || delta->Empty()) {
3266  var_synced_.assign(var_synced_.size(), false);
3267  SynchronizeOnAssignment(assignment);
3268  } else {
3270  }
3272 }
3273 
3275  const Assignment* assignment) {
3276  const Assignment::IntContainer& container = assignment->IntVarContainer();
3277  const int size = container.Size();
3278  for (int i = 0; i < size; ++i) {
3279  const IntVarElement& element = container.Element(i);
3280  IntVar* const var = element.Var();
3281  if (var != nullptr) {
3282  if (i < vars_.size() && vars_[i] == var) {
3283  values_[i] = element.Value();
3284  var_synced_[i] = true;
3285  } else {
3286  const int64 kUnallocated = -1;
3287  int64 index = kUnallocated;
3288  if (FindIndex(var, &index)) {
3289  values_[index] = element.Value();
3290  var_synced_[index] = true;
3291  }
3292  }
3293  }
3294  }
3295 }
3296 
3297 // ----- Sum Objective filter ------
3298 // Maintains the sum of costs of variables, where the subclass implements
3299 // CostOfSynchronizedVariable() and FillCostOfBoundDeltaVariable() to compute
3300 // the cost of a variable depending on its value.
3301 // An assignment is accepted by this filter if the total cost is allowed
3302 // depending on the relation defined by filter_enum:
3303 // - Solver::LE -> total_cost <= objective_max.
3304 // - Solver::GE -> total_cost >= objective_min.
3305 // - Solver::EQ -> the conjunction of LE and GE.
3306 namespace {
3307 class SumObjectiveFilter : public IntVarLocalSearchFilter {
3308  public:
3309  SumObjectiveFilter(const std::vector<IntVar*>& vars,
3310  Solver::LocalSearchFilterBound filter_enum)
3311  : IntVarLocalSearchFilter(vars),
3312  primary_vars_size_(vars.size()),
3313  synchronized_costs_(new int64[vars.size()]),
3314  delta_costs_(new int64[vars.size()]),
3315  filter_enum_(filter_enum),
3318  incremental_(false) {
3319  for (int i = 0; i < vars.size(); ++i) {
3320  synchronized_costs_[i] = 0;
3321  delta_costs_[i] = 0;
3322  }
3323  }
3324  ~SumObjectiveFilter() override {
3325  delete[] synchronized_costs_;
3326  delete[] delta_costs_;
3327  }
3328  bool Accept(const Assignment* delta, const Assignment* deltadelta,
3329  int64 objective_min, int64 objective_max) override {
3330  if (delta == nullptr) {
3331  return false;
3332  }
3333  if (deltadelta->Empty()) {
3334  if (incremental_) {
3335  for (int i = 0; i < primary_vars_size_; ++i) {
3337  }
3339  }
3340  incremental_ = false;
3342  CostOfChanges(delta, synchronized_costs_, false));
3343  } else {
3344  if (incremental_) {
3345  delta_sum_ =
3346  CapAdd(delta_sum_, CostOfChanges(deltadelta, delta_costs_, true));
3347  } else {
3349  CostOfChanges(delta, synchronized_costs_, true));
3350  }
3351  incremental_ = true;
3352  }
3353  switch (filter_enum_) {
3354  case Solver::LE: {
3355  return delta_sum_ <= objective_max;
3356  }
3357  case Solver::GE: {
3358  return delta_sum_ >= objective_min;
3359  }
3360  case Solver::EQ: {
3361  return objective_min <= delta_sum_ && delta_sum_ <= objective_max;
3362  }
3363  default: {
3364  LOG(ERROR) << "Unknown local search filter enum value";
3365  return false;
3366  }
3367  }
3368  }
3369  // If the variable is synchronized, returns its associated cost, otherwise
3370  // returns 0.
3371  virtual int64 CostOfSynchronizedVariable(int64 index) = 0;
3372  // If the variable is bound, fills new_cost with the cost associated to the
3373  // variable's valuation in container, and returns true. Otherwise, fills
3374  // new_cost with 0, and returns false.
3375  virtual bool FillCostOfBoundDeltaVariable(
3376  const Assignment::IntContainer& container, int index,
3377  int* container_index, int64* new_cost) = 0;
3378  bool IsIncremental() const override { return true; }
3379 
3380  std::string DebugString() const override { return "SumObjectiveFilter"; }
3381 
3382  int64 GetSynchronizedObjectiveValue() const override {
3383  return synchronized_sum_;
3384  }
3385  int64 GetAcceptedObjectiveValue() const override { return delta_sum_; }
3386 
3387  protected:
3395 
3396  private:
3397  void OnSynchronize(const Assignment* delta) override {
3398  synchronized_sum_ = 0;
3399  for (int i = 0; i < primary_vars_size_; ++i) {
3400  const int64 cost = CostOfSynchronizedVariable(i);
3402  delta_costs_[i] = cost;
3404  }
3406  incremental_ = false;
3407  }
3408  int64 CostOfChanges(const Assignment* changes, const int64* const old_costs,
3409  bool cache_delta_values) {
3410  int64 total_cost = 0;
3411  const Assignment::IntContainer& container = changes->IntVarContainer();
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();
3416  int64 index = -1;
3417  if (FindIndex(var, &index) && index < primary_vars_size_) {
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);
3422  }
3423  if (cache_delta_values) {
3424  delta_costs_[index] = new_cost;
3425  }
3426  }
3427  }
3428  return total_cost;
3429  }
3430 };
3431 
3432 class BinaryObjectiveFilter : public SumObjectiveFilter {
3433  public:
3434  BinaryObjectiveFilter(const std::vector<IntVar*>& vars,
3435  Solver::IndexEvaluator2 value_evaluator,
3436  Solver::LocalSearchFilterBound filter_enum)
3437  : SumObjectiveFilter(vars, filter_enum),
3438  value_evaluator_(std::move(value_evaluator)) {}
3439  ~BinaryObjectiveFilter() override {}
3440  int64 CostOfSynchronizedVariable(int64 index) override {
3442  ? value_evaluator_(index, IntVarLocalSearchFilter::Value(index))
3443  : 0;
3444  }
3445  bool FillCostOfBoundDeltaVariable(const Assignment::IntContainer& container,
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());
3451  return true;
3452  }
3453  const IntVar* var = element.Var();
3454  if (var->Bound()) {
3455  *new_cost = value_evaluator_(index, var->Min());
3456  return true;
3457  }
3458  *new_cost = 0;
3459  return false;
3460  }
3461 
3462  private:
3463  Solver::IndexEvaluator2 value_evaluator_;
3464 };
3465 
3466 class TernaryObjectiveFilter : public SumObjectiveFilter {
3467  public:
3468  TernaryObjectiveFilter(const std::vector<IntVar*>& vars,
3469  const std::vector<IntVar*>& secondary_vars,
3470  Solver::IndexEvaluator3 value_evaluator,
3471  Solver::LocalSearchFilterBound filter_enum)
3472  : SumObjectiveFilter(vars, filter_enum),
3473  secondary_vars_offset_(vars.size()),
3474  value_evaluator_(std::move(value_evaluator)) {
3475  IntVarLocalSearchFilter::AddVars(secondary_vars);
3477  }
3478  ~TernaryObjectiveFilter() override {}
3479  int64 CostOfSynchronizedVariable(int64 index) override {
3480  DCHECK_LT(index, secondary_vars_offset_);
3482  ? value_evaluator_(index, IntVarLocalSearchFilter::Value(index),
3484  index + secondary_vars_offset_))
3485  : 0;
3486  }
3487  bool FillCostOfBoundDeltaVariable(const Assignment::IntContainer& container,
3488  int index, int* container_index,
3489  int64* new_cost) override {
3490  DCHECK_LT(index, secondary_vars_offset_);
3491  *new_cost = 0LL;
3492  const IntVarElement& element = container.Element(*container_index);
3493  const IntVar* secondary_var =
3494  IntVarLocalSearchFilter::Var(index + secondary_vars_offset_);
3495  if (element.Activated()) {
3496  const int64 value = element.Value();
3497  int hint_index = *container_index + 1;
3498  if (hint_index < container.Size() &&
3499  secondary_var == container.Element(hint_index).Var()) {
3500  *new_cost = value_evaluator_(index, value,
3501  container.Element(hint_index).Value());
3502  *container_index = hint_index;
3503  } else {
3504  *new_cost = value_evaluator_(index, value,
3505  container.Element(secondary_var).Value());
3506  }
3507  return true;
3508  }
3509  const IntVar* var = element.Var();
3510  if (var->Bound() && secondary_var->Bound()) {
3511  *new_cost = value_evaluator_(index, var->Min(), secondary_var->Min());
3512  return true;
3513  }
3514  *new_cost = 0;
3515  return false;
3516  }
3517 
3518  private:
3519  int secondary_vars_offset_;
3520  Solver::IndexEvaluator3 value_evaluator_;
3521 };
3522 } // namespace
3523 
3525  const std::vector<IntVar*>& vars, Solver::IndexEvaluator2 values,
3526  Solver::LocalSearchFilterBound filter_enum) {
3527  return RevAlloc(
3528  new BinaryObjectiveFilter(vars, std::move(values), filter_enum));
3529 }
3530 
3532  const std::vector<IntVar*>& vars,
3533  const std::vector<IntVar*>& secondary_vars, Solver::IndexEvaluator3 values,
3534  Solver::LocalSearchFilterBound filter_enum) {
3535  return RevAlloc(new TernaryObjectiveFilter(vars, secondary_vars,
3536  std::move(values), filter_enum));
3537 }
3538 
3540  int64 initial_max) {
3541  DCHECK(state_is_valid_);
3542  DCHECK_LE(initial_min, 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);
3546 
3547  const int variable_index = variable_bounds_.size() - 1;
3548  return {this, variable_index};
3549 }
3550 
3551 void LocalSearchState::RelaxVariableBounds(int variable_index) {
3552  DCHECK(state_is_valid_);
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],
3557  variable_index);
3558  variable_bounds_[variable_index] = initial_variable_bounds_[variable_index];
3559  }
3560 }
3561 
3562 int64 LocalSearchState::VariableMin(int variable_index) const {
3563  DCHECK(state_is_valid_);
3564  DCHECK(0 <= variable_index && variable_index < variable_bounds_.size());
3565  return variable_bounds_[variable_index].min;
3566 }
3567 
3568 int64 LocalSearchState::VariableMax(int variable_index) const {
3569  DCHECK(state_is_valid_);
3570  DCHECK(0 <= variable_index && variable_index < variable_bounds_.size());
3571  return variable_bounds_[variable_index].max;
3572 }
3573 
3574 bool LocalSearchState::TightenVariableMin(int variable_index, int64 min_value) {
3575  DCHECK(state_is_valid_);
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;
3581  }
3582  bounds.min = std::max(bounds.min, min_value);
3583  return state_is_valid_;
3584 }
3585 
3586 bool LocalSearchState::TightenVariableMax(int variable_index, int64 max_value) {
3587  DCHECK(state_is_valid_);
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;
3593  }
3594  bounds.max = std::min(bounds.max, max_value);
3595  return state_is_valid_;
3596 }
3597 
3598 // TODO(user): When the class has more users, find a threshold ratio of
3599 // saved/total variables under which a sparse clear would be more efficient
3600 // for both Commit() and Revert().
3602  DCHECK(state_is_valid_);
3603  saved_variable_bounds_trail_.clear();
3604  variable_is_relaxed_.assign(variable_is_relaxed_.size(), false);
3605 }
3606 
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;
3611  }
3612  saved_variable_bounds_trail_.clear();
3613  variable_is_relaxed_.assign(variable_is_relaxed_.size(), false);
3614  state_is_valid_ = true;
3615 }
3616 
3617 // ----- LocalSearchProfiler -----
3618 
3620  public:
3622  std::string DebugString() const override { return "LocalSearchProfiler"; }
3623  void RestartSearch() override {
3624  operator_stats_.clear();
3625  filter_stats_.clear();
3626  }
3627  void ExitSearch() override {
3628  // Update times for current operator when the search ends.
3629  if (solver()->TopLevelSearch() == solver()->ActiveSearch()) {
3630  UpdateTime();
3631  }
3632  }
3633  LocalSearchStatistics ExportToLocalSearchStatistics() const {
3634  LocalSearchStatistics statistics_proto;
3635  std::vector<const LocalSearchOperator*> operators;
3636  for (const auto& stat : operator_stats_) {
3637  operators.push_back(stat.first);
3638  }
3639  std::sort(
3640  operators.begin(), operators.end(),
3641  [this](const LocalSearchOperator* op1, const LocalSearchOperator* op2) {
3642  return gtl::FindOrDie(operator_stats_, op1).neighbors >
3643  gtl::FindOrDie(operator_stats_, op2).neighbors;
3644  });
3645  for (const LocalSearchOperator* const op : operators) {
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(
3651  op->DebugString());
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);
3658  }
3659  std::vector<const LocalSearchFilter*> filters;
3660  for (const auto& stat : filter_stats_) {
3661  filters.push_back(stat.first);
3662  }
3663  std::sort(filters.begin(), filters.end(),
3664  [this](const LocalSearchFilter* filter1,
3665  const LocalSearchFilter* filter2) {
3666  return gtl::FindOrDie(filter_stats_, filter1).calls >
3667  gtl::FindOrDie(filter_stats_, filter2).calls;
3668  });
3669  for (const LocalSearchFilter* const filter : filters) {
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);
3679  }
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;
3686  }
3687  std::string PrintOverview() const {
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);
3692  max_name_size =
3693  std::max(max_name_size, stat.first->DebugString().length());
3694  }
3695  std::sort(
3696  operators.begin(), operators.end(),
3697  [this](const LocalSearchOperator* op1, const LocalSearchOperator* op2) {
3698  return gtl::FindOrDie(operator_stats_, op1).neighbors >
3699  gtl::FindOrDie(operator_stats_, op2).neighbors;
3700  });
3701  std::string overview = "Local search operator statistics:\n";
3702  absl::StrAppendFormat(&overview,
3703  "%*s | Neighbors | Filtered | Accepted | Time (s)\n",
3704  max_name_size, "");
3705  OperatorStats total_stats;
3706  for (const LocalSearchOperator* const op : operators) {
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,
3712  stats.seconds);
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;
3717  }
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);
3722  max_name_size = 0;
3723  std::vector<const LocalSearchFilter*> filters;
3724  for (const auto& stat : filter_stats_) {
3725  filters.push_back(stat.first);
3726  max_name_size =
3727  std::max(max_name_size, stat.first->DebugString().length());
3728  }
3729  std::sort(filters.begin(), filters.end(),
3730  [this](const LocalSearchFilter* filter1,
3731  const LocalSearchFilter* filter2) {
3732  return gtl::FindOrDie(filter_stats_, filter1).calls >
3733  gtl::FindOrDie(filter_stats_, filter2).calls;
3734  });
3735  absl::StrAppendFormat(&overview,
3736  "Local search filter statistics:\n%*s | Calls | "
3737  " Rejects | Time (s) "
3738  "| Rejects/s\n",
3739  max_name_size, "");
3740  FilterStats total_filter_stats;
3741  for (const LocalSearchFilter* const filter : filters) {
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;
3750  }
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);
3756  return overview;
3757  }
3758  void BeginOperatorStart() override {}
3759  void EndOperatorStart() override {}
3760  void BeginMakeNextNeighbor(const LocalSearchOperator* op) override {
3761  if (last_operator_ != op->Self()) {
3762  UpdateTime();
3763  last_operator_ = op->Self();
3764  }
3765  }
3766  void EndMakeNextNeighbor(const LocalSearchOperator* op, bool neighbor_found,
3767  const Assignment* delta,
3768  const Assignment* deltadelta) override {
3769  if (neighbor_found) {
3770  operator_stats_[op->Self()].neighbors++;
3771  }
3772  }
3773  void BeginFilterNeighbor(const LocalSearchOperator* op) override {}
3775  bool neighbor_found) override {
3776  if (neighbor_found) {
3777  operator_stats_[op->Self()].filtered_neighbors++;
3778  }
3779  }
3780  void BeginAcceptNeighbor(const LocalSearchOperator* op) override {}
3782  bool neighbor_found) override {
3783  if (neighbor_found) {
3784  operator_stats_[op->Self()].accepted_neighbors++;
3785  }
3786  }
3787  void BeginFiltering(const LocalSearchFilter* filter) override {
3788  filter_stats_[filter].calls++;
3789  filter_timer_.Start();
3790  }
3791  void EndFiltering(const LocalSearchFilter* filter, bool reject) override {
3792  filter_timer_.Stop();
3793  auto& stats = filter_stats_[filter];
3794  stats.seconds += filter_timer_.Get();
3795  if (reject) {
3796  stats.rejects++;
3797  }
3798  }
3799  void Install() override { SearchMonitor::Install(); }
3800 
3801  private:
3802  void UpdateTime() {
3803  if (last_operator_ != nullptr) {
3804  timer_.Stop();
3805  operator_stats_[last_operator_].seconds += timer_.Get();
3806  }
3807  timer_.Start();
3808  }
3809 
3810  struct OperatorStats {
3811  int64 neighbors = 0;
3812  int64 filtered_neighbors = 0;
3813  int64 accepted_neighbors = 0;
3814  double seconds = 0;
3815  };
3816 
3817  struct FilterStats {
3818  int64 calls = 0;
3819  int64 rejects = 0;
3820  double seconds = 0;
3821  };
3822  WallTimer timer_;
3823  WallTimer filter_timer_;
3824  const LocalSearchOperator* last_operator_ = nullptr;
3825  absl::flat_hash_map<const LocalSearchOperator*, OperatorStats>
3826  operator_stats_;
3827  absl::flat_hash_map<const LocalSearchFilter*, FilterStats> filter_stats_;
3828 };
3829 
3831  monitor->Install();
3832 }
3833 
3835  if (solver->IsLocalSearchProfilingEnabled()) {
3836  return new LocalSearchProfiler(solver);
3837  }
3838  return nullptr;
3839 }
3840 
3841 void DeleteLocalSearchProfiler(LocalSearchProfiler* monitor) { delete monitor; }
3842 
3843 std::string Solver::LocalSearchProfile() const {
3844  if (local_search_profiler_ != nullptr) {
3845  return local_search_profiler_->PrintOverview();
3846  }
3847  return "";
3848 }
3849 
3850 LocalSearchStatistics Solver::GetLocalSearchStatistics() const {
3851  if (local_search_profiler_ != nullptr) {
3852  return local_search_profiler_->ExportToLocalSearchStatistics();
3853  }
3854  return LocalSearchStatistics();
3855 }
3856 
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;
3867  }
3868  }
3869 }
3870 
3872  std::vector<LocalSearchFilter*> filters)
3873  : synchronized_value_(kint64min), accepted_value_(kint64min) {
3874  filter_events_.reserve(2 * filters.size());
3875  for (LocalSearchFilter* filter : filters) {
3876  filter_events_.push_back({filter, FilterEventType::kRelax});
3877  }
3878  for (LocalSearchFilter* filter : filters) {
3879  filter_events_.push_back({filter, FilterEventType::kAccept});
3880  }
3881  InitializeForcedEvents();
3882 }
3883 
3885  std::vector<FilterEvent> filter_events)
3886  : filter_events_(std::move(filter_events)),
3887  synchronized_value_(kint64min),
3888  accepted_value_(kint64min) {
3889  InitializeForcedEvents();
3890 }
3891 
3892 // Filters' Revert() must be called in the reverse order in which their
3893 // Relax() was called.
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();
3898  }
3899  last_event_called_ = -1;
3900 }
3901 
3902 // TODO(user): the behaviour of Accept relies on the initial order of
3903 // filters having at most one filter with negative objective values,
3904 // this could be fixed by having filters return their general bounds.
3906  const Assignment* delta,
3907  const Assignment* deltadelta,
3908  int64 objective_min,
3909  int64 objective_max) {
3910  Revert();
3911  accepted_value_ = 0;
3912  bool ok = true;
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: {
3919  if (monitor != nullptr) monitor->BeginFiltering(filter);
3920  const bool accept = filter->Accept(
3921  delta, deltadelta, CapSub(objective_min, accepted_value_),
3922  CapSub(objective_max, accepted_value_));
3923  ok &= accept;
3924  if (monitor != nullptr) monitor->EndFiltering(filter, !accept);
3925  if (ok) {
3926  accepted_value_ =
3927  CapAdd(accepted_value_, filter->GetAcceptedObjectiveValue());
3928  // TODO(user): handle objective min.
3929  ok = accepted_value_ <= objective_max;
3930  }
3931  break;
3932  }
3933  case FilterEventType::kRelax: {
3934  filter->Relax(delta, deltadelta);
3935  break;
3936  }
3937  default:
3938  LOG(FATAL) << "Unknown filter event type.";
3939  }
3940  // If the candidate is rejected, forced events must still be called.
3941  if (ok) {
3942  ++i;
3943  } else {
3944  i = next_forced_events_[i];
3945  }
3946  }
3947  return ok;
3948 }
3949 
3951  const Assignment* delta) {
3952  // If delta is nullptr or empty, then assignment may be a partial solution.
3953  // Send a signal to Relaxing filters to inform them,
3954  // so they can show the partial solution as a change from the empty solution.
3955  const bool reset_to_assignment = delta == nullptr || delta->Empty();
3956  // Relax in the forward direction.
3957  for (auto [filter, event_type] : filter_events_) {
3958  switch (event_type) {
3959  case FilterEventType::kAccept: {
3960  break;
3961  }
3962  case FilterEventType::kRelax: {
3963  if (reset_to_assignment) {
3964  filter->Reset();
3965  filter->Relax(assignment, nullptr);
3966  } else {
3967  filter->Relax(delta, nullptr);
3968  }
3969  break;
3970  }
3971  default:
3972  LOG(FATAL) << "Unknown filter event type.";
3973  }
3974  }
3975  // Synchronize/Commit backwards, so filters can read changes from their
3976  // dependencies before those are synchronized/committed.
3977  synchronized_value_ = 0;
3978  for (auto [filter, event_type] : ::gtl::reversed_view(filter_events_)) {
3979  switch (event_type) {
3980  case FilterEventType::kAccept: {
3981  filter->Synchronize(assignment, delta);
3982  synchronized_value_ = CapAdd(synchronized_value_,
3983  filter->GetSynchronizedObjectiveValue());
3984  break;
3985  }
3986  case FilterEventType::kRelax: {
3987  filter->Commit(assignment, delta);
3988  break;
3989  }
3990  default:
3991  LOG(FATAL) << "Unknown filter event type.";
3992  }
3993  }
3994 }
3995 
3996 // ----- Finds a neighbor of the assignment passed -----
3997 
3999  public:
4000  FindOneNeighbor(Assignment* const assignment, IntVar* objective,
4001  SolutionPool* const pool,
4002  LocalSearchOperator* const ls_operator,
4003  DecisionBuilder* const sub_decision_builder,
4004  const RegularLimit* const limit,
4005  LocalSearchFilterManager* filter_manager);
4006  ~FindOneNeighbor() override {}
4007  Decision* Next(Solver* const solver) override;
4008  std::string DebugString() const override { return "FindOneNeighbor"; }
4009 
4010  private:
4011  bool FilterAccept(Solver* solver, Assignment* delta, Assignment* deltadelta,
4012  int64 objective_min, int64 objective_max);
4013  void SynchronizeAll(Solver* solver, bool synchronize_filters = true);
4014 
4015  Assignment* const assignment_;
4016  IntVar* const objective_;
4017  std::unique_ptr<Assignment> reference_assignment_;
4018  SolutionPool* const pool_;
4019  LocalSearchOperator* const ls_operator_;
4020  DecisionBuilder* const sub_decision_builder_;
4021  RegularLimit* limit_;
4022  const RegularLimit* const original_limit_;
4023  bool neighbor_found_;
4024  LocalSearchFilterManager* const filter_manager_;
4025  int64 solutions_since_last_check_;
4026  int64 check_period_;
4027  Assignment last_checked_assignment_;
4028  bool has_checked_assignment_ = false;
4029 };
4030 
4031 // reference_assignment_ is used to keep track of the last assignment on which
4032 // operators were started, assignment_ corresponding to the last successful
4033 // neighbor.
4035  IntVar* objective, SolutionPool* const pool,
4036  LocalSearchOperator* const ls_operator,
4037  DecisionBuilder* const sub_decision_builder,
4038  const RegularLimit* const limit,
4039  LocalSearchFilterManager* filter_manager)
4040  : assignment_(assignment),
4041  objective_(objective),
4042  reference_assignment_(new Assignment(assignment_)),
4043  pool_(pool),
4044  ls_operator_(ls_operator),
4045  sub_decision_builder_(sub_decision_builder),
4046  limit_(nullptr),
4047  original_limit_(limit),
4048  neighbor_found_(false),
4049  filter_manager_(filter_manager),
4050  solutions_since_last_check_(0),
4051  check_period_(
4052  assignment_->solver()->parameters().check_solution_period()),
4053  last_checked_assignment_(assignment) {
4054  CHECK(nullptr != assignment);
4055  CHECK(nullptr != ls_operator);
4056 
4057  Solver* const solver = assignment_->solver();
4058  // If limit is nullptr, default limit is 1 solution
4059  if (nullptr == limit) {
4060  limit_ = solver->MakeSolutionsLimit(1);
4061  } else {
4062  limit_ = limit->MakeIdenticalClone();
4063  // TODO(user): Support skipping neighborhood checks for limits accepting
4064  // more than one solution (e.g. best accept). For now re-enabling systematic
4065  // checks.
4066  if (limit_->solutions() != 1) {
4067  VLOG(1) << "Disabling neighbor-check skipping outside of first accept.";
4068  check_period_ = 1;
4069  }
4070  }
4071  // TODO(user): Support skipping neighborhood checks with LNS (at least on
4072  // the non-LNS operators).
4073  if (ls_operator->HasFragments()) {
4074  VLOG(1) << "Disabling neighbor-check skipping for LNS.";
4075  check_period_ = 1;
4076  }
4077 
4078  if (!reference_assignment_->HasObjective()) {
4079  reference_assignment_->AddObjective(objective_);
4080  }
4081 }
4082 
4084  CHECK(nullptr != solver);
4085 
4086  if (original_limit_ != nullptr) {
4087  limit_->Copy(original_limit_);
4088  }
4089 
4090  if (!last_checked_assignment_.HasObjective()) {
4091  last_checked_assignment_.AddObjective(assignment_->Objective());
4092  }
4093 
4094  if (!neighbor_found_) {
4095  // Only called on the first call to Next(), reference_assignment_ has not
4096  // been synced with assignment_ yet
4097 
4098  // Keeping the code in case a performance problem forces us to
4099  // use the old code with a zero test on pool_.
4100  // reference_assignment_->CopyIntersection(assignment_);
4101  pool_->Initialize(assignment_);
4102  SynchronizeAll(solver, /*synchronize_filters*/ false);
4103  }
4104 
4105  {
4106  // Another assignment is needed to apply the delta
4107  Assignment* assignment_copy =
4108  solver->MakeAssignment(reference_assignment_.get());
4109  int counter = 0;
4110 
4111  DecisionBuilder* restore = solver->MakeRestoreAssignment(assignment_copy);
4112  if (sub_decision_builder_) {
4113  restore = solver->Compose(restore, sub_decision_builder_);
4114  }
4115  Assignment* delta = solver->MakeAssignment();
4116  Assignment* deltadelta = solver->MakeAssignment();
4117  while (true) {
4118  if (!ls_operator_->HoldsDelta()) {
4119  delta->Clear();
4120  }
4121  delta->ClearObjective();
4122  deltadelta->Clear();
4123  solver->TopPeriodicCheck();
4124  if (++counter >= absl::GetFlag(FLAGS_cp_local_search_sync_frequency) &&
4125  pool_->SyncNeeded(reference_assignment_.get())) {
4126  // TODO(user) : SyncNeed(assignment_) ?
4127  counter = 0;
4128  SynchronizeAll(solver);
4129  }
4130 
4131  bool has_neighbor = false;
4132  if (!limit_->Check()) {
4133  solver->GetLocalSearchMonitor()->BeginMakeNextNeighbor(ls_operator_);
4134  has_neighbor = ls_operator_->MakeNextNeighbor(delta, deltadelta);
4136  ls_operator_, has_neighbor, delta, deltadelta);
4137  }
4138 
4139  if (has_neighbor && !solver->IsUncheckedSolutionLimitReached()) {
4140  solver->neighbors_ += 1;
4141  // All filters must be called for incrementality reasons.
4142  // Empty deltas must also be sent to incremental filters; can be needed
4143  // to resync filters on non-incremental (empty) moves.
4144  // TODO(user): Don't call both if no filter is incremental and one
4145  // of them returned false.
4146  solver->GetLocalSearchMonitor()->BeginFilterNeighbor(ls_operator_);
4147  const bool mh_filter =
4148  AcceptDelta(solver->ParentSearch(), delta, deltadelta);
4149  int64 objective_min = kint64min;
4150  int64 objective_max = kint64max;
4151  if (objective_) {
4152  objective_min = objective_->Min();
4153  objective_max = objective_->Max();
4154  }
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());
4158  }
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();
4165  continue;
4166  }
4167  solver->filtered_neighbors_ += 1;
4168  if (delta->HasObjective()) {
4169  if (!assignment_copy->HasObjective()) {
4170  assignment_copy->AddObjective(delta->Objective());
4171  }
4172  if (!assignment_->HasObjective()) {
4173  assignment_->AddObjective(delta->Objective());
4174  last_checked_assignment_.AddObjective(delta->Objective());
4175  }
4176  }
4177  assignment_copy->CopyIntersection(reference_assignment_.get());
4178  assignment_copy->CopyIntersection(delta);
4179  solver->GetLocalSearchMonitor()->BeginAcceptNeighbor(ls_operator_);
4180  const bool check_solution = (solutions_since_last_check_ == 0) ||
4181  !solver->UseFastLocalSearch() ||
4182  // LNS deltas need to be restored
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;
4187  }
4188  const bool accept = !check_solution || solver->SolveAndCommit(restore);
4189  solver->GetLocalSearchMonitor()->EndAcceptNeighbor(ls_operator_,
4190  accept);
4191  if (accept) {
4192  solver->accepted_neighbors_ += 1;
4193  if (check_solution) {
4194  solver->SetSearchContext(solver->ParentSearch(),
4195  ls_operator_->DebugString());
4196  assignment_->Store();
4197  last_checked_assignment_.CopyIntersection(assignment_);
4198  neighbor_found_ = true;
4199  has_checked_assignment_ = true;
4200  return nullptr;
4201  }
4202  solver->SetSearchContext(solver->ActiveSearch(),
4203  ls_operator_->DebugString());
4204  assignment_->CopyIntersection(assignment_copy);
4205  assignment_->SetObjectiveValue(
4206  filter_manager_ ? filter_manager_->GetAcceptedObjectiveValue()
4207  : 0);
4208  // Advancing local search to the current solution without
4209  // checking.
4210  // TODO(user): support the case were limit_ accepts more than
4211  // one solution (e.g. best accept).
4212  AcceptUncheckedNeighbor(solver->ParentSearch());
4213  solver->IncrementUncheckedSolutionCounter();
4214  pool_->RegisterNewSolution(assignment_);
4215  SynchronizeAll(solver);
4216  // NOTE: SynchronizeAll() sets neighbor_found_ to false, force it
4217  // back to true when skipping checks.
4218  neighbor_found_ = true;
4219  } else {
4220  if (filter_manager_ != nullptr) filter_manager_->Revert();
4221  if (check_period_ > 1 && has_checked_assignment_) {
4222  // Filtering is not perfect, disabling fast local search and
4223  // resynchronizing with the last checked solution.
4224  // TODO(user): Restore state of local search operators to
4225  // make sure we are exploring neighbors in the same order. This can
4226  // affect the local optimum found.
4227  VLOG(1) << "Imperfect filtering detected, backtracking to last "
4228  "checked solution and checking all solutions.";
4229  check_period_ = 1;
4230  solutions_since_last_check_ = 0;
4231  pool_->RegisterNewSolution(&last_checked_assignment_);
4232  SynchronizeAll(solver);
4233  assignment_->CopyIntersection(&last_checked_assignment_);
4234  }
4235  }
4236  } else {
4237  if (neighbor_found_) {
4238  // In case the last checked assignment isn't the current one, restore
4239  // it to make sure the solver knows about it, especially if this is
4240  // the end of the search.
4241  // TODO(user): Compare assignments in addition to their cost.
4242  if (last_checked_assignment_.ObjectiveValue() !=
4243  assignment_->ObjectiveValue()) {
4244  // If restoring fails this means filtering is not perfect and the
4245  // solver will consider the last checked assignment.
4246  assignment_copy->CopyIntersection(assignment_);
4247  if (!solver->SolveAndCommit(restore)) solver->Fail();
4248  last_checked_assignment_.CopyIntersection(assignment_);
4249  has_checked_assignment_ = true;
4250  return nullptr;
4251  }
4252  AcceptNeighbor(solver->ParentSearch());
4253  // Keeping the code in case a performance problem forces us to
4254  // use the old code with a zero test on pool_.
4255  // reference_assignment_->CopyIntersection(assignment_);
4256  pool_->RegisterNewSolution(assignment_);
4257  SynchronizeAll(solver);
4258  } else {
4259  break;
4260  }
4261  }
4262  }
4263  }
4264  solver->Fail();
4265  return nullptr;
4266 }
4267 
4268 bool FindOneNeighbor::FilterAccept(Solver* solver, Assignment* delta,
4269  Assignment* deltadelta, int64 objective_min,
4270  int64 objective_max) {
4271  if (filter_manager_ == nullptr) return true;
4272  LocalSearchMonitor* const monitor = solver->GetLocalSearchMonitor();
4273  return filter_manager_->Accept(monitor, delta, deltadelta, objective_min,
4274  objective_max);
4275 }
4276 
4277 void FindOneNeighbor::SynchronizeAll(Solver* solver, bool synchronize_filters) {
4278  pool_->GetNextSolution(reference_assignment_.get());
4279  neighbor_found_ = false;
4280  limit_->Init();
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);
4285  }
4286  solver->GetLocalSearchMonitor()->EndOperatorStart();
4287 }
4288 
4289 // ---------- Local Search Phase Parameters ----------
4290 
4292  public:
4296  RegularLimit* const limit,
4298  : objective_(objective),
4299  solution_pool_(pool),
4300  ls_operator_(ls_operator),
4301  sub_decision_builder_(sub_decision_builder),
4302  limit_(limit),
4303  filter_manager_(filter_manager) {}
4305  std::string DebugString() const override {
4306  return "LocalSearchPhaseParameters";
4307  }
4308 
4309  IntVar* objective() const { return objective_; }
4310  SolutionPool* solution_pool() const { return solution_pool_; }
4311  LocalSearchOperator* ls_operator() const { return ls_operator_; }
4313  return sub_decision_builder_;
4314  }
4315  RegularLimit* limit() const { return limit_; }
4317  return filter_manager_;
4318  }
4319 
4320  private:
4321  IntVar* const objective_;
4322  SolutionPool* const solution_pool_;
4323  LocalSearchOperator* const ls_operator_;
4324  DecisionBuilder* const sub_decision_builder_;
4325  RegularLimit* const limit_;
4326  LocalSearchFilterManager* const filter_manager_;
4327 };
4328 
4330  IntVar* objective, LocalSearchOperator* const ls_operator,
4331  DecisionBuilder* const sub_decision_builder) {
4333  ls_operator, sub_decision_builder,
4334  nullptr, nullptr);
4335 }
4336 
4338  IntVar* objective, LocalSearchOperator* const ls_operator,
4339  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit) {
4341  ls_operator, sub_decision_builder,
4342  limit, nullptr);
4343 }
4344 
4346  IntVar* objective, LocalSearchOperator* const ls_operator,
4347  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
4348  LocalSearchFilterManager* filter_manager) {
4350  ls_operator, sub_decision_builder,
4351  limit, filter_manager);
4352 }
4353 
4355  IntVar* objective, SolutionPool* const pool,
4356  LocalSearchOperator* const ls_operator,
4357  DecisionBuilder* const sub_decision_builder) {
4358  return MakeLocalSearchPhaseParameters(objective, pool, ls_operator,
4359  sub_decision_builder, nullptr, nullptr);
4360 }
4361 
4363  IntVar* objective, SolutionPool* const pool,
4364  LocalSearchOperator* const ls_operator,
4365  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit) {
4366  return MakeLocalSearchPhaseParameters(objective, pool, ls_operator,
4367  sub_decision_builder, limit, nullptr);
4368 }
4369 
4371  IntVar* objective, SolutionPool* const pool,
4372  LocalSearchOperator* const ls_operator,
4373  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
4374  LocalSearchFilterManager* filter_manager) {
4375  return RevAlloc(new LocalSearchPhaseParameters(objective, pool, ls_operator,
4376  sub_decision_builder, limit,
4377  filter_manager));
4378 }
4379 
4380 namespace {
4381 // ----- NestedSolve decision wrapper -----
4382 
4383 // This decision calls a nested Solve on the given DecisionBuilder in its
4384 // left branch; does nothing in the left branch.
4385 // The state of the decision corresponds to the result of the nested Solve:
4386 // DECISION_PENDING - Nested Solve not called yet
4387 // DECISION_FAILED - Nested Solve failed
4388 // DECISION_FOUND - Nested Solve succeeded
4389 
4390 class NestedSolveDecision : public Decision {
4391  public:
4392  // This enum is used internally to tag states in the local search tree.
4393  enum StateType { DECISION_PENDING, DECISION_FAILED, DECISION_FOUND };
4394 
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_; }
4403 
4404  private:
4405  DecisionBuilder* const db_;
4406  bool restore_;
4407  std::vector<SearchMonitor*> monitors_;
4408  int state_;
4409 };
4410 
4411 NestedSolveDecision::NestedSolveDecision(
4412  DecisionBuilder* const db, bool restore,
4413  const std::vector<SearchMonitor*>& monitors)
4414  : db_(db),
4415  restore_(restore),
4416  monitors_(monitors),
4417  state_(DECISION_PENDING) {
4418  CHECK(nullptr != db);
4419 }
4420 
4421 NestedSolveDecision::NestedSolveDecision(DecisionBuilder* const db,
4422  bool restore)
4423  : db_(db), restore_(restore), state_(DECISION_PENDING) {
4424  CHECK(nullptr != db);
4425 }
4426 
4427 void NestedSolveDecision::Apply(Solver* const solver) {
4428  CHECK(nullptr != solver);
4429  if (restore_) {
4430  if (solver->Solve(db_, monitors_)) {
4431  solver->SaveAndSetValue(&state_, static_cast<int>(DECISION_FOUND));
4432  } else {
4433  solver->SaveAndSetValue(&state_, static_cast<int>(DECISION_FAILED));
4434  }
4435  } else {
4436  if (solver->SolveAndCommit(db_, monitors_)) {
4437  solver->SaveAndSetValue(&state_, static_cast<int>(DECISION_FOUND));
4438  } else {
4439  solver->SaveAndSetValue(&state_, static_cast<int>(DECISION_FAILED));
4440  }
4441  }
4442 }
4443 
4444 void NestedSolveDecision::Refute(Solver* const solver) {}
4445 
4446 // ----- Local search decision builder -----
4447 
4448 // Given a first solution (resulting from either an initial assignment or the
4449 // result of a decision builder), it searches for neighbors using a local
4450 // search operator. The first solution corresponds to the first leaf of the
4451 // search.
4452 // The local search applies to the variables contained either in the assignment
4453 // or the vector of variables passed.
4454 
4455 class LocalSearch : public DecisionBuilder {
4456  public:
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);
4462  // TODO(user): find a way to not have to pass vars here: redundant with
4463  // variables in operators
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;
4487 
4488  protected:
4489  void PushFirstSolutionDecision(DecisionBuilder* first_solution);
4490  void PushLocalSearchDecision();
4491 
4492  private:
4493  Assignment* assignment_;
4494  IntVar* const objective_ = nullptr;
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_;
4503  bool has_started_;
4504 };
4505 
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),
4513  objective_(objective),
4514  pool_(pool),
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),
4519  limit_(limit),
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();
4530 }
4531 
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),
4540  objective_(objective),
4541  pool_(pool),
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),
4546  limit_(limit),
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();
4557 }
4558 
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),
4567  objective_(objective),
4568  pool_(pool),
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),
4573  limit_(limit),
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();
4584 }
4585 
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),
4594  objective_(objective),
4595  pool_(pool),
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),
4600  limit_(limit),
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();
4611 }
4612 
4613 LocalSearch::~LocalSearch() {}
4614 
4615 // Model Visitor support.
4616 void LocalSearch::Accept(ModelVisitor* const visitor) const {
4617  DCHECK(assignment_ != nullptr);
4618  visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);
4619  // We collect decision variables from the assignment.
4620  const std::vector<IntVarElement>& elements =
4621  assignment_->IntVarContainer().elements();
4622  if (!elements.empty()) {
4623  std::vector<IntVar*> vars;
4624  for (const IntVarElement& elem : elements) {
4625  vars.push_back(elem.Var());
4626  }
4627  visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
4628  vars);
4629  }
4630  const std::vector<IntervalVarElement>& interval_elements =
4631  assignment_->IntervalVarContainer().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());
4636  }
4637  visitor->VisitIntervalArrayArgument(ModelVisitor::kIntervalsArgument,
4638  interval_vars);
4639  }
4640  visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);
4641 }
4642 
4643 // This is equivalent to a multi-restart decision builder
4644 // TODO(user): abstract this from the local search part
4645 // TODO(user): handle the case where the tree depth is not enough to hold
4646 // all solutions.
4647 
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) {
4655  solver->Fail();
4656  }
4657  NestedSolveDecision* decision = nested_decisions_[nested_decision_index_];
4658  const int state = decision->state();
4659  switch (state) {
4660  case NestedSolveDecision::DECISION_FAILED: {
4661  // A local optimum has been reached. The search will continue only if we
4662  // accept up-hill moves (due to metaheuristics). In this case we need to
4663  // reset neighborhood optimal routes.
4664  ls_operator_->Reset();
4665  if (!LocalOptimumReached(solver->ActiveSearch())) {
4666  nested_decision_index_ = -1; // Stop the search
4667  }
4668  solver->Fail();
4669  return nullptr;
4670  }
4671  case NestedSolveDecision::DECISION_PENDING: {
4672  // TODO(user): Find a way to make this balancing invisible to the
4673  // user (no increase in branch or fail counts for instance).
4674  const int32 kLocalSearchBalancedTreeDepth = 32;
4675  const int depth = solver->SearchDepth();
4676  if (depth < kLocalSearchBalancedTreeDepth) {
4677  return solver->balancing_decision();
4678  }
4679  if (depth > kLocalSearchBalancedTreeDepth) {
4680  solver->Fail();
4681  }
4682  return decision;
4683  }
4684  case NestedSolveDecision::DECISION_FOUND: {
4685  // Next time go to next decision
4686  if (nested_decision_index_ + 1 < nested_decisions_.size()) {
4687  ++nested_decision_index_;
4688  }
4689  return nullptr;
4690  }
4691  default: {
4692  LOG(ERROR) << "Unknown local search state";
4693  return nullptr;
4694  }
4695  }
4696  return nullptr;
4697 }
4698 
4699 namespace {
4700 class SynchronizeFiltersDecisionBuilder : public DecisionBuilder {
4701  public:
4702  SynchronizeFiltersDecisionBuilder(Assignment* assignment,
4703  LocalSearchFilterManager* filter_manager)
4704  : assignment_(assignment), filter_manager_(filter_manager) {}
4705 
4706  Decision* Next(Solver* const solver) override {
4707  if (filter_manager_ != nullptr) {
4708  filter_manager_->Synchronize(assignment_, nullptr);
4709  }
4710  return nullptr;
4711  }
4712 
4713  private:
4714  Assignment* const assignment_;
4715  LocalSearchFilterManager* const filter_manager_;
4716 };
4717 } // namespace
4718 
4719 void LocalSearch::PushFirstSolutionDecision(DecisionBuilder* first_solution) {
4720  CHECK(first_solution);
4721  Solver* const solver = assignment_->solver();
4722  DecisionBuilder* store = solver->MakeStoreAssignment(assignment_);
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)));
4731 }
4732 
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)));
4740 }
4741 
4742 class DefaultSolutionPool : public SolutionPool {
4743  public:
4744  DefaultSolutionPool() {}
4745 
4746  ~DefaultSolutionPool() override {}
4747 
4748  void Initialize(Assignment* const assignment) override {
4749  reference_assignment_ = absl::make_unique<Assignment>(assignment);
4750  }
4751 
4752  void RegisterNewSolution(Assignment* const assignment) override {
4753  reference_assignment_->CopyIntersection(assignment);
4754  }
4755 
4756  void GetNextSolution(Assignment* const assignment) override {
4757  assignment->CopyIntersection(reference_assignment_.get());
4758  }
4759 
4760  bool SyncNeeded(Assignment* const local_assignment) override { return false; }
4761 
4762  std::string DebugString() const override { return "DefaultSolutionPool"; }
4763 
4764  private:
4765  std::unique_ptr<Assignment> reference_assignment_;
4766 };
4767 } // namespace
4768 
4770  return RevAlloc(new DefaultSolutionPool());
4771 }
4772 
4775  return RevAlloc(new LocalSearch(
4776  assignment, parameters->objective(), parameters->solution_pool(),
4777  parameters->ls_operator(), parameters->sub_decision_builder(),
4778  parameters->limit(), parameters->filter_manager()));
4779 }
4780 
4782  const std::vector<IntVar*>& vars, DecisionBuilder* first_solution,
4784  return RevAlloc(new LocalSearch(
4785  vars, parameters->objective(), parameters->solution_pool(),
4786  first_solution, parameters->ls_operator(),
4787  parameters->sub_decision_builder(), parameters->limit(),
4788  parameters->filter_manager()));
4789 }
4790 
4792  const std::vector<IntVar*>& vars, DecisionBuilder* first_solution,
4793  DecisionBuilder* first_solution_sub_decision_builder,
4795  return RevAlloc(new LocalSearch(
4796  vars, parameters->objective(), parameters->solution_pool(),
4797  first_solution, first_solution_sub_decision_builder,
4798  parameters->ls_operator(), parameters->sub_decision_builder(),
4799  parameters->limit(), parameters->filter_manager()));
4800 }
4801 
4803  const std::vector<SequenceVar*>& vars, DecisionBuilder* first_solution,
4805  return RevAlloc(new LocalSearch(
4806  vars, parameters->objective(), parameters->solution_pool(),
4807  first_solution, parameters->ls_operator(),
4808  parameters->sub_decision_builder(), parameters->limit(),
4809  parameters->filter_manager()));
4810 }
4811 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define VLOG(verboselevel)
Definition: base/logging.h:978
void Start()
Definition: timer.h:31
void Stop()
Definition: timer.h:39
double Get() const
Definition: timer.h:45
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
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
AssignmentContainer< IntVar, IntVarElement > IntContainer
const IntervalContainer & IntervalVarContainer() const
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)
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)
Definition: local_search.cc:99
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
A BaseObject is the root of all reversibly allocated objects.
virtual std::string DebugString() const
void Set(IndexType i)
Definition: bitset.h:491
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.
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
ExtendedSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
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
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
void Synchronize(const Assignment *assignment, const Assignment *delta) override
This method should not be overridden.
IntVarLocalSearchFilter(const std::vector< IntVar * > &vars)
void AddVars(const std::vector< IntVar * > &vars)
Add variables to "track" to the filter.
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.
Definition: local_search.cc:74
virtual bool MakeOneNeighbor()
Creates a new neighbor.
Definition: local_search.cc:95
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)
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 const LocalSearchOperator * Self() const
virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0
virtual void Start(const Assignment *assignment)=0
LocalSearchFilterManager *const filter_manager() const
LocalSearchPhaseParameters(IntVar *objective, SolutionPool *const pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, RegularLimit *const limit, LocalSearchFilterManager *filter_manager)
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.
void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
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)
std::string DebugString() const 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 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...
MakeChainInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
MakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
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
NeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) 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 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...
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),...
bool ReverseChain(int64 before_chain, int64 after_chain, int64 *chain_last)
Reverses the chain starting after before_chain and ending before after_chain.
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.
void ResetPosition()
Reset the position of the operator to its position when Start() was last called; this can be used to ...
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.
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
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.
Definition: search.cc:3988
void Init() override
This method is called when the search limit is initialized.
Definition: search.cc:4009
void Copy(const SearchLimit *const limit) override
Copy a limit.
Definition: search.cc:3969
RegularLimit * MakeIdenticalClone() const
Definition: search.cc:3982
RelocateAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
RelocateAndMakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
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.
Definition: search.cc:4105
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.
Definition: search.cc:552
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(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const 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
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)
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.
Block * next
SatParameters parameters
SharedBoundsManager * bounds
const std::string name
int64 value
IntVar * var
Definition: expr_array.cc:1858
const int64 limit_
int int32
static const int64 kint64max
int64_t int64
static const int64 kint64min
ABSL_FLAG(int, cp_local_search_sync_frequency, 16, "Frequency of checks for better solutions in the solution pool.")
int64 synchronized_sum_
Solver::LocalSearchFilterBound filter_enum_
int64 delta_sum_
int64 *const delta_costs_
const int primary_vars_size_
#define MAKE_LOCAL_SEARCH_OPERATOR(OperatorClass)
bool incremental_
int64 *const synchronized_costs_
const int ERROR
Definition: log_severity.h:32
const int FATAL
Definition: log_severity.h:32
RowIndex row
Definition: markowitz.cc:175
Definition: cleanup.h:22
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:176
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)
Definition: bitset.h:273
LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)
int index
Definition: pack.cc:508
int64 demand
Definition: resource.cc:123
int64 delta
Definition: resource.cc:1684
int64 cost
std::function< int64(int64, int64)> evaluator_
Definition: search.cc:1361
const bool maximize_
Definition: search.cc:2499
IntVar *const objective_
Definition: search.cc:2951