OR-Tools  8.2
local_search.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#include <algorithm>
15#include <iterator>
16#include <map>
17#include <memory>
18#include <numeric>
19#include <set>
20#include <string>
21#include <utility>
22#include <vector>
23
24#include "absl/container/flat_hash_map.h"
25#include "absl/container/flat_hash_set.h"
26#include "absl/memory/memory.h"
27#include "absl/random/distributions.h"
28#include "absl/random/random.h"
29#include "absl/strings/str_cat.h"
31#include "ortools/base/hash.h"
35#include "ortools/base/macros.h"
41
42ABSL_FLAG(int, cp_local_search_sync_frequency, 16,
43 "Frequency of checks for better solutions in the solution pool.");
44
45ABSL_FLAG(int, cp_local_search_tsp_opt_size, 13,
46 "Size of TSPs solved in the TSPOpt operator.");
47
48ABSL_FLAG(int, cp_local_search_tsp_lns_size, 10,
49 "Size of TSPs solved in the TSPLns operator.");
50
51ABSL_FLAG(bool, cp_use_empty_path_symmetry_breaker, true,
52 "If true, equivalent empty paths are removed from the neighborhood "
53 "of PathOperators");
54
55namespace 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.
61bool 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).
65bool AcceptDelta(Search* const search, Assignment* delta,
66 Assignment* deltadelta);
67
68// Notifies the search that a neighbor has been accepted by local search.
69void AcceptNeighbor(Search* const search);
70void 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
99BaseLns::BaseLns(const std::vector<IntVar*>& 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
115void BaseLns::OnStart() { InitFragments(); }
116
118
120 if (index >= 0 && index < Size()) {
121 fragment_.push_back(index);
122 }
123}
124
125int BaseLns::FragmentSize() const { return fragment_.size(); }
126
127// ----- Simple Large Neighborhood Search operator -----
128
129// Frees number_of_variables (contiguous in vars) variables.
130
131namespace {
132class 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
148bool 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
164class 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
182bool 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.
206namespace {
207class 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
293ChangeValue::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
309void ChangeValue::OnStart() { index_ = 0; }
310
311// Increments the current value of variables.
312
313namespace {
314class 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
326class 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
339PathOperator::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
378void PathOperator::Reset() { optimal_paths_.clear(); }
379
380void 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
411bool 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
434bool 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
457bool 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
467bool 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
490bool 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
632void 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();
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
750void 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
757void 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) {
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
797void 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
811bool 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).
833bool 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
864class 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
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
935class 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
1000class 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
1036class 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
1096void 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)) {}
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)) {}
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
1375class 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
1393TSPOpt::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
1443class 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
1471TSPLns::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);
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
1624const std::vector<int>& NearestNeighbors::Neighbors(int index) const {
1625 return neighbors_[index];
1626}
1627
1628void 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
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
1679LinKernighan::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
1689void 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
1749const int LinKernighan::kNeighbors = 5 + 1;
1750
1751bool 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
1781class 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
1825void 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
1836void 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
1889namespace {
1890class 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
1941CompoundOperator::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
1961void CompoundOperator::Reset() {
1962 for (LocalSearchOperator* const op : operators_) {
1963 op->Reset();
1964 }
1965}
1966
1967void 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
1977bool 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
2004int64 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
2010int64 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
2038namespace {
2039class 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
2059void RandomCompoundOperator::Start(const Assignment* assignment) {
2060 for (LocalSearchOperator* const op : operators_) {
2061 op->Start(assignment);
2062 }
2063}
2064
2065RandomCompoundOperator::RandomCompoundOperator(
2066 std::vector<LocalSearchOperator*> operators)
2067 : RandomCompoundOperator(std::move(operators), CpRandomSeed()) {}
2068
2069RandomCompoundOperator::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
2080void RandomCompoundOperator::Reset() {
2081 for (LocalSearchOperator* const op : operators_) {
2082 op->Reset();
2083 }
2084}
2085
2086bool 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
2115namespace {
2116class 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
2162MultiArmedBanditCompoundOperator::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
2192void MultiArmedBanditCompoundOperator::Reset() {
2193 for (LocalSearchOperator* const op : operators_) {
2194 op->Reset();
2195 }
2196}
2197
2198double 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
2205void 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
2240bool 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
2276template <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
2299MAKE_LOCAL_SEARCH_OPERATOR(MakeActiveOperator)
2300MAKE_LOCAL_SEARCH_OPERATOR(MakeInactiveOperator)
2301MAKE_LOCAL_SEARCH_OPERATOR(MakeChainInactiveOperator)
2302MAKE_LOCAL_SEARCH_OPERATOR(SwapActiveOperator)
2303MAKE_LOCAL_SEARCH_OPERATOR(ExtendedSwapActiveOperator)
2304MAKE_LOCAL_SEARCH_OPERATOR(MakeActiveAndRelocate)
2305MAKE_LOCAL_SEARCH_OPERATOR(RelocateAndMakeActiveOperator)
2306MAKE_LOCAL_SEARCH_OPERATOR(RelocateAndMakeInactiveOperator)
2307
2308#undef MAKE_LOCAL_SEARCH_OPERATOR
2309
2310LocalSearchOperator* 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
2463namespace {
2464// Classes for Local Search Operation used in Local Search filters.
2465
2466class 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
2479class 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
2496class 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
2510class 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.
2525class 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
2541namespace {
2542// Never accepts deltas, cost 0.
2543class 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
2559PathState::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
2611void 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
2657void 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
2772void 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.
2791void 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
2817void 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
2846namespace {
2847
2848class 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
2873PathStateFilter::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
2894void 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
2914void 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.
2938void 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
2949void 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
3070void 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
3078void 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
3091void 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
3119void 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].
3146UnaryDimensionChecker::Interval
3147UnaryDimensionChecker::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
3164bool 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
3172namespace {
3173
3174class 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
3202namespace {
3203// ----- Variable domain filter -----
3204// Rejects assignments to values outside the domain of variables
3205
3206class 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
3218bool 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
3239const int IntVarLocalSearchFilter::kUnassigned = -1;
3240
3242 const std::vector<IntVar*>& vars) {
3243 AddVars(vars);
3244}
3245
3246void 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.
3306namespace {
3307class SumObjectiveFilter : public IntVarLocalSearchFilter {
3308 public:
3309 SumObjectiveFilter(const std::vector<IntVar*>& 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 {
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
3432class BinaryObjectiveFilter : public SumObjectiveFilter {
3433 public:
3434 BinaryObjectiveFilter(const std::vector<IntVar*>& vars,
3435 Solver::IndexEvaluator2 value_evaluator,
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
3466class TernaryObjectiveFilter : public SumObjectiveFilter {
3467 public:
3468 TernaryObjectiveFilter(const std::vector<IntVar*>& vars,
3469 const std::vector<IntVar*>& secondary_vars,
3470 Solver::IndexEvaluator3 value_evaluator,
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
3551void 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
3562int64 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
3568int64 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
3574bool 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
3586bool 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 {}
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
3841void DeleteLocalSearchProfiler(LocalSearchProfiler* monitor) { delete monitor; }
3842
3843std::string Solver::LocalSearchProfile() const {
3844 if (local_search_profiler_ != nullptr) {
3845 return local_search_profiler_->PrintOverview();
3846 }
3847 return "";
3848}
3849
3850LocalSearchStatistics Solver::GetLocalSearchStatistics() const {
3851 if (local_search_profiler_ != nullptr) {
3852 return local_search_profiler_->ExportToLocalSearchStatistics();
3853 }
3854 return LocalSearchStatistics();
3855}
3856
3857void 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
4268bool 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
4277void 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
4380namespace {
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
4390class 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
4411NestedSolveDecision::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
4421NestedSolveDecision::NestedSolveDecision(DecisionBuilder* const db,
4422 bool restore)
4423 : db_(db), restore_(restore), state_(DECISION_PENDING) {
4424 CHECK(nullptr != db);
4425}
4426
4427void 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
4444void 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
4455class 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
4506LocalSearch::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
4532LocalSearch::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
4559LocalSearch::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
4586LocalSearch::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
4613LocalSearch::~LocalSearch() {}
4614
4615// Model Visitor support.
4616void 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
4648Decision* 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
4699namespace {
4700class 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
4719void 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
4733void 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
4742class DefaultSolutionPool : public SolutionPool {
4743 public:
4744 DefaultSolutionPool() {}
4745
4746 ~DefaultSolutionPool() override {}
4747
4748 void Initialize(Assignment* const assignment) override {
4749 reference_assignment_ = absl::make_unique<Assignment>(assignment);
4750 }
4751
4752 void RegisterNewSolution(Assignment* const assignment) override {
4753 reference_assignment_->CopyIntersection(assignment);
4754 }
4755
4756 void GetNextSolution(Assignment* const assignment) override {
4757 assignment->CopyIntersection(reference_assignment_.get());
4758 }
4759
4760 bool SyncNeeded(Assignment* const local_assignment) override { return false; }
4761
4762 std::string DebugString() const override { return "DefaultSolutionPool"; }
4763
4764 private:
4765 std::unique_ptr<Assignment> reference_assignment_;
4766};
4767} // namespace
4768
4770 return RevAlloc(new DefaultSolutionPool());
4771}
4772
4775 return RevAlloc(new LocalSearch(
4776 assignment, parameters->objective(), parameters->solution_pool(),
4777 parameters->ls_operator(), parameters->sub_decision_builder(),
4778 parameters->limit(), parameters->filter_manager()));
4779}
4780
4782 const std::vector<IntVar*>& vars, DecisionBuilder* first_solution,
4784 return RevAlloc(new LocalSearch(
4785 vars, parameters->objective(), parameters->solution_pool(),
4786 first_solution, parameters->ls_operator(),
4787 parameters->sub_decision_builder(), parameters->limit(),
4788 parameters->filter_manager()));
4789}
4790
4792 const std::vector<IntVar*>& vars, DecisionBuilder* first_solution,
4793 DecisionBuilder* first_solution_sub_decision_builder,
4795 return RevAlloc(new LocalSearch(
4796 vars, parameters->objective(), parameters->solution_pool(),
4797 first_solution, first_solution_sub_decision_builder,
4798 parameters->ls_operator(), parameters->sub_decision_builder(),
4799 parameters->limit(), parameters->filter_manager()));
4800}
4801
4803 const std::vector<SequenceVar*>& vars, DecisionBuilder* first_solution,
4805 return RevAlloc(new LocalSearch(
4806 vars, parameters->objective(), parameters->solution_pool(),
4807 first_solution, parameters->ls_operator(),
4808 parameters->sub_decision_builder(), parameters->limit(),
4809 parameters->filter_manager()));
4810}
4811} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define VLOG(verboselevel)
Definition: base/logging.h:978
void Start()
Definition: timer.h:31
void Stop()
Definition: timer.h:39
double Get() const
Definition: timer.h:45
const E & Element(const V *const var) const
const std::vector< E > & elements() const
An Assignment is a variable -> domains mapping, used to report solutions to the user.
const IntervalContainer & IntervalVarContainer() const
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
AssignmentContainer< IntVar, IntVarElement > IntContainer
const IntContainer & IntVarContainer() const
BaseInactiveNodeToPathOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_base_nodes, std::function< int(int64)> start_empty_path_class)
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
This is the base class for building an Lns operator.
virtual bool NextFragment()=0
void AppendToFragment(int index)
BaseLns(const std::vector< IntVar * > &vars)
Definition: local_search.cc:99
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
A BaseObject is the root of all reversibly allocated objects.
virtual std::string DebugString() const
void Set(IndexType i)
Definition: bitset.h:491
ChangeValue(const std::vector< IntVar * > &vars)
virtual int64 ModifyValue(int64 index, int64 value)=0
bool MakeOneNeighbor() override
This method should not be overridden. Override ModifyValue() instead.
bool MakeNeighbor() override
Cross(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
A DecisionBuilder is responsible for creating the search tree.
A Decision represents a choice point in the search tree.
Exchange(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
ExtendedSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
FindOneNeighbor(Assignment *const assignment, IntVar *objective, SolutionPool *const pool, LocalSearchOperator *const ls_operator, DecisionBuilder *const sub_decision_builder, const RegularLimit *const limit, LocalSearchFilterManager *filter_manager)
Decision * Next(Solver *const solver) override
This is the main method of the decision builder class.
std::string DebugString() const override
virtual int64 Max() const =0
virtual int64 Min() const =0
The class IntVar is a subset of IntExpr.
void SynchronizeOnAssignment(const Assignment *assignment)
virtual void OnSynchronize(const Assignment *delta)
bool FindIndex(IntVar *const var, int64 *index) const
void Synchronize(const Assignment *assignment, const Assignment *delta) override
This method should not be overridden.
IntVarLocalSearchFilter(const std::vector< IntVar * > &vars)
void AddVars(const std::vector< IntVar * > &vars)
Add variables to "track" to the filter.
Specialization of LocalSearchOperator built from an array of IntVars which specifies the scope of the...
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
Definition: local_search.cc:74
virtual bool MakeOneNeighbor()
Creates a new neighbor.
Definition: local_search.cc:95
LinKernighan(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)
std::string DebugString() const override
Local Search Filters are used for fast neighbor pruning.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
LocalSearchFilterManager(std::vector< FilterEvent > filter_events)
bool Accept(LocalSearchMonitor *const monitor, const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max)
Returns true iff all filters return true, and the sum of their accepted objectives is between objecti...
void Synchronize(const Assignment *assignment, const Assignment *delta)
Synchronizes all filters to assignment.
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
The base class for all local search operators.
virtual const LocalSearchOperator * Self() const
virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0
virtual void Start(const Assignment *assignment)=0
LocalSearchFilterManager *const filter_manager() const
LocalSearchPhaseParameters(IntVar *objective, SolutionPool *const pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, RegularLimit *const limit, LocalSearchFilterManager *filter_manager)
void BeginFiltering(const LocalSearchFilter *filter) override
void Install() override
Install itself on the solver.
void BeginOperatorStart() override
Local search operator events.
void RestartSearch() override
Restart the search.
void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta) override
LocalSearchStatistics ExportToLocalSearchStatistics() const
void BeginMakeNextNeighbor(const LocalSearchOperator *op) override
void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
void BeginAcceptNeighbor(const LocalSearchOperator *op) override
void ExitSearch() override
End of the search.
void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found) override
void EndFiltering(const LocalSearchFilter *filter, bool reject) override
void BeginFilterNeighbor(const LocalSearchOperator *op) override
std::string DebugString() const override
LocalSearchVariable AddVariable(int64 initial_min, int64 initial_max)
MakeActiveAndRelocate(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
MakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
MakeChainInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
MakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
static const char kVariableGroupExtension[]
const std::vector< int > & Neighbors(int index) const
NearestNeighbors(Solver::IndexEvaluator3 evaluator, const PathOperator &path_operator, int size)
virtual std::string DebugString() const
NeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
void Start(const Assignment *assignment) override
std::string DebugString() const override
PathLns(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments)
bool HasFragments() const override
std::string DebugString() const override
Base class of the local search operators dedicated to path modifications (a path is a set of nodes li...
bool SwapActiveAndInactive(int64 active, int64 inactive)
Replaces active by inactive in the current path, making active inactive.
int PathClass(int i) const
Returns the class of the path of the ith base node.
virtual void OnNodeInitialization()
Called by OnStart() after initializing node information.
int64 BaseNode(int i) const
Returns the ith base node of the operator.
bool IsInactive(int64 node) const
Returns true if node is inactive.
int number_of_nexts() const
Number of next variables.
bool IsPathEnd(int64 node) const
Returns true if node is the last node on the path; defined by the fact that node is outside the range...
virtual bool ConsiderAlternatives(int64 base_index) const
Indicates if alternatives should be considered when iterating over base nodes.
virtual bool RestartAtPathStartOnSynchronize()
When the operator is being synchronized with a new solution (when Start() is called),...
bool ReverseChain(int64 before_chain, int64 after_chain, int64 *chain_last)
Reverses the chain starting after before_chain and ending before after_chain.
void SetNext(int64 from, int64 to, int64 path)
Sets 'to' to be the node after 'from' on the given path.
bool MakeActive(int64 node, int64 destination)
Insert the inactive node after destination.
int64 Prev(int64 node) const
Returns the node before node in the current delta.
int64 StartNode(int i) const
Returns the start node of the ith base node.
bool SkipUnchanged(int index) const override
int64 Next(int64 node) const
Returns the node after node in the current delta.
void ResetPosition()
Reset the position of the operator to its position when Start() was last called; this can be used to ...
virtual int64 GetBaseNodeRestartPosition(int base_index)
Returns the index of the node to which the base node of index base_index must be set to when it reach...
int GetSiblingAlternativeIndex(int node) const
Returns the index of the alternative set of the sibling of node.
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
virtual bool OnSamePathAsPreviousBase(int64 base_index)
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
bool MakeChainInactive(int64 before_chain, int64 chain_end)
Makes the nodes on the chain starting after before_chain and ending at chain_end inactive.
virtual bool InitPosition() const
Returns true if the operator needs to restart its initial position at each call to Start()
int64 Path(int64 node) const
Returns the index of the path to which node belongs in the current delta.
bool CheckChainValidity(int64 before_chain, int64 chain_end, int64 exclude) const
Returns true if the chain is a valid path without cycles from before_chain to chain_end and does not ...
PathOperator(const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, int number_of_base_nodes, bool skip_locally_optimal_paths, bool accept_path_end_base, std::function< int(int64)> start_empty_path_class)
Builds an instance of PathOperator from next and path variables.
bool MoveChain(int64 before_chain, int64 chain_end, int64 destination)
Moves the chain starting after the node before_chain and ending at the node chain_end after the node ...
const std::vector< int > & ChangedPaths() const
NodeRange Nodes(int path) const
const std::vector< std::pair< int, int > > & ChangedArcs() const
ChainRange Chains(int path) const
PathState(int num_nodes, std::vector< int > path_start, std::vector< int > path_end)
Usual limit based on wall_time, number of explored branches and number of failures in the search tree...
bool Check() override
This method is called to check the status of the limit.
Definition: search.cc:3988
void Init() override
This method is called when the search limit is initialized.
Definition: search.cc:4009
void Copy(const SearchLimit *const limit) override
Copy a limit.
Definition: search.cc:3969
RegularLimit * MakeIdenticalClone() const
Definition: search.cc:3982
RelocateAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
RelocateAndMakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Relocate(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const std::string &name, std::function< int(int64)> start_empty_path_class, int64 chain_length=1LL, bool single_path=false)
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
std::string DebugString() const override
Relocate(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, int64 chain_length=1LL, bool single_path=false)
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
This class is used to manage a pool of solutions.
virtual bool SyncNeeded(Assignment *const local_assignment)=0
This method checks if the local solution needs to be updated with an external one.
virtual void RegisterNewSolution(Assignment *const assignment)=0
This method is called when a new solution has been accepted by the local search.
virtual void GetNextSolution(Assignment *const assignment)=0
This method is called when the local search starts a new neighborhood to initialize the default assig...
virtual void Initialize(Assignment *const assignment)=0
This method is called to initialize the solution pool with the assignment from the local search.
LocalSearchFilter * MakeVariableDomainFilter()
RegularLimit * MakeSolutionsLimit(int64 solutions)
Creates a search limit that constrains the number of solutions found during the search.
Definition: search.cc:4105
bool SolveAndCommit(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolveAndCommit using a decision builder and up to three search monitors, usually one for the objectiv...
LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)
Creates a local search operator that tries to move the assignment of some variables toward a target.
LocalSearchStatistics GetLocalSearchStatistics() const
Returns detailed local search statistics.
ConstraintSolverParameters parameters() const
Stored Parameters.
void SetSearchContext(Search *search, const std::string &search_context)
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Creates a local search operator which concatenates a vector of operators.
LocalSearchFilter * MakeRejectFilter()
LocalSearchFilter * MakeAcceptFilter()
Local Search Filters.
LocalSearchOperator * MakeRandomLnsOperator(const std::vector< IntVar * > &vars, int number_of_variables)
Creates a large neighborhood search operator which creates fragments (set of relaxed variables) with ...
LocalSearchOperator * RandomConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Randomized version of local search concatenator; calls a random operator at each call to MakeNextNeig...
LocalSearchOperators
This enum is used in Solver::MakeOperator to specify the neighborhood to create.
@ EXCHANGE
Operator which exchanges the positions of two nodes.
@ MAKEINACTIVE
Operator which makes path nodes inactive.
@ RELOCATE
Relocate neighborhood with length of 1 (see OROPT comment).
@ SWAPACTIVE
Operator which replaces an active node by an inactive one.
@ SIMPLELNS
Operator which defines one neighbor per variable.
@ INCREMENT
Operator which defines one neighbor per variable.
@ MAKECHAININACTIVE
Operator which makes a "chain" of path nodes inactive.
@ TWOOPT
Operator which reverses a sub-chain of a path.
@ FULLPATHLNS
Operator which relaxes one entire path and all inactive nodes, thus defining num_paths neighbors.
@ EXTENDEDSWAPACTIVE
Operator which makes an inactive node active and an active one inactive.
@ OROPT
Relocate: OROPT and RELOCATE.
@ PATHLNS
Operator which relaxes two sub-chains of three consecutive arcs each.
@ UNACTIVELNS
Operator which relaxes all inactive nodes and one sub-chain of six consecutive arcs.
@ MAKEACTIVE
Operator which inserts an inactive node into a path.
@ DECREMENT
Operator which defines a neighborhood to decrement values.
@ CROSS
Operator which cross exchanges the starting chains of 2 paths, including exchanging the whole paths.
LocalSearchPhaseParameters * MakeLocalSearchPhaseParameters(IntVar *objective, LocalSearchOperator *const ls_operator, DecisionBuilder *const sub_decision_builder)
Local Search Phase Parameters.
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
IntVarLocalSearchFilter * MakeSumObjectiveFilter(const std::vector< IntVar * > &vars, IndexEvaluator2 values, Solver::LocalSearchFilterBound filter_enum)
LocalSearchOperator * MakeNeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
Creates a local search operator that wraps another local search operator and limits the number of nei...
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
std::function< int64(int64, int64, int64)> IndexEvaluator3
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
SolutionPool * MakeDefaultSolutionPool()
Solution Pool.
bool UseFastLocalSearch() const
Returns true if fast local search is enabled.
LocalSearchOperator * MakeOperator(const std::vector< IntVar * > &vars, LocalSearchOperators op)
Local Search Operators.
std::string LocalSearchProfile() const
Returns local search profiling information in a human readable format.
Solver(const std::string &name)
Solver API.
std::function< int64(int64, int64)> IndexEvaluator2
DecisionBuilder * MakeLocalSearchPhase(Assignment *const assignment, LocalSearchPhaseParameters *const parameters)
Local Search decision builders factories.
LocalSearchOperator * MultiArmedBanditConcatenateOperators(const std::vector< LocalSearchOperator * > &ops, double memory_coefficient, double exploration_coefficient, bool maximize)
Creates a local search operator which concatenates a vector of operators.
Assignment * MakeAssignment()
This method creates an empty assignment.
DecisionBuilder * Compose(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which sequentially composes decision builders.
Definition: search.cc:552
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which stores an Assignment (calls void Assignment::Store())
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
T * RevAlloc(T *object)
Registers the given object as being reversible.
EvaluatorLocalSearchOperators
This enum is used in Solver::MakeOperator associated with an evaluator to specify the neighborhood to...
@ TSPOPT
Sliding TSP operator.
@ LK
Lin-Kernighan local search.
LocalSearchFilterBound
This enum is used in Solver::MakeLocalSearchObjectiveFilter.
@ GE
Move is accepted when the current objective value >= objective.Min.
@ LE
Move is accepted when the current objective value <= objective.Max.
@ EQ
Move is accepted when the current objective value is in the interval objective.Min .
SwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
std::string DebugString() const override
TSPLns(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
std::string DebugString() const override
TSPOpt(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)
std::string DebugString() const override
bool MakeNeighbor() override
bool IsIncremental() const override
TwoOpt(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
std::string DebugString() const override
UnaryDimensionChecker(const PathState *path_state, std::vector< Interval > path_capacity, std::vector< int > path_class, std::vector< std::vector< Interval > > demand, std::vector< Interval > node_capacity)
IntVar * Var(int64 index) const
Returns the variable of given index.
const int64 & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
Block * next
SatParameters parameters
SharedBoundsManager * bounds
const std::string name
int64 value
IntVar * var
Definition: expr_array.cc:1858
const int64 limit_
int int32
static const int64 kint64max
int64_t int64
static const int64 kint64min
ABSL_FLAG(int, cp_local_search_sync_frequency, 16, "Frequency of checks for better solutions in the solution pool.")
int64 synchronized_sum_
Solver::LocalSearchFilterBound filter_enum_
int64 delta_sum_
int64 *const delta_costs_
const int primary_vars_size_
#define MAKE_LOCAL_SEARCH_OPERATOR(OperatorClass)
bool incremental_
int64 *const synchronized_costs_
const int ERROR
Definition: log_severity.h:32
const int FATAL
Definition: log_severity.h:32
RowIndex row
Definition: markowitz.cc:175
Definition: cleanup.h:22
ReverseView< Container > reversed_view(const Container &c)
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
Definition: map_util.h:176
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
void InstallLocalSearchProfiler(LocalSearchProfiler *monitor)
int64 CapSub(int64 x, int64 y)
void DeleteLocalSearchProfiler(LocalSearchProfiler *monitor)
bool AcceptDelta(Search *const search, Assignment *delta, Assignment *deltadelta)
int MostSignificantBitPosition32(uint32 n)
Definition: bitset.h:273
void AcceptNeighbor(Search *const search)
LocalSearchFilter * MakeUnaryDimensionFilter(Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)
LocalSearchOperator * MakeLocalSearchOperator(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Operator Factories.
LocalSearchFilter * MakePathStateFilter(Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)
bool LocalOptimumReached(Search *const search)
void AcceptUncheckedNeighbor(Search *const search)
LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)
STL namespace.
int index
Definition: pack.cc:508
int64 demand
Definition: resource.cc:123
int64 delta
Definition: resource.cc:1684
int64 cost
std::function< int64(int64, int64)> evaluator_
Definition: search.cc:1361
const bool maximize_
Definition: search.cc:2499
IntVar *const objective_
Definition: search.cc:2951