Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
constraint_solveri.h
Go to the documentation of this file.
1// Copyright 2010-2025 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
48
49#ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
50#define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
51
52#include <stdint.h>
53#include <string.h>
54
55#include <algorithm>
56#include <functional>
57#include <memory>
58#include <string>
59#include <tuple>
60#include <utility>
61#include <vector>
62
63#include "absl/algorithm/container.h"
64#include "absl/container/flat_hash_map.h"
65#include "absl/container/flat_hash_set.h"
66#include "absl/log/check.h"
67#include "absl/strings/str_cat.h"
68#include "absl/strings/str_format.h"
69#include "absl/time/time.h"
70#include "absl/types/span.h"
74#include "ortools/base/timer.h"
75#include "ortools/base/types.h"
77#include "ortools/util/bitset.h"
79
80namespace operations_research {
81
108
109class BaseIntExpr : public IntExpr {
110 public:
111 explicit BaseIntExpr(Solver* const s) : IntExpr(s), var_(nullptr) {}
112 ~BaseIntExpr() override {}
113
114 IntVar* Var() override;
115 virtual IntVar* CastToVar();
117 private:
118 IntVar* var_;
120
123enum VarTypes {
127 CONST_VAR,
141
143#ifndef SWIG
144template <class T>
145class SimpleRevFIFO {
146 private:
147 enum { CHUNK_SIZE = 16 }; // TODO(user): could be an extra template param
148 struct Chunk {
149 T data[CHUNK_SIZE];
150 const Chunk* const next;
151 explicit Chunk(const Chunk* next) : next(next) {}
152 };
153
154 public:
156 class Iterator {
157 public:
158 explicit Iterator(const SimpleRevFIFO<T>* l)
159 : chunk_(l->chunks_), value_(l->Last()) {}
160 bool ok() const { return (value_ != nullptr); }
161 T operator*() const { return *value_; }
162 void operator++() {
163 ++value_;
164 if (value_ == chunk_->data + CHUNK_SIZE) {
165 chunk_ = chunk_->next;
166 value_ = chunk_ ? chunk_->data : nullptr;
170 private:
171 const Chunk* chunk_;
172 const T* value_;
173 };
174
175 SimpleRevFIFO() : chunks_(nullptr), pos_(0) {}
176
177 void Push(Solver* const s, T val) {
178 if (pos_.Value() == 0) {
179 Chunk* const chunk = s->UnsafeRevAlloc(new Chunk(chunks_));
180 s->SaveAndSetValue(reinterpret_cast<void**>(&chunks_),
181 reinterpret_cast<void*>(chunk));
182 pos_.SetValue(s, CHUNK_SIZE - 1);
183 } else {
184 pos_.Decr(s);
185 }
186 chunks_->data[pos_.Value()] = val;
187 }
188
190 void PushIfNotTop(Solver* const s, T val) {
191 if (chunks_ == nullptr || LastValue() != val) {
192 Push(s, val);
193 }
194 }
195
197 const T* Last() const {
198 return chunks_ ? &chunks_->data[pos_.Value()] : nullptr;
199 }
200
201 T* MutableLast() { return chunks_ ? &chunks_->data[pos_.Value()] : nullptr; }
202
204 const T& LastValue() const {
205 DCHECK(chunks_);
206 return chunks_->data[pos_.Value()];
207 }
210 void SetLastValue(const T& v) {
211 DCHECK(Last());
212 chunks_->data[pos_.Value()] = v;
213 }
214
215 private:
216 Chunk* chunks_;
218};
219
221// TODO(user): use murmurhash.
222inline uint64_t Hash1(uint64_t value) {
223 value = (~value) + (value << 21);
224 value ^= value >> 24;
225 value += (value << 3) + (value << 8);
226 value ^= value >> 14;
227 value += (value << 2) + (value << 4);
228 value ^= value >> 28;
229 value += (value << 31);
230 return value;
231}
232
233inline uint64_t Hash1(uint32_t value) {
234 uint64_t a = value;
235 a = (a + 0x7ed55d16) + (a << 12);
236 a = (a ^ 0xc761c23c) ^ (a >> 19);
237 a = (a + 0x165667b1) + (a << 5);
238 a = (a + 0xd3a2646c) ^ (a << 9);
239 a = (a + 0xfd7046c5) + (a << 3);
240 a = (a ^ 0xb55a4f09) ^ (a >> 16);
241 return a;
242}
243
244inline uint64_t Hash1(int64_t value) {
245 return Hash1(static_cast<uint64_t>(value));
246}
247
248inline uint64_t Hash1(int value) { return Hash1(static_cast<uint32_t>(value)); }
249
250inline uint64_t Hash1(void* const ptr) {
251#if defined(__x86_64__) || defined(_M_X64) || defined(__powerpc64__) || \
252 defined(__aarch64__) || (defined(_MIPS_SZPTR) && (_MIPS_SZPTR == 64))
253 return Hash1(reinterpret_cast<uint64_t>(ptr));
254#else
255 return Hash1(reinterpret_cast<uint32_t>(ptr));
256#endif
258
259template <class T>
260uint64_t Hash1(const std::vector<T*>& ptrs) {
261 if (ptrs.empty()) return 0;
262 if (ptrs.size() == 1) return Hash1(ptrs[0]);
263 uint64_t hash = Hash1(ptrs[0]);
264 for (int i = 1; i < ptrs.size(); ++i) {
265 hash = hash * i + Hash1(ptrs[i]);
266 }
267 return hash;
268}
269
270inline uint64_t Hash1(const std::vector<int64_t>& ptrs) {
271 if (ptrs.empty()) return 0;
272 if (ptrs.size() == 1) return Hash1(ptrs[0]);
273 uint64_t hash = Hash1(ptrs[0]);
274 for (int i = 1; i < ptrs.size(); ++i) {
275 hash = hash * i + Hash1(ptrs[i]);
276 }
277 return hash;
278}
279
282template <class K, class V>
283class RevImmutableMultiMap {
284 public:
285 RevImmutableMultiMap(Solver* const solver, int initial_size)
286 : solver_(solver),
287 array_(solver->UnsafeRevAllocArray(new Cell*[initial_size])),
288 size_(initial_size),
289 num_items_(0) {
290 memset(array_, 0, sizeof(*array_) * size_.Value());
291 }
294
295 int num_items() const { return num_items_.Value(); }
296
298 bool ContainsKey(const K& key) const {
299 uint64_t code = Hash1(key) % size_.Value();
300 Cell* tmp = array_[code];
301 while (tmp) {
302 if (tmp->key() == key) {
303 return true;
304 }
305 tmp = tmp->next();
306 }
307 return false;
308 }
309
313 const V& FindWithDefault(const K& key, const V& default_value) const {
314 uint64_t code = Hash1(key) % size_.Value();
315 Cell* tmp = array_[code];
316 while (tmp) {
317 if (tmp->key() == key) {
318 return tmp->value();
319 }
320 tmp = tmp->next();
321 }
322 return default_value;
323 }
324
326 void Insert(const K& key, const V& value) {
327 const int position = Hash1(key) % size_.Value();
328 Cell* const cell =
329 solver_->UnsafeRevAlloc(new Cell(key, value, array_[position]));
330 solver_->SaveAndSetValue(reinterpret_cast<void**>(&array_[position]),
331 reinterpret_cast<void*>(cell));
332 num_items_.Incr(solver_);
333 if (num_items_.Value() > 2 * size_.Value()) {
334 Double();
335 }
336 }
337
338 private:
339 class Cell {
340 public:
341 Cell(const K& key, const V& value, Cell* const next)
342 : key_(key), value_(value), next_(next) {}
343
344 void SetRevNext(Solver* const solver, Cell* const next) {
345 solver->SaveAndSetValue(reinterpret_cast<void**>(&next_),
346 reinterpret_cast<void*>(next));
347 }
348
349 Cell* next() const { return next_; }
350
351 const K& key() const { return key_; }
352
353 const V& value() const { return value_; }
354
355 private:
356 const K key_;
357 const V value_;
358 Cell* next_;
359 };
360
361 void Double() {
362 Cell** const old_cell_array = array_;
363 const int old_size = size_.Value();
364 size_.SetValue(solver_, size_.Value() * 2);
365 solver_->SaveAndSetValue(
366 reinterpret_cast<void**>(&array_),
367 reinterpret_cast<void*>(
368 solver_->UnsafeRevAllocArray(new Cell*[size_.Value()])));
369 memset(array_, 0, size_.Value() * sizeof(*array_));
370 for (int i = 0; i < old_size; ++i) {
371 Cell* tmp = old_cell_array[i];
372 while (tmp != nullptr) {
373 Cell* const to_reinsert = tmp;
374 tmp = tmp->next();
375 const uint64_t new_position = Hash1(to_reinsert->key()) % size_.Value();
376 to_reinsert->SetRevNext(solver_, array_[new_position]);
377 solver_->SaveAndSetValue(
378 reinterpret_cast<void**>(&array_[new_position]),
379 reinterpret_cast<void*>(to_reinsert));
380 }
381 }
382 }
383
384 Solver* const solver_;
385 Cell** array_;
386 NumericalRev<int> size_;
387 NumericalRev<int> num_items_;
388};
389
391class RevSwitch {
392 public:
393 RevSwitch() : value_(false) {}
394
395 bool Switched() const { return value_; }
396
397 void Switch(Solver* const solver) { solver->SaveAndSetValue(&value_, true); }
399 private:
400 bool value_;
401};
405class SmallRevBitSet {
406 public:
407 explicit SmallRevBitSet(int64_t size);
409 void SetToOne(Solver* solver, int64_t pos);
411 void SetToZero(Solver* solver, int64_t pos);
412 /// Returns the number of bits set to one.
413 int64_t Cardinality() const;
415 bool IsCardinalityZero() const { return bits_.Value() == uint64_t{0}; }
417 bool IsCardinalityOne() const {
418 return (bits_.Value() != 0) && !(bits_.Value() & (bits_.Value() - 1));
419 }
422 int64_t GetFirstOne() const;
423
424 private:
425 Rev<uint64_t> bits_;
426};
427
430class RevBitSet {
431 public:
432 explicit RevBitSet(int64_t size);
433 ~RevBitSet();
434
436 void SetToOne(Solver* solver, int64_t index);
437 /// Erases the 'index' bit.
438 void SetToZero(Solver* solver, int64_t index);
440 bool IsSet(int64_t index) const;
442 int64_t Cardinality() const;
444 bool IsCardinalityZero() const;
446 bool IsCardinalityOne() const;
449 int64_t GetFirstBit(int start) const;
451 void ClearAll(Solver* solver);
452
453 friend class RevBitMatrix;
454
455 private:
457 void Save(Solver* solver, int offset);
458 const int64_t size_;
459 const int64_t length_;
460 uint64_t* bits_;
461 uint64_t* stamps_;
462};
463
465class RevBitMatrix : private RevBitSet {
466 public:
467 RevBitMatrix(int64_t rows, int64_t columns);
469
470
471 void SetToOne(Solver* solver, int64_t row, int64_t column);
472 /// Erases the 'column' bit in the 'row' row.
473 void SetToZero(Solver* solver, int64_t row, int64_t column);
475 bool IsSet(int64_t row, int64_t column) const {
476 DCHECK_GE(row, 0);
477 DCHECK_LT(row, rows_);
478 DCHECK_GE(column, 0);
479 DCHECK_LT(column, columns_);
480 return RevBitSet::IsSet(row * columns_ + column);
481 }
482 /// Returns the number of bits set to one in the 'row' row.
483 int64_t Cardinality(int row) const;
485 bool IsCardinalityZero(int row) const;
487 bool IsCardinalityOne(int row) const;
489
490 int64_t GetFirstBit(int row, int start) const;
492 void ClearAll(Solver* solver);
493
494 private:
495 const int64_t rows_;
496 const int64_t columns_;
497};
498
504
505
506template <class T>
507class CallMethod0 : public Demon {
508 public:
509 CallMethod0(T* const ct, void (T::*method)(), const std::string& name)
510 : constraint_(ct), method_(method), name_(name) {}
511
512 ~CallMethod0() override {}
513
514 void Run(Solver* const) override { (constraint_->*method_)(); }
515
516 std::string DebugString() const override {
517 return "CallMethod_" + name_ + "(" + constraint_->DebugString() + ")";
518 }
520 private:
521 T* const constraint_;
522 void (T::* const method_)();
523 const std::string name_;
524};
525
526template <class T>
527Demon* MakeConstraintDemon0(Solver* const s, T* const ct, void (T::*method)(),
528 const std::string& name) {
529 return s->RevAlloc(new CallMethod0<T>(ct, method, name));
530}
531
532template <class P>
533std::string ParameterDebugString(P param) {
534 return absl::StrCat(param);
535}
536
538template <class P>
539std::string ParameterDebugString(P* param) {
540 return param->DebugString();
541}
542
543
544template <class T, class P>
545class CallMethod1 : public Demon {
546 public:
547 CallMethod1(T* const ct, void (T::*method)(P), const std::string& name,
548 P param1)
549 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
550
551 ~CallMethod1() override {}
553 void Run(Solver* const) override { (constraint_->*method_)(param1_); }
555 std::string DebugString() const override {
556 return absl::StrCat("CallMethod_", name_, "(", constraint_->DebugString(),
557 ", ", ParameterDebugString(param1_), ")");
559
560 private:
561 T* const constraint_;
562 void (T::* const method_)(P);
563 const std::string name_;
564 P param1_;
565};
566
567template <class T, class P>
568Demon* MakeConstraintDemon1(Solver* const s, T* const ct, void (T::*method)(P),
569 const std::string& name, P param1) {
570 return s->RevAlloc(new CallMethod1<T, P>(ct, method, name, param1));
571}
572
573
574template <class T, class P, class Q>
575class CallMethod2 : public Demon {
576 public:
577 CallMethod2(T* const ct, void (T::*method)(P, Q), const std::string& name,
578 P param1, Q param2)
579 : constraint_(ct),
580 method_(method),
581 name_(name),
582 param1_(param1),
583 param2_(param2) {}
585 ~CallMethod2() override {}
586
587 void Run(Solver* const) override {
588 (constraint_->*method_)(param1_, param2_);
589 }
590
591 std::string DebugString() const override {
592 return absl::StrCat("CallMethod_", name_, "(", constraint_->DebugString(),
593 ", ", ParameterDebugString(param1_), ", ",
594 ParameterDebugString(param2_), ")");
595 }
596
597 private:
598 T* const constraint_;
599 void (T::* const method_)(P, Q);
600 const std::string name_;
601 P param1_;
602 Q param2_;
603};
604
605template <class T, class P, class Q>
606Demon* MakeConstraintDemon2(Solver* const s, T* const ct,
607 void (T::*method)(P, Q), const std::string& name,
608 P param1, Q param2) {
609 return s->RevAlloc(
610 new CallMethod2<T, P, Q>(ct, method, name, param1, param2));
611}
613template <class T, class P, class Q, class R>
614class CallMethod3 : public Demon {
615 public:
616 CallMethod3(T* const ct, void (T::*method)(P, Q, R), const std::string& name,
617 P param1, Q param2, R param3)
618 : constraint_(ct),
619 method_(method),
620 name_(name),
621 param1_(param1),
622 param2_(param2),
623 param3_(param3) {}
624
625 ~CallMethod3() override {}
626
627 void Run(Solver* const) override {
628 (constraint_->*method_)(param1_, param2_, param3_);
629 }
630
631 std::string DebugString() const override {
632 return absl::StrCat(absl::StrCat("CallMethod_", name_),
633 absl::StrCat("(", constraint_->DebugString()),
634 absl::StrCat(", ", ParameterDebugString(param1_)),
635 absl::StrCat(", ", ParameterDebugString(param2_)),
636 absl::StrCat(", ", ParameterDebugString(param3_), ")"));
637 }
639 private:
640 T* const constraint_;
641 void (T::* const method_)(P, Q, R);
642 const std::string name_;
643 P param1_;
644 Q param2_;
645 R param3_;
646};
647
648template <class T, class P, class Q, class R>
649Demon* MakeConstraintDemon3(Solver* const s, T* const ct,
650 void (T::*method)(P, Q, R), const std::string& name,
651 P param1, Q param2, R param3) {
652 return s->RevAlloc(
653 new CallMethod3<T, P, Q, R>(ct, method, name, param1, param2, param3));
654}
661
662
663template <class T>
664class DelayedCallMethod0 : public Demon {
665 public:
666 DelayedCallMethod0(T* const ct, void (T::*method)(), const std::string& name)
667 : constraint_(ct), method_(method), name_(name) {}
668
669 ~DelayedCallMethod0() override {}
670
671 void Run(Solver* const) override { (constraint_->*method_)(); }
672
675 }
677 std::string DebugString() const override {
678 return "DelayedCallMethod_" + name_ + "(" + constraint_->DebugString() +
679 ")";
681
682 private:
683 T* const constraint_;
684 void (T::* const method_)();
685 const std::string name_;
686};
687
688template <class T>
689Demon* MakeDelayedConstraintDemon0(Solver* const s, T* const ct,
690 void (T::*method)(),
691 const std::string& name) {
692 return s->RevAlloc(new DelayedCallMethod0<T>(ct, method, name));
693}
694
696template <class T, class P>
697class DelayedCallMethod1 : public Demon {
698 public:
699 DelayedCallMethod1(T* const ct, void (T::*method)(P), const std::string& name,
700 P param1)
701 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
702
703 ~DelayedCallMethod1() override {}
705 void Run(Solver* const) override { (constraint_->*method_)(param1_); }
707 Solver::DemonPriority priority() const override {
709 }
711 std::string DebugString() const override {
712 return absl::StrCat("DelayedCallMethod_", name_, "(",
713 constraint_->DebugString(), ", ",
714 ParameterDebugString(param1_), ")");
715 }
716
717 private:
718 T* const constraint_;
719 void (T::* const method_)(P);
720 const std::string name_;
721 P param1_;
722};
723
724template <class T, class P>
725Demon* MakeDelayedConstraintDemon1(Solver* const s, T* const ct,
726 void (T::*method)(P),
727 const std::string& name, P param1) {
728 return s->RevAlloc(new DelayedCallMethod1<T, P>(ct, method, name, param1));
729}
730
732template <class T, class P, class Q>
733class DelayedCallMethod2 : public Demon {
734 public:
735 DelayedCallMethod2(T* const ct, void (T::*method)(P, Q),
736 const std::string& name, P param1, Q param2)
737 : constraint_(ct),
738 method_(method),
739 name_(name),
740 param1_(param1),
741 param2_(param2) {}
743 ~DelayedCallMethod2() override {}
744
745 void Run(Solver* const) override {
746 (constraint_->*method_)(param1_, param2_);
747 }
748
749 Solver::DemonPriority priority() const override {
751 }
753 std::string DebugString() const override {
754 return absl::StrCat(absl::StrCat("DelayedCallMethod_", name_),
755 absl::StrCat("(", constraint_->DebugString()),
756 absl::StrCat(", ", ParameterDebugString(param1_)),
757 absl::StrCat(", ", ParameterDebugString(param2_), ")"));
758 }
759
760 private:
761 T* const constraint_;
762 void (T::* const method_)(P, Q);
763 const std::string name_;
764 P param1_;
765 Q param2_;
766};
767
768template <class T, class P, class Q>
769Demon* MakeDelayedConstraintDemon2(Solver* const s, T* const ct,
770 void (T::*method)(P, Q),
771 const std::string& name, P param1,
772 Q param2) {
773 return s->RevAlloc(
774 new DelayedCallMethod2<T, P, Q>(ct, method, name, param1, param2));
775}
776/// @}
777
778#endif // !defined(SWIG)
779
780// ----- LightIntFunctionElementCt -----
781
782template <typename F>
784 public:
786 IntVar* const index, F values,
787 std::function<bool()> deep_serialize)
789 var_(var),
790 index_(index),
791 values_(std::move(values)),
792 deep_serialize_(std::move(deep_serialize)) {}
793 ~LightIntFunctionElementCt() override {}
794
795 void Post() override {
796 Demon* demon = MakeConstraintDemon0(
797 solver(), this, &LightIntFunctionElementCt::IndexBound, "IndexBound");
798 index_->WhenBound(demon);
799 }
801 void InitialPropagate() override {
802 if (index_->Bound()) {
803 IndexBound();
804 }
805 }
806
807 std::string DebugString() const override {
808 return absl::StrFormat("LightIntFunctionElementCt(%s, %s)",
809 var_->DebugString(), index_->DebugString());
810 }
811
812 void Accept(ModelVisitor* const visitor) const override {
818 // Warning: This will expand all values into a vector.
819 if (deep_serialize_ == nullptr || deep_serialize_()) {
820 visitor->VisitInt64ToInt64Extension(values_, index_->Min(),
821 index_->Max());
822 }
824 }
825
826 private:
827 void IndexBound() { var_->SetValue(values_(index_->Min())); }
828
829 IntVar* const var_;
830 IntVar* const index_;
831 F values_;
832 std::function<bool()> deep_serialize_;
833};
834
835// ----- LightIntIntFunctionElementCt -----
836
837template <typename F>
839 public:
840 LightIntIntFunctionElementCt(Solver* const solver, IntVar* const var,
841 IntVar* const index1, IntVar* const index2,
842 F values, std::function<bool()> deep_serialize)
844 var_(var),
845 index1_(index1),
846 index2_(index2),
847 values_(std::move(values)),
848 deep_serialize_(std::move(deep_serialize)) {}
850 void Post() override {
851 Demon* demon = MakeConstraintDemon0(
852 solver(), this, &LightIntIntFunctionElementCt::IndexBound,
853 "IndexBound");
854 index1_->WhenBound(demon);
855 index2_->WhenBound(demon);
857 void InitialPropagate() override { IndexBound(); }
858
859 std::string DebugString() const override {
860 return "LightIntIntFunctionElementCt";
861 }
862
863 void Accept(ModelVisitor* const visitor) const override {
864 visitor->BeginVisitConstraint(ModelVisitor::kLightElementEqual, this);
865 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
866 var_);
867 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndexArgument,
868 index1_);
869 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndex2Argument,
870 index2_);
871 // Warning: This will expand all values into a vector.
872 const int64_t index1_min = index1_->Min();
873 const int64_t index1_max = index1_->Max();
874 visitor->VisitIntegerArgument(ModelVisitor::kMinArgument, index1_min);
875 visitor->VisitIntegerArgument(ModelVisitor::kMaxArgument, index1_max);
876 if (deep_serialize_ == nullptr || deep_serialize_()) {
877 for (int i = index1_min; i <= index1_max; ++i) {
878 visitor->VisitInt64ToInt64Extension(
879 [this, i](int64_t j) { return values_(i, j); }, index2_->Min(),
880 index2_->Max());
881 }
882 }
883 visitor->EndVisitConstraint(ModelVisitor::kLightElementEqual, this);
884 }
885
886 private:
887 void IndexBound() {
888 if (index1_->Bound() && index2_->Bound()) {
889 var_->SetValue(values_(index1_->Min(), index2_->Min()));
890 }
891 }
892
893 IntVar* const var_;
894 IntVar* const index1_;
895 IntVar* const index2_;
896 F values_;
897 std::function<bool()> deep_serialize_;
898};
899
900// ----- LightIntIntIntFunctionElementCt -----
901
902template <typename F>
904 public:
905 LightIntIntIntFunctionElementCt(Solver* const solver, IntVar* const var,
906 IntVar* const index1, IntVar* const index2,
907 IntVar* const index3, F values)
909 var_(var),
910 index1_(index1),
911 index2_(index2),
912 index3_(index3),
913 values_(std::move(values)) {}
915 void Post() override {
916 Demon* demon = MakeConstraintDemon0(
917 solver(), this, &LightIntIntIntFunctionElementCt::IndexBound,
918 "IndexBound");
919 index1_->WhenBound(demon);
920 index2_->WhenBound(demon);
921 index3_->WhenBound(demon);
923 void InitialPropagate() override { IndexBound(); }
924
925 std::string DebugString() const override {
926 return "LightIntIntFunctionElementCt";
927 }
928
929 void Accept(ModelVisitor* const visitor) const override {
930 visitor->BeginVisitConstraint(ModelVisitor::kLightElementEqual, this);
931 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
932 var_);
933 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndexArgument,
934 index1_);
935 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndex2Argument,
936 index2_);
937 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndex3Argument,
938 index3_);
939 visitor->EndVisitConstraint(ModelVisitor::kLightElementEqual, this);
940 }
941
942 private:
943 void IndexBound() {
944 if (index1_->Bound() && index2_->Bound() && index3_->Bound()) {
945 var_->SetValue(values_(index1_->Min(), index2_->Min(), index3_->Min()));
946 }
947 }
948
949 IntVar* const var_;
950 IntVar* const index1_;
951 IntVar* const index2_;
952 IntVar* const index3_;
953 F values_;
954};
955
962
973// TODO(user): rename Start to Synchronize ?
974// TODO(user): decouple the iterating from the defining of a neighbor.
975class LocalSearchOperator : public BaseObject {
976 public:
978 ~LocalSearchOperator() override {}
979 virtual bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) = 0;
980 virtual void EnterSearch() {}
981 virtual void Start(const Assignment* assignment) = 0;
982 virtual void Reset() {}
983#ifndef SWIG
984 virtual const LocalSearchOperator* Self() const { return this; }
985#endif // SWIG
986 virtual bool HasFragments() const { return false; }
987 virtual bool HoldsDelta() const { return false; }
991 public:
995 max_inversible_index_ = candidate_values_.size();
996 candidate_value_to_index_.resize(max_value + 1, -1);
997 committed_value_to_index_.resize(max_value + 1, -1);
999
1000
1001 /// index.
1002 int64_t CandidateValue(int64_t index) const {
1003 DCHECK_LT(index, candidate_values_.size());
1004 return candidate_values_[index];
1006 int64_t CommittedValue(int64_t index) const {
1007 return committed_values_[index];
1008 }
1009 int64_t CheckPointValue(int64_t index) const {
1010 return checkpoint_values_[index];
1011 }
1012 void SetCandidateValue(int64_t index, int64_t value) {
1013 candidate_values_[index] = value;
1014 if (index < max_inversible_index_) {
1015 candidate_value_to_index_[value] = index;
1016 }
1017 MarkChange(index);
1018 }
1019
1020 bool CandidateIsActive(int64_t index) const {
1021 return candidate_is_active_[index];
1022 }
1023 void SetCandidateActive(int64_t index, bool active) {
1024 if (active) {
1025 candidate_is_active_.Set(index);
1026 } else {
1027 candidate_is_active_.Clear(index);
1028 }
1029 MarkChange(index);
1030 }
1032 void Commit() {
1033 for (const int64_t index : changes_.PositionsSetAtLeastOnce()) {
1034 const int64_t value = candidate_values_[index];
1035 committed_values_[index] = value;
1036 if (index < max_inversible_index_) {
1037 committed_value_to_index_[value] = index;
1038 }
1039 committed_is_active_.CopyBucket(candidate_is_active_, index);
1040 }
1041 changes_.SparseClearAll();
1042 incremental_changes_.SparseClearAll();
1044
1045 void CheckPoint() { checkpoint_values_ = committed_values_; }
1046
1047 void Revert(bool only_incremental) {
1048 incremental_changes_.SparseClearAll();
1049 if (only_incremental) return;
1050
1051 for (const int64_t index : changes_.PositionsSetAtLeastOnce()) {
1052 const int64_t committed_value = committed_values_[index];
1053 candidate_values_[index] = committed_value;
1054 if (index < max_inversible_index_) {
1055 candidate_value_to_index_[committed_value] = index;
1057 candidate_is_active_.CopyBucket(committed_is_active_, index);
1059 changes_.SparseClearAll();
1060 }
1061
1062 const std::vector<int64_t>& CandidateIndicesChanged() const {
1063 return changes_.PositionsSetAtLeastOnce();
1064 }
1065 const std::vector<int64_t>& IncrementalIndicesChanged() const {
1066 return incremental_changes_.PositionsSetAtLeastOnce();
1067 }
1068
1069 void Resize(int size) {
1070 candidate_values_.resize(size);
1071 committed_values_.resize(size);
1072 checkpoint_values_.resize(size);
1073 candidate_is_active_.Resize(size);
1074 committed_is_active_.Resize(size);
1075 changes_.ClearAndResize(size);
1076 incremental_changes_.ClearAndResize(size);
1077 }
1078
1079 int64_t CandidateInverseValue(int64_t value) const {
1080 return candidate_value_to_index_[value];
1081 }
1082 int64_t CommittedInverseValue(int64_t value) const {
1083 return committed_value_to_index_[value];
1084 }
1085
1086 private:
1087 void MarkChange(int64_t index) {
1088 incremental_changes_.Set(index);
1089 changes_.Set(index);
1091
1092 std::vector<int64_t> candidate_values_;
1093 std::vector<int64_t> committed_values_;
1094 std::vector<int64_t> checkpoint_values_;
1095
1096 Bitset64<> candidate_is_active_;
1097 Bitset64<> committed_is_active_;
1098
1099 SparseBitset<> changes_;
1100 SparseBitset<> incremental_changes_;
1101
1102 int64_t max_inversible_index_ = -1;
1103 std::vector<int64_t> candidate_value_to_index_;
1104 std::vector<int64_t> committed_value_to_index_;
1105};
1106
1113 public:
1114 // If keep_inverse_values is true, assumes that vars models an injective
1115 // function f with domain [0, vars.size()) in which case the operator will
1116 // maintain the inverse function.
1117 explicit IntVarLocalSearchOperator(const std::vector<IntVar*>& vars,
1118 bool keep_inverse_values = false) {
1119 AddVars(vars);
1120 if (keep_inverse_values) {
1121 int64_t max_value = -1;
1122 for (const IntVar* const var : vars) {
1123 max_value = std::max(max_value, var->Max());
1124 }
1126 }
1127 }
1129
1130 bool HoldsDelta() const override { return true; }
1133 void Start(const Assignment* assignment) override {
1134 state_.CheckPoint();
1135 RevertChanges(false);
1136 const int size = Size();
1137 CHECK_LE(size, assignment->Size())
1138 << "Assignment contains fewer variables than operator";
1139 const Assignment::IntContainer& container = assignment->IntVarContainer();
1140 for (int i = 0; i < size; ++i) {
1141 const IntVarElement* element = &(container.Element(i));
1142 if (element->Var() != vars_[i]) {
1143 CHECK(container.Contains(vars_[i]))
1144 << "Assignment does not contain operator variable " << vars_[i];
1145 element = &(container.Element(vars_[i]));
1146 }
1147 state_.SetCandidateValue(i, element->Value());
1148 state_.SetCandidateActive(i, element->Activated());
1149 }
1150 state_.Commit();
1151 OnStart();
1152 }
1153 virtual bool IsIncremental() const { return false; }
1154
1155 int Size() const { return vars_.size(); }
1158 int64_t Value(int64_t index) const {
1159 DCHECK_LT(index, vars_.size());
1160 return state_.CandidateValue(index);
1161 }
1163 IntVar* Var(int64_t index) const { return vars_[index]; }
1164 virtual bool SkipUnchanged(int) const { return false; }
1165 int64_t OldValue(int64_t index) const { return state_.CommittedValue(index); }
1166 int64_t PrevValue(int64_t index) const {
1167 return state_.CheckPointValue(index);
1168 }
1169 void SetValue(int64_t index, int64_t value) {
1170 state_.SetCandidateValue(index, value);
1171 }
1172 bool Activated(int64_t index) const {
1173 return state_.CandidateIsActive(index);
1175 void Activate(int64_t index) { state_.SetCandidateActive(index, true); }
1176 void Deactivate(int64_t index) { state_.SetCandidateActive(index, false); }
1178 bool ApplyChanges(Assignment* delta, Assignment* deltadelta) const {
1179 if (IsIncremental() && candidate_has_changes_) {
1180 for (const int64_t index : state_.IncrementalIndicesChanged()) {
1181 IntVar* var = Var(index);
1182 const int64_t value = Value(index);
1183 const bool activated = Activated(index);
1184 AddToAssignment(var, value, activated, nullptr, index, deltadelta);
1185 AddToAssignment(var, value, activated, &assignment_indices_, index,
1186 delta);
1188 } else {
1189 delta->Clear();
1190 for (const int64_t index : state_.CandidateIndicesChanged()) {
1191 const int64_t value = Value(index);
1192 const bool activated = Activated(index);
1193 if (!activated || value != OldValue(index) || !SkipUnchanged(index)) {
1194 AddToAssignment(Var(index), value, activated, &assignment_indices_,
1195 index, delta);
1196 }
1197 }
1198 }
1199 return true;
1200 }
1201
1202 void RevertChanges(bool change_was_incremental) {
1203 candidate_has_changes_ = change_was_incremental && IsIncremental();
1204
1205 if (!candidate_has_changes_) {
1206 for (const int64_t index : state_.CandidateIndicesChanged()) {
1207 assignment_indices_[index] = -1;
1208 }
1209 }
1210 state_.Revert(candidate_has_changes_);
1211 }
1212
1213 void AddVars(const std::vector<IntVar*>& vars) {
1214 if (!vars.empty()) {
1215 vars_.insert(vars_.end(), vars.begin(), vars.end());
1216 const int64_t size = Size();
1217 assignment_indices_.resize(size, -1);
1218 state_.Resize(size);
1219 }
1220 }
1221
1223
1224 /// IntVarLocalSearchOperator::Start explicitly.
1225 virtual void OnStart() {}
1226
1229
1232
1236 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
1237
1238 protected:
1241 // TODO(user): make it pure virtual, implies porting all apps overriding
1243 virtual bool MakeOneNeighbor();
1244
1245 int64_t InverseValue(int64_t index) const {
1246 return state_.CandidateInverseValue(index);
1247 }
1248 int64_t OldInverseValue(int64_t index) const {
1249 return state_.CommittedInverseValue(index);
1250 }
1251
1252 void AddToAssignment(IntVar* var, int64_t value, bool active,
1253 std::vector<int>* assignment_indices, int64_t index,
1254 Assignment* assignment) const {
1255 Assignment::IntContainer* const container =
1256 assignment->MutableIntVarContainer();
1257 IntVarElement* element = nullptr;
1258 if (assignment_indices != nullptr) {
1259 if ((*assignment_indices)[index] == -1) {
1260 (*assignment_indices)[index] = container->Size();
1261 element = assignment->FastAdd(var);
1262 } else {
1263 element = container->MutableElement((*assignment_indices)[index]);
1264 }
1265 } else {
1266 element = assignment->FastAdd(var);
1267 }
1268 if (active) {
1269 element->SetValue(value);
1270 element->Activate();
1271 } else {
1272 element->Deactivate();
1273 }
1274 }
1275
1276 private:
1277 std::vector<IntVar*> vars_;
1278 mutable std::vector<int> assignment_indices_;
1279 bool candidate_has_changes_ = false;
1280
1281 LocalSearchOperatorState state_;
1282};
1283
1286
1294
1311class BaseLns : public IntVarLocalSearchOperator {
1312 public:
1313 explicit BaseLns(const std::vector<IntVar*>& vars);
1314 ~BaseLns() override;
1315 virtual void InitFragments();
1316 virtual bool NextFragment() = 0;
1317 void AppendToFragment(int index);
1318 int FragmentSize() const;
1319 bool HasFragments() const override { return true; }
1320
1321 protected:
1323 bool MakeOneNeighbor() override;
1324
1325 private:
1327 void OnStart() override;
1328 std::vector<int> fragment_;
1329};
1336 public:
1337 explicit ChangeValue(const std::vector<IntVar*>& vars);
1338 ~ChangeValue() override;
1339 virtual int64_t ModifyValue(int64_t index, int64_t value) = 0;
1340
1341 protected:
1343 bool MakeOneNeighbor() override;
1344
1345 private:
1346 void OnStart() override;
1347
1348 int index_;
1350
1351// Iterators on nodes used by Pathoperator to traverse the search space.
1352
1354 public:
1355 explicit AlternativeNodeIterator(bool use_sibling)
1356 : use_sibling_(use_sibling) {}
1358 template <class PathOperator>
1359 void Reset(const PathOperator& path_operator, int base_index_reference) {
1360 index_ = 0;
1361 DCHECK(path_operator.ConsiderAlternatives(base_index_reference));
1362 const int64_t base_node = path_operator.BaseNode(base_index_reference);
1363 const int alternative_index =
1364 use_sibling_ ? path_operator.GetSiblingAlternativeIndex(base_node)
1365 : path_operator.GetAlternativeIndex(base_node);
1366 alternative_set_ =
1367 alternative_index >= 0
1368 ? absl::Span<const int64_t>(
1369 path_operator.alternative_sets_[alternative_index])
1370 : absl::Span<const int64_t>();
1372 bool Next() { return ++index_ < alternative_set_.size(); }
1373 int GetValue() const {
1374 return (index_ >= alternative_set_.size()) ? -1 : alternative_set_[index_];
1375 }
1376
1377 private:
1378 const bool use_sibling_;
1379 int index_ = 0;
1380 absl::Span<const int64_t> alternative_set_;
1381};
1382
1383class NodeNeighborIterator {
1384 public:
1387 template <class PathOperator>
1388 void Reset(const PathOperator& path_operator, int base_index_reference) {
1389 using Span = absl::Span<const int>;
1390 index_ = 0;
1391 const int64_t base_node = path_operator.BaseNode(base_index_reference);
1392 const int64_t start_node = path_operator.StartNode(base_index_reference);
1393 const auto& get_incoming_neighbors =
1394 path_operator.iteration_parameters_.get_incoming_neighbors;
1395 incoming_neighbors_ =
1396 path_operator.IsPathStart(base_node) || !get_incoming_neighbors
1397 ? Span()
1398 : Span(get_incoming_neighbors(base_node, start_node));
1399 const auto& get_outgoing_neighbors =
1400 path_operator.iteration_parameters_.get_outgoing_neighbors;
1401 outgoing_neighbors_ =
1402 path_operator.IsPathEnd(base_node) || !get_outgoing_neighbors
1403 ? Span()
1404 : Span(get_outgoing_neighbors(base_node, start_node));
1405 }
1406 bool Next() {
1407 return ++index_ < incoming_neighbors_.size() + outgoing_neighbors_.size();
1408 }
1409 int GetValue() const {
1410 if (index_ < incoming_neighbors_.size()) {
1411 return incoming_neighbors_[index_];
1412 }
1413 const int index = index_ - incoming_neighbors_.size();
1414 return (index >= outgoing_neighbors_.size()) ? -1
1415 : outgoing_neighbors_[index];
1416 }
1417 bool IsIncomingNeighbor() const {
1418 return index_ < incoming_neighbors_.size();
1419 }
1420 bool IsOutgoingNeighbor() const {
1421 return index_ >= incoming_neighbors_.size();
1422 }
1424 private:
1425 int index_ = 0;
1426 absl::Span<const int> incoming_neighbors_;
1427 absl::Span<const int> outgoing_neighbors_;
1428};
1429
1430template <class PathOperator>
1432 public:
1433 BaseNodeIterators(const PathOperator* path_operator, int base_index_reference)
1434 : path_operator_(*path_operator),
1435 base_index_reference_(base_index_reference) {}
1437 DCHECK(!alternatives_.empty());
1438 DCHECK(!finished_);
1439 return alternatives_[0].get();
1440 }
1441 AlternativeNodeIterator* GetAlternativeIterator() const {
1442 DCHECK(!alternatives_.empty());
1443 DCHECK(!finished_);
1444 return alternatives_[1].get();
1447 DCHECK(neighbors_);
1448 DCHECK(!finished_);
1449 return neighbors_.get();
1451 void Initialize() {
1452 if (path_operator_.ConsiderAlternatives(base_index_reference_)) {
1453 alternatives_.push_back(std::make_unique<AlternativeNodeIterator>(
1454 /*is_sibling=*/true));
1455 alternatives_.push_back(std::make_unique<AlternativeNodeIterator>(
1456 /*is_sibling=*/false));
1457 }
1458 if (path_operator_.HasNeighbors()) {
1459 neighbors_ = std::make_unique<NodeNeighborIterator>();
1461 }
1462 void Reset(bool update_end_nodes = false) {
1463 finished_ = false;
1464 for (auto& alternative_iterator : alternatives_) {
1465 alternative_iterator->Reset(path_operator_, base_index_reference_);
1466 }
1467 if (neighbors_) {
1468 neighbors_->Reset(path_operator_, base_index_reference_);
1469 if (update_end_nodes) neighbor_end_node_ = neighbors_->GetValue();
1470 }
1471 }
1472 bool Increment() {
1473 DCHECK(!finished_);
1474 for (auto& alternative_iterator : alternatives_) {
1475 if (alternative_iterator->Next()) return true;
1476 alternative_iterator->Reset(path_operator_, base_index_reference_);
1477 }
1478 if (neighbors_) {
1479 if (neighbors_->Next()) return true;
1480 neighbors_->Reset(path_operator_, base_index_reference_);
1481 }
1482 finished_ = true;
1483 return false;
1484 }
1485 bool HasReachedEnd() const {
1486 // TODO(user): Extend to other iterators.
1487 if (!neighbors_) return true;
1488 return neighbor_end_node_ == neighbors_->GetValue();
1489 }
1490
1491 private:
1492 const PathOperator& path_operator_;
1493 int base_index_reference_ = -1;
1494#ifndef SWIG
1495 std::vector<std::unique_ptr<AlternativeNodeIterator>> alternatives_;
1496#endif // SWIG
1497 std::unique_ptr<NodeNeighborIterator> neighbors_;
1498 int neighbor_end_node_ = -1;
1499 bool finished_ = false;
1500};
1501
1504
1515template <bool ignore_path_vars>
1517 public:
1519 struct IterationParameters {
1530 /// p1 and p2 are path indices,
1531 /// then if c1 == c2, p1 and p2 are equivalent if they are empty.
1532 /// This is used to remove neighborhood symmetries on equivalent empty
1533 /// paths; for instance if a node cannot be moved to an empty path, then all
1534 /// moves moving the same node to equivalent empty paths will be skipped.
1535 /// 'start_empty_path_class' can be nullptr in which case no symmetries will
1536 /// be removed.
1537 std::function<int(int64_t)> start_empty_path_class;
1540 std::function<const std::vector<int>&(
1541 /*node=*/int, /*start_node=*/int)>
1543 std::function<const std::vector<int>&(
1544 /*node=*/int, /*start_node=*/int)>
1546 };
1548 PathOperator(const std::vector<IntVar*>& next_vars,
1549 const std::vector<IntVar*>& path_vars,
1550 IterationParameters iteration_parameters)
1551 : IntVarLocalSearchOperator(next_vars, true),
1552 number_of_nexts_(next_vars.size()),
1553 base_nodes_(
1554 std::make_unique<int[]>(iteration_parameters.number_of_base_nodes)),
1555 end_nodes_(
1556 std::make_unique<int[]>(iteration_parameters.number_of_base_nodes)),
1557 base_paths_(
1558 std::make_unique<int[]>(iteration_parameters.number_of_base_nodes)),
1559 node_path_starts_(number_of_nexts_, -1),
1560 node_path_ends_(number_of_nexts_, -1),
1561 just_started_(false),
1562 first_start_(true),
1563 next_base_to_increment_(iteration_parameters.number_of_base_nodes),
1564 iteration_parameters_(std::move(iteration_parameters)),
1565 optimal_paths_enabled_(false),
1566 active_paths_(number_of_nexts_),
1567 alternative_index_(next_vars.size(), -1) {
1568 DCHECK_GT(iteration_parameters_.number_of_base_nodes, 0);
1569 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
1570 base_node_iterators_.push_back(BaseNodeIterators<PathOperator>(this, i));
1571 }
1572 if constexpr (!ignore_path_vars) {
1573 AddVars(path_vars);
1574 }
1575 path_basis_.push_back(0);
1576 for (int i = 1; i < iteration_parameters_.number_of_base_nodes; ++i) {
1577 if (!OnSamePathAsPreviousBase(i)) path_basis_.push_back(i);
1578 }
1579 if ((path_basis_.size() > 2) ||
1580 (!next_vars.empty() && !next_vars.back()
1581 ->solver()
1582 ->parameters()
1583 .skip_locally_optimal_paths())) {
1584 iteration_parameters_.skip_locally_optimal_paths = false;
1585 }
1586 }
1588 const std::vector<IntVar*>& next_vars,
1589 const std::vector<IntVar*>& path_vars, int number_of_base_nodes,
1590 bool skip_locally_optimal_paths, bool accept_path_end_base,
1591 std::function<int(int64_t)> start_empty_path_class,
1592 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
1593 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors)
1594 : PathOperator(next_vars, path_vars,
1595 {number_of_base_nodes, skip_locally_optimal_paths,
1596 accept_path_end_base, std::move(start_empty_path_class),
1597 std::move(get_incoming_neighbors),
1598 std::move(get_outgoing_neighbors)}) {}
1599 ~PathOperator() override {}
1600 virtual bool MakeNeighbor() = 0;
1601 void EnterSearch() override {
1602 first_start_ = true;
1604 }
1605 void Reset() override {
1606 active_paths_.Clear();
1608 }
1609
1610 // TODO(user): Make the following methods protected.
1611 bool SkipUnchanged(int index) const override {
1612 if constexpr (ignore_path_vars) return true;
1613 if (index < number_of_nexts_) {
1614 const int path_index = index + number_of_nexts_;
1615 return Value(path_index) == OldValue(path_index);
1616 }
1617 const int next_index = index - number_of_nexts_;
1618 return Value(next_index) == OldValue(next_index);
1620
1622 int64_t Next(int64_t node) const {
1623 DCHECK(!IsPathEnd(node));
1624 return Value(node);
1626
1628 int64_t Prev(int64_t node) const {
1629 DCHECK(!IsPathStart(node));
1630 DCHECK_EQ(Next(InverseValue(node)), node);
1631 return InverseValue(node);
1632 }
1633
1634
1636 int64_t Path(int64_t node) const {
1637 if constexpr (ignore_path_vars) return 0LL;
1638 return Value(node + number_of_nexts_);
1639 }
1640
1642 int number_of_nexts() const { return number_of_nexts_; }
1643
1644 protected:
1646 bool MakeOneNeighbor() override {
1647 while (IncrementPosition()) {
1648 // Need to revert changes here since MakeNeighbor might have returned
1649 // false and have done changes in the previous iteration.
1651 if (MakeNeighbor()) {
1652 return true;
1653 }
1654 }
1655 return false;
1657
1660 /// explicitly.
1661 virtual void OnNodeInitialization() {}
1666 virtual void ResetIncrementalism() {}
1667
1669 int64_t BaseNode(int i) const { return base_nodes_[i]; }
1671 int64_t BaseAlternativeNode(int i) const {
1672 return GetNodeWithDefault(base_node_iterators_[i].GetAlternativeIterator(),
1673 BaseNode(i));
1674 }
1676 int64_t BaseSiblingAlternativeNode(int i) const {
1677 return GetNodeWithDefault(
1678 base_node_iterators_[i].GetSiblingAlternativeIterator(), BaseNode(i));
1679 }
1681 int64_t StartNode(int i) const { return path_starts_[base_paths_[i]]; }
1683 int64_t EndNode(int i) const { return path_ends_[base_paths_[i]]; }
1685 const std::vector<int64_t>& path_starts() const { return path_starts_; }
1687 int PathClass(int i) const { return PathClassFromStartNode(StartNode(i)); }
1688 int PathClassFromStartNode(int64_t start_node) const {
1689 return iteration_parameters_.start_empty_path_class != nullptr
1690 ? iteration_parameters_.start_empty_path_class(start_node)
1691 : start_node;
1692 }
1693
1694
1700 // TODO(user): remove this when automatic detection of such cases in done.
1701 virtual bool RestartAtPathStartOnSynchronize() { return false; }
1702 /// Returns true if a base node has to be on the same path as the "previous"
1703 /// base node (base node of index base_index - 1).
1704 /// Useful to limit neighborhood exploration to nodes on the same path.
1705 // TODO(user): ideally this should be OnSamePath(int64_t node1, int64_t
1706 // node2);
1707
1708 virtual bool OnSamePathAsPreviousBase(int64_t) { return false; }
1714 virtual int64_t GetBaseNodeRestartPosition(int base_index) {
1715 return StartNode(base_index);
1716 }
1719 virtual void SetNextBaseToIncrement(int64_t base_index) {
1720 next_base_to_increment_ = base_index;
1721 }
1724 virtual bool ConsiderAlternatives(int64_t) const { return false; }
1725
1726 int64_t OldNext(int64_t node) const {
1727 DCHECK(!IsPathEnd(node));
1728 return OldValue(node);
1729 }
1730
1731 int64_t PrevNext(int64_t node) const {
1732 DCHECK(!IsPathEnd(node));
1733 return PrevValue(node);
1734 }
1735
1736 int64_t OldPrev(int64_t node) const {
1737 DCHECK(!IsPathStart(node));
1738 return OldInverseValue(node);
1739 }
1741 int64_t OldPath(int64_t node) const {
1742 if constexpr (ignore_path_vars) return 0LL;
1743 return OldValue(node + number_of_nexts_);
1744 }
1746 int CurrentNodePathStart(int64_t node) const {
1747 return node_path_starts_[node];
1748 }
1749
1750 int CurrentNodePathEnd(int64_t node) const { return node_path_ends_[node]; }
1751
1754 bool MoveChain(int64_t before_chain, int64_t chain_end, int64_t destination) {
1755 if (destination == before_chain || destination == chain_end) return false;
1756 DCHECK(CheckChainValidity(before_chain, chain_end, destination) &&
1757 !IsPathEnd(chain_end) && !IsPathEnd(destination));
1758 const int64_t destination_path = Path(destination);
1759 const int64_t after_chain = Next(chain_end);
1760 SetNext(chain_end, Next(destination), destination_path);
1761 if constexpr (!ignore_path_vars) {
1762 int current = destination;
1763 int next = Next(before_chain);
1764 while (current != chain_end) {
1765 SetNext(current, next, destination_path);
1766 current = next;
1767 next = Next(next);
1769 } else {
1770 SetNext(destination, Next(before_chain), destination_path);
1771 }
1772 SetNext(before_chain, after_chain, Path(before_chain));
1773 return true;
1774 }
1775
1778 bool ReverseChain(int64_t before_chain, int64_t after_chain,
1779 int64_t* chain_last) {
1780 if (CheckChainValidity(before_chain, after_chain, -1)) {
1781 int64_t path = Path(before_chain);
1782 int64_t current = Next(before_chain);
1783 if (current == after_chain) {
1784 return false;
1785 }
1786 int64_t current_next = Next(current);
1787 SetNext(current, after_chain, path);
1788 while (current_next != after_chain) {
1789 const int64_t next = Next(current_next);
1790 SetNext(current_next, current, path);
1791 current = current_next;
1792 current_next = next;
1793 }
1794 SetNext(before_chain, current, path);
1795 *chain_last = current;
1796 return true;
1797 }
1798 return false;
1799 }
1800
1802 bool SwapNodes(int64_t node1, int64_t node2) {
1803 if (IsPathEnd(node1) || IsPathEnd(node2) || IsPathStart(node1) ||
1804 IsPathStart(node2)) {
1805 return false;
1806 }
1807 if (node1 == node2) return false;
1808 const int64_t prev_node1 = Prev(node1);
1809 const bool ok = MoveChain(prev_node1, node1, Prev(node2));
1810 return MoveChain(Prev(node2), node2, prev_node1) || ok;
1811 }
1812
1814 bool MakeActive(int64_t node, int64_t destination) {
1815 if (IsPathEnd(destination)) return false;
1816 const int64_t destination_path = Path(destination);
1817 SetNext(node, Next(destination), destination_path);
1818 SetNext(destination, node, destination_path);
1819 return true;
1820 }
1823 bool MakeChainInactive(int64_t before_chain, int64_t chain_end) {
1824 const int64_t kNoPath = -1;
1825 if (CheckChainValidity(before_chain, chain_end, -1) &&
1826 !IsPathEnd(chain_end)) {
1827 const int64_t after_chain = Next(chain_end);
1828 int64_t current = Next(before_chain);
1829 while (current != after_chain) {
1830 const int64_t next = Next(current);
1831 SetNext(current, current, kNoPath);
1832 current = next;
1833 }
1834 SetNext(before_chain, after_chain, Path(before_chain));
1835 return true;
1836 }
1837 return false;
1838 }
1839
1841 bool SwapActiveAndInactive(int64_t active, int64_t inactive) {
1842 if (active == inactive) return false;
1843 const int64_t prev = Prev(active);
1844 return MakeChainInactive(prev, active) && MakeActive(inactive, prev);
1845 }
1848 bool SwapActiveAndInactiveChains(absl::Span<const int64_t> active_chain,
1849 absl::Span<const int64_t> inactive_chain) {
1850 if (active_chain.empty()) return false;
1851 if (active_chain == inactive_chain) return false;
1852 const int before_active_chain = Prev(active_chain.front());
1853 if (!MakeChainInactive(before_active_chain, active_chain.back())) {
1854 return false;
1856 for (auto it = inactive_chain.crbegin(); it != inactive_chain.crend();
1857 ++it) {
1858 if (!MakeActive(*it, before_active_chain)) return false;
1859 }
1860 return true;
1861 }
1864 void SetNext(int64_t from, int64_t to, int64_t path) {
1865 DCHECK_LT(from, number_of_nexts_);
1866 SetValue(from, to);
1867 if constexpr (!ignore_path_vars) {
1868 DCHECK_LT(from + number_of_nexts_, Size());
1869 SetValue(from + number_of_nexts_, path);
1870 }
1871 }
1872
1875 bool IsPathEnd(int64_t node) const { return node >= number_of_nexts_; }
1876
1878 bool IsPathStart(int64_t node) const { return OldInverseValue(node) == -1; }
1879
1881 bool IsInactive(int64_t node) const {
1882 return !IsPathEnd(node) && inactives_[node];
1883 }
1884
1886
1887 virtual bool InitPosition() const { return false; }
1891 void ResetPosition() { just_started_ = true; }
1895 /// two alternatives.
1896 int AddAlternativeSet(const std::vector<int64_t>& alternative_set) {
1897 const int alternative = alternative_sets_.size();
1898 for (int64_t node : alternative_set) {
1899 DCHECK_EQ(-1, alternative_index_[node]);
1900 alternative_index_[node] = alternative;
1902 alternative_sets_.push_back(alternative_set);
1903 sibling_alternative_.push_back(-1);
1904 return alternative;
1906#ifndef SWIG
1909 template <typename PairType>
1911 const std::vector<PairType>& pair_alternative_sets) {
1912 for (const auto& [alternative_set, sibling_alternative_set] :
1913 pair_alternative_sets) {
1914 sibling_alternative_.back() = AddAlternativeSet(alternative_set) + 1;
1915 AddAlternativeSet(sibling_alternative_set);
1916 }
1917 }
1918#endif // SWIG
1920 int64_t GetActiveInAlternativeSet(int alternative_index) const {
1921 return alternative_index >= 0
1922 ? active_in_alternative_set_[alternative_index]
1923 : -1;
1926 int64_t GetActiveAlternativeNode(int node) const {
1927 return GetActiveInAlternativeSet(alternative_index_[node]);
1928 }
1930 int GetSiblingAlternativeIndex(int node) const {
1931 const int alternative = GetAlternativeIndex(node);
1932 return alternative >= 0 ? sibling_alternative_[alternative] : -1;
1933 }
1934 /// Returns the index of the alternative set of the node.
1935 int GetAlternativeIndex(int node) const {
1936 return (node >= alternative_index_.size()) ? -1 : alternative_index_[node];
1937 }
1939
1940 int64_t GetActiveAlternativeSibling(int node) const {
1942 }
1943
1944 /// to chain_end and does not contain exclude.
1945 /// In particular, rejects a chain if chain_end is not strictly after
1946 /// before_chain on the path.
1947 /// Cycles are detected through chain length overflow.
1948 bool CheckChainValidity(int64_t before_chain, int64_t chain_end,
1949 int64_t exclude) const {
1950 if (before_chain == chain_end || before_chain == exclude) return false;
1951 int64_t current = before_chain;
1952 int chain_size = 0;
1953 while (current != chain_end) {
1954 if (chain_size > number_of_nexts_) return false;
1955 if (IsPathEnd(current)) return false;
1956 current = Next(current);
1957 ++chain_size;
1958 if (current == exclude) return false;
1959 }
1960 return true;
1961 }
1963 bool HasNeighbors() const {
1964 return iteration_parameters_.get_incoming_neighbors != nullptr ||
1965 iteration_parameters_.get_outgoing_neighbors != nullptr;
1966 }
1967
1968 struct Neighbor {
1969 // Index of the neighbor node.
1970 int neighbor;
1971 // True if 'neighbor' is an outgoing neighbor (i.e. arc main_node->neighbor)
1972 // and false if it's an incoming one (arc neighbor->main_node).
1973 bool outgoing;
1974 };
1975 Neighbor GetNeighborForBaseNode(int64_t base_index) const {
1976 auto* iterator = base_node_iterators_[base_index].GetNeighborIterator();
1977 return {.neighbor = iterator->GetValue(),
1978 .outgoing = iterator->IsOutgoingNeighbor()};
1979 }
1980
1981 const int number_of_nexts_;
1983 private:
1984 template <class NodeIterator>
1985 static int GetNodeWithDefault(const NodeIterator* node_iterator,
1986 int default_value) {
1987 const int node = node_iterator->GetValue();
1988 return node >= 0 ? node : default_value;
1990
1991 void OnStart() override {
1992 optimal_paths_enabled_ = false;
1993 if (!iterators_initialized_) {
1994 iterators_initialized_ = true;
1995 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
1996 base_node_iterators_[i].Initialize();
1997 }
1998 }
1999 InitializeBaseNodes();
2000 InitializeAlternatives();
2001 OnNodeInitialization();
2002 }
2003
2005 bool OnSamePath(int64_t node1, int64_t node2) const {
2006 if (IsInactive(node1) != IsInactive(node2)) {
2007 return false;
2008 }
2009 for (int node = node1; !IsPathEnd(node); node = OldNext(node)) {
2010 if (node == node2) {
2011 return true;
2012 }
2013 }
2014 for (int node = node2; !IsPathEnd(node); node = OldNext(node)) {
2015 if (node == node1) {
2016 return true;
2017 }
2018 }
2019 return false;
2020 }
2021
2022 bool CheckEnds() const {
2023 for (int i = iteration_parameters_.number_of_base_nodes - 1; i >= 0; --i) {
2024 if (base_nodes_[i] != end_nodes_[i] ||
2025 !base_node_iterators_[i].HasReachedEnd()) {
2026 return true;
2027 }
2028 }
2029 return false;
2030 }
2031 bool IncrementPosition() {
2032 const int base_node_size = iteration_parameters_.number_of_base_nodes;
2033
2034 if (just_started_) {
2035 just_started_ = false;
2036 return true;
2037 }
2038 const int number_of_paths = path_starts_.size();
2039 // Finding next base node positions.
2040 // Increment the position of inner base nodes first (higher index nodes);
2041 // if a base node is at the end of a path, reposition it at the start
2042 // of the path and increment the position of the preceding base node (this
2043 // action is called a restart).
2044 int last_restarted = base_node_size;
2045 for (int i = base_node_size - 1; i >= 0; --i) {
2046 if (base_nodes_[i] < number_of_nexts_ && i <= next_base_to_increment_) {
2047 if (base_node_iterators_[i].Increment()) break;
2048 base_nodes_[i] = OldNext(base_nodes_[i]);
2049 base_node_iterators_[i].Reset();
2050 if (iteration_parameters_.accept_path_end_base ||
2051 !IsPathEnd(base_nodes_[i])) {
2052 break;
2053 }
2054 }
2055 base_nodes_[i] = StartNode(i);
2056 base_node_iterators_[i].Reset();
2057 last_restarted = i;
2058 }
2059 next_base_to_increment_ = base_node_size;
2060 // At the end of the loop, base nodes with indexes in
2061 // [last_restarted, base_node_size[ have been restarted.
2062 // Restarted base nodes are then repositioned by the virtual
2063 // GetBaseNodeRestartPosition to reflect position constraints between
2064 // base nodes (by default GetBaseNodeRestartPosition leaves the nodes
2065 // at the start of the path).
2066 // Base nodes are repositioned in ascending order to ensure that all
2067 // base nodes "below" the node being repositioned have their final
2068 // position.
2069 for (int i = last_restarted; i < base_node_size; ++i) {
2070 base_nodes_[i] = GetBaseNodeRestartPosition(i);
2071 base_node_iterators_[i].Reset();
2072 }
2073 if (last_restarted > 0) {
2074 return CheckEnds();
2075 }
2076 // If all base nodes have been restarted, base nodes are moved to new paths.
2077 // First we mark the current paths as locally optimal if they have been
2078 // completely explored.
2079 if (optimal_paths_enabled_ &&
2080 iteration_parameters_.skip_locally_optimal_paths) {
2081 if (path_basis_.size() > 1) {
2082 for (int i = 1; i < path_basis_.size(); ++i) {
2083 active_paths_.DeactivatePathPair(StartNode(path_basis_[i - 1]),
2084 StartNode(path_basis_[i]));
2085 }
2086 } else {
2087 active_paths_.DeactivatePathPair(StartNode(path_basis_[0]),
2088 StartNode(path_basis_[0]));
2089 }
2090 }
2091 std::vector<int> current_starts(base_node_size);
2092 for (int i = 0; i < base_node_size; ++i) {
2093 current_starts[i] = StartNode(i);
2094 }
2095 // Exploration of next paths can lead to locally optimal paths since we are
2096 // exploring them from scratch.
2097 optimal_paths_enabled_ = true;
2098 while (true) {
2099 for (int i = base_node_size - 1; i >= 0; --i) {
2100 const int next_path_index = base_paths_[i] + 1;
2101 if (next_path_index < number_of_paths) {
2102 base_paths_[i] = next_path_index;
2103 base_nodes_[i] = path_starts_[next_path_index];
2104 base_node_iterators_[i].Reset();
2105 if (i == 0 || !OnSamePathAsPreviousBase(i)) {
2106 break;
2107 }
2108 } else {
2109 base_paths_[i] = 0;
2110 base_nodes_[i] = path_starts_[0];
2111 base_node_iterators_[i].Reset();
2112 }
2113 }
2114 if (!iteration_parameters_.skip_locally_optimal_paths) return CheckEnds();
2115 // If the new paths have already been completely explored, we can
2116 // skip them from now on.
2117 if (path_basis_.size() > 1) {
2118 for (int j = 1; j < path_basis_.size(); ++j) {
2119 if (active_paths_.IsPathPairActive(StartNode(path_basis_[j - 1]),
2120 StartNode(path_basis_[j]))) {
2121 return CheckEnds();
2122 }
2123 }
2124 } else {
2125 if (active_paths_.IsPathPairActive(StartNode(path_basis_[0]),
2126 StartNode(path_basis_[0]))) {
2127 return CheckEnds();
2128 }
2129 }
2130 // If we are back to paths we just iterated on or have reached the end
2131 // of the neighborhood search space, we can stop.
2132 if (!CheckEnds()) return false;
2133 bool stop = true;
2134 for (int i = 0; i < base_node_size; ++i) {
2135 if (StartNode(i) != current_starts[i]) {
2136 stop = false;
2137 break;
2138 }
2139 }
2140 if (stop) return false;
2141 }
2142 return CheckEnds();
2143 }
2144
2145 void InitializePathStarts() {
2146 // Detect nodes which do not have any possible predecessor in a path; these
2147 // nodes are path starts.
2148 int max_next = -1;
2149 std::vector<bool> has_prevs(number_of_nexts_, false);
2150 for (int i = 0; i < number_of_nexts_; ++i) {
2151 const int next = OldNext(i);
2152 if (next < number_of_nexts_) {
2153 has_prevs[next] = true;
2154 }
2155 max_next = std::max(max_next, next);
2156 }
2157 // Update locally optimal paths.
2158 if (iteration_parameters_.skip_locally_optimal_paths) {
2159 active_paths_.Initialize(
2160 /*is_start=*/[&has_prevs](int node) { return !has_prevs[node]; });
2161 for (int i = 0; i < number_of_nexts_; ++i) {
2162 if (!has_prevs[i]) {
2163 int current = i;
2164 while (!IsPathEnd(current)) {
2165 if ((OldNext(current) != PrevNext(current))) {
2166 active_paths_.ActivatePath(i);
2167 break;
2168 }
2169 current = OldNext(current);
2170 }
2171 }
2172 }
2173 }
2174 // Create a list of path starts, dropping equivalent path starts of
2175 // currently empty paths.
2176 std::vector<bool> empty_found(number_of_nexts_, false);
2177 std::vector<int64_t> new_path_starts;
2178 for (int i = 0; i < number_of_nexts_; ++i) {
2179 if (!has_prevs[i]) {
2180 if (IsPathEnd(OldNext(i))) {
2181 if (iteration_parameters_.start_empty_path_class != nullptr) {
2182 if (empty_found[iteration_parameters_.start_empty_path_class(i)])
2183 continue;
2184 empty_found[iteration_parameters_.start_empty_path_class(i)] = true;
2185 }
2186 }
2187 new_path_starts.push_back(i);
2188 }
2189 }
2190 if (!first_start_) {
2191 // Synchronizing base_paths_ with base node positions. When the last move
2192 // was performed a base node could have been moved to a new route in which
2193 // case base_paths_ needs to be updated. This needs to be done on the path
2194 // starts before we re-adjust base nodes for new path starts.
2195 std::vector<int> node_paths(max_next + 1, -1);
2196 for (int i = 0; i < path_starts_.size(); ++i) {
2197 int node = path_starts_[i];
2198 while (!IsPathEnd(node)) {
2199 node_paths[node] = i;
2200 node = OldNext(node);
2201 }
2202 node_paths[node] = i;
2203 }
2204 for (int j = 0; j < iteration_parameters_.number_of_base_nodes; ++j) {
2205 if (IsInactive(base_nodes_[j]) || node_paths[base_nodes_[j]] == -1) {
2206 // Base node was made inactive or was moved to a new path, reposition
2207 // the base node to its restart position.
2208 base_nodes_[j] = GetBaseNodeRestartPosition(j);
2209 base_paths_[j] = node_paths[base_nodes_[j]];
2210 } else {
2211 base_paths_[j] = node_paths[base_nodes_[j]];
2212 }
2213 // Always restart from first alternative.
2214 base_node_iterators_[j].Reset();
2215 }
2216 // Re-adjust current base_nodes and base_paths to take into account new
2217 // path starts (there could be fewer if a new path was made empty, or more
2218 // if nodes were added to a formerly empty path).
2219 int new_index = 0;
2220 absl::flat_hash_set<int> found_bases;
2221 for (int i = 0; i < path_starts_.size(); ++i) {
2222 int index = new_index;
2223 // Note: old and new path starts are sorted by construction.
2224 while (index < new_path_starts.size() &&
2225 new_path_starts[index] < path_starts_[i]) {
2226 ++index;
2227 }
2228 const bool found = (index < new_path_starts.size() &&
2229 new_path_starts[index] == path_starts_[i]);
2230 if (found) {
2231 new_index = index;
2232 }
2233 for (int j = 0; j < iteration_parameters_.number_of_base_nodes; ++j) {
2234 if (base_paths_[j] == i && !found_bases.contains(j)) {
2235 found_bases.insert(j);
2236 base_paths_[j] = new_index;
2237 // If the current position of the base node is a removed empty path,
2238 // readjusting it to the last visited path start.
2239 if (!found) {
2240 base_nodes_[j] = new_path_starts[new_index];
2241 }
2242 }
2243 }
2244 }
2245 }
2246 path_starts_.swap(new_path_starts);
2247 // For every base path, store the end corresponding to the path start.
2248 // TODO(user): make this faster, maybe by pairing starts with ends.
2249 path_ends_.clear();
2250 path_ends_.reserve(path_starts_.size());
2251 int64_t max_node_index = number_of_nexts_ - 1;
2252 for (const int start_node : path_starts_) {
2253 int64_t node = start_node;
2254 while (!IsPathEnd(node)) node = OldNext(node);
2255 path_ends_.push_back(node);
2256 max_node_index = std::max(max_node_index, node);
2257 }
2258 node_path_starts_.assign(max_node_index + 1, -1);
2259 node_path_ends_.assign(max_node_index + 1, -1);
2260 for (int i = 0; i < path_starts_.size(); ++i) {
2261 const int64_t start_node = path_starts_[i];
2262 const int64_t end_node = path_ends_[i];
2263 int64_t node = start_node;
2264 while (!IsPathEnd(node)) {
2265 node_path_starts_[node] = start_node;
2266 node_path_ends_[node] = end_node;
2267 node = OldNext(node);
2268 }
2269 node_path_starts_[node] = start_node;
2270 node_path_ends_[node] = end_node;
2271 }
2272 }
2273 void InitializeInactives() {
2274 inactives_.clear();
2275 for (int i = 0; i < number_of_nexts_; ++i) {
2276 inactives_.push_back(OldNext(i) == i);
2277 }
2278 }
2279 void InitializeBaseNodes() {
2280 // Inactive nodes must be detected before determining new path starts.
2281 InitializeInactives();
2282 InitializePathStarts();
2283 if (first_start_ || InitPosition()) {
2284 // Only do this once since the following starts will continue from the
2285 // preceding position
2286 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
2287 base_paths_[i] = 0;
2288 base_nodes_[i] = path_starts_[0];
2289 }
2290 first_start_ = false;
2291 }
2292 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
2293 // If base node has been made inactive, restart from path start.
2294 int64_t base_node = base_nodes_[i];
2295 if (RestartAtPathStartOnSynchronize() || IsInactive(base_node)) {
2296 base_node = path_starts_[base_paths_[i]];
2297 base_nodes_[i] = base_node;
2298 }
2299 end_nodes_[i] = base_node;
2300 }
2301 // Repair end_nodes_ in case some must be on the same path and are not
2302 // anymore (due to other operators moving these nodes).
2303 for (int i = 1; i < iteration_parameters_.number_of_base_nodes; ++i) {
2304 if (OnSamePathAsPreviousBase(i) &&
2305 !OnSamePath(base_nodes_[i - 1], base_nodes_[i])) {
2306 const int64_t base_node = base_nodes_[i - 1];
2307 base_nodes_[i] = base_node;
2308 end_nodes_[i] = base_node;
2309 base_paths_[i] = base_paths_[i - 1];
2310 }
2311 }
2312 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
2313 base_node_iterators_[i].Reset(/*update_end_nodes=*/true);
2314 }
2315 just_started_ = true;
2316 }
2317 void InitializeAlternatives() {
2318 active_in_alternative_set_.resize(alternative_sets_.size(), -1);
2319 for (int i = 0; i < alternative_sets_.size(); ++i) {
2320 const int64_t current_active = active_in_alternative_set_[i];
2321 if (current_active >= 0 && !IsInactive(current_active)) continue;
2322 for (int64_t index : alternative_sets_[i]) {
2323 if (!IsInactive(index)) {
2324 active_in_alternative_set_[i] = index;
2325 break;
2326 }
2327 }
2328 }
2329 }
2330
2331 class ActivePaths {
2332 public:
2333 explicit ActivePaths(int num_nodes) : start_to_path_(num_nodes, -1) {}
2334 void Clear() { is_path_pair_active_.clear(); }
2335 template <typename T>
2336 void Initialize(T is_start) {
2337 if (is_path_pair_active_.empty()) {
2338 num_paths_ = 0;
2339 absl::c_fill(start_to_path_, -1);
2340 for (int i = 0; i < start_to_path_.size(); ++i) {
2341 if (is_start(i)) {
2342 start_to_path_[i] = num_paths_;
2343 ++num_paths_;
2344 }
2345 }
2346 is_path_pair_active_.resize(num_paths_ * num_paths_, true);
2347 }
2348 }
2349 void DeactivatePathPair(int start1, int start2) {
2350 is_path_pair_active_[start_to_path_[start1] * num_paths_ +
2351 start_to_path_[start2]] = false;
2352 }
2353 void ActivatePath(int start) {
2354 const int p1 = start_to_path_[start];
2355 const int p1_block = num_paths_ * p1;
2356 for (int p2 = 0; p2 < num_paths_; ++p2) {
2357 is_path_pair_active_[p1_block + p2] = true;
2358 }
2359 for (int p2_block = 0; p2_block < is_path_pair_active_.size();
2360 p2_block += num_paths_) {
2361 is_path_pair_active_[p2_block + p1] = true;
2362 }
2363 }
2364 bool IsPathPairActive(int start1, int start2) const {
2365 return is_path_pair_active_[start_to_path_[start1] * num_paths_ +
2366 start_to_path_[start2]];
2367 }
2368
2369 private:
2370 int num_paths_ = 0;
2371 std::vector<int64_t> start_to_path_;
2372 std::vector<bool> is_path_pair_active_;
2373 };
2374
2375 std::unique_ptr<int[]> base_nodes_;
2376 std::unique_ptr<int[]> end_nodes_;
2377 std::unique_ptr<int[]> base_paths_;
2378 std::vector<int> node_path_starts_;
2379 std::vector<int> node_path_ends_;
2380 bool iterators_initialized_ = false;
2381#ifndef SWIG
2382 std::vector<BaseNodeIterators<PathOperator>> base_node_iterators_;
2383#endif // SWIG
2384 std::vector<int64_t> path_starts_;
2385 std::vector<int64_t> path_ends_;
2386 std::vector<bool> inactives_;
2387 bool just_started_;
2388 bool first_start_;
2389 int next_base_to_increment_;
2390 IterationParameters iteration_parameters_;
2391 bool optimal_paths_enabled_;
2392 std::vector<int> path_basis_;
2393 ActivePaths active_paths_;
2395#ifndef SWIG
2396 std::vector<std::vector<int64_t>> alternative_sets_;
2397#endif // SWIG
2398 std::vector<int> alternative_index_;
2399 std::vector<int64_t> active_in_alternative_set_;
2400 std::vector<int> sibling_alternative_;
2401
2402 friend class BaseNodeIterators<PathOperator>;
2403 friend class AlternativeNodeIterator;
2404 friend class NodeNeighborIterator;
2405};
2406
2407#ifndef SWIG
2409
2420 Solver* solver, const std::vector<IntVar*>& vars,
2421 const std::vector<IntVar*>& secondary_vars,
2422 std::function<int(int64_t)> start_empty_path_class,
2423 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2424 nullptr,
2425 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2426 nullptr);
2427
2429
2442
2444 Solver* solver, const std::vector<IntVar*>& vars,
2445 const std::vector<IntVar*>& secondary_vars,
2446 std::function<int(int64_t)> start_empty_path_class,
2447 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2448 nullptr,
2449 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2450 nullptr,
2451 int64_t chain_length = 1LL, bool single_path = false,
2452 const std::string& name = "Relocate");
2453
2455
2463
2465 Solver* solver, const std::vector<IntVar*>& vars,
2466 const std::vector<IntVar*>& secondary_vars,
2467 std::function<int(int64_t)> start_empty_path_class,
2468 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2469 nullptr,
2470 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2471 nullptr);
2472
2474
2484
2486 Solver* solver, const std::vector<IntVar*>& vars,
2487 const std::vector<IntVar*>& secondary_vars,
2488 std::function<int(int64_t)> start_empty_path_class,
2489 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2490 nullptr,
2491 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2492 nullptr);
2493
2495
2502
2504 Solver* solver, const std::vector<IntVar*>& vars,
2505 const std::vector<IntVar*>& secondary_vars,
2506 std::function<int(int64_t)> start_empty_path_class,
2507 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2508 nullptr,
2509 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2510 nullptr);
2511
2513
2520
2522 Solver* solver, const std::vector<IntVar*>& vars,
2523 const std::vector<IntVar*>& secondary_vars,
2524 std::function<int(int64_t)> start_empty_path_class);
2525
2526// ----- ExchangeAndMakeActive -----
2527
2528// ExchangeAndMakeActive exchanges two nodes and inserts an inactive node.
2529// Possible neighbors for paths 0 -> 2 -> 4, 1 -> 3 -> 6 and 5 inactive are:
2530// 0 -> 3 -> 4, 1 -> 5 -> 2 -> 6
2531// 0 -> 3 -> 5 -> 4, 1 -> 2 -> 6
2532// 0 -> 5 -> 3 -> 4, 1 -> 2 -> 6
2533// 0 -> 3 -> 4, 1 -> 2 -> 5 -> 6
2534//
2535// Warning this operator creates a very large neighborhood, with O(m*n^3)
2536// neighbors (n: number of active nodes, m: number of non active nodes).
2537// It should be used with only a small number of non active nodes.
2538// TODO(user): Add support for neighbors which would make this operator more
2539// usable.
2540
2542 Solver* solver, const std::vector<IntVar*>& vars,
2543 const std::vector<IntVar*>& secondary_vars,
2544 std::function<int(int64_t)> start_empty_path_class);
2545
2546// ----- ExchangePathEndsAndMakeActive -----
2547
2548// An operator which exchanges the first and last nodes of two paths and makes a
2549// node active.
2550// Possible neighbors for paths 0 -> 1 -> 2 -> 7, 6 -> 3 -> 4 -> 8
2551// and 5 inactive are:
2552// 0 -> 5 -> 3 -> 4 -> 7, 6 -> 1 -> 2 -> 8
2553// 0 -> 3 -> 4 -> 7, 6 -> 1 -> 5 -> 2 -> 8
2554// 0 -> 3 -> 4 -> 7, 6 -> 1 -> 2 -> 5 -> 8
2555// 0 -> 3 -> 5 -> 4 -> 7, 6 -> 1 -> 2 -> 8
2556// 0 -> 3 -> 4 -> 5 -> 7, 6 -> 1 -> 2 -> 8
2557//
2558// This neighborhood is an artificially reduced version of
2559// ExchangeAndMakeActiveOperator. It can still be used to opportunistically
2560// insert inactive nodes.
2561
2563 Solver* solver, const std::vector<IntVar*>& vars,
2564 const std::vector<IntVar*>& secondary_vars,
2565 std::function<int(int64_t)> start_empty_path_class);
2566
2568
2572
2574 Solver* solver, const std::vector<IntVar*>& vars,
2575 const std::vector<IntVar*>& secondary_vars,
2576 std::function<int(int64_t)> start_empty_path_class);
2577
2579
2585
2587 Solver* solver, const std::vector<IntVar*>& vars,
2588 const std::vector<IntVar*>& secondary_vars,
2589 std::function<int(int64_t)> start_empty_path_class);
2590
2592
2598
2600 Solver* solver, const std::vector<IntVar*>& vars,
2601 const std::vector<IntVar*>& secondary_vars,
2602 std::function<int(int64_t)> start_empty_path_class);
2603
2605
2612
2614 Solver* solver, const std::vector<IntVar*>& vars,
2615 const std::vector<IntVar*>& secondary_vars,
2616 std::function<int(int64_t)> start_empty_path_class);
2617
2619
2625
2627 Solver* solver, const std::vector<IntVar*>& vars,
2628 const std::vector<IntVar*>& secondary_vars,
2629 std::function<int(int64_t)> start_empty_path_class);
2630
2632
2634 Solver* solver, const std::vector<IntVar*>& vars,
2635 const std::vector<IntVar*>& secondary_vars,
2636 std::function<int(int64_t)> start_empty_path_class, int max_chain_size);
2637
2639
2650
2652 Solver* solver, const std::vector<IntVar*>& vars,
2653 const std::vector<IntVar*>& secondary_vars,
2654 std::function<int(int64_t)> start_empty_path_class);
2655
2657
2664
2666 const std::vector<IntVar*>& vars,
2667 const std::vector<IntVar*>& secondary_vars,
2668 Solver::IndexEvaluator3 evaluator,
2669 int chain_length);
2670
2678
2680 const std::vector<IntVar*>& vars,
2681 const std::vector<IntVar*>& secondary_vars,
2682 Solver::IndexEvaluator3 evaluator,
2683 int tsp_size);
2684
2686
2688 Solver* solver, const std::vector<IntVar*>& vars,
2689 const std::vector<IntVar*>& secondary_vars,
2690 const Solver::IndexEvaluator3& evaluator, bool topt);
2691
2693
2697
2699 const std::vector<IntVar*>& vars,
2700 const std::vector<IntVar*>& secondary_vars,
2701 int number_of_chunks, int chunk_size,
2702 bool unactive_fragments);
2703#endif // SWIG
2704
2705#if !defined(SWIG)
2706// After building a Directed Acyclic Graph, allows to generate sub-DAGs
2707// reachable from a node.
2708// Workflow:
2709// - Call AddArc() repeatedly to add arcs describing a DAG. Nodes are allocated
2710// on the user side, they must be nonnegative, and it is better but not
2711// mandatory for the set of nodes to be dense.
2712// - Call BuildGraph(). This precomputes all the information needed to make
2713// subsequent requests for sub-DAGs.
2714// - Call ComputeSortedSubDagArcs(node). This returns a view to arcs reachable
2715// from node, in topological order.
2716// All arcs must be added before calling BuildGraph(),
2717// and ComputeSortedSubDagArcs() can only be called after BuildGraph().
2718// If the arcs form a graph that has directed cycles,
2719// - in debug mode, BuildGraph() will crash.
2720// - otherwise, BuildGraph() will not crash, but ComputeSortedSubDagArcs()
2721// will only return a subset of arcs reachable by the given node.
2722class SubDagComputer {
2723 public:
2726 SubDagComputer() = default;
2727 // Adds an arc between node 'tail' and node 'head'. Nodes must be nonnegative.
2728 // Returns the index of the new arc, those are used to identify arcs when
2729 // calling ComputeSortedSubDagArcs().
2730 ArcId AddArc(NodeId tail, NodeId head) {
2731 DCHECK(!graph_was_built_);
2732 num_nodes_ = std::max(num_nodes_, std::max(tail.value(), head.value()) + 1);
2733 const ArcId arc_id(arcs_.size());
2734 arcs_.push_back({.tail = tail, .head = head, .arc_id = arc_id});
2735 return arc_id;
2736 }
2737 // Finishes the construction of the DAG. 'num_nodes' is the number of nodes
2738 // in the DAG and must be greater than all node indices passed to AddArc().
2739 void BuildGraph(int num_nodes);
2740 // Computes the arcs of the sub-DAG reachable from node returns a view of
2741 // those arcs in topological order.
2742 const std::vector<ArcId>& ComputeSortedSubDagArcs(NodeId node);
2743
2744 private:
2745 // Checks whether the underlying graph has a directed cycle.
2746 // Should be called after the graph has been built.
2747 bool HasDirectedCycle() const;
2748
2749 struct Arc {
2750 NodeId tail;
2751 NodeId head;
2752 ArcId arc_id;
2753 bool operator<(const Arc& other) const {
2754 return std::tie(tail, arc_id) < std::tie(other.tail, other.arc_id);
2755 }
2756 };
2757 int num_nodes_ = 0;
2758 std::vector<Arc> arcs_;
2759 // Initialized by BuildGraph(), after which the outgoing arcs of node n are
2760 // the range from arcs_[arcs_of_node_[n]] included to
2761 // arcs_[arcs_of_node_[n+1]] excluded.
2763 // Must be false before BuildGraph() is called, true afterwards.
2764 bool graph_was_built_ = false;
2765 // Used by ComputeSortedSubDagArcs.
2767 // Used by ComputeSortedSubDagArcs.
2768 std::vector<NodeId> nodes_to_visit_;
2769 // Used as output, set up as a member to allow reuse.
2770 std::vector<ArcId> sorted_arcs_;
2771};
2772
2773// A LocalSearchState is a container for variables with domains that can be
2774// relaxed and tightened, saved and restored. It represents the solution state
2775// of a local search engine, and allows it to go from solution to solution by
2776// relaxing some variables to form a new subproblem, then tightening those
2777// variables to move to a new solution representation. That state may be saved
2778// to an internal copy, or reverted to the last saved internal copy.
2779// Relaxing a variable returns its bounds to their initial state.
2780// Tightening a variable's bounds may make its min larger than its max,
2781// in that case, the tightening function will return false, and the state will
2782// be marked as invalid. No other operations than Revert() can be called on an
2783// invalid state: in particular, an invalid state cannot be saved.
2784class LocalSearchState {
2785 public:
2786 class Variable;
2787 DEFINE_STRONG_INT_TYPE(VariableDomainId, int);
2788 DEFINE_STRONG_INT_TYPE(ConstraintId, int);
2789 // Adds a variable domain to this state, returns a handler to the new domain.
2790 VariableDomainId AddVariableDomain(int64_t relaxed_min, int64_t relaxed_max);
2791 // Relaxes the domain, returns false iff the domain was already relaxed.
2792 bool RelaxVariableDomain(VariableDomainId domain_id);
2793 bool TightenVariableDomainMin(VariableDomainId domain_id, int64_t value);
2794 bool TightenVariableDomainMax(VariableDomainId domain_id, int64_t value);
2795 int64_t VariableDomainMin(VariableDomainId domain_id) const;
2796 int64_t VariableDomainMax(VariableDomainId domain_id) const;
2797 void ChangeRelaxedVariableDomain(VariableDomainId domain_id, int64_t min,
2798 int64_t max);
2800 // Propagation of all events.
2801 void PropagateRelax(VariableDomainId domain_id);
2803 // Makes a variable, an object with restricted operations on the underlying
2804 // domain identified by domain_id: only Relax, Tighten and Min/Max read
2805 // operations are available.
2807 // Makes a variable from an interval without going through a domain_id.
2808 // Can be used when no direct manipulation of the domain is needed.
2809 Variable MakeVariableWithRelaxedDomain(int64_t min, int64_t max);
2810 // Makes a variable with no state, this is meant as a placeholder.
2811 static Variable DummyVariable();
2812 void Commit();
2813 void Revert();
2814 bool StateIsFeasible() const {
2815 return state_domains_are_all_nonempty_ && num_committed_empty_domains_ == 0;
2816 }
2817 // Adds a constraint that output = input_offset + sum_i weight_i * input_i.
2818 void AddWeightedSumConstraint(
2819 const std::vector<VariableDomainId>& input_domain_ids,
2820 const std::vector<int64_t>& input_weights, int64_t input_offset,
2821 VariableDomainId output_domain_id);
2822 // Precomputes which domain change triggers which constraint(s).
2823 // Should be run after adding all constraints, before any Relax()/Tighten().
2824 void CompileConstraints();
2825
2826 private:
2827 // VariableDomains implement the domain of Variables.
2828 // Those are trailed, meaning they are saved on their first modification,
2829 // and can be reverted or committed in O(1) per modification.
2830 struct VariableDomain {
2831 int64_t min;
2832 int64_t max;
2833 };
2834 bool IntersectionIsEmpty(const VariableDomain& d1,
2835 const VariableDomain& d2) const {
2836 return d1.max < d2.min || d2.max < d1.min;
2837 }
2840 struct TrailedVariableDomain {
2841 VariableDomain committed_domain;
2842 VariableDomainId domain_id;
2843 };
2844 std::vector<TrailedVariableDomain> trailed_domains_;
2845 util_intops::StrongVector<VariableDomainId, bool> domain_is_trailed_;
2846 // True iff all domains have their min <= max.
2847 bool state_domains_are_all_nonempty_ = true;
2848 bool state_has_relaxed_domains_ = false;
2849 // Number of domains d for which the intersection of
2850 // current_domains_[d] and relaxed_domains_[d] is empty.
2851 int num_committed_empty_domains_ = 0;
2852 int trailed_num_committed_empty_domains_ = 0;
2853
2854 // Constraints may be trailed too, they decide how to track their internal
2855 // structure.
2856 class Constraint;
2857 void TrailConstraint(Constraint* constraint) {
2858 trailed_constraints_.push_back(constraint);
2859 }
2860 std::vector<Constraint*> trailed_constraints_;
2861
2862 // Stores domain-constraint dependencies, allows to generate topological
2863 // orderings of dependency arcs reachable from nodes.
2864 class DependencyGraph {
2865 public:
2866 DependencyGraph() {}
2867 // There are two kinds of domain-constraint dependencies:
2868 // - domain -> constraint when the domain is an input to the constraint.
2869 // Then the label is the index of the domain in the input tuple.
2870 // - constraint -> domain when the domain is the output of the constraint.
2871 // Then, the label is -1.
2872 struct Dependency {
2873 VariableDomainId domain_id;
2874 int input_index;
2875 ConstraintId constraint_id;
2876 };
2877 // Adds all dependencies domains[i] -> constraint labelled by i.
2878 void AddDomainsConstraintDependencies(
2879 const std::vector<VariableDomainId>& domain_ids,
2880 ConstraintId constraint_id);
2881 // Adds a dependency domain -> constraint labelled by -1.
2882 void AddConstraintDomainDependency(ConstraintId constraint_id,
2883 VariableDomainId domain_id);
2884 // After all dependencies have been added,
2885 // builds the DAG representation that allows to compute sorted dependencies.
2886 void BuildDependencyDAG(int num_domains);
2887 // Returns a view on the list of arc dependencies reachable by given domain,
2888 // in some topological order of the overall DAG. Modifying the graph or
2889 // calling ComputeSortedDependencies() again invalidates the view.
2890 const std::vector<Dependency>& ComputeSortedDependencies(
2892
2893 private:
2894 using ArcId = SubDagComputer::ArcId;
2895 using NodeId = SubDagComputer::NodeId;
2896 // Returns dag_node_of_domain_[domain_id] if already defined,
2897 // or makes a node for domain_id, possibly extending dag_node_of_domain_.
2898 NodeId GetOrCreateNodeOfDomainId(VariableDomainId domain_id);
2899 // Returns dag_node_of_constraint_[constraint_id] if already defined,
2900 // or makes a node for constraint_id, possibly extending
2901 // dag_node_of_constraint_.
2902 NodeId GetOrCreateNodeOfConstraintId(ConstraintId constraint_id);
2903 // Structure of the expression DAG, used to buffer propagation storage.
2904 SubDagComputer dag_;
2905 // Maps arcs of dag_ to domain/constraint dependencies.
2906 util_intops::StrongVector<ArcId, Dependency> dependency_of_dag_arc_;
2907 // Maps domain ids to dag_ nodes.
2909 // Maps constraint ids to dag_ nodes.
2911 // Number of nodes currently allocated in dag_.
2912 // Reserve node 0 as a default dummy node with no dependencies.
2913 int num_dag_nodes_ = 1;
2914 // Used as reusable output of ComputeSortedDependencies().
2915 std::vector<Dependency> sorted_dependencies_;
2916 };
2917 DependencyGraph dependency_graph_;
2918
2919 // Propagation order storage: each domain change triggers constraints.
2920 // Each trigger tells a constraint that a domain changed, and identifies
2921 // the domain by the index in the list of the constraint's inputs.
2922 struct Trigger {
2923 Constraint* constraint;
2924 int input_index;
2925 };
2926 // Triggers of all constraints, concatenated.
2927 // The triggers of domain i are stored from triggers_of_domain_[i]
2928 // to triggers_of_domain_[i+1] excluded.
2929 std::vector<Trigger> triggers_;
2931
2932 // Constraints are used to form expressions that make up the objective.
2933 // Constraints are directed: they have inputs and an output, moreover the
2934 // constraint-domain graph must not have directed cycles.
2935 class Constraint {
2936 public:
2937 virtual ~Constraint() = default;
2938 virtual LocalSearchState::VariableDomain Propagate(int input_index) = 0;
2939 virtual VariableDomainId Output() const = 0;
2940 virtual void Commit() = 0;
2941 virtual void Revert() = 0;
2942 };
2943 // WeightedSum constraints enforces the equation:
2944 // output = offset + sum_i input_weights[i] * input_domain_ids[i]
2945 class WeightedSum final : public Constraint {
2946 public:
2947 WeightedSum(LocalSearchState* state,
2948 const std::vector<VariableDomainId>& input_domain_ids,
2949 const std::vector<int64_t>& input_weights, int64_t input_offset,
2950 VariableDomainId output);
2951 ~WeightedSum() override = default;
2952 LocalSearchState::VariableDomain Propagate(int input_index) override;
2953 void Commit() override;
2954 void Revert() override;
2955 VariableDomainId Output() const override { return output_; }
2956
2957 private:
2958 // Weighted variable holds a variable's domain, an associated weight,
2959 // and the variable's last known min and max.
2960 struct WeightedVariable {
2961 int64_t min;
2962 int64_t max;
2963 int64_t committed_min;
2964 int64_t committed_max;
2965 int64_t weight;
2966 VariableDomainId domain;
2967 bool is_trailed;
2968 void Commit() {
2969 committed_min = min;
2970 committed_max = max;
2971 is_trailed = false;
2972 }
2973 void Revert() {
2974 min = committed_min;
2975 max = committed_max;
2976 is_trailed = false;
2977 }
2978 };
2979 std::vector<WeightedVariable> inputs_;
2980 std::vector<WeightedVariable*> trailed_inputs_;
2981 // Invariants held by this constraint to allow O(1) propagation.
2982 struct Invariants {
2983 // Number of inputs_[i].min equal to kint64min.
2984 int64_t num_neg_inf;
2985 // Sum of inputs_[i].min that are different from kint64min.
2986 int64_t wsum_mins;
2987 // Number of inputs_[i].max equal to kint64max.
2988 int64_t num_pos_inf;
2989 // Sum of inputs_[i].max that are different from kint64max.
2990 int64_t wsum_maxs;
2991 };
2992 Invariants invariants_;
2993 Invariants committed_invariants_;
2994
2995 const VariableDomainId output_;
2996 LocalSearchState* const state_;
2997 bool constraint_is_trailed_ = false;
2998 };
2999 // Used to identify constraints and hold ownership.
3000 util_intops::StrongVector<ConstraintId, std::unique_ptr<Constraint>>
3001 constraints_;
3002};
3003
3004// A LocalSearchState Variable can only be created by a LocalSearchState,
3005// then it is meant to be passed by copy. If at some point the duplication of
3006// LocalSearchState pointers is too expensive, we could switch to index only,
3007// and the user would have to know the relevant state. The present setup allows
3008// to ensure that variable users will not misuse the state.
3009class LocalSearchState::Variable {
3010 public:
3011 Variable() : state_(nullptr), domain_id_(VariableDomainId(-1)) {}
3012 int64_t Min() const {
3013 DCHECK(Exists());
3014 return state_->VariableDomainMin(domain_id_);
3015 }
3016 int64_t Max() const {
3017 DCHECK(Exists());
3018 return state_->VariableDomainMax(domain_id_);
3019 }
3020 // Sets variable's minimum to max(Min(), new_min) and propagates the change.
3021 // Returns true iff the variable domain is nonempty and propagation succeeded.
3022 bool SetMin(int64_t new_min) const {
3023 if (!Exists()) return true;
3024 return state_->TightenVariableDomainMin(domain_id_, new_min) &&
3025 state_->PropagateTighten(domain_id_);
3027 // Sets variable's maximum to min(Max(), new_max) and propagates the change.
3028 // Returns true iff the variable domain is nonempty and propagation succeeded.
3029 bool SetMax(int64_t new_max) const {
3030 if (!Exists()) return true;
3031 return state_->TightenVariableDomainMax(domain_id_, new_max) &&
3032 state_->PropagateTighten(domain_id_);
3033 }
3034 void Relax() const {
3035 if (state_ == nullptr) return;
3036 if (state_->RelaxVariableDomain(domain_id_)) {
3037 state_->PropagateRelax(domain_id_);
3038 }
3039 }
3040 bool Exists() const { return state_ != nullptr; }
3041
3042 private:
3043 // Only LocalSearchState can construct LocalSearchVariables.
3044 friend class LocalSearchState;
3045
3046 Variable(LocalSearchState* state, VariableDomainId domain_id)
3047 : state_(state), domain_id_(domain_id) {}
3048
3050 VariableDomainId domain_id_;
3051};
3052#endif // !defined(SWIG)
3053
3055
3067
3070class LocalSearchFilter : public BaseObject {
3071 public:
3074 virtual void Relax(const Assignment*, const Assignment*) {}
3076 virtual void Commit(const Assignment*, const Assignment*) {}
3077
3085 /// but the delta (a,0) will be accepted.
3086 /// TODO(user): Remove arguments when there are no more need for those.
3087 virtual bool Accept(const Assignment* delta, const Assignment* deltadelta,
3088 int64_t objective_min, int64_t objective_max) = 0;
3089 virtual bool IsIncremental() const { return false; }
3090
3096 virtual void Synchronize(const Assignment* assignment,
3097 const Assignment* delta) = 0;
3099 virtual void Revert() {}
3100
3102 virtual void Reset() {}
3103
3105 virtual int64_t GetSynchronizedObjectiveValue() const { return 0LL; }
3107 // If the last Accept() call returned false, returns an undefined value.
3108 virtual int64_t GetAcceptedObjectiveValue() const { return 0LL; }
3109};
3110
3115 public:
3116 // This class is responsible for calling filters methods in a correct order.
3117 // For now, an order is specified explicitly by the user.
3118 enum FilterEventType { kAccept, kRelax };
3119 struct FilterEvent {
3121 FilterEventType event_type;
3122 int priority;
3124
3125 std::string DebugString() const override {
3126 return "LocalSearchFilterManager";
3127 }
3128 // Builds a manager that calls filter methods ordered by increasing priority.
3129 // Note that some filters might appear only once, if their Relax() or Accept()
3130 // are trivial.
3131 explicit LocalSearchFilterManager(std::vector<FilterEvent> filter_events);
3132 // Builds a manager that calls filter methods using the following ordering:
3133 // first Relax() in vector order, then Accept() in vector order.
3134 explicit LocalSearchFilterManager(std::vector<LocalSearchFilter*> filters);
3136 // Calls Revert() of filters, in reverse order of Relax events.
3137 void Revert();
3139
3140 /// The monitor has its Begin/EndFiltering events triggered.
3141 bool Accept(LocalSearchMonitor* monitor, const Assignment* delta,
3142 const Assignment* deltadelta, int64_t objective_min,
3143 int64_t objective_max);
3145 void Synchronize(const Assignment* assignment, const Assignment* delta);
3146 int64_t GetSynchronizedObjectiveValue() const { return synchronized_value_; }
3147 int64_t GetAcceptedObjectiveValue() const { return accepted_value_; }
3148
3149 private:
3150 // Finds the last event (incremental -itself- or not) with the same priority
3151 // as the last incremental event.
3152 void FindIncrementalEventEnd();
3153
3154 std::vector<FilterEvent> events_;
3155 int last_event_called_ = -1;
3156 // If a filter is incremental, its Relax() and Accept() must be called for
3157 // every candidate, even if the Accept() of a prior filter rejected it.
3158 // To ensure that those incremental filters have consistent inputs, all
3159 // intermediate events with Relax() must also be called.
3160 int incremental_events_end_ = 0;
3161 int64_t synchronized_value_;
3162 int64_t accepted_value_;
3163};
3164
3166 public:
3167 explicit IntVarLocalSearchFilter(const std::vector<IntVar*>& vars);
3168 ~IntVarLocalSearchFilter() override;
3171 void Synchronize(const Assignment* assignment,
3172 const Assignment* delta) override;
3173
3174 bool FindIndex(IntVar* const var, int64_t* index) const {
3175 DCHECK(index != nullptr);
3176 const int var_index = var->index();
3177 *index = (var_index < var_index_to_index_.size())
3178 ? var_index_to_index_[var_index]
3179 : kUnassigned;
3180 return *index != kUnassigned;
3181 }
3182
3184 void AddVars(const std::vector<IntVar*>& vars);
3185 int Size() const { return vars_.size(); }
3186 IntVar* Var(int index) const { return vars_[index]; }
3187 int64_t Value(int index) const {
3188 DCHECK(IsVarSynced(index));
3189 return values_[index];
3190 }
3191 bool IsVarSynced(int index) const { return var_synced_[index]; }
3192
3193 protected:
3194 virtual void OnSynchronize(const Assignment*) {}
3195 void SynchronizeOnAssignment(const Assignment* assignment);
3196
3197 private:
3198 std::vector<IntVar*> vars_;
3199 std::vector<int64_t> values_;
3200 std::vector<bool> var_synced_;
3201 std::vector<int> var_index_to_index_;
3202 static const int kUnassigned;
3203};
3204
3205class PropagationMonitor : public SearchMonitor {
3206 public:
3207 explicit PropagationMonitor(Solver* solver);
3208 ~PropagationMonitor() override;
3209 std::string DebugString() const override { return "PropagationMonitor"; }
3210
3212 virtual void BeginConstraintInitialPropagation(Constraint* constraint) = 0;
3213 virtual void EndConstraintInitialPropagation(Constraint* constraint) = 0;
3214 virtual void BeginNestedConstraintInitialPropagation(Constraint* parent,
3215 Constraint* nested) = 0;
3216 virtual void EndNestedConstraintInitialPropagation(Constraint* parent,
3217 Constraint* nested) = 0;
3218 virtual void RegisterDemon(Demon* demon) = 0;
3219 virtual void BeginDemonRun(Demon* demon) = 0;
3220 virtual void EndDemonRun(Demon* demon) = 0;
3221 virtual void StartProcessingIntegerVariable(IntVar* var) = 0;
3222 virtual void EndProcessingIntegerVariable(IntVar* var) = 0;
3223 virtual void PushContext(const std::string& context) = 0;
3224 virtual void PopContext() = 0;
3226 virtual void SetMin(IntExpr* expr, int64_t new_min) = 0;
3227 virtual void SetMax(IntExpr* expr, int64_t new_max) = 0;
3228 virtual void SetRange(IntExpr* expr, int64_t new_min, int64_t new_max) = 0;
3230 virtual void SetMin(IntVar* var, int64_t new_min) = 0;
3231 virtual void SetMax(IntVar* var, int64_t new_max) = 0;
3232 virtual void SetRange(IntVar* var, int64_t new_min, int64_t new_max) = 0;
3233 virtual void RemoveValue(IntVar* var, int64_t value) = 0;
3234 virtual void SetValue(IntVar* var, int64_t value) = 0;
3235 virtual void RemoveInterval(IntVar* var, int64_t imin, int64_t imax) = 0;
3236 virtual void SetValues(IntVar* var, const std::vector<int64_t>& values) = 0;
3237 virtual void RemoveValues(IntVar* var,
3238 const std::vector<int64_t>& values) = 0;
3240 virtual void SetStartMin(IntervalVar* var, int64_t new_min) = 0;
3241 virtual void SetStartMax(IntervalVar* var, int64_t new_max) = 0;
3242 virtual void SetStartRange(IntervalVar* var, int64_t new_min,
3243 int64_t new_max) = 0;
3244 virtual void SetEndMin(IntervalVar* var, int64_t new_min) = 0;
3245 virtual void SetEndMax(IntervalVar* var, int64_t new_max) = 0;
3246 virtual void SetEndRange(IntervalVar* var, int64_t new_min,
3247 int64_t new_max) = 0;
3248 virtual void SetDurationMin(IntervalVar* var, int64_t new_min) = 0;
3249 virtual void SetDurationMax(IntervalVar* var, int64_t new_max) = 0;
3250 virtual void SetDurationRange(IntervalVar* var, int64_t new_min,
3251 int64_t new_max) = 0;
3252 virtual void SetPerformed(IntervalVar* var, bool value) = 0;
3254 virtual void RankFirst(SequenceVar* var, int index) = 0;
3255 virtual void RankNotFirst(SequenceVar* var, int index) = 0;
3256 virtual void RankLast(SequenceVar* var, int index) = 0;
3257 virtual void RankNotLast(SequenceVar* var, int index) = 0;
3258 virtual void RankSequence(SequenceVar* var,
3259 const std::vector<int>& rank_first,
3260 const std::vector<int>& rank_last,
3261 const std::vector<int>& unperformed) = 0;
3263 void Install() override;
3266class LocalSearchMonitor : public SearchMonitor {
3267 // TODO(user): Add monitoring of local search filters.
3268 public:
3271 std::string DebugString() const override { return "LocalSearchMonitor"; }
3274 virtual void BeginOperatorStart() = 0;
3275 virtual void EndOperatorStart() = 0;
3276 virtual void BeginMakeNextNeighbor(const LocalSearchOperator* op) = 0;
3277 virtual void EndMakeNextNeighbor(const LocalSearchOperator* op,
3278 bool neighbor_found, const Assignment* delta,
3279 const Assignment* deltadelta) = 0;
3280 virtual void BeginFilterNeighbor(const LocalSearchOperator* op) = 0;
3282 bool neighbor_found) = 0;
3283 virtual void BeginAcceptNeighbor(const LocalSearchOperator* op) = 0;
3284 virtual void EndAcceptNeighbor(const LocalSearchOperator* op,
3285 bool neighbor_found) = 0;
3286 virtual void BeginFiltering(const LocalSearchFilter* filter) = 0;
3287 virtual void EndFiltering(const LocalSearchFilter* filter, bool reject) = 0;
3288
3289 virtual bool IsActive() const = 0;
3292 void Install() override;
3293};
3294
3295class OR_DLL BooleanVar : public IntVar {
3296 public:
3297 static const int kUnboundBooleanVarValue;
3299 explicit BooleanVar(Solver* const s, const std::string& name = "")
3300 : IntVar(s, name), value_(kUnboundBooleanVarValue) {}
3302 ~BooleanVar() override {}
3303
3304 int64_t Min() const override { return (value_ == 1); }
3305 void SetMin(int64_t m) override;
3306 int64_t Max() const override { return (value_ != 0); }
3307 void SetMax(int64_t m) override;
3308 void SetRange(int64_t mi, int64_t ma) override;
3309 bool Bound() const override { return (value_ != kUnboundBooleanVarValue); }
3310 int64_t Value() const override {
3311 CHECK_NE(value_, kUnboundBooleanVarValue) << "variable is not bound";
3312 return value_;
3313 }
3314 void RemoveValue(int64_t v) override;
3315 void RemoveInterval(int64_t l, int64_t u) override;
3316 void WhenBound(Demon* d) override;
3317 void WhenRange(Demon* d) override { WhenBound(d); }
3318 void WhenDomain(Demon* d) override { WhenBound(d); }
3319 uint64_t Size() const override;
3320 bool Contains(int64_t v) const override;
3321 IntVarIterator* MakeHoleIterator(bool reversible) const override;
3322 IntVarIterator* MakeDomainIterator(bool reversible) const override;
3323 std::string DebugString() const override;
3324 int VarType() const override { return BOOLEAN_VAR; }
3326 IntVar* IsEqual(int64_t constant) override;
3327 IntVar* IsDifferent(int64_t constant) override;
3328 IntVar* IsGreaterOrEqual(int64_t constant) override;
3329 IntVar* IsLessOrEqual(int64_t constant) override;
3330
3331 virtual void RestoreValue() = 0;
3332 std::string BaseName() const override { return "BooleanVar"; }
3334 int RawValue() const { return value_; }
3335
3336 protected:
3337 int value_;
3338 SimpleRevFIFO<Demon*> bound_demons_;
3340};
3341
3342class SymmetryManager;
3343
3348 public:
3350 : symmetry_manager_(nullptr), index_in_symmetry_manager_(-1) {}
3351 ~SymmetryBreaker() override {}
3353 void AddIntegerVariableEqualValueClause(IntVar* var, int64_t value);
3354 void AddIntegerVariableGreaterOrEqualValueClause(IntVar* var, int64_t value);
3355 void AddIntegerVariableLessOrEqualValueClause(IntVar* var, int64_t value);
3356
3357 private:
3358 friend class SymmetryManager;
3359 void set_symmetry_manager_and_index(SymmetryManager* manager, int index) {
3360 CHECK(symmetry_manager_ == nullptr);
3361 CHECK_EQ(-1, index_in_symmetry_manager_);
3362 symmetry_manager_ = manager;
3363 index_in_symmetry_manager_ = index;
3365 SymmetryManager* symmetry_manager() const { return symmetry_manager_; }
3366 int index_in_symmetry_manager() const { return index_in_symmetry_manager_; }
3367
3368 SymmetryManager* symmetry_manager_;
3370 int index_in_symmetry_manager_;
3371};
3372
3375class SearchLog : public SearchMonitor {
3376 public:
3377 SearchLog(Solver* solver, std::vector<IntVar*> vars, std::string vars_name,
3378 std::vector<double> scaling_factors, std::vector<double> offsets,
3379 std::function<std::string()> display_callback,
3380 bool display_on_new_solutions_only, int period);
3381 ~SearchLog() override;
3382 void EnterSearch() override;
3383 void ExitSearch() override;
3384 bool AtSolution() override;
3385 void BeginFail() override;
3386 void NoMoreSolutions() override;
3387 void AcceptUncheckedNeighbor() override;
3388 void ApplyDecision(Decision* decision) override;
3389 void RefuteDecision(Decision* decision) override;
3391 void Maintain();
3392 void BeginInitialPropagation() override;
3393 void EndInitialPropagation() override;
3394 std::string DebugString() const override;
3395
3396 protected:
3397 /* Bottleneck function used for all UI related output. */
3398 virtual void OutputLine(const std::string& line);
3399
3400 private:
3401 static std::string MemoryUsage();
3402
3403 const int period_;
3404 std::unique_ptr<WallTimer> timer_;
3405 const std::vector<IntVar*> vars_;
3406 const std::string vars_name_;
3407 const std::vector<double> scaling_factors_;
3408 const std::vector<double> offsets_;
3409 std::function<std::string()> display_callback_;
3410 const bool display_on_new_solutions_only_;
3411 int nsol_;
3412 absl::Duration tick_;
3413 std::vector<int64_t> objective_min_;
3414 std::vector<int64_t> objective_max_;
3415 std::vector<int64_t> last_objective_value_;
3416 absl::Duration last_objective_timestamp_;
3417 int min_right_depth_;
3418 int max_depth_;
3419 int sliding_min_depth_;
3420 int sliding_max_depth_;
3421 int neighbors_offset_ = 0;
3422};
3423
3428class ModelCache {
3429 public:
3430 enum VoidConstraintType {
3431 VOID_FALSE_CONSTRAINT = 0,
3432 VOID_TRUE_CONSTRAINT,
3433 VOID_CONSTRAINT_MAX,
3434 };
3435
3436 enum VarConstantConstraintType {
3437 VAR_CONSTANT_EQUALITY = 0,
3438 VAR_CONSTANT_GREATER_OR_EQUAL,
3439 VAR_CONSTANT_LESS_OR_EQUAL,
3440 VAR_CONSTANT_NON_EQUALITY,
3441 VAR_CONSTANT_CONSTRAINT_MAX,
3442 };
3458
3480 enum ExprExprConstantExpressionType {
3498 enum VarConstantConstantExpressionType {
3499 VAR_CONSTANT_CONSTANT_SEMI_CONTINUOUS = 0,
3526 virtual ~ModelCache();
3527
3528 virtual void Clear() = 0;
3533
3534 virtual void InsertVoidConstraint(Constraint* ct,
3539 IntVar* var, int64_t value, VarConstantConstraintType type) const = 0;
3540
3541 virtual void InsertVarConstantConstraint(Constraint* ct, IntVar* var,
3542 int64_t value,
3544
3546
3548 IntVar* var, int64_t value1, int64_t value2,
3550
3552 Constraint* ct, IntVar* var, int64_t value1, int64_t value2,
3554
3558 IntExpr* expr1, IntExpr* expr2, ExprExprConstraintType type) const = 0;
3559
3560 virtual void InsertExprExprConstraint(Constraint* ct, IntExpr* expr1,
3561 IntExpr* expr2,
3563
3565
3567 ExprExpressionType type) const = 0;
3568
3569 virtual void InsertExprExpression(IntExpr* expression, IntExpr* expr,
3570 ExprExpressionType type) = 0;
3571
3573
3575 IntExpr* expr, int64_t value, ExprConstantExpressionType type) const = 0;
3576
3577 virtual void InsertExprConstantExpression(
3578 IntExpr* expression, IntExpr* var, int64_t value,
3580
3582
3584 IntExpr* var1, IntExpr* var2, ExprExprExpressionType type) const = 0;
3585
3586 virtual void InsertExprExprExpression(IntExpr* expression, IntExpr* var1,
3587 IntExpr* var2,
3588 ExprExprExpressionType type) = 0;
3591
3593 IntExpr* var1, IntExpr* var2, int64_t constant,
3594 ExprExprConstantExpressionType type) const = 0;
3595
3597 IntExpr* expression, IntExpr* var1, IntExpr* var2, int64_t constant,
3599
3603 IntVar* var, int64_t value1, int64_t value2,
3604 VarConstantConstantExpressionType type) const = 0;
3605
3607 IntExpr* expression, IntVar* var, int64_t value1, int64_t value2,
3609
3613 IntVar* var, const std::vector<int64_t>& values,
3614 VarConstantArrayExpressionType type) const = 0;
3615
3617 IntExpr* expression, IntVar* var, const std::vector<int64_t>& values,
3619
3623 const std::vector<IntVar*>& vars, VarArrayExpressionType type) const = 0;
3624
3625 virtual void InsertVarArrayExpression(IntExpr* expression,
3626 const std::vector<IntVar*>& vars,
3628
3630
3632 const std::vector<IntVar*>& vars, const std::vector<int64_t>& values,
3634
3636 IntExpr* expression, const std::vector<IntVar*>& var,
3637 const std::vector<int64_t>& values,
3639
3641
3643 const std::vector<IntVar*>& vars, int64_t value,
3644 VarArrayConstantExpressionType type) const = 0;
3645
3647 IntExpr* expression, const std::vector<IntVar*>& var, int64_t value,
3649
3650 Solver* solver() const;
3651
3652 private:
3653 Solver* const solver_;
3654};
3655
3657#if !defined(SWIG)
3658class ArgumentHolder {
3659 public:
3661 const std::string& TypeName() const;
3662 void SetTypeName(const std::string& type_name);
3663
3665 void SetIntegerArgument(const std::string& arg_name, int64_t value);
3666 void SetIntegerArrayArgument(const std::string& arg_name,
3667 const std::vector<int64_t>& values);
3668 void SetIntegerMatrixArgument(const std::string& arg_name,
3669 const IntTupleSet& values);
3670 void SetIntegerExpressionArgument(const std::string& arg_name, IntExpr* expr);
3671 void SetIntegerVariableArrayArgument(const std::string& arg_name,
3672 const std::vector<IntVar*>& vars);
3673 void SetIntervalArgument(const std::string& arg_name, IntervalVar* var);
3674 void SetIntervalArrayArgument(const std::string& arg_name,
3675 const std::vector<IntervalVar*>& vars);
3676 void SetSequenceArgument(const std::string& arg_name, SequenceVar* var);
3677 void SetSequenceArrayArgument(const std::string& arg_name,
3678 const std::vector<SequenceVar*>& vars);
3679
3681 bool HasIntegerExpressionArgument(const std::string& arg_name) const;
3682 bool HasIntegerVariableArrayArgument(const std::string& arg_name) const;
3683
3685 int64_t FindIntegerArgumentWithDefault(const std::string& arg_name,
3686 int64_t def) const;
3687 int64_t FindIntegerArgumentOrDie(const std::string& arg_name) const;
3688 const std::vector<int64_t>& FindIntegerArrayArgumentOrDie(
3689 const std::string& arg_name) const;
3691 const std::string& arg_name) const;
3692
3694 const std::string& arg_name) const;
3695 const std::vector<IntVar*>& FindIntegerVariableArrayArgumentOrDie(
3696 const std::string& arg_name) const;
3697
3698 private:
3699 std::string type_name_;
3700 absl::flat_hash_map<std::string, int64_t> integer_argument_;
3701 absl::flat_hash_map<std::string, std::vector<int64_t>>
3702 integer_array_argument_;
3703 absl::flat_hash_map<std::string, IntTupleSet> matrix_argument_;
3704 absl::flat_hash_map<std::string, IntExpr*> integer_expression_argument_;
3705 absl::flat_hash_map<std::string, IntervalVar*> interval_argument_;
3706 absl::flat_hash_map<std::string, SequenceVar*> sequence_argument_;
3707 absl::flat_hash_map<std::string, std::vector<IntVar*>>
3708 integer_variable_array_argument_;
3709 absl::flat_hash_map<std::string, std::vector<IntervalVar*>>
3710 interval_array_argument_;
3711 absl::flat_hash_map<std::string, std::vector<SequenceVar*>>
3712 sequence_array_argument_;
3713};
3714
3716class ModelParser : public ModelVisitor {
3717 public:
3718 ModelParser();
3719
3720 ~ModelParser() override;
3721
3723 void BeginVisitModel(const std::string& solver_name) override;
3724 void EndVisitModel(const std::string& solver_name) override;
3725 void BeginVisitConstraint(const std::string& type_name,
3726 const Constraint* constraint) override;
3727 void EndVisitConstraint(const std::string& type_name,
3728 const Constraint* constraint) override;
3729 void BeginVisitIntegerExpression(const std::string& type_name,
3730 const IntExpr* expr) override;
3731 void EndVisitIntegerExpression(const std::string& type_name,
3732 const IntExpr* expr) override;
3733 void VisitIntegerVariable(const IntVar* variable, IntExpr* delegate) override;
3734 void VisitIntegerVariable(const IntVar* variable,
3735 const std::string& operation, int64_t value,
3736 IntVar* delegate) override;
3737 void VisitIntervalVariable(const IntervalVar* variable,
3738 const std::string& operation, int64_t value,
3739 IntervalVar* delegate) override;
3740 void VisitSequenceVariable(const SequenceVar* variable) override;
3742 void VisitIntegerArgument(const std::string& arg_name,
3743 int64_t value) override;
3744 void VisitIntegerArrayArgument(const std::string& arg_name,
3745 const std::vector<int64_t>& values) override;
3746 void VisitIntegerMatrixArgument(const std::string& arg_name,
3747 const IntTupleSet& values) override;
3749 void VisitIntegerExpressionArgument(const std::string& arg_name,
3750 IntExpr* argument) override;
3752 const std::string& arg_name,
3753 const std::vector<IntVar*>& arguments) override;
3755 void VisitIntervalArgument(const std::string& arg_name,
3756 IntervalVar* argument) override;
3758 const std::string& arg_name,
3759 const std::vector<IntervalVar*>& arguments) override;
3761 void VisitSequenceArgument(const std::string& arg_name,
3762 SequenceVar* argument) override;
3764 const std::string& arg_name,
3765 const std::vector<SequenceVar*>& arguments) override;
3766
3767 protected:
3768 void PushArgumentHolder();
3769 void PopArgumentHolder();
3770 ArgumentHolder* Top() const;
3771
3772 private:
3773 std::vector<ArgumentHolder*> holders_;
3774};
3775
3776template <class T>
3777class ArrayWithOffset : public BaseObject {
3778 public:
3779 ArrayWithOffset(int64_t index_min, int64_t index_max)
3780 : index_min_(index_min),
3781 index_max_(index_max),
3782 values_(new T[index_max - index_min + 1]) {
3783 DCHECK_LE(index_min, index_max);
3784 }
3785
3786 ~ArrayWithOffset() override {}
3787
3788 virtual T Evaluate(int64_t index) const {
3789 DCHECK_GE(index, index_min_);
3790 DCHECK_LE(index, index_max_);
3791 return values_[index - index_min_];
3793
3794 void SetValue(int64_t index, T value) {
3795 DCHECK_GE(index, index_min_);
3796 DCHECK_LE(index, index_max_);
3797 values_[index - index_min_] = value;
3798 }
3799
3800 std::string DebugString() const override { return "ArrayWithOffset"; }
3802 private:
3803 const int64_t index_min_;
3804 const int64_t index_max_;
3805 std::unique_ptr<T[]> values_;
3806};
3807#endif // SWIG
3808
3809/// This class is a reversible growing array. In can grow in both
3810/// directions, and even accept negative indices. The objects stored
3811/// have a type T. As it relies on the solver for reversibility, these
3812/// objects can be up-casted to 'C' when using Solver::SaveValue().
3813template <class T, class C>
3814class RevGrowingArray {
3815 public:
3816 explicit RevGrowingArray(int64_t block_size)
3817 : block_size_(block_size), block_offset_(0) {
3818 CHECK_GT(block_size, 0);
3819 }
3820
3822 for (int i = 0; i < elements_.size(); ++i) {
3823 delete[] elements_[i];
3824 }
3825 }
3826
3827 T At(int64_t index) const {
3828 const int64_t block_index = ComputeBlockIndex(index);
3829 const int64_t relative_index = block_index - block_offset_;
3830 if (relative_index < 0 || relative_index >= elements_.size()) {
3831 return T();
3832 }
3833 const T* block = elements_[relative_index];
3834 return block != nullptr ? block[index - block_index * block_size_] : T();
3835 }
3837 void RevInsert(Solver* const solver, int64_t index, T value) {
3838 const int64_t block_index = ComputeBlockIndex(index);
3839 T* const block = GetOrCreateBlock(block_index);
3840 const int64_t residual = index - block_index * block_size_;
3841 solver->SaveAndSetValue(reinterpret_cast<C*>(&block[residual]),
3842 reinterpret_cast<C>(value));
3843 }
3844
3845 private:
3846 T* NewBlock() const {
3847 T* const result = new T[block_size_];
3848 for (int i = 0; i < block_size_; ++i) {
3849 result[i] = T();
3850 }
3851 return result;
3853
3854 T* GetOrCreateBlock(int block_index) {
3855 if (elements_.size() == 0) {
3856 block_offset_ = block_index;
3857 GrowUp(block_index);
3858 } else if (block_index < block_offset_) {
3859 GrowDown(block_index);
3860 } else if (block_index - block_offset_ >= elements_.size()) {
3861 GrowUp(block_index);
3862 }
3863 T* block = elements_[block_index - block_offset_];
3864 if (block == nullptr) {
3865 block = NewBlock();
3866 elements_[block_index - block_offset_] = block;
3867 }
3868 return block;
3869 }
3870
3871 int64_t ComputeBlockIndex(int64_t value) const {
3872 return value >= 0 ? value / block_size_
3873 : (value - block_size_ + 1) / block_size_;
3874 }
3875
3876 void GrowUp(int64_t block_index) {
3877 elements_.resize(block_index - block_offset_ + 1);
3878 }
3879
3880 void GrowDown(int64_t block_index) {
3881 const int64_t delta = block_offset_ - block_index;
3882 block_offset_ = block_index;
3883 DCHECK_GT(delta, 0);
3884 elements_.insert(elements_.begin(), delta, nullptr);
3885 }
3886
3887 const int64_t block_size_;
3888 std::vector<T*> elements_;
3889 int block_offset_;
3890};
3891
3896template <class T>
3897class RevIntSet {
3898 public:
3899 static constexpr int kNoInserted = -1;
3900
3902 explicit RevIntSet(int capacity)
3903 : elements_(new T[capacity]),
3904 num_elements_(0),
3905 capacity_(capacity),
3906 position_(new int[capacity]),
3907 delete_position_(true) {
3908 for (int i = 0; i < capacity; ++i) {
3909 position_[i] = kNoInserted;
3910 }
3911 }
3914 RevIntSet(int capacity, int* shared_positions, int shared_positions_size)
3915 : elements_(new T[capacity]),
3916 num_elements_(0),
3917 capacity_(capacity),
3918 position_(shared_positions),
3919 delete_position_(false) {
3920 for (int i = 0; i < shared_positions_size; ++i) {
3921 position_[i] = kNoInserted;
3922 }
3923 }
3924
3925 ~RevIntSet() {
3926 if (delete_position_) {
3927 delete[] position_;
3928 }
3930
3931 int Size() const { return num_elements_.Value(); }
3932
3933 int Capacity() const { return capacity_; }
3934
3935 T Element(int i) const {
3936 DCHECK_GE(i, 0);
3937 DCHECK_LT(i, num_elements_.Value());
3938 return elements_[i];
3939 }
3941 T RemovedElement(int i) const {
3942 DCHECK_GE(i, 0);
3943 DCHECK_LT(i + num_elements_.Value(), capacity_);
3944 return elements_[i + num_elements_.Value()];
3945 }
3947 void Insert(Solver* const solver, const T& elt) {
3948 const int position = num_elements_.Value();
3949 DCHECK_LT(position, capacity_);
3950 DCHECK(NotAlreadyInserted(elt));
3951 elements_[position] = elt;
3952 position_[elt] = position;
3953 num_elements_.Incr(solver);
3954 }
3955
3956 void Remove(Solver* const solver, const T& value_index) {
3957 num_elements_.Decr(solver);
3958 SwapTo(value_index, num_elements_.Value());
3959 }
3960
3961 void Restore(Solver* const solver, const T& value_index) {
3962 SwapTo(value_index, num_elements_.Value());
3963 num_elements_.Incr(solver);
3964 }
3965
3966 void Clear(Solver* const solver) { num_elements_.SetValue(solver, 0); }
3967
3969 typedef const T* const_iterator;
3970 const_iterator begin() const { return elements_.get(); }
3971 const_iterator end() const { return elements_.get() + num_elements_.Value(); }
3972
3973 private:
3975 bool NotAlreadyInserted(const T& elt) {
3976 for (int i = 0; i < num_elements_.Value(); ++i) {
3977 if (elt == elements_[i]) {
3978 return false;
3979 }
3980 }
3981 return true;
3982 }
3983
3984 void SwapTo(T value_index, int next_position) {
3985 const int current_position = position_[value_index];
3986 if (current_position != next_position) {
3987 const T next_value_index = elements_[next_position];
3988 elements_[current_position] = next_value_index;
3989 elements_[next_position] = value_index;
3990 position_[value_index] = next_position;
3991 position_[next_value_index] = current_position;
3992 }
3993 }
3994
3996 std::unique_ptr<T[]> elements_;
3998 NumericalRev<int> num_elements_;
4000 const int capacity_;
4002 int* position_;
4004 const bool delete_position_;
4005};
4006
4008
4009class RevPartialSequence {
4010 public:
4011 explicit RevPartialSequence(const std::vector<int>& items)
4012 : elements_(items),
4013 first_ranked_(0),
4014 last_ranked_(items.size() - 1),
4015 size_(items.size()),
4016 position_(new int[size_]) {
4017 for (int i = 0; i < size_; ++i) {
4018 elements_[i] = items[i];
4019 position_[i] = i;
4020 }
4021 }
4022
4023 explicit RevPartialSequence(int size)
4024 : elements_(size),
4025 first_ranked_(0),
4026 last_ranked_(size - 1),
4027 size_(size),
4028 position_(new int[size_]) {
4029 for (int i = 0; i < size_; ++i) {
4030 elements_[i] = i;
4031 position_[i] = i;
4032 }
4033 }
4034
4036
4037 int NumFirstRanked() const { return first_ranked_.Value(); }
4039 int NumLastRanked() const { return size_ - 1 - last_ranked_.Value(); }
4040
4041 int Size() const { return size_; }
4042
4043#if !defined(SWIG)
4044 const int& operator[](int index) const {
4045 DCHECK_GE(index, 0);
4046 DCHECK_LT(index, size_);
4047 return elements_[index];
4048 }
4049#endif
4051 void RankFirst(Solver* const solver, int elt) {
4052 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
4053 SwapTo(elt, first_ranked_.Value());
4054 first_ranked_.Incr(solver);
4055 }
4057 void RankLast(Solver* const solver, int elt) {
4058 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
4059 SwapTo(elt, last_ranked_.Value());
4060 last_ranked_.Decr(solver);
4061 }
4062
4063 bool IsRanked(int elt) const {
4064 const int position = position_[elt];
4065 return (position < first_ranked_.Value() ||
4066 position > last_ranked_.Value());
4067 }
4068
4069 std::string DebugString() const {
4070 std::string result = "[";
4071 for (int i = 0; i < first_ranked_.Value(); ++i) {
4072 absl::StrAppend(&result, elements_[i]);
4073 if (i != first_ranked_.Value() - 1) {
4074 result.append("-");
4075 }
4076 }
4077 result.append("|");
4078 for (int i = first_ranked_.Value(); i <= last_ranked_.Value(); ++i) {
4079 absl::StrAppend(&result, elements_[i]);
4080 if (i != last_ranked_.Value()) {
4081 result.append("-");
4082 }
4083 }
4084 result.append("|");
4085 for (int i = last_ranked_.Value() + 1; i < size_; ++i) {
4086 absl::StrAppend(&result, elements_[i]);
4087 if (i != size_ - 1) {
4088 result.append("-");
4089 }
4090 }
4091 result.append("]");
4092 return result;
4093 }
4094
4095 private:
4096 void SwapTo(int elt, int next_position) {
4097 const int current_position = position_[elt];
4098 if (current_position != next_position) {
4099 const int next_elt = elements_[next_position];
4100 elements_[current_position] = next_elt;
4101 elements_[next_position] = elt;
4102 position_[elt] = next_position;
4103 position_[next_elt] = current_position;
4104 }
4105 }
4106
4108 std::vector<int> elements_;
4109
4110 NumericalRev<int> first_ranked_;
4112 NumericalRev<int> last_ranked_;
4114 const int size_;
4116 std::unique_ptr<int[]> position_;
4117};
4118
4123class UnsortedNullableRevBitset {
4124 public:
4126 explicit UnsortedNullableRevBitset(int bit_size);
4127
4128 ~UnsortedNullableRevBitset() {}
4129
4132 void Init(Solver* solver, const std::vector<uint64_t>& mask);
4133
4136 bool RevSubtract(Solver* solver, const std::vector<uint64_t>& mask);
4137
4138 /// This method ANDs the mask with the active bitset. It returns true if
4139 /// the active bitset was changed in the process.
4140 bool RevAnd(Solver* solver, const std::vector<uint64_t>& mask);
4141
4144 int ActiveWordSize() const { return active_words_.Size(); }
4145
4147 bool Empty() const { return active_words_.Size() == 0; }
4148
4156 bool Intersects(const std::vector<uint64_t>& mask, int* support_index);
4157
4159 int64_t bit_size() const { return bit_size_; }
4161 int64_t word_size() const { return word_size_; }
4163 const RevIntSet<int>& active_words() const { return active_words_; }
4164
4165 private:
4166 void CleanUpActives(Solver* solver);
4167
4168 const int64_t bit_size_;
4169 const int64_t word_size_;
4170 RevArray<uint64_t> bits_;
4171 RevIntSet<int> active_words_;
4172 std::vector<int> to_remove_;
4173};
4175template <class T>
4176bool IsArrayConstant(const std::vector<T>& values, const T& value) {
4177 for (int i = 0; i < values.size(); ++i) {
4178 if (values[i] != value) {
4179 return false;
4180 }
4181 }
4182 return true;
4183}
4184
4185template <class T>
4186bool IsArrayBoolean(const std::vector<T>& values) {
4187 for (int i = 0; i < values.size(); ++i) {
4188 if (values[i] != 0 && values[i] != 1) {
4189 return false;
4190 }
4192 return true;
4193}
4194
4195template <class T>
4196bool AreAllOnes(const std::vector<T>& values) {
4197 return IsArrayConstant(values, T(1));
4198}
4199
4200template <class T>
4201bool AreAllNull(const std::vector<T>& values) {
4202 return IsArrayConstant(values, T(0));
4203}
4204
4205template <class T>
4206bool AreAllGreaterOrEqual(const std::vector<T>& values, const T& value) {
4207 for (const T& current_value : values) {
4208 if (current_value < value) {
4209 return false;
4210 }
4212 return true;
4213}
4214
4215template <class T>
4216bool AreAllLessOrEqual(const std::vector<T>& values, const T& value) {
4217 for (const T& current_value : values) {
4218 if (current_value > value) {
4219 return false;
4220 }
4222 return true;
4223}
4224
4225template <class T>
4226bool AreAllPositive(const std::vector<T>& values) {
4227 return AreAllGreaterOrEqual(values, T(0));
4228}
4229
4230template <class T>
4231bool AreAllNegative(const std::vector<T>& values) {
4232 return AreAllLessOrEqual(values, T(0));
4233}
4234
4235template <class T>
4236bool AreAllStrictlyPositive(const std::vector<T>& values) {
4237 return AreAllGreaterOrEqual(values, T(1));
4238}
4239
4240template <class T>
4241bool AreAllStrictlyNegative(const std::vector<T>& values) {
4242 return AreAllLessOrEqual(values, T(-1));
4243}
4244
4245template <class T>
4246bool IsIncreasingContiguous(const std::vector<T>& values) {
4247 for (int i = 0; i < values.size() - 1; ++i) {
4248 if (values[i + 1] != values[i] + 1) {
4249 return false;
4250 }
4252 return true;
4253}
4254
4255template <class T>
4256bool IsIncreasing(const std::vector<T>& values) {
4257 for (int i = 0; i < values.size() - 1; ++i) {
4258 if (values[i + 1] < values[i]) {
4259 return false;
4260 }
4262 return true;
4263}
4264
4265template <class T>
4266bool IsArrayInRange(const std::vector<IntVar*>& vars, T range_min,
4267 T range_max) {
4268 for (int i = 0; i < vars.size(); ++i) {
4269 if (vars[i]->Min() < range_min || vars[i]->Max() > range_max) {
4270 return false;
4272 }
4273 return true;
4274}
4275
4276inline bool AreAllBound(const std::vector<IntVar*>& vars) {
4277 for (int i = 0; i < vars.size(); ++i) {
4278 if (!vars[i]->Bound()) {
4279 return false;
4280 }
4282 return true;
4283}
4284
4285inline bool AreAllBooleans(const std::vector<IntVar*>& vars) {
4286 return IsArrayInRange(vars, 0, 1);
4287}
4288
4290
4291template <class T>
4292bool AreAllBoundOrNull(const std::vector<IntVar*>& vars,
4293 const std::vector<T>& values) {
4294 for (int i = 0; i < vars.size(); ++i) {
4295 if (values[i] != 0 && !vars[i]->Bound()) {
4296 return false;
4297 }
4298 }
4299 return true;
4301
4303inline bool AreAllBoundTo(const std::vector<IntVar*>& vars, int64_t value) {
4304 for (int i = 0; i < vars.size(); ++i) {
4305 if (!vars[i]->Bound() || vars[i]->Min() != value) {
4306 return false;
4308 }
4309 return true;
4310}
4311
4312inline int64_t MaxVarArray(const std::vector<IntVar*>& vars) {
4313 DCHECK(!vars.empty());
4314 int64_t result = kint64min;
4315 for (int i = 0; i < vars.size(); ++i) {
4316
4317 result = std::max<int64_t>(result, vars[i]->Max());
4319 return result;
4320}
4321
4322inline int64_t MinVarArray(const std::vector<IntVar*>& vars) {
4323 DCHECK(!vars.empty());
4324 int64_t result = kint64max;
4325 for (int i = 0; i < vars.size(); ++i) {
4326
4327 result = std::min<int64_t>(result, vars[i]->Min());
4328 }
4329 return result;
4330}
4331
4332inline void FillValues(const std::vector<IntVar*>& vars,
4333 std::vector<int64_t>* const values) {
4334 values->clear();
4335 values->resize(vars.size());
4336 for (int i = 0; i < vars.size(); ++i) {
4337 (*values)[i] = vars[i]->Value();
4338 }
4339}
4340
4341inline int64_t PosIntDivUp(int64_t e, int64_t v) {
4342 DCHECK_GT(v, 0);
4343 return (e < 0 || e % v == 0) ? e / v : e / v + 1;
4344}
4345
4346inline int64_t PosIntDivDown(int64_t e, int64_t v) {
4347 DCHECK_GT(v, 0);
4348 return (e >= 0 || e % v == 0) ? e / v : e / v - 1;
4349}
4350
4351std::vector<int64_t> ToInt64Vector(const std::vector<int>& input);
4352
4353} // namespace operations_research
4354
4355#endif // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
int64_t MemoryUsage(int unused)
Definition sysinfo.h:24
#define OR_DLL
Definition base_export.h:27
Iterators on nodes used by Pathoperator to traverse the search space.
void Reset(const PathOperator &path_operator, int base_index_reference)
Argument Holder: useful when visiting a model.
const IntTupleSet & FindIntegerMatrixArgumentOrDie(const std::string &arg_name) const
Definition visitor.cc:117
void SetIntervalArgument(const std::string &arg_name, IntervalVar *var)
Definition visitor.cc:61
void SetIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &vars)
Definition visitor.cc:66
IntExpr * FindIntegerExpressionArgumentOrDie(const std::string &arg_name) const
Definition visitor.cc:106
bool HasIntegerExpressionArgument(const std::string &arg_name) const
Checks if arguments exist.
Definition visitor.cc:81
const std::vector< IntVar * > & FindIntegerVariableArrayArgumentOrDie(const std::string &arg_name) const
Definition visitor.cc:112
void SetSequenceArgument(const std::string &arg_name, SequenceVar *var)
Definition visitor.cc:71
bool HasIntegerVariableArrayArgument(const std::string &arg_name) const
Definition visitor.cc:86
const std::vector< int64_t > & FindIntegerArrayArgumentOrDie(const std::string &arg_name) const
Definition visitor.cc:101
int64_t FindIntegerArgumentOrDie(const std::string &arg_name) const
Definition visitor.cc:96
void SetSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &vars)
Definition visitor.cc:76
int64_t FindIntegerArgumentWithDefault(const std::string &arg_name, int64_t def) const
Getters.
Definition visitor.cc:91
void SetValue(int64_t index, T value)
const E & Element(const V *const var) const
bool Contains(const V *const var) const
AssignmentContainer< IntVar, IntVarElement > IntContainer
IntVar * Var() override
Creates a variable from the expression.
bool HasFragments() const override
BaseLns(const std::vector< IntVar * > &vars)
--— Base Large Neighborhood Search operator --—
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
virtual bool NextFragment()=0
BaseNodeIterators(const PathOperator *path_operator, int base_index_reference)
AlternativeNodeIterator * GetAlternativeIterator() const
NodeNeighborIterator * GetNeighborIterator() const
void Reset(bool update_end_nodes=false)
AlternativeNodeIterator * GetSiblingAlternativeIterator() const
virtual std::string DebugString() const
void CopyBucket(const Bitset64< IndexType > &other, IndexType i)
Copies bucket containing bit i from "other" to "this".
Definition bitset.h:561
bool Contains(int64_t v) const override
IntVarIterator * MakeDomainIterator(bool reversible) const override
IntVar * IsGreaterOrEqual(int64_t constant) override
IntVarIterator * MakeHoleIterator(bool reversible) const override
--— Misc --—
IntVar * IsEqual(int64_t constant) override
IsEqual.
void RemoveValue(int64_t v) override
This method removes the value 'v' from the domain of the variable.
IntVar * IsDifferent(int64_t constant) override
SimpleRevFIFO< Demon * > delayed_bound_demons_
void RemoveInterval(int64_t l, int64_t u) override
uint64_t Size() const override
This method returns the number of values in the domain of the variable.
static const int kUnboundBooleanVarValue
--— Boolean variable --—
void WhenBound(Demon *d) override
int VarType() const override
------— IntVar ------—
IntVar * IsLessOrEqual(int64_t constant) override
std::string BaseName() const override
Returns a base name for automatic naming.
void WhenRange(Demon *d) override
Attach a demon that will watch the min or the max of the expression.
Demon proxy to a method on the constraint with no arguments.
std::string DebugString() const override
CallMethod0(T *const ct, void(T::*method)(), const std::string &name)
Demon proxy to a method on the constraint with one argument.
CallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)
std::string DebugString() const override
Demon proxy to a method on the constraint with two arguments.
std::string DebugString() const override
CallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
Demon proxy to a method on the constraint with three arguments.
CallMethod3(T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
std::string DebugString() const override
virtual int64_t ModifyValue(int64_t index, int64_t value)=0
bool MakeOneNeighbor() override
This method should not be overridden. Override ModifyValue() instead.
ChangeValue(const std::vector< IntVar * > &vars)
--— ChangeValue Operators --—
Low-priority demon proxy to a method on the constraint with no arguments.
DelayedCallMethod0(T *const ct, void(T::*method)(), const std::string &name)
std::string DebugString() const override
Solver::DemonPriority priority() const override
---------------— Demon class -------------—
Low-priority demon proxy to a method on the constraint with one argument.
DelayedCallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)
Solver::DemonPriority priority() const override
---------------— Demon class -------------—
std::string DebugString() const override
Low-priority demon proxy to a method on the constraint with two arguments.
std::string DebugString() const override
Solver::DemonPriority priority() const override
---------------— Demon class -------------—
DelayedCallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
virtual void SetValue(int64_t v)
This method sets the value of the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual int64_t Min() const =0
--— Main IntTupleSet class --—
Definition tuple_set.h:47
void AddToAssignment(IntVar *var, int64_t value, bool active, std::vector< int > *assignment_indices, int64_t index, Assignment *assignment) const
void SetValue(int64_t index, int64_t value)
void Start(const Assignment *assignment) override
void RevertChanges(bool change_was_incremental)
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
--— Base operator class for operators manipulating IntVars --—
void AddVars(const std::vector< IntVar * > &vars)
IntVar * Var(int64_t index) const
Returns the variable of given index.
bool ApplyChanges(Assignment *delta, Assignment *deltadelta) const
IntVarLocalSearchOperator(const std::vector< IntVar * > &vars, bool keep_inverse_values=false)
virtual void WhenBound(Demon *d)=0
int index() const
Returns the index of the variable.
IntVar(Solver *s)
-------— IntVar -------—
--— LightIntFunctionElementCt --—
LightIntFunctionElementCt(Solver *const solver, IntVar *const var, IntVar *const index, F values, std::function< bool()> deep_serialize)
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
std::string DebugString() const override
--------------— Constraint class ----------------—
--— LightIntIntFunctionElementCt --—
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
LightIntIntFunctionElementCt(Solver *const solver, IntVar *const var, IntVar *const index1, IntVar *const index2, F values, std::function< bool()> deep_serialize)
std::string DebugString() const override
--------------— Constraint class ----------------—
--— LightIntIntIntFunctionElementCt --—
LightIntIntIntFunctionElementCt(Solver *const solver, IntVar *const var, IntVar *const index1, IntVar *const index2, IntVar *const index3, F values)
std::string DebugString() const override
--------------— Constraint class ----------------—
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
LocalSearchFilterManager(std::vector< FilterEvent > filter_events)
void Revert()
Calls Revert() of filters, in reverse order of Relax events.
void Synchronize(const Assignment *assignment, const Assignment *delta)
Synchronizes all filters to assignment.
bool Accept(LocalSearchMonitor *monitor, const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max)
virtual void Reset()
Sets the filter to empty solution.
virtual void Revert()
Cancels the changes made by the last Relax()/Accept() calls.
virtual bool Accept(const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max)=0
virtual int64_t GetSynchronizedObjectiveValue() const
Objective value from last time Synchronize() was called.
virtual void Synchronize(const Assignment *assignment, const Assignment *delta)=0
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
void Install() override
Install itself on the solver.
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
void SetCandidateActive(int64_t index, bool active)
void SetCandidateValue(int64_t index, int64_t value)
const std::vector< int64_t > & IncrementalIndicesChanged() const
const std::vector< int64_t > & CandidateIndicesChanged() const
virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0
virtual const LocalSearchOperator * Self() const
virtual void Start(const Assignment *assignment)=0
friend class LocalSearchState
Only LocalSearchState can construct LocalSearchVariables.
void PropagateRelax(VariableDomainId domain_id)
Propagation of all events.
static Variable DummyVariable()
Makes a variable with no state, this is meant as a placeholder.
Variable MakeVariable(VariableDomainId domain_id)
Variable MakeVariableWithRelaxedDomain(int64_t min, int64_t max)
bool PropagateTighten(VariableDomainId domain_id)
virtual void InsertVarArrayConstantArrayExpression(IntExpr *expression, const std::vector< IntVar * > &var, const std::vector< int64_t > &values, VarArrayConstantArrayExpressionType type)=0
virtual void InsertVarConstantConstraint(Constraint *ct, IntVar *var, int64_t value, VarConstantConstraintType type)=0
virtual IntExpr * FindExprExprExpression(IntExpr *var1, IntExpr *var2, ExprExprExpressionType type) const =0
Expr Expr Expressions.
virtual Constraint * FindExprExprConstraint(IntExpr *expr1, IntExpr *expr2, ExprExprConstraintType type) const =0
Expr Expr Constraints.
virtual Constraint * FindVoidConstraint(VoidConstraintType type) const =0
Void constraints.
virtual IntExpr * FindVarArrayConstantArrayExpression(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values, VarArrayConstantArrayExpressionType type) const =0
Var Array Constant Array Expressions.
virtual IntExpr * FindVarArrayExpression(const std::vector< IntVar * > &vars, VarArrayExpressionType type) const =0
Var Array Expressions.
virtual IntExpr * FindExprExpression(IntExpr *expr, ExprExpressionType type) const =0
Expr Expressions.
virtual void InsertExprExprConstraint(Constraint *ct, IntExpr *expr1, IntExpr *expr2, ExprExprConstraintType type)=0
virtual void InsertExprExpression(IntExpr *expression, IntExpr *expr, ExprExpressionType type)=0
virtual void InsertVoidConstraint(Constraint *ct, VoidConstraintType type)=0
virtual void InsertExprExprExpression(IntExpr *expression, IntExpr *var1, IntExpr *var2, ExprExprExpressionType type)=0
virtual void InsertVarConstantArrayExpression(IntExpr *expression, IntVar *var, const std::vector< int64_t > &values, VarConstantArrayExpressionType type)=0
virtual IntExpr * FindVarArrayConstantExpression(const std::vector< IntVar * > &vars, int64_t value, VarArrayConstantExpressionType type) const =0
Var Array Constant Expressions.
virtual void InsertExprConstantExpression(IntExpr *expression, IntExpr *var, int64_t value, ExprConstantExpressionType type)=0
virtual void InsertVarConstantConstantConstraint(Constraint *ct, IntVar *var, int64_t value1, int64_t value2, VarConstantConstantConstraintType type)=0
virtual void InsertVarArrayConstantExpression(IntExpr *expression, const std::vector< IntVar * > &var, int64_t value, VarArrayConstantExpressionType type)=0
virtual void InsertVarConstantConstantExpression(IntExpr *expression, IntVar *var, int64_t value1, int64_t value2, VarConstantConstantExpressionType type)=0
virtual Constraint * FindVarConstantConstraint(IntVar *var, int64_t value, VarConstantConstraintType type) const =0
Var Constant Constraints.
virtual IntExpr * FindVarConstantArrayExpression(IntVar *var, const std::vector< int64_t > &values, VarConstantArrayExpressionType type) const =0
Var Constant Array Expressions.
ModelCache(Solver *solver)
--— ModelCache --—
virtual IntExpr * FindExprConstantExpression(IntExpr *expr, int64_t value, ExprConstantExpressionType type) const =0
Expr Constant Expressions.
virtual void InsertExprExprConstantExpression(IntExpr *expression, IntExpr *var1, IntExpr *var2, int64_t constant, ExprExprConstantExpressionType type)=0
virtual IntExpr * FindExprExprConstantExpression(IntExpr *var1, IntExpr *var2, int64_t constant, ExprExprConstantExpressionType type) const =0
Expr Expr Constant Expressions.
virtual IntExpr * FindVarConstantConstantExpression(IntVar *var, int64_t value1, int64_t value2, VarConstantConstantExpressionType type) const =0
Var Constant Constant Expressions.
virtual Constraint * FindVarConstantConstantConstraint(IntVar *var, int64_t value1, int64_t value2, VarConstantConstantConstraintType type) const =0
Var Constant Constant Constraints.
virtual void InsertVarArrayExpression(IntExpr *expression, const std::vector< IntVar * > &vars, VarArrayExpressionType type)=0
void VisitIntervalArgument(const std::string &arg_name, IntervalVar *argument) override
Visit interval argument.
Definition visitor.cc:216
void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments) override
Definition visitor.cc:222
void VisitIntervalVariable(const IntervalVar *variable, const std::string &operation, int64_t value, IntervalVar *delegate) override
Definition visitor.cc:170
void VisitIntegerArgument(const std::string &arg_name, int64_t value) override
Integer arguments.
Definition visitor.cc:185
void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64_t > &values) override
Definition visitor.cc:190
void VisitSequenceVariable(const SequenceVar *variable) override
Definition visitor.cc:180
void VisitSequenceArgument(const std::string &arg_name, SequenceVar *argument) override
Visit sequence argument.
Definition visitor.cc:231
void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments) override
Definition visitor.cc:237
void VisitIntegerVariable(const IntVar *variable, IntExpr *delegate) override
Definition visitor.cc:158
void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments) override
Definition visitor.cc:207
ArgumentHolder * Top() const
Definition visitor.cc:255
void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &values) override
Definition visitor.cc:195
void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *expr) override
Definition visitor.cc:152
void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *argument) override
Variables.
Definition visitor.cc:201
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *argument)
Visit integer expression argument.
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *constraint)
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64_t index_min, int64_t index_max)
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *constraint)
void Reset(const PathOperator &path_operator, int base_index_reference)
Subclass of Rev<T> which adds numerical operations.
int number_of_nexts() const
Number of next variables.
bool SkipUnchanged(int index) const override
bool MakeChainInactive(int64_t before_chain, int64_t chain_end)
int64_t Prev(int64_t node) const
Returns the node before node in the current delta.
bool SwapActiveAndInactive(int64_t active, int64_t inactive)
Replaces active by inactive in the current path, making active inactive.
int PathClassFromStartNode(int64_t start_node) const
int64_t Path(int64_t node) const
void AddPairAlternativeSets(const std::vector< PairType > &pair_alternative_sets)
bool MakeActive(int64_t node, int64_t destination)
Insert the inactive node after destination.
int64_t OldNext(int64_t node) const
virtual bool ConsiderAlternatives(int64_t) const
bool SwapNodes(int64_t node1, int64_t node2)
Swaps the nodes node1 and node2.
int64_t BaseSiblingAlternativeNode(int i) const
Returns the alternative node for the sibling of the ith base node.
void SetNext(int64_t from, int64_t to, int64_t path)
Sets 'to' to be the node after 'from' on the given path.
virtual bool OnSamePathAsPreviousBase(int64_t)
virtual int64_t GetBaseNodeRestartPosition(int base_index)
int CurrentNodePathStart(int64_t node) const
int GetSiblingAlternativeIndex(int node) const
Returns the index of the alternative set of the sibling of node.
int64_t OldPath(int64_t node) const
int GetAlternativeIndex(int node) const
Returns the index of the alternative set of the node.
int64_t PrevNext(int64_t node) const
int64_t OldPrev(int64_t node) const
int AddAlternativeSet(const std::vector< int64_t > &alternative_set)
int64_t GetActiveAlternativeSibling(int node) const
bool IsPathStart(int64_t node) const
Returns true if node is the first node on the path.
bool MoveChain(int64_t before_chain, int64_t chain_end, int64_t destination)
bool SwapActiveAndInactiveChains(absl::Span< const int64_t > active_chain, absl::Span< const int64_t > inactive_chain)
int64_t EndNode(int i) const
Returns the end node of the ith base node.
int64_t GetActiveInAlternativeSet(int alternative_index) const
Returns the active node in the given alternative set.
PathOperator(const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, IterationParameters iteration_parameters)
Builds an instance of PathOperator from next and path variables.
bool IsInactive(int64_t node) const
Returns true if node is inactive.
const std::vector< int64_t > & path_starts() const
Returns the vector of path start nodes.
bool CheckChainValidity(int64_t before_chain, int64_t chain_end, int64_t exclude) const
bool ReverseChain(int64_t before_chain, int64_t after_chain, int64_t *chain_last)
int PathClass(int i) const
Returns the class of the path of the ith base node.
virtual void SetNextBaseToIncrement(int64_t base_index)
int64_t BaseAlternativeNode(int i) const
Returns the alternative node for the ith base node.
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
int64_t StartNode(int i) const
Returns the start node of the ith base node.
int64_t BaseNode(int i) const
Returns the ith base node of the operator.
int CurrentNodePathEnd(int64_t node) const
virtual void SetValues(IntVar *var, const std::vector< int64_t > &values)=0
virtual void SetDurationMax(IntervalVar *var, int64_t new_max)=0
virtual void SetStartMax(IntervalVar *var, int64_t new_max)=0
virtual void SetStartMin(IntervalVar *var, int64_t new_min)=0
IntervalVar modifiers.
virtual void RankSequence(SequenceVar *var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)=0
virtual void RankNotFirst(SequenceVar *var, int index)=0
virtual void RankNotLast(SequenceVar *var, int index)=0
virtual void PushContext(const std::string &context)=0
virtual void SetPerformed(IntervalVar *var, bool value)=0
virtual void SetEndMax(IntervalVar *var, int64_t new_max)=0
virtual void RemoveValue(IntVar *var, int64_t value)=0
virtual void EndDemonRun(Demon *demon)=0
virtual void SetDurationMin(IntervalVar *var, int64_t new_min)=0
virtual void SetMin(IntExpr *expr, int64_t new_min)=0
IntExpr modifiers.
virtual void SetEndMin(IntervalVar *var, int64_t new_min)=0
virtual void RankFirst(SequenceVar *var, int index)=0
SequenceVar modifiers.
virtual void SetMax(IntExpr *expr, int64_t new_max)=0
virtual void RankLast(SequenceVar *var, int index)=0
virtual void SetDurationRange(IntervalVar *var, int64_t new_min, int64_t new_max)=0
virtual void StartProcessingIntegerVariable(IntVar *var)=0
virtual void EndProcessingIntegerVariable(IntVar *var)=0
void Install() override
Install itself on the solver.
virtual void RemoveInterval(IntVar *var, int64_t imin, int64_t imax)=0
virtual void SetRange(IntExpr *expr, int64_t new_min, int64_t new_max)=0
virtual void RemoveValues(IntVar *var, const std::vector< int64_t > &values)=0
virtual void SetStartRange(IntervalVar *var, int64_t new_min, int64_t new_max)=0
virtual void SetValue(IntVar *var, int64_t value)=0
virtual void SetEndRange(IntervalVar *var, int64_t new_min, int64_t new_max)=0
Matrix version of the RevBitSet class.
bool IsSet(int64_t row, int64_t column) const
Returns whether the 'column' bit in the 'row' row is set.
void ClearAll(Solver *solver)
Cleans all bits.
Definition utilities.cc:221
int64_t GetFirstBit(int row, int start) const
Definition utilities.cc:205
void SetToZero(Solver *solver, int64_t row, int64_t column)
Erases the 'column' bit in the 'row' row.
Definition utilities.cc:179
void SetToOne(Solver *solver, int64_t row, int64_t column)
Sets the 'column' bit in the 'row' row.
Definition utilities.cc:171
int64_t Cardinality() const
Returns the number of bits set to one.
Definition utilities.cc:113
void ClearAll(Solver *solver)
Cleans all bits.
Definition utilities.cc:152
RevBitSet(int64_t size)
-------— RevBitSet -------—
Definition utilities.cc:62
void SetToZero(Solver *solver, int64_t index)
Erases the 'index' bit.
Definition utilities.cc:96
bool IsCardinalityOne() const
Does it contains only one bit set?
Definition utilities.cc:130
void SetToOne(Solver *solver, int64_t index)
Sets the 'index' bit.
Definition utilities.cc:85
bool IsSet(int64_t index) const
Returns whether the 'index' bit is set.
Definition utilities.cc:107
int64_t GetFirstBit(int start) const
Definition utilities.cc:148
bool IsCardinalityZero() const
Is bitset null?
Definition utilities.cc:121
void RevInsert(Solver *const solver, int64_t index, T value)
void Insert(const K &key, const V &value)
Inserts (key, value) in the multi-map.
bool ContainsKey(const K &key) const
Returns true if the multi-map contains at least one instance of 'key'.
RevImmutableMultiMap(Solver *const solver, int initial_size)
const V & FindWithDefault(const K &key, const V &default_value) const
RevIntSet(int capacity)
Capacity is the fixed size of the set (it cannot grow).
void Remove(Solver *const solver, const T &value_index)
const T * const_iterator
Iterators on the indices.
void Insert(Solver *const solver, const T &elt)
void RankLast(Solver *const solver, int elt)
void RankFirst(Solver *const solver, int elt)
A reversible switch that can switch once from false to true.
void Switch(Solver *const solver)
virtual void OutputLine(const std::string &line)
Definition search.cc:304
void EndInitialPropagation() override
After the initial propagation.
Definition search.cc:295
void BeginInitialPropagation() override
Before the initial propagation.
Definition search.cc:293
std::string DebugString() const override
Definition search.cc:84
A search monitor is a simple set of callbacks to monitor all search events.
void SetLastValue(const T &v)
Sets the last value in the FIFO.
const T * Last() const
Returns the last item of the FIFO.
void Push(Solver *const s, T val)
void PushIfNotTop(Solver *const s, T val)
Pushes the var on top if is not a duplicate of the current top object.
const T & LastValue() const
Returns the last value in the FIFO.
void SetToZero(Solver *solver, int64_t pos)
Erases the 'pos' bit.
Definition utilities.cc:44
SmallRevBitSet(int64_t size)
-------— SmallRevBitSet -------—
Definition utilities.cc:34
void SetToOne(Solver *solver, int64_t pos)
Sets the 'pos' bit.
Definition utilities.cc:39
bool IsCardinalityZero() const
Is bitset null?
int64_t Cardinality() const
Returns the number of bits set to one.
Definition utilities.cc:49
bool IsCardinalityOne() const
Does it contains only one bit set?
For the time being, Solver is neither MT_SAFE nor MT_HOT.
std::function< int64_t(int64_t, int64_t, int64_t)> IndexEvaluator3
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition bitset.h:903
void Set(IntegerType index)
Definition bitset.h:885
const std::vector< ArcId > & ComputeSortedSubDagArcs(NodeId node)
-------— Symmetry Breaking -------—
Definition search.cc:5347
int64_t bit_size() const
Returns the number of bits given in the constructor of the bitset.
const RevIntSet< int > & active_words() const
Returns the set of active word indices.
bool RevAnd(Solver *solver, const std::vector< uint64_t > &mask)
Definition utilities.cc:271
absl::Status Exists(absl::string_view path, Options options)
Definition file.cc:380
For infeasible and unbounded see Not checked if options check_solutions_if_inf_or_unbounded and the If options first_solution_only is false
problem is infeasible or unbounded (default).
Definition matchers.h:468
dual_gradient T(y - `dual_solution`) class DiagonalTrustRegionProblemFromQp
std::function< int64_t(const Model &)> Value(IntegerVariable v)
This checks that the variable is fixed.
Definition integer.h:1559
In SWIG mode, we don't want anything besides these top-level includes.
LocalSearchOperator * MakeExtendedSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExtendedSwapActive --—
std::string ParameterDebugString(P param)
bool IsArrayConstant(const std::vector< T > &values, const T &value)
bool AreAllLessOrEqual(const std::vector< T > &values, const T &value)
LocalSearchOperator * RelocateAndMakeInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— RelocateAndMakeInactive --—
LocalSearchOperator * MakeTSPOpt(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)
--— TSP-based operators --—
LocalSearchOperator * MakeCross(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— Cross --—
SubDagComputer::ArcId ArcId
Demon * MakeConstraintDemon3(Solver *const s, T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
LocalSearchOperator * MakeSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— SwapActive --—
LocalSearchOperator * ExchangeAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExchangeAndMakeActive --—
bool AreAllNegative(const std::vector< T > &values)
bool AreAllGreaterOrEqual(const std::vector< T > &values, const T &value)
bool IsIncreasing(const std::vector< T > &values)
bool IsArrayBoolean(const std::vector< T > &values)
LocalSearchOperator * MakeExchange(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— Exchange --—
void AcceptUncheckedNeighbor(Search *search)
LocalSearchOperator * MakeActiveAndRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeActiveAndRelocate --—
bool AreAllBoundOrNull(const std::vector< IntVar * > &vars, const std::vector< T > &values)
int64_t MaxVarArray(const std::vector< IntVar * > &vars)
LocalSearchOperator * MakeTSPLns(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)
Demon * MakeConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
Demon * MakeDelayedConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
LocalSearchOperator * MakeRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr, int64_t chain_length=1LL, bool single_path=false, const std::string &name="Relocate")
--— Relocate --—
LocalSearchOperator * RelocateAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
-— RelocateAndMakeActive --—
void FillValues(const std::vector< IntVar * > &vars, std::vector< int64_t > *const values)
bool AreAllBooleans(const std::vector< IntVar * > &vars)
bool AreAllStrictlyNegative(const std::vector< T > &values)
LocalSearchOperator * MakePathLns(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments)
--— Path-based Large Neighborhood Search --—
int64_t MinVarArray(const std::vector< IntVar * > &vars)
LocalSearchOperator * MakeInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeInactive --—
void RegisterDemon(Solver *const solver, Demon *const demon, DemonProfiler *const monitor)
--— Exported Methods for Unit Tests --—
LocalSearchOperator * MakeTwoOpt(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— 2Opt --—
LocalSearchOperator * MakeChainInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeChainInactive --—
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
static const int kUnassigned
--— Routing model --—
Definition routing.cc:507
bool IsIncreasingContiguous(const std::vector< T > &values)
bool AreAllNull(const std::vector< T > &values)
bool AreAllPositive(const std::vector< T > &values)
LocalSearchOperator * ExchangePathStartEndsAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExchangePathEndsAndMakeActive --—
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
LocalSearchOperator * MakeSwapActiveChain(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int max_chain_size)
--— SwapActiveChain --—
LocalSearchOperator * MakeLinKernighan(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)
--— Lin-Kernighan --—
LocalSearchState::VariableDomainId VariableDomainId
int64_t PosIntDivDown(int64_t e, int64_t v)
bool IsArrayInRange(const std::vector< IntVar * > &vars, T range_min, T range_max)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
bool AreAllOnes(const std::vector< T > &values)
bool AreAllBound(const std::vector< IntVar * > &vars)
uint64_t Hash1(uint64_t value)
LocalSearchOperator * MakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— MakeActive --—
int64_t PosIntDivUp(int64_t e, int64_t v)
SubDagComputer::NodeId NodeId
STL namespace.
false true
Definition numbers.cc:228
bool Next()
trees with all degrees equal to
static int input(yyscan_t yyscanner)
#define DEFINE_STRONG_INT_TYPE(int_type_name, value_type)
Definition strong_int.h:168
Set of parameters used to configure how the neighnorhood is traversed.
bool accept_path_end_base
True if path ends should be considered when iterating over neighbors.
std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors
int number_of_base_nodes
Number of nodes needed to define a neighbor.
std::function< const std::vector< int > &(int, int)> get_incoming_neighbors
static const int64_t kint64max
Definition types.h:32
static const int64_t kint64min
Definition types.h:31