OR-Tools  8.2
constraint_solveri.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
48
49#ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
50#define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
51
52#include <algorithm>
53#include <cmath>
54#include <cstddef>
55#include <functional>
56#include <memory>
57#include <string>
58#include <vector>
59
60#include "absl/container/flat_hash_map.h"
61#include "absl/strings/str_cat.h"
62#include "absl/strings/str_format.h"
63#include "absl/strings/str_join.h"
65#include "ortools/base/hash.h"
70#include "ortools/base/timer.h"
72#include "ortools/util/bitset.h"
75
76class WallTimer;
77
78namespace operations_research {
79class CPArgumentProto;
80class CPConstraintProto;
81class CPIntegerExpressionProto;
82class CPIntervalVariableProto;
83
109class BaseIntExpr : public IntExpr {
110 public:
111 explicit BaseIntExpr(Solver* const s) : IntExpr(s), var_(nullptr) {}
112 ~BaseIntExpr() override {}
113
114 IntVar* Var() override;
115 virtual IntVar* CastToVar();
116
117 private:
118 IntVar* var_;
119};
120
134
143#ifndef SWIG
144template <class T>
146 private:
147 enum { CHUNK_SIZE = 16 }; // TODO(user): could be an extra template param
148 struct Chunk {
149 T data_[CHUNK_SIZE];
150 const Chunk* const next_;
151 explicit Chunk(const Chunk* next) : next_(next) {}
152 };
153
154 public:
156 class Iterator {
157 public:
158 explicit Iterator(const SimpleRevFIFO<T>* l)
159 : chunk_(l->chunks_), value_(l->Last()) {}
160 bool ok() const { return (value_ != nullptr); }
161 T operator*() const { return *value_; }
162 void operator++() {
163 ++value_;
164 if (value_ == chunk_->data_ + CHUNK_SIZE) {
165 chunk_ = chunk_->next_;
166 value_ = chunk_ ? chunk_->data_ : nullptr;
167 }
168 }
169
170 private:
171 const Chunk* chunk_;
172 const T* value_;
173 };
174
175 SimpleRevFIFO() : chunks_(nullptr), pos_(0) {}
176
177 void Push(Solver* const s, T val) {
178 if (pos_.Value() == 0) {
179 Chunk* const chunk = s->UnsafeRevAlloc(new Chunk(chunks_));
180 s->SaveAndSetValue(reinterpret_cast<void**>(&chunks_),
181 reinterpret_cast<void*>(chunk));
182 pos_.SetValue(s, CHUNK_SIZE - 1);
183 } else {
184 pos_.Decr(s);
185 }
186 chunks_->data_[pos_.Value()] = val;
187 }
188
190 void PushIfNotTop(Solver* const s, T val) {
191 if (chunks_ == nullptr || LastValue() != val) {
192 Push(s, val);
193 }
194 }
195
197 const T* Last() const {
198 return chunks_ ? &chunks_->data_[pos_.Value()] : nullptr;
199 }
200
201 T* MutableLast() { return chunks_ ? &chunks_->data_[pos_.Value()] : nullptr; }
202
204 const T& LastValue() const {
205 DCHECK(chunks_);
206 return chunks_->data_[pos_.Value()];
207 }
208
210 void SetLastValue(const T& v) {
211 DCHECK(Last());
212 chunks_->data_[pos_.Value()] = v;
213 }
214
215 private:
216 Chunk* chunks_;
218};
219
221// TODO(user): use murmurhash.
223 value = (~value) + (value << 21);
224 value ^= value >> 24;
225 value += (value << 3) + (value << 8);
226 value ^= value >> 14;
227 value += (value << 2) + (value << 4);
228 value ^= value >> 28;
229 value += (value << 31);
230 return value;
231}
232
234 uint64 a = value;
235 a = (a + 0x7ed55d16) + (a << 12);
236 a = (a ^ 0xc761c23c) ^ (a >> 19);
237 a = (a + 0x165667b1) + (a << 5);
238 a = (a + 0xd3a2646c) ^ (a << 9);
239 a = (a + 0xfd7046c5) + (a << 3);
240 a = (a ^ 0xb55a4f09) ^ (a >> 16);
241 return a;
242}
243
244inline uint64 Hash1(int64 value) { return Hash1(static_cast<uint64>(value)); }
245
246inline uint64 Hash1(int value) { return Hash1(static_cast<uint32>(value)); }
247
248inline uint64 Hash1(void* const ptr) {
249#if defined(__x86_64__) || defined(_M_X64) || defined(__powerpc64__) || \
250 defined(__aarch64__)
251 return Hash1(reinterpret_cast<uint64>(ptr));
252#else
253 return Hash1(reinterpret_cast<uint32>(ptr));
254#endif
255}
256
257template <class T>
258uint64 Hash1(const std::vector<T*>& ptrs) {
259 if (ptrs.empty()) return 0;
260 if (ptrs.size() == 1) return Hash1(ptrs[0]);
261 uint64 hash = Hash1(ptrs[0]);
262 for (int i = 1; i < ptrs.size(); ++i) {
263 hash = hash * i + Hash1(ptrs[i]);
264 }
265 return hash;
266}
267
268inline uint64 Hash1(const std::vector<int64>& ptrs) {
269 if (ptrs.empty()) return 0;
270 if (ptrs.size() == 1) return Hash1(ptrs[0]);
271 uint64 hash = Hash1(ptrs[0]);
272 for (int i = 1; i < ptrs.size(); ++i) {
273 hash = hash * i + Hash1(ptrs[i]);
274 }
275 return hash;
276}
277
280template <class K, class V>
282 public:
283 RevImmutableMultiMap(Solver* const solver, int initial_size)
284 : solver_(solver),
285 array_(solver->UnsafeRevAllocArray(new Cell*[initial_size])),
286 size_(initial_size),
287 num_items_(0) {
288 memset(array_, 0, sizeof(*array_) * size_.Value());
289 }
290
292
293 int num_items() const { return num_items_.Value(); }
294
296 bool ContainsKey(const K& key) const {
297 uint64 code = Hash1(key) % size_.Value();
298 Cell* tmp = array_[code];
299 while (tmp) {
300 if (tmp->key() == key) {
301 return true;
302 }
303 tmp = tmp->next();
304 }
305 return false;
306 }
307
311 const V& FindWithDefault(const K& key, const V& default_value) const {
312 uint64 code = Hash1(key) % size_.Value();
313 Cell* tmp = array_[code];
314 while (tmp) {
315 if (tmp->key() == key) {
316 return tmp->value();
317 }
318 tmp = tmp->next();
319 }
320 return default_value;
321 }
322
324 void Insert(const K& key, const V& value) {
325 const int position = Hash1(key) % size_.Value();
326 Cell* const cell =
327 solver_->UnsafeRevAlloc(new Cell(key, value, array_[position]));
328 solver_->SaveAndSetValue(reinterpret_cast<void**>(&array_[position]),
329 reinterpret_cast<void*>(cell));
330 num_items_.Incr(solver_);
331 if (num_items_.Value() > 2 * size_.Value()) {
332 Double();
333 }
334 }
335
336 private:
337 class Cell {
338 public:
339 Cell(const K& key, const V& value, Cell* const next)
340 : key_(key), value_(value), next_(next) {}
341
342 void SetRevNext(Solver* const solver, Cell* const next) {
343 solver->SaveAndSetValue(reinterpret_cast<void**>(&next_),
344 reinterpret_cast<void*>(next));
345 }
346
347 Cell* next() const { return next_; }
348
349 const K& key() const { return key_; }
350
351 const V& value() const { return value_; }
352
353 private:
354 const K key_;
355 const V value_;
356 Cell* next_;
357 };
358
359 void Double() {
360 Cell** const old_cell_array = array_;
361 const int old_size = size_.Value();
362 size_.SetValue(solver_, size_.Value() * 2);
363 solver_->SaveAndSetValue(
364 reinterpret_cast<void**>(&array_),
365 reinterpret_cast<void*>(
366 solver_->UnsafeRevAllocArray(new Cell*[size_.Value()])));
367 memset(array_, 0, size_.Value() * sizeof(*array_));
368 for (int i = 0; i < old_size; ++i) {
369 Cell* tmp = old_cell_array[i];
370 while (tmp != nullptr) {
371 Cell* const to_reinsert = tmp;
372 tmp = tmp->next();
373 const uint64 new_position = Hash1(to_reinsert->key()) % size_.Value();
374 to_reinsert->SetRevNext(solver_, array_[new_position]);
375 solver_->SaveAndSetValue(
376 reinterpret_cast<void**>(&array_[new_position]),
377 reinterpret_cast<void*>(to_reinsert));
378 }
379 }
380 }
381
382 Solver* const solver_;
383 Cell** array_;
384 NumericalRev<int> size_;
385 NumericalRev<int> num_items_;
386};
387
390 public:
391 RevSwitch() : value_(false) {}
392
393 bool Switched() const { return value_; }
394
395 void Switch(Solver* const solver) { solver->SaveAndSetValue(&value_, true); }
396
397 private:
398 bool value_;
399};
400
404 public:
405 explicit SmallRevBitSet(int64 size);
407 void SetToOne(Solver* const solver, int64 pos);
409 void SetToZero(Solver* const solver, int64 pos);
411 int64 Cardinality() const;
413 bool IsCardinalityZero() const { return bits_.Value() == uint64_t{0}; }
415 bool IsCardinalityOne() const {
416 return (bits_.Value() != 0) && !(bits_.Value() & (bits_.Value() - 1));
417 }
420 int64 GetFirstOne() const;
421
422 private:
423 Rev<uint64> bits_;
424};
425
429 public:
430 explicit RevBitSet(int64 size);
431 ~RevBitSet();
432
434 void SetToOne(Solver* const solver, int64 index);
436 void SetToZero(Solver* const solver, int64 index);
438 bool IsSet(int64 index) const;
440 int64 Cardinality() const;
442 bool IsCardinalityZero() const;
444 bool IsCardinalityOne() const;
447 int64 GetFirstBit(int start) const;
449 void ClearAll(Solver* const solver);
450
451 friend class RevBitMatrix;
452
453 private:
455 void Save(Solver* const solver, int offset);
456 const int64 size_;
457 const int64 length_;
458 uint64* bits_;
459 uint64* stamps_;
460};
461
463class RevBitMatrix : private RevBitSet {
464 public:
465 RevBitMatrix(int64 rows, int64 columns);
467
469 void SetToOne(Solver* const solver, int64 row, int64 column);
471 void SetToZero(Solver* const solver, int64 row, int64 column);
473 bool IsSet(int64 row, int64 column) const {
474 DCHECK_GE(row, 0);
475 DCHECK_LT(row, rows_);
476 DCHECK_GE(column, 0);
477 DCHECK_LT(column, columns_);
478 return RevBitSet::IsSet(row * columns_ + column);
479 }
481 int64 Cardinality(int row) const;
483 bool IsCardinalityZero(int row) const;
485 bool IsCardinalityOne(int row) const;
488 int64 GetFirstBit(int row, int start) const;
490 void ClearAll(Solver* const solver);
491
492 private:
493 const int64 rows_;
494 const int64 columns_;
495};
496
502
504template <class T>
505class CallMethod0 : public Demon {
506 public:
507 CallMethod0(T* const ct, void (T::*method)(), const std::string& name)
508 : constraint_(ct), method_(method), name_(name) {}
509
510 ~CallMethod0() override {}
511
512 void Run(Solver* const s) override { (constraint_->*method_)(); }
513
514 std::string DebugString() const override {
515 return "CallMethod_" + name_ + "(" + constraint_->DebugString() + ")";
516 }
517
518 private:
519 T* const constraint_;
520 void (T::*const method_)();
521 const std::string name_;
522};
523
524template <class T>
525Demon* MakeConstraintDemon0(Solver* const s, T* const ct, void (T::*method)(),
526 const std::string& name) {
527 return s->RevAlloc(new CallMethod0<T>(ct, method, name));
528}
529
530template <class P>
531std::string ParameterDebugString(P param) {
532 return absl::StrCat(param);
533}
534
536template <class P>
537std::string ParameterDebugString(P* param) {
538 return param->DebugString();
539}
540
542template <class T, class P>
543class CallMethod1 : public Demon {
544 public:
545 CallMethod1(T* const ct, void (T::*method)(P), const std::string& name,
546 P param1)
547 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
548
549 ~CallMethod1() override {}
550
551 void Run(Solver* const s) override { (constraint_->*method_)(param1_); }
552
553 std::string DebugString() const override {
554 return absl::StrCat("CallMethod_", name_, "(", constraint_->DebugString(),
555 ", ", ParameterDebugString(param1_), ")");
556 }
557
558 private:
559 T* const constraint_;
560 void (T::*const method_)(P);
561 const std::string name_;
562 P param1_;
563};
564
565template <class T, class P>
566Demon* MakeConstraintDemon1(Solver* const s, T* const ct, void (T::*method)(P),
567 const std::string& name, P param1) {
568 return s->RevAlloc(new CallMethod1<T, P>(ct, method, name, param1));
569}
570
572template <class T, class P, class Q>
573class CallMethod2 : public Demon {
574 public:
575 CallMethod2(T* const ct, void (T::*method)(P, Q), const std::string& name,
576 P param1, Q param2)
577 : constraint_(ct),
578 method_(method),
579 name_(name),
580 param1_(param1),
581 param2_(param2) {}
582
583 ~CallMethod2() override {}
584
585 void Run(Solver* const s) override {
586 (constraint_->*method_)(param1_, param2_);
587 }
588
589 std::string DebugString() const override {
590 return absl::StrCat(absl::StrCat("CallMethod_", name_),
591 absl::StrCat("(", constraint_->DebugString()),
592 absl::StrCat(", ", ParameterDebugString(param1_)),
593 absl::StrCat(", ", ParameterDebugString(param2_), ")"));
594 }
595
596 private:
597 T* const constraint_;
598 void (T::*const method_)(P, Q);
599 const std::string name_;
600 P param1_;
601 Q param2_;
602};
603
604template <class T, class P, class Q>
606 void (T::*method)(P, Q), const std::string& name,
607 P param1, Q param2) {
608 return s->RevAlloc(
609 new CallMethod2<T, P, Q>(ct, method, name, param1, param2));
610}
612template <class T, class P, class Q, class R>
613class CallMethod3 : public Demon {
614 public:
615 CallMethod3(T* const ct, void (T::*method)(P, Q, R), const std::string& name,
616 P param1, Q param2, R param3)
617 : constraint_(ct),
618 method_(method),
619 name_(name),
620 param1_(param1),
621 param2_(param2),
622 param3_(param3) {}
623
624 ~CallMethod3() override {}
625
626 void Run(Solver* const s) override {
627 (constraint_->*method_)(param1_, param2_, param3_);
628 }
629
630 std::string DebugString() const override {
631 return absl::StrCat(absl::StrCat("CallMethod_", name_),
632 absl::StrCat("(", constraint_->DebugString()),
633 absl::StrCat(", ", ParameterDebugString(param1_)),
634 absl::StrCat(", ", ParameterDebugString(param2_)),
635 absl::StrCat(", ", ParameterDebugString(param3_), ")"));
636 }
637
638 private:
639 T* const constraint_;
640 void (T::*const method_)(P, Q, R);
641 const std::string name_;
642 P param1_;
643 Q param2_;
644 R param3_;
645};
646
647template <class T, class P, class Q, class R>
649 void (T::*method)(P, Q, R), const std::string& name,
650 P param1, Q param2, R param3) {
651 return s->RevAlloc(
652 new CallMethod3<T, P, Q, R>(ct, method, name, param1, param2, param3));
653}
655
660
662template <class T>
663class DelayedCallMethod0 : public Demon {
664 public:
665 DelayedCallMethod0(T* const ct, void (T::*method)(), const std::string& name)
666 : constraint_(ct), method_(method), name_(name) {}
667
669
670 void Run(Solver* const s) override { (constraint_->*method_)(); }
671
674 }
675
676 std::string DebugString() const override {
677 return "DelayedCallMethod_" + name_ + "(" + constraint_->DebugString() +
678 ")";
679 }
680
681 private:
682 T* const constraint_;
683 void (T::*const method_)();
684 const std::string name_;
685};
686
687template <class T>
689 void (T::*method)(),
690 const std::string& name) {
691 return s->RevAlloc(new DelayedCallMethod0<T>(ct, method, name));
692}
693
695template <class T, class P>
696class DelayedCallMethod1 : public Demon {
697 public:
698 DelayedCallMethod1(T* const ct, void (T::*method)(P), const std::string& name,
699 P param1)
700 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
701
703
704 void Run(Solver* const s) override { (constraint_->*method_)(param1_); }
705
708 }
709
710 std::string DebugString() const override {
711 return absl::StrCat("DelayedCallMethod_", name_, "(",
712 constraint_->DebugString(), ", ",
713 ParameterDebugString(param1_), ")");
714 }
715
716 private:
717 T* const constraint_;
718 void (T::*const method_)(P);
719 const std::string name_;
720 P param1_;
721};
722
723template <class T, class P>
725 void (T::*method)(P),
726 const std::string& name, P param1) {
727 return s->RevAlloc(new DelayedCallMethod1<T, P>(ct, method, name, param1));
728}
729
731template <class T, class P, class Q>
732class DelayedCallMethod2 : public Demon {
733 public:
734 DelayedCallMethod2(T* const ct, void (T::*method)(P, Q),
735 const std::string& name, P param1, Q param2)
736 : constraint_(ct),
737 method_(method),
738 name_(name),
739 param1_(param1),
740 param2_(param2) {}
741
743
744 void Run(Solver* const s) override {
745 (constraint_->*method_)(param1_, param2_);
746 }
747
750 }
751
752 std::string DebugString() const override {
753 return absl::StrCat(absl::StrCat("DelayedCallMethod_", name_),
754 absl::StrCat("(", constraint_->DebugString()),
755 absl::StrCat(", ", ParameterDebugString(param1_)),
756 absl::StrCat(", ", ParameterDebugString(param2_), ")"));
757 }
758
759 private:
760 T* const constraint_;
761 void (T::*const method_)(P, Q);
762 const std::string name_;
763 P param1_;
764 Q param2_;
765};
766
767template <class T, class P, class Q>
769 void (T::*method)(P, Q),
770 const std::string& name, P param1,
771 Q param2) {
772 return s->RevAlloc(
773 new DelayedCallMethod2<T, P, Q>(ct, method, name, param1, param2));
774}
776
777#endif // !defined(SWIG)
778
796// TODO(user): rename Start to Synchronize ?
797// TODO(user): decouple the iterating from the defining of a neighbor.
799 public:
802 virtual bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) = 0;
803 virtual void Start(const Assignment* assignment) = 0;
804 virtual void Reset() {}
805#ifndef SWIG
806 virtual const LocalSearchOperator* Self() const { return this; }
807#endif // SWIG
808 virtual bool HasFragments() const { return false; }
809 virtual bool HoldsDelta() const { return false; }
810};
811
813template <class V, class Val, class Handler>
815 public:
817 explicit VarLocalSearchOperator(Handler var_handler)
818 : activated_(),
820 cleared_(true),
821 var_handler_(var_handler) {}
823 bool HoldsDelta() const override { return true; }
826 void Start(const Assignment* assignment) override {
827 const int size = Size();
828 CHECK_LE(size, assignment->Size())
829 << "Assignment contains fewer variables than operator";
830 for (int i = 0; i < size; ++i) {
831 activated_.Set(i, var_handler_.ValueFromAssignment(*assignment, vars_[i],
832 i, &values_[i]));
833 }
837 OnStart();
838 }
839 virtual bool IsIncremental() const { return false; }
840 int Size() const { return vars_.size(); }
843 const Val& Value(int64 index) const {
844 DCHECK_LT(index, vars_.size());
845 return values_[index];
846 }
848 V* Var(int64 index) const { return vars_[index]; }
849 virtual bool SkipUnchanged(int index) const { return false; }
850 const Val& OldValue(int64 index) const { return old_values_[index]; }
851 void SetValue(int64 index, const Val& value) {
854 }
855 bool Activated(int64 index) const { return activated_[index]; }
859 }
863 }
864 bool ApplyChanges(Assignment* delta, Assignment* deltadelta) const {
865 if (IsIncremental() && !cleared_) {
867 V* var = Var(index);
868 const Val& value = Value(index);
869 const bool activated = activated_[index];
870 var_handler_.AddToAssignment(var, value, activated, nullptr, index,
871 deltadelta);
872 var_handler_.AddToAssignment(var, value, activated,
874 }
875 } else {
876 delta->Clear();
878 const Val& value = Value(index);
879 const bool activated = activated_[index];
880 if (!activated || value != OldValue(index) || !SkipUnchanged(index)) {
881 var_handler_.AddToAssignment(Var(index), value, activated_[index],
883 }
884 }
885 }
886 return true;
887 }
888 void RevertChanges(bool incremental) {
889 cleared_ = false;
891 if (incremental && IsIncremental()) return;
892 cleared_ = true;
895 var_handler_.OnRevertChanges(index, values_[index]);
898 }
900 }
901 void AddVars(const std::vector<V*>& vars) {
902 if (!vars.empty()) {
903 vars_.insert(vars_.end(), vars.begin(), vars.end());
904 const int64 size = Size();
905 values_.resize(size);
906 old_values_.resize(size);
907 prev_values_.resize(size);
908 assignment_indices_.resize(size, -1);
909 activated_.Resize(size);
913 var_handler_.OnAddVars();
914 }
915 }
916
920 virtual void OnStart() {}
921
924 protected:
928 }
929
930 std::vector<V*> vars_;
931 std::vector<Val> values_;
932 std::vector<Val> old_values_;
933 std::vector<Val> prev_values_;
934 mutable std::vector<int> assignment_indices_;
941};
942
945
947 public:
948 IntVarLocalSearchHandler() : op_(nullptr) {}
950 : op_(other.op_) {}
952 void AddToAssignment(IntVar* var, int64 value, bool active,
953 std::vector<int>* assignment_indices, int64 index,
954 Assignment* assignment) const {
955 Assignment::IntContainer* const container =
956 assignment->MutableIntVarContainer();
957 IntVarElement* element = nullptr;
958 if (assignment_indices != nullptr) {
959 if ((*assignment_indices)[index] == -1) {
960 (*assignment_indices)[index] = container->Size();
961 element = assignment->FastAdd(var);
962 } else {
963 element = container->MutableElement((*assignment_indices)[index]);
964 }
965 } else {
966 element = assignment->FastAdd(var);
967 }
968 if (active) {
969 element->SetValue(value);
970 element->Activate();
971 } else {
972 element->Deactivate();
973 }
974 }
975 bool ValueFromAssignment(const Assignment& assignment, IntVar* var,
978 void OnAddVars() {}
979
980 private:
981 IntVarLocalSearchOperator* const op_;
982};
983
989
990#ifdef SWIG
994// TODO(user): find a way to move this code back to the .i file, where it
998#if defined(SWIGPYTHON)
999// clang-format off
1000%unignore VarLocalSearchOperator<IntVar, int64,
1001 IntVarLocalSearchHandler>::Size;
1002%unignore VarLocalSearchOperator<IntVar, int64,
1003 IntVarLocalSearchHandler>::Value;
1004%unignore VarLocalSearchOperator<IntVar, int64,
1005 IntVarLocalSearchHandler>::OldValue;
1006%unignore VarLocalSearchOperator<IntVar, int64,
1007 IntVarLocalSearchHandler>::SetValue;
1008%feature("director") VarLocalSearchOperator<IntVar, int64,
1009 IntVarLocalSearchHandler>::IsIncremental;
1010%feature("director") VarLocalSearchOperator<IntVar, int64,
1011 IntVarLocalSearchHandler>::OnStart;
1012%unignore VarLocalSearchOperator<IntVar, int64,
1013 IntVarLocalSearchHandler>::IsIncremental;
1014%unignore VarLocalSearchOperator<IntVar, int64,
1015 IntVarLocalSearchHandler>::OnStart;
1016// clang-format on
1017#endif // SWIGPYTHON
1018
1019// clang-format off
1020%rename(IntVarLocalSearchOperatorTemplate)
1021 VarLocalSearchOperator<IntVar, int64, IntVarLocalSearchHandler>;
1022%template(IntVarLocalSearchOperatorTemplate)
1023 VarLocalSearchOperator<IntVar, int64, IntVarLocalSearchHandler>;
1024// clang-format on
1025#endif // SWIG
1026
1029 public:
1030 IntVarLocalSearchOperator() : max_inverse_value_(-1) {}
1031 // If keep_inverse_values is true, assumes that vars models an injective
1032 // function f with domain [0, vars.size()) in which case the operator will
1033 // maintain the inverse function.
1034 explicit IntVarLocalSearchOperator(const std::vector<IntVar*>& vars,
1035 bool keep_inverse_values = false)
1038 max_inverse_value_(keep_inverse_values ? vars.size() - 1 : -1) {
1039 AddVars(vars);
1040 if (keep_inverse_values) {
1041 int64 max_value = -1;
1042 for (const IntVar* const var : vars) {
1043 max_value = std::max(max_value, var->Max());
1044 }
1045 inverse_values_.resize(max_value + 1, -1);
1046 old_inverse_values_.resize(max_value + 1, -1);
1047 }
1048 }
1056 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
1057
1058 protected:
1060
1063 // TODO(user): make it pure virtual, implies porting all apps overriding
1065 virtual bool MakeOneNeighbor();
1066
1068 DCHECK_GE(index, 0);
1069 return index <= max_inverse_value_;
1070 }
1071
1072 int64 InverseValue(int64 index) const { return inverse_values_[index]; }
1073
1075 return old_inverse_values_[index];
1076 }
1077
1079 inverse_values_[index] = value;
1080 }
1081
1083 old_inverse_values_[index] = value;
1084 }
1085
1086 private:
1087 const int64 max_inverse_value_;
1088 std::vector<int64> old_inverse_values_;
1089 std::vector<int64> inverse_values_;
1090};
1091
1093 const Assignment& assignment, IntVar* var, int64 index, int64* value) {
1094 const Assignment::IntContainer& container = assignment.IntVarContainer();
1095 const IntVarElement* element = &(container.Element(index));
1096 if (element->Var() != var) {
1097 CHECK(container.Contains(var))
1098 << "Assignment does not contain operator variable " << var;
1099 element = &(container.Element(var));
1100 }
1101 *value = element->Value();
1102 if (op_->IsInverseValue(index)) {
1103 op_->SetInverseValue(*value, index);
1105 }
1106 return element->Activated();
1107}
1108
1110 int64 value) {
1111 if (op_->IsInverseValue(index)) {
1113 }
1114}
1115
1118
1120 public:
1123 : op_(other.op_) {}
1125 : op_(op) {}
1126 void AddToAssignment(SequenceVar* var, const std::vector<int>& value,
1127 bool active, std::vector<int>* assignment_indices,
1128 int64 index, Assignment* assignment) const;
1129 bool ValueFromAssignment(const Assignment& assignment, SequenceVar* var,
1130 int64 index, std::vector<int>* value);
1131 void OnRevertChanges(int64 index, const std::vector<int>& value);
1132 void OnAddVars();
1133
1134 private:
1136};
1137
1138#ifdef SWIG
1142// TODO(user): find a way to move this code back to the .i file, where it
1144// clang-format off
1145%rename(SequenceVarLocalSearchOperatorTemplate) VarLocalSearchOperator<
1146 SequenceVar, std::vector<int>, SequenceVarLocalSearchHandler>;
1147%template(SequenceVarLocalSearchOperatorTemplate) VarLocalSearchOperator<
1148 SequenceVar, std::vector<int>, SequenceVarLocalSearchHandler>;
1149// clang-format on
1150#endif
1151
1152typedef VarLocalSearchOperator<SequenceVar, std::vector<int>,
1153 SequenceVarLocalSearchHandler>
1155
1158 public:
1160 explicit SequenceVarLocalSearchOperator(const std::vector<SequenceVar*>& vars)
1163 AddVars(vars);
1164 }
1168 const std::vector<int>& Sequence(int64 index) const { return Value(index); }
1169 const std::vector<int>& OldSequence(int64 index) const {
1170 return OldValue(index);
1171 }
1172 void SetForwardSequence(int64 index, const std::vector<int>& value) {
1174 }
1175 void SetBackwardSequence(int64 index, const std::vector<int>& value) {
1178 }
1179
1180 protected:
1182
1183 std::vector<std::vector<int>> backward_values_;
1184};
1185
1187 SequenceVar* var, const std::vector<int>& value, bool active,
1188 std::vector<int>* assignment_indices, int64 index,
1189 Assignment* assignment) const {
1190 Assignment::SequenceContainer* const container =
1191 assignment->MutableSequenceVarContainer();
1192 SequenceVarElement* element = nullptr;
1193 if (assignment_indices != nullptr) {
1194 if ((*assignment_indices)[index] == -1) {
1195 (*assignment_indices)[index] = container->Size();
1196 element = assignment->FastAdd(var);
1197 } else {
1198 element = container->MutableElement((*assignment_indices)[index]);
1199 }
1200 } else {
1201 element = assignment->FastAdd(var);
1202 }
1203 if (active) {
1204 element->SetForwardSequence(value);
1206 element->Activate();
1207 } else {
1208 element->Deactivate();
1209 }
1210}
1211
1213 const Assignment& assignment, SequenceVar* var, int64 index,
1214 std::vector<int>* value) {
1215 const Assignment::SequenceContainer& container =
1216 assignment.SequenceVarContainer();
1217 const SequenceVarElement* element = &(container.Element(index));
1218 if (element->Var() != var) {
1219 CHECK(container.Contains(var))
1220 << "Assignment does not contain operator variable " << var;
1221 element = &(container.Element(var));
1222 }
1223 const std::vector<int>& element_value = element->ForwardSequence();
1224 CHECK_GE(var->size(), element_value.size());
1225 op_->backward_values_[index].clear();
1226 *value = element_value;
1227 return element->Activated();
1228}
1229
1231 int64 index, const std::vector<int>& value) {
1232 op_->backward_values_[index].clear();
1233}
1234
1236 op_->backward_values_.resize(op_->Size());
1237}
1238
1267 public:
1268 explicit BaseLns(const std::vector<IntVar*>& vars);
1269 ~BaseLns() override;
1270 virtual void InitFragments();
1271 virtual bool NextFragment() = 0;
1272 void AppendToFragment(int index);
1273 int FragmentSize() const;
1274 bool HasFragments() const override { return true; }
1275
1276 protected:
1278 bool MakeOneNeighbor() override;
1279
1280 private:
1282 void OnStart() override;
1283 std::vector<int> fragment_;
1284};
1285
1291 public:
1292 explicit ChangeValue(const std::vector<IntVar*>& vars);
1293 ~ChangeValue() override;
1295
1296 protected:
1298 bool MakeOneNeighbor() override;
1299
1300 private:
1301 void OnStart() override;
1302
1303 int index_;
1304};
1305
1320 public:
1334 PathOperator(const std::vector<IntVar*>& next_vars,
1335 const std::vector<IntVar*>& path_vars, int number_of_base_nodes,
1336 bool skip_locally_optimal_paths, bool accept_path_end_base,
1337 std::function<int(int64)> start_empty_path_class);
1338 ~PathOperator() override {}
1339 virtual bool MakeNeighbor() = 0;
1340 void Reset() override;
1341
1342 // TODO(user): Make the following methods protected.
1343 bool SkipUnchanged(int index) const override;
1344
1346 int64 Next(int64 node) const {
1347 DCHECK(!IsPathEnd(node));
1348 return Value(node);
1349 }
1350
1352 int64 Prev(int64 node) const {
1353 DCHECK(!IsPathStart(node));
1354 DCHECK_EQ(Next(InverseValue(node)), node);
1355 return InverseValue(node);
1356 }
1357
1360 int64 Path(int64 node) const {
1361 return ignore_path_vars_ ? 0LL : Value(node + number_of_nexts_);
1362 }
1363
1365 int number_of_nexts() const { return number_of_nexts_; }
1366
1367 protected:
1369 bool MakeOneNeighbor() override;
1373 virtual void OnNodeInitialization() {}
1374
1376 int64 BaseNode(int i) const { return base_nodes_[i]; }
1378 int BaseAlternative(int i) const { return base_alternatives_[i]; }
1381 if (!ConsiderAlternatives(i)) return BaseNode(i);
1382 const int alternative_index = alternative_index_[BaseNode(i)];
1383 return alternative_index >= 0
1384 ? alternative_sets_[alternative_index][base_alternatives_[i]]
1385 : BaseNode(i);
1386 }
1388 int BaseSiblingAlternative(int i) const {
1389 return base_sibling_alternatives_[i];
1390 }
1393 if (!ConsiderAlternatives(i)) return BaseNode(i);
1394 const int sibling_alternative_index =
1396 return sibling_alternative_index >= 0
1397 ? alternative_sets_[sibling_alternative_index]
1398 [base_sibling_alternatives_[i]]
1399 : BaseNode(i);
1400 }
1402 int64 StartNode(int i) const { return path_starts_[base_paths_[i]]; }
1404 const std::vector<int64>& path_starts() const { return path_starts_; }
1406 int PathClass(int i) const {
1407 return start_empty_path_class_ != nullptr
1408 ? start_empty_path_class_(StartNode(i))
1409 : StartNode(i);
1410 }
1411
1418 // TODO(user): remove this when automatic detection of such cases in done.
1419 virtual bool RestartAtPathStartOnSynchronize() { return false; }
1423 // TODO(user): ideally this should be OnSamePath(int64 node1, int64 node2);
1425 virtual bool OnSamePathAsPreviousBase(int64 base_index) { return false; }
1431 virtual int64 GetBaseNodeRestartPosition(int base_index) {
1432 return StartNode(base_index);
1433 }
1436 virtual void SetNextBaseToIncrement(int64 base_index) {
1437 next_base_to_increment_ = base_index;
1438 }
1441 virtual bool ConsiderAlternatives(int64 base_index) const { return false; }
1442
1443 int64 OldNext(int64 node) const {
1444 DCHECK(!IsPathEnd(node));
1445 return OldValue(node);
1446 }
1447
1448 int64 OldPrev(int64 node) const {
1449 DCHECK(!IsPathStart(node));
1450 return OldInverseValue(node);
1451 }
1452
1453 int64 OldPath(int64 node) const {
1454 return ignore_path_vars_ ? 0LL : OldValue(node + number_of_nexts_);
1455 }
1456
1459 bool MoveChain(int64 before_chain, int64 chain_end, int64 destination);
1460
1463 bool ReverseChain(int64 before_chain, int64 after_chain, int64* chain_last);
1464
1466 bool MakeActive(int64 node, int64 destination);
1469 bool MakeChainInactive(int64 before_chain, int64 chain_end);
1471 bool SwapActiveAndInactive(int64 active, int64 inactive);
1472
1474 void SetNext(int64 from, int64 to, int64 path) {
1476 SetValue(from, to);
1477 SetInverseValue(to, from);
1478 if (!ignore_path_vars_) {
1479 DCHECK_LT(from + number_of_nexts_, Size());
1480 SetValue(from + number_of_nexts_, path);
1481 }
1482 }
1483
1486 bool IsPathEnd(int64 node) const { return node >= number_of_nexts_; }
1487
1489 bool IsPathStart(int64 node) const { return OldInverseValue(node) == -1; }
1490
1492 bool IsInactive(int64 node) const {
1493 return !IsPathEnd(node) && inactives_[node];
1494 }
1495
1498 virtual bool InitPosition() const { return false; }
1502 void ResetPosition() { just_started_ = true; }
1503
1507 int AddAlternativeSet(const std::vector<int64>& alternative_set) {
1508 const int alternative = alternative_sets_.size();
1509 for (int64 node : alternative_set) {
1510 DCHECK_EQ(-1, alternative_index_[node]);
1511 alternative_index_[node] = alternative;
1512 }
1513 alternative_sets_.push_back(alternative_set);
1514 sibling_alternative_.push_back(-1);
1515 return alternative;
1516 }
1517#ifndef SWIG
1521 const std::vector<std::pair<std::vector<int64>, std::vector<int64>>>&
1522 pair_alternative_sets) {
1523 for (const auto& pair_alternative_set : pair_alternative_sets) {
1524 const int alternative = AddAlternativeSet(pair_alternative_set.first);
1525 sibling_alternative_.back() = alternative + 1;
1526 AddAlternativeSet(pair_alternative_set.second);
1527 }
1528 }
1529#endif // SWIG
1531 int64 GetActiveInAlternativeSet(int alternative_index) const {
1532 return alternative_index >= 0
1533 ? active_in_alternative_set_[alternative_index]
1534 : -1;
1535 }
1538 return GetActiveInAlternativeSet(alternative_index_[node]);
1539 }
1541 int GetSiblingAlternativeIndex(int node) const {
1542 if (node >= alternative_index_.size()) return -1;
1543 const int alternative = alternative_index_[node];
1544 return alternative >= 0 ? sibling_alternative_[alternative] : -1;
1545 }
1549 if (node >= alternative_index_.size()) return -1;
1550 const int alternative = alternative_index_[node];
1551 const int sibling_alternative =
1552 alternative >= 0 ? sibling_alternative_[alternative] : -1;
1553 return GetActiveInAlternativeSet(sibling_alternative);
1554 }
1557 bool CheckChainValidity(int64 before_chain, int64 chain_end,
1558 int64 exclude) const;
1559
1563 int num_paths_ = 0;
1564 std::vector<int64> start_to_path_;
1565
1566 private:
1567 void OnStart() override;
1569 bool OnSamePath(int64 node1, int64 node2) const;
1570
1571 bool CheckEnds() const {
1572 const int base_node_size = base_nodes_.size();
1573 for (int i = base_node_size - 1; i >= 0; --i) {
1574 if (base_nodes_[i] != end_nodes_[i]) {
1575 return true;
1576 }
1577 }
1578 return false;
1579 }
1580 bool IncrementPosition();
1581 void InitializePathStarts();
1582 void InitializeInactives();
1583 void InitializeBaseNodes();
1584 void InitializeAlternatives();
1585 void Synchronize();
1586
1587 std::vector<int> base_nodes_;
1588 std::vector<int> base_alternatives_;
1589 std::vector<int> base_sibling_alternatives_;
1590 std::vector<int> end_nodes_;
1591 std::vector<int> base_paths_;
1592 std::vector<int64> path_starts_;
1593 std::vector<bool> inactives_;
1594 bool just_started_;
1595 bool first_start_;
1596 const bool accept_path_end_base_;
1597 std::function<int(int64)> start_empty_path_class_;
1598 bool skip_locally_optimal_paths_;
1599 bool optimal_paths_enabled_;
1600 std::vector<int> path_basis_;
1601 std::vector<bool> optimal_paths_;
1603#ifndef SWIG
1604 std::vector<std::vector<int64>> alternative_sets_;
1605#endif // SWIG
1606 std::vector<int> alternative_index_;
1607 std::vector<int64> active_in_alternative_set_;
1608 std::vector<int> sibling_alternative_;
1609};
1610
1612template <class T>
1613LocalSearchOperator* MakeLocalSearchOperator(
1614 Solver* solver, const std::vector<IntVar*>& vars,
1615 const std::vector<IntVar*>& secondary_vars,
1616 std::function<int(int64)> start_empty_path_class);
1617
1620class TwoOpt;
1621class Relocate;
1622class Exchange;
1623class Cross;
1624class MakeActiveOperator;
1625class MakeInactiveOperator;
1626class MakeChainInactiveOperator;
1627class SwapActiveOperator;
1628class ExtendedSwapActiveOperator;
1629class MakeActiveAndRelocate;
1630class RelocateAndMakeActiveOperator;
1631class RelocateAndMakeInactiveOperator;
1632
1633#if !defined(SWIG)
1634// A LocalSearchState is a container for variables with bounds that can be
1635// relaxed and tightened, saved and restored. It represents the solution state
1636// of a local search engine, and allows it to go from solution to solution by
1637// relaxing some variables to form a new subproblem, then tightening those
1638// variables to move to a new solution representation. That state may be saved
1639// to an internal copy, or reverted to the last saved internal copy.
1640// Relaxing a variable returns its bounds to their initial state.
1641// Tightening a variable's bounds may make its min larger than its max,
1642// in that case, the tightening function will return false, and the state will
1643// be marked as invalid. No other operations than Revert() can be called on an
1644// invalid state: in particular, an invalid state cannot be saved.
1645class LocalSearchVariable;
1647 public:
1648 LocalSearchVariable AddVariable(int64 initial_min, int64 initial_max);
1649 void Commit();
1650 void Revert();
1651 bool StateIsValid() const { return state_is_valid_; }
1652
1653 private:
1655
1656 struct Bounds {
1657 int64 min;
1658 int64 max;
1659 };
1660
1661 void RelaxVariableBounds(int variable_index);
1662 bool TightenVariableMin(int variable_index, int64 value);
1663 bool TightenVariableMax(int variable_index, int64 value);
1664 int64 VariableMin(int variable_index) const;
1665 int64 VariableMax(int variable_index) const;
1666
1667 std::vector<Bounds> initial_variable_bounds_;
1668 std::vector<Bounds> variable_bounds_;
1669 std::vector<std::pair<Bounds, int>> saved_variable_bounds_trail_;
1670 std::vector<bool> variable_is_relaxed_;
1671 bool state_is_valid_ = true;
1672};
1673
1674// A LocalSearchVariable can only be created by a LocalSearchState, then it is
1675// meant to be passed by copy. If at some point the duplication of
1676// LocalSearchState pointers is too expensive, we could switch to index only,
1677// and the user would have to know the relevant state. The present setup allows
1678// to ensure that variable users will not misuse the state.
1680 public:
1681 int64 Min() const { return state_->VariableMin(variable_index_); }
1682 int64 Max() const { return state_->VariableMax(variable_index_); }
1683 bool SetMin(int64 new_min) {
1684 return state_->TightenVariableMin(variable_index_, new_min);
1685 }
1686 bool SetMax(int64 new_max) {
1687 return state_->TightenVariableMax(variable_index_, new_max);
1688 }
1689 void Relax() { state_->RelaxVariableBounds(variable_index_); }
1690
1691 private:
1692 // Only LocalSearchState can construct LocalSearchVariables.
1693 friend class LocalSearchState;
1694
1695 LocalSearchVariable(LocalSearchState* state, int variable_index)
1696 : state_(state), variable_index_(variable_index) {}
1697
1698 LocalSearchState* const state_;
1699 const int variable_index_;
1700};
1701#endif // !defined(SWIG)
1702
1720 public:
1723 virtual void Relax(const Assignment* delta, const Assignment* deltadelta) {}
1725 virtual void Commit(const Assignment* delta, const Assignment* deltadelta) {}
1726
1736 virtual bool Accept(const Assignment* delta, const Assignment* deltadelta,
1737 int64 objective_min, int64 objective_max) = 0;
1738 virtual bool IsIncremental() const { return false; }
1739
1745 virtual void Synchronize(const Assignment* assignment,
1746 const Assignment* delta) = 0;
1748 virtual void Revert() {}
1749
1751 virtual void Reset() {}
1752
1754 virtual int64 GetSynchronizedObjectiveValue() const { return 0LL; }
1756 // If the last Accept() call returned false, returns an undefined value.
1757 virtual int64 GetAcceptedObjectiveValue() const { return 0LL; }
1758};
1759
1764 public:
1765 // This class is responsible for calling filters methods in a correct order.
1766 // For now, an order is specified explicitly by the user.
1767 enum FilterEventType { kAccept, kRelax };
1771 };
1772
1773 std::string DebugString() const override {
1774 return "LocalSearchFilterManager";
1775 }
1776 // Builds a manager that calls filter methods using an explicit ordering.
1777 explicit LocalSearchFilterManager(std::vector<FilterEvent> filter_events);
1778 // Builds a manager that calls filter methods using the following ordering:
1779 // first Relax() in vector order, then Accept() in vector order.
1780 // Note that some filters might appear only once, if their Relax() or Accept()
1781 // are trivial.
1782 explicit LocalSearchFilterManager(std::vector<LocalSearchFilter*> filters);
1783
1784 // Calls Revert() of filters, in reverse order of Relax events.
1785 void Revert();
1789 bool Accept(LocalSearchMonitor* const monitor, const Assignment* delta,
1790 const Assignment* deltadelta, int64 objective_min,
1791 int64 objective_max);
1793 void Synchronize(const Assignment* assignment, const Assignment* delta);
1794 int64 GetSynchronizedObjectiveValue() const { return synchronized_value_; }
1795 int64 GetAcceptedObjectiveValue() const { return accepted_value_; }
1796
1797 private:
1798 void InitializeForcedEvents();
1799
1800 std::vector<FilterEvent> filter_events_;
1801 int last_event_called_ = -1;
1802 // If a filter is incremental, its Relax() and Accept() must be called for
1803 // every candidate, even if a previous Accept() rejected it.
1804 // To ensure that those filters have consistent inputs, all intermediate
1805 // Relax events are also triggered. All those events are called 'forced'.
1806 std::vector<int> next_forced_events_;
1807 int64 synchronized_value_;
1808 int64 accepted_value_;
1809};
1810
1812 public:
1813 explicit IntVarLocalSearchFilter(const std::vector<IntVar*>& vars);
1814 ~IntVarLocalSearchFilter() override;
1817 void Synchronize(const Assignment* assignment,
1818 const Assignment* delta) override;
1819
1820 bool FindIndex(IntVar* const var, int64* index) const {
1821 DCHECK(index != nullptr);
1822 const int var_index = var->index();
1823 *index = (var_index < var_index_to_index_.size())
1824 ? var_index_to_index_[var_index]
1825 : kUnassigned;
1826 return *index != kUnassigned;
1827 }
1828
1830 void AddVars(const std::vector<IntVar*>& vars);
1831 int Size() const { return vars_.size(); }
1832 IntVar* Var(int index) const { return vars_[index]; }
1833 int64 Value(int index) const {
1834 DCHECK(IsVarSynced(index));
1835 return values_[index];
1836 }
1837 bool IsVarSynced(int index) const { return var_synced_[index]; }
1838
1839 protected:
1840 virtual void OnSynchronize(const Assignment* delta) {}
1841 void SynchronizeOnAssignment(const Assignment* assignment);
1842
1843 private:
1844 std::vector<IntVar*> vars_;
1845 std::vector<int64> values_;
1846 std::vector<bool> var_synced_;
1847 std::vector<int> var_index_to_index_;
1848 static const int kUnassigned;
1849};
1850
1852 public:
1853 explicit PropagationMonitor(Solver* const solver);
1854 ~PropagationMonitor() override;
1855 std::string DebugString() const override { return "PropagationMonitor"; }
1856
1859 Constraint* const constraint) = 0;
1861 Constraint* const constraint) = 0;
1863 Constraint* const parent, Constraint* const nested) = 0;
1865 Constraint* const parent, Constraint* const nested) = 0;
1866 virtual void RegisterDemon(Demon* const demon) = 0;
1867 virtual void BeginDemonRun(Demon* const demon) = 0;
1868 virtual void EndDemonRun(Demon* const demon) = 0;
1870 virtual void EndProcessingIntegerVariable(IntVar* const var) = 0;
1871 virtual void PushContext(const std::string& context) = 0;
1872 virtual void PopContext() = 0;
1874 virtual void SetMin(IntExpr* const expr, int64 new_min) = 0;
1875 virtual void SetMax(IntExpr* const expr, int64 new_max) = 0;
1876 virtual void SetRange(IntExpr* const expr, int64 new_min, int64 new_max) = 0;
1878 virtual void SetMin(IntVar* const var, int64 new_min) = 0;
1879 virtual void SetMax(IntVar* const var, int64 new_max) = 0;
1880 virtual void SetRange(IntVar* const var, int64 new_min, int64 new_max) = 0;
1881 virtual void RemoveValue(IntVar* const var, int64 value) = 0;
1882 virtual void SetValue(IntVar* const var, int64 value) = 0;
1883 virtual void RemoveInterval(IntVar* const var, int64 imin, int64 imax) = 0;
1884 virtual void SetValues(IntVar* const var,
1885 const std::vector<int64>& values) = 0;
1886 virtual void RemoveValues(IntVar* const var,
1887 const std::vector<int64>& values) = 0;
1889 virtual void SetStartMin(IntervalVar* const var, int64 new_min) = 0;
1890 virtual void SetStartMax(IntervalVar* const var, int64 new_max) = 0;
1891 virtual void SetStartRange(IntervalVar* const var, int64 new_min,
1892 int64 new_max) = 0;
1893 virtual void SetEndMin(IntervalVar* const var, int64 new_min) = 0;
1894 virtual void SetEndMax(IntervalVar* const var, int64 new_max) = 0;
1895 virtual void SetEndRange(IntervalVar* const var, int64 new_min,
1896 int64 new_max) = 0;
1897 virtual void SetDurationMin(IntervalVar* const var, int64 new_min) = 0;
1898 virtual void SetDurationMax(IntervalVar* const var, int64 new_max) = 0;
1899 virtual void SetDurationRange(IntervalVar* const var, int64 new_min,
1900 int64 new_max) = 0;
1901 virtual void SetPerformed(IntervalVar* const var, bool value) = 0;
1903 virtual void RankFirst(SequenceVar* const var, int index) = 0;
1904 virtual void RankNotFirst(SequenceVar* const var, int index) = 0;
1905 virtual void RankLast(SequenceVar* const var, int index) = 0;
1906 virtual void RankNotLast(SequenceVar* const var, int index) = 0;
1907 virtual void RankSequence(SequenceVar* const var,
1908 const std::vector<int>& rank_first,
1909 const std::vector<int>& rank_last,
1910 const std::vector<int>& unperformed) = 0;
1912 void Install() override;
1913};
1914
1916 // TODO(user): Add monitoring of local search filters.
1917 public:
1918 explicit LocalSearchMonitor(Solver* const solver);
1919 ~LocalSearchMonitor() override;
1920 std::string DebugString() const override { return "LocalSearchMonitor"; }
1921
1923 virtual void BeginOperatorStart() = 0;
1924 virtual void EndOperatorStart() = 0;
1925 virtual void BeginMakeNextNeighbor(const LocalSearchOperator* op) = 0;
1927 bool neighbor_found, const Assignment* delta,
1928 const Assignment* deltadelta) = 0;
1929 virtual void BeginFilterNeighbor(const LocalSearchOperator* op) = 0;
1931 bool neighbor_found) = 0;
1932 virtual void BeginAcceptNeighbor(const LocalSearchOperator* op) = 0;
1934 bool neighbor_found) = 0;
1935 virtual void BeginFiltering(const LocalSearchFilter* filter) = 0;
1936 virtual void EndFiltering(const LocalSearchFilter* filter, bool reject) = 0;
1937
1939 void Install() override;
1940};
1941
1942class BooleanVar : public IntVar {
1943 public:
1944 static const int kUnboundBooleanVarValue;
1945
1946 explicit BooleanVar(Solver* const s, const std::string& name = "")
1947 : IntVar(s, name), value_(kUnboundBooleanVarValue) {}
1948
1949 ~BooleanVar() override {}
1950
1951 int64 Min() const override { return (value_ == 1); }
1952 void SetMin(int64 m) override;
1953 int64 Max() const override { return (value_ != 0); }
1954 void SetMax(int64 m) override;
1955 void SetRange(int64 mi, int64 ma) override;
1956 bool Bound() const override { return (value_ != kUnboundBooleanVarValue); }
1957 int64 Value() const override {
1958 CHECK_NE(value_, kUnboundBooleanVarValue) << "variable is not bound";
1959 return value_;
1960 }
1961 void RemoveValue(int64 v) override;
1962 void RemoveInterval(int64 l, int64 u) override;
1963 void WhenBound(Demon* d) override;
1964 void WhenRange(Demon* d) override { WhenBound(d); }
1965 void WhenDomain(Demon* d) override { WhenBound(d); }
1966 uint64 Size() const override;
1967 bool Contains(int64 v) const override;
1968 IntVarIterator* MakeHoleIterator(bool reversible) const override;
1969 IntVarIterator* MakeDomainIterator(bool reversible) const override;
1970 std::string DebugString() const override;
1971 int VarType() const override { return BOOLEAN_VAR; }
1972
1973 IntVar* IsEqual(int64 constant) override;
1974 IntVar* IsDifferent(int64 constant) override;
1975 IntVar* IsGreaterOrEqual(int64 constant) override;
1976 IntVar* IsLessOrEqual(int64 constant) override;
1977
1978 virtual void RestoreValue() = 0;
1979 std::string BaseName() const override { return "BooleanVar"; }
1980
1981 int RawValue() const { return value_; }
1982
1983 protected:
1987};
1988
1989class SymmetryManager;
1990
1995 public:
1997 : symmetry_manager_(nullptr), index_in_symmetry_manager_(-1) {}
1998 ~SymmetryBreaker() override {}
1999
2000 void AddIntegerVariableEqualValueClause(IntVar* const var, int64 value);
2001 void AddIntegerVariableGreaterOrEqualValueClause(IntVar* const var,
2002 int64 value);
2003 void AddIntegerVariableLessOrEqualValueClause(IntVar* const var, int64 value);
2004
2005 private:
2006 friend class SymmetryManager;
2007 void set_symmetry_manager_and_index(SymmetryManager* manager, int index) {
2008 CHECK(symmetry_manager_ == nullptr);
2009 CHECK_EQ(-1, index_in_symmetry_manager_);
2010 symmetry_manager_ = manager;
2011 index_in_symmetry_manager_ = index;
2012 }
2013 SymmetryManager* symmetry_manager() const { return symmetry_manager_; }
2014 int index_in_symmetry_manager() const { return index_in_symmetry_manager_; }
2015
2016 SymmetryManager* symmetry_manager_;
2018 int index_in_symmetry_manager_;
2019};
2020
2023class SearchLog : public SearchMonitor {
2024 public:
2025 SearchLog(Solver* const s, OptimizeVar* const obj, IntVar* const var,
2026 double scaling_factor, double offset,
2027 std::function<std::string()> display_callback,
2028 bool display_on_new_solutions_only, int period);
2029 ~SearchLog() override;
2030 void EnterSearch() override;
2031 void ExitSearch() override;
2032 bool AtSolution() override;
2033 void BeginFail() override;
2034 void NoMoreSolutions() override;
2035 void AcceptUncheckedNeighbor() override;
2036 void ApplyDecision(Decision* const decision) override;
2037 void RefuteDecision(Decision* const decision) override;
2038 void OutputDecision();
2039 void Maintain();
2040 void BeginInitialPropagation() override;
2041 void EndInitialPropagation() override;
2042 std::string DebugString() const override;
2043
2044 protected:
2045 /* Bottleneck function used for all UI related output. */
2046 virtual void OutputLine(const std::string& line);
2047
2048 private:
2049 static std::string MemoryUsage();
2050
2051 const int period_;
2052 std::unique_ptr<WallTimer> timer_;
2053 IntVar* const var_;
2054 OptimizeVar* const obj_;
2055 const double scaling_factor_;
2056 const double offset_;
2057 std::function<std::string()> display_callback_;
2058 const bool display_on_new_solutions_only_;
2059 int nsol_;
2060 int64 tick_;
2061 int64 objective_min_;
2062 int64 objective_max_;
2063 int min_right_depth_;
2064 int max_depth_;
2065 int sliding_min_depth_;
2066 int sliding_max_depth_;
2067};
2068
2074 public:
2076 VOID_FALSE_CONSTRAINT = 0,
2079 };
2080
2082 VAR_CONSTANT_EQUALITY = 0,
2087 };
2088
2090 VAR_CONSTANT_CONSTANT_BETWEEN = 0,
2092 };
2093
2095 EXPR_EXPR_EQUALITY = 0,
2102 };
2103
2105 EXPR_OPPOSITE = 0,
2109 };
2110
2112 EXPR_EXPR_DIFFERENCE = 0,
2123 };
2124
2126 EXPR_EXPR_CONSTANT_CONDITIONAL = 0,
2128 };
2129
2131 EXPR_CONSTANT_DIFFERENCE = 0,
2142 };
2144 VAR_CONSTANT_CONSTANT_SEMI_CONTINUOUS = 0,
2146 };
2147
2149 VAR_CONSTANT_ARRAY_ELEMENT = 0,
2151 };
2152
2154 VAR_ARRAY_CONSTANT_ARRAY_SCAL_PROD = 0,
2156 };
2157
2159 VAR_ARRAY_MAX = 0,
2163 };
2164
2166 VAR_ARRAY_CONSTANT_INDEX = 0,
2168 };
2169
2170 explicit ModelCache(Solver* const solver);
2171 virtual ~ModelCache();
2172
2173 virtual void Clear() = 0;
2174
2176
2178
2180 VoidConstraintType type) = 0;
2181
2184 IntVar* const var, int64 value, VarConstantConstraintType type) const = 0;
2185
2187 IntVar* const var, int64 value,
2188 VarConstantConstraintType type) = 0;
2189
2191
2193 IntVar* const var, int64 value1, int64 value2,
2194 VarConstantConstantConstraintType type) const = 0;
2195
2197 Constraint* const ct, IntVar* const var, int64 value1, int64 value2,
2199
2201
2203 IntExpr* const expr1, IntExpr* const expr2,
2204 ExprExprConstraintType type) const = 0;
2205
2207 IntExpr* const expr1,
2208 IntExpr* const expr2,
2209 ExprExprConstraintType type) = 0;
2210
2212
2213 virtual IntExpr* FindExprExpression(IntExpr* const expr,
2214 ExprExpressionType type) const = 0;
2215
2216 virtual void InsertExprExpression(IntExpr* const expression,
2217 IntExpr* const expr,
2218 ExprExpressionType type) = 0;
2219
2221
2223 IntExpr* const expr, int64 value,
2224 ExprConstantExpressionType type) const = 0;
2225
2227 IntExpr* const expression, IntExpr* const var, int64 value,
2229
2231
2233 IntExpr* const var1, IntExpr* const var2,
2234 ExprExprExpressionType type) const = 0;
2235
2236 virtual void InsertExprExprExpression(IntExpr* const expression,
2237 IntExpr* const var1,
2238 IntExpr* const var2,
2239 ExprExprExpressionType type) = 0;
2240
2242
2244 IntExpr* const var1, IntExpr* const var2, int64 constant,
2245 ExprExprConstantExpressionType type) const = 0;
2246
2248 IntExpr* const expression, IntExpr* const var1, IntExpr* const var2,
2249 int64 constant, ExprExprConstantExpressionType type) = 0;
2250
2252
2254 IntVar* const var, int64 value1, int64 value2,
2255 VarConstantConstantExpressionType type) const = 0;
2256
2258 IntExpr* const expression, IntVar* const var, int64 value1, int64 value2,
2260
2262
2264 IntVar* const var, const std::vector<int64>& values,
2265 VarConstantArrayExpressionType type) const = 0;
2266
2268 IntExpr* const expression, IntVar* const var,
2269 const std::vector<int64>& values,
2271
2273
2275 const std::vector<IntVar*>& vars, VarArrayExpressionType type) const = 0;
2276
2277 virtual void InsertVarArrayExpression(IntExpr* const expression,
2278 const std::vector<IntVar*>& vars,
2279 VarArrayExpressionType type) = 0;
2280
2282
2284 const std::vector<IntVar*>& vars, const std::vector<int64>& values,
2286
2288 IntExpr* const expression, const std::vector<IntVar*>& var,
2289 const std::vector<int64>& values,
2291
2293
2295 const std::vector<IntVar*>& vars, int64 value,
2296 VarArrayConstantExpressionType type) const = 0;
2297
2299 IntExpr* const expression, const std::vector<IntVar*>& var, int64 value,
2301
2302 Solver* solver() const;
2303
2304 private:
2305 Solver* const solver_;
2306};
2307
2309#if !defined(SWIG)
2311 public:
2313 const std::string& TypeName() const;
2314 void SetTypeName(const std::string& type_name);
2315
2317 void SetIntegerArgument(const std::string& arg_name, int64 value);
2318 void SetIntegerArrayArgument(const std::string& arg_name,
2319 const std::vector<int64>& values);
2320 void SetIntegerMatrixArgument(const std::string& arg_name,
2321 const IntTupleSet& values);
2322 void SetIntegerExpressionArgument(const std::string& arg_name,
2323 IntExpr* const expr);
2324 void SetIntegerVariableArrayArgument(const std::string& arg_name,
2325 const std::vector<IntVar*>& vars);
2326 void SetIntervalArgument(const std::string& arg_name, IntervalVar* const var);
2327 void SetIntervalArrayArgument(const std::string& arg_name,
2328 const std::vector<IntervalVar*>& vars);
2329 void SetSequenceArgument(const std::string& arg_name, SequenceVar* const var);
2330 void SetSequenceArrayArgument(const std::string& arg_name,
2331 const std::vector<SequenceVar*>& vars);
2332
2334 bool HasIntegerExpressionArgument(const std::string& arg_name) const;
2335 bool HasIntegerVariableArrayArgument(const std::string& arg_name) const;
2336
2338 int64 FindIntegerArgumentWithDefault(const std::string& arg_name,
2339 int64 def) const;
2340 int64 FindIntegerArgumentOrDie(const std::string& arg_name) const;
2341 const std::vector<int64>& FindIntegerArrayArgumentOrDie(
2342 const std::string& arg_name) const;
2343 const IntTupleSet& FindIntegerMatrixArgumentOrDie(
2344 const std::string& arg_name) const;
2345
2346 IntExpr* FindIntegerExpressionArgumentOrDie(
2347 const std::string& arg_name) const;
2348 const std::vector<IntVar*>& FindIntegerVariableArrayArgumentOrDie(
2349 const std::string& arg_name) const;
2350
2351 private:
2352 std::string type_name_;
2353 absl::flat_hash_map<std::string, int64> integer_argument_;
2354 absl::flat_hash_map<std::string, std::vector<int64>> integer_array_argument_;
2355 absl::flat_hash_map<std::string, IntTupleSet> matrix_argument_;
2356 absl::flat_hash_map<std::string, IntExpr*> integer_expression_argument_;
2357 absl::flat_hash_map<std::string, IntervalVar*> interval_argument_;
2358 absl::flat_hash_map<std::string, SequenceVar*> sequence_argument_;
2359 absl::flat_hash_map<std::string, std::vector<IntVar*>>
2360 integer_variable_array_argument_;
2361 absl::flat_hash_map<std::string, std::vector<IntervalVar*>>
2362 interval_array_argument_;
2363 absl::flat_hash_map<std::string, std::vector<SequenceVar*>>
2364 sequence_array_argument_;
2365};
2366
2369 public:
2370 ModelParser();
2371
2372 ~ModelParser() override;
2373
2375 void BeginVisitModel(const std::string& solver_name) override;
2376 void EndVisitModel(const std::string& solver_name) override;
2377 void BeginVisitConstraint(const std::string& type_name,
2378 const Constraint* const constraint) override;
2379 void EndVisitConstraint(const std::string& type_name,
2380 const Constraint* const constraint) override;
2381 void BeginVisitIntegerExpression(const std::string& type_name,
2382 const IntExpr* const expr) override;
2383 void EndVisitIntegerExpression(const std::string& type_name,
2384 const IntExpr* const expr) override;
2385 void VisitIntegerVariable(const IntVar* const variable,
2386 IntExpr* const delegate) override;
2387 void VisitIntegerVariable(const IntVar* const variable,
2388 const std::string& operation, int64 value,
2389 IntVar* const delegate) override;
2390 void VisitIntervalVariable(const IntervalVar* const variable,
2391 const std::string& operation, int64 value,
2392 IntervalVar* const delegate) override;
2393 void VisitSequenceVariable(const SequenceVar* const variable) override;
2395 void VisitIntegerArgument(const std::string& arg_name, int64 value) override;
2396 void VisitIntegerArrayArgument(const std::string& arg_name,
2397 const std::vector<int64>& values) override;
2398 void VisitIntegerMatrixArgument(const std::string& arg_name,
2399 const IntTupleSet& values) override;
2401 void VisitIntegerExpressionArgument(const std::string& arg_name,
2402 IntExpr* const argument) override;
2403 void VisitIntegerVariableArrayArgument(
2404 const std::string& arg_name,
2405 const std::vector<IntVar*>& arguments) override;
2407 void VisitIntervalArgument(const std::string& arg_name,
2408 IntervalVar* const argument) override;
2409 void VisitIntervalArrayArgument(
2410 const std::string& arg_name,
2411 const std::vector<IntervalVar*>& arguments) override;
2413 void VisitSequenceArgument(const std::string& arg_name,
2414 SequenceVar* const argument) override;
2415 void VisitSequenceArrayArgument(
2416 const std::string& arg_name,
2417 const std::vector<SequenceVar*>& arguments) override;
2418
2419 protected:
2420 void PushArgumentHolder();
2421 void PopArgumentHolder();
2422 ArgumentHolder* Top() const;
2423
2424 private:
2425 std::vector<ArgumentHolder*> holders_;
2426};
2427
2428template <class T>
2430 public:
2431 ArrayWithOffset(int64 index_min, int64 index_max)
2432 : index_min_(index_min),
2433 index_max_(index_max),
2434 values_(new T[index_max - index_min + 1]) {
2435 DCHECK_LE(index_min, index_max);
2436 }
2437
2438 ~ArrayWithOffset() override {}
2439
2440 virtual T Evaluate(int64 index) const {
2441 DCHECK_GE(index, index_min_);
2442 DCHECK_LE(index, index_max_);
2443 return values_[index - index_min_];
2444 }
2445
2447 DCHECK_GE(index, index_min_);
2448 DCHECK_LE(index, index_max_);
2449 values_[index - index_min_] = value;
2450 }
2451
2452 std::string DebugString() const override { return "ArrayWithOffset"; }
2453
2454 private:
2455 const int64 index_min_;
2456 const int64 index_max_;
2457 std::unique_ptr<T[]> values_;
2458};
2459#endif // SWIG
2460
2465template <class T, class C>
2467 public:
2468 explicit RevGrowingArray(int64 block_size)
2469 : block_size_(block_size), block_offset_(0) {
2470 CHECK_GT(block_size, 0);
2471 }
2472
2474 for (int i = 0; i < elements_.size(); ++i) {
2475 delete[] elements_[i];
2476 }
2477 }
2478
2479 T At(int64 index) const {
2480 const int64 block_index = ComputeBlockIndex(index);
2481 const int64 relative_index = block_index - block_offset_;
2482 if (relative_index < 0 || relative_index >= elements_.size()) {
2483 return T();
2484 }
2485 const T* block = elements_[relative_index];
2486 return block != nullptr ? block[index - block_index * block_size_] : T();
2487 }
2488
2489 void RevInsert(Solver* const solver, int64 index, T value) {
2490 const int64 block_index = ComputeBlockIndex(index);
2491 T* const block = GetOrCreateBlock(block_index);
2492 const int64 residual = index - block_index * block_size_;
2493 solver->SaveAndSetValue(reinterpret_cast<C*>(&block[residual]),
2494 reinterpret_cast<C>(value));
2495 }
2496
2497 private:
2498 T* NewBlock() const {
2499 T* const result = new T[block_size_];
2500 for (int i = 0; i < block_size_; ++i) {
2501 result[i] = T();
2502 }
2503 return result;
2504 }
2505
2506 T* GetOrCreateBlock(int block_index) {
2507 if (elements_.size() == 0) {
2508 block_offset_ = block_index;
2509 GrowUp(block_index);
2510 } else if (block_index < block_offset_) {
2511 GrowDown(block_index);
2512 } else if (block_index - block_offset_ >= elements_.size()) {
2513 GrowUp(block_index);
2514 }
2515 T* block = elements_[block_index - block_offset_];
2516 if (block == nullptr) {
2517 block = NewBlock();
2518 elements_[block_index - block_offset_] = block;
2519 }
2520 return block;
2521 }
2522
2523 int64 ComputeBlockIndex(int64 value) const {
2524 return value >= 0 ? value / block_size_
2525 : (value - block_size_ + 1) / block_size_;
2526 }
2527
2528 void GrowUp(int64 block_index) {
2529 elements_.resize(block_index - block_offset_ + 1);
2530 }
2531
2532 void GrowDown(int64 block_index) {
2533 const int64 delta = block_offset_ - block_index;
2534 block_offset_ = block_index;
2535 DCHECK_GT(delta, 0);
2536 elements_.insert(elements_.begin(), delta, nullptr);
2537 }
2538
2539 const int64 block_size_;
2540 std::vector<T*> elements_;
2541 int block_offset_;
2542};
2543
2548template <class T>
2550 public:
2551 static constexpr int kNoInserted = -1;
2552
2554 explicit RevIntSet(int capacity)
2555 : elements_(new T[capacity]),
2556 num_elements_(0),
2557 capacity_(capacity),
2558 position_(new int[capacity]),
2559 delete_position_(true) {
2560 for (int i = 0; i < capacity; ++i) {
2561 position_[i] = kNoInserted;
2562 }
2563 }
2564
2566 RevIntSet(int capacity, int* shared_positions, int shared_positions_size)
2567 : elements_(new T[capacity]),
2568 num_elements_(0),
2569 capacity_(capacity),
2570 position_(shared_positions),
2571 delete_position_(false) {
2572 for (int i = 0; i < shared_positions_size; ++i) {
2573 position_[i] = kNoInserted;
2574 }
2575 }
2576
2578 if (delete_position_) {
2579 delete[] position_;
2580 }
2581 }
2582
2583 int Size() const { return num_elements_.Value(); }
2584
2585 int Capacity() const { return capacity_; }
2586
2587 T Element(int i) const {
2588 DCHECK_GE(i, 0);
2589 DCHECK_LT(i, num_elements_.Value());
2590 return elements_[i];
2591 }
2592
2593 T RemovedElement(int i) const {
2594 DCHECK_GE(i, 0);
2595 DCHECK_LT(i + num_elements_.Value(), capacity_);
2596 return elements_[i + num_elements_.Value()];
2597 }
2598
2599 void Insert(Solver* const solver, const T& elt) {
2600 const int position = num_elements_.Value();
2601 DCHECK_LT(position, capacity_);
2602 DCHECK(NotAlreadyInserted(elt));
2603 elements_[position] = elt;
2604 position_[elt] = position;
2605 num_elements_.Incr(solver);
2606 }
2607
2608 void Remove(Solver* const solver, const T& value_index) {
2609 num_elements_.Decr(solver);
2610 SwapTo(value_index, num_elements_.Value());
2611 }
2612
2613 void Restore(Solver* const solver, const T& value_index) {
2614 SwapTo(value_index, num_elements_.Value());
2615 num_elements_.Incr(solver);
2616 }
2617
2618 void Clear(Solver* const solver) { num_elements_.SetValue(solver, 0); }
2619
2621 typedef const T* const_iterator;
2622 const_iterator begin() const { return elements_.get(); }
2623 const_iterator end() const { return elements_.get() + num_elements_.Value(); }
2624
2625 private:
2627 bool NotAlreadyInserted(const T& elt) {
2628 for (int i = 0; i < num_elements_.Value(); ++i) {
2629 if (elt == elements_[i]) {
2630 return false;
2631 }
2632 }
2633 return true;
2634 }
2635
2636 void SwapTo(T value_index, int next_position) {
2637 const int current_position = position_[value_index];
2638 if (current_position != next_position) {
2639 const T next_value_index = elements_[next_position];
2640 elements_[current_position] = next_value_index;
2641 elements_[next_position] = value_index;
2642 position_[value_index] = next_position;
2643 position_[next_value_index] = current_position;
2644 }
2645 }
2646
2648 std::unique_ptr<T[]> elements_;
2650 NumericalRev<int> num_elements_;
2652 const int capacity_;
2654 int* position_;
2656 const bool delete_position_;
2657};
2658
2660
2662 public:
2663 explicit RevPartialSequence(const std::vector<int>& items)
2664 : elements_(items),
2665 first_ranked_(0),
2666 last_ranked_(items.size() - 1),
2667 size_(items.size()),
2668 position_(new int[size_]) {
2669 for (int i = 0; i < size_; ++i) {
2670 elements_[i] = items[i];
2671 position_[i] = i;
2672 }
2673 }
2674
2675 explicit RevPartialSequence(int size)
2676 : elements_(size),
2677 first_ranked_(0),
2678 last_ranked_(size - 1),
2679 size_(size),
2680 position_(new int[size_]) {
2681 for (int i = 0; i < size_; ++i) {
2682 elements_[i] = i;
2683 position_[i] = i;
2684 }
2685 }
2686
2688
2689 int NumFirstRanked() const { return first_ranked_.Value(); }
2690
2691 int NumLastRanked() const { return size_ - 1 - last_ranked_.Value(); }
2692
2693 int Size() const { return size_; }
2694
2695#if !defined(SWIG)
2696 const int& operator[](int index) const {
2697 DCHECK_GE(index, 0);
2698 DCHECK_LT(index, size_);
2699 return elements_[index];
2700 }
2701#endif
2702
2703 void RankFirst(Solver* const solver, int elt) {
2704 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
2705 SwapTo(elt, first_ranked_.Value());
2706 first_ranked_.Incr(solver);
2707 }
2708
2709 void RankLast(Solver* const solver, int elt) {
2710 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
2711 SwapTo(elt, last_ranked_.Value());
2712 last_ranked_.Decr(solver);
2713 }
2714
2715 bool IsRanked(int elt) const {
2716 const int position = position_[elt];
2717 return (position < first_ranked_.Value() ||
2718 position > last_ranked_.Value());
2719 }
2720
2721 std::string DebugString() const {
2722 std::string result = "[";
2723 for (int i = 0; i < first_ranked_.Value(); ++i) {
2724 absl::StrAppend(&result, elements_[i]);
2725 if (i != first_ranked_.Value() - 1) {
2726 result.append("-");
2727 }
2728 }
2729 result.append("|");
2730 for (int i = first_ranked_.Value(); i <= last_ranked_.Value(); ++i) {
2731 absl::StrAppend(&result, elements_[i]);
2732 if (i != last_ranked_.Value()) {
2733 result.append("-");
2734 }
2735 }
2736 result.append("|");
2737 for (int i = last_ranked_.Value() + 1; i < size_; ++i) {
2738 absl::StrAppend(&result, elements_[i]);
2739 if (i != size_ - 1) {
2740 result.append("-");
2741 }
2742 }
2743 result.append("]");
2744 return result;
2745 }
2746
2747 private:
2748 void SwapTo(int elt, int next_position) {
2749 const int current_position = position_[elt];
2750 if (current_position != next_position) {
2751 const int next_elt = elements_[next_position];
2752 elements_[current_position] = next_elt;
2753 elements_[next_position] = elt;
2754 position_[elt] = next_position;
2755 position_[next_elt] = current_position;
2756 }
2757 }
2758
2760 std::vector<int> elements_;
2762 NumericalRev<int> first_ranked_;
2764 NumericalRev<int> last_ranked_;
2766 const int size_;
2768 std::unique_ptr<int[]> position_;
2769};
2770
2776 public:
2778 explicit UnsortedNullableRevBitset(int bit_size);
2779
2781
2784 void Init(Solver* const solver, const std::vector<uint64>& mask);
2785
2788 bool RevSubtract(Solver* const solver, const std::vector<uint64>& mask);
2789
2792 bool RevAnd(Solver* const solver, const std::vector<uint64>& mask);
2793
2796 int ActiveWordSize() const { return active_words_.Size(); }
2797
2799 bool Empty() const { return active_words_.Size() == 0; }
2800
2808 bool Intersects(const std::vector<uint64>& mask, int* support_index);
2809
2811 int64 bit_size() const { return bit_size_; }
2813 int64 word_size() const { return word_size_; }
2815 const RevIntSet<int>& active_words() const { return active_words_; }
2816
2817 private:
2818 void CleanUpActives(Solver* const solver);
2819
2820 const int64 bit_size_;
2821 const int64 word_size_;
2822 RevArray<uint64> bits_;
2823 RevIntSet<int> active_words_;
2824 std::vector<int> to_remove_;
2825};
2826
2827template <class T>
2828bool IsArrayConstant(const std::vector<T>& values, const T& value) {
2829 for (int i = 0; i < values.size(); ++i) {
2830 if (values[i] != value) {
2831 return false;
2832 }
2833 }
2834 return true;
2835}
2836
2837template <class T>
2838bool IsArrayBoolean(const std::vector<T>& values) {
2839 for (int i = 0; i < values.size(); ++i) {
2840 if (values[i] != 0 && values[i] != 1) {
2841 return false;
2842 }
2843 }
2844 return true;
2845}
2846
2847template <class T>
2848bool AreAllOnes(const std::vector<T>& values) {
2849 return IsArrayConstant(values, T(1));
2850}
2851
2852template <class T>
2853bool AreAllNull(const std::vector<T>& values) {
2854 return IsArrayConstant(values, T(0));
2855}
2856
2857template <class T>
2858bool AreAllGreaterOrEqual(const std::vector<T>& values, const T& value) {
2859 for (const T& current_value : values) {
2860 if (current_value < value) {
2861 return false;
2862 }
2863 }
2864 return true;
2865}
2866
2867template <class T>
2868bool AreAllLessOrEqual(const std::vector<T>& values, const T& value) {
2869 for (const T& current_value : values) {
2870 if (current_value > value) {
2871 return false;
2872 }
2873 }
2874 return true;
2875}
2876
2877template <class T>
2878bool AreAllPositive(const std::vector<T>& values) {
2879 return AreAllGreaterOrEqual(values, T(0));
2880}
2881
2882template <class T>
2883bool AreAllNegative(const std::vector<T>& values) {
2884 return AreAllLessOrEqual(values, T(0));
2885}
2886
2887template <class T>
2888bool AreAllStrictlyPositive(const std::vector<T>& values) {
2889 return AreAllGreaterOrEqual(values, T(1));
2890}
2891
2892template <class T>
2893bool AreAllStrictlyNegative(const std::vector<T>& values) {
2894 return AreAllLessOrEqual(values, T(-1));
2895}
2896
2897template <class T>
2898bool IsIncreasingContiguous(const std::vector<T>& values) {
2899 for (int i = 0; i < values.size() - 1; ++i) {
2900 if (values[i + 1] != values[i] + 1) {
2901 return false;
2902 }
2903 }
2904 return true;
2905}
2906
2907template <class T>
2908bool IsIncreasing(const std::vector<T>& values) {
2909 for (int i = 0; i < values.size() - 1; ++i) {
2910 if (values[i + 1] < values[i]) {
2911 return false;
2912 }
2913 }
2914 return true;
2915}
2916
2917template <class T>
2918bool IsArrayInRange(const std::vector<IntVar*>& vars, T range_min,
2919 T range_max) {
2920 for (int i = 0; i < vars.size(); ++i) {
2921 if (vars[i]->Min() < range_min || vars[i]->Max() > range_max) {
2922 return false;
2923 }
2924 }
2925 return true;
2926}
2927
2928inline bool AreAllBound(const std::vector<IntVar*>& vars) {
2929 for (int i = 0; i < vars.size(); ++i) {
2930 if (!vars[i]->Bound()) {
2931 return false;
2932 }
2933 }
2934 return true;
2935}
2936
2937inline bool AreAllBooleans(const std::vector<IntVar*>& vars) {
2938 return IsArrayInRange(vars, 0, 1);
2939}
2940
2943template <class T>
2944bool AreAllBoundOrNull(const std::vector<IntVar*>& vars,
2945 const std::vector<T>& values) {
2946 for (int i = 0; i < vars.size(); ++i) {
2947 if (values[i] != 0 && !vars[i]->Bound()) {
2948 return false;
2949 }
2950 }
2951 return true;
2952}
2953
2955inline bool AreAllBoundTo(const std::vector<IntVar*>& vars, int64 value) {
2956 for (int i = 0; i < vars.size(); ++i) {
2957 if (!vars[i]->Bound() || vars[i]->Min() != value) {
2958 return false;
2959 }
2960 }
2961 return true;
2962}
2963
2964inline int64 MaxVarArray(const std::vector<IntVar*>& vars) {
2965 DCHECK(!vars.empty());
2966 int64 result = kint64min;
2967 for (int i = 0; i < vars.size(); ++i) {
2969 result = std::max<int64>(result, vars[i]->Max());
2970 }
2971 return result;
2972}
2973
2974inline int64 MinVarArray(const std::vector<IntVar*>& vars) {
2975 DCHECK(!vars.empty());
2976 int64 result = kint64max;
2977 for (int i = 0; i < vars.size(); ++i) {
2979 result = std::min<int64>(result, vars[i]->Min());
2980 }
2981 return result;
2982}
2983
2984inline void FillValues(const std::vector<IntVar*>& vars,
2985 std::vector<int64>* const values) {
2986 values->clear();
2987 values->resize(vars.size());
2988 for (int i = 0; i < vars.size(); ++i) {
2989 (*values)[i] = vars[i]->Value();
2990 }
2991}
2992
2994 DCHECK_GT(v, 0);
2995 return (e < 0 || e % v == 0) ? e / v : e / v + 1;
2996}
2997
2999 DCHECK_GT(v, 0);
3000 return (e >= 0 || e % v == 0) ? e / v : e / v - 1;
3001}
3002
3003std::vector<int64> ToInt64Vector(const std::vector<int>& input);
3004
3005#if !defined(SWIG)
3006// A PathState represents a set of paths and changed made on it.
3007//
3008// More accurately, let us define P_{num_nodes, starts, ends}-graphs the set of
3009// directed graphs with nodes [0, num_nodes) whose connected components are
3010// paths from starts[i] to ends[i] (for the same i) and loops.
3011// Let us fix num_nodes, starts and ends so we call these P-graphs.
3012//
3013// Let us define some notions on graphs with the same set of nodes:
3014// tails(D) is the set of nodes that are the tail of some arc of D.
3015// P0 inter P1 is the graph of all arcs both in P0 and P1.
3016// P0 union P1 is the graph of all arcs either in P0 or P1.
3017// P1 - P0 is the graph with arcs in P1 and not in P0.
3018// P0 |> D is the graph with arcs of P0 whose tail is not in tails(D).
3019// P0 + D is (P0 |> D) union D.
3020//
3021// Now suppose P0 and P1 are P-graphs.
3022// P0 + (P1 - P0) is exactly P1.
3023// Moreover, note that P0 |> D is not a union of paths from some starts[i] to
3024// ends[i] and loops like P0, because the operation removes arcs from P0.
3025// P0 |> D is a union of generic paths, loops, and isolated nodes.
3026// Let us call the generic paths and isolated nodes "chains".
3027// Then the paths of P0 + D are chains linked by arcs of D.
3028// Those chains are particularly interesting when examining a P-graph change.
3029//
3030// A PathState represents a P-graph for a fixed {num_nodes, starts, ends}.
3031// The value of a PathState can be changed incrementally from P0 to P1
3032// by passing the arcs of P1 - P0 to ChangeNext() and marking the end of the
3033// change with a call to CutChains().
3034// If P0 + D is not a P-graph, the behaviour is undefined.
3035// TODO(user): check whether we want to have a DCHECK that P0 + D
3036// is a P-graph or if CutChains() should return false.
3037//
3038// After CutChains(), tails(D) can be traversed using an iterator,
3039// and the chains of P0 |> D can be browsed by chain-based iterators.
3040// An iterator allows to browse the set of paths that have changed.
3041// Then Commit() or Revert() can be called: Commit() changes the PathState to
3042// represent P1 = P0 + D, all further changes are made from P1; Revert() changes
3043// the PathState to forget D completely and return the state to P0.
3044//
3045// After a Commit(), Revert() or at initial state, the same iterators are
3046// available and represent the change by an empty D: the set of changed paths
3047// and the set of changed nodes is empty. Still, the chain-based iterator allows
3048// to browse paths: each path has exactly one chain.
3050 public:
3051 // A ChainRange allows to iterate on all chains of a path.
3052 // ChainRange is a range, its iterator Chain*, its value type Chain.
3053 class ChainRange;
3054 // A Chain allows to iterate on all nodes of a chain, and access some data:
3055 // first node, last node, number of nodes in the chain.
3056 // Chain is a range, its iterator ChainNodeIterator, its value type int.
3057 // Chains are returned by PathChainIterator's operator*().
3058 class Chain;
3059 // A NodeRange allows to iterate on all nodes of a path.
3060 // NodeRange is a range, its iterator PathNodeIterator, its value type int.
3061 class NodeRange;
3062
3063 // Path constructor: path_start and path_end must be disjoint,
3064 // their values in [0, num_nodes).
3065 PathState(int num_nodes, std::vector<int> path_start,
3066 std::vector<int> path_end);
3067
3068 // Instance-constant accessors.
3069
3070 // Returns the number of nodes in the underlying graph.
3071 int NumNodes() const { return num_nodes_; }
3072 // Returns the number of paths (empty paths included).
3073 int NumPaths() const { return num_paths_; }
3074 // Returns the start of a path.
3075 int Start(int path) const { return path_start_end_[path].start; }
3076 // Returns the end of a path.
3077 int End(int path) const { return path_start_end_[path].end; }
3078
3079 // State-dependent accessors.
3080
3081 // Returns the committed path of a given node, -1 if it is a loop.
3082 int Path(int node) const {
3083 return committed_nodes_[committed_index_[node]].path;
3084 }
3085 // Returns the set of arcs that have been added,
3086 // i.e. that were changed and were not in the committed state.
3087 const std::vector<std::pair<int, int>>& ChangedArcs() const {
3088 return changed_arcs_;
3089 }
3090 // Returns the set of paths that actually changed,
3091 // i.e. that have an arc in ChangedArcs().
3092 const std::vector<int>& ChangedPaths() const { return changed_paths_; }
3093 // Returns the current range of chains of path.
3094 ChainRange Chains(int path) const;
3095 // Returns the current range of nodes of path.
3096 NodeRange Nodes(int path) const;
3097
3098 // State modifiers.
3099
3100 // Adds arc (node, new_next) to the changed state, more formally,
3101 // changes the state from (P0, D) to (P0, D + (node, new_next)).
3102 void ChangeNext(int node, int new_next) {
3103 changed_arcs_.emplace_back(node, new_next);
3104 }
3105 // Marks the end of ChangeNext() sequence, more formally,
3106 // changes the state from (P0, D) to (P0 |> D, D).
3107 void CutChains();
3108 // Makes the current temporary state permanent, more formally,
3109 // changes the state from (P0 |> D, D) to (P0 + D, \emptyset),
3110 void Commit();
3111 // Erase incremental changes made by ChangeNext() and CutChains(),
3112 // more formally, changes the state from (P0 |> D, D) to (P0, \emptyset).
3113 void Revert();
3114
3115 // LNS Operators may not fix variables,
3116 // in which case we mark the candidate invalid.
3117 void SetInvalid() { is_invalid_ = true; }
3118 bool IsInvalid() const { return is_invalid_; }
3119
3120 private:
3121 // Most structs below are named pairs of ints, for typing purposes.
3122
3123 // Start and end are stored together to optimize (likely) simultaneous access.
3124 struct PathStartEnd {
3125 PathStartEnd(int start, int end) : start(start), end(end) {}
3126 int start;
3127 int end;
3128 };
3129 // Paths are ranges of chains, which are ranges of committed nodes, see below.
3130 struct PathBounds {
3131 int begin_index;
3132 int end_index;
3133 };
3134 struct ChainBounds {
3135 ChainBounds() = default;
3136 ChainBounds(int begin_index, int end_index)
3137 : begin_index(begin_index), end_index(end_index) {}
3138 int begin_index;
3139 int end_index;
3140 };
3141 struct CommittedNode {
3142 CommittedNode(int node, int path) : node(node), path(path) {}
3143 int node;
3144 // Path of node in the committed state, -1 for loop nodes.
3145 // TODO(user): check if path would be better stored
3146 // with committed_index_, or in its own vector, or just recomputed.
3147 int path;
3148 };
3149 // Used in temporary structures, see below.
3150 struct TailHeadIndices {
3151 int tail_index;
3152 int head_index;
3153 };
3154 struct IndexArc {
3155 int index;
3156 int arc;
3157 bool operator<(const IndexArc& other) const { return index < other.index; }
3158 };
3159
3160 // From changed_paths_ and changed_arcs_, fill chains_ and paths_.
3161 // Selection-based algorithm in O(n^2), to use for small change sets.
3162 void MakeChainsFromChangedPathsAndArcsWithSelectionAlgorithm();
3163 // From changed_paths_ and changed_arcs_, fill chains_ and paths_.
3164 // Generic algorithm in O(std::sort(n)+n), to use for larger change sets.
3165 void MakeChainsFromChangedPathsAndArcsWithGenericAlgorithm();
3166
3167 // Copies nodes in chains of path at the end of nodes,
3168 // and sets those nodes' path member to value path.
3169 void CopyNewPathAtEndOfNodes(int path);
3170 // Commits paths in O(#{changed paths' nodes}) time,
3171 // increasing this object's space usage by O(|changed path nodes|).
3172 void IncrementalCommit();
3173 // Commits paths in O(num_nodes + num_paths) time,
3174 // reducing this object's space usage to O(num_nodes + num_paths).
3175 void FullCommit();
3176
3177 // Instance-constant data.
3178 const int num_nodes_;
3179 const int num_paths_;
3180 std::vector<PathStartEnd> path_start_end_;
3181
3182 // Representation of the committed and changed paths.
3183 // A path is a range of chains, which is a range of nodes.
3184 // Ranges are represented internally by indices in vectors:
3185 // ChainBounds are indices in committed_nodes_. PathBounds are indices in
3186 // chains_. When committed (after construction, Revert() or Commit()):
3187 // - path ranges are [path, path+1): they have one chain.
3188 // - chain ranges don't overlap, chains_ has an empty sentinel at the end.
3189 // - committed_nodes_ contains all nodes and old duplicates may appear,
3190 // the current version of a node is at the index given by
3191 // committed_index_[node]. A Commit() can add nodes at the end of
3192 // committed_nodes_ in a space/time tradeoff, but if committed_nodes_' size
3193 // is above num_nodes_threshold_, Commit() must reclaim useless duplicates'
3194 // space by rewriting the path/chain/nodes structure.
3195 // When changed (after CutChains()), new chains are computed,
3196 // and the structure is updated accordingly:
3197 // - path ranges that were changed have nonoverlapping values [begin, end)
3198 // where begin is >= num_paths_ + 1, i.e. new chains are stored after
3199 // committed state.
3200 // - additional chain ranges are stored after the committed chains
3201 // to represent the new chains resulting from the changes.
3202 // Those chains do not overlap with each other or with unchanged chains.
3203 // An empty sentinel chain is added at the end of additional chains.
3204 // - committed_nodes_ are not modified, and still represent the committed
3205 // paths.
3206 // committed_index_ is not modified either.
3207 std::vector<CommittedNode> committed_nodes_;
3208 std::vector<int> committed_index_;
3209 const int num_nodes_threshold_;
3210 std::vector<ChainBounds> chains_;
3211 std::vector<PathBounds> paths_;
3212
3213 // Incremental information: indices of nodes whose successor have changed,
3214 // path that have changed nodes.
3215 std::vector<std::pair<int, int>> changed_arcs_;
3216 std::vector<int> changed_paths_;
3217 std::vector<bool> path_has_changed_;
3218
3219 // Temporary structures, since they will be reused heavily,
3220 // those are members in order to be allocated once and for all.
3221 std::vector<TailHeadIndices> tail_head_indices_;
3222 std::vector<IndexArc> arcs_by_tail_index_;
3223 std::vector<IndexArc> arcs_by_head_index_;
3224 std::vector<int> next_arc_;
3225
3226 // See IsInvalid() and SetInvalid().
3227 bool is_invalid_ = false;
3228};
3229
3230// A Chain is a range of committed nodes.
3232 public:
3233 class Iterator {
3234 public:
3236 ++current_node_;
3237 return *this;
3238 }
3239 int operator*() const { return current_node_->node; }
3240 bool operator!=(Iterator other) const {
3241 return current_node_ != other.current_node_;
3242 }
3243
3244 private:
3245 // Only a Chain can construct its iterator.
3246 friend class PathState::Chain;
3247 explicit Iterator(const CommittedNode* node) : current_node_(node) {}
3248 const CommittedNode* current_node_;
3249 };
3250
3251 // Chains hold CommittedNode* values, a Chain may be invalidated
3252 // if the underlying vector is modified.
3253 Chain(const CommittedNode* begin_node, const CommittedNode* end_node)
3254 : begin_(begin_node), end_(end_node) {}
3255
3256 int NumNodes() const { return end_ - begin_; }
3257 int First() const { return begin_->node; }
3258 int Last() const { return (end_ - 1)->node; }
3259 Iterator begin() const { return Iterator(begin_); }
3260 Iterator end() const { return Iterator(end_); }
3261
3262 private:
3263 const CommittedNode* const begin_;
3264 const CommittedNode* const end_;
3265};
3266
3267// A ChainRange is a range of Chains, committed or not.
3269 public:
3270 class Iterator {
3271 public:
3273 ++current_chain_;
3274 return *this;
3275 }
3277 return {first_node_ + current_chain_->begin_index,
3278 first_node_ + current_chain_->end_index};
3279 }
3280 bool operator!=(Iterator other) const {
3281 return current_chain_ != other.current_chain_;
3282 }
3283
3284 private:
3285 // Only a ChainRange can construct its Iterator.
3286 friend class ChainRange;
3287 Iterator(const ChainBounds* chain, const CommittedNode* const first_node)
3288 : current_chain_(chain), first_node_(first_node) {}
3289 const ChainBounds* current_chain_;
3290 const CommittedNode* const first_node_;
3291 };
3292
3293 // ChainRanges hold ChainBounds* and CommittedNode*,
3294 // a ChainRange may be invalidated if on of the underlying vector is modified.
3295 ChainRange(const ChainBounds* const begin_chain,
3296 const ChainBounds* const end_chain,
3297 const CommittedNode* const first_node)
3298 : begin_(begin_chain), end_(end_chain), first_node_(first_node) {}
3299
3300 Iterator begin() const { return {begin_, first_node_}; }
3301 Iterator end() const { return {end_, first_node_}; }
3302
3303 private:
3304 const ChainBounds* const begin_;
3305 const ChainBounds* const end_;
3306 const CommittedNode* const first_node_;
3307};
3308
3309// A NodeRange allows to iterate on all nodes of a path,
3310// by a two-level iteration on ChainBounds* and CommittedNode* of a PathState.
3312 public:
3313 class Iterator {
3314 public:
3316 ++current_node_;
3317 if (current_node_ == end_node_) {
3318 ++current_chain_;
3319 // Note: dereferencing bounds is valid because there is a sentinel
3320 // value at the end of PathState::chains_ to that intent.
3321 const ChainBounds bounds = *current_chain_;
3322 current_node_ = first_node_ + bounds.begin_index;
3323 end_node_ = first_node_ + bounds.end_index;
3324 }
3325 return *this;
3326 }
3327 int operator*() const { return current_node_->node; }
3328 bool operator!=(Iterator other) const {
3329 return current_chain_ != other.current_chain_;
3330 }
3331
3332 private:
3333 // Only a NodeRange can construct its Iterator.
3334 friend class NodeRange;
3335 Iterator(const ChainBounds* current_chain,
3336 const CommittedNode* const first_node)
3337 : current_node_(first_node + current_chain->begin_index),
3338 end_node_(first_node + current_chain->end_index),
3339 current_chain_(current_chain),
3340 first_node_(first_node) {}
3341 const CommittedNode* current_node_;
3342 const CommittedNode* end_node_;
3343 const ChainBounds* current_chain_;
3344 const CommittedNode* const first_node_;
3345 };
3346
3347 // NodeRanges hold ChainBounds* and CommittedNode*,
3348 // a NodeRange may be invalidated if on of the underlying vector is modified.
3349 NodeRange(const ChainBounds* begin_chain, const ChainBounds* end_chain,
3350 const CommittedNode* first_node)
3351 : begin_chain_(begin_chain),
3352 end_chain_(end_chain),
3353 first_node_(first_node) {}
3354 Iterator begin() const { return {begin_chain_, first_node_}; }
3355 // Note: there is a sentinel value at the end of PathState::chains_,
3356 // so dereferencing chain_range_.end()->begin_ is always valid.
3357 Iterator end() const { return {end_chain_, first_node_}; }
3358
3359 private:
3360 const ChainBounds* begin_chain_;
3361 const ChainBounds* end_chain_;
3362 const CommittedNode* const first_node_;
3363};
3364
3365// This checker enforces unary dimension requirements.
3366// A unary dimension requires that there is some valuation of
3367// node_capacity and demand such that for all paths,
3368// if arc A -> B is on a path of path_class p,
3369// then node_capacity[A] + demand[p][A] = node_capacity[B].
3370// Moreover, all node_capacities of a path must be inside interval
3371// path_capacity[path].
3372// Note that Intervals have two meanings:
3373// - for demand and node_capacity, those are values allowed for each associated
3374// decision variable.
3375// - for path_capacity, those are set of values that node_capacities of the path
3376// must respect.
3377// If the path capacity of a path is [kint64min, kint64max],
3378// then the unary dimension requirements are not enforced on this path.
3380 public:
3381 struct Interval {
3384 };
3385
3386 UnaryDimensionChecker(const PathState* path_state,
3387 std::vector<Interval> path_capacity,
3388 std::vector<int> path_class,
3389 std::vector<std::vector<Interval>> demand,
3390 std::vector<Interval> node_capacity);
3391
3392 // Given the change made in PathState, checks that the unary dimension
3393 // constraint is still feasible.
3394 bool Check() const;
3395
3396 // Commits to the changes made in PathState,
3397 // must be called before PathState::Commit().
3398 void Commit();
3399
3400 private:
3401 // Range min/max query on partial_demand_sums_.
3402 // The first_node and last_node MUST form a subpath in the committed state.
3403 // Nodes first_node and last_node are passed by their index in precomputed
3404 // data, they must be committed in some path, and it has to be the same path.
3405 // See partial_demand_sums_.
3406 Interval GetMinMaxPartialDemandSum(int first_node_index,
3407 int last_node_index) const;
3408
3409 // Queries whether all nodes in the committed subpath [first_node, last_node]
3410 // have fixed demands and trivial node_capacity [kint64min, kint64max].
3411 // first_node and last_node MUST form a subpath in the committed state.
3412 // Nodes are passed by their index in precomputed data.
3413 bool SubpathOnlyHasTrivialNodes(int first_node_index,
3414 int last_node_index) const;
3415
3416 // Commits to the current solution and rebuilds structures from scratch.
3417 void FullCommit();
3418 // Commits to the current solution and only build structures for paths that
3419 // changed, using additional space to do so in a time-memory tradeoff.
3420 void IncrementalCommit();
3421 // Adds sums of given path to the bottom layer of the RMQ structure,
3422 // updates index_ and previous_nontrivial_index_.
3423 void AppendPathDemandsToSums(int path);
3424 // Updates the RMQ structure from its bottom layer,
3425 // with [begin_index, end_index) the range of the change,
3426 // which must be at the end of the bottom layer.
3427 // Supposes that requests overlapping the range will be inside the range,
3428 // to avoid updating all layers.
3429 void UpdateRMQStructure(int begin_index, int end_index);
3430
3431 const PathState* const path_state_;
3432 const std::vector<Interval> path_capacity_;
3433 const std::vector<int> path_class_;
3434 const std::vector<std::vector<Interval>> demand_;
3435 const std::vector<Interval> node_capacity_;
3436
3437 // Precomputed data.
3438 // Maps nodes to their pre-computed data, except for isolated nodes,
3439 // which do not have precomputed data.
3440 // Only valid for nodes that are in some path in the committed state.
3441 std::vector<int> index_;
3442 // Implementation of a <O(n log n), O(1)> range min/max query, n = #nodes.
3443 // partial_demand_sums_rmq_[0][index_[node]] contains the sum of demands
3444 // from the start of the node's path to the node.
3445 // If node is the start of path, the sum is demand_[path_class_[path]][node],
3446 // moreover partial_demand_sums_rmq_[0][index_[node]-1] is {0, 0}.
3447 // partial_demand_sums_rmq_[layer][index] contains an interval
3448 // [min_value, max_value] such that min_value is
3449 // min(partial_demand_sums_rmq_[0][index+i].min | i in [0, 2^layer)),
3450 // similarly max_value is the maximum of .max on the same range.
3451 std::vector<std::vector<Interval>> partial_demand_sums_rmq_;
3452 // The incremental branch of Commit() may waste space in the layers of the
3453 // RMQ structure. This is the upper limit of a layer's size.
3454 const int maximum_partial_demand_layer_size_;
3455 // previous_nontrivial_index_[index_[node]] has the index of the previous
3456 // node on its committed path that has nonfixed demand or nontrivial node
3457 // capacity. This allows for O(1) queries that all nodes on a subpath
3458 // are nonfixed and nontrivial.
3459 std::vector<int> previous_nontrivial_index_;
3460};
3461
3462// Make a filter that takes ownership of a PathState and synchronizes it with
3463// solver events. The solver represents a graph with array of variables 'nexts'.
3464// Solver events are embodied by Assignment* deltas, that are translated to node
3465// changes during Relax(), committed during Synchronize(), and reverted on
3466// Revert().
3468 std::unique_ptr<PathState> path_state,
3469 const std::vector<IntVar*>& nexts);
3470
3471// Make a filter that translates solver events to the input checker's interface.
3472// Since UnaryDimensionChecker has a PathState, the filter returned by this
3473// must be synchronized to the corresponding PathStateFilter:
3474// - Relax() must be called after the PathStateFilter's.
3475// - Accept() must be called after.
3476// - Synchronize() must be called before.
3477// - Revert() must be called before.
3479 Solver* solver, std::unique_ptr<UnaryDimensionChecker> checker);
3480
3481#endif // !defined(SWIG)
3482
3483} // namespace operations_research
3484
3485#endif // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
int64 min
Definition: alldiff_cst.cc:138
const std::vector< IntVar * > vars_
Definition: alldiff_cst.cc:43
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
int64 MemoryUsage(int unused)
Definition: base/sysinfo.h:24
Argument Holder: useful when visiting a model.
ArrayWithOffset(int64 index_min, int64 index_max)
virtual T Evaluate(int64 index) const
std::string DebugString() const override
bool Contains(const V *const var) const
const E & Element(const V *const var) const
An Assignment is a variable -> domains mapping, used to report solutions to the user.
SequenceContainer * MutableSequenceVarContainer()
const SequenceContainer & SequenceVarContainer() const
const IntContainer & IntVarContainer() const
IntVarElement * FastAdd(IntVar *const var)
Adds without checking if variable has been previously added.
This is the base class for all expressions that are not variables.
IntVar * Var() override
Creates a variable from the expression.
This is the base class for building an Lns operator.
virtual bool NextFragment()=0
bool HasFragments() const override
void AppendToFragment(int index)
BaseLns(const std::vector< IntVar * > &vars)
Definition: local_search.cc:99
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
A BaseObject is the root of all reversibly allocated objects.
void SetContentFromBitsetOfSameSize(const Bitset64< OtherIndexType > &other)
Definition: bitset.h:531
void Clear(IndexType i)
Definition: bitset.h:453
void Set(IndexType i)
Definition: bitset.h:491
void Resize(IndexType size)
Definition: bitset.h:429
void CopyBucket(const Bitset64< IndexType > &other, IndexType i)
Definition: bitset.h:507
bool Bound() const override
Returns true if the min and the max of the expression are equal.
void WhenRange(Demon *d) override
Attach a demon that will watch the min or the max of the expression.
SimpleRevFIFO< Demon * > delayed_bound_demons_
int64 Value() const override
This method returns the value of the variable.
void WhenDomain(Demon *d) override
This method attaches a demon that will watch any domain modification of the domain of the variable.
SimpleRevFIFO< Demon * > bound_demons_
std::string BaseName() const override
Returns a base name for automatic naming.
BooleanVar(Solver *const s, const std::string &name="")
Demon proxy to a method on the constraint with no arguments.
CallMethod0(T *const ct, void(T::*method)(), const std::string &name)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
Demon proxy to a method on the constraint with one argument.
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
CallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)
Demon proxy to a method on the constraint with two arguments.
CallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
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)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
Defines operators which change the value of variables; each neighbor corresponds to one modified vari...
ChangeValue(const std::vector< IntVar * > &vars)
virtual int64 ModifyValue(int64 index, int64 value)=0
bool MakeOneNeighbor() override
This method should not be overridden. Override ModifyValue() instead.
A constraint is the main modeling object.
A Decision represents a choice point in the search tree.
A DecisionVisitor is used to inspect a decision.
Low-priority demon proxy to a method on the constraint with no arguments.
Solver::DemonPriority priority() const override
This method returns the priority of the demon.
void Run(Solver *const s) override
This is the main callback of the demon.
DelayedCallMethod0(T *const ct, void(T::*method)(), const std::string &name)
std::string DebugString() const override
Low-priority demon proxy to a method on the constraint with one argument.
Solver::DemonPriority priority() const override
This method returns the priority of the demon.
DelayedCallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
Low-priority demon proxy to a method on the constraint with two arguments.
Solver::DemonPriority priority() const override
This method returns the priority of the demon.
DelayedCallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
A Demon is the base element of a propagation queue.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual int64 Max() const =0
The class IntVar is a subset of IntExpr.
The class Iterator has two direct subclasses.
virtual void OnSynchronize(const Assignment *delta)
bool FindIndex(IntVar *const var, int64 *index) const
void OnRevertChanges(int64 index, int64 value)
IntVarLocalSearchHandler(const IntVarLocalSearchHandler &other)
bool ValueFromAssignment(const Assignment &assignment, IntVar *var, int64 index, int64 *value)
IntVarLocalSearchHandler(IntVarLocalSearchOperator *op)
void AddToAssignment(IntVar *var, int64 value, bool active, std::vector< int > *assignment_indices, int64 index, Assignment *assignment) const
Specialization of LocalSearchOperator built from an array of IntVars which specifies the scope of the...
void SetOldInverseValue(int64 index, int64 value)
IntVarLocalSearchOperator(const std::vector< IntVar * > &vars, bool keep_inverse_values=false)
Interval variables are often used in scheduling.
Local Search Filters are used for fast neighbor pruning.
virtual void Synchronize(const Assignment *assignment, const Assignment *delta)=0
Synchronizes the filter with the current solution, delta being the difference with the solution passe...
virtual int64 GetSynchronizedObjectiveValue() const
Objective value from last time Synchronize() was called.
virtual bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max)=0
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
virtual void Reset()
Sets the filter to empty solution.
virtual void Relax(const Assignment *delta, const Assignment *deltadelta)
Lets the filter know what delta and deltadelta will be passed in the next Accept().
virtual void Revert()
Cancels the changes made by the last Relax()/Accept() calls.
virtual void Commit(const Assignment *delta, const Assignment *deltadelta)
Dual of Relax(), lets the filter know that the delta was accepted.
virtual int64 GetAcceptedObjectiveValue() const
Objective value from the last time Accept() was called and returned true.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0
virtual void BeginOperatorStart()=0
Local search operator events.
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
std::string DebugString() const override
The base class for all local search operators.
virtual const LocalSearchOperator * Self() const
virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0
virtual void Start(const Assignment *assignment)=0
Implements a complete cache for model elements: expressions and constraints.
virtual IntExpr * FindVarArrayExpression(const std::vector< IntVar * > &vars, VarArrayExpressionType type) const =0
Var Array Expressions.
virtual IntExpr * FindVarConstantArrayExpression(IntVar *const var, const std::vector< int64 > &values, VarConstantArrayExpressionType type) const =0
Var Constant Array Expressions.
virtual Constraint * FindVarConstantConstraint(IntVar *const var, int64 value, VarConstantConstraintType type) const =0
Var Constant Constraints.
virtual void InsertExprConstantExpression(IntExpr *const expression, IntExpr *const var, int64 value, ExprConstantExpressionType type)=0
virtual void InsertVarConstantConstantConstraint(Constraint *const ct, IntVar *const var, int64 value1, int64 value2, VarConstantConstantConstraintType type)=0
virtual IntExpr * FindExprExpression(IntExpr *const expr, ExprExpressionType type) const =0
Expr Expressions.
virtual IntExpr * FindVarArrayConstantExpression(const std::vector< IntVar * > &vars, int64 value, VarArrayConstantExpressionType type) const =0
Var Array Constant Expressions.
virtual void InsertExprExprExpression(IntExpr *const expression, IntExpr *const var1, IntExpr *const var2, ExprExprExpressionType type)=0
virtual void InsertVarConstantConstraint(Constraint *const ct, IntVar *const var, int64 value, VarConstantConstraintType type)=0
virtual IntExpr * FindVarArrayConstantArrayExpression(const std::vector< IntVar * > &vars, const std::vector< int64 > &values, VarArrayConstantArrayExpressionType type) const =0
Var Array Constant Array Expressions.
virtual void InsertVarArrayConstantExpression(IntExpr *const expression, const std::vector< IntVar * > &var, int64 value, VarArrayConstantExpressionType type)=0
virtual IntExpr * FindExprExprConstantExpression(IntExpr *const var1, IntExpr *const var2, int64 constant, ExprExprConstantExpressionType type) const =0
Expr Expr Constant Expressions.
virtual void InsertVoidConstraint(Constraint *const ct, VoidConstraintType type)=0
virtual void InsertExprExprConstantExpression(IntExpr *const expression, IntExpr *const var1, IntExpr *const var2, int64 constant, ExprExprConstantExpressionType type)=0
virtual void InsertVarArrayExpression(IntExpr *const expression, const std::vector< IntVar * > &vars, VarArrayExpressionType type)=0
virtual IntExpr * FindVarConstantConstantExpression(IntVar *const var, int64 value1, int64 value2, VarConstantConstantExpressionType type) const =0
Var Constant Constant Expressions.
virtual Constraint * FindVoidConstraint(VoidConstraintType type) const =0
Void constraints.
virtual void InsertVarArrayConstantArrayExpression(IntExpr *const expression, const std::vector< IntVar * > &var, const std::vector< int64 > &values, VarArrayConstantArrayExpressionType type)=0
virtual void InsertVarConstantConstantExpression(IntExpr *const expression, IntVar *const var, int64 value1, int64 value2, VarConstantConstantExpressionType type)=0
virtual IntExpr * FindExprConstantExpression(IntExpr *const expr, int64 value, ExprConstantExpressionType type) const =0
Expr Constant Expressions.
virtual IntExpr * FindExprExprExpression(IntExpr *const var1, IntExpr *const var2, ExprExprExpressionType type) const =0
Expr Expr Expressions.
virtual Constraint * FindVarConstantConstantConstraint(IntVar *const var, int64 value1, int64 value2, VarConstantConstantConstraintType type) const =0
Var Constant Constant Constraints.
virtual Constraint * FindExprExprConstraint(IntExpr *const expr1, IntExpr *const expr2, ExprExprConstraintType type) const =0
Expr Expr Constraints.
virtual void InsertVarConstantArrayExpression(IntExpr *const expression, IntVar *const var, const std::vector< int64 > &values, VarConstantArrayExpressionType type)=0
virtual void InsertExprExpression(IntExpr *const expression, IntExpr *const expr, ExprExpressionType type)=0
virtual void InsertExprExprConstraint(Constraint *const ct, IntExpr *const expr1, IntExpr *const expr2, ExprExprConstraintType type)=0
This class encapsulates an objective.
Base class of the local search operators dedicated to path modifications (a path is a set of nodes li...
int64 BaseAlternativeNode(int i) const
Returns the alternative node for the ith base node.
void AddPairAlternativeSets(const std::vector< std::pair< std::vector< int64 >, std::vector< int64 > > > &pair_alternative_sets)
Adds all sets of node alternatives of a vector of alternative pairs.
bool SwapActiveAndInactive(int64 active, int64 inactive)
Replaces active by inactive in the current path, making active inactive.
int PathClass(int i) const
Returns the class of the path of the ith base node.
virtual void OnNodeInitialization()
Called by OnStart() after initializing node information.
int64 BaseNode(int i) const
Returns the ith base node of the operator.
bool IsInactive(int64 node) const
Returns true if node is inactive.
int number_of_nexts() const
Number of next variables.
bool IsPathEnd(int64 node) const
Returns true if node is the last node on the path; defined by the fact that node is outside the range...
virtual void SetNextBaseToIncrement(int64 base_index)
Set the next base to increment on next iteration.
virtual bool ConsiderAlternatives(int64 base_index) const
Indicates if alternatives should be considered when iterating over base nodes.
virtual bool RestartAtPathStartOnSynchronize()
When the operator is being synchronized with a new solution (when Start() is called),...
const std::vector< int64 > & path_starts() const
Returns the vector of path start nodes.
int BaseSiblingAlternative(int i) const
Returns the alternative for the sibling of the ith base node.
bool ReverseChain(int64 before_chain, int64 after_chain, int64 *chain_last)
Reverses the chain starting after before_chain and ending before after_chain.
int BaseAlternative(int i) const
Returns the alternative for the ith base node.
void SetNext(int64 from, int64 to, int64 path)
Sets 'to' to be the node after 'from' on the given path.
bool MakeActive(int64 node, int64 destination)
Insert the inactive node after destination.
int AddAlternativeSet(const std::vector< int64 > &alternative_set)
Handling node alternatives.
int64 Prev(int64 node) const
Returns the node before node in the current delta.
int64 GetActiveAlternativeNode(int node) const
Returns the active node in the alternative set of the given node.
int64 StartNode(int i) const
Returns the start node of the ith base node.
bool SkipUnchanged(int index) const override
int64 Next(int64 node) const
Returns the node after node in the current delta.
void ResetPosition()
Reset the position of the operator to its position when Start() was last called; this can be used to ...
bool IsPathStart(int64 node) const
Returns true if node is the first node on the path.
int64 BaseSiblingAlternativeNode(int i) const
Returns the alternative node for the sibling of the ith base node.
virtual int64 GetBaseNodeRestartPosition(int base_index)
Returns the index of the node to which the base node of index base_index must be set to when it reach...
int GetSiblingAlternativeIndex(int node) const
Returns the index of the alternative set of the sibling of node.
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
virtual bool OnSamePathAsPreviousBase(int64 base_index)
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
bool MakeChainInactive(int64 before_chain, int64 chain_end)
Makes the nodes on the chain starting after before_chain and ending at chain_end inactive.
virtual bool InitPosition() const
Returns true if the operator needs to restart its initial position at each call to Start()
int64 Path(int64 node) const
Returns the index of the path to which node belongs in the current delta.
int64 GetActiveAlternativeSibling(int node) const
Returns the active node in the alternative set of the sibling of the given node.
PathOperator(const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, int number_of_base_nodes, bool skip_locally_optimal_paths, bool accept_path_end_base, std::function< int(int64)> start_empty_path_class)
Builds an instance of PathOperator from next and path variables.
bool MoveChain(int64 before_chain, int64 chain_end, int64 destination)
Moves the chain starting after the node before_chain and ending at the node chain_end after the node ...
Chain(const CommittedNode *begin_node, const CommittedNode *end_node)
ChainRange(const ChainBounds *const begin_chain, const ChainBounds *const end_chain, const CommittedNode *const first_node)
NodeRange(const ChainBounds *begin_chain, const ChainBounds *end_chain, const CommittedNode *first_node)
const std::vector< int > & ChangedPaths() const
const std::vector< std::pair< int, int > > & ChangedArcs() const
void ChangeNext(int node, int new_next)
virtual void SetMin(IntVar *const var, int64 new_min)=0
IntVar modifiers.
virtual void RankLast(SequenceVar *const var, int index)=0
virtual void SetEndMin(IntervalVar *const var, int64 new_min)=0
virtual void EndConstraintInitialPropagation(Constraint *const constraint)=0
virtual void SetValues(IntVar *const var, const std::vector< int64 > &values)=0
virtual void SetRange(IntVar *const var, int64 new_min, int64 new_max)=0
virtual void SetMax(IntVar *const var, int64 new_max)=0
virtual void RemoveValue(IntVar *const var, int64 value)=0
virtual void SetEndMax(IntervalVar *const var, int64 new_max)=0
virtual void RankNotLast(SequenceVar *const var, int index)=0
virtual void RankNotFirst(SequenceVar *const var, int index)=0
virtual void BeginDemonRun(Demon *const demon)=0
virtual void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)=0
virtual void PushContext(const std::string &context)=0
virtual void RemoveInterval(IntVar *const var, int64 imin, int64 imax)=0
virtual void RemoveValues(IntVar *const var, const std::vector< int64 > &values)=0
virtual void SetStartMin(IntervalVar *const var, int64 new_min)=0
IntervalVar modifiers.
virtual void SetValue(IntVar *const var, int64 value)=0
virtual void SetStartRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
virtual void BeginNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
virtual void EndNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
virtual void SetRange(IntExpr *const expr, int64 new_min, int64 new_max)=0
virtual void SetPerformed(IntervalVar *const var, bool value)=0
virtual void StartProcessingIntegerVariable(IntVar *const var)=0
virtual void SetDurationRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
virtual void BeginConstraintInitialPropagation(Constraint *const constraint)=0
Propagation events.
virtual void SetDurationMin(IntervalVar *const var, int64 new_min)=0
virtual void SetMax(IntExpr *const expr, int64 new_max)=0
virtual void SetStartMax(IntervalVar *const var, int64 new_max)=0
virtual void EndDemonRun(Demon *const demon)=0
virtual void RegisterDemon(Demon *const demon)=0
virtual void EndProcessingIntegerVariable(IntVar *const var)=0
virtual void SetDurationMax(IntervalVar *const var, int64 new_max)=0
virtual void SetMin(IntExpr *const expr, int64 new_min)=0
IntExpr modifiers.
std::string DebugString() const override
virtual void RankFirst(SequenceVar *const var, int index)=0
SequenceVar modifiers.
virtual void SetEndRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
Matrix version of the RevBitSet class.
bool IsSet(int64 row, int64 column) const
Returns whether the 'column' bit in the 'row' row is set.
int64 GetFirstBit(int row, int start) const
Returns the first bit in the row 'row' which position is >= 'start'.
Definition: utilities.cc:200
void SetToOne(Solver *const solver, int64 row, int64 column)
Sets the 'column' bit in the 'row' row.
Definition: utilities.cc:167
void ClearAll(Solver *const solver)
Cleans all bits.
Definition: utilities.cc:215
void SetToZero(Solver *const solver, int64 row, int64 column)
Erases the 'column' bit in the 'row' row.
Definition: utilities.cc:175
This class represents a reversible bitset.
bool IsCardinalityOne() const
Does it contains only one bit set?
Definition: utilities.cc:126
bool IsSet(int64 index) const
Returns whether the 'index' bit is set.
Definition: utilities.cc:103
void SetToOne(Solver *const solver, int64 index)
Sets the 'index' bit.
Definition: utilities.cc:81
int64 GetFirstBit(int start) const
Gets the index of the first bit set starting from start.
Definition: utilities.cc:144
void ClearAll(Solver *const solver)
Cleans all bits.
Definition: utilities.cc:148
bool IsCardinalityZero() const
Is bitset null?
Definition: utilities.cc:117
int64 Cardinality() const
Returns the number of bits set to one.
Definition: utilities.cc:109
void SetToZero(Solver *const solver, int64 index)
Erases the 'index' bit.
Definition: utilities.cc:92
This class is a reversible growing array.
void RevInsert(Solver *const solver, int64 index, T value)
void SetValue(Solver *const s, const T &val)
Reversible Immutable MultiMap class.
void Insert(const K &key, const V &value)
Inserts (key, value) in the multi-map.
RevImmutableMultiMap(Solver *const solver, int initial_size)
const V & FindWithDefault(const K &key, const V &default_value) const
Returns one value attached to 'key', or 'default_value' if 'key' is not in the multi-map.
bool ContainsKey(const K &key) const
Returns true if the multi-map contains at least one instance of 'key'.
This is a special class to represent a 'residual' set of T.
void Insert(Solver *const solver, const T &elt)
RevIntSet(int capacity)
Capacity is the fixed size of the set (it cannot grow).
const T * const_iterator
Iterators on the indices.
RevIntSet(int capacity, int *shared_positions, int shared_positions_size)
Capacity is the fixed size of the set (it cannot grow).
void Restore(Solver *const solver, const T &value_index)
void Remove(Solver *const solver, const T &value_index)
void Clear(Solver *const solver)
--— RevPartialSequence --—
void RankLast(Solver *const solver, int elt)
const int & operator[](int index) const
void RankFirst(Solver *const solver, int elt)
RevPartialSequence(const std::vector< int > &items)
A reversible switch that can switch once from false to true.
void Switch(Solver *const solver)
The base class of all search logs that periodically outputs information when the search is running.
A search monitor is a simple set of callbacks to monitor all search events.
The SequenceVarElement stores a partial representation of ranked interval variables in the underlying...
void SetBackwardSequence(const std::vector< int > &backward_sequence)
const std::vector< int > & ForwardSequence() const
void SetForwardSequence(const std::vector< int > &forward_sequence)
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
SequenceVarLocalSearchHandler(const SequenceVarLocalSearchHandler &other)
SequenceVarLocalSearchHandler(SequenceVarLocalSearchOperator *op)
bool ValueFromAssignment(const Assignment &assignment, SequenceVar *var, int64 index, std::vector< int > *value)
void OnRevertChanges(int64 index, const std::vector< int > &value)
void AddToAssignment(SequenceVar *var, const std::vector< int > &value, bool active, std::vector< int > *assignment_indices, int64 index, Assignment *assignment) const
const std::vector< int > & Sequence(int64 index) const
Returns the value in the current assignment of the variable of given index.
const std::vector< int > & OldSequence(int64 index) const
void SetBackwardSequence(int64 index, const std::vector< int > &value)
SequenceVarLocalSearchOperator(const std::vector< SequenceVar * > &vars)
void SetForwardSequence(int64 index, const std::vector< int > &value)
This iterator is not stable with respect to deletion.
This class represent a reversible FIFO structure.
void SetLastValue(const T &v)
Sets the last value in the FIFO.
const T * Last() const
Returns the last item of the FIFO.
const T & LastValue() const
Returns the last value in the FIFO.
void PushIfNotTop(Solver *const s, T val)
Pushes the var on top if is not a duplicate of the current top object.
void Push(Solver *const s, T val)
This class represents a small reversible bitset (size <= 64).
void SetToZero(Solver *const solver, int64 pos)
Erases the 'pos' bit.
Definition: utilities.cc:42
bool IsCardinalityOne() const
Does it contains only one bit set?
void SetToOne(Solver *const solver, int64 pos)
Sets the 'pos' bit.
Definition: utilities.cc:37
int64 GetFirstOne() const
Gets the index of the first bit set starting from 0.
Definition: utilities.cc:49
bool IsCardinalityZero() const
Is bitset null?
int64 Cardinality() const
Returns the number of bits set to one.
Definition: utilities.cc:47
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
T * RevAlloc(T *object)
Registers the given object as being reversible.
void Set(IntegerType index)
Definition: bitset.h:803
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition: bitset.h:813
void ClearAndResize(IntegerType size)
Definition: bitset.h:778
A symmetry breaker is an object that will visit a decision and create the 'symmetrical' decision in r...
This class represents a reversible bitset.
int64 word_size() const
Returns the number of 64 bit words used to store the bitset.
const RevIntSet< int > & active_words() const
Returns the set of active word indices.
int64 bit_size() const
Returns the number of bits given in the constructor of the bitset.
bool Empty() const
This method returns true if the active bitset is null.
int ActiveWordSize() const
This method returns the number of non null 64 bit words in the bitset representation.
Base operator class for operators manipulating variables.
virtual bool SkipUnchanged(int index) const
V * Var(int64 index) const
Returns the variable of given index.
void MarkChange(int64 index)
OnStart() should really be protected, but then SWIG doesn't see it.
bool ApplyChanges(Assignment *delta, Assignment *deltadelta) const
virtual void OnStart()
Called by Start() after synchronizing the operator with the current assignment.
void AddVars(const std::vector< V * > &vars)
const Val & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
void Start(const Assignment *assignment) override
This method should not be overridden.
void SetValue(int64 index, const Val &value)
std::vector< int64 > to_remove_
Block * next
SharedBoundsManager * bounds
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
GurobiMPCallbackContext * context
unsigned int uint32
static const int64 kint64max
int64_t int64
uint64_t uint64
static const int64 kint64min
const int64 offset_
Definition: interval.cc:2076
RowIndex row
Definition: markowitz.cc:175
int64 hash
Definition: matrix_utils.cc:60
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1487
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool AreAllStrictlyNegative(const std::vector< T > &values)
bool IsArrayInRange(const std::vector< IntVar * > &vars, T range_min, T range_max)
Demon * MakeConstraintDemon3(Solver *const s, T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
int64 PosIntDivUp(int64 e, int64 v)
int64 MinVarArray(const std::vector< IntVar * > &vars)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
bool AreAllBound(const std::vector< IntVar * > &vars)
bool AreAllNegative(const std::vector< T > &values)
int64 PosIntDivDown(int64 e, int64 v)
Demon * MakeConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
bool AreAllPositive(const std::vector< T > &values)
VarTypes
This enum is used internally to do dynamic typing on subclasses of integer variables.
bool AreAllBooleans(const std::vector< IntVar * > &vars)
bool AreAllLessOrEqual(const std::vector< T > &values, const T &value)
void FillValues(const std::vector< IntVar * > &vars, std::vector< int64 > *const values)
bool IsArrayConstant(const std::vector< T > &values, const T &value)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
bool IsIncreasingContiguous(const std::vector< T > &values)
uint64 Hash1(uint64 value)
Hash functions.
bool AreAllStrictlyPositive(const std::vector< T > &values)
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
int64 MaxVarArray(const std::vector< IntVar * > &vars)
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
Definition: utilities.cc:822
LocalSearchFilter * MakeUnaryDimensionFilter(Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)
bool AreAllNull(const std::vector< T > &values)
bool AreAllBoundTo(const std::vector< IntVar * > &vars, int64 value)
Returns true if all variables are assigned to 'value'.
std::string ParameterDebugString(P param)
Demon * MakeDelayedConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
VarLocalSearchOperator< SequenceVar, std::vector< int >, SequenceVarLocalSearchHandler > SequenceVarLocalSearchOperatorTemplate
LocalSearchOperator * MakeLocalSearchOperator(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Operator Factories.
bool AreAllOnes(const std::vector< T > &values)
bool IsIncreasing(const std::vector< T > &values)
static const int kUnassigned
Definition: routing.cc:638
LocalSearchFilter * MakePathStateFilter(Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)
bool IsArrayBoolean(const std::vector< T > &values)
bool AreAllGreaterOrEqual(const std::vector< T > &values, const T &value)
bool AreAllBoundOrNull(const std::vector< IntVar * > &vars, const std::vector< T > &values)
Returns true if all the variables are assigned to a single value, or if their corresponding value is ...
void AcceptUncheckedNeighbor(Search *const search)
int index
Definition: pack.cc:508
static int input(yyscan_t yyscanner)
int64 demand
Definition: resource.cc:123
int64 delta
Definition: resource.cc:1684
int64 capacity