Google OR-Tools v9.14
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"
75#include "ortools/base/timer.h"
76#include "ortools/base/types.h"
78#include "ortools/util/bitset.h"
80
81namespace operations_research {
82
109
110class BaseIntExpr : public IntExpr {
111 public:
112 explicit BaseIntExpr(Solver* const s) : IntExpr(s), var_(nullptr) {}
113 ~BaseIntExpr() override {}
114
115 IntVar* Var() override;
116 virtual IntVar* CastToVar();
118 private:
119 IntVar* var_;
121
124enum VarTypes {
128 CONST_VAR,
142
144#ifndef SWIG
145template <class T>
146class SimpleRevFIFO {
147 private:
148 enum { CHUNK_SIZE = 16 }; // TODO(user): could be an extra template param
149 struct Chunk {
150 T data[CHUNK_SIZE];
151 const Chunk* const next;
152 explicit Chunk(const Chunk* next) : next(next) {}
153 };
154
155 public:
157 class Iterator {
158 public:
159 explicit Iterator(const SimpleRevFIFO<T>* l)
160 : chunk_(l->chunks_), value_(l->Last()) {}
161 bool ok() const { return (value_ != nullptr); }
162 T operator*() const { return *value_; }
163 void operator++() {
164 ++value_;
165 if (value_ == chunk_->data + CHUNK_SIZE) {
166 chunk_ = chunk_->next;
167 value_ = chunk_ ? chunk_->data : nullptr;
171 private:
172 const Chunk* chunk_;
173 const T* value_;
174 };
175
176 SimpleRevFIFO() : chunks_(nullptr), pos_(0) {}
177
178 void Push(Solver* const s, T val) {
179 if (pos_.Value() == 0) {
180 Chunk* const chunk = s->UnsafeRevAlloc(new Chunk(chunks_));
181 s->SaveAndSetValue(reinterpret_cast<void**>(&chunks_),
182 reinterpret_cast<void*>(chunk));
183 pos_.SetValue(s, CHUNK_SIZE - 1);
184 } else {
185 pos_.Decr(s);
186 }
187 chunks_->data[pos_.Value()] = val;
188 }
189
191 void PushIfNotTop(Solver* const s, T val) {
192 if (chunks_ == nullptr || LastValue() != val) {
193 Push(s, val);
194 }
195 }
196
198 const T* Last() const {
199 return chunks_ ? &chunks_->data[pos_.Value()] : nullptr;
200 }
201
202 T* MutableLast() { return chunks_ ? &chunks_->data[pos_.Value()] : nullptr; }
203
205 const T& LastValue() const {
206 DCHECK(chunks_);
207 return chunks_->data[pos_.Value()];
208 }
211 void SetLastValue(const T& v) {
212 DCHECK(Last());
213 chunks_->data[pos_.Value()] = v;
214 }
215
216 private:
217 Chunk* chunks_;
219};
220
222// TODO(user): use murmurhash.
223inline uint64_t Hash1(uint64_t value) {
224 value = (~value) + (value << 21);
225 value ^= value >> 24;
226 value += (value << 3) + (value << 8);
227 value ^= value >> 14;
228 value += (value << 2) + (value << 4);
229 value ^= value >> 28;
230 value += (value << 31);
231 return value;
232}
233
234inline uint64_t Hash1(uint32_t value) {
235 uint64_t a = value;
236 a = (a + 0x7ed55d16) + (a << 12);
237 a = (a ^ 0xc761c23c) ^ (a >> 19);
238 a = (a + 0x165667b1) + (a << 5);
239 a = (a + 0xd3a2646c) ^ (a << 9);
240 a = (a + 0xfd7046c5) + (a << 3);
241 a = (a ^ 0xb55a4f09) ^ (a >> 16);
242 return a;
243}
244
245inline uint64_t Hash1(int64_t value) {
246 return Hash1(static_cast<uint64_t>(value));
247}
248
249inline uint64_t Hash1(int value) { return Hash1(static_cast<uint32_t>(value)); }
250
251inline uint64_t Hash1(void* const ptr) {
252#if defined(__x86_64__) || defined(_M_X64) || defined(__powerpc64__) || \
253 defined(__aarch64__) || (defined(_MIPS_SZPTR) && (_MIPS_SZPTR == 64))
254 return Hash1(reinterpret_cast<uint64_t>(ptr));
255#else
256 return Hash1(reinterpret_cast<uint32_t>(ptr));
257#endif
259
260template <class T>
261uint64_t Hash1(const std::vector<T*>& ptrs) {
262 if (ptrs.empty()) return 0;
263 if (ptrs.size() == 1) return Hash1(ptrs[0]);
264 uint64_t hash = Hash1(ptrs[0]);
265 for (int i = 1; i < ptrs.size(); ++i) {
266 hash = hash * i + Hash1(ptrs[i]);
267 }
268 return hash;
269}
270
271inline uint64_t Hash1(const std::vector<int64_t>& ptrs) {
272 if (ptrs.empty()) return 0;
273 if (ptrs.size() == 1) return Hash1(ptrs[0]);
274 uint64_t hash = Hash1(ptrs[0]);
275 for (int i = 1; i < ptrs.size(); ++i) {
276 hash = hash * i + Hash1(ptrs[i]);
277 }
278 return hash;
279}
280
283template <class K, class V>
284class RevImmutableMultiMap {
285 public:
286 RevImmutableMultiMap(Solver* const solver, int initial_size)
287 : solver_(solver),
288 array_(solver->UnsafeRevAllocArray(new Cell*[initial_size])),
289 size_(initial_size),
290 num_items_(0) {
291 memset(array_, 0, sizeof(*array_) * size_.Value());
292 }
295
296 int num_items() const { return num_items_.Value(); }
297
299 bool ContainsKey(const K& key) const {
300 uint64_t code = Hash1(key) % size_.Value();
301 Cell* tmp = array_[code];
302 while (tmp) {
303 if (tmp->key() == key) {
304 return true;
305 }
306 tmp = tmp->next();
307 }
308 return false;
309 }
310
314 const V& FindWithDefault(const K& key, const V& default_value) const {
315 uint64_t code = Hash1(key) % size_.Value();
316 Cell* tmp = array_[code];
317 while (tmp) {
318 if (tmp->key() == key) {
319 return tmp->value();
320 }
321 tmp = tmp->next();
322 }
323 return default_value;
324 }
325
327 void Insert(const K& key, const V& value) {
328 const int position = Hash1(key) % size_.Value();
329 Cell* const cell =
330 solver_->UnsafeRevAlloc(new Cell(key, value, array_[position]));
331 solver_->SaveAndSetValue(reinterpret_cast<void**>(&array_[position]),
332 reinterpret_cast<void*>(cell));
333 num_items_.Incr(solver_);
334 if (num_items_.Value() > 2 * size_.Value()) {
335 Double();
336 }
337 }
338
339 private:
340 class Cell {
341 public:
342 Cell(const K& key, const V& value, Cell* const next)
343 : key_(key), value_(value), next_(next) {}
344
345 void SetRevNext(Solver* const solver, Cell* const next) {
346 solver->SaveAndSetValue(reinterpret_cast<void**>(&next_),
347 reinterpret_cast<void*>(next));
348 }
349
350 Cell* next() const { return next_; }
351
352 const K& key() const { return key_; }
353
354 const V& value() const { return value_; }
355
356 private:
357 const K key_;
358 const V value_;
359 Cell* next_;
360 };
361
362 void Double() {
363 Cell** const old_cell_array = array_;
364 const int old_size = size_.Value();
365 size_.SetValue(solver_, size_.Value() * 2);
366 solver_->SaveAndSetValue(
367 reinterpret_cast<void**>(&array_),
368 reinterpret_cast<void*>(
369 solver_->UnsafeRevAllocArray(new Cell*[size_.Value()])));
370 memset(array_, 0, size_.Value() * sizeof(*array_));
371 for (int i = 0; i < old_size; ++i) {
372 Cell* tmp = old_cell_array[i];
373 while (tmp != nullptr) {
374 Cell* const to_reinsert = tmp;
375 tmp = tmp->next();
376 const uint64_t new_position = Hash1(to_reinsert->key()) % size_.Value();
377 to_reinsert->SetRevNext(solver_, array_[new_position]);
378 solver_->SaveAndSetValue(
379 reinterpret_cast<void**>(&array_[new_position]),
380 reinterpret_cast<void*>(to_reinsert));
381 }
382 }
383 }
384
385 Solver* const solver_;
386 Cell** array_;
387 NumericalRev<int> size_;
388 NumericalRev<int> num_items_;
389};
390
392class RevSwitch {
393 public:
394 RevSwitch() : value_(false) {}
395
396 bool Switched() const { return value_; }
397
398 void Switch(Solver* const solver) { solver->SaveAndSetValue(&value_, true); }
400 private:
401 bool value_;
402};
406class SmallRevBitSet {
407 public:
408 explicit SmallRevBitSet(int64_t size);
410 void SetToOne(Solver* solver, int64_t pos);
412 void SetToZero(Solver* solver, int64_t pos);
413 /// Returns the number of bits set to one.
414 int64_t Cardinality() const;
416 bool IsCardinalityZero() const { return bits_.Value() == uint64_t{0}; }
418 bool IsCardinalityOne() const {
419 return (bits_.Value() != 0) && !(bits_.Value() & (bits_.Value() - 1));
420 }
423 int64_t GetFirstOne() const;
424
425 private:
426 Rev<uint64_t> bits_;
427};
428
431class RevBitSet {
432 public:
433 explicit RevBitSet(int64_t size);
434 ~RevBitSet();
435
437 void SetToOne(Solver* solver, int64_t index);
438 /// Erases the 'index' bit.
439 void SetToZero(Solver* solver, int64_t index);
441 bool IsSet(int64_t index) const;
443 int64_t Cardinality() const;
445 bool IsCardinalityZero() const;
447 bool IsCardinalityOne() const;
450 int64_t GetFirstBit(int start) const;
452 void ClearAll(Solver* solver);
453
454 friend class RevBitMatrix;
455
456 private:
458 void Save(Solver* solver, int offset);
459 const int64_t size_;
460 const int64_t length_;
461 uint64_t* bits_;
462 uint64_t* stamps_;
463};
464
466class RevBitMatrix : private RevBitSet {
467 public:
468 RevBitMatrix(int64_t rows, int64_t columns);
470
471
472 void SetToOne(Solver* solver, int64_t row, int64_t column);
473 /// Erases the 'column' bit in the 'row' row.
474 void SetToZero(Solver* solver, int64_t row, int64_t column);
476 bool IsSet(int64_t row, int64_t column) const {
477 DCHECK_GE(row, 0);
478 DCHECK_LT(row, rows_);
479 DCHECK_GE(column, 0);
480 DCHECK_LT(column, columns_);
481 return RevBitSet::IsSet(row * columns_ + column);
482 }
483 /// Returns the number of bits set to one in the 'row' row.
484 int64_t Cardinality(int row) const;
486 bool IsCardinalityZero(int row) const;
488 bool IsCardinalityOne(int row) const;
490
491 int64_t GetFirstBit(int row, int start) const;
493 void ClearAll(Solver* solver);
494
495 private:
496 const int64_t rows_;
497 const int64_t columns_;
498};
499
505
506
507template <class T>
508class CallMethod0 : public Demon {
509 public:
510 CallMethod0(T* const ct, void (T::*method)(), const std::string& name)
511 : constraint_(ct), method_(method), name_(name) {}
512
513 ~CallMethod0() override {}
514
515 void Run(Solver* const) override { (constraint_->*method_)(); }
516
517 std::string DebugString() const override {
518 return "CallMethod_" + name_ + "(" + constraint_->DebugString() + ")";
519 }
521 private:
522 T* const constraint_;
523 void (T::* const method_)();
524 const std::string name_;
525};
526
527template <class T>
528Demon* MakeConstraintDemon0(Solver* const s, T* const ct, void (T::*method)(),
529 const std::string& name) {
530 return s->RevAlloc(new CallMethod0<T>(ct, method, name));
531}
532
533template <class P>
534std::string ParameterDebugString(P param) {
535 return absl::StrCat(param);
536}
537
539template <class P>
540std::string ParameterDebugString(P* param) {
541 return param->DebugString();
542}
543
544
545template <class T, class P>
546class CallMethod1 : public Demon {
547 public:
548 CallMethod1(T* const ct, void (T::*method)(P), const std::string& name,
549 P param1)
550 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
551
552 ~CallMethod1() override {}
554 void Run(Solver* const) override { (constraint_->*method_)(param1_); }
556 std::string DebugString() const override {
557 return absl::StrCat("CallMethod_", name_, "(", constraint_->DebugString(),
558 ", ", ParameterDebugString(param1_), ")");
560
561 private:
562 T* const constraint_;
563 void (T::* const method_)(P);
564 const std::string name_;
565 P param1_;
566};
567
568template <class T, class P>
569Demon* MakeConstraintDemon1(Solver* const s, T* const ct, void (T::*method)(P),
570 const std::string& name, P param1) {
571 return s->RevAlloc(new CallMethod1<T, P>(ct, method, name, param1));
572}
573
574
575template <class T, class P, class Q>
576class CallMethod2 : public Demon {
577 public:
578 CallMethod2(T* const ct, void (T::*method)(P, Q), const std::string& name,
579 P param1, Q param2)
580 : constraint_(ct),
581 method_(method),
582 name_(name),
583 param1_(param1),
584 param2_(param2) {}
586 ~CallMethod2() override {}
587
588 void Run(Solver* const) override {
589 (constraint_->*method_)(param1_, param2_);
590 }
591
592 std::string DebugString() const override {
593 return absl::StrCat("CallMethod_", name_, "(", constraint_->DebugString(),
594 ", ", ParameterDebugString(param1_), ", ",
595 ParameterDebugString(param2_), ")");
596 }
597
598 private:
599 T* const constraint_;
600 void (T::* const method_)(P, Q);
601 const std::string name_;
602 P param1_;
603 Q param2_;
604};
605
606template <class T, class P, class Q>
607Demon* MakeConstraintDemon2(Solver* const s, T* const ct,
608 void (T::*method)(P, Q), const std::string& name,
609 P param1, Q param2) {
610 return s->RevAlloc(
611 new CallMethod2<T, P, Q>(ct, method, name, param1, param2));
612}
614template <class T, class P, class Q, class R>
615class CallMethod3 : public Demon {
616 public:
617 CallMethod3(T* const ct, void (T::*method)(P, Q, R), const std::string& name,
618 P param1, Q param2, R param3)
619 : constraint_(ct),
620 method_(method),
621 name_(name),
622 param1_(param1),
623 param2_(param2),
624 param3_(param3) {}
625
626 ~CallMethod3() override {}
627
628 void Run(Solver* const) override {
629 (constraint_->*method_)(param1_, param2_, param3_);
630 }
631
632 std::string DebugString() const override {
633 return absl::StrCat(absl::StrCat("CallMethod_", name_),
634 absl::StrCat("(", constraint_->DebugString()),
635 absl::StrCat(", ", ParameterDebugString(param1_)),
636 absl::StrCat(", ", ParameterDebugString(param2_)),
637 absl::StrCat(", ", ParameterDebugString(param3_), ")"));
638 }
640 private:
641 T* const constraint_;
642 void (T::* const method_)(P, Q, R);
643 const std::string name_;
644 P param1_;
645 Q param2_;
646 R param3_;
647};
648
649template <class T, class P, class Q, class R>
650Demon* MakeConstraintDemon3(Solver* const s, T* const ct,
651 void (T::*method)(P, Q, R), const std::string& name,
652 P param1, Q param2, R param3) {
653 return s->RevAlloc(
654 new CallMethod3<T, P, Q, R>(ct, method, name, param1, param2, param3));
655}
662
663
664template <class T>
665class DelayedCallMethod0 : public Demon {
666 public:
667 DelayedCallMethod0(T* const ct, void (T::*method)(), const std::string& name)
668 : constraint_(ct), method_(method), name_(name) {}
669
670 ~DelayedCallMethod0() override {}
671
672 void Run(Solver* const) override { (constraint_->*method_)(); }
673
676 }
678 std::string DebugString() const override {
679 return "DelayedCallMethod_" + name_ + "(" + constraint_->DebugString() +
680 ")";
682
683 private:
684 T* const constraint_;
685 void (T::* const method_)();
686 const std::string name_;
687};
688
689template <class T>
690Demon* MakeDelayedConstraintDemon0(Solver* const s, T* const ct,
691 void (T::*method)(),
692 const std::string& name) {
693 return s->RevAlloc(new DelayedCallMethod0<T>(ct, method, name));
694}
695
697template <class T, class P>
698class DelayedCallMethod1 : public Demon {
699 public:
700 DelayedCallMethod1(T* const ct, void (T::*method)(P), const std::string& name,
701 P param1)
702 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
703
704 ~DelayedCallMethod1() override {}
706 void Run(Solver* const) override { (constraint_->*method_)(param1_); }
708 Solver::DemonPriority priority() const override {
710 }
712 std::string DebugString() const override {
713 return absl::StrCat("DelayedCallMethod_", name_, "(",
714 constraint_->DebugString(), ", ",
715 ParameterDebugString(param1_), ")");
716 }
717
718 private:
719 T* const constraint_;
720 void (T::* const method_)(P);
721 const std::string name_;
722 P param1_;
723};
724
725template <class T, class P>
726Demon* MakeDelayedConstraintDemon1(Solver* const s, T* const ct,
727 void (T::*method)(P),
728 const std::string& name, P param1) {
729 return s->RevAlloc(new DelayedCallMethod1<T, P>(ct, method, name, param1));
730}
731
733template <class T, class P, class Q>
734class DelayedCallMethod2 : public Demon {
735 public:
736 DelayedCallMethod2(T* const ct, void (T::*method)(P, Q),
737 const std::string& name, P param1, Q param2)
738 : constraint_(ct),
739 method_(method),
740 name_(name),
741 param1_(param1),
742 param2_(param2) {}
744 ~DelayedCallMethod2() override {}
745
746 void Run(Solver* const) override {
747 (constraint_->*method_)(param1_, param2_);
748 }
749
750 Solver::DemonPriority priority() const override {
752 }
754 std::string DebugString() const override {
755 return absl::StrCat(absl::StrCat("DelayedCallMethod_", name_),
756 absl::StrCat("(", constraint_->DebugString()),
757 absl::StrCat(", ", ParameterDebugString(param1_)),
758 absl::StrCat(", ", ParameterDebugString(param2_), ")"));
759 }
760
761 private:
762 T* const constraint_;
763 void (T::* const method_)(P, Q);
764 const std::string name_;
765 P param1_;
766 Q param2_;
767};
768
769template <class T, class P, class Q>
770Demon* MakeDelayedConstraintDemon2(Solver* const s, T* const ct,
771 void (T::*method)(P, Q),
772 const std::string& name, P param1,
773 Q param2) {
774 return s->RevAlloc(
775 new DelayedCallMethod2<T, P, Q>(ct, method, name, param1, param2));
776}
777/// @}
778
779#endif // !defined(SWIG)
780
781// ----- LightIntFunctionElementCt -----
782
783template <typename F>
785 public:
787 IntVar* const index, F values,
788 std::function<bool()> deep_serialize)
790 var_(var),
791 index_(index),
792 values_(std::move(values)),
793 deep_serialize_(std::move(deep_serialize)) {}
794 ~LightIntFunctionElementCt() override {}
795
796 void Post() override {
797 Demon* demon = MakeConstraintDemon0(
798 solver(), this, &LightIntFunctionElementCt::IndexBound, "IndexBound");
799 index_->WhenBound(demon);
800 }
802 void InitialPropagate() override {
803 if (index_->Bound()) {
804 IndexBound();
805 }
806 }
807
808 std::string DebugString() const override {
809 return absl::StrFormat("LightIntFunctionElementCt(%s, %s)",
810 var_->DebugString(), index_->DebugString());
811 }
812
813 void Accept(ModelVisitor* const visitor) const override {
819 // Warning: This will expand all values into a vector.
820 if (deep_serialize_ == nullptr || deep_serialize_()) {
821 visitor->VisitInt64ToInt64Extension(values_, index_->Min(),
822 index_->Max());
823 }
825 }
826
827 private:
828 void IndexBound() { var_->SetValue(values_(index_->Min())); }
829
830 IntVar* const var_;
831 IntVar* const index_;
832 F values_;
833 std::function<bool()> deep_serialize_;
834};
835
836// ----- LightIntIntFunctionElementCt -----
837
838template <typename F>
840 public:
841 LightIntIntFunctionElementCt(Solver* const solver, IntVar* const var,
842 IntVar* const index1, IntVar* const index2,
843 F values, std::function<bool()> deep_serialize)
845 var_(var),
846 index1_(index1),
847 index2_(index2),
848 values_(std::move(values)),
849 deep_serialize_(std::move(deep_serialize)) {}
851 void Post() override {
852 Demon* demon = MakeConstraintDemon0(
853 solver(), this, &LightIntIntFunctionElementCt::IndexBound,
854 "IndexBound");
855 index1_->WhenBound(demon);
856 index2_->WhenBound(demon);
858 void InitialPropagate() override { IndexBound(); }
859
860 std::string DebugString() const override {
861 return "LightIntIntFunctionElementCt";
862 }
863
864 void Accept(ModelVisitor* const visitor) const override {
865 visitor->BeginVisitConstraint(ModelVisitor::kLightElementEqual, this);
866 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
867 var_);
868 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndexArgument,
869 index1_);
870 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndex2Argument,
871 index2_);
872 // Warning: This will expand all values into a vector.
873 const int64_t index1_min = index1_->Min();
874 const int64_t index1_max = index1_->Max();
875 visitor->VisitIntegerArgument(ModelVisitor::kMinArgument, index1_min);
876 visitor->VisitIntegerArgument(ModelVisitor::kMaxArgument, index1_max);
877 if (deep_serialize_ == nullptr || deep_serialize_()) {
878 for (int i = index1_min; i <= index1_max; ++i) {
879 visitor->VisitInt64ToInt64Extension(
880 [this, i](int64_t j) { return values_(i, j); }, index2_->Min(),
881 index2_->Max());
882 }
883 }
884 visitor->EndVisitConstraint(ModelVisitor::kLightElementEqual, this);
885 }
886
887 private:
888 void IndexBound() {
889 if (index1_->Bound() && index2_->Bound()) {
890 var_->SetValue(values_(index1_->Min(), index2_->Min()));
891 }
892 }
893
894 IntVar* const var_;
895 IntVar* const index1_;
896 IntVar* const index2_;
897 F values_;
898 std::function<bool()> deep_serialize_;
899};
900
901// ----- LightIntIntIntFunctionElementCt -----
902
903template <typename F>
905 public:
906 LightIntIntIntFunctionElementCt(Solver* const solver, IntVar* const var,
907 IntVar* const index1, IntVar* const index2,
908 IntVar* const index3, F values)
910 var_(var),
911 index1_(index1),
912 index2_(index2),
913 index3_(index3),
914 values_(std::move(values)) {}
916 void Post() override {
917 Demon* demon = MakeConstraintDemon0(
918 solver(), this, &LightIntIntIntFunctionElementCt::IndexBound,
919 "IndexBound");
920 index1_->WhenBound(demon);
921 index2_->WhenBound(demon);
922 index3_->WhenBound(demon);
924 void InitialPropagate() override { IndexBound(); }
925
926 std::string DebugString() const override {
927 return "LightIntIntFunctionElementCt";
928 }
929
930 void Accept(ModelVisitor* const visitor) const override {
931 visitor->BeginVisitConstraint(ModelVisitor::kLightElementEqual, this);
932 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
933 var_);
934 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndexArgument,
935 index1_);
936 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndex2Argument,
937 index2_);
938 visitor->VisitIntegerExpressionArgument(ModelVisitor::kIndex3Argument,
939 index3_);
940 visitor->EndVisitConstraint(ModelVisitor::kLightElementEqual, this);
941 }
942
943 private:
944 void IndexBound() {
945 if (index1_->Bound() && index2_->Bound() && index3_->Bound()) {
946 var_->SetValue(values_(index1_->Min(), index2_->Min(), index3_->Min()));
947 }
948 }
949
950 IntVar* const var_;
951 IntVar* const index1_;
952 IntVar* const index2_;
953 IntVar* const index3_;
954 F values_;
955};
956
963
974// TODO(user): rename Start to Synchronize ?
975// TODO(user): decouple the iterating from the defining of a neighbor.
976class LocalSearchOperator : public BaseObject {
977 public:
979 ~LocalSearchOperator() override {}
980 virtual bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) = 0;
981 virtual void EnterSearch() {}
982 virtual void Start(const Assignment* assignment) = 0;
983 virtual void Reset() {}
984#ifndef SWIG
985 virtual const LocalSearchOperator* Self() const { return this; }
986#endif // SWIG
987 virtual bool HasFragments() const { return false; }
988 virtual bool HoldsDelta() const { return false; }
992 public:
996 max_inversible_index_ = candidate_values_.size();
997 candidate_value_to_index_.resize(max_value + 1, -1);
998 committed_value_to_index_.resize(max_value + 1, -1);
1000
1001
1002 /// index.
1003 int64_t CandidateValue(int64_t index) const {
1004 DCHECK_LT(index, candidate_values_.size());
1005 return candidate_values_[index];
1007 int64_t CommittedValue(int64_t index) const {
1008 return committed_values_[index];
1009 }
1010 int64_t CheckPointValue(int64_t index) const {
1011 return checkpoint_values_[index];
1012 }
1013 void SetCandidateValue(int64_t index, int64_t value) {
1014 candidate_values_[index] = value;
1015 if (index < max_inversible_index_) {
1016 candidate_value_to_index_[value] = index;
1017 }
1018 MarkChange(index);
1019 }
1020
1021 bool CandidateIsActive(int64_t index) const {
1022 return candidate_is_active_[index];
1023 }
1024 void SetCandidateActive(int64_t index, bool active) {
1025 if (active) {
1026 candidate_is_active_.Set(index);
1027 } else {
1028 candidate_is_active_.Clear(index);
1029 }
1030 MarkChange(index);
1031 }
1033 void Commit() {
1034 for (const int64_t index : changes_.PositionsSetAtLeastOnce()) {
1035 const int64_t value = candidate_values_[index];
1036 committed_values_[index] = value;
1037 if (index < max_inversible_index_) {
1038 committed_value_to_index_[value] = index;
1039 }
1040 committed_is_active_.CopyBucket(candidate_is_active_, index);
1041 }
1042 changes_.ResetAllToFalse();
1043 incremental_changes_.ResetAllToFalse();
1045
1046 void CheckPoint() { checkpoint_values_ = committed_values_; }
1047
1048 void Revert(bool only_incremental) {
1049 incremental_changes_.ResetAllToFalse();
1050 if (only_incremental) return;
1051
1052 for (const int64_t index : changes_.PositionsSetAtLeastOnce()) {
1053 const int64_t committed_value = committed_values_[index];
1054 candidate_values_[index] = committed_value;
1055 if (index < max_inversible_index_) {
1056 candidate_value_to_index_[committed_value] = index;
1058 candidate_is_active_.CopyBucket(committed_is_active_, index);
1060 changes_.ResetAllToFalse();
1061 }
1062
1063 const std::vector<int64_t>& CandidateIndicesChanged() const {
1064 return changes_.PositionsSetAtLeastOnce();
1065 }
1066 const std::vector<int64_t>& IncrementalIndicesChanged() const {
1067 return incremental_changes_.PositionsSetAtLeastOnce();
1068 }
1069
1070 void Resize(int size) {
1071 candidate_values_.resize(size);
1072 committed_values_.resize(size);
1073 checkpoint_values_.resize(size);
1074 candidate_is_active_.Resize(size);
1075 committed_is_active_.Resize(size);
1076 changes_.ClearAndResize(size);
1077 incremental_changes_.ClearAndResize(size);
1078 }
1079
1080 int64_t CandidateInverseValue(int64_t value) const {
1081 return candidate_value_to_index_[value];
1082 }
1083 int64_t CommittedInverseValue(int64_t value) const {
1084 return committed_value_to_index_[value];
1085 }
1086
1087 private:
1088 void MarkChange(int64_t index) {
1089 incremental_changes_.Set(index);
1090 changes_.Set(index);
1092
1093 std::vector<int64_t> candidate_values_;
1094 std::vector<int64_t> committed_values_;
1095 std::vector<int64_t> checkpoint_values_;
1096
1097 Bitset64<> candidate_is_active_;
1098 Bitset64<> committed_is_active_;
1099
1100 SparseBitset<> changes_;
1101 SparseBitset<> incremental_changes_;
1102
1103 int64_t max_inversible_index_ = -1;
1104 std::vector<int64_t> candidate_value_to_index_;
1105 std::vector<int64_t> committed_value_to_index_;
1106};
1107
1114 public:
1115 // If keep_inverse_values is true, assumes that vars models an injective
1116 // function f with domain [0, vars.size()) in which case the operator will
1117 // maintain the inverse function.
1118 explicit IntVarLocalSearchOperator(const std::vector<IntVar*>& vars,
1119 bool keep_inverse_values = false) {
1120 AddVars(vars);
1121 if (keep_inverse_values) {
1122 int64_t max_value = -1;
1123 for (const IntVar* const var : vars) {
1124 max_value = std::max(max_value, var->Max());
1125 }
1127 }
1128 }
1130
1131 bool HoldsDelta() const override { return true; }
1134 void Start(const Assignment* assignment) override {
1135 state_.CheckPoint();
1136 RevertChanges(false);
1137 const int size = Size();
1138 CHECK_LE(size, assignment->Size())
1139 << "Assignment contains fewer variables than operator";
1140 const Assignment::IntContainer& container = assignment->IntVarContainer();
1141 for (int i = 0; i < size; ++i) {
1142 const IntVarElement* element = &(container.Element(i));
1143 if (element->Var() != vars_[i]) {
1144 CHECK(container.Contains(vars_[i]))
1145 << "Assignment does not contain operator variable " << vars_[i];
1146 element = &(container.Element(vars_[i]));
1147 }
1148 state_.SetCandidateValue(i, element->Value());
1149 state_.SetCandidateActive(i, element->Activated());
1150 }
1151 state_.Commit();
1152 OnStart();
1153 }
1154 virtual bool IsIncremental() const { return false; }
1155
1156 int Size() const { return vars_.size(); }
1159 int64_t Value(int64_t index) const {
1160 DCHECK_LT(index, vars_.size());
1161 return state_.CandidateValue(index);
1162 }
1164 IntVar* Var(int64_t index) const { return vars_[index]; }
1165 virtual bool SkipUnchanged(int) const { return false; }
1166 int64_t OldValue(int64_t index) const { return state_.CommittedValue(index); }
1167 int64_t PrevValue(int64_t index) const {
1168 return state_.CheckPointValue(index);
1169 }
1170 void SetValue(int64_t index, int64_t value) {
1171 state_.SetCandidateValue(index, value);
1172 }
1173 bool Activated(int64_t index) const {
1174 return state_.CandidateIsActive(index);
1176 void Activate(int64_t index) { state_.SetCandidateActive(index, true); }
1177 void Deactivate(int64_t index) { state_.SetCandidateActive(index, false); }
1179 bool ApplyChanges(Assignment* delta, Assignment* deltadelta) const {
1180 if (IsIncremental() && candidate_has_changes_) {
1181 for (const int64_t index : state_.IncrementalIndicesChanged()) {
1182 IntVar* var = Var(index);
1183 const int64_t value = Value(index);
1184 const bool activated = Activated(index);
1185 AddToAssignment(var, value, activated, nullptr, index, deltadelta);
1186 AddToAssignment(var, value, activated, &assignment_indices_, index,
1187 delta);
1189 } else {
1190 delta->Clear();
1191 for (const int64_t index : state_.CandidateIndicesChanged()) {
1192 const int64_t value = Value(index);
1193 const bool activated = Activated(index);
1194 if (!activated || value != OldValue(index) || !SkipUnchanged(index)) {
1195 AddToAssignment(Var(index), value, activated, &assignment_indices_,
1196 index, delta);
1197 }
1198 }
1199 }
1200 return true;
1201 }
1202
1203 void RevertChanges(bool change_was_incremental) {
1204 candidate_has_changes_ = change_was_incremental && IsIncremental();
1205
1206 if (!candidate_has_changes_) {
1207 for (const int64_t index : state_.CandidateIndicesChanged()) {
1208 assignment_indices_[index] = -1;
1209 }
1210 }
1211 state_.Revert(candidate_has_changes_);
1212 }
1213
1214 void AddVars(const std::vector<IntVar*>& vars) {
1215 if (!vars.empty()) {
1216 vars_.insert(vars_.end(), vars.begin(), vars.end());
1217 const int64_t size = Size();
1218 assignment_indices_.resize(size, -1);
1219 state_.Resize(size);
1220 }
1221 }
1222
1224
1225 /// IntVarLocalSearchOperator::Start explicitly.
1226 virtual void OnStart() {}
1227
1230
1233
1237 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
1238
1239 protected:
1242 // TODO(user): make it pure virtual, implies porting all apps overriding
1244 virtual bool MakeOneNeighbor();
1245
1246 int64_t InverseValue(int64_t index) const {
1247 return state_.CandidateInverseValue(index);
1248 }
1249 int64_t OldInverseValue(int64_t index) const {
1250 return state_.CommittedInverseValue(index);
1251 }
1252
1253 void AddToAssignment(IntVar* var, int64_t value, bool active,
1254 std::vector<int>* assignment_indices, int64_t index,
1255 Assignment* assignment) const {
1256 Assignment::IntContainer* const container =
1257 assignment->MutableIntVarContainer();
1258 IntVarElement* element = nullptr;
1259 if (assignment_indices != nullptr) {
1260 if ((*assignment_indices)[index] == -1) {
1261 (*assignment_indices)[index] = container->Size();
1262 element = assignment->FastAdd(var);
1263 } else {
1264 element = container->MutableElement((*assignment_indices)[index]);
1265 }
1266 } else {
1267 element = assignment->FastAdd(var);
1268 }
1269 if (active) {
1270 element->SetValue(value);
1271 element->Activate();
1272 } else {
1273 element->Deactivate();
1274 }
1275 }
1276
1277 private:
1278 std::vector<IntVar*> vars_;
1279 mutable std::vector<int> assignment_indices_;
1280 bool candidate_has_changes_ = false;
1281
1282 LocalSearchOperatorState state_;
1283};
1284
1287
1295
1312class BaseLns : public IntVarLocalSearchOperator {
1313 public:
1314 explicit BaseLns(const std::vector<IntVar*>& vars);
1315 ~BaseLns() override;
1316 virtual void InitFragments();
1317 virtual bool NextFragment() = 0;
1318 void AppendToFragment(int index);
1319 int FragmentSize() const;
1320 bool HasFragments() const override { return true; }
1321
1322 protected:
1324 bool MakeOneNeighbor() override;
1325
1326 private:
1328 void OnStart() override;
1329 std::vector<int> fragment_;
1330};
1337 public:
1338 explicit ChangeValue(const std::vector<IntVar*>& vars);
1339 ~ChangeValue() override;
1340 virtual int64_t ModifyValue(int64_t index, int64_t value) = 0;
1341
1342 protected:
1344 bool MakeOneNeighbor() override;
1345
1346 private:
1347 void OnStart() override;
1348
1349 int index_;
1351
1352// Iterators on nodes used by Pathoperator to traverse the search space.
1353
1355 public:
1356 explicit AlternativeNodeIterator(bool use_sibling)
1357 : use_sibling_(use_sibling) {}
1359 template <class PathOperator>
1360 void Reset(const PathOperator& path_operator, int base_index_reference) {
1361 index_ = 0;
1362 DCHECK(path_operator.ConsiderAlternatives(base_index_reference));
1363 const int64_t base_node = path_operator.BaseNode(base_index_reference);
1364 const int alternative_index =
1365 use_sibling_ ? path_operator.GetSiblingAlternativeIndex(base_node)
1366 : path_operator.GetAlternativeIndex(base_node);
1367 alternative_set_ =
1368 alternative_index >= 0
1369 ? absl::Span<const int64_t>(
1370 path_operator.alternative_sets_[alternative_index])
1371 : absl::Span<const int64_t>();
1373 bool Next() { return ++index_ < alternative_set_.size(); }
1374 int GetValue() const {
1375 return (index_ >= alternative_set_.size()) ? -1 : alternative_set_[index_];
1376 }
1377
1378 private:
1379 const bool use_sibling_;
1380 int index_ = 0;
1381 absl::Span<const int64_t> alternative_set_;
1382};
1383
1384class NodeNeighborIterator {
1385 public:
1388 template <class PathOperator>
1389 void Reset(const PathOperator& path_operator, int base_index_reference) {
1390 using Span = absl::Span<const int>;
1391 index_ = 0;
1392 const int64_t base_node = path_operator.BaseNode(base_index_reference);
1393 const int64_t start_node = path_operator.StartNode(base_index_reference);
1394 const auto& get_incoming_neighbors =
1395 path_operator.iteration_parameters_.get_incoming_neighbors;
1396 incoming_neighbors_ =
1397 path_operator.IsPathStart(base_node) || !get_incoming_neighbors
1398 ? Span()
1399 : Span(get_incoming_neighbors(base_node, start_node));
1400 const auto& get_outgoing_neighbors =
1401 path_operator.iteration_parameters_.get_outgoing_neighbors;
1402 outgoing_neighbors_ =
1403 path_operator.IsPathEnd(base_node) || !get_outgoing_neighbors
1404 ? Span()
1405 : Span(get_outgoing_neighbors(base_node, start_node));
1406 }
1407 bool Next() {
1408 return ++index_ < incoming_neighbors_.size() + outgoing_neighbors_.size();
1409 }
1410 int GetValue() const {
1411 if (index_ < incoming_neighbors_.size()) {
1412 return incoming_neighbors_[index_];
1413 }
1414 const int index = index_ - incoming_neighbors_.size();
1415 return (index >= outgoing_neighbors_.size()) ? -1
1416 : outgoing_neighbors_[index];
1417 }
1418 bool IsIncomingNeighbor() const {
1419 return index_ < incoming_neighbors_.size();
1420 }
1421 bool IsOutgoingNeighbor() const {
1422 return index_ >= incoming_neighbors_.size();
1423 }
1425 private:
1426 int index_ = 0;
1427 absl::Span<const int> incoming_neighbors_;
1428 absl::Span<const int> outgoing_neighbors_;
1429};
1430
1431template <class PathOperator>
1433 public:
1434 BaseNodeIterators(const PathOperator* path_operator, int base_index_reference)
1435 : path_operator_(*path_operator),
1436 base_index_reference_(base_index_reference) {}
1438 DCHECK(!alternatives_.empty());
1439 DCHECK(!finished_);
1440 return alternatives_[0].get();
1441 }
1442 AlternativeNodeIterator* GetAlternativeIterator() const {
1443 DCHECK(!alternatives_.empty());
1444 DCHECK(!finished_);
1445 return alternatives_[1].get();
1448 DCHECK(neighbors_);
1449 DCHECK(!finished_);
1450 return neighbors_.get();
1452 void Initialize() {
1453 if (path_operator_.ConsiderAlternatives(base_index_reference_)) {
1454 alternatives_.push_back(std::make_unique<AlternativeNodeIterator>(
1455 /*is_sibling=*/true));
1456 alternatives_.push_back(std::make_unique<AlternativeNodeIterator>(
1457 /*is_sibling=*/false));
1458 }
1459 if (path_operator_.HasNeighbors()) {
1460 neighbors_ = std::make_unique<NodeNeighborIterator>();
1462 }
1463 void Reset(bool update_end_nodes = false) {
1464 finished_ = false;
1465 for (auto& alternative_iterator : alternatives_) {
1466 alternative_iterator->Reset(path_operator_, base_index_reference_);
1467 }
1468 if (neighbors_) {
1469 neighbors_->Reset(path_operator_, base_index_reference_);
1470 if (update_end_nodes) neighbor_end_node_ = neighbors_->GetValue();
1471 }
1472 }
1473 bool Increment() {
1474 DCHECK(!finished_);
1475 for (auto& alternative_iterator : alternatives_) {
1476 if (alternative_iterator->Next()) return true;
1477 alternative_iterator->Reset(path_operator_, base_index_reference_);
1478 }
1479 if (neighbors_) {
1480 if (neighbors_->Next()) return true;
1481 neighbors_->Reset(path_operator_, base_index_reference_);
1482 }
1483 finished_ = true;
1484 return false;
1485 }
1486 bool HasReachedEnd() const {
1487 // TODO(user): Extend to other iterators.
1488 if (!neighbors_) return true;
1489 return neighbor_end_node_ == neighbors_->GetValue();
1490 }
1491
1492 private:
1493 const PathOperator& path_operator_;
1494 int base_index_reference_ = -1;
1495#ifndef SWIG
1496 std::vector<std::unique_ptr<AlternativeNodeIterator>> alternatives_;
1497#endif // SWIG
1498 std::unique_ptr<NodeNeighborIterator> neighbors_;
1499 int neighbor_end_node_ = -1;
1500 bool finished_ = false;
1501};
1502
1505
1516template <bool ignore_path_vars>
1518 public:
1520 struct IterationParameters {
1531 /// p1 and p2 are path indices,
1532 /// then if c1 == c2, p1 and p2 are equivalent if they are empty.
1533 /// This is used to remove neighborhood symmetries on equivalent empty
1534 /// paths; for instance if a node cannot be moved to an empty path, then all
1535 /// moves moving the same node to equivalent empty paths will be skipped.
1536 /// 'start_empty_path_class' can be nullptr in which case no symmetries will
1537 /// be removed.
1538 std::function<int(int64_t)> start_empty_path_class;
1541 std::function<const std::vector<int>&(
1542 /*node=*/int, /*start_node=*/int)>
1544 std::function<const std::vector<int>&(
1545 /*node=*/int, /*start_node=*/int)>
1547 };
1549 PathOperator(const std::vector<IntVar*>& next_vars,
1550 const std::vector<IntVar*>& path_vars,
1551 IterationParameters iteration_parameters)
1552 : IntVarLocalSearchOperator(next_vars, true),
1553 number_of_nexts_(next_vars.size()),
1554 base_nodes_(
1555 std::make_unique<int[]>(iteration_parameters.number_of_base_nodes)),
1556 end_nodes_(
1557 std::make_unique<int[]>(iteration_parameters.number_of_base_nodes)),
1558 base_paths_(
1559 std::make_unique<int[]>(iteration_parameters.number_of_base_nodes)),
1560 node_path_starts_(number_of_nexts_, -1),
1561 node_path_ends_(number_of_nexts_, -1),
1562 just_started_(false),
1563 first_start_(true),
1564 next_base_to_increment_(iteration_parameters.number_of_base_nodes),
1565 iteration_parameters_(std::move(iteration_parameters)),
1566 optimal_paths_enabled_(false),
1567 active_paths_(number_of_nexts_),
1568 alternative_index_(next_vars.size(), -1) {
1569 DCHECK_GT(iteration_parameters_.number_of_base_nodes, 0);
1570 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
1571 base_node_iterators_.push_back(BaseNodeIterators<PathOperator>(this, i));
1572 }
1573 if constexpr (!ignore_path_vars) {
1574 AddVars(path_vars);
1575 }
1576 path_basis_.push_back(0);
1577 for (int i = 1; i < iteration_parameters_.number_of_base_nodes; ++i) {
1578 if (!OnSamePathAsPreviousBase(i)) path_basis_.push_back(i);
1579 }
1580 if ((path_basis_.size() > 2) ||
1581 (!next_vars.empty() && !next_vars.back()
1582 ->solver()
1583 ->parameters()
1584 .skip_locally_optimal_paths())) {
1585 iteration_parameters_.skip_locally_optimal_paths = false;
1586 }
1587 }
1589 const std::vector<IntVar*>& next_vars,
1590 const std::vector<IntVar*>& path_vars, int number_of_base_nodes,
1591 bool skip_locally_optimal_paths, bool accept_path_end_base,
1592 std::function<int(int64_t)> start_empty_path_class,
1593 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
1594 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors)
1595 : PathOperator(next_vars, path_vars,
1596 {number_of_base_nodes, skip_locally_optimal_paths,
1597 accept_path_end_base, std::move(start_empty_path_class),
1598 std::move(get_incoming_neighbors),
1599 std::move(get_outgoing_neighbors)}) {}
1600 ~PathOperator() override {}
1601 virtual bool MakeNeighbor() = 0;
1602 void EnterSearch() override {
1603 first_start_ = true;
1605 }
1606 void Reset() override {
1607 active_paths_.Clear();
1609 }
1610
1611 // TODO(user): Make the following methods protected.
1612 bool SkipUnchanged(int index) const override {
1613 if constexpr (ignore_path_vars) return true;
1614 if (index < number_of_nexts_) {
1615 const int path_index = index + number_of_nexts_;
1616 return Value(path_index) == OldValue(path_index);
1617 }
1618 const int next_index = index - number_of_nexts_;
1619 return Value(next_index) == OldValue(next_index);
1621
1623 int64_t Next(int64_t node) const {
1624 DCHECK(!IsPathEnd(node));
1625 return Value(node);
1627
1629 int64_t Prev(int64_t node) const {
1630 DCHECK(!IsPathStart(node));
1631 DCHECK_EQ(Next(InverseValue(node)), node);
1632 return InverseValue(node);
1633 }
1634
1635
1637 int64_t Path(int64_t node) const {
1638 if constexpr (ignore_path_vars) return 0LL;
1639 return Value(node + number_of_nexts_);
1640 }
1641
1643 int number_of_nexts() const { return number_of_nexts_; }
1644
1645 protected:
1647 bool MakeOneNeighbor() override {
1648 while (IncrementPosition()) {
1649 // Need to revert changes here since MakeNeighbor might have returned
1650 // false and have done changes in the previous iteration.
1652 if (MakeNeighbor()) {
1653 return true;
1654 }
1655 }
1656 return false;
1658
1661 /// explicitly.
1662 virtual void OnNodeInitialization() {}
1667 virtual void ResetIncrementalism() {}
1668
1670 int64_t BaseNode(int i) const { return base_nodes_[i]; }
1672 int64_t BaseAlternativeNode(int i) const {
1673 return GetNodeWithDefault(base_node_iterators_[i].GetAlternativeIterator(),
1674 BaseNode(i));
1675 }
1677 int64_t BaseSiblingAlternativeNode(int i) const {
1678 return GetNodeWithDefault(
1679 base_node_iterators_[i].GetSiblingAlternativeIterator(), BaseNode(i));
1680 }
1682 int64_t StartNode(int i) const { return path_starts_[base_paths_[i]]; }
1684 int64_t EndNode(int i) const { return path_ends_[base_paths_[i]]; }
1686 const std::vector<int64_t>& path_starts() const { return path_starts_; }
1688 int PathClass(int i) const { return PathClassFromStartNode(StartNode(i)); }
1689 int PathClassFromStartNode(int64_t start_node) const {
1690 return iteration_parameters_.start_empty_path_class != nullptr
1691 ? iteration_parameters_.start_empty_path_class(start_node)
1692 : start_node;
1693 }
1694
1695
1701 // TODO(user): remove this when automatic detection of such cases in done.
1702 virtual bool RestartAtPathStartOnSynchronize() { return false; }
1703 /// Returns true if a base node has to be on the same path as the "previous"
1704 /// base node (base node of index base_index - 1).
1705 /// Useful to limit neighborhood exploration to nodes on the same path.
1706 // TODO(user): ideally this should be OnSamePath(int64_t node1, int64_t
1707 // node2);
1708
1709 virtual bool OnSamePathAsPreviousBase(int64_t) { return false; }
1715 virtual int64_t GetBaseNodeRestartPosition(int base_index) {
1716 return StartNode(base_index);
1717 }
1720 virtual void SetNextBaseToIncrement(int64_t base_index) {
1721 next_base_to_increment_ = base_index;
1722 }
1725 virtual bool ConsiderAlternatives(int64_t) const { return false; }
1726
1727 int64_t OldNext(int64_t node) const {
1728 DCHECK(!IsPathEnd(node));
1729 return OldValue(node);
1730 }
1731
1732 int64_t PrevNext(int64_t node) const {
1733 DCHECK(!IsPathEnd(node));
1734 return PrevValue(node);
1735 }
1736
1737 int64_t OldPrev(int64_t node) const {
1738 DCHECK(!IsPathStart(node));
1739 return OldInverseValue(node);
1740 }
1742 int64_t OldPath(int64_t node) const {
1743 if constexpr (ignore_path_vars) return 0LL;
1744 return OldValue(node + number_of_nexts_);
1745 }
1747 int CurrentNodePathStart(int64_t node) const {
1748 return node_path_starts_[node];
1749 }
1750
1751 int CurrentNodePathEnd(int64_t node) const { return node_path_ends_[node]; }
1752
1755 bool MoveChain(int64_t before_chain, int64_t chain_end, int64_t destination) {
1756 if (destination == before_chain || destination == chain_end) return false;
1757 DCHECK(CheckChainValidity(before_chain, chain_end, destination) &&
1758 !IsPathEnd(chain_end) && !IsPathEnd(destination));
1759 const int64_t destination_path = Path(destination);
1760 const int64_t after_chain = Next(chain_end);
1761 SetNext(chain_end, Next(destination), destination_path);
1762 if constexpr (!ignore_path_vars) {
1763 int current = destination;
1764 int next = Next(before_chain);
1765 while (current != chain_end) {
1766 SetNext(current, next, destination_path);
1767 current = next;
1768 next = Next(next);
1770 } else {
1771 SetNext(destination, Next(before_chain), destination_path);
1772 }
1773 SetNext(before_chain, after_chain, Path(before_chain));
1774 return true;
1775 }
1776
1779 bool ReverseChain(int64_t before_chain, int64_t after_chain,
1780 int64_t* chain_last) {
1781 if (CheckChainValidity(before_chain, after_chain, -1)) {
1782 int64_t path = Path(before_chain);
1783 int64_t current = Next(before_chain);
1784 if (current == after_chain) {
1785 return false;
1786 }
1787 int64_t current_next = Next(current);
1788 SetNext(current, after_chain, path);
1789 while (current_next != after_chain) {
1790 const int64_t next = Next(current_next);
1791 SetNext(current_next, current, path);
1792 current = current_next;
1793 current_next = next;
1794 }
1795 SetNext(before_chain, current, path);
1796 *chain_last = current;
1797 return true;
1798 }
1799 return false;
1800 }
1801
1803 bool SwapNodes(int64_t node1, int64_t node2) {
1804 if (IsPathEnd(node1) || IsPathEnd(node2) || IsPathStart(node1) ||
1805 IsPathStart(node2)) {
1806 return false;
1807 }
1808 if (node1 == node2) return false;
1809 const int64_t prev_node1 = Prev(node1);
1810 const bool ok = MoveChain(prev_node1, node1, Prev(node2));
1811 return MoveChain(Prev(node2), node2, prev_node1) || ok;
1812 }
1813
1815 bool MakeActive(int64_t node, int64_t destination) {
1816 if (IsPathEnd(destination)) return false;
1817 const int64_t destination_path = Path(destination);
1818 SetNext(node, Next(destination), destination_path);
1819 SetNext(destination, node, destination_path);
1820 return true;
1821 }
1824 bool MakeChainInactive(int64_t before_chain, int64_t chain_end) {
1825 const int64_t kNoPath = -1;
1826 if (CheckChainValidity(before_chain, chain_end, -1) &&
1827 !IsPathEnd(chain_end)) {
1828 const int64_t after_chain = Next(chain_end);
1829 int64_t current = Next(before_chain);
1830 while (current != after_chain) {
1831 const int64_t next = Next(current);
1832 SetNext(current, current, kNoPath);
1833 current = next;
1834 }
1835 SetNext(before_chain, after_chain, Path(before_chain));
1836 return true;
1837 }
1838 return false;
1839 }
1840
1842 bool SwapActiveAndInactive(int64_t active, int64_t inactive) {
1843 if (active == inactive) return false;
1844 const int64_t prev = Prev(active);
1845 return MakeChainInactive(prev, active) && MakeActive(inactive, prev);
1846 }
1849 bool SwapActiveAndInactiveChains(absl::Span<const int64_t> active_chain,
1850 absl::Span<const int64_t> inactive_chain) {
1851 if (active_chain.empty()) return false;
1852 if (active_chain == inactive_chain) return false;
1853 const int before_active_chain = Prev(active_chain.front());
1854 if (!MakeChainInactive(before_active_chain, active_chain.back())) {
1855 return false;
1857 for (auto it = inactive_chain.crbegin(); it != inactive_chain.crend();
1858 ++it) {
1859 if (!MakeActive(*it, before_active_chain)) return false;
1860 }
1861 return true;
1862 }
1865 void SetNext(int64_t from, int64_t to, int64_t path) {
1866 DCHECK_LT(from, number_of_nexts_);
1867 SetValue(from, to);
1868 if constexpr (!ignore_path_vars) {
1869 DCHECK_LT(from + number_of_nexts_, Size());
1870 SetValue(from + number_of_nexts_, path);
1871 }
1872 }
1873
1876 bool IsPathEnd(int64_t node) const { return node >= number_of_nexts_; }
1877
1879 bool IsPathStart(int64_t node) const { return OldInverseValue(node) == -1; }
1880
1882 bool IsInactive(int64_t node) const {
1883 return !IsPathEnd(node) && inactives_[node];
1884 }
1885
1887
1888 virtual bool InitPosition() const { return false; }
1892 void ResetPosition() { just_started_ = true; }
1896 /// two alternatives.
1897 int AddAlternativeSet(const std::vector<int64_t>& alternative_set) {
1898 const int alternative = alternative_sets_.size();
1899 for (int64_t node : alternative_set) {
1900 DCHECK_EQ(-1, alternative_index_[node]);
1901 alternative_index_[node] = alternative;
1903 alternative_sets_.push_back(alternative_set);
1904 sibling_alternative_.push_back(-1);
1905 return alternative;
1907#ifndef SWIG
1910 template <typename PairType>
1912 const std::vector<PairType>& pair_alternative_sets) {
1913 for (const auto& [alternative_set, sibling_alternative_set] :
1914 pair_alternative_sets) {
1915 sibling_alternative_.back() = AddAlternativeSet(alternative_set) + 1;
1916 AddAlternativeSet(sibling_alternative_set);
1917 }
1918 }
1919#endif // SWIG
1921 int64_t GetActiveInAlternativeSet(int alternative_index) const {
1922 return alternative_index >= 0
1923 ? active_in_alternative_set_[alternative_index]
1924 : -1;
1927 int64_t GetActiveAlternativeNode(int node) const {
1928 return GetActiveInAlternativeSet(alternative_index_[node]);
1929 }
1931 int GetSiblingAlternativeIndex(int node) const {
1932 const int alternative = GetAlternativeIndex(node);
1933 return alternative >= 0 ? sibling_alternative_[alternative] : -1;
1934 }
1935 /// Returns the index of the alternative set of the node.
1936 int GetAlternativeIndex(int node) const {
1937 return (node >= alternative_index_.size()) ? -1 : alternative_index_[node];
1938 }
1940
1941 int64_t GetActiveAlternativeSibling(int node) const {
1943 }
1944
1945 /// to chain_end and does not contain exclude.
1946 /// In particular, rejects a chain if chain_end is not strictly after
1947 /// before_chain on the path.
1948 /// Cycles are detected through chain length overflow.
1949 bool CheckChainValidity(int64_t before_chain, int64_t chain_end,
1950 int64_t exclude) const {
1951 if (before_chain == chain_end || before_chain == exclude) return false;
1952 int64_t current = before_chain;
1953 int chain_size = 0;
1954 while (current != chain_end) {
1955 if (chain_size > number_of_nexts_) return false;
1956 if (IsPathEnd(current)) return false;
1957 current = Next(current);
1958 ++chain_size;
1959 if (current == exclude) return false;
1960 }
1961 return true;
1962 }
1964 bool HasNeighbors() const {
1965 return iteration_parameters_.get_incoming_neighbors != nullptr ||
1966 iteration_parameters_.get_outgoing_neighbors != nullptr;
1967 }
1968
1969 struct Neighbor {
1970 // Index of the neighbor node.
1971 int neighbor;
1972 // True if 'neighbor' is an outgoing neighbor (i.e. arc main_node->neighbor)
1973 // and false if it's an incoming one (arc neighbor->main_node).
1974 bool outgoing;
1975 };
1976 Neighbor GetNeighborForBaseNode(int64_t base_index) const {
1977 auto* iterator = base_node_iterators_[base_index].GetNeighborIterator();
1978 return {.neighbor = iterator->GetValue(),
1979 .outgoing = iterator->IsOutgoingNeighbor()};
1980 }
1981
1982 const int number_of_nexts_;
1984 private:
1985 template <class NodeIterator>
1986 static int GetNodeWithDefault(const NodeIterator* node_iterator,
1987 int default_value) {
1988 const int node = node_iterator->GetValue();
1989 return node >= 0 ? node : default_value;
1991
1992 void OnStart() override {
1993 optimal_paths_enabled_ = false;
1994 if (!iterators_initialized_) {
1995 iterators_initialized_ = true;
1996 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
1997 base_node_iterators_[i].Initialize();
1998 }
1999 }
2000 InitializeBaseNodes();
2001 InitializeAlternatives();
2002 OnNodeInitialization();
2003 }
2004
2006 bool OnSamePath(int64_t node1, int64_t node2) const {
2007 if (IsInactive(node1) != IsInactive(node2)) {
2008 return false;
2009 }
2010 for (int node = node1; !IsPathEnd(node); node = OldNext(node)) {
2011 if (node == node2) {
2012 return true;
2013 }
2014 }
2015 for (int node = node2; !IsPathEnd(node); node = OldNext(node)) {
2016 if (node == node1) {
2017 return true;
2018 }
2019 }
2020 return false;
2021 }
2022
2023 bool CheckEnds() const {
2024 for (int i = iteration_parameters_.number_of_base_nodes - 1; i >= 0; --i) {
2025 if (base_nodes_[i] != end_nodes_[i] ||
2026 !base_node_iterators_[i].HasReachedEnd()) {
2027 return true;
2028 }
2029 }
2030 return false;
2031 }
2032 bool IncrementPosition() {
2033 const int base_node_size = iteration_parameters_.number_of_base_nodes;
2034
2035 if (just_started_) {
2036 just_started_ = false;
2037 return true;
2038 }
2039 const int number_of_paths = path_starts_.size();
2040 // Finding next base node positions.
2041 // Increment the position of inner base nodes first (higher index nodes);
2042 // if a base node is at the end of a path, reposition it at the start
2043 // of the path and increment the position of the preceding base node (this
2044 // action is called a restart).
2045 int last_restarted = base_node_size;
2046 for (int i = base_node_size - 1; i >= 0; --i) {
2047 if (base_nodes_[i] < number_of_nexts_ && i <= next_base_to_increment_) {
2048 if (base_node_iterators_[i].Increment()) break;
2049 base_nodes_[i] = OldNext(base_nodes_[i]);
2050 base_node_iterators_[i].Reset();
2051 if (iteration_parameters_.accept_path_end_base ||
2052 !IsPathEnd(base_nodes_[i])) {
2053 break;
2054 }
2055 }
2056 base_nodes_[i] = StartNode(i);
2057 base_node_iterators_[i].Reset();
2058 last_restarted = i;
2059 }
2060 next_base_to_increment_ = base_node_size;
2061 // At the end of the loop, base nodes with indexes in
2062 // [last_restarted, base_node_size[ have been restarted.
2063 // Restarted base nodes are then repositioned by the virtual
2064 // GetBaseNodeRestartPosition to reflect position constraints between
2065 // base nodes (by default GetBaseNodeRestartPosition leaves the nodes
2066 // at the start of the path).
2067 // Base nodes are repositioned in ascending order to ensure that all
2068 // base nodes "below" the node being repositioned have their final
2069 // position.
2070 for (int i = last_restarted; i < base_node_size; ++i) {
2071 base_nodes_[i] = GetBaseNodeRestartPosition(i);
2072 base_node_iterators_[i].Reset();
2073 }
2074 if (last_restarted > 0) {
2075 return CheckEnds();
2076 }
2077 // If all base nodes have been restarted, base nodes are moved to new paths.
2078 // First we mark the current paths as locally optimal if they have been
2079 // completely explored.
2080 if (optimal_paths_enabled_ &&
2081 iteration_parameters_.skip_locally_optimal_paths) {
2082 if (path_basis_.size() > 1) {
2083 for (int i = 1; i < path_basis_.size(); ++i) {
2084 active_paths_.DeactivatePathPair(StartNode(path_basis_[i - 1]),
2085 StartNode(path_basis_[i]));
2086 }
2087 } else {
2088 active_paths_.DeactivatePathPair(StartNode(path_basis_[0]),
2089 StartNode(path_basis_[0]));
2090 }
2091 }
2092 std::vector<int> current_starts(base_node_size);
2093 for (int i = 0; i < base_node_size; ++i) {
2094 current_starts[i] = StartNode(i);
2095 }
2096 // Exploration of next paths can lead to locally optimal paths since we are
2097 // exploring them from scratch.
2098 optimal_paths_enabled_ = true;
2099 while (true) {
2100 for (int i = base_node_size - 1; i >= 0; --i) {
2101 const int next_path_index = base_paths_[i] + 1;
2102 if (next_path_index < number_of_paths) {
2103 base_paths_[i] = next_path_index;
2104 base_nodes_[i] = path_starts_[next_path_index];
2105 base_node_iterators_[i].Reset();
2106 if (i == 0 || !OnSamePathAsPreviousBase(i)) {
2107 break;
2108 }
2109 } else {
2110 base_paths_[i] = 0;
2111 base_nodes_[i] = path_starts_[0];
2112 base_node_iterators_[i].Reset();
2113 }
2114 }
2115 if (!iteration_parameters_.skip_locally_optimal_paths) return CheckEnds();
2116 // If the new paths have already been completely explored, we can
2117 // skip them from now on.
2118 if (path_basis_.size() > 1) {
2119 for (int j = 1; j < path_basis_.size(); ++j) {
2120 if (active_paths_.IsPathPairActive(StartNode(path_basis_[j - 1]),
2121 StartNode(path_basis_[j]))) {
2122 return CheckEnds();
2123 }
2124 }
2125 } else {
2126 if (active_paths_.IsPathPairActive(StartNode(path_basis_[0]),
2127 StartNode(path_basis_[0]))) {
2128 return CheckEnds();
2129 }
2130 }
2131 // If we are back to paths we just iterated on or have reached the end
2132 // of the neighborhood search space, we can stop.
2133 if (!CheckEnds()) return false;
2134 bool stop = true;
2135 for (int i = 0; i < base_node_size; ++i) {
2136 if (StartNode(i) != current_starts[i]) {
2137 stop = false;
2138 break;
2139 }
2140 }
2141 if (stop) return false;
2142 }
2143 return CheckEnds();
2144 }
2145
2146 void InitializePathStarts() {
2147 // Detect nodes which do not have any possible predecessor in a path; these
2148 // nodes are path starts.
2149 int max_next = -1;
2150 std::vector<bool> has_prevs(number_of_nexts_, false);
2151 for (int i = 0; i < number_of_nexts_; ++i) {
2152 const int next = OldNext(i);
2153 if (next < number_of_nexts_) {
2154 has_prevs[next] = true;
2155 }
2156 max_next = std::max(max_next, next);
2157 }
2158 // Update locally optimal paths.
2159 if (iteration_parameters_.skip_locally_optimal_paths) {
2160 active_paths_.Initialize(
2161 /*is_start=*/[&has_prevs](int node) { return !has_prevs[node]; });
2162 for (int i = 0; i < number_of_nexts_; ++i) {
2163 if (!has_prevs[i]) {
2164 int current = i;
2165 while (!IsPathEnd(current)) {
2166 if ((OldNext(current) != PrevNext(current))) {
2167 active_paths_.ActivatePath(i);
2168 break;
2169 }
2170 current = OldNext(current);
2171 }
2172 }
2173 }
2174 }
2175 // Create a list of path starts, dropping equivalent path starts of
2176 // currently empty paths.
2177 std::vector<bool> empty_found(number_of_nexts_, false);
2178 std::vector<int64_t> new_path_starts;
2179 for (int i = 0; i < number_of_nexts_; ++i) {
2180 if (!has_prevs[i]) {
2181 if (IsPathEnd(OldNext(i))) {
2182 if (iteration_parameters_.start_empty_path_class != nullptr) {
2183 if (empty_found[iteration_parameters_.start_empty_path_class(i)])
2184 continue;
2185 empty_found[iteration_parameters_.start_empty_path_class(i)] = true;
2186 }
2187 }
2188 new_path_starts.push_back(i);
2189 }
2190 }
2191 if (!first_start_) {
2192 // Synchronizing base_paths_ with base node positions. When the last move
2193 // was performed a base node could have been moved to a new route in which
2194 // case base_paths_ needs to be updated. This needs to be done on the path
2195 // starts before we re-adjust base nodes for new path starts.
2196 std::vector<int> node_paths(max_next + 1, -1);
2197 for (int i = 0; i < path_starts_.size(); ++i) {
2198 int node = path_starts_[i];
2199 while (!IsPathEnd(node)) {
2200 node_paths[node] = i;
2201 node = OldNext(node);
2202 }
2203 node_paths[node] = i;
2204 }
2205 for (int j = 0; j < iteration_parameters_.number_of_base_nodes; ++j) {
2206 if (IsInactive(base_nodes_[j]) || node_paths[base_nodes_[j]] == -1) {
2207 // Base node was made inactive or was moved to a new path, reposition
2208 // the base node to its restart position.
2209 base_nodes_[j] = GetBaseNodeRestartPosition(j);
2210 base_paths_[j] = node_paths[base_nodes_[j]];
2211 } else {
2212 base_paths_[j] = node_paths[base_nodes_[j]];
2213 }
2214 // Always restart from first alternative.
2215 base_node_iterators_[j].Reset();
2216 }
2217 // Re-adjust current base_nodes and base_paths to take into account new
2218 // path starts (there could be fewer if a new path was made empty, or more
2219 // if nodes were added to a formerly empty path).
2220 int new_index = 0;
2221 absl::flat_hash_set<int> found_bases;
2222 for (int i = 0; i < path_starts_.size(); ++i) {
2223 int index = new_index;
2224 // Note: old and new path starts are sorted by construction.
2225 while (index < new_path_starts.size() &&
2226 new_path_starts[index] < path_starts_[i]) {
2227 ++index;
2228 }
2229 const bool found = (index < new_path_starts.size() &&
2230 new_path_starts[index] == path_starts_[i]);
2231 if (found) {
2232 new_index = index;
2233 }
2234 for (int j = 0; j < iteration_parameters_.number_of_base_nodes; ++j) {
2235 if (base_paths_[j] == i && !found_bases.contains(j)) {
2236 found_bases.insert(j);
2237 base_paths_[j] = new_index;
2238 // If the current position of the base node is a removed empty path,
2239 // readjusting it to the last visited path start.
2240 if (!found) {
2241 base_nodes_[j] = new_path_starts[new_index];
2242 }
2243 }
2244 }
2245 }
2246 }
2247 path_starts_.swap(new_path_starts);
2248 // For every base path, store the end corresponding to the path start.
2249 // TODO(user): make this faster, maybe by pairing starts with ends.
2250 path_ends_.clear();
2251 path_ends_.reserve(path_starts_.size());
2252 int64_t max_node_index = number_of_nexts_ - 1;
2253 for (const int start_node : path_starts_) {
2254 int64_t node = start_node;
2255 while (!IsPathEnd(node)) node = OldNext(node);
2256 path_ends_.push_back(node);
2257 max_node_index = std::max(max_node_index, node);
2258 }
2259 node_path_starts_.assign(max_node_index + 1, -1);
2260 node_path_ends_.assign(max_node_index + 1, -1);
2261 for (int i = 0; i < path_starts_.size(); ++i) {
2262 const int64_t start_node = path_starts_[i];
2263 const int64_t end_node = path_ends_[i];
2264 int64_t node = start_node;
2265 while (!IsPathEnd(node)) {
2266 node_path_starts_[node] = start_node;
2267 node_path_ends_[node] = end_node;
2268 node = OldNext(node);
2269 }
2270 node_path_starts_[node] = start_node;
2271 node_path_ends_[node] = end_node;
2272 }
2273 }
2274 void InitializeInactives() {
2275 inactives_.clear();
2276 for (int i = 0; i < number_of_nexts_; ++i) {
2277 inactives_.push_back(OldNext(i) == i);
2278 }
2279 }
2280 void InitializeBaseNodes() {
2281 // Inactive nodes must be detected before determining new path starts.
2282 InitializeInactives();
2283 InitializePathStarts();
2284 if (first_start_ || InitPosition()) {
2285 // Only do this once since the following starts will continue from the
2286 // preceding position
2287 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
2288 base_paths_[i] = 0;
2289 base_nodes_[i] = path_starts_[0];
2290 }
2291 first_start_ = false;
2292 }
2293 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
2294 // If base node has been made inactive, restart from path start.
2295 int64_t base_node = base_nodes_[i];
2296 if (RestartAtPathStartOnSynchronize() || IsInactive(base_node)) {
2297 base_node = path_starts_[base_paths_[i]];
2298 base_nodes_[i] = base_node;
2299 }
2300 end_nodes_[i] = base_node;
2301 }
2302 // Repair end_nodes_ in case some must be on the same path and are not
2303 // anymore (due to other operators moving these nodes).
2304 for (int i = 1; i < iteration_parameters_.number_of_base_nodes; ++i) {
2305 if (OnSamePathAsPreviousBase(i) &&
2306 !OnSamePath(base_nodes_[i - 1], base_nodes_[i])) {
2307 const int64_t base_node = base_nodes_[i - 1];
2308 base_nodes_[i] = base_node;
2309 end_nodes_[i] = base_node;
2310 base_paths_[i] = base_paths_[i - 1];
2311 }
2312 }
2313 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
2314 base_node_iterators_[i].Reset(/*update_end_nodes=*/true);
2315 }
2316 just_started_ = true;
2317 }
2318 void InitializeAlternatives() {
2319 active_in_alternative_set_.resize(alternative_sets_.size(), -1);
2320 for (int i = 0; i < alternative_sets_.size(); ++i) {
2321 const int64_t current_active = active_in_alternative_set_[i];
2322 if (current_active >= 0 && !IsInactive(current_active)) continue;
2323 for (int64_t index : alternative_sets_[i]) {
2324 if (!IsInactive(index)) {
2325 active_in_alternative_set_[i] = index;
2326 break;
2327 }
2328 }
2329 }
2330 }
2331
2332 class ActivePaths {
2333 public:
2334 explicit ActivePaths(int num_nodes) : start_to_path_(num_nodes, -1) {}
2335 void Clear() { to_reset_ = true; }
2336 template <typename T>
2337 void Initialize(T is_start) {
2338 if (is_path_pair_active_.empty()) {
2339 num_paths_ = 0;
2340 absl::c_fill(start_to_path_, -1);
2341 for (int i = 0; i < start_to_path_.size(); ++i) {
2342 if (is_start(i)) {
2343 start_to_path_[i] = num_paths_;
2344 ++num_paths_;
2345 }
2346 }
2347 }
2348 }
2349 void DeactivatePathPair(int start1, int start2) {
2350 if (to_reset_) Reset();
2351 is_path_pair_active_[start_to_path_[start1] * num_paths_ +
2352 start_to_path_[start2]] = false;
2353 }
2354 void ActivatePath(int start) {
2355 if (to_reset_) Reset();
2356 const int p1 = start_to_path_[start];
2357 const int p1_block = num_paths_ * p1;
2358 for (int p2 = 0; p2 < num_paths_; ++p2) {
2359 is_path_pair_active_[p1_block + p2] = true;
2360 }
2361 for (int p2_block = 0; p2_block < is_path_pair_active_.size();
2362 p2_block += num_paths_) {
2363 is_path_pair_active_[p2_block + p1] = true;
2364 }
2365 }
2366 bool IsPathPairActive(int start1, int start2) const {
2367 if (to_reset_) return true;
2368 return is_path_pair_active_[start_to_path_[start1] * num_paths_ +
2369 start_to_path_[start2]];
2370 }
2371
2372 private:
2373 void Reset() {
2374 if (!to_reset_) return;
2375 is_path_pair_active_.assign(num_paths_ * num_paths_, true);
2376 to_reset_ = false;
2377 }
2378
2379 bool to_reset_ = true;
2380 int num_paths_ = 0;
2381 std::vector<int64_t> start_to_path_;
2382 std::vector<bool> is_path_pair_active_;
2383 };
2384
2385 std::unique_ptr<int[]> base_nodes_;
2386 std::unique_ptr<int[]> end_nodes_;
2387 std::unique_ptr<int[]> base_paths_;
2388 std::vector<int> node_path_starts_;
2389 std::vector<int> node_path_ends_;
2390 bool iterators_initialized_ = false;
2391#ifndef SWIG
2392 std::vector<BaseNodeIterators<PathOperator>> base_node_iterators_;
2393#endif // SWIG
2394 std::vector<int64_t> path_starts_;
2395 std::vector<int64_t> path_ends_;
2396 std::vector<bool> inactives_;
2397 bool just_started_;
2398 bool first_start_;
2399 int next_base_to_increment_;
2400 IterationParameters iteration_parameters_;
2401 bool optimal_paths_enabled_;
2402 std::vector<int> path_basis_;
2403 ActivePaths active_paths_;
2405#ifndef SWIG
2406 std::vector<std::vector<int64_t>> alternative_sets_;
2407#endif // SWIG
2408 std::vector<int> alternative_index_;
2409 std::vector<int64_t> active_in_alternative_set_;
2410 std::vector<int> sibling_alternative_;
2411
2412 friend class BaseNodeIterators<PathOperator>;
2413 friend class AlternativeNodeIterator;
2414 friend class NodeNeighborIterator;
2415};
2416
2417#ifndef SWIG
2419
2430 Solver* solver, const std::vector<IntVar*>& vars,
2431 const std::vector<IntVar*>& secondary_vars,
2432 std::function<int(int64_t)> start_empty_path_class,
2433 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2434 nullptr,
2435 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2436 nullptr);
2437
2439
2452
2454 Solver* solver, const std::vector<IntVar*>& vars,
2455 const std::vector<IntVar*>& secondary_vars,
2456 std::function<int(int64_t)> start_empty_path_class,
2457 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2458 nullptr,
2459 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2460 nullptr,
2461 int64_t chain_length = 1LL, bool single_path = false,
2462 const std::string& name = "Relocate");
2463
2465
2473
2475 Solver* solver, const std::vector<IntVar*>& vars,
2476 const std::vector<IntVar*>& secondary_vars,
2477 std::function<int(int64_t)> start_empty_path_class,
2478 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2479 nullptr,
2480 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2481 nullptr);
2482
2484
2494
2496 Solver* solver, const std::vector<IntVar*>& vars,
2497 const std::vector<IntVar*>& secondary_vars,
2498 std::function<int(int64_t)> start_empty_path_class,
2499 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2500 nullptr,
2501 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2502 nullptr);
2503
2505
2512
2514 Solver* solver, const std::vector<IntVar*>& vars,
2515 const std::vector<IntVar*>& secondary_vars,
2516 std::function<int(int64_t)> start_empty_path_class,
2517 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2518 nullptr,
2519 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2520 nullptr);
2521
2523
2530
2532 Solver* solver, const std::vector<IntVar*>& vars,
2533 const std::vector<IntVar*>& secondary_vars,
2534 std::function<int(int64_t)> start_empty_path_class);
2535
2536// ----- ExchangeAndMakeActive -----
2537
2538// ExchangeAndMakeActive exchanges two nodes and inserts an inactive node.
2539// Possible neighbors for paths 0 -> 2 -> 4, 1 -> 3 -> 6 and 5 inactive are:
2540// 0 -> 3 -> 4, 1 -> 5 -> 2 -> 6
2541// 0 -> 3 -> 5 -> 4, 1 -> 2 -> 6
2542// 0 -> 5 -> 3 -> 4, 1 -> 2 -> 6
2543// 0 -> 3 -> 4, 1 -> 2 -> 5 -> 6
2544//
2545// Warning this operator creates a very large neighborhood, with O(m*n^3)
2546// neighbors (n: number of active nodes, m: number of non active nodes).
2547// It should be used with only a small number of non active nodes.
2548// TODO(user): Add support for neighbors which would make this operator more
2549// usable.
2550
2552 Solver* solver, const std::vector<IntVar*>& vars,
2553 const std::vector<IntVar*>& secondary_vars,
2554 std::function<int(int64_t)> start_empty_path_class);
2555
2556// ----- ExchangePathEndsAndMakeActive -----
2557
2558// An operator which exchanges the first and last nodes of two paths and makes a
2559// node active.
2560// Possible neighbors for paths 0 -> 1 -> 2 -> 7, 6 -> 3 -> 4 -> 8
2561// and 5 inactive are:
2562// 0 -> 5 -> 3 -> 4 -> 7, 6 -> 1 -> 2 -> 8
2563// 0 -> 3 -> 4 -> 7, 6 -> 1 -> 5 -> 2 -> 8
2564// 0 -> 3 -> 4 -> 7, 6 -> 1 -> 2 -> 5 -> 8
2565// 0 -> 3 -> 5 -> 4 -> 7, 6 -> 1 -> 2 -> 8
2566// 0 -> 3 -> 4 -> 5 -> 7, 6 -> 1 -> 2 -> 8
2567//
2568// This neighborhood is an artificially reduced version of
2569// ExchangeAndMakeActiveOperator. It can still be used to opportunistically
2570// insert inactive nodes.
2571
2573 Solver* solver, const std::vector<IntVar*>& vars,
2574 const std::vector<IntVar*>& secondary_vars,
2575 std::function<int(int64_t)> start_empty_path_class);
2576
2578
2582
2584 Solver* solver, const std::vector<IntVar*>& vars,
2585 const std::vector<IntVar*>& secondary_vars,
2586 std::function<int(int64_t)> start_empty_path_class);
2587
2589
2595
2597 Solver* solver, const std::vector<IntVar*>& vars,
2598 const std::vector<IntVar*>& secondary_vars,
2599 std::function<int(int64_t)> start_empty_path_class);
2600
2602
2608
2610 Solver* solver, const std::vector<IntVar*>& vars,
2611 const std::vector<IntVar*>& secondary_vars,
2612 std::function<int(int64_t)> start_empty_path_class);
2613
2615
2622
2624 Solver* solver, const std::vector<IntVar*>& vars,
2625 const std::vector<IntVar*>& secondary_vars,
2626 std::function<int(int64_t)> start_empty_path_class);
2627
2629
2635
2637 Solver* solver, const std::vector<IntVar*>& vars,
2638 const std::vector<IntVar*>& secondary_vars,
2639 std::function<int(int64_t)> start_empty_path_class);
2640
2642
2644 Solver* solver, const std::vector<IntVar*>& vars,
2645 const std::vector<IntVar*>& secondary_vars,
2646 std::function<int(int64_t)> start_empty_path_class, int max_chain_size);
2647
2649
2660
2662 Solver* solver, const std::vector<IntVar*>& vars,
2663 const std::vector<IntVar*>& secondary_vars,
2664 std::function<int(int64_t)> start_empty_path_class);
2665
2667
2674
2676 const std::vector<IntVar*>& vars,
2677 const std::vector<IntVar*>& secondary_vars,
2678 Solver::IndexEvaluator3 evaluator,
2679 int chain_length);
2680
2688
2690 const std::vector<IntVar*>& vars,
2691 const std::vector<IntVar*>& secondary_vars,
2692 Solver::IndexEvaluator3 evaluator,
2693 int tsp_size);
2694
2696
2698 Solver* solver, const std::vector<IntVar*>& vars,
2699 const std::vector<IntVar*>& secondary_vars,
2700 const Solver::IndexEvaluator3& evaluator, bool topt);
2701
2703
2707
2709 const std::vector<IntVar*>& vars,
2710 const std::vector<IntVar*>& secondary_vars,
2711 int number_of_chunks, int chunk_size,
2712 bool unactive_fragments);
2713#endif // SWIG
2714
2715#if !defined(SWIG)
2716// After building a Directed Acyclic Graph, allows to generate sub-DAGs
2717// reachable from a node.
2718// Workflow:
2719// - Call AddArc() repeatedly to add arcs describing a DAG. Nodes are allocated
2720// on the user side, they must be nonnegative, and it is better but not
2721// mandatory for the set of nodes to be dense.
2722// - Call BuildGraph(). This precomputes all the information needed to make
2723// subsequent requests for sub-DAGs.
2724// - Call ComputeSortedSubDagArcs(node). This returns a view to arcs reachable
2725// from node, in topological order.
2726// All arcs must be added before calling BuildGraph(),
2727// and ComputeSortedSubDagArcs() can only be called after BuildGraph().
2728// If the arcs form a graph that has directed cycles,
2729// - in debug mode, BuildGraph() will crash.
2730// - otherwise, BuildGraph() will not crash, but ComputeSortedSubDagArcs()
2731// will only return a subset of arcs reachable by the given node.
2732class SubDagComputer {
2733 public:
2736 SubDagComputer() = default;
2737 // Adds an arc between node 'tail' and node 'head'. Nodes must be nonnegative.
2738 // Returns the index of the new arc, those are used to identify arcs when
2739 // calling ComputeSortedSubDagArcs().
2740 ArcId AddArc(NodeId tail, NodeId head) {
2741 DCHECK(!graph_was_built_);
2742 num_nodes_ = std::max(num_nodes_, std::max(tail.value(), head.value()) + 1);
2743 const ArcId arc_id(arcs_.size());
2744 arcs_.push_back({.tail = tail, .head = head, .arc_id = arc_id});
2745 return arc_id;
2746 }
2747 // Finishes the construction of the DAG. 'num_nodes' is the number of nodes
2748 // in the DAG and must be greater than all node indices passed to AddArc().
2749 void BuildGraph(int num_nodes);
2750 // Computes the arcs of the sub-DAG reachable from node returns a view of
2751 // those arcs in topological order.
2752 const std::vector<ArcId>& ComputeSortedSubDagArcs(NodeId node);
2753
2754 private:
2755 // Checks whether the underlying graph has a directed cycle.
2756 // Should be called after the graph has been built.
2757 bool HasDirectedCycle() const;
2758
2759 struct Arc {
2760 NodeId tail;
2761 NodeId head;
2762 ArcId arc_id;
2763 bool operator<(const Arc& other) const {
2764 return std::tie(tail, arc_id) < std::tie(other.tail, other.arc_id);
2765 }
2766 };
2767 int num_nodes_ = 0;
2768 std::vector<Arc> arcs_;
2769 // Initialized by BuildGraph(), after which the outgoing arcs of node n are
2770 // the range from arcs_[arcs_of_node_[n]] included to
2771 // arcs_[arcs_of_node_[n+1]] excluded.
2773 // Must be false before BuildGraph() is called, true afterwards.
2774 bool graph_was_built_ = false;
2775 // Used by ComputeSortedSubDagArcs.
2777 // Used by ComputeSortedSubDagArcs.
2778 std::vector<NodeId> nodes_to_visit_;
2779 // Used as output, set up as a member to allow reuse.
2780 std::vector<ArcId> sorted_arcs_;
2781};
2782
2783// A LocalSearchState is a container for variables with domains that can be
2784// relaxed and tightened, saved and restored. It represents the solution state
2785// of a local search engine, and allows it to go from solution to solution by
2786// relaxing some variables to form a new subproblem, then tightening those
2787// variables to move to a new solution representation. That state may be saved
2788// to an internal copy, or reverted to the last saved internal copy.
2789// Relaxing a variable returns its bounds to their initial state.
2790// Tightening a variable's bounds may make its min larger than its max,
2791// in that case, the tightening function will return false, and the state will
2792// be marked as invalid. No other operations than Revert() can be called on an
2793// invalid state: in particular, an invalid state cannot be saved.
2794class LocalSearchState {
2795 public:
2796 class Variable;
2797 DEFINE_STRONG_INT_TYPE(VariableDomainId, int);
2798 DEFINE_STRONG_INT_TYPE(ConstraintId, int);
2799 // Adds a variable domain to this state, returns a handler to the new domain.
2800 VariableDomainId AddVariableDomain(int64_t relaxed_min, int64_t relaxed_max);
2801 // Relaxes the domain, returns false iff the domain was already relaxed.
2802 bool RelaxVariableDomain(VariableDomainId domain_id);
2803 bool TightenVariableDomainMin(VariableDomainId domain_id, int64_t value);
2804 bool TightenVariableDomainMax(VariableDomainId domain_id, int64_t value);
2805 int64_t VariableDomainMin(VariableDomainId domain_id) const;
2806 int64_t VariableDomainMax(VariableDomainId domain_id) const;
2807 void ChangeRelaxedVariableDomain(VariableDomainId domain_id, int64_t min,
2808 int64_t max);
2810 // Propagation of all events.
2811 void PropagateRelax(VariableDomainId domain_id);
2813 // Makes a variable, an object with restricted operations on the underlying
2814 // domain identified by domain_id: only Relax, Tighten and Min/Max read
2815 // operations are available.
2817 // Makes a variable from an interval without going through a domain_id.
2818 // Can be used when no direct manipulation of the domain is needed.
2819 Variable MakeVariableWithRelaxedDomain(int64_t min, int64_t max);
2820 // Makes a variable with no state, this is meant as a placeholder.
2821 static Variable DummyVariable();
2822 void Commit();
2823 void Revert();
2824 bool StateIsFeasible() const {
2825 return state_domains_are_all_nonempty_ && num_committed_empty_domains_ == 0;
2826 }
2827 // Adds a constraint that output = input_offset + sum_i weight_i * input_i.
2828 void AddWeightedSumConstraint(
2829 const std::vector<VariableDomainId>& input_domain_ids,
2830 const std::vector<int64_t>& input_weights, int64_t input_offset,
2831 VariableDomainId output_domain_id);
2832 // Precomputes which domain change triggers which constraint(s).
2833 // Should be run after adding all constraints, before any Relax()/Tighten().
2834 void CompileConstraints();
2835
2836 private:
2837 // VariableDomains implement the domain of Variables.
2838 // Those are trailed, meaning they are saved on their first modification,
2839 // and can be reverted or committed in O(1) per modification.
2840 struct VariableDomain {
2841 int64_t min;
2842 int64_t max;
2843 };
2844 bool IntersectionIsEmpty(const VariableDomain& d1,
2845 const VariableDomain& d2) const {
2846 return d1.max < d2.min || d2.max < d1.min;
2847 }
2850 struct TrailedVariableDomain {
2851 VariableDomain committed_domain;
2852 VariableDomainId domain_id;
2853 };
2854 std::vector<TrailedVariableDomain> trailed_domains_;
2855 util_intops::StrongVector<VariableDomainId, bool> domain_is_trailed_;
2856 // True iff all domains have their min <= max.
2857 bool state_domains_are_all_nonempty_ = true;
2858 bool state_has_relaxed_domains_ = false;
2859 // Number of domains d for which the intersection of
2860 // current_domains_[d] and relaxed_domains_[d] is empty.
2861 int num_committed_empty_domains_ = 0;
2862 int trailed_num_committed_empty_domains_ = 0;
2863
2864 // Constraints may be trailed too, they decide how to track their internal
2865 // structure.
2866 class Constraint;
2867 void TrailConstraint(Constraint* constraint) {
2868 trailed_constraints_.push_back(constraint);
2869 }
2870 std::vector<Constraint*> trailed_constraints_;
2871
2872 // Stores domain-constraint dependencies, allows to generate topological
2873 // orderings of dependency arcs reachable from nodes.
2874 class DependencyGraph {
2875 public:
2876 DependencyGraph() {}
2877 // There are two kinds of domain-constraint dependencies:
2878 // - domain -> constraint when the domain is an input to the constraint.
2879 // Then the label is the index of the domain in the input tuple.
2880 // - constraint -> domain when the domain is the output of the constraint.
2881 // Then, the label is -1.
2882 struct Dependency {
2883 VariableDomainId domain_id;
2884 int input_index;
2885 ConstraintId constraint_id;
2886 };
2887 // Adds all dependencies domains[i] -> constraint labelled by i.
2888 void AddDomainsConstraintDependencies(
2889 const std::vector<VariableDomainId>& domain_ids,
2890 ConstraintId constraint_id);
2891 // Adds a dependency domain -> constraint labelled by -1.
2892 void AddConstraintDomainDependency(ConstraintId constraint_id,
2893 VariableDomainId domain_id);
2894 // After all dependencies have been added,
2895 // builds the DAG representation that allows to compute sorted dependencies.
2896 void BuildDependencyDAG(int num_domains);
2897 // Returns a view on the list of arc dependencies reachable by given domain,
2898 // in some topological order of the overall DAG. Modifying the graph or
2899 // calling ComputeSortedDependencies() again invalidates the view.
2900 const std::vector<Dependency>& ComputeSortedDependencies(
2902
2903 private:
2904 using ArcId = SubDagComputer::ArcId;
2905 using NodeId = SubDagComputer::NodeId;
2906 // Returns dag_node_of_domain_[domain_id] if already defined,
2907 // or makes a node for domain_id, possibly extending dag_node_of_domain_.
2908 NodeId GetOrCreateNodeOfDomainId(VariableDomainId domain_id);
2909 // Returns dag_node_of_constraint_[constraint_id] if already defined,
2910 // or makes a node for constraint_id, possibly extending
2911 // dag_node_of_constraint_.
2912 NodeId GetOrCreateNodeOfConstraintId(ConstraintId constraint_id);
2913 // Structure of the expression DAG, used to buffer propagation storage.
2914 SubDagComputer dag_;
2915 // Maps arcs of dag_ to domain/constraint dependencies.
2916 util_intops::StrongVector<ArcId, Dependency> dependency_of_dag_arc_;
2917 // Maps domain ids to dag_ nodes.
2919 // Maps constraint ids to dag_ nodes.
2921 // Number of nodes currently allocated in dag_.
2922 // Reserve node 0 as a default dummy node with no dependencies.
2923 int num_dag_nodes_ = 1;
2924 // Used as reusable output of ComputeSortedDependencies().
2925 std::vector<Dependency> sorted_dependencies_;
2926 };
2927 DependencyGraph dependency_graph_;
2928
2929 // Propagation order storage: each domain change triggers constraints.
2930 // Each trigger tells a constraint that a domain changed, and identifies
2931 // the domain by the index in the list of the constraint's inputs.
2932 struct Trigger {
2933 Constraint* constraint;
2934 int input_index;
2935 };
2936 // Triggers of all constraints, concatenated.
2937 // The triggers of domain i are stored from triggers_of_domain_[i]
2938 // to triggers_of_domain_[i+1] excluded.
2939 std::vector<Trigger> triggers_;
2941
2942 // Constraints are used to form expressions that make up the objective.
2943 // Constraints are directed: they have inputs and an output, moreover the
2944 // constraint-domain graph must not have directed cycles.
2945 class Constraint {
2946 public:
2947 virtual ~Constraint() = default;
2948 virtual LocalSearchState::VariableDomain Propagate(int input_index) = 0;
2949 virtual VariableDomainId Output() const = 0;
2950 virtual void Commit() = 0;
2951 virtual void Revert() = 0;
2952 };
2953 // WeightedSum constraints enforces the equation:
2954 // output = offset + sum_i input_weights[i] * input_domain_ids[i]
2955 class WeightedSum final : public Constraint {
2956 public:
2957 WeightedSum(LocalSearchState* state,
2958 const std::vector<VariableDomainId>& input_domain_ids,
2959 const std::vector<int64_t>& input_weights, int64_t input_offset,
2960 VariableDomainId output);
2961 ~WeightedSum() override = default;
2962 LocalSearchState::VariableDomain Propagate(int input_index) override;
2963 void Commit() override;
2964 void Revert() override;
2965 VariableDomainId Output() const override { return output_; }
2966
2967 private:
2968 // Weighted variable holds a variable's domain, an associated weight,
2969 // and the variable's last known min and max.
2970 struct WeightedVariable {
2971 int64_t min;
2972 int64_t max;
2973 int64_t committed_min;
2974 int64_t committed_max;
2975 int64_t weight;
2976 VariableDomainId domain;
2977 bool is_trailed;
2978 void Commit() {
2979 committed_min = min;
2980 committed_max = max;
2981 is_trailed = false;
2982 }
2983 void Revert() {
2984 min = committed_min;
2985 max = committed_max;
2986 is_trailed = false;
2987 }
2988 };
2989 std::vector<WeightedVariable> inputs_;
2990 std::vector<WeightedVariable*> trailed_inputs_;
2991 // Invariants held by this constraint to allow O(1) propagation.
2992 struct Invariants {
2993 // Number of inputs_[i].min equal to kint64min.
2994 int64_t num_neg_inf;
2995 // Sum of inputs_[i].min that are different from kint64min.
2996 int64_t wsum_mins;
2997 // Number of inputs_[i].max equal to kint64max.
2998 int64_t num_pos_inf;
2999 // Sum of inputs_[i].max that are different from kint64max.
3000 int64_t wsum_maxs;
3001 };
3002 Invariants invariants_;
3003 Invariants committed_invariants_;
3004
3005 const VariableDomainId output_;
3006 LocalSearchState* const state_;
3007 bool constraint_is_trailed_ = false;
3008 };
3009 // Used to identify constraints and hold ownership.
3010 util_intops::StrongVector<ConstraintId, std::unique_ptr<Constraint>>
3011 constraints_;
3012};
3013
3014// A LocalSearchState Variable can only be created by a LocalSearchState,
3015// then it is meant to be passed by copy. If at some point the duplication of
3016// LocalSearchState pointers is too expensive, we could switch to index only,
3017// and the user would have to know the relevant state. The present setup allows
3018// to ensure that variable users will not misuse the state.
3019class LocalSearchState::Variable {
3020 public:
3021 Variable() : state_(nullptr), domain_id_(VariableDomainId(-1)) {}
3022 int64_t Min() const {
3023 DCHECK(Exists());
3024 return state_->VariableDomainMin(domain_id_);
3025 }
3026 int64_t Max() const {
3027 DCHECK(Exists());
3028 return state_->VariableDomainMax(domain_id_);
3029 }
3030 // Sets variable's minimum to max(Min(), new_min) and propagates the change.
3031 // Returns true iff the variable domain is nonempty and propagation succeeded.
3032 bool SetMin(int64_t new_min) const {
3033 if (!Exists()) return true;
3034 return state_->TightenVariableDomainMin(domain_id_, new_min) &&
3035 state_->PropagateTighten(domain_id_);
3037 // Sets variable's maximum to min(Max(), new_max) and propagates the change.
3038 // Returns true iff the variable domain is nonempty and propagation succeeded.
3039 bool SetMax(int64_t new_max) const {
3040 if (!Exists()) return true;
3041 return state_->TightenVariableDomainMax(domain_id_, new_max) &&
3042 state_->PropagateTighten(domain_id_);
3043 }
3044 void Relax() const {
3045 if (state_ == nullptr) return;
3046 if (state_->RelaxVariableDomain(domain_id_)) {
3047 state_->PropagateRelax(domain_id_);
3048 }
3049 }
3050 bool Exists() const { return state_ != nullptr; }
3051
3052 private:
3053 // Only LocalSearchState can construct LocalSearchVariables.
3054 friend class LocalSearchState;
3055
3056 Variable(LocalSearchState* state, VariableDomainId domain_id)
3057 : state_(state), domain_id_(domain_id) {}
3058
3060 VariableDomainId domain_id_;
3061};
3062#endif // !defined(SWIG)
3063
3065
3077
3080class LocalSearchFilter : public BaseObject {
3081 public:
3084 virtual void Relax(const Assignment*, const Assignment*) {}
3086 virtual void Commit(const Assignment*, const Assignment*) {}
3087
3095 /// but the delta (a,0) will be accepted.
3096 /// TODO(user): Remove arguments when there are no more need for those.
3097 virtual bool Accept(const Assignment* delta, const Assignment* deltadelta,
3098 int64_t objective_min, int64_t objective_max) = 0;
3099 virtual bool IsIncremental() const { return false; }
3100
3106 virtual void Synchronize(const Assignment* assignment,
3107 const Assignment* delta) = 0;
3109 virtual void Revert() {}
3110
3112 virtual void Reset() {}
3113
3115 virtual int64_t GetSynchronizedObjectiveValue() const { return 0LL; }
3117 // If the last Accept() call returned false, returns an undefined value.
3118 virtual int64_t GetAcceptedObjectiveValue() const { return 0LL; }
3119};
3120
3125 public:
3126 // This class is responsible for calling filters methods in a correct order.
3127 // For now, an order is specified explicitly by the user.
3128 enum FilterEventType { kAccept, kRelax };
3129 struct FilterEvent {
3131 FilterEventType event_type;
3132 int priority;
3134
3135 std::string DebugString() const override {
3136 return "LocalSearchFilterManager";
3137 }
3138 // Builds a manager that calls filter methods ordered by increasing priority.
3139 // Note that some filters might appear only once, if their Relax() or Accept()
3140 // are trivial.
3141 explicit LocalSearchFilterManager(std::vector<FilterEvent> filter_events);
3142 // Builds a manager that calls filter methods using the following ordering:
3143 // first Relax() in vector order, then Accept() in vector order.
3144 explicit LocalSearchFilterManager(std::vector<LocalSearchFilter*> filters);
3146 // Calls Revert() of filters, in reverse order of Relax events.
3147 void Revert();
3149
3150 /// The monitor has its Begin/EndFiltering events triggered.
3151 bool Accept(LocalSearchMonitor* monitor, const Assignment* delta,
3152 const Assignment* deltadelta, int64_t objective_min,
3153 int64_t objective_max);
3155 void Synchronize(const Assignment* assignment, const Assignment* delta);
3156 int64_t GetSynchronizedObjectiveValue() const { return synchronized_value_; }
3157 int64_t GetAcceptedObjectiveValue() const { return accepted_value_; }
3158
3159 private:
3160 // Finds the last event (incremental -itself- or not) with the same priority
3161 // as the last incremental event.
3162 void FindIncrementalEventEnd();
3163
3164 std::vector<FilterEvent> events_;
3165 int last_event_called_ = -1;
3166 // If a filter is incremental, its Relax() and Accept() must be called for
3167 // every candidate, even if the Accept() of a prior filter rejected it.
3168 // To ensure that those incremental filters have consistent inputs, all
3169 // intermediate events with Relax() must also be called.
3170 int incremental_events_end_ = 0;
3171 int64_t synchronized_value_;
3172 int64_t accepted_value_;
3173};
3174
3176 public:
3177 explicit IntVarLocalSearchFilter(const std::vector<IntVar*>& vars);
3178 ~IntVarLocalSearchFilter() override;
3181 void Synchronize(const Assignment* assignment,
3182 const Assignment* delta) override;
3183
3184 bool FindIndex(IntVar* const var, int64_t* index) const {
3185 DCHECK(index != nullptr);
3186 const int var_index = var->index();
3187 *index = (var_index < var_index_to_index_.size())
3188 ? var_index_to_index_[var_index]
3189 : kUnassigned;
3190 return *index != kUnassigned;
3191 }
3192
3194 void AddVars(const std::vector<IntVar*>& vars);
3195 int Size() const { return vars_.size(); }
3196 IntVar* Var(int index) const { return vars_[index]; }
3197 int64_t Value(int index) const {
3198 DCHECK(IsVarSynced(index));
3199 return values_[index];
3200 }
3201 bool IsVarSynced(int index) const { return var_synced_[index]; }
3202
3203 protected:
3204 virtual void OnSynchronize(const Assignment*) {}
3205 void SynchronizeOnAssignment(const Assignment* assignment);
3206
3207 private:
3208 std::vector<IntVar*> vars_;
3209 std::vector<int64_t> values_;
3210 std::vector<bool> var_synced_;
3211 std::vector<int> var_index_to_index_;
3212 static const int kUnassigned;
3213};
3214
3215class PropagationMonitor : public SearchMonitor {
3216 public:
3217 explicit PropagationMonitor(Solver* solver);
3218 ~PropagationMonitor() override;
3219 std::string DebugString() const override { return "PropagationMonitor"; }
3220
3222 virtual void BeginConstraintInitialPropagation(Constraint* constraint) = 0;
3223 virtual void EndConstraintInitialPropagation(Constraint* constraint) = 0;
3224 virtual void BeginNestedConstraintInitialPropagation(Constraint* parent,
3225 Constraint* nested) = 0;
3226 virtual void EndNestedConstraintInitialPropagation(Constraint* parent,
3227 Constraint* nested) = 0;
3228 virtual void RegisterDemon(Demon* demon) = 0;
3229 virtual void BeginDemonRun(Demon* demon) = 0;
3230 virtual void EndDemonRun(Demon* demon) = 0;
3231 virtual void StartProcessingIntegerVariable(IntVar* var) = 0;
3232 virtual void EndProcessingIntegerVariable(IntVar* var) = 0;
3233 virtual void PushContext(const std::string& context) = 0;
3234 virtual void PopContext() = 0;
3236 virtual void SetMin(IntExpr* expr, int64_t new_min) = 0;
3237 virtual void SetMax(IntExpr* expr, int64_t new_max) = 0;
3238 virtual void SetRange(IntExpr* expr, int64_t new_min, int64_t new_max) = 0;
3240 virtual void SetMin(IntVar* var, int64_t new_min) = 0;
3241 virtual void SetMax(IntVar* var, int64_t new_max) = 0;
3242 virtual void SetRange(IntVar* var, int64_t new_min, int64_t new_max) = 0;
3243 virtual void RemoveValue(IntVar* var, int64_t value) = 0;
3244 virtual void SetValue(IntVar* var, int64_t value) = 0;
3245 virtual void RemoveInterval(IntVar* var, int64_t imin, int64_t imax) = 0;
3246 virtual void SetValues(IntVar* var, const std::vector<int64_t>& values) = 0;
3247 virtual void RemoveValues(IntVar* var,
3248 const std::vector<int64_t>& values) = 0;
3250 virtual void SetStartMin(IntervalVar* var, int64_t new_min) = 0;
3251 virtual void SetStartMax(IntervalVar* var, int64_t new_max) = 0;
3252 virtual void SetStartRange(IntervalVar* var, int64_t new_min,
3253 int64_t new_max) = 0;
3254 virtual void SetEndMin(IntervalVar* var, int64_t new_min) = 0;
3255 virtual void SetEndMax(IntervalVar* var, int64_t new_max) = 0;
3256 virtual void SetEndRange(IntervalVar* var, int64_t new_min,
3257 int64_t new_max) = 0;
3258 virtual void SetDurationMin(IntervalVar* var, int64_t new_min) = 0;
3259 virtual void SetDurationMax(IntervalVar* var, int64_t new_max) = 0;
3260 virtual void SetDurationRange(IntervalVar* var, int64_t new_min,
3261 int64_t new_max) = 0;
3262 virtual void SetPerformed(IntervalVar* var, bool value) = 0;
3264 virtual void RankFirst(SequenceVar* var, int index) = 0;
3265 virtual void RankNotFirst(SequenceVar* var, int index) = 0;
3266 virtual void RankLast(SequenceVar* var, int index) = 0;
3267 virtual void RankNotLast(SequenceVar* var, int index) = 0;
3268 virtual void RankSequence(SequenceVar* var,
3269 const std::vector<int>& rank_first,
3270 const std::vector<int>& rank_last,
3271 const std::vector<int>& unperformed) = 0;
3273 void Install() override;
3276class LocalSearchMonitor : public SearchMonitor {
3277 // TODO(user): Add monitoring of local search filters.
3278 public:
3281 std::string DebugString() const override { return "LocalSearchMonitor"; }
3284 virtual void BeginOperatorStart() = 0;
3285 virtual void EndOperatorStart() = 0;
3286 virtual void BeginMakeNextNeighbor(const LocalSearchOperator* op) = 0;
3287 virtual void EndMakeNextNeighbor(const LocalSearchOperator* op,
3288 bool neighbor_found, const Assignment* delta,
3289 const Assignment* deltadelta) = 0;
3290 virtual void BeginFilterNeighbor(const LocalSearchOperator* op) = 0;
3292 bool neighbor_found) = 0;
3293 virtual void BeginAcceptNeighbor(const LocalSearchOperator* op) = 0;
3294 virtual void EndAcceptNeighbor(const LocalSearchOperator* op,
3295 bool neighbor_found) = 0;
3296 virtual void BeginFiltering(const LocalSearchFilter* filter) = 0;
3297 virtual void EndFiltering(const LocalSearchFilter* filter, bool reject) = 0;
3298
3299 virtual bool IsActive() const = 0;
3302 void Install() override;
3303};
3304
3305class OR_DLL BooleanVar : public IntVar {
3306 public:
3307 static const int kUnboundBooleanVarValue;
3309 explicit BooleanVar(Solver* const s, const std::string& name = "")
3310 : IntVar(s, name), value_(kUnboundBooleanVarValue) {}
3312 ~BooleanVar() override {}
3313
3314 int64_t Min() const override { return (value_ == 1); }
3315 void SetMin(int64_t m) override;
3316 int64_t Max() const override { return (value_ != 0); }
3317 void SetMax(int64_t m) override;
3318 void SetRange(int64_t mi, int64_t ma) override;
3319 bool Bound() const override { return (value_ != kUnboundBooleanVarValue); }
3320 int64_t Value() const override {
3321 CHECK_NE(value_, kUnboundBooleanVarValue) << "variable is not bound";
3322 return value_;
3323 }
3324 void RemoveValue(int64_t v) override;
3325 void RemoveInterval(int64_t l, int64_t u) override;
3326 void WhenBound(Demon* d) override;
3327 void WhenRange(Demon* d) override { WhenBound(d); }
3328 void WhenDomain(Demon* d) override { WhenBound(d); }
3329 uint64_t Size() const override;
3330 bool Contains(int64_t v) const override;
3331 IntVarIterator* MakeHoleIterator(bool reversible) const override;
3332 IntVarIterator* MakeDomainIterator(bool reversible) const override;
3333 std::string DebugString() const override;
3334 int VarType() const override { return BOOLEAN_VAR; }
3336 IntVar* IsEqual(int64_t constant) override;
3337 IntVar* IsDifferent(int64_t constant) override;
3338 IntVar* IsGreaterOrEqual(int64_t constant) override;
3339 IntVar* IsLessOrEqual(int64_t constant) override;
3340
3341 virtual void RestoreValue() = 0;
3342 std::string BaseName() const override { return "BooleanVar"; }
3344 int RawValue() const { return value_; }
3345
3346 protected:
3347 int value_;
3348 SimpleRevFIFO<Demon*> bound_demons_;
3350};
3351
3352class SymmetryManager;
3353
3358 public:
3360 : symmetry_manager_(nullptr), index_in_symmetry_manager_(-1) {}
3361 ~SymmetryBreaker() override {}
3363 void AddIntegerVariableEqualValueClause(IntVar* var, int64_t value);
3364 void AddIntegerVariableGreaterOrEqualValueClause(IntVar* var, int64_t value);
3365 void AddIntegerVariableLessOrEqualValueClause(IntVar* var, int64_t value);
3366
3367 private:
3368 friend class SymmetryManager;
3369 void set_symmetry_manager_and_index(SymmetryManager* manager, int index) {
3370 CHECK(symmetry_manager_ == nullptr);
3371 CHECK_EQ(-1, index_in_symmetry_manager_);
3372 symmetry_manager_ = manager;
3373 index_in_symmetry_manager_ = index;
3375 SymmetryManager* symmetry_manager() const { return symmetry_manager_; }
3376 int index_in_symmetry_manager() const { return index_in_symmetry_manager_; }
3377
3378 SymmetryManager* symmetry_manager_;
3380 int index_in_symmetry_manager_;
3381};
3382
3385class SearchLog : public SearchMonitor {
3386 public:
3387 SearchLog(Solver* solver, std::vector<IntVar*> vars, std::string vars_name,
3388 std::vector<double> scaling_factors, std::vector<double> offsets,
3389 std::function<std::string()> display_callback,
3390 bool display_on_new_solutions_only, int period);
3391 ~SearchLog() override;
3392 void EnterSearch() override;
3393 void ExitSearch() override;
3394 bool AtSolution() override;
3395 void BeginFail() override;
3396 void NoMoreSolutions() override;
3397 void AcceptUncheckedNeighbor() override;
3398 void ApplyDecision(Decision* decision) override;
3399 void RefuteDecision(Decision* decision) override;
3401 void Maintain();
3402 void BeginInitialPropagation() override;
3403 void EndInitialPropagation() override;
3404 std::string DebugString() const override;
3405
3406 protected:
3407 /* Bottleneck function used for all UI related output. */
3408 virtual void OutputLine(const std::string& line);
3409
3410 private:
3411 static std::string MemoryUsage();
3412
3413 const int period_;
3414 std::unique_ptr<WallTimer> timer_;
3415 const std::vector<IntVar*> vars_;
3416 const std::string vars_name_;
3417 const std::vector<double> scaling_factors_;
3418 const std::vector<double> offsets_;
3419 std::function<std::string()> display_callback_;
3420 const bool display_on_new_solutions_only_;
3421 int nsol_;
3422 absl::Duration tick_;
3423 std::vector<int64_t> objective_min_;
3424 std::vector<int64_t> objective_max_;
3425 std::vector<int64_t> last_objective_value_;
3426 absl::Duration last_objective_timestamp_;
3427 int min_right_depth_;
3428 int max_depth_;
3429 int sliding_min_depth_;
3430 int sliding_max_depth_;
3431 int neighbors_offset_ = 0;
3432};
3433
3438class ModelCache {
3439 public:
3440 enum VoidConstraintType {
3441 VOID_FALSE_CONSTRAINT = 0,
3442 VOID_TRUE_CONSTRAINT,
3443 VOID_CONSTRAINT_MAX,
3444 };
3445
3446 enum VarConstantConstraintType {
3447 VAR_CONSTANT_EQUALITY = 0,
3448 VAR_CONSTANT_GREATER_OR_EQUAL,
3449 VAR_CONSTANT_LESS_OR_EQUAL,
3450 VAR_CONSTANT_NON_EQUALITY,
3451 VAR_CONSTANT_CONSTRAINT_MAX,
3452 };
3468
3490 enum ExprExprConstantExpressionType {
3508 enum VarConstantConstantExpressionType {
3509 VAR_CONSTANT_CONSTANT_SEMI_CONTINUOUS = 0,
3536 virtual ~ModelCache();
3537
3538 virtual void Clear() = 0;
3543
3544 virtual void InsertVoidConstraint(Constraint* ct,
3549 IntVar* var, int64_t value, VarConstantConstraintType type) const = 0;
3550
3551 virtual void InsertVarConstantConstraint(Constraint* ct, IntVar* var,
3552 int64_t value,
3554
3556
3558 IntVar* var, int64_t value1, int64_t value2,
3560
3562 Constraint* ct, IntVar* var, int64_t value1, int64_t value2,
3564
3568 IntExpr* expr1, IntExpr* expr2, ExprExprConstraintType type) const = 0;
3569
3570 virtual void InsertExprExprConstraint(Constraint* ct, IntExpr* expr1,
3571 IntExpr* expr2,
3573
3575
3577 ExprExpressionType type) const = 0;
3578
3579 virtual void InsertExprExpression(IntExpr* expression, IntExpr* expr,
3580 ExprExpressionType type) = 0;
3581
3583
3585 IntExpr* expr, int64_t value, ExprConstantExpressionType type) const = 0;
3586
3587 virtual void InsertExprConstantExpression(
3588 IntExpr* expression, IntExpr* var, int64_t value,
3590
3592
3594 IntExpr* var1, IntExpr* var2, ExprExprExpressionType type) const = 0;
3595
3596 virtual void InsertExprExprExpression(IntExpr* expression, IntExpr* var1,
3597 IntExpr* var2,
3598 ExprExprExpressionType type) = 0;
3601
3603 IntExpr* var1, IntExpr* var2, int64_t constant,
3604 ExprExprConstantExpressionType type) const = 0;
3605
3607 IntExpr* expression, IntExpr* var1, IntExpr* var2, int64_t constant,
3609
3613 IntVar* var, int64_t value1, int64_t value2,
3614 VarConstantConstantExpressionType type) const = 0;
3615
3617 IntExpr* expression, IntVar* var, int64_t value1, int64_t value2,
3619
3623 IntVar* var, const std::vector<int64_t>& values,
3624 VarConstantArrayExpressionType type) const = 0;
3625
3627 IntExpr* expression, IntVar* var, const std::vector<int64_t>& values,
3629
3633 const std::vector<IntVar*>& vars, VarArrayExpressionType type) const = 0;
3634
3635 virtual void InsertVarArrayExpression(IntExpr* expression,
3636 const std::vector<IntVar*>& vars,
3638
3640
3642 const std::vector<IntVar*>& vars, const std::vector<int64_t>& values,
3644
3646 IntExpr* expression, const std::vector<IntVar*>& var,
3647 const std::vector<int64_t>& values,
3649
3651
3653 const std::vector<IntVar*>& vars, int64_t value,
3654 VarArrayConstantExpressionType type) const = 0;
3655
3657 IntExpr* expression, const std::vector<IntVar*>& var, int64_t value,
3659
3660 Solver* solver() const;
3661
3662 private:
3663 Solver* const solver_;
3664};
3665
3667#if !defined(SWIG)
3668class ArgumentHolder {
3669 public:
3671 const std::string& TypeName() const;
3672 void SetTypeName(const std::string& type_name);
3673
3675 void SetIntegerArgument(const std::string& arg_name, int64_t value);
3676 void SetIntegerArrayArgument(const std::string& arg_name,
3677 const std::vector<int64_t>& values);
3678 void SetIntegerMatrixArgument(const std::string& arg_name,
3679 const IntTupleSet& values);
3680 void SetIntegerExpressionArgument(const std::string& arg_name, IntExpr* expr);
3681 void SetIntegerVariableArrayArgument(const std::string& arg_name,
3682 const std::vector<IntVar*>& vars);
3683 void SetIntervalArgument(const std::string& arg_name, IntervalVar* var);
3684 void SetIntervalArrayArgument(const std::string& arg_name,
3685 const std::vector<IntervalVar*>& vars);
3686 void SetSequenceArgument(const std::string& arg_name, SequenceVar* var);
3687 void SetSequenceArrayArgument(const std::string& arg_name,
3688 const std::vector<SequenceVar*>& vars);
3689
3691 bool HasIntegerExpressionArgument(const std::string& arg_name) const;
3692 bool HasIntegerVariableArrayArgument(const std::string& arg_name) const;
3693
3695 int64_t FindIntegerArgumentWithDefault(const std::string& arg_name,
3696 int64_t def) const;
3697 int64_t FindIntegerArgumentOrDie(const std::string& arg_name) const;
3698 const std::vector<int64_t>& FindIntegerArrayArgumentOrDie(
3699 const std::string& arg_name) const;
3701 const std::string& arg_name) const;
3702
3704 const std::string& arg_name) const;
3705 const std::vector<IntVar*>& FindIntegerVariableArrayArgumentOrDie(
3706 const std::string& arg_name) const;
3707
3708 private:
3709 std::string type_name_;
3710 absl::flat_hash_map<std::string, int64_t> integer_argument_;
3711 absl::flat_hash_map<std::string, std::vector<int64_t>>
3712 integer_array_argument_;
3713 absl::flat_hash_map<std::string, IntTupleSet> matrix_argument_;
3714 absl::flat_hash_map<std::string, IntExpr*> integer_expression_argument_;
3715 absl::flat_hash_map<std::string, IntervalVar*> interval_argument_;
3716 absl::flat_hash_map<std::string, SequenceVar*> sequence_argument_;
3717 absl::flat_hash_map<std::string, std::vector<IntVar*>>
3718 integer_variable_array_argument_;
3719 absl::flat_hash_map<std::string, std::vector<IntervalVar*>>
3720 interval_array_argument_;
3721 absl::flat_hash_map<std::string, std::vector<SequenceVar*>>
3722 sequence_array_argument_;
3723};
3724
3726class ModelParser : public ModelVisitor {
3727 public:
3728 ModelParser();
3729
3730 ~ModelParser() override;
3731
3733 void BeginVisitModel(const std::string& solver_name) override;
3734 void EndVisitModel(const std::string& solver_name) override;
3735 void BeginVisitConstraint(const std::string& type_name,
3736 const Constraint* constraint) override;
3737 void EndVisitConstraint(const std::string& type_name,
3738 const Constraint* constraint) override;
3739 void BeginVisitIntegerExpression(const std::string& type_name,
3740 const IntExpr* expr) override;
3741 void EndVisitIntegerExpression(const std::string& type_name,
3742 const IntExpr* expr) override;
3743 void VisitIntegerVariable(const IntVar* variable, IntExpr* delegate) override;
3744 void VisitIntegerVariable(const IntVar* variable,
3745 const std::string& operation, int64_t value,
3746 IntVar* delegate) override;
3747 void VisitIntervalVariable(const IntervalVar* variable,
3748 const std::string& operation, int64_t value,
3749 IntervalVar* delegate) override;
3750 void VisitSequenceVariable(const SequenceVar* variable) override;
3752 void VisitIntegerArgument(const std::string& arg_name,
3753 int64_t value) override;
3754 void VisitIntegerArrayArgument(const std::string& arg_name,
3755 const std::vector<int64_t>& values) override;
3756 void VisitIntegerMatrixArgument(const std::string& arg_name,
3757 const IntTupleSet& values) override;
3759 void VisitIntegerExpressionArgument(const std::string& arg_name,
3760 IntExpr* argument) override;
3762 const std::string& arg_name,
3763 const std::vector<IntVar*>& arguments) override;
3765 void VisitIntervalArgument(const std::string& arg_name,
3766 IntervalVar* argument) override;
3768 const std::string& arg_name,
3769 const std::vector<IntervalVar*>& arguments) override;
3771 void VisitSequenceArgument(const std::string& arg_name,
3772 SequenceVar* argument) override;
3774 const std::string& arg_name,
3775 const std::vector<SequenceVar*>& arguments) override;
3776
3777 protected:
3778 void PushArgumentHolder();
3779 void PopArgumentHolder();
3780 ArgumentHolder* Top() const;
3781
3782 private:
3783 std::vector<ArgumentHolder*> holders_;
3784};
3785
3786template <class T>
3787class ArrayWithOffset : public BaseObject {
3788 public:
3789 ArrayWithOffset(int64_t index_min, int64_t index_max)
3790 : index_min_(index_min),
3791 index_max_(index_max),
3792 values_(new T[index_max - index_min + 1]) {
3793 DCHECK_LE(index_min, index_max);
3794 }
3795
3796 ~ArrayWithOffset() override {}
3797
3798 virtual T Evaluate(int64_t index) const {
3799 DCHECK_GE(index, index_min_);
3800 DCHECK_LE(index, index_max_);
3801 return values_[index - index_min_];
3803
3804 void SetValue(int64_t index, T value) {
3805 DCHECK_GE(index, index_min_);
3806 DCHECK_LE(index, index_max_);
3807 values_[index - index_min_] = value;
3808 }
3809
3810 std::string DebugString() const override { return "ArrayWithOffset"; }
3812 private:
3813 const int64_t index_min_;
3814 const int64_t index_max_;
3815 std::unique_ptr<T[]> values_;
3816};
3817#endif // SWIG
3818
3819/// This class is a reversible growing array. In can grow in both
3820/// directions, and even accept negative indices. The objects stored
3821/// have a type T. As it relies on the solver for reversibility, these
3822/// objects can be up-casted to 'C' when using Solver::SaveValue().
3823template <class T, class C>
3824class RevGrowingArray {
3825 public:
3826 explicit RevGrowingArray(int64_t block_size)
3827 : block_size_(block_size), block_offset_(0) {
3828 CHECK_GT(block_size, 0);
3829 }
3830
3832 for (int i = 0; i < elements_.size(); ++i) {
3833 delete[] elements_[i];
3834 }
3835 }
3836
3837 T At(int64_t index) const {
3838 const int64_t block_index = ComputeBlockIndex(index);
3839 const int64_t relative_index = block_index - block_offset_;
3840 if (relative_index < 0 || relative_index >= elements_.size()) {
3841 return T();
3842 }
3843 const T* block = elements_[relative_index];
3844 return block != nullptr ? block[index - block_index * block_size_] : T();
3845 }
3847 void RevInsert(Solver* const solver, int64_t index, T value) {
3848 const int64_t block_index = ComputeBlockIndex(index);
3849 T* const block = GetOrCreateBlock(block_index);
3850 const int64_t residual = index - block_index * block_size_;
3851 solver->SaveAndSetValue(reinterpret_cast<C*>(&block[residual]),
3852 reinterpret_cast<C>(value));
3853 }
3854
3855 private:
3856 T* NewBlock() const {
3857 T* const result = new T[block_size_];
3858 for (int i = 0; i < block_size_; ++i) {
3859 result[i] = T();
3860 }
3861 return result;
3863
3864 T* GetOrCreateBlock(int block_index) {
3865 if (elements_.size() == 0) {
3866 block_offset_ = block_index;
3867 GrowUp(block_index);
3868 } else if (block_index < block_offset_) {
3869 GrowDown(block_index);
3870 } else if (block_index - block_offset_ >= elements_.size()) {
3871 GrowUp(block_index);
3872 }
3873 T* block = elements_[block_index - block_offset_];
3874 if (block == nullptr) {
3875 block = NewBlock();
3876 elements_[block_index - block_offset_] = block;
3877 }
3878 return block;
3879 }
3880
3881 int64_t ComputeBlockIndex(int64_t value) const {
3882 return value >= 0 ? value / block_size_
3883 : (value - block_size_ + 1) / block_size_;
3884 }
3885
3886 void GrowUp(int64_t block_index) {
3887 elements_.resize(block_index - block_offset_ + 1);
3888 }
3889
3890 void GrowDown(int64_t block_index) {
3891 const int64_t delta = block_offset_ - block_index;
3892 block_offset_ = block_index;
3893 DCHECK_GT(delta, 0);
3894 elements_.insert(elements_.begin(), delta, nullptr);
3895 }
3896
3897 const int64_t block_size_;
3898 std::vector<T*> elements_;
3899 int block_offset_;
3900};
3901
3906template <class T>
3907class RevIntSet {
3908 public:
3909 static constexpr int kNoInserted = -1;
3910
3912 explicit RevIntSet(int capacity)
3913 : elements_(new T[capacity]),
3914 num_elements_(0),
3915 capacity_(capacity),
3916 position_(new int[capacity]),
3917 delete_position_(true) {
3918 for (int i = 0; i < capacity; ++i) {
3919 position_[i] = kNoInserted;
3920 }
3921 }
3924 RevIntSet(int capacity, int* shared_positions, int shared_positions_size)
3925 : elements_(new T[capacity]),
3926 num_elements_(0),
3927 capacity_(capacity),
3928 position_(shared_positions),
3929 delete_position_(false) {
3930 for (int i = 0; i < shared_positions_size; ++i) {
3931 position_[i] = kNoInserted;
3932 }
3933 }
3934
3935 ~RevIntSet() {
3936 if (delete_position_) {
3937 delete[] position_;
3938 }
3940
3941 int Size() const { return num_elements_.Value(); }
3942
3943 int Capacity() const { return capacity_; }
3944
3945 T Element(int i) const {
3946 DCHECK_GE(i, 0);
3947 DCHECK_LT(i, num_elements_.Value());
3948 return elements_[i];
3949 }
3951 T RemovedElement(int i) const {
3952 DCHECK_GE(i, 0);
3953 DCHECK_LT(i + num_elements_.Value(), capacity_);
3954 return elements_[i + num_elements_.Value()];
3955 }
3957 void Insert(Solver* const solver, const T& elt) {
3958 const int position = num_elements_.Value();
3959 DCHECK_LT(position, capacity_);
3960 DCHECK(NotAlreadyInserted(elt));
3961 elements_[position] = elt;
3962 position_[elt] = position;
3963 num_elements_.Incr(solver);
3964 }
3965
3966 void Remove(Solver* const solver, const T& value_index) {
3967 num_elements_.Decr(solver);
3968 SwapTo(value_index, num_elements_.Value());
3969 }
3970
3971 void Restore(Solver* const solver, const T& value_index) {
3972 SwapTo(value_index, num_elements_.Value());
3973 num_elements_.Incr(solver);
3974 }
3975
3976 void Clear(Solver* const solver) { num_elements_.SetValue(solver, 0); }
3977
3979 typedef const T* const_iterator;
3980 const_iterator begin() const { return elements_.get(); }
3981 const_iterator end() const { return elements_.get() + num_elements_.Value(); }
3982
3983 private:
3985 bool NotAlreadyInserted(const T& elt) {
3986 for (int i = 0; i < num_elements_.Value(); ++i) {
3987 if (elt == elements_[i]) {
3988 return false;
3989 }
3990 }
3991 return true;
3992 }
3993
3994 void SwapTo(T value_index, int next_position) {
3995 const int current_position = position_[value_index];
3996 if (current_position != next_position) {
3997 const T next_value_index = elements_[next_position];
3998 elements_[current_position] = next_value_index;
3999 elements_[next_position] = value_index;
4000 position_[value_index] = next_position;
4001 position_[next_value_index] = current_position;
4002 }
4003 }
4004
4006 std::unique_ptr<T[]> elements_;
4008 NumericalRev<int> num_elements_;
4010 const int capacity_;
4012 int* position_;
4014 const bool delete_position_;
4015};
4016
4018
4019class RevPartialSequence {
4020 public:
4021 explicit RevPartialSequence(const std::vector<int>& items)
4022 : elements_(items),
4023 first_ranked_(0),
4024 last_ranked_(items.size() - 1),
4025 size_(items.size()),
4026 position_(new int[size_]) {
4027 for (int i = 0; i < size_; ++i) {
4028 elements_[i] = items[i];
4029 position_[i] = i;
4030 }
4031 }
4032
4033 explicit RevPartialSequence(int size)
4034 : elements_(size),
4035 first_ranked_(0),
4036 last_ranked_(size - 1),
4037 size_(size),
4038 position_(new int[size_]) {
4039 for (int i = 0; i < size_; ++i) {
4040 elements_[i] = i;
4041 position_[i] = i;
4042 }
4043 }
4044
4046
4047 int NumFirstRanked() const { return first_ranked_.Value(); }
4049 int NumLastRanked() const { return size_ - 1 - last_ranked_.Value(); }
4050
4051 int Size() const { return size_; }
4052
4053#if !defined(SWIG)
4054 const int& operator[](int index) const {
4055 DCHECK_GE(index, 0);
4056 DCHECK_LT(index, size_);
4057 return elements_[index];
4058 }
4059#endif
4061 void RankFirst(Solver* const solver, int elt) {
4062 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
4063 SwapTo(elt, first_ranked_.Value());
4064 first_ranked_.Incr(solver);
4065 }
4067 void RankLast(Solver* const solver, int elt) {
4068 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
4069 SwapTo(elt, last_ranked_.Value());
4070 last_ranked_.Decr(solver);
4071 }
4072
4073 bool IsRanked(int elt) const {
4074 const int position = position_[elt];
4075 return (position < first_ranked_.Value() ||
4076 position > last_ranked_.Value());
4077 }
4078
4079 std::string DebugString() const {
4080 std::string result = "[";
4081 for (int i = 0; i < first_ranked_.Value(); ++i) {
4082 absl::StrAppend(&result, elements_[i]);
4083 if (i != first_ranked_.Value() - 1) {
4084 result.append("-");
4085 }
4086 }
4087 result.append("|");
4088 for (int i = first_ranked_.Value(); i <= last_ranked_.Value(); ++i) {
4089 absl::StrAppend(&result, elements_[i]);
4090 if (i != last_ranked_.Value()) {
4091 result.append("-");
4092 }
4093 }
4094 result.append("|");
4095 for (int i = last_ranked_.Value() + 1; i < size_; ++i) {
4096 absl::StrAppend(&result, elements_[i]);
4097 if (i != size_ - 1) {
4098 result.append("-");
4099 }
4100 }
4101 result.append("]");
4102 return result;
4103 }
4104
4105 private:
4106 void SwapTo(int elt, int next_position) {
4107 const int current_position = position_[elt];
4108 if (current_position != next_position) {
4109 const int next_elt = elements_[next_position];
4110 elements_[current_position] = next_elt;
4111 elements_[next_position] = elt;
4112 position_[elt] = next_position;
4113 position_[next_elt] = current_position;
4114 }
4115 }
4116
4118 std::vector<int> elements_;
4119
4120 NumericalRev<int> first_ranked_;
4122 NumericalRev<int> last_ranked_;
4124 const int size_;
4126 std::unique_ptr<int[]> position_;
4127};
4128
4133class UnsortedNullableRevBitset {
4134 public:
4136 explicit UnsortedNullableRevBitset(int bit_size);
4137
4138 ~UnsortedNullableRevBitset() {}
4139
4142 void Init(Solver* solver, const std::vector<uint64_t>& mask);
4143
4146 bool RevSubtract(Solver* solver, const std::vector<uint64_t>& mask);
4147
4148 /// This method ANDs the mask with the active bitset. It returns true if
4149 /// the active bitset was changed in the process.
4150 bool RevAnd(Solver* solver, const std::vector<uint64_t>& mask);
4151
4154 int ActiveWordSize() const { return active_words_.Size(); }
4155
4157 bool Empty() const { return active_words_.Size() == 0; }
4158
4166 bool Intersects(const std::vector<uint64_t>& mask, int* support_index);
4167
4169 int64_t bit_size() const { return bit_size_; }
4171 int64_t word_size() const { return word_size_; }
4173 const RevIntSet<int>& active_words() const { return active_words_; }
4174
4175 private:
4176 void CleanUpActives(Solver* solver);
4177
4178 const int64_t bit_size_;
4179 const int64_t word_size_;
4180 RevArray<uint64_t> bits_;
4181 RevIntSet<int> active_words_;
4182 std::vector<int> to_remove_;
4183};
4185template <class T>
4186bool IsArrayConstant(const std::vector<T>& values, const T& value) {
4187 for (int i = 0; i < values.size(); ++i) {
4188 if (values[i] != value) {
4189 return false;
4190 }
4191 }
4192 return true;
4193}
4194
4195template <class T>
4196bool IsArrayBoolean(const std::vector<T>& values) {
4197 for (int i = 0; i < values.size(); ++i) {
4198 if (values[i] != 0 && values[i] != 1) {
4199 return false;
4200 }
4202 return true;
4203}
4204
4205template <class T>
4206bool AreAllOnes(const std::vector<T>& values) {
4207 return IsArrayConstant(values, T(1));
4208}
4209
4210template <class T>
4211bool AreAllNull(const std::vector<T>& values) {
4212 return IsArrayConstant(values, T(0));
4213}
4214
4215template <class T>
4216bool AreAllGreaterOrEqual(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 AreAllLessOrEqual(const std::vector<T>& values, const T& value) {
4227 for (const T& current_value : values) {
4228 if (current_value > value) {
4229 return false;
4230 }
4232 return true;
4233}
4234
4235template <class T>
4236bool AreAllPositive(const std::vector<T>& values) {
4237 return AreAllGreaterOrEqual(values, T(0));
4238}
4239
4240template <class T>
4241bool AreAllNegative(const std::vector<T>& values) {
4242 return AreAllLessOrEqual(values, T(0));
4243}
4244
4245template <class T>
4246bool AreAllStrictlyPositive(const std::vector<T>& values) {
4247 return AreAllGreaterOrEqual(values, T(1));
4248}
4249
4250template <class T>
4251bool AreAllStrictlyNegative(const std::vector<T>& values) {
4252 return AreAllLessOrEqual(values, T(-1));
4253}
4254
4255template <class T>
4256bool IsIncreasingContiguous(const std::vector<T>& values) {
4257 for (int i = 0; i < values.size() - 1; ++i) {
4258 if (values[i + 1] != values[i] + 1) {
4259 return false;
4260 }
4262 return true;
4263}
4264
4265template <class T>
4266bool IsIncreasing(const std::vector<T>& values) {
4267 for (int i = 0; i < values.size() - 1; ++i) {
4268 if (values[i + 1] < values[i]) {
4269 return false;
4270 }
4272 return true;
4273}
4274
4275template <class T>
4276bool IsArrayInRange(const std::vector<IntVar*>& vars, T range_min,
4277 T range_max) {
4278 for (int i = 0; i < vars.size(); ++i) {
4279 if (vars[i]->Min() < range_min || vars[i]->Max() > range_max) {
4280 return false;
4282 }
4283 return true;
4284}
4285
4286inline bool AreAllBound(const std::vector<IntVar*>& vars) {
4287 for (int i = 0; i < vars.size(); ++i) {
4288 if (!vars[i]->Bound()) {
4289 return false;
4290 }
4292 return true;
4293}
4294
4295inline bool AreAllBooleans(const std::vector<IntVar*>& vars) {
4296 return IsArrayInRange(vars, 0, 1);
4297}
4298
4300
4301template <class T>
4302bool AreAllBoundOrNull(const std::vector<IntVar*>& vars,
4303 const std::vector<T>& values) {
4304 for (int i = 0; i < vars.size(); ++i) {
4305 if (values[i] != 0 && !vars[i]->Bound()) {
4306 return false;
4307 }
4308 }
4309 return true;
4311
4313inline bool AreAllBoundTo(const std::vector<IntVar*>& vars, int64_t value) {
4314 for (int i = 0; i < vars.size(); ++i) {
4315 if (!vars[i]->Bound() || vars[i]->Min() != value) {
4316 return false;
4318 }
4319 return true;
4320}
4321
4322inline int64_t MaxVarArray(const std::vector<IntVar*>& vars) {
4323 DCHECK(!vars.empty());
4324 int64_t result = kint64min;
4325 for (int i = 0; i < vars.size(); ++i) {
4326
4327 result = std::max<int64_t>(result, vars[i]->Max());
4329 return result;
4330}
4331
4332inline int64_t MinVarArray(const std::vector<IntVar*>& vars) {
4333 DCHECK(!vars.empty());
4334 int64_t result = kint64max;
4335 for (int i = 0; i < vars.size(); ++i) {
4336
4337 result = std::min<int64_t>(result, vars[i]->Min());
4338 }
4339 return result;
4340}
4341
4342inline void FillValues(const std::vector<IntVar*>& vars,
4343 std::vector<int64_t>* const values) {
4344 values->clear();
4345 values->resize(vars.size());
4346 for (int i = 0; i < vars.size(); ++i) {
4347 (*values)[i] = vars[i]->Value();
4348 }
4349}
4350
4351inline int64_t PosIntDivUp(int64_t e, int64_t v) {
4352 DCHECK_GT(v, 0);
4353 return (e < 0 || e % v == 0) ? e / v : e / v + 1;
4354}
4355
4356inline int64_t PosIntDivDown(int64_t e, int64_t v) {
4357 DCHECK_GT(v, 0);
4358 return (e >= 0 || e % v == 0) ? e / v : e / v - 1;
4359}
4360
4361std::vector<int64_t> ToInt64Vector(const std::vector<int>& input);
4362
4363} // namespace operations_research
4364
4365#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:560
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:306
void EndInitialPropagation() override
After the initial propagation.
Definition search.cc:297
void BeginInitialPropagation() override
Before the initial propagation.
Definition search.cc:295
std::string DebugString() const override
Definition search.cc:86
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:896
void Set(IntegerType index)
Definition bitset.h:878
const std::vector< ArcId > & ComputeSortedSubDagArcs(NodeId node)
-------— Symmetry Breaking -------—
Definition search.cc:5349
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:499
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:1601
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:223
bool Next()
trees with all degrees equal to
static int input(yyscan_t yyscanner)
#define DEFINE_STRONG_INT_TYPE(type_name, value_type)
Set of parameters used to configure how the neighborhood 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