C++ Reference

C++ Reference: Routing

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"
64 #include "ortools/base/commandlineflags.h"
65 #include "ortools/base/hash.h"
66 #include "ortools/base/integral_types.h"
67 #include "ortools/base/logging.h"
68 #include "ortools/base/map_util.h"
69 #include "ortools/base/sysinfo.h"
70 #include "ortools/base/timer.h"
72 #include "ortools/util/bitset.h"
73 #include "ortools/util/tuple_set.h"
74 #include "ortools/util/vector_map.h"
75 
76 class WallTimer;
77 
78 namespace operations_research {
79 class CPArgumentProto;
80 class CPConstraintProto;
81 class CPIntegerExpressionProto;
82 class CPIntervalVariableProto;
83 
109 class 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 
123 enum VarTypes {
132  TRACE_VAR
133 };
134 
143 #ifndef SWIG
144 template <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_;
217  NumericalRev<int> pos_;
218 };
219 
221 // TODO(user): use murmurhash.
222 inline uint64 Hash1(uint64 value) {
223  value = (~value) + (value << 21);
224  value ^= value >> 24;
225  value += (value << 3) + (value << 8);
226  value ^= value >> 14;
227  value += (value << 2) + (value << 4);
228  value ^= value >> 28;
229  value += (value << 31);
230  return value;
231 }
232 
233 inline uint64 Hash1(uint32 value) {
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 
244 inline uint64 Hash1(int64 value) { return Hash1(static_cast<uint64>(value)); }
245 
246 inline uint64 Hash1(int value) { return Hash1(static_cast<uint32>(value)); }
247 
248 inline 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 
257 template <class T>
258 uint64 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 
268 inline 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 
280 template <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 
389 class RevSwitch {
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 
428 class RevBitSet {
429  public:
430  explicit RevBitSet(int64 size);
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 
463 class 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 
504 template <class T>
505 class 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 
524 template <class T>
525 Demon* 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 
530 template <class P>
531 std::string ParameterDebugString(P param) {
532  return absl::StrCat(param);
533 }
534 
536 template <class P>
537 std::string ParameterDebugString(P* param) {
538  return param->DebugString();
539 }
540 
542 template <class T, class P>
543 class 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 
565 template <class T, class P>
566 Demon* 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 
572 template <class T, class P, class Q>
573 class 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 
604 template <class T, class P, class Q>
605 Demon* MakeConstraintDemon2(Solver* const s, T* const ct,
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 }
612 template <class T, class P, class Q, class R>
613 class 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 
647 template <class T, class P, class Q, class R>
648 Demon* MakeConstraintDemon3(Solver* const s, T* const ct,
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 
662 template <class T>
663 class 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 
668  ~DelayedCallMethod0() override {}
669 
670  void Run(Solver* const s) override { (constraint_->*method_)(); }
671 
672  Solver::DemonPriority priority() const override {
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 
687 template <class T>
688 Demon* MakeDelayedConstraintDemon0(Solver* const s, T* const ct,
689  void (T::*method)(),
690  const std::string& name) {
691  return s->RevAlloc(new DelayedCallMethod0<T>(ct, method, name));
692 }
693 
695 template <class T, class P>
696 class 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 
702  ~DelayedCallMethod1() override {}
703 
704  void Run(Solver* const s) override { (constraint_->*method_)(param1_); }
705 
706  Solver::DemonPriority priority() const override {
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 
723 template <class T, class P>
724 Demon* MakeDelayedConstraintDemon1(Solver* const s, T* const ct,
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 
731 template <class T, class P, class Q>
732 class 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 
742  ~DelayedCallMethod2() override {}
743 
744  void Run(Solver* const s) override {
745  (constraint_->*method_)(param1_, param2_);
746  }
747 
748  Solver::DemonPriority priority() const override {
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 
767 template <class T, class P, class Q>
768 Demon* MakeDelayedConstraintDemon2(Solver* const s, T* const ct,
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:
801  ~LocalSearchOperator() override {}
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 
813 template <class V, class Val, class Handler>
815  public:
817  explicit VarLocalSearchOperator(Handler var_handler)
818  : activated_(),
819  was_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  }
836  was_activated_.SetContentFromBitsetOfSameSize(activated_);
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) {
852  values_[index] = value;
853  MarkChange(index);
854  }
855  bool Activated(int64 index) const { return activated_[index]; }
856  void Activate(int64 index) {
857  activated_.Set(index);
858  MarkChange(index);
859  }
860  void Deactivate(int64 index) {
861  activated_.Clear(index);
862  MarkChange(index);
863  }
864  bool ApplyChanges(Assignment* delta, Assignment* deltadelta) const {
865  if (IsIncremental() && !cleared_) {
866  for (const int64 index : delta_changes_.PositionsSetAtLeastOnce()) {
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,
873  &assignment_indices_, index, delta);
874  }
875  } else {
876  delta->Clear();
877  for (const int64 index : changes_.PositionsSetAtLeastOnce()) {
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],
882  &assignment_indices_, index, delta);
883  }
884  }
885  }
886  return true;
887  }
888  void RevertChanges(bool incremental) {
889  cleared_ = false;
890  delta_changes_.SparseClearAll();
891  if (incremental && IsIncremental()) return;
892  cleared_ = true;
893  for (const int64 index : changes_.PositionsSetAtLeastOnce()) {
894  values_[index] = old_values_[index];
895  var_handler_.OnRevertChanges(index, values_[index]);
896  activated_.CopyBucket(was_activated_, index);
897  assignment_indices_[index] = -1;
898  }
899  changes_.SparseClearAll();
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);
910  was_activated_.Resize(size);
911  changes_.ClearAndResize(size);
912  delta_changes_.ClearAndResize(size);
913  var_handler_.OnAddVars();
914  }
915  }
916 
920  virtual void OnStart() {}
921 
924  protected:
925  void MarkChange(int64 index) {
926  delta_changes_.Set(index);
927  changes_.Set(index);
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_;
935  Bitset64<> activated_;
936  Bitset64<> was_activated_;
937  SparseBitset<> changes_;
938  SparseBitset<> delta_changes_;
939  bool cleared_;
940  Handler var_handler_;
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,
976  int64 index, int64* value);
977  void OnRevertChanges(int64 index, int64 value);
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)
1037  IntVarLocalSearchHandler(this)),
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 
1067  bool IsInverseValue(int64 index) const {
1068  DCHECK_GE(index, 0);
1069  return index <= max_inverse_value_;
1070  }
1071 
1072  int64 InverseValue(int64 index) const { return inverse_values_[index]; }
1073 
1074  int64 OldInverseValue(int64 index) const {
1075  return old_inverse_values_[index];
1076  }
1077 
1078  void SetInverseValue(int64 index, int64 value) {
1079  inverse_values_[index] = value;
1080  }
1081 
1082  void SetOldInverseValue(int64 index, int64 value) {
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);
1104  op_->SetOldInverseValue(*value, index);
1105  }
1106  return element->Activated();
1107 }
1108 
1110  int64 value) {
1111  if (op_->IsInverseValue(index)) {
1112  op_->SetInverseValue(value, index);
1113  }
1114 }
1115 
1118 
1120  public:
1121  SequenceVarLocalSearchHandler() : op_(nullptr) {}
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:
1135  SequenceVarLocalSearchOperator* const op_;
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 
1152 typedef 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) {
1173  SetValue(index, value);
1174  }
1175  void SetBackwardSequence(int64 index, const std::vector<int>& value) {
1176  backward_values_[index] = value;
1177  MarkChange(index);
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);
1205  element->SetBackwardSequence(op_->backward_values_[index]);
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;
1294  virtual int64 ModifyValue(int64 index, int64 value) = 0;
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]; }
1380  int64 BaseAlternativeNode(int i) const {
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  }
1392  int64 BaseSiblingAlternativeNode(int i) const {
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) {
1475  DCHECK_LT(from, number_of_nexts_);
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  }
1537  int64 GetActiveAlternativeNode(int node) const {
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  }
1548  int64 GetActiveAlternativeSibling(int node) const {
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 
1560  const int number_of_nexts_;
1561  const bool ignore_path_vars_;
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 
1612 template <class T>
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 
1620 class TwoOpt;
1621 class Relocate;
1622 class Exchange;
1623 class Cross;
1624 class MakeActiveOperator;
1625 class MakeInactiveOperator;
1626 class MakeChainInactiveOperator;
1627 class SwapActiveOperator;
1628 class ExtendedSwapActiveOperator;
1629 class MakeActiveAndRelocate;
1630 class RelocateAndMakeActiveOperator;
1631 class 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.
1645 class 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:
1654  friend class LocalSearchVariable;
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 };
1768  struct FilterEvent {
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);
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);
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;
1869  virtual void StartProcessingIntegerVariable(IntVar* const var) = 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);
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;
1930  virtual void EndFilterNeighbor(const LocalSearchOperator* op,
1931  bool neighbor_found) = 0;
1932  virtual void BeginAcceptNeighbor(const LocalSearchOperator* op) = 0;
1933  virtual void EndAcceptNeighbor(const LocalSearchOperator* op,
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 
1942 class 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:
1984  int value_;
1987 };
1988 
1989 class 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);
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 
2023 class 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;
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 
2073 class ModelCache {
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 
2179  virtual void InsertVoidConstraint(Constraint* const ct,
2180  VoidConstraintType type) = 0;
2181 
2184  IntVar* const var, int64 value, VarConstantConstraintType type) const = 0;
2185 
2186  virtual void InsertVarConstantConstraint(Constraint* const ct,
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 
2206  virtual void InsertExprExprConstraint(Constraint* const ct,
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,
2228  ExprConstantExpressionType type) = 0;
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,
2285  VarArrayConstantArrayExpressionType type) const = 0;
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;
2344  const std::string& arg_name) const;
2345 
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 
2368 class ModelParser : public ModelVisitor {
2369  public:
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;
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;
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;
2416  const std::string& arg_name,
2417  const std::vector<SequenceVar*>& arguments) override;
2418 
2419  protected:
2423 
2424  private:
2425  std::vector<ArgumentHolder*> holders_;
2426 };
2427 
2428 template <class T>
2429 class ArrayWithOffset : public BaseObject {
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 
2446  void SetValue(int64 index, T value) {
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 
2465 template <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 
2548 template <class T>
2549 class RevIntSet {
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 
2827 template <class T>
2828 bool 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 
2837 template <class T>
2838 bool 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 
2847 template <class T>
2848 bool AreAllOnes(const std::vector<T>& values) {
2849  return IsArrayConstant(values, T(1));
2850 }
2851 
2852 template <class T>
2853 bool AreAllNull(const std::vector<T>& values) {
2854  return IsArrayConstant(values, T(0));
2855 }
2856 
2857 template <class T>
2858 bool 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 
2867 template <class T>
2868 bool 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 
2877 template <class T>
2878 bool AreAllPositive(const std::vector<T>& values) {
2879  return AreAllGreaterOrEqual(values, T(0));
2880 }
2881 
2882 template <class T>
2883 bool AreAllNegative(const std::vector<T>& values) {
2884  return AreAllLessOrEqual(values, T(0));
2885 }
2886 
2887 template <class T>
2888 bool AreAllStrictlyPositive(const std::vector<T>& values) {
2889  return AreAllGreaterOrEqual(values, T(1));
2890 }
2891 
2892 template <class T>
2893 bool AreAllStrictlyNegative(const std::vector<T>& values) {
2894  return AreAllLessOrEqual(values, T(-1));
2895 }
2896 
2897 template <class T>
2898 bool 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 
2907 template <class T>
2908 bool 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 
2917 template <class T>
2918 bool 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 
2928 inline 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 
2937 inline bool AreAllBooleans(const std::vector<IntVar*>& vars) {
2938  return IsArrayInRange(vars, 0, 1);
2939 }
2940 
2943 template <class T>
2944 bool 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 
2955 inline 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 
2964 inline 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 
2974 inline 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 
2984 inline 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 
2993 inline int64 PosIntDivUp(int64 e, int64 v) {
2994  DCHECK_GT(v, 0);
2995  return (e < 0 || e % v == 0) ? e / v : e / v + 1;
2996 }
2997 
2998 inline int64 PosIntDivDown(int64 e, int64 v) {
2999  DCHECK_GT(v, 0);
3000  return (e >= 0 || e % v == 0) ? e / v : e / v - 1;
3001 }
3002 
3003 std::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.
3049 class PathState {
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  }
3276  Chain operator*() const {
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 {
3382  int64 min;
3383  int64 max;
3384  };
3385 
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_
Argument Holder: useful when visiting a model.
const std::vector< IntVar * > & FindIntegerVariableArrayArgumentOrDie(const std::string &arg_name) const
bool HasIntegerVariableArrayArgument(const std::string &arg_name) const
int64 FindIntegerArgumentWithDefault(const std::string &arg_name, int64 def) const
Getters.
void SetSequenceArgument(const std::string &arg_name, SequenceVar *const var)
const IntTupleSet & FindIntegerMatrixArgumentOrDie(const std::string &arg_name) const
void SetIntegerArrayArgument(const std::string &arg_name, const std::vector< int64 > &values)
void SetIntegerExpressionArgument(const std::string &arg_name, IntExpr *const expr)
void SetTypeName(const std::string &type_name)
void SetIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &vars)
const std::vector< int64 > & FindIntegerArrayArgumentOrDie(const std::string &arg_name) const
IntExpr * FindIntegerExpressionArgumentOrDie(const std::string &arg_name) const
void SetSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &vars)
void SetIntervalArgument(const std::string &arg_name, IntervalVar *const var)
void SetIntegerArgument(const std::string &arg_name, int64 value)
Setters.
const std::string & TypeName() const
Type of the argument.
void SetIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &values)
bool HasIntegerExpressionArgument(const std::string &arg_name) const
Checks if arguments exist.
void SetIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &vars)
int64 FindIntegerArgumentOrDie(const std::string &arg_name) const
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.
const IntContainer & IntVarContainer() const
const SequenceContainer & SequenceVarContainer() const
SequenceContainer * MutableSequenceVarContainer()
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)
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
A BaseObject is the root of all reversibly allocated objects.
IntVar * IsGreaterOrEqual(int64 constant) override
void RemoveInterval(int64 l, int64 u) override
This method removes the interval 'l' .
IntVarIterator * MakeHoleIterator(bool reversible) const override
Creates a hole iterator.
IntVar * IsLessOrEqual(int64 constant) override
bool Bound() const override
Returns true if the min and the max of the expression are equal.
void SetMax(int64 m) override
void WhenBound(Demon *d) override
This method attaches a demon that will be awakened when the variable is bound.
bool Contains(int64 v) const override
This method returns whether the value 'v' is in the domain of the variable.
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.
void SetRange(int64 mi, int64 ma) override
This method sets both the min and the max of the expression.
IntVar * IsEqual(int64 constant) override
IsEqual.
void RemoveValue(int64 v) override
This method removes the value 'v' from the domain of the variable.
SimpleRevFIFO< Demon * > bound_demons_
IntVar * IsDifferent(int64 constant) override
void SetMin(int64 m) override
std::string BaseName() const override
Returns a base name for automatic naming.
std::string DebugString() const override
BooleanVar(Solver *const s, const std::string &name="")
IntVarIterator * MakeDomainIterator(bool reversible) const override
Creates a domain iterator.
uint64 Size() const override
This method returns the number of values in the domain of the variable.
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.
The class IntVar is a subset of IntExpr.
int index() const
Returns the index of the variable.
The class Iterator has two direct subclasses.
void SynchronizeOnAssignment(const Assignment *assignment)
virtual void OnSynchronize(const Assignment *delta)
bool FindIndex(IntVar *const var, int64 *index) const
void Synchronize(const Assignment *assignment, const Assignment *delta) override
This method should not be overridden.
IntVarLocalSearchFilter(const std::vector< IntVar * > &vars)
void AddVars(const std::vector< IntVar * > &vars)
Add variables to "track" to the filter.
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)
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
virtual bool MakeOneNeighbor()
Creates a new neighbor.
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 ...
LocalSearchFilterManager(std::vector< FilterEvent > filter_events)
LocalSearchFilterManager(std::vector< LocalSearchFilter * > filters)
bool Accept(LocalSearchMonitor *const monitor, const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max)
Returns true iff all filters return true, and the sum of their accepted objectives is between objecti...
void Synchronize(const Assignment *assignment, const Assignment *delta)
Synchronizes all filters to assignment.
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
void Install() override
Install itself on the solver.
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
LocalSearchMonitor(Solver *const solver)
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
LocalSearchVariable AddVariable(int64 initial_min, int64 initial_max)
Implements a complete cache for model elements: expressions and constraints.
virtual IntExpr * FindExprExprConstantExpression(IntExpr *const var1, IntExpr *const var2, int64 constant, ExprExprConstantExpressionType type) const =0
Expr Expr Constant Expressions.
virtual IntExpr * FindExprConstantExpression(IntExpr *const expr, int64 value, ExprConstantExpressionType type) const =0
Expr Constant Expressions.
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 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 void InsertVarArrayConstantExpression(IntExpr *const expression, const std::vector< IntVar * > &var, int64 value, VarArrayConstantExpressionType type)=0
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 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 IntExpr * FindExprExpression(IntExpr *const expr, ExprExpressionType type) const =0
Expr Expressions.
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 Constraint * FindVoidConstraint(VoidConstraintType type) const =0
Void constraints.
virtual IntExpr * FindVarConstantConstantExpression(IntVar *const var, int64 value1, int64 value2, VarConstantConstantExpressionType type) const =0
Var Constant Constant Expressions.
virtual IntExpr * FindVarArrayConstantArrayExpression(const std::vector< IntVar * > &vars, const std::vector< int64 > &values, VarArrayConstantArrayExpressionType type) const =0
Var Array Constant Array Expressions.
ModelCache(Solver *const solver)
virtual Constraint * FindVarConstantConstraint(IntVar *const var, int64 value, VarConstantConstraintType type) const =0
Var Constant Constraints.
virtual IntExpr * FindExprExprExpression(IntExpr *const var1, IntExpr *const var2, ExprExprExpressionType type) const =0
Expr Expr Expressions.
virtual IntExpr * FindVarConstantArrayExpression(IntVar *const var, const std::vector< int64 > &values, VarConstantArrayExpressionType type) const =0
Var Constant Array Expressions.
virtual IntExpr * FindVarArrayExpression(const std::vector< IntVar * > &vars, VarArrayExpressionType type) const =0
Var Array Expressions.
virtual void InsertVarConstantArrayExpression(IntExpr *const expression, IntVar *const var, const std::vector< int64 > &values, VarConstantArrayExpressionType type)=0
virtual IntExpr * FindVarArrayConstantExpression(const std::vector< IntVar * > &vars, int64 value, VarArrayConstantExpressionType type) const =0
Var Array Constant Expressions.
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
void VisitIntervalVariable(const IntervalVar *const variable, const std::string &operation, int64 value, IntervalVar *const delegate) override
void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr) override
void BeginVisitConstraint(const std::string &type_name, const Constraint *const constraint) override
void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *const argument) override
Variables.
void VisitSequenceVariable(const SequenceVar *const variable) override
void VisitIntervalArgument(const std::string &arg_name, IntervalVar *const argument) override
Visit interval argument.
void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments) override
void VisitIntegerVariable(const IntVar *const variable, const std::string &operation, int64 value, IntVar *const delegate) override
void EndVisitConstraint(const std::string &type_name, const Constraint *const constraint) override
void EndVisitModel(const std::string &solver_name) override
void VisitSequenceArgument(const std::string &arg_name, SequenceVar *const argument) override
Visit sequence argument.
void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64 > &values) override
void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments) override
void VisitIntegerVariable(const IntVar *const variable, IntExpr *const delegate) override
void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &values) override
void BeginVisitModel(const std::string &solver_name) override
Header/footers.
void VisitIntegerArgument(const std::string &arg_name, int64 value) override
Integer arguments.
void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr) override
void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments) override
ArgumentHolder * Top() const
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.
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),...
int BaseSiblingAlternative(int i) const
Returns the alternative for the sibling of the ith base node.
const std::vector< int64 > & path_starts() const
Returns the vector of path start nodes.
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.
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 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.
bool CheckChainValidity(int64 before_chain, int64 chain_end, int64 exclude) const
Returns true if the chain is a valid path without cycles from before_chain to chain_end and does not ...
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
ChainRange Chains(int path) const
NodeRange Nodes(int path) const
const std::vector< std::pair< int, int > > & ChangedArcs() const
void ChangeNext(int node, int new_next)
PathState(int num_nodes, std::vector< int > path_start, std::vector< int > path_end)
virtual void SetMin(IntVar *const var, int64 new_min)=0
IntVar modifiers.
void Install() override
Install itself on the solver.
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
PropagationMonitor(Solver *const solver)
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'.
RevBitMatrix(int64 rows, int64 columns)
void SetToOne(Solver *const solver, int64 row, int64 column)
Sets the 'column' bit in the 'row' row.
int64 Cardinality(int row) const
Returns the number of bits set to one in the 'row' row.
bool IsCardinalityOne(int row) const
Does the 'row' bitset contains only one bit set?
void ClearAll(Solver *const solver)
Cleans all bits.
void SetToZero(Solver *const solver, int64 row, int64 column)
Erases the 'column' bit in the 'row' row.
bool IsCardinalityZero(int row) const
Is bitset of row 'row' null?
This class represents a reversible bitset.
bool IsCardinalityOne() const
Does it contains only one bit set?
bool IsSet(int64 index) const
Returns whether the 'index' bit is set.
void SetToOne(Solver *const solver, int64 index)
Sets the 'index' bit.
int64 GetFirstBit(int start) const
Gets the index of the first bit set starting from start.
void ClearAll(Solver *const solver)
Cleans all bits.
bool IsCardinalityZero() const
Is bitset null?
int64 Cardinality() const
Returns the number of bits set to one.
void SetToZero(Solver *const solver, int64 index)
Erases the 'index' bit.
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)
bool ContainsKey(const K &key) const
Returns true if the multi-map contains at least one instance of 'key'.
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.
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)
void RankFirst(Solver *const solver, int elt)
const int & operator[](int index) const
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.
void BeginFail() override
Just when the failure occurs.
void EnterSearch() override
Beginning of the search.
void RefuteDecision(Decision *const decision) override
Before refuting the decision.
void ExitSearch() override
End of the search.
virtual void OutputLine(const std::string &line)
SearchLog(Solver *const s, OptimizeVar *const obj, IntVar *const var, double scaling_factor, double offset, std::function< std::string()> display_callback, bool display_on_new_solutions_only, int period)
void BeginInitialPropagation() override
Before the initial propagation.
void NoMoreSolutions() override
When the search tree is finished.
void ApplyDecision(Decision *const decision) override
Before applying the decision.
bool AtSolution() override
This method is called when a valid solution is found.
std::string DebugString() const override
void AcceptUncheckedNeighbor() override
After accepting an unchecked neighbor during local search.
void EndInitialPropagation() override
After the initial propagation.
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)
void SetForwardSequence(const std::vector< int > &forward_sequence)
const std::vector< int > & ForwardSequence() const
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
int64 size() const
Returns the number of interval vars in the sequence.
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.
void SetBackwardSequence(int64 index, const std::vector< int > &value)
SequenceVarLocalSearchOperator(const std::vector< SequenceVar * > &vars)
void SetForwardSequence(int64 index, const std::vector< int > &value)
const std::vector< int > & OldSequence(int64 index) const
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.
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)
const T & LastValue() const
Returns the last value in the FIFO.
const T * Last() const
Returns the last item of the FIFO.
This class represents a small reversible bitset (size <= 64).
void SetToZero(Solver *const solver, int64 pos)
Erases the 'pos' bit.
bool IsCardinalityOne() const
Does it contains only one bit set?
void SetToOne(Solver *const solver, int64 pos)
Sets the 'pos' bit.
int64 GetFirstOne() const
Gets the index of the first bit set starting from 0.
bool IsCardinalityZero() const
Is bitset null?
int64 Cardinality() const
Returns the number of bits set to one.
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.
A symmetry breaker is an object that will visit a decision and create the 'symmetrical' decision in r...
void AddIntegerVariableEqualValueClause(IntVar *const var, int64 value)
void AddIntegerVariableLessOrEqualValueClause(IntVar *const var, int64 value)
void AddIntegerVariableGreaterOrEqualValueClause(IntVar *const var, int64 value)
UnaryDimensionChecker(const PathState *path_state, std::vector< Interval > path_capacity, std::vector< int > path_class, std::vector< std::vector< Interval >> demand, std::vector< Interval > node_capacity)
This class represents a reversible bitset.
bool RevSubtract(Solver *const solver, const std::vector< uint64 > &mask)
This method subtracts the mask from the active bitset.
int64 word_size() const
Returns the number of 64 bit words used to store the bitset.
bool RevAnd(Solver *const solver, const std::vector< uint64 > &mask)
This method ANDs the mask with the active bitset.
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.
const RevIntSet< int > & active_words() const
Returns the set of active word indices.
bool Intersects(const std::vector< uint64 > &mask, int *support_index)
This method returns true iff the mask and the active bitset have a non null intersection.
void Init(Solver *const solver, const std::vector< uint64 > &mask)
This methods overwrites the active bitset with the mask.
UnsortedNullableRevBitset(int bit_size)
Size is the number of bits to store in the bitset.
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
void MarkChange(int64 index)
OnStart() should really be protected, but then SWIG doesn't see it.
V * Var(int64 index) const
Returns the variable of given index.
const Val & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
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)
void Start(const Assignment *assignment) override
This method should not be overridden.
void SetValue(int64 index, const Val &value)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::string ParameterDebugString(P param)
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
bool IsArrayConstant(const std::vector< T > &values, const T &value)
bool AreAllLessOrEqual(const std::vector< T > &values, const T &value)
Demon * MakeDelayedConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
bool AreAllNegative(const std::vector< T > &values)
bool AreAllGreaterOrEqual(const std::vector< T > &values, const T &value)
bool IsIncreasing(const std::vector< T > &values)
bool AreAllStrictlyPositive(const std::vector< T > &values)
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
bool IsArrayBoolean(const std::vector< T > &values)
VarTypes
This enum is used internally to do dynamic typing on subclasses of integer variables.
Demon * MakeConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
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 ...
int64 MinVarArray(const std::vector< IntVar * > &vars)
int64 PosIntDivUp(int64 e, int64 v)
uint64 Hash1(uint64 value)
Hash functions.
void FillValues(const std::vector< IntVar * > &vars, std::vector< int64 > *const values)
bool AreAllBoundTo(const std::vector< IntVar * > &vars, int64 value)
Returns true if all variables are assigned to 'value'.
bool AreAllBooleans(const std::vector< IntVar * > &vars)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
bool AreAllStrictlyNegative(const std::vector< T > &values)
LocalSearchFilter * MakeUnaryDimensionFilter(Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)
LocalSearchOperator * MakeLocalSearchOperator(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Operator Factories.
int64 PosIntDivDown(int64 e, int64 v)
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
bool IsIncreasingContiguous(const std::vector< T > &values)
bool AreAllNull(const std::vector< T > &values)
bool AreAllPositive(const std::vector< T > &values)
int64 MaxVarArray(const std::vector< IntVar * > &vars)
Demon * MakeConstraintDemon3(Solver *const s, T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
VarLocalSearchOperator< SequenceVar, std::vector< int >, SequenceVarLocalSearchHandler > SequenceVarLocalSearchOperatorTemplate
bool IsArrayInRange(const std::vector< IntVar * > &vars, T range_min, T range_max)
bool AreAllOnes(const std::vector< T > &values)
bool AreAllBound(const std::vector< IntVar * > &vars)
LocalSearchFilter * MakePathStateFilter(Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)