OR-Tools  8.1
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
operations_research::UnaryDimensionChecker::Interval
Definition: constraint_solveri.h:3381
operations_research::IntVar
The class IntVar is a subset of IntExpr.
Definition: constraint_solver.h:3992
operations_research::TSPOpt::TSPOpt
TSPOpt(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)
Definition: local_search.cc:1393
operations_research::TSPLns::MakeOneNeighbor
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
Definition: local_search.cc:1487
operations_research::Solver::MakeAssignment
Assignment * MakeAssignment()
This method creates an empty assignment.
Definition: constraint_solver/assignment.cc:1037
operations_research::AssignmentContainer::Size
int Size() const
Definition: constraint_solver.h:4952
operations_research::LocalSearchMonitor::BeginAcceptNeighbor
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
operations_research::RegularLimit::Check
bool Check() override
This method is called to check the status of the limit.
Definition: search.cc:3988
operations_research::Solver::MakeRandomLnsOperator
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 ...
Definition: local_search.cc:191
operations_research::LocalSearchPhaseParameters
Definition: local_search.cc:4291
var
IntVar * var
Definition: expr_array.cc:1858
operations_research::IntVarLocalSearchFilter::IsVarSynced
bool IsVarSynced(int index) const
Definition: constraint_solveri.h:1837
operations_research::Solver::parameters
ConstraintSolverParameters parameters() const
Stored Parameters.
Definition: constraint_solver.h:763
operations_research::Solver::IndexEvaluator2
std::function< int64(int64, int64)> IndexEvaluator2
Definition: constraint_solver.h:739
operations_research::PathState::ChangedArcs
const std::vector< std::pair< int, int > > & ChangedArcs() const
Definition: constraint_solveri.h:3087
operations_research::BaseLns::AppendToFragment
void AppendToFragment(int index)
Definition: local_search.cc:119
operations_research::Solver::SolveAndCommit
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...
Definition: constraint_solver.cc:2405
operations_research::PathState::IsInvalid
bool IsInvalid() const
Definition: constraint_solveri.h:3118
operations_research::RegularLimit::solutions
int64 solutions() const
Definition: constraint_solver.h:4298
operations_research::Solver::GE
@ GE
Move is accepted when the current objective value >= objective.Min.
Definition: constraint_solver.h:597
operations_research::LocalSearchPhaseParameters::filter_manager
LocalSearchFilterManager *const filter_manager() const
Definition: local_search.cc:4316
operations_research::LocalSearchProfiler::EndFilterNeighbor
void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
Definition: local_search.cc:3774
operations_research::PathOperator::Next
int64 Next(int64 node) const
Returns the node after node in the current delta.
Definition: constraint_solveri.h:1346
operations_research::NeighborhoodLimit
Definition: local_search.cc:1851
operations_research::PathLns
Definition: local_search.cc:1781
operations_research::CpRandomSeed
int64 CpRandomSeed()
Definition: constraint_solver.h:163
min
int64 min
Definition: alldiff_cst.cc:138
integral_types.h
DCHECK_LT
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
map_util.h
operations_research::PathLns::DebugString
std::string DebugString() const override
Definition: local_search.cc:1796
VLOG
#define VLOG(verboselevel)
Definition: base/logging.h:978
operations_research::NeighborhoodLimit::MakeNextNeighbor
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Definition: local_search.cc:1864
operations_research::PathOperator::ignore_path_vars_
const bool ignore_path_vars_
Definition: constraint_solveri.h:1561
operations_research::CapSub
int64 CapSub(int64 x, int64 y)
Definition: saturated_arithmetic.h:154
operations_research::PathState::Chains
ChainRange Chains(int path) const
Definition: local_search.cc:2597
operations_research::BaseInactiveNodeToPathOperator::MakeOneNeighbor
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
Definition: local_search.cc:1106
operations_research::RelocateAndMakeInactiveOperator::DebugString
std::string DebugString() const override
Definition: local_search.cc:1258
operations_research::BaseLns::InitFragments
virtual void InitFragments()
Definition: local_search.cc:117
max
int64 max
Definition: alldiff_cst.cc:139
operations_research::Assignment::IntVarContainer
const IntContainer & IntVarContainer() const
Definition: constraint_solver.h:5184
operations_research::MakeChainInactiveOperator::OnSamePathAsPreviousBase
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...
Definition: local_search.cc:1289
limit_
const int64 limit_
Definition: expressions.cc:5447
operations_research::PathOperator::StartNode
int64 StartNode(int i) const
Returns the start node of the ith base node.
Definition: constraint_solveri.h:1402
operations_research::PathOperator::start_to_path_
std::vector< int64 > start_to_path_
Definition: constraint_solveri.h:1564
operations_research::IntVarElement::Value
int64 Value() const
Definition: constraint_solver.h:4670
operations_research::BaseLns::FragmentSize
int FragmentSize() const
Definition: local_search.cc:125
operations_research::LinKernighan::LinKernighan
LinKernighan(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)
Definition: local_search.cc:1679
operations_research::TSPLns
Definition: local_search.cc:1443
operations_research::RegularLimit::Copy
void Copy(const SearchLimit *const limit) override
Copy a limit.
Definition: search.cc:3969
operations_research::BaseInactiveNodeToPathOperator::GetInactiveNode
int64 GetInactiveNode() const
Definition: local_search.cc:1088
operations_research::SolutionPool::GetNextSolution
virtual void GetNextSolution(Assignment *const assignment)=0
This method is called when the local search starts a new neighborhood to initialize the default assig...
operations_research::BaseLns
This is the base class for building an Lns operator.
Definition: constraint_solveri.h:1266
operations_research::LocalSearchState::Commit
void Commit()
Definition: local_search.cc:3601
operations_research::Solver::CROSS
@ CROSS
Operator which cross exchanges the starting chains of 2 paths, including exchanging the whole paths.
Definition: constraint_solver.h:478
operations_research::LocalSearchMonitor::BeginMakeNextNeighbor
virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0
operations_research::Solver::TWOOPT
@ TWOOPT
Operator which reverses a sub-chain of a path.
Definition: constraint_solver.h:439
LOG
#define LOG(severity)
Definition: base/logging.h:420
operations_research::IntVarElement::Var
IntVar * Var() const
Definition: constraint_solver.h:4653
operations_research::RelocateAndMakeInactiveOperator::RelocateAndMakeInactiveOperator
RelocateAndMakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1239
ERROR
const int ERROR
Definition: log_severity.h:32
operations_research::PathState::ChangedPaths
const std::vector< int > & ChangedPaths() const
Definition: constraint_solveri.h:3092
WallTimer::Get
double Get() const
Definition: timer.h:45
operations_research::MostSignificantBitPosition32
int MostSignificantBitPosition32(uint32 n)
Definition: bitset.h:273
operations_research::FindOneNeighbor
Definition: local_search.cc:3998
primary_vars_size_
const int primary_vars_size_
Definition: local_search.cc:3388
operations_research::IntVarLocalSearchFilter::AddVars
void AddVars(const std::vector< IntVar * > &vars)
Add variables to "track" to the filter.
Definition: local_search.cc:3246
operations_research::MakeChainInactiveOperator::DebugString
std::string DebugString() const override
Definition: local_search.cc:1284
operations_research::Assignment::Objective
IntVar * Objective() const
Definition: constraint_solver/assignment.cc:878
FATAL
const int FATAL
Definition: log_severity.h:32
operations_research::MakeChainInactiveOperator
Definition: local_search.cc:1272
operations_research::MakeChainInactiveOperator::MakeChainInactiveOperator
MakeChainInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1274
operations_research::NearestNeighbors::Neighbors
const std::vector< int > & Neighbors(int index) const
Definition: local_search.cc:1624
operations_research::PathOperator::MoveChain
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 ...
Definition: local_search.cc:411
operations_research::Assignment::CopyIntersection
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
Definition: constraint_solver/assignment.cc:999
hamiltonian_path.h
operations_research::SearchMonitor::solver
Solver * solver() const
Definition: constraint_solver.h:3703
operations_research::Relocate::~Relocate
~Relocate() override
Definition: local_search.cc:956
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::ApplyChanges
bool ApplyChanges(Assignment *delta, Assignment *deltadelta) const
Definition: constraint_solveri.h:864
CHECK_GE
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
operations_research::ModelVisitor::kVarsArgument
static const char kVarsArgument[]
Definition: constraint_solver.h:3489
operations_research::IntVarLocalSearchOperator::MakeOneNeighbor
virtual bool MakeOneNeighbor()
Creates a new neighbor.
Definition: local_search.cc:95
operations_research::LocalSearchProfiler::DebugString
std::string DebugString() const override
Definition: local_search.cc:3622
operations_research::Solver::RevAlloc
T * RevAlloc(T *object)
Registers the given object as being reversible.
Definition: constraint_solver.h:791
operations_research::Solver::MAKEACTIVE
@ MAKEACTIVE
Operator which inserts an inactive node into a path.
Definition: constraint_solver.h:486
operations_research::BaseLns::MakeOneNeighbor
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
Definition: local_search.cc:104
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::Value
const int64 & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
Definition: constraint_solveri.h:843
operations_research::PathOperator::ConsiderAlternatives
virtual bool ConsiderAlternatives(int64 base_index) const
Indicates if alternatives should be considered when iterating over base nodes.
Definition: constraint_solveri.h:1441
operations_research::SwapActiveOperator::SwapActiveOperator
SwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1311
logging.h
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::OldValue
const int64 & OldValue(int64 index) const
Definition: constraint_solveri.h:850
operations_research::LinKernighan::~LinKernighan
~LinKernighan() override
Definition: local_search.cc:1687
operations_research::MakeActiveOperator::MakeActiveOperator
MakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1129
operations_research::Assignment::AddObjective
void AddObjective(IntVar *const v)
Definition: constraint_solver/assignment.cc:872
operations_research::RelocateAndMakeActiveOperator::RelocateAndMakeActiveOperator
RelocateAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1155
operations_research::IntExpr::Min
virtual int64 Min() const =0
operations_research::MakeActiveAndRelocate::MakeActiveAndRelocate
MakeActiveAndRelocate(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1183
operations_research::LocalSearchProfiler::BeginFiltering
void BeginFiltering(const LocalSearchFilter *filter) override
Definition: local_search.cc:3787
DCHECK_GT
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
operations_research::Solver::IndexEvaluator3
std::function< int64(int64, int64, int64)> IndexEvaluator3
Definition: constraint_solver.h:740
value
int64 value
Definition: demon_profiler.cc:43
operations_research::ExtendedSwapActiveOperator
Definition: local_search.cc:1341
CHECK_GT
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
operations_research::Solver::SetSearchContext
void SetSearchContext(Search *search, const std::string &search_context)
Definition: constraint_solver.cc:3215
operations_research::BaseInactiveNodeToPathOperator
Definition: local_search.cc:1073
operations_research::PathOperator::next_base_to_increment_
int next_base_to_increment_
Definition: constraint_solveri.h:1562
operations_research::NearestNeighbors::~NearestNeighbors
virtual ~NearestNeighbors()
Definition: local_search.cc:1588
operations_research::AcceptNeighbor
void AcceptNeighbor(Search *const search)
Definition: constraint_solver.cc:1353
CHECK_LT
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
operations_research::LocalSearchProfiler::ExportToLocalSearchStatistics
LocalSearchStatistics ExportToLocalSearchStatistics() const
Definition: local_search.cc:3633
operations_research::Solver::TSPOPT
@ TSPOPT
Sliding TSP operator.
Definition: constraint_solver.h:580
operations_research::SearchMonitor::Install
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
Definition: constraint_solver.cc:2892
bounds
SharedBoundsManager * bounds
Definition: cp_model_solver.cc:2104
macros.h
operations_research::RelocateAndMakeActiveOperator::~RelocateAndMakeActiveOperator
~RelocateAndMakeActiveOperator() override
Definition: local_search.cc:1161
saturated_arithmetic.h
operations_research::FindOneNeighbor::DebugString
std::string DebugString() const override
Definition: local_search.cc:4008
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::PathOperator::SwapActiveAndInactive
bool SwapActiveAndInactive(int64 active, int64 inactive)
Replaces active by inactive in the current path, making active inactive.
Definition: local_search.cc:484
operations_research::SwapActiveOperator
Definition: local_search.cc:1309
operations_research::LocalSearchProfiler::EndOperatorStart
void EndOperatorStart() override
Definition: local_search.cc:3759
operations_research::RegularLimit
Usual limit based on wall_time, number of explored branches and number of failures in the search tree...
Definition: constraint_solver.h:4276
operations_research::PathState::NumPaths
int NumPaths() const
Definition: constraint_solveri.h:3073
operations_research::Assignment::HasObjective
bool HasObjective() const
Definition: constraint_solver.h:5076
operations_research::PathState::NodeRange
Definition: constraint_solveri.h:3311
WallTimer::Stop
void Stop()
Definition: timer.h:39
operations_research::LocalSearchProfiler::ExitSearch
void ExitSearch() override
End of the search.
Definition: local_search.cc:3627
operations_research::Cross
Definition: local_search.cc:1036
operations_research::PathState::Commit
void Commit()
Definition: local_search.cc:2752
operations_research::MakeLocalSearchOperator
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.
Definition: local_search.cc:2277
operations_research::LocalSearchProfiler::EndMakeNextNeighbor
void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta) override
Definition: local_search.cc:3766
kint64min
static const int64 kint64min
Definition: integral_types.h:60
operations_research::PathState::Start
int Start(int path) const
Definition: constraint_solveri.h:3075
operations_research::Assignment::Store
void Store()
Definition: constraint_solver/assignment.cc:425
operations_research::Solver::MakeNeighborhoodLimit
LocalSearchOperator * MakeNeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
Creates a local search operator that wraps another local search operator and limits the number of nei...
Definition: local_search.cc:1882
operations_research::SolutionPool
This class is used to manage a pool of solutions.
Definition: constraint_solver.h:5372
operations_research::RelocateAndMakeInactiveOperator
Definition: local_search.cc:1237
operations_research::BaseInactiveNodeToPathOperator::BaseInactiveNodeToPathOperator
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)
Definition: local_search.cc:1075
operations_research::DeleteLocalSearchProfiler
void DeleteLocalSearchProfiler(LocalSearchProfiler *monitor)
Definition: local_search.cc:3841
operations_research::IntVarLocalSearchFilter::Synchronize
void Synchronize(const Assignment *assignment, const Assignment *delta) override
This method should not be overridden.
Definition: local_search.cc:3263
operations_research::SwapActiveOperator::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1322
operations_research::PathOperator::GetBaseNodeRestartPosition
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...
Definition: constraint_solveri.h:1431
operations_research::NearestNeighbors::NearestNeighbors
NearestNeighbors(Solver::IndexEvaluator3 evaluator, const PathOperator &path_operator, int size)
Definition: local_search.cc:1606
operations_research::MakeInactiveOperator::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1221
operations_research::BaseInactiveNodeToPathOperator::~BaseInactiveNodeToPathOperator
~BaseInactiveNodeToPathOperator() override
Definition: local_search.cc:1084
int64
int64_t int64
Definition: integral_types.h:34
operations_research::Cross::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1049
constraint_solveri.h
operations_research::PathOperator::MakeOneNeighbor
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
Definition: local_search.cc:387
operations_research::Solver::EXTENDEDSWAPACTIVE
@ EXTENDEDSWAPACTIVE
Operator which makes an inactive node active and an active one inactive.
Definition: constraint_solver.h:520
operations_research::PathLns::PathLns
PathLns(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments)
Definition: local_search.cc:1783
operations_research::MakeActiveAndRelocate::DebugString
std::string DebugString() const override
Definition: local_search.cc:1191
operations_research::Bitset64::ClearAll
void ClearAll()
Definition: bitset.h:452
operations_research::BaseObject::DebugString
virtual std::string DebugString() const
Definition: constraint_solver.h:3151
operations_research::PathOperator::ResetPosition
void ResetPosition()
Reset the position of the operator to its position when Start() was last called; this can be used to ...
Definition: constraint_solveri.h:1502
operations_research::LocalSearchFilterManager::Accept
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...
Definition: local_search.cc:3905
operations_research::LinKernighan::DebugString
std::string DebugString() const override
Definition: local_search.cc:1660
operations_research::MakeInactiveOperator::~MakeInactiveOperator
~MakeInactiveOperator() override
Definition: local_search.cc:1220
index
int index
Definition: pack.cc:508
operations_research::RelocateAndMakeInactiveOperator::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1246
int32
int int32
Definition: integral_types.h:33
operations_research::LocalSearchMonitor::EndFilterNeighbor
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
operations_research::LocalSearchPhaseParameters::solution_pool
SolutionPool * solution_pool() const
Definition: local_search.cc:4310
operations_research::BaseObject
A BaseObject is the root of all reversibly allocated objects.
Definition: constraint_solver.h:3147
operations_research::SwapActiveOperator::~SwapActiveOperator
~SwapActiveOperator() override
Definition: local_search.cc:1316
operations_research::Assignment::DebugString
std::string DebugString() const override
Definition: constraint_solver/assignment.cc:623
operations_research::Solver::MakeVariableDomainFilter
LocalSearchFilter * MakeVariableDomainFilter()
Definition: local_search.cc:3233
operations_research::LocalSearchProfiler::LocalSearchProfiler
LocalSearchProfiler(Solver *solver)
Definition: local_search.cc:3621
operations_research::TwoOpt::DebugString
std::string DebugString() const override
Definition: local_search.cc:877
operations_research::AssignmentContainer< IntVar, IntVarElement >
gtl::FindOrDie
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:176
operations_research::TSPLns::TSPLns
TSPLns(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)
Definition: local_search.cc:1471
evaluator_
std::function< int64(int64, int64)> evaluator_
Definition: search.cc:1361
operations_research::HamiltonianPathSolver::ChangeCostMatrix
void ChangeCostMatrix(CostFunction cost)
Definition: hamiltonian_path.h:627
operations_research::LocalSearchPhaseParameters::LocalSearchPhaseParameters
LocalSearchPhaseParameters(IntVar *objective, SolutionPool *const pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, RegularLimit *const limit, LocalSearchFilterManager *filter_manager)
Definition: local_search.cc:4293
operations_research::LocalSearchProfiler::RestartSearch
void RestartSearch() override
Restart the search.
Definition: local_search.cc:3623
operations_research::TwoOpt::OnSamePathAsPreviousBase
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...
Definition: local_search.cc:880
operations_research::LocalSearchFilter
Local Search Filters are used for fast neighbor pruning.
Definition: constraint_solveri.h:1719
demand
int64 demand
Definition: resource.cc:123
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::Size
int Size() const
Definition: constraint_solveri.h:840
operations_research::LocalSearchVariable
Definition: constraint_solveri.h:1679
operations_research::LocalSearchFilterManager::Synchronize
void Synchronize(const Assignment *assignment, const Assignment *delta)
Synchronizes all filters to assignment.
Definition: local_search.cc:3950
operations_research::LocalSearchPhaseParameters::ls_operator
LocalSearchOperator * ls_operator() const
Definition: local_search.cc:4311
operations_research::MakeChainInactiveOperator::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1280
operations_research::IntExpr::Max
virtual int64 Max() const =0
operations_research::MakeUnaryDimensionFilter
LocalSearchFilter * MakeUnaryDimensionFilter(Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)
Definition: local_search.cc:3196
operations_research::Relocate::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:974
cost
int64 cost
Definition: routing_flow.cc:130
operations_research::IntVarLocalSearchFilter::SynchronizeOnAssignment
void SynchronizeOnAssignment(const Assignment *assignment)
Definition: local_search.cc:3274
operations_research::TwoOpt::TwoOpt
TwoOpt(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:866
operations_research::PathState::CutChains
void CutChains()
Definition: local_search.cc:2716
operations_research::PathLns::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1809
operations_research::ChangeValue::MakeOneNeighbor
bool MakeOneNeighbor() override
This method should not be overridden. Override ModifyValue() instead.
Definition: local_search.cc:298
operations_research::Solver::MultiArmedBanditConcatenateOperators
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.
Definition: local_search.cc:2267
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::AddVars
void AddVars(const std::vector< IntVar * > &vars)
Definition: constraint_solveri.h:901
operations_research::NearestNeighbors::DebugString
virtual std::string DebugString() const
Definition: local_search.cc:1592
constraint_solver.h
operations_research::UnaryDimensionChecker::Check
bool Check() const
Definition: local_search.cc:2983
operations_research::TwoOpt
Definition: local_search.cc:864
WallTimer::Start
void Start()
Definition: timer.h:31
operations_research::PathOperator::PathClass
int PathClass(int i) const
Returns the class of the path of the ith base node.
Definition: constraint_solveri.h:1406
operations_research::LocalSearchProfiler::BeginOperatorStart
void BeginOperatorStart() override
Local search operator events.
Definition: local_search.cc:3758
operations_research::LocalSearchMonitor
Definition: constraint_solveri.h:1915
operations_research::Assignment
An Assignment is a variable -> domains mapping, used to report solutions to the user.
Definition: constraint_solver.h:5033
operations_research::NearestNeighbors
Definition: local_search.cc:1584
operations_research::PathOperator::num_paths_
int num_paths_
Definition: constraint_solveri.h:1563
operations_research::AssignmentContainer::Element
const E & Element(const V *const var) const
Definition: constraint_solver.h:4936
operations_research::SwapActiveOperator::DebugString
std::string DebugString() const override
Definition: local_search.cc:1319
operations_research::Relocate::Relocate
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)
Definition: local_search.cc:948
operations_research::MakeChainInactiveOperator::~MakeChainInactiveOperator
~MakeChainInactiveOperator() override
Definition: local_search.cc:1279
operations_research::PathLns::HasFragments
bool HasFragments() const override
Definition: local_search.cc:1797
operations_research::MakeActiveOperator
Definition: local_search.cc:1127
operations_research::IntVarLocalSearchOperator::MakeNextNeighbor
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
Definition: local_search.cc:74
operations_research::FindOneNeighbor::FindOneNeighbor
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)
Definition: local_search.cc:4034
operations_research::BuildLocalSearchProfiler
LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)
Definition: local_search.cc:3834
filter_enum_
Solver::LocalSearchFilterBound filter_enum_
Definition: local_search.cc:3391
operations_research::ModelVisitor::kVariableGroupExtension
static const char kVariableGroupExtension[]
Definition: constraint_solver.h:3425
operations_research::Assignment::IntContainer
AssignmentContainer< IntVar, IntVarElement > IntContainer
Definition: constraint_solver.h:5035
operations_research::CapAdd
int64 CapAdd(int64 x, int64 y)
Definition: saturated_arithmetic.h:124
operations_research::InstallLocalSearchProfiler
void InstallLocalSearchProfiler(LocalSearchProfiler *monitor)
Definition: local_search.cc:3830
operations_research::Solver::RandomConcatenateOperators
LocalSearchOperator * RandomConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Randomized version of local search concatenator; calls a random operator at each call to MakeNextNeig...
Definition: local_search.cc:2105
operations_research::Assignment::IntervalVarContainer
const IntervalContainer & IntervalVarContainer() const
Definition: constraint_solver.h:5186
operations_research::Relocate::OnSamePathAsPreviousBase
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...
Definition: local_search.cc:962
operations_research::Solver::MakeStoreAssignment
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which stores an Assignment (calls void Assignment::Store())
Definition: constraint_solver/assignment.cc:1085
operations_research::Cross::Cross
Cross(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1038
operations_research::IntVarLocalSearchFilter::Value
int64 Value(int index) const
Definition: constraint_solveri.h:1833
operations_research::PathState::PathState
PathState(int num_nodes, std::vector< int > path_start, std::vector< int > path_end)
Definition: local_search.cc:2559
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::RevertChanges
void RevertChanges(bool incremental)
Definition: constraint_solveri.h:888
operations_research::Solver::MakeLocalSearchPhase
DecisionBuilder * MakeLocalSearchPhase(Assignment *const assignment, LocalSearchPhaseParameters *const parameters)
Local Search decision builders factories.
Definition: local_search.cc:4773
operations_research::Solver::LocalSearchFilterBound
LocalSearchFilterBound
This enum is used in Solver::MakeLocalSearchObjectiveFilter.
Definition: constraint_solver.h:595
operations_research::RelocateAndMakeActiveOperator::DebugString
std::string DebugString() const override
Definition: local_search.cc:1170
operations_research::LocalSearchProfiler::EndAcceptNeighbor
void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
Definition: local_search.cc:3781
operations_research::Solver::MakeDefaultSolutionPool
SolutionPool * MakeDefaultSolutionPool()
Solution Pool.
Definition: local_search.cc:4769
ABSL_FLAG
ABSL_FLAG(int, cp_local_search_sync_frequency, 16, "Frequency of checks for better solutions in the solution pool.")
operations_research::ChangeValue::ModifyValue
virtual int64 ModifyValue(int64 index, int64 value)=0
CHECK_EQ
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
operations_research::LocalSearchMonitor::EndMakeNextNeighbor
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
operations_research::MakePathStateFilter
LocalSearchFilter * MakePathStateFilter(Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)
Definition: local_search.cc:2953
operations_research::SolutionPool::SyncNeeded
virtual bool SyncNeeded(Assignment *const local_assignment)=0
This method checks if the local solution needs to be updated with an external one.
operations_research::MakeActiveOperator::~MakeActiveOperator
~MakeActiveOperator() override
Definition: local_search.cc:1134
operations_research::PathOperator::PathOperator
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.
Definition: local_search.cc:339
operations_research::LocalSearchPhaseParameters::objective
IntVar * objective() const
Definition: local_search.cc:4309
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::Var
IntVar * Var(int64 index) const
Returns the variable of given index.
Definition: constraint_solveri.h:848
operations_research::Exchange::Exchange
Exchange(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1002
operations_research::Assignment::ObjectiveValue
int64 ObjectiveValue() const
Definition: constraint_solver/assignment.cc:894
operations_research::Solver::FULLPATHLNS
@ FULLPATHLNS
Operator which relaxes one entire path and all inactive nodes, thus defining num_paths neighbors.
Definition: constraint_solver.h:533
operations_research::HamiltonianPathSolver
Definition: hamiltonian_path.h:453
operations_research::LocalSearchOperator::Reset
virtual void Reset()
Definition: constraint_solveri.h:804
operations_research::Solver::MAKEINACTIVE
@ MAKEINACTIVE
Operator which makes path nodes inactive.
Definition: constraint_solver.h:493
operations_research::DecisionBuilder
A DecisionBuilder is responsible for creating the search tree.
Definition: constraint_solver.h:3263
operations_research::IntVarElement
Definition: constraint_solver.h:4646
operations_research::Solver::MakeOperator
LocalSearchOperator * MakeOperator(const std::vector< IntVar * > &vars, LocalSearchOperators op)
Local Search Operators.
Definition: local_search.cc:2310
operations_research::Solver::MakeSumObjectiveFilter
IntVarLocalSearchFilter * MakeSumObjectiveFilter(const std::vector< IntVar * > &vars, IndexEvaluator2 values, Solver::LocalSearchFilterBound filter_enum)
Definition: local_search.cc:3524
operations_research::PathOperator::RestartAtPathStartOnSynchronize
virtual bool RestartAtPathStartOnSynchronize()
When the operator is being synchronized with a new solution (when Start() is called),...
Definition: constraint_solveri.h:1419
operations_research::PathOperator::CheckChainValidity
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 ...
Definition: local_search.cc:833
operations_research::LocalSearchMonitor::BeginFiltering
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
objective_
IntVar *const objective_
Definition: search.cc:2951
operations_research::PathLns::~PathLns
~PathLns() override
Definition: local_search.cc:1793
operations_research::TSPOpt::DebugString
std::string DebugString() const override
Definition: local_search.cc:1383
operations_research::LocalSearchOperator::MakeNextNeighbor
virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0
operations_research::NeighborhoodLimit::Start
void Start(const Assignment *assignment) override
Definition: local_search.cc:1859
WallTimer
Definition: timer.h:23
operations_research::Solver::MakeRejectFilter
LocalSearchFilter * MakeRejectFilter()
Definition: local_search.cc:2555
operations_research::Solver::UNACTIVELNS
@ UNACTIVELNS
Operator which relaxes all inactive nodes and one sub-chain of six consecutive arcs.
Definition: constraint_solver.h:538
operations_research::ExtendedSwapActiveOperator::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1356
operations_research::AcceptDelta
bool AcceptDelta(Search *const search, Assignment *delta, Assignment *deltadelta)
Definition: constraint_solver.cc:1348
operations_research::MakeInactiveOperator::DebugString
std::string DebugString() const override
Definition: local_search.cc:1226
operations_research::FindOneNeighbor::~FindOneNeighbor
~FindOneNeighbor() override
Definition: local_search.cc:4006
operations_research::PathState::Revert
void Revert()
Definition: local_search.cc:2761
operations_research::LocalSearchMonitor::EndFiltering
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
operations_research::LocalSearchFilterManager::LocalSearchFilterManager
LocalSearchFilterManager(std::vector< FilterEvent > filter_events)
Definition: local_search.cc:3884
operations_research::Relocate
Definition: local_search.cc:935
operations_research::PathOperator::MakeNeighbor
virtual bool MakeNeighbor()=0
operations_research::MakeActiveOperator::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1140
DCHECK
#define DCHECK(condition)
Definition: base/logging.h:884
operations_research::TSPLns::~TSPLns
~TSPLns() override
Definition: local_search.cc:1448
operations_research::RelocateAndMakeActiveOperator
Definition: local_search.cc:1153
operations_research::ModelVisitor::kIntervalsArgument
static const char kIntervalsArgument[]
Definition: constraint_solver.h:3455
delta_costs_
int64 *const delta_costs_
Definition: local_search.cc:3390
operations_research::Relocate::Relocate
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)
Definition: local_search.cc:937
operations_research::PathOperator::Prev
int64 Prev(int64 node) const
Returns the node before node in the current delta.
Definition: constraint_solveri.h:1352
operations_research::Solver::SIMPLELNS
@ SIMPLELNS
Operator which defines one neighbor per variable.
Definition: constraint_solver.h:562
CHECK_LE
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
operations_research::PathOperator::SetNext
void SetNext(int64 from, int64 to, int64 path)
Sets 'to' to be the node after 'from' on the given path.
Definition: constraint_solveri.h:1474
operations_research::UnaryDimensionChecker::UnaryDimensionChecker
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)
Definition: local_search.cc:2960
operations_research::ChangeValue::~ChangeValue
~ChangeValue() override
Definition: local_search.cc:296
operations_research::Solver::DECREMENT
@ DECREMENT
Operator which defines a neighborhood to decrement values.
Definition: constraint_solver.h:553
operations_research::Solver::MakeAcceptFilter
LocalSearchFilter * MakeAcceptFilter()
Local Search Filters.
Definition: local_search.cc:2537
operations_research::Solver::GetLocalSearchMonitor
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
Definition: constraint_solver.cc:3211
operations_research::LinKernighan
Definition: local_search.cc:1652
operations_research::Exchange
Definition: local_search.cc:1000
synchronized_sum_
int64 synchronized_sum_
Definition: local_search.cc:3392
operations_research::RelocateAndMakeInactiveOperator::~RelocateAndMakeInactiveOperator
~RelocateAndMakeInactiveOperator() override
Definition: local_search.cc:1245
operations_research::Bitset64::Set
void Set(IndexType i)
Definition: bitset.h:493
operations_research::Solver::PATHLNS
@ PATHLNS
Operator which relaxes two sub-chains of three consecutive arcs each.
Definition: constraint_solver.h:529
operations_research::PathOperator::number_of_nexts
int number_of_nexts() const
Number of next variables.
Definition: constraint_solveri.h:1365
operations_research::Assignment::SetObjectiveValue
void SetObjectiveValue(int64 value)
Definition: constraint_solver/assignment.cc:926
operations_research::Solver::Fail
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
Definition: constraint_solver.cc:2416
operations_research::AcceptUncheckedNeighbor
void AcceptUncheckedNeighbor(Search *const search)
Definition: constraint_solver.cc:1355
operations_research::IntVarLocalSearchFilter::~IntVarLocalSearchFilter
~IntVarLocalSearchFilter() override
Definition: local_search.cc:3261
operations_research::LocalSearchProfiler::Install
void Install() override
Install itself on the solver.
Definition: local_search.cc:3799
operations_research::MakeActiveOperator::DebugString
std::string DebugString() const override
Definition: local_search.cc:1137
operations_research::LocalSearchProfiler::PrintOverview
std::string PrintOverview() const
Definition: local_search.cc:3687
operations_research::UnaryDimensionChecker::Interval::min
int64 min
Definition: constraint_solveri.h:3382
operations_research::PathOperator::OnSamePathAsPreviousBase
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...
Definition: constraint_solveri.h:1425
operations_research::NearestNeighbors::Initialize
void Initialize()
Definition: local_search.cc:1613
operations_research::PathOperator::MakeActive
bool MakeActive(int64 node, int64 destination)
Insert the inactive node after destination.
Definition: local_search.cc:457
operations_research::LocalSearchPhaseParameters::~LocalSearchPhaseParameters
~LocalSearchPhaseParameters() override
Definition: local_search.cc:4304
DCHECK_GE
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
operations_research::Solver
Solver Class.
Definition: constraint_solver.h:248
operations_research::LocalSearchPhaseParameters::sub_decision_builder
DecisionBuilder * sub_decision_builder() const
Definition: local_search.cc:4312
operations_research::Solver::MakeSolutionsLimit
RegularLimit * MakeSolutionsLimit(int64 solutions)
Creates a search limit that constrains the number of solutions found during the search.
Definition: search.cc:4105
operations_research::PathOperator::GetSiblingAlternativeIndex
int GetSiblingAlternativeIndex(int node) const
Returns the index of the alternative set of the sibling of node.
Definition: constraint_solveri.h:1541
operations_research::Solver::EQ
@ EQ
Move is accepted when the current objective value is in the interval objective.Min .
Definition: constraint_solver.h:602
operations_research::UnaryDimensionChecker::Interval::max
int64 max
Definition: constraint_solveri.h:3383
operations_research::PathOperator::Reset
void Reset() override
Definition: local_search.cc:378
operations_research::LocalSearchPhaseParameters::DebugString
std::string DebugString() const override
Definition: local_search.cc:4305
operations_research::SolutionPool::Initialize
virtual void Initialize(Assignment *const assignment)=0
This method is called to initialize the solution pool with the assignment from the local search.
operations_research::Exchange::~Exchange
~Exchange() override
Definition: local_search.cc:1007
operations_research::LocalSearchProfiler::BeginAcceptNeighbor
void BeginAcceptNeighbor(const LocalSearchOperator *op) override
Definition: local_search.cc:3780
operations_research::ExtendedSwapActiveOperator::DebugString
std::string DebugString() const override
Definition: local_search.cc:1351
operations_research::Solver::LE
@ LE
Move is accepted when the current objective value <= objective.Max.
Definition: constraint_solver.h:599
operations_research::BaseLns::BaseLns
BaseLns(const std::vector< IntVar * > &vars)
Definition: local_search.cc:99
operations_research::TwoOpt::~TwoOpt
~TwoOpt() override
Definition: local_search.cc:873
operations_research::BaseLns::~BaseLns
~BaseLns() override
Definition: local_search.cc:102
operations_research::LocalSearchFilterManager
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
Definition: constraint_solveri.h:1763
operations_research::HamiltonianPathSolver::TravelingSalesmanPath
std::vector< int > TravelingSalesmanPath()
Definition: hamiltonian_path.h:864
operations_research::PathState
Definition: constraint_solveri.h:3049
operations_research::LocalSearchProfiler::BeginFilterNeighbor
void BeginFilterNeighbor(const LocalSearchOperator *op) override
Definition: local_search.cc:3773
operations_research::IntVarLocalSearchFilter::IntVarLocalSearchFilter
IntVarLocalSearchFilter(const std::vector< IntVar * > &vars)
Definition: local_search.cc:3241
operations_research::LocalSearchProfiler::EndFiltering
void EndFiltering(const LocalSearchFilter *filter, bool reject) override
Definition: local_search.cc:3791
operations_research::AssignmentContainer::elements
const std::vector< E > & elements() const
Definition: constraint_solver.h:4949
operations_research::Solver::Solver
Solver(const std::string &name)
Solver API.
Definition: constraint_solver.cc:1417
operations_research::Solver::MakeMoveTowardTargetOperator
LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)
Creates a local search operator that tries to move the assignment of some variables toward a target.
Definition: local_search.cc:269
operations_research::LinKernighan::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1691
operations_research::ExtendedSwapActiveOperator::ExtendedSwapActiveOperator
ExtendedSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1343
operations_research::LocalSearchState::Revert
void Revert()
Definition: local_search.cc:3607
operations_research::TSPOpt::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1401
gtl::reversed_view
ReverseView< Container > reversed_view(const Container &c)
Definition: iterator_adaptors.h:33
delta_sum_
int64 delta_sum_
Definition: local_search.cc:3393
row
RowIndex row
Definition: markowitz.cc:175
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::SetValue
void SetValue(int64 index, const int64 &value)
Definition: constraint_solveri.h:851
operations_research::IntVarLocalSearchOperator
Specialization of LocalSearchOperator built from an array of IntVars which specifies the scope of the...
Definition: constraint_solveri.h:1028
operations_research::NeighborhoodLimit::DebugString
std::string DebugString() const override
Definition: local_search.cc:1874
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::Deactivate
void Deactivate(int64 index)
Definition: constraint_solveri.h:860
operations_research::TwoOpt::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:895
operations_research::PathOperator
Base class of the local search operators dedicated to path modifications (a path is a set of nodes li...
Definition: constraint_solveri.h:1319
operations_research::IntVarLocalSearchFilter::Size
int Size() const
Definition: constraint_solveri.h:1831
iterator_adaptors.h
operations_research::LocalSearchOperator::HoldsDelta
virtual bool HoldsDelta() const
Definition: constraint_solveri.h:809
operations_research::PathOperator::IsInactive
bool IsInactive(int64 node) const
Returns true if node is inactive.
Definition: constraint_solveri.h:1492
operations_research::TSPOpt::~TSPOpt
~TSPOpt() override
Definition: local_search.cc:1380
operations_research::TSPOpt
Definition: local_search.cc:1375
operations_research::MakeInactiveOperator
Definition: local_search.cc:1213
operations_research::Exchange::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1013
operations_research::Solver::MAKECHAININACTIVE
@ MAKECHAININACTIVE
Operator which makes a "chain" of path nodes inactive.
Definition: constraint_solver.h:501
operations_research::PathOperator::number_of_nexts_
const int number_of_nexts_
Definition: constraint_solveri.h:1560
operations_research::Solver::MakeLocalSearchPhaseParameters
LocalSearchPhaseParameters * MakeLocalSearchPhaseParameters(IntVar *objective, LocalSearchOperator *const ls_operator, DecisionBuilder *const sub_decision_builder)
Local Search Phase Parameters.
Definition: local_search.cc:4329
operations_research::Solver::ConcatenateOperators
LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Creates a local search operator which concatenates a vector of operators.
Definition: local_search.cc:2015
operations_research::Solver::UseFastLocalSearch
bool UseFastLocalSearch() const
Returns true if fast local search is enabled.
Definition: constraint_solver.h:2883
operations_research::MakeInactiveOperator::MakeInactiveOperator
MakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Definition: local_search.cc:1215
DCHECK_EQ
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
hash.h
operations_research::Assignment::Clear
void Clear()
Definition: constraint_solver/assignment.cc:418
operations_research::IntVarLocalSearchFilter
Definition: constraint_solveri.h:1811
operations_research::Assignment::NumIntVars
int NumIntVars() const
Definition: constraint_solver.h:5053
maximize_
const bool maximize_
Definition: search.cc:2499
operations_research::MakeChainInactiveOperator::GetBaseNodeRestartPosition
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...
Definition: local_search.cc:1295
delta
int64 delta
Definition: resource.cc:1684
operations_research::LocalSearchProfiler
Definition: local_search.cc:3619
operations_research::TSPLns::DebugString
std::string DebugString() const override
Definition: local_search.cc:1451
MAKE_LOCAL_SEARCH_OPERATOR
#define MAKE_LOCAL_SEARCH_OPERATOR(OperatorClass)
Definition: local_search.cc:2285
operations_research::PathOperator::IsPathEnd
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...
Definition: constraint_solveri.h:1486
operations_research::LocalSearchOperator
The base class for all local search operators.
Definition: constraint_solveri.h:798
next
Block * next
Definition: constraint_solver.cc:674
operations_research::PathOperator::OnNodeInitialization
virtual void OnNodeInitialization()
Called by OnStart() after initializing node information.
Definition: constraint_solveri.h:1373
incremental_
bool incremental_
Definition: local_search.cc:3394
absl
Definition: cleanup.h:22
operations_research::LocalSearchMonitor::BeginFilterNeighbor
virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0
operations_research::LocalSearchMonitor::EndAcceptNeighbor
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
operations_research::Solver::TopPeriodicCheck
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
Definition: constraint_solver.cc:1542
operations_research::LocalOptimumReached
bool LocalOptimumReached(Search *const search)
Definition: constraint_solver.cc:1344
operations_research::PathState::Path
int Path(int node) const
Definition: constraint_solveri.h:3082
operations_research::RelocateAndMakeActiveOperator::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1162
operations_research::Solver::LocalSearchProfile
std::string LocalSearchProfile() const
Returns local search profiling information in a human readable format.
Definition: local_search.cc:3843
operations_research::MakeActiveAndRelocate::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1196
operations_research::Cross::~Cross
~Cross() override
Definition: local_search.cc:1043
operations_research::LocalSearchPhaseParameters::limit
RegularLimit * limit() const
Definition: local_search.cc:4315
operations_research::PathState::NumNodes
int NumNodes() const
Definition: constraint_solveri.h:3071
operations_research::LocalSearchOperator::Start
virtual void Start(const Assignment *assignment)=0
operations_research::PathState::Nodes
NodeRange Nodes(int path) const
Definition: local_search.cc:2604
operations_research::FindOneNeighbor::Next
Decision * Next(Solver *const solver) override
This is the main method of the decision builder class.
Definition: local_search.cc:4083
operations_research::Solver::SWAPACTIVE
@ SWAPACTIVE
Operator which replaces an active node by an inactive one.
Definition: constraint_solver.h:508
operations_research::RegularLimit::Init
void Init() override
This method is called when the search limit is initialized.
Definition: search.cc:4009
operations_research::BaseLns::NextFragment
virtual bool NextFragment()=0
operations_research::PropagationBaseObject::solver
Solver * solver() const
Definition: constraint_solver.h:3174
operations_research::Solver::IsLocalSearchProfilingEnabled
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
Definition: constraint_solver.cc:178
operations_research::LocalSearchProfiler::BeginMakeNextNeighbor
void BeginMakeNextNeighbor(const LocalSearchOperator *op) override
Definition: local_search.cc:3760
operations_research::PathOperator::BaseNode
int64 BaseNode(int i) const
Returns the ith base node of the operator.
Definition: constraint_solveri.h:1376
DCHECK_LE
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
operations_research::VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >::prev_values_
std::vector< int64 > prev_values_
Definition: constraint_solveri.h:933
operations_research::Solver::LK
@ LK
Lin-Kernighan local search.
Definition: constraint_solver.h:572
operations_research::LocalSearchFilterManager::Revert
void Revert()
Definition: local_search.cc:3894
operations_research::Solver::Compose
DecisionBuilder * Compose(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which sequentially composes decision builders.
Definition: search.cc:552
operations_research::UnaryDimensionChecker::Commit
void Commit()
Definition: local_search.cc:3055
operations_research::PathOperator::SkipUnchanged
bool SkipUnchanged(int index) const override
Definition: local_search.cc:399
operations_research::Exchange::DebugString
std::string DebugString() const override
Definition: local_search.cc:1010
operations_research::LocalSearchOperator::Self
virtual const LocalSearchOperator * Self() const
Definition: constraint_solveri.h:806
operations_research::IntVarLocalSearchFilter::Var
IntVar * Var(int index) const
Definition: constraint_solveri.h:1832
operations_research::LocalSearchFilterManager::GetAcceptedObjectiveValue
int64 GetAcceptedObjectiveValue() const
Definition: constraint_solveri.h:1795
operations_research::Solver::INCREMENT
@ INCREMENT
Operator which defines one neighbor per variable.
Definition: constraint_solver.h:548
operations_research::TSPLns::MakeNeighbor
bool MakeNeighbor() override
Definition: local_search.cc:1498
operations_research::TwoOpt::GetBaseNodeRestartPosition
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...
Definition: local_search.cc:884
operations_research::PathState::ChainRange
Definition: constraint_solveri.h:3268
operations_research::Solver::OROPT
@ OROPT
Relocate: OROPT and RELOCATE.
Definition: constraint_solver.h:455
operations_research::Relocate::DebugString
std::string DebugString() const override
Definition: local_search.cc:959
CHECK
#define CHECK(condition)
Definition: base/logging.h:495
commandlineflags.h
operations_research::Solver::EvaluatorLocalSearchOperators
EvaluatorLocalSearchOperators
This enum is used in Solver::MakeOperator associated with an evaluator to specify the neighborhood to...
Definition: constraint_solver.h:567
parameters
SatParameters parameters
Definition: cp_model_fz_solver.cc:108
operations_research::ChangeValue::ChangeValue
ChangeValue(const std::vector< IntVar * > &vars)
Definition: local_search.cc:293
operations_research::MakeActiveAndRelocate
Definition: local_search.cc:1181
operations_research::TwoOpt::IsIncremental
bool IsIncremental() const override
Definition: local_search.cc:875
operations_research::RegularLimit::MakeIdenticalClone
RegularLimit * MakeIdenticalClone() const
Definition: search.cc:3982
operations_research::Solver::ActiveSearch
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
Definition: constraint_solver.cc:1127
operations_research::PathOperator::OldNext
int64 OldNext(int64 node) const
Definition: constraint_solveri.h:1443
name
const std::string name
Definition: default_search.cc:808
operations_research::NeighborhoodLimit::NeighborhoodLimit
NeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
Definition: local_search.cc:1853
operations_research::NeighborhoodLimit::HoldsDelta
bool HoldsDelta() const override
Definition: local_search.cc:1872
operations_research::Solver::LocalSearchOperators
LocalSearchOperators
This enum is used in Solver::MakeOperator to specify the neighborhood to create.
Definition: constraint_solver.h:429
operations_research::PathOperator::InitPosition
virtual bool InitPosition() const
Returns true if the operator needs to restart its initial position at each call to Start()
Definition: constraint_solveri.h:1498
operations_research::Solver::EXCHANGE
@ EXCHANGE
Operator which exchanges the positions of two nodes.
Definition: constraint_solver.h:467
operations_research::PathOperator::Path
int64 Path(int64 node) const
Returns the index of the path to which node belongs in the current delta.
Definition: constraint_solveri.h:1360
operations_research::Solver::TSPLNS
@ TSPLNS
TSP-base LNS.
Definition: constraint_solver.h:588
kint64max
static const int64 kint64max
Definition: integral_types.h:62
operations_research::PathOperator::MakeChainInactive
bool MakeChainInactive(int64 before_chain, int64 chain_end)
Makes the nodes on the chain starting after before_chain and ending at chain_end inactive.
Definition: local_search.cc:467
operations_research::Solver::RELOCATE
@ RELOCATE
Relocate neighborhood with length of 1 (see OROPT comment).
Definition: constraint_solver.h:458
operations_research::MakeActiveAndRelocate::~MakeActiveAndRelocate
~MakeActiveAndRelocate() override
Definition: local_search.cc:1188
operations_research::Solver::GetLocalSearchStatistics
LocalSearchStatistics GetLocalSearchStatistics() const
Returns detailed local search statistics.
Definition: local_search.cc:3850
operations_research::LocalSearchState::AddVariable
LocalSearchVariable AddVariable(int64 initial_min, int64 initial_max)
Definition: local_search.cc:3539
operations_research::SolutionPool::RegisterNewSolution
virtual void RegisterNewSolution(Assignment *const assignment)=0
This method is called when a new solution has been accepted by the local search.
operations_research::Solver::MakeRestoreAssignment
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
Definition: constraint_solver/assignment.cc:1081
gtl::ContainsKey
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
operations_research::Cross::DebugString
std::string DebugString() const override
Definition: local_search.cc:1046
operations_research::PathOperator::ReverseChain
bool ReverseChain(int64 before_chain, int64 after_chain, int64 *chain_last)
Reverses the chain starting after before_chain and ending before after_chain.
Definition: local_search.cc:434
operations_research::ExtendedSwapActiveOperator::~ExtendedSwapActiveOperator
~ExtendedSwapActiveOperator() override
Definition: local_search.cc:1348
operations_research::IntVarLocalSearchFilter::OnSynchronize
virtual void OnSynchronize(const Assignment *delta)
Definition: constraint_solveri.h:1840
operations_research::LocalSearchOperator::HasFragments
virtual bool HasFragments() const
Definition: constraint_solveri.h:808
operations_research::IntVarLocalSearchFilter::FindIndex
bool FindIndex(IntVar *const var, int64 *index) const
Definition: constraint_solveri.h:1820
synchronized_costs_
int64 *const synchronized_costs_
Definition: local_search.cc:3389
operations_research::Decision
A Decision represents a choice point in the search tree.
Definition: constraint_solver.h:3223