1 // Copyright 2010-2021 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 /// Collection of objects used to extend the Constraint Solver library.
15 ///
16 /// This file contains a set of objects that simplifies writing extensions
17 /// of the library.
18 ///
19 /// The main objects that define extensions are:
20 /// - BaseIntExpr, the base class of all expressions that are not variables.
21 /// - SimpleRevFIFO, a reversible FIFO list with templatized values.
22 /// A reversible data structure is a data structure that reverts its
23 /// modifications when the search is going up in the search tree, usually
24 /// after a failure occurs.
25 /// - RevImmutableMultiMap, a reversible immutable multimap.
26 /// - MakeConstraintDemon<n> and MakeDelayedConstraintDemon<n> to wrap methods
27 /// of a constraint as a demon.
28 /// - RevSwitch, a reversible flip-once switch.
29 /// - SmallRevBitSet, RevBitSet, and RevBitMatrix: reversible 1D or 2D
30 /// bitsets.
31 /// - LocalSearchOperator, IntVarLocalSearchOperator, ChangeValue and
32 /// PathOperator, to create new local search operators.
33 /// - LocalSearchFilter and IntVarLocalSearchFilter, to create new local
34 /// search filters.
35 /// - BaseLns, to write Large Neighborhood Search operators.
36 /// - SymmetryBreaker, to describe model symmetries that will be broken during
37 /// search using the 'Symmetry Breaking During Search' framework
38 /// see Gent, I. P., Harvey, W., & Kelsey, T. (2002).
39 /// Groups and Constraints: Symmetry Breaking During Search.
40 /// Principles and Practice of Constraint Programming CP2002
41 /// (Vol. 2470, pp. 415-430). Springer. Retrieved from
42 /// http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.1442.
43 ///
44 /// Then, there are some internal classes that are used throughout the solver
45 /// and exposed in this file:
46 /// - SearchLog, the root class of all periodic outputs during search.
47 /// - ModelCache, A caching layer to avoid creating twice the same object.
48
49 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
50 #define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
51
52 #include <stdint.h>
53 #include <string.h>
54
55 #include <algorithm>
56 #include <functional>
57 #include <memory>
58 #include <string>
59 #include <utility>
60 #include <vector>
61
62 #include "absl/container/flat_hash_map.h"
63 #include "absl/strings/str_cat.h"
64 #include "ortools/base/integral_types.h"
65 #include "ortools/base/logging.h"
66 #include "ortools/base/timer.h"
67 #include "ortools/constraint_solver/constraint_solver.h"
68 #include "ortools/util/bitset.h"
69 #include "ortools/util/tuple_set.h"
70
71 namespace operations_research {
72
73 /// This is the base class for all expressions that are not variables.
74 /// It provides a basic 'CastToVar()' implementation.
75 ///
76 /// The class of expressions represent two types of objects: variables
77 /// and subclasses of BaseIntExpr. Variables are stateful objects that
78 /// provide a rich API (remove values, WhenBound...). On the other hand,
79 /// subclasses of BaseIntExpr represent range-only stateless objects.
80 /// That is, min(A + B) is recomputed each time as min(A) + min(B).
81 ///
82 /// Furthermore, sometimes, the propagation on an expression is not complete,
83 /// and Min(), Max() are not monotonic with respect to SetMin() and SetMax().
84 /// For instance, if A is a var with domain [0 .. 5], and B another variable
85 /// with domain [0 .. 5], then Plus(A, B) has domain [0, 10].
86 ///
87 /// If we apply SetMax(Plus(A, B), 4)), we will deduce that both A
88 /// and B have domain [0 .. 4]. In that case, Max(Plus(A, B)) is 8
89 /// and not 4. To get back monotonicity, we 'cast' the expression
90 /// into a variable using the Var() method (that will call CastToVar()
91 /// internally). The resulting variable will be stateful and monotonic.
92 ///
93 /// Finally, one should never store a pointer to a IntExpr, or
94 /// BaseIntExpr in the code. The safe code should always call Var() on an
95 /// expression built by the solver, and store the object as an IntVar*.
96 /// This is a consequence of the stateless nature of the expressions that
97 /// makes the code error-prone.
98 class LocalSearchMonitor;
99
100 class BaseIntExpr : public IntExpr {
101 public:
BaseIntExpr(Solver * const s)102 explicit BaseIntExpr(Solver* const s) : IntExpr(s), var_(nullptr) {}
~BaseIntExpr()103 ~BaseIntExpr() override {}
104
105 IntVar* Var() override;
106 virtual IntVar* CastToVar();
107
108 private:
109 IntVar* var_;
110 };
111
112 /// This enum is used internally to do dynamic typing on subclasses of integer
113 /// variables.
114 enum VarTypes {
115 UNSPECIFIED,
116 DOMAIN_INT_VAR,
117 BOOLEAN_VAR,
118 CONST_VAR,
119 VAR_ADD_CST,
120 VAR_TIMES_CST,
121 CST_SUB_VAR,
122 OPP_VAR,
123 TRACE_VAR
124 };
125
126 /// This class represent a reversible FIFO structure.
127 /// The main difference w.r.t a standard FIFO structure is that a Solver is
128 /// given as parameter to the modifiers such that the solver can store the
129 /// backtrack information
130 /// Iterator's traversing order should not be changed, as some algorithm
131 /// depend on it to be consistent.
132 /// It's main use is to store a list of demons in the various classes of
133 /// variables.
134 #ifndef SWIG
135 template <class T>
136 class SimpleRevFIFO {
137 private:
138 enum { CHUNK_SIZE = 16 }; // TODO(user): could be an extra template param
139 struct Chunk {
140 T data_[CHUNK_SIZE];
141 const Chunk* const next_;
ChunkChunk142 explicit Chunk(const Chunk* next) : next_(next) {}
143 };
144
145 public:
146 /// This iterator is not stable with respect to deletion.
147 class Iterator {
148 public:
Iterator(const SimpleRevFIFO<T> * l)149 explicit Iterator(const SimpleRevFIFO<T>* l)
150 : chunk_(l->chunks_), value_(l->Last()) {}
ok()151 bool ok() const { return (value_ != nullptr); }
152 T operator*() const { return *value_; }
153 void operator++() {
154 ++value_;
155 if (value_ == chunk_->data_ + CHUNK_SIZE) {
156 chunk_ = chunk_->next_;
157 value_ = chunk_ ? chunk_->data_ : nullptr;
158 }
159 }
160
161 private:
162 const Chunk* chunk_;
163 const T* value_;
164 };
165
SimpleRevFIFO()166 SimpleRevFIFO() : chunks_(nullptr), pos_(0) {}
167
Push(Solver * const s,T val)168 void Push(Solver* const s, T val) {
169 if (pos_.Value() == 0) {
170 Chunk* const chunk = s->UnsafeRevAlloc(new Chunk(chunks_));
171 s->SaveAndSetValue(reinterpret_cast<void**>(&chunks_),
172 reinterpret_cast<void*>(chunk));
173 pos_.SetValue(s, CHUNK_SIZE - 1);
174 } else {
175 pos_.Decr(s);
176 }
177 chunks_->data_[pos_.Value()] = val;
178 }
179
180 /// Pushes the var on top if is not a duplicate of the current top object.
PushIfNotTop(Solver * const s,T val)181 void PushIfNotTop(Solver* const s, T val) {
182 if (chunks_ == nullptr || LastValue() != val) {
183 Push(s, val);
184 }
185 }
186
187 /// Returns the last item of the FIFO.
Last()188 const T* Last() const {
189 return chunks_ ? &chunks_->data_[pos_.Value()] : nullptr;
190 }
191
MutableLast()192 T* MutableLast() { return chunks_ ? &chunks_->data_[pos_.Value()] : nullptr; }
193
194 /// Returns the last value in the FIFO.
LastValue()195 const T& LastValue() const {
196 DCHECK(chunks_);
197 return chunks_->data_[pos_.Value()];
198 }
199
200 /// Sets the last value in the FIFO.
SetLastValue(const T & v)201 void SetLastValue(const T& v) {
202 DCHECK(Last());
203 chunks_->data_[pos_.Value()] = v;
204 }
205
206 private:
207 Chunk* chunks_;
208 NumericalRev<int> pos_;
209 };
210
211 /// Hash functions
212 // TODO(user): use murmurhash.
Hash1(uint64_t value)213 inline uint64_t Hash1(uint64_t value) {
214 value = (~value) + (value << 21); /// value = (value << 21) - value - 1;
215 value ^= value >> 24;
216 value += (value << 3) + (value << 8); /// value * 265
217 value ^= value >> 14;
218 value += (value << 2) + (value << 4); /// value * 21
219 value ^= value >> 28;
220 value += (value << 31);
221 return value;
222 }
223
Hash1(uint32_t value)224 inline uint64_t Hash1(uint32_t value) {
225 uint64_t a = value;
226 a = (a + 0x7ed55d16) + (a << 12);
227 a = (a ^ 0xc761c23c) ^ (a >> 19);
228 a = (a + 0x165667b1) + (a << 5);
229 a = (a + 0xd3a2646c) ^ (a << 9);
230 a = (a + 0xfd7046c5) + (a << 3);
231 a = (a ^ 0xb55a4f09) ^ (a >> 16);
232 return a;
233 }
234
Hash1(int64_t value)235 inline uint64_t Hash1(int64_t value) {
236 return Hash1(static_cast<uint64_t>(value));
237 }
238
Hash1(int value)239 inline uint64_t Hash1(int value) { return Hash1(static_cast<uint32_t>(value)); }
240
Hash1(void * const ptr)241 inline uint64_t Hash1(void* const ptr) {
242 #if defined(__x86_64__) || defined(_M_X64) || defined(__powerpc64__) || \
243 defined(__aarch64__)
244 return Hash1(reinterpret_cast<uint64_t>(ptr));
245 #else
246 return Hash1(reinterpret_cast<uint32_t>(ptr));
247 #endif
248 }
249
250 template <class T>
Hash1(const std::vector<T * > & ptrs)251 uint64_t Hash1(const std::vector<T*>& ptrs) {
252 if (ptrs.empty()) return 0;
253 if (ptrs.size() == 1) return Hash1(ptrs[0]);
254 uint64_t hash = Hash1(ptrs[0]);
255 for (int i = 1; i < ptrs.size(); ++i) {
256 hash = hash * i + Hash1(ptrs[i]);
257 }
258 return hash;
259 }
260
Hash1(const std::vector<int64_t> & ptrs)261 inline uint64_t Hash1(const std::vector<int64_t>& ptrs) {
262 if (ptrs.empty()) return 0;
263 if (ptrs.size() == 1) return Hash1(ptrs[0]);
264 uint64_t hash = Hash1(ptrs[0]);
265 for (int i = 1; i < ptrs.size(); ++i) {
266 hash = hash * i + Hash1(ptrs[i]);
267 }
268 return hash;
269 }
270
271 /// Reversible Immutable MultiMap class.
272 /// Represents an immutable multi-map that backtracks with the solver.
273 template <class K, class V>
274 class RevImmutableMultiMap {
275 public:
RevImmutableMultiMap(Solver * const solver,int initial_size)276 RevImmutableMultiMap(Solver* const solver, int initial_size)
277 : solver_(solver),
278 array_(solver->UnsafeRevAllocArray(new Cell*[initial_size])),
279 size_(initial_size),
280 num_items_(0) {
281 memset(array_, 0, sizeof(*array_) * size_.Value());
282 }
283
~RevImmutableMultiMap()284 ~RevImmutableMultiMap() {}
285
num_items()286 int num_items() const { return num_items_.Value(); }
287
288 /// Returns true if the multi-map contains at least one instance of 'key'.
ContainsKey(const K & key)289 bool ContainsKey(const K& key) const {
290 uint64_t code = Hash1(key) % size_.Value();
291 Cell* tmp = array_[code];
292 while (tmp) {
293 if (tmp->key() == key) {
294 return true;
295 }
296 tmp = tmp->next();
297 }
298 return false;
299 }
300
301 /// Returns one value attached to 'key', or 'default_value' if 'key'
302 /// is not in the multi-map. The actual value returned if more than one
303 /// values is attached to the same key is not specified.
FindWithDefault(const K & key,const V & default_value)304 const V& FindWithDefault(const K& key, const V& default_value) const {
305 uint64_t code = Hash1(key) % size_.Value();
306 Cell* tmp = array_[code];
307 while (tmp) {
308 if (tmp->key() == key) {
309 return tmp->value();
310 }
311 tmp = tmp->next();
312 }
313 return default_value;
314 }
315
316 /// Inserts (key, value) in the multi-map.
Insert(const K & key,const V & value)317 void Insert(const K& key, const V& value) {
318 const int position = Hash1(key) % size_.Value();
319 Cell* const cell =
320 solver_->UnsafeRevAlloc(new Cell(key, value, array_[position]));
321 solver_->SaveAndSetValue(reinterpret_cast<void**>(&array_[position]),
322 reinterpret_cast<void*>(cell));
323 num_items_.Incr(solver_);
324 if (num_items_.Value() > 2 * size_.Value()) {
325 Double();
326 }
327 }
328
329 private:
330 class Cell {
331 public:
Cell(const K & key,const V & value,Cell * const next)332 Cell(const K& key, const V& value, Cell* const next)
333 : key_(key), value_(value), next_(next) {}
334
SetRevNext(Solver * const solver,Cell * const next)335 void SetRevNext(Solver* const solver, Cell* const next) {
336 solver->SaveAndSetValue(reinterpret_cast<void**>(&next_),
337 reinterpret_cast<void*>(next));
338 }
339
next()340 Cell* next() const { return next_; }
341
key()342 const K& key() const { return key_; }
343
value()344 const V& value() const { return value_; }
345
346 private:
347 const K key_;
348 const V value_;
349 Cell* next_;
350 };
351
Double()352 void Double() {
353 Cell** const old_cell_array = array_;
354 const int old_size = size_.Value();
355 size_.SetValue(solver_, size_.Value() * 2);
356 solver_->SaveAndSetValue(
357 reinterpret_cast<void**>(&array_),
358 reinterpret_cast<void*>(
359 solver_->UnsafeRevAllocArray(new Cell*[size_.Value()])));
360 memset(array_, 0, size_.Value() * sizeof(*array_));
361 for (int i = 0; i < old_size; ++i) {
362 Cell* tmp = old_cell_array[i];
363 while (tmp != nullptr) {
364 Cell* const to_reinsert = tmp;
365 tmp = tmp->next();
366 const uint64_t new_position = Hash1(to_reinsert->key()) % size_.Value();
367 to_reinsert->SetRevNext(solver_, array_[new_position]);
368 solver_->SaveAndSetValue(
369 reinterpret_cast<void**>(&array_[new_position]),
370 reinterpret_cast<void*>(to_reinsert));
371 }
372 }
373 }
374
375 Solver* const solver_;
376 Cell** array_;
377 NumericalRev<int> size_;
378 NumericalRev<int> num_items_;
379 };
380
381 /// A reversible switch that can switch once from false to true.
382 class RevSwitch {
383 public:
RevSwitch()384 RevSwitch() : value_(false) {}
385
Switched()386 bool Switched() const { return value_; }
387
Switch(Solver * const solver)388 void Switch(Solver* const solver) { solver->SaveAndSetValue(&value_, true); }
389
390 private:
391 bool value_;
392 };
393
394 /// This class represents a small reversible bitset (size <= 64).
395 /// This class is useful to maintain supports.
396 class SmallRevBitSet {
397 public:
398 explicit SmallRevBitSet(int64_t size);
399 /// Sets the 'pos' bit.
400 void SetToOne(Solver* const solver, int64_t pos);
401 /// Erases the 'pos' bit.
402 void SetToZero(Solver* const solver, int64_t pos);
403 /// Returns the number of bits set to one.
404 int64_t Cardinality() const;
405 /// Is bitset null?
IsCardinalityZero()406 bool IsCardinalityZero() const { return bits_.Value() == uint64_t{0}; }
407 /// Does it contains only one bit set?
IsCardinalityOne()408 bool IsCardinalityOne() const {
409 return (bits_.Value() != 0) && !(bits_.Value() & (bits_.Value() - 1));
410 }
411 /// Gets the index of the first bit set starting from 0.
412 /// It returns -1 if the bitset is empty.
413 int64_t GetFirstOne() const;
414
415 private:
416 Rev<uint64_t> bits_;
417 };
418
419 /// This class represents a reversible bitset.
420 /// This class is useful to maintain supports.
421 class RevBitSet {
422 public:
423 explicit RevBitSet(int64_t size);
424 ~RevBitSet();
425
426 /// Sets the 'index' bit.
427 void SetToOne(Solver* const solver, int64_t index);
428 /// Erases the 'index' bit.
429 void SetToZero(Solver* const solver, int64_t index);
430 /// Returns whether the 'index' bit is set.
431 bool IsSet(int64_t index) const;
432 /// Returns the number of bits set to one.
433 int64_t Cardinality() const;
434 /// Is bitset null?
435 bool IsCardinalityZero() const;
436 /// Does it contains only one bit set?
437 bool IsCardinalityOne() const;
438 /// Gets the index of the first bit set starting from start.
439 /// It returns -1 if the bitset is empty after start.
440 int64_t GetFirstBit(int start) const;
441 /// Cleans all bits.
442 void ClearAll(Solver* const solver);
443
444 friend class RevBitMatrix;
445
446 private:
447 /// Save the offset's part of the bitset.
448 void Save(Solver* const solver, int offset);
449 const int64_t size_;
450 const int64_t length_;
451 uint64_t* bits_;
452 uint64_t* stamps_;
453 };
454
455 /// Matrix version of the RevBitSet class.
456 class RevBitMatrix : private RevBitSet {
457 public:
458 RevBitMatrix(int64_t rows, int64_t columns);
459 ~RevBitMatrix();
460
461 /// Sets the 'column' bit in the 'row' row.
462 void SetToOne(Solver* const solver, int64_t row, int64_t column);
463 /// Erases the 'column' bit in the 'row' row.
464 void SetToZero(Solver* const solver, int64_t row, int64_t column);
465 /// Returns whether the 'column' bit in the 'row' row is set.
IsSet(int64_t row,int64_t column)466 bool IsSet(int64_t row, int64_t column) const {
467 DCHECK_GE(row, 0);
468 DCHECK_LT(row, rows_);
469 DCHECK_GE(column, 0);
470 DCHECK_LT(column, columns_);
471 return RevBitSet::IsSet(row * columns_ + column);
472 }
473 /// Returns the number of bits set to one in the 'row' row.
474 int64_t Cardinality(int row) const;
475 /// Is bitset of row 'row' null?
476 bool IsCardinalityZero(int row) const;
477 /// Does the 'row' bitset contains only one bit set?
478 bool IsCardinalityOne(int row) const;
479 /// Returns the first bit in the row 'row' which position is >= 'start'.
480 /// It returns -1 if there are none.
481 int64_t GetFirstBit(int row, int start) const;
482 /// Cleans all bits.
483 void ClearAll(Solver* const solver);
484
485 private:
486 const int64_t rows_;
487 const int64_t columns_;
488 };
489
490 /// @{
491 /// These methods represent generic demons that will call back a
492 /// method on the constraint during their Run method.
493 /// This way, all propagation methods are members of the constraint class,
494 /// and demons are just proxies with a priority of NORMAL_PRIORITY.
495
496 /// Demon proxy to a method on the constraint with no arguments.
497 template <class T>
498 class CallMethod0 : public Demon {
499 public:
CallMethod0(T * const ct,void (T::* method)(),const std::string & name)500 CallMethod0(T* const ct, void (T::*method)(), const std::string& name)
501 : constraint_(ct), method_(method), name_(name) {}
502
~CallMethod0()503 ~CallMethod0() override {}
504
Run(Solver * const s)505 void Run(Solver* const s) override { (constraint_->*method_)(); }
506
DebugString()507 std::string DebugString() const override {
508 return "CallMethod_" + name_ + "(" + constraint_->DebugString() + ")";
509 }
510
511 private:
512 T* const constraint_;
513 void (T::*const method_)();
514 const std::string name_;
515 };
516
517 template <class T>
MakeConstraintDemon0(Solver * const s,T * const ct,void (T::* method)(),const std::string & name)518 Demon* MakeConstraintDemon0(Solver* const s, T* const ct, void (T::*method)(),
519 const std::string& name) {
520 return s->RevAlloc(new CallMethod0<T>(ct, method, name));
521 }
522
523 template <class P>
ParameterDebugString(P param)524 std::string ParameterDebugString(P param) {
525 return absl::StrCat(param);
526 }
527
528 /// Support limited to pointers to classes which define DebugString().
529 template <class P>
ParameterDebugString(P * param)530 std::string ParameterDebugString(P* param) {
531 return param->DebugString();
532 }
533
534 /// Demon proxy to a method on the constraint with one argument.
535 template <class T, class P>
536 class CallMethod1 : public Demon {
537 public:
CallMethod1(T * const ct,void (T::* method)(P),const std::string & name,P param1)538 CallMethod1(T* const ct, void (T::*method)(P), const std::string& name,
539 P param1)
540 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
541
~CallMethod1()542 ~CallMethod1() override {}
543
Run(Solver * const s)544 void Run(Solver* const s) override { (constraint_->*method_)(param1_); }
545
DebugString()546 std::string DebugString() const override {
547 return absl::StrCat("CallMethod_", name_, "(", constraint_->DebugString(),
548 ", ", ParameterDebugString(param1_), ")");
549 }
550
551 private:
552 T* const constraint_;
553 void (T::*const method_)(P);
554 const std::string name_;
555 P param1_;
556 };
557
558 template <class T, class P>
MakeConstraintDemon1(Solver * const s,T * const ct,void (T::* method)(P),const std::string & name,P param1)559 Demon* MakeConstraintDemon1(Solver* const s, T* const ct, void (T::*method)(P),
560 const std::string& name, P param1) {
561 return s->RevAlloc(new CallMethod1<T, P>(ct, method, name, param1));
562 }
563
564 /// Demon proxy to a method on the constraint with two arguments.
565 template <class T, class P, class Q>
566 class CallMethod2 : public Demon {
567 public:
CallMethod2(T * const ct,void (T::* method)(P,Q),const std::string & name,P param1,Q param2)568 CallMethod2(T* const ct, void (T::*method)(P, Q), const std::string& name,
569 P param1, Q param2)
570 : constraint_(ct),
571 method_(method),
572 name_(name),
573 param1_(param1),
574 param2_(param2) {}
575
~CallMethod2()576 ~CallMethod2() override {}
577
Run(Solver * const s)578 void Run(Solver* const s) override {
579 (constraint_->*method_)(param1_, param2_);
580 }
581
DebugString()582 std::string DebugString() const override {
583 return absl::StrCat(absl::StrCat("CallMethod_", name_),
584 absl::StrCat("(", constraint_->DebugString()),
585 absl::StrCat(", ", ParameterDebugString(param1_)),
586 absl::StrCat(", ", ParameterDebugString(param2_), ")"));
587 }
588
589 private:
590 T* const constraint_;
591 void (T::*const method_)(P, Q);
592 const std::string name_;
593 P param1_;
594 Q param2_;
595 };
596
597 template <class T, class P, class Q>
MakeConstraintDemon2(Solver * const s,T * const ct,void (T::* method)(P,Q),const std::string & name,P param1,Q param2)598 Demon* MakeConstraintDemon2(Solver* const s, T* const ct,
599 void (T::*method)(P, Q), const std::string& name,
600 P param1, Q param2) {
601 return s->RevAlloc(
602 new CallMethod2<T, P, Q>(ct, method, name, param1, param2));
603 }
604 /// Demon proxy to a method on the constraint with three arguments.
605 template <class T, class P, class Q, class R>
606 class CallMethod3 : public Demon {
607 public:
CallMethod3(T * const ct,void (T::* method)(P,Q,R),const std::string & name,P param1,Q param2,R param3)608 CallMethod3(T* const ct, void (T::*method)(P, Q, R), const std::string& name,
609 P param1, Q param2, R param3)
610 : constraint_(ct),
611 method_(method),
612 name_(name),
613 param1_(param1),
614 param2_(param2),
615 param3_(param3) {}
616
~CallMethod3()617 ~CallMethod3() override {}
618
Run(Solver * const s)619 void Run(Solver* const s) override {
620 (constraint_->*method_)(param1_, param2_, param3_);
621 }
622
DebugString()623 std::string DebugString() const override {
624 return absl::StrCat(absl::StrCat("CallMethod_", name_),
625 absl::StrCat("(", constraint_->DebugString()),
626 absl::StrCat(", ", ParameterDebugString(param1_)),
627 absl::StrCat(", ", ParameterDebugString(param2_)),
628 absl::StrCat(", ", ParameterDebugString(param3_), ")"));
629 }
630
631 private:
632 T* const constraint_;
633 void (T::*const method_)(P, Q, R);
634 const std::string name_;
635 P param1_;
636 Q param2_;
637 R param3_;
638 };
639
640 template <class T, class P, class Q, class R>
MakeConstraintDemon3(Solver * const s,T * const ct,void (T::* method)(P,Q,R),const std::string & name,P param1,Q param2,R param3)641 Demon* MakeConstraintDemon3(Solver* const s, T* const ct,
642 void (T::*method)(P, Q, R), const std::string& name,
643 P param1, Q param2, R param3) {
644 return s->RevAlloc(
645 new CallMethod3<T, P, Q, R>(ct, method, name, param1, param2, param3));
646 }
647 /// @}
648
649 /// @{
650 /// These methods represents generic demons that will call back a
651 /// method on the constraint during their Run method. This demon will
652 /// have a priority DELAYED_PRIORITY.
653
654 /// Low-priority demon proxy to a method on the constraint with no arguments.
655 template <class T>
656 class DelayedCallMethod0 : public Demon {
657 public:
DelayedCallMethod0(T * const ct,void (T::* method)(),const std::string & name)658 DelayedCallMethod0(T* const ct, void (T::*method)(), const std::string& name)
659 : constraint_(ct), method_(method), name_(name) {}
660
~DelayedCallMethod0()661 ~DelayedCallMethod0() override {}
662
Run(Solver * const s)663 void Run(Solver* const s) override { (constraint_->*method_)(); }
664
priority()665 Solver::DemonPriority priority() const override {
666 return Solver::DELAYED_PRIORITY;
667 }
668
DebugString()669 std::string DebugString() const override {
670 return "DelayedCallMethod_" + name_ + "(" + constraint_->DebugString() +
671 ")";
672 }
673
674 private:
675 T* const constraint_;
676 void (T::*const method_)();
677 const std::string name_;
678 };
679
680 template <class T>
MakeDelayedConstraintDemon0(Solver * const s,T * const ct,void (T::* method)(),const std::string & name)681 Demon* MakeDelayedConstraintDemon0(Solver* const s, T* const ct,
682 void (T::*method)(),
683 const std::string& name) {
684 return s->RevAlloc(new DelayedCallMethod0<T>(ct, method, name));
685 }
686
687 /// Low-priority demon proxy to a method on the constraint with one argument.
688 template <class T, class P>
689 class DelayedCallMethod1 : public Demon {
690 public:
DelayedCallMethod1(T * const ct,void (T::* method)(P),const std::string & name,P param1)691 DelayedCallMethod1(T* const ct, void (T::*method)(P), const std::string& name,
692 P param1)
693 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
694
~DelayedCallMethod1()695 ~DelayedCallMethod1() override {}
696
Run(Solver * const s)697 void Run(Solver* const s) override { (constraint_->*method_)(param1_); }
698
priority()699 Solver::DemonPriority priority() const override {
700 return Solver::DELAYED_PRIORITY;
701 }
702
DebugString()703 std::string DebugString() const override {
704 return absl::StrCat("DelayedCallMethod_", name_, "(",
705 constraint_->DebugString(), ", ",
706 ParameterDebugString(param1_), ")");
707 }
708
709 private:
710 T* const constraint_;
711 void (T::*const method_)(P);
712 const std::string name_;
713 P param1_;
714 };
715
716 template <class T, class P>
MakeDelayedConstraintDemon1(Solver * const s,T * const ct,void (T::* method)(P),const std::string & name,P param1)717 Demon* MakeDelayedConstraintDemon1(Solver* const s, T* const ct,
718 void (T::*method)(P),
719 const std::string& name, P param1) {
720 return s->RevAlloc(new DelayedCallMethod1<T, P>(ct, method, name, param1));
721 }
722
723 /// Low-priority demon proxy to a method on the constraint with two arguments.
724 template <class T, class P, class Q>
725 class DelayedCallMethod2 : public Demon {
726 public:
DelayedCallMethod2(T * const ct,void (T::* method)(P,Q),const std::string & name,P param1,Q param2)727 DelayedCallMethod2(T* const ct, void (T::*method)(P, Q),
728 const std::string& name, P param1, Q param2)
729 : constraint_(ct),
730 method_(method),
731 name_(name),
732 param1_(param1),
733 param2_(param2) {}
734
~DelayedCallMethod2()735 ~DelayedCallMethod2() override {}
736
Run(Solver * const s)737 void Run(Solver* const s) override {
738 (constraint_->*method_)(param1_, param2_);
739 }
740
priority()741 Solver::DemonPriority priority() const override {
742 return Solver::DELAYED_PRIORITY;
743 }
744
DebugString()745 std::string DebugString() const override {
746 return absl::StrCat(absl::StrCat("DelayedCallMethod_", name_),
747 absl::StrCat("(", constraint_->DebugString()),
748 absl::StrCat(", ", ParameterDebugString(param1_)),
749 absl::StrCat(", ", ParameterDebugString(param2_), ")"));
750 }
751
752 private:
753 T* const constraint_;
754 void (T::*const method_)(P, Q);
755 const std::string name_;
756 P param1_;
757 Q param2_;
758 };
759
760 template <class T, class P, class Q>
MakeDelayedConstraintDemon2(Solver * const s,T * const ct,void (T::* method)(P,Q),const std::string & name,P param1,Q param2)761 Demon* MakeDelayedConstraintDemon2(Solver* const s, T* const ct,
762 void (T::*method)(P, Q),
763 const std::string& name, P param1,
764 Q param2) {
765 return s->RevAlloc(
766 new DelayedCallMethod2<T, P, Q>(ct, method, name, param1, param2));
767 }
768 /// @}
769
770 #endif // !defined(SWIG)
771
772 /// The base class for all local search operators.
773 ///
774 /// A local search operator is an object that defines the neighborhood of a
775 /// solution. In other words, a neighborhood is the set of solutions which can
776 /// be reached from a given solution using an operator.
777 ///
778 /// The behavior of the LocalSearchOperator class is similar to iterators.
779 /// The operator is synchronized with an assignment (gives the
780 /// current values of the variables); this is done in the Start() method.
781 ///
782 /// Then one can iterate over the neighbors using the MakeNextNeighbor method.
783 /// This method returns an assignment which represents the incremental changes
784 /// to the current solution. It also returns a second assignment representing
785 /// the changes to the last solution defined by the neighborhood operator; this
786 /// assignment is empty if the neighborhood operator cannot track this
787 /// information.
788 ///
789 // TODO(user): rename Start to Synchronize ?
790 // TODO(user): decouple the iterating from the defining of a neighbor.
791 class LocalSearchOperator : public BaseObject {
792 public:
LocalSearchOperator()793 LocalSearchOperator() {}
~LocalSearchOperator()794 ~LocalSearchOperator() override {}
795 virtual bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) = 0;
796 virtual void Start(const Assignment* assignment) = 0;
Reset()797 virtual void Reset() {}
798 #ifndef SWIG
Self()799 virtual const LocalSearchOperator* Self() const { return this; }
800 #endif // SWIG
HasFragments()801 virtual bool HasFragments() const { return false; }
HoldsDelta()802 virtual bool HoldsDelta() const { return false; }
803 };
804
805 /// Base operator class for operators manipulating variables.
806 template <class V, class Val, class Handler>
807 class VarLocalSearchOperator : public LocalSearchOperator {
808 public:
VarLocalSearchOperator()809 VarLocalSearchOperator() : activated_(), was_activated_(), cleared_(true) {}
VarLocalSearchOperator(Handler var_handler)810 explicit VarLocalSearchOperator(Handler var_handler)
811 : activated_(),
812 was_activated_(),
813 cleared_(true),
814 var_handler_(var_handler) {}
~VarLocalSearchOperator()815 ~VarLocalSearchOperator() override {}
HoldsDelta()816 bool HoldsDelta() const override { return true; }
817 /// This method should not be overridden. Override OnStart() instead which is
818 /// called before exiting this method.
Start(const Assignment * assignment)819 void Start(const Assignment* assignment) override {
820 const int size = Size();
821 CHECK_LE(size, assignment->Size())
822 << "Assignment contains fewer variables than operator";
823 for (int i = 0; i < size; ++i) {
824 activated_.Set(i, var_handler_.ValueFromAssignment(*assignment, vars_[i],
825 i, &values_[i]));
826 }
827 prev_values_ = old_values_;
828 old_values_ = values_;
829 was_activated_.SetContentFromBitsetOfSameSize(activated_);
830 OnStart();
831 }
IsIncremental()832 virtual bool IsIncremental() const { return false; }
Size()833 int Size() const { return vars_.size(); }
834 /// Returns the value in the current assignment of the variable of given
835 /// index.
Value(int64_t index)836 const Val& Value(int64_t index) const {
837 DCHECK_LT(index, vars_.size());
838 return values_[index];
839 }
840 /// Returns the variable of given index.
Var(int64_t index)841 V* Var(int64_t index) const { return vars_[index]; }
SkipUnchanged(int index)842 virtual bool SkipUnchanged(int index) const { return false; }
OldValue(int64_t index)843 const Val& OldValue(int64_t index) const { return old_values_[index]; }
SetValue(int64_t index,const Val & value)844 void SetValue(int64_t index, const Val& value) {
845 values_[index] = value;
846 MarkChange(index);
847 }
Activated(int64_t index)848 bool Activated(int64_t index) const { return activated_[index]; }
Activate(int64_t index)849 void Activate(int64_t index) {
850 activated_.Set(index);
851 MarkChange(index);
852 }
Deactivate(int64_t index)853 void Deactivate(int64_t index) {
854 activated_.Clear(index);
855 MarkChange(index);
856 }
ApplyChanges(Assignment * delta,Assignment * deltadelta)857 bool ApplyChanges(Assignment* delta, Assignment* deltadelta) const {
858 if (IsIncremental() && !cleared_) {
859 for (const int64_t index : delta_changes_.PositionsSetAtLeastOnce()) {
860 V* var = Var(index);
861 const Val& value = Value(index);
862 const bool activated = activated_[index];
863 var_handler_.AddToAssignment(var, value, activated, nullptr, index,
864 deltadelta);
865 var_handler_.AddToAssignment(var, value, activated,
866 &assignment_indices_, index, delta);
867 }
868 } else {
869 delta->Clear();
870 for (const int64_t index : changes_.PositionsSetAtLeastOnce()) {
871 const Val& value = Value(index);
872 const bool activated = activated_[index];
873 if (!activated || value != OldValue(index) || !SkipUnchanged(index)) {
874 var_handler_.AddToAssignment(Var(index), value, activated_[index],
875 &assignment_indices_, index, delta);
876 }
877 }
878 }
879 return true;
880 }
RevertChanges(bool incremental)881 void RevertChanges(bool incremental) {
882 cleared_ = false;
883 delta_changes_.SparseClearAll();
884 if (incremental && IsIncremental()) return;
885 cleared_ = true;
886 for (const int64_t index : changes_.PositionsSetAtLeastOnce()) {
887 values_[index] = old_values_[index];
888 var_handler_.OnRevertChanges(index, values_[index]);
889 activated_.CopyBucket(was_activated_, index);
890 assignment_indices_[index] = -1;
891 }
892 changes_.SparseClearAll();
893 }
AddVars(const std::vector<V * > & vars)894 void AddVars(const std::vector<V*>& vars) {
895 if (!vars.empty()) {
896 vars_.insert(vars_.end(), vars.begin(), vars.end());
897 const int64_t size = Size();
898 values_.resize(size);
899 old_values_.resize(size);
900 prev_values_.resize(size);
901 assignment_indices_.resize(size, -1);
902 activated_.Resize(size);
903 was_activated_.Resize(size);
904 changes_.ClearAndResize(size);
905 delta_changes_.ClearAndResize(size);
906 var_handler_.OnAddVars();
907 }
908 }
909
910 /// Called by Start() after synchronizing the operator with the current
911 /// assignment. Should be overridden instead of Start() to avoid calling
912 /// VarLocalSearchOperator::Start explicitly.
OnStart()913 virtual void OnStart() {}
914
915 /// OnStart() should really be protected, but then SWIG doesn't see it. So we
916 /// make it public, but only subclasses should access to it (to override it).
917 protected:
MarkChange(int64_t index)918 void MarkChange(int64_t index) {
919 delta_changes_.Set(index);
920 changes_.Set(index);
921 }
922
923 std::vector<V*> vars_;
924 std::vector<Val> values_;
925 std::vector<Val> old_values_;
926 std::vector<Val> prev_values_;
927 mutable std::vector<int> assignment_indices_;
928 Bitset64<> activated_;
929 Bitset64<> was_activated_;
930 SparseBitset<> changes_;
931 SparseBitset<> delta_changes_;
932 bool cleared_;
933 Handler var_handler_;
934 };
935
936 /// Base operator class for operators manipulating IntVars.
937 class IntVarLocalSearchOperator;
938
939 class IntVarLocalSearchHandler {
940 public:
IntVarLocalSearchHandler()941 IntVarLocalSearchHandler() : op_(nullptr) {}
IntVarLocalSearchHandler(const IntVarLocalSearchHandler & other)942 IntVarLocalSearchHandler(const IntVarLocalSearchHandler& other)
943 : op_(other.op_) {}
IntVarLocalSearchHandler(IntVarLocalSearchOperator * op)944 explicit IntVarLocalSearchHandler(IntVarLocalSearchOperator* op) : op_(op) {}
AddToAssignment(IntVar * var,int64_t value,bool active,std::vector<int> * assignment_indices,int64_t index,Assignment * assignment)945 void AddToAssignment(IntVar* var, int64_t value, bool active,
946 std::vector<int>* assignment_indices, int64_t index,
947 Assignment* assignment) const {
948 Assignment::IntContainer* const container =
949 assignment->MutableIntVarContainer();
950 IntVarElement* element = nullptr;
951 if (assignment_indices != nullptr) {
952 if ((*assignment_indices)[index] == -1) {
953 (*assignment_indices)[index] = container->Size();
954 element = assignment->FastAdd(var);
955 } else {
956 element = container->MutableElement((*assignment_indices)[index]);
957 }
958 } else {
959 element = assignment->FastAdd(var);
960 }
961 if (active) {
962 element->SetValue(value);
963 element->Activate();
964 } else {
965 element->Deactivate();
966 }
967 }
968 bool ValueFromAssignment(const Assignment& assignment, IntVar* var,
969 int64_t index, int64_t* value);
970 void OnRevertChanges(int64_t index, int64_t value);
OnAddVars()971 void OnAddVars() {}
972
973 private:
974 IntVarLocalSearchOperator* const op_;
975 };
976
977 /// Specialization of LocalSearchOperator built from an array of IntVars
978 /// which specifies the scope of the operator.
979 /// This class also takes care of storing current variable values in Start(),
980 /// keeps track of changes done by the operator and builds the delta.
981 /// The Deactivate() method can be used to perform Large Neighborhood Search.
982
983 #ifdef SWIG
984 /// Unfortunately, we must put this code here and not in
985 /// */constraint_solver.i, because it must be parsed by SWIG before the
986 /// derived C++ class.
987 // TODO(user): find a way to move this code back to the .i file, where it
988 /// belongs.
989 /// In python, we use an allow-list to expose the API. This list must also
990 /// be extended here.
991 #if defined(SWIGPYTHON)
992 // clang-format off
993 %unignore VarLocalSearchOperator<IntVar, int64_t,
994 IntVarLocalSearchHandler>::Size;
995 %unignore VarLocalSearchOperator<IntVar, int64_t,
996 IntVarLocalSearchHandler>::Value;
997 %unignore VarLocalSearchOperator<IntVar, int64_t,
998 IntVarLocalSearchHandler>::OldValue;
999 %unignore VarLocalSearchOperator<IntVar, int64_t,
1000 IntVarLocalSearchHandler>::SetValue;
1001 %feature("director") VarLocalSearchOperator<IntVar, int64_t,
1002 IntVarLocalSearchHandler>::IsIncremental;
1003 %feature("director") VarLocalSearchOperator<IntVar, int64_t,
1004 IntVarLocalSearchHandler>::OnStart;
1005 %unignore VarLocalSearchOperator<IntVar, int64_t,
1006 IntVarLocalSearchHandler>::IsIncremental;
1007 %unignore VarLocalSearchOperator<IntVar, int64_t,
1008 IntVarLocalSearchHandler>::OnStart;
1009 // clang-format on
1010 #endif // SWIGPYTHON
1011
1012 // clang-format off
1013 %rename(IntVarLocalSearchOperatorTemplate)
1014 VarLocalSearchOperator<IntVar, int64_t, IntVarLocalSearchHandler>;
1015 %template(IntVarLocalSearchOperatorTemplate)
1016 VarLocalSearchOperator<IntVar, int64_t, IntVarLocalSearchHandler>;
1017 // clang-format on
1018 #endif // SWIG
1019
1020 class IntVarLocalSearchOperator
1021 : public VarLocalSearchOperator<IntVar, int64_t, IntVarLocalSearchHandler> {
1022 public:
IntVarLocalSearchOperator()1023 IntVarLocalSearchOperator() : max_inverse_value_(-1) {}
1024 // If keep_inverse_values is true, assumes that vars models an injective
1025 // function f with domain [0, vars.size()) in which case the operator will
1026 // maintain the inverse function.
1027 explicit IntVarLocalSearchOperator(const std::vector<IntVar*>& vars,
1028 bool keep_inverse_values = false)
1029 : VarLocalSearchOperator<IntVar, int64_t, IntVarLocalSearchHandler>(
IntVarLocalSearchHandler(this)1030 IntVarLocalSearchHandler(this)),
1031 max_inverse_value_(keep_inverse_values ? vars.size() - 1 : -1) {
1032 AddVars(vars);
1033 if (keep_inverse_values) {
1034 int64_t max_value = -1;
1035 for (const IntVar* const var : vars) {
1036 max_value = std::max(max_value, var->Max());
1037 }
1038 inverse_values_.resize(max_value + 1, -1);
1039 old_inverse_values_.resize(max_value + 1, -1);
1040 }
1041 }
~IntVarLocalSearchOperator()1042 ~IntVarLocalSearchOperator() override {}
1043 /// Redefines MakeNextNeighbor to export a simpler interface. The calls to
1044 /// ApplyChanges() and RevertChanges() are factored in this method, hiding
1045 /// both delta and deltadelta from subclasses which only need to override
1046 /// MakeOneNeighbor().
1047 /// Therefore this method should not be overridden. Override MakeOneNeighbor()
1048 /// instead.
1049 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
1050
1051 protected:
1052 friend class IntVarLocalSearchHandler;
1053
1054 /// Creates a new neighbor. It returns false when the neighborhood is
1055 /// completely explored.
1056 // TODO(user): make it pure virtual, implies porting all apps overriding
1057 /// MakeNextNeighbor() in a subclass of IntVarLocalSearchOperator.
1058 virtual bool MakeOneNeighbor();
1059
IsInverseValue(int64_t index)1060 bool IsInverseValue(int64_t index) const {
1061 DCHECK_GE(index, 0);
1062 return index <= max_inverse_value_;
1063 }
1064
InverseValue(int64_t index)1065 int64_t InverseValue(int64_t index) const { return inverse_values_[index]; }
1066
OldInverseValue(int64_t index)1067 int64_t OldInverseValue(int64_t index) const {
1068 return old_inverse_values_[index];
1069 }
1070
SetInverseValue(int64_t index,int64_t value)1071 void SetInverseValue(int64_t index, int64_t value) {
1072 inverse_values_[index] = value;
1073 }
1074
SetOldInverseValue(int64_t index,int64_t value)1075 void SetOldInverseValue(int64_t index, int64_t value) {
1076 old_inverse_values_[index] = value;
1077 }
1078
1079 private:
1080 const int64_t max_inverse_value_;
1081 std::vector<int64_t> old_inverse_values_;
1082 std::vector<int64_t> inverse_values_;
1083 };
1084
ValueFromAssignment(const Assignment & assignment,IntVar * var,int64_t index,int64_t * value)1085 inline bool IntVarLocalSearchHandler::ValueFromAssignment(
1086 const Assignment& assignment, IntVar* var, int64_t index, int64_t* value) {
1087 const Assignment::IntContainer& container = assignment.IntVarContainer();
1088 const IntVarElement* element = &(container.Element(index));
1089 if (element->Var() != var) {
1090 CHECK(container.Contains(var))
1091 << "Assignment does not contain operator variable " << var;
1092 element = &(container.Element(var));
1093 }
1094 *value = element->Value();
1095 if (op_->IsInverseValue(index)) {
1096 op_->SetInverseValue(*value, index);
1097 op_->SetOldInverseValue(*value, index);
1098 }
1099 return element->Activated();
1100 }
1101
OnRevertChanges(int64_t index,int64_t value)1102 inline void IntVarLocalSearchHandler::OnRevertChanges(int64_t index,
1103 int64_t value) {
1104 if (op_->IsInverseValue(index)) {
1105 op_->SetInverseValue(value, index);
1106 }
1107 }
1108
1109 /// SequenceVarLocalSearchOperator
1110 class SequenceVarLocalSearchOperator;
1111
1112 class SequenceVarLocalSearchHandler {
1113 public:
SequenceVarLocalSearchHandler()1114 SequenceVarLocalSearchHandler() : op_(nullptr) {}
SequenceVarLocalSearchHandler(const SequenceVarLocalSearchHandler & other)1115 SequenceVarLocalSearchHandler(const SequenceVarLocalSearchHandler& other)
1116 : op_(other.op_) {}
SequenceVarLocalSearchHandler(SequenceVarLocalSearchOperator * op)1117 explicit SequenceVarLocalSearchHandler(SequenceVarLocalSearchOperator* op)
1118 : op_(op) {}
1119 void AddToAssignment(SequenceVar* var, const std::vector<int>& value,
1120 bool active, std::vector<int>* assignment_indices,
1121 int64_t index, Assignment* assignment) const;
1122 bool ValueFromAssignment(const Assignment& assignment, SequenceVar* var,
1123 int64_t index, std::vector<int>* value);
1124 void OnRevertChanges(int64_t index, const std::vector<int>& value);
1125 void OnAddVars();
1126
1127 private:
1128 SequenceVarLocalSearchOperator* const op_;
1129 };
1130
1131 #ifdef SWIG
1132 /// Unfortunately, we must put this code here and not in
1133 /// */constraint_solver.i, because it must be parsed by SWIG before the
1134 /// derived C++ class.
1135 // TODO(user): find a way to move this code back to the .i file, where it
1136 /// belongs.
1137 // clang-format off
1138 %rename(SequenceVarLocalSearchOperatorTemplate) VarLocalSearchOperator<
1139 SequenceVar, std::vector<int>, SequenceVarLocalSearchHandler>;
1140 %template(SequenceVarLocalSearchOperatorTemplate) VarLocalSearchOperator<
1141 SequenceVar, std::vector<int>, SequenceVarLocalSearchHandler>;
1142 // clang-format on
1143 #endif
1144
1145 typedef VarLocalSearchOperator<SequenceVar, std::vector<int>,
1146 SequenceVarLocalSearchHandler>
1147 SequenceVarLocalSearchOperatorTemplate;
1148
1149 class SequenceVarLocalSearchOperator
1150 : public SequenceVarLocalSearchOperatorTemplate {
1151 public:
SequenceVarLocalSearchOperator()1152 SequenceVarLocalSearchOperator() {}
SequenceVarLocalSearchOperator(const std::vector<SequenceVar * > & vars)1153 explicit SequenceVarLocalSearchOperator(const std::vector<SequenceVar*>& vars)
1154 : SequenceVarLocalSearchOperatorTemplate(
1155 SequenceVarLocalSearchHandler(this)) {
1156 AddVars(vars);
1157 }
~SequenceVarLocalSearchOperator()1158 ~SequenceVarLocalSearchOperator() override {}
1159 /// Returns the value in the current assignment of the variable of given
1160 /// index.
Sequence(int64_t index)1161 const std::vector<int>& Sequence(int64_t index) const { return Value(index); }
OldSequence(int64_t index)1162 const std::vector<int>& OldSequence(int64_t index) const {
1163 return OldValue(index);
1164 }
SetForwardSequence(int64_t index,const std::vector<int> & value)1165 void SetForwardSequence(int64_t index, const std::vector<int>& value) {
1166 SetValue(index, value);
1167 }
SetBackwardSequence(int64_t index,const std::vector<int> & value)1168 void SetBackwardSequence(int64_t index, const std::vector<int>& value) {
1169 backward_values_[index] = value;
1170 MarkChange(index);
1171 }
1172
1173 protected:
1174 friend class SequenceVarLocalSearchHandler;
1175
1176 std::vector<std::vector<int>> backward_values_;
1177 };
1178
AddToAssignment(SequenceVar * var,const std::vector<int> & value,bool active,std::vector<int> * assignment_indices,int64_t index,Assignment * assignment)1179 inline void SequenceVarLocalSearchHandler::AddToAssignment(
1180 SequenceVar* var, const std::vector<int>& value, bool active,
1181 std::vector<int>* assignment_indices, int64_t index,
1182 Assignment* assignment) const {
1183 Assignment::SequenceContainer* const container =
1184 assignment->MutableSequenceVarContainer();
1185 SequenceVarElement* element = nullptr;
1186 if (assignment_indices != nullptr) {
1187 if ((*assignment_indices)[index] == -1) {
1188 (*assignment_indices)[index] = container->Size();
1189 element = assignment->FastAdd(var);
1190 } else {
1191 element = container->MutableElement((*assignment_indices)[index]);
1192 }
1193 } else {
1194 element = assignment->FastAdd(var);
1195 }
1196 if (active) {
1197 element->SetForwardSequence(value);
1198 element->SetBackwardSequence(op_->backward_values_[index]);
1199 element->Activate();
1200 } else {
1201 element->Deactivate();
1202 }
1203 }
1204
ValueFromAssignment(const Assignment & assignment,SequenceVar * var,int64_t index,std::vector<int> * value)1205 inline bool SequenceVarLocalSearchHandler::ValueFromAssignment(
1206 const Assignment& assignment, SequenceVar* var, int64_t index,
1207 std::vector<int>* value) {
1208 const Assignment::SequenceContainer& container =
1209 assignment.SequenceVarContainer();
1210 const SequenceVarElement* element = &(container.Element(index));
1211 if (element->Var() != var) {
1212 CHECK(container.Contains(var))
1213 << "Assignment does not contain operator variable " << var;
1214 element = &(container.Element(var));
1215 }
1216 const std::vector<int>& element_value = element->ForwardSequence();
1217 CHECK_GE(var->size(), element_value.size());
1218 op_->backward_values_[index].clear();
1219 *value = element_value;
1220 return element->Activated();
1221 }
1222
OnRevertChanges(int64_t index,const std::vector<int> & value)1223 inline void SequenceVarLocalSearchHandler::OnRevertChanges(
1224 int64_t index, const std::vector<int>& value) {
1225 op_->backward_values_[index].clear();
1226 }
1227
OnAddVars()1228 inline void SequenceVarLocalSearchHandler::OnAddVars() {
1229 op_->backward_values_.resize(op_->Size());
1230 }
1231
1232 /// This is the base class for building an Lns operator. An Lns fragment is a
1233 /// collection of variables which will be relaxed. Fragments are built with
1234 /// NextFragment(), which returns false if there are no more fragments to build.
1235 /// Optionally one can override InitFragments, which is called from
1236 /// LocalSearchOperator::Start to initialize fragment data.
1237 ///
1238 /// Here's a sample relaxing one variable at a time:
1239 ///
1240 /// class OneVarLns : public BaseLns {
1241 /// public:
1242 /// OneVarLns(const std::vector<IntVar*>& vars) : BaseLns(vars), index_(0) {}
1243 /// virtual ~OneVarLns() {}
1244 /// virtual void InitFragments() { index_ = 0; }
1245 /// virtual bool NextFragment() {
1246 /// const int size = Size();
1247 /// if (index_ < size) {
1248 /// AppendToFragment(index_);
1249 /// ++index_;
1250 /// return true;
1251 /// } else {
1252 /// return false;
1253 /// }
1254 /// }
1255 ///
1256 /// private:
1257 /// int index_;
1258 /// };
1259 class BaseLns : public IntVarLocalSearchOperator {
1260 public:
1261 explicit BaseLns(const std::vector<IntVar*>& vars);
1262 ~BaseLns() override;
1263 virtual void InitFragments();
1264 virtual bool NextFragment() = 0;
1265 void AppendToFragment(int index);
1266 int FragmentSize() const;
HasFragments()1267 bool HasFragments() const override { return true; }
1268
1269 protected:
1270 /// This method should not be overridden. Override NextFragment() instead.
1271 bool MakeOneNeighbor() override;
1272
1273 private:
1274 /// This method should not be overridden. Override InitFragments() instead.
1275 void OnStart() override;
1276 std::vector<int> fragment_;
1277 };
1278
1279 /// Defines operators which change the value of variables;
1280 /// each neighbor corresponds to *one* modified variable.
1281 /// Sub-classes have to define ModifyValue which determines what the new
1282 /// variable value is going to be (given the current value and the variable).
1283 class ChangeValue : public IntVarLocalSearchOperator {
1284 public:
1285 explicit ChangeValue(const std::vector<IntVar*>& vars);
1286 ~ChangeValue() override;
1287 virtual int64_t ModifyValue(int64_t index, int64_t value) = 0;
1288
1289 protected:
1290 /// This method should not be overridden. Override ModifyValue() instead.
1291 bool MakeOneNeighbor() override;
1292
1293 private:
1294 void OnStart() override;
1295
1296 int index_;
1297 };
1298
1299 /// Base class of the local search operators dedicated to path modifications
1300 /// (a path is a set of nodes linked together by arcs).
1301 /// This family of neighborhoods supposes they are handling next variables
1302 /// representing the arcs (var[i] represents the node immediately after i on
1303 /// a path).
1304 /// Several services are provided:
1305 /// - arc manipulators (SetNext(), ReverseChain(), MoveChain())
1306 /// - path inspectors (Next(), Prev(), IsPathEnd())
1307 /// - path iterators: operators need a given number of nodes to define a
1308 /// neighbor; this class provides the iteration on a given number of (base)
1309 /// nodes which can be used to define a neighbor (through the BaseNode method)
1310 /// Subclasses only need to override MakeNeighbor to create neighbors using
1311 /// the services above (no direct manipulation of assignments).
1312 class PathOperator : public IntVarLocalSearchOperator {
1313 public:
1314 /// Set of parameters used to configure how the neighnorhood is traversed.
1315 struct IterationParameters {
1316 /// Number of nodes needed to define a neighbor.
1317 int number_of_base_nodes;
1318 /// Skip paths which have been proven locally optimal. Note this might skip
1319 /// neighbors when paths are not independent.
1320 bool skip_locally_optimal_paths;
1321 /// True if path ends should be considered when iterating over neighbors.
1322 bool accept_path_end_base;
1323 /// Callback returning an index such that if
1324 /// c1 = start_empty_path_class(StartNode(p1)),
1325 /// c2 = start_empty_path_class(StartNode(p2)),
1326 /// p1 and p2 are path indices,
1327 /// then if c1 == c2, p1 and p2 are equivalent if they are empty.
1328 /// This is used to remove neighborhood symmetries on equivalent empty
1329 /// paths; for instance if a node cannot be moved to an empty path, then all
1330 /// moves moving the same node to equivalent empty paths will be skipped.
1331 /// 'start_empty_path_class' can be nullptr in which case no symmetries will
1332 /// be removed.
1333 std::function<int(int64_t)> start_empty_path_class;
1334 };
1335 /// Builds an instance of PathOperator from next and path variables.
1336 PathOperator(const std::vector<IntVar*>& next_vars,
1337 const std::vector<IntVar*>& path_vars,
1338 IterationParameters iteration_parameters);
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_t)> start_empty_path_class)1339 PathOperator(const std::vector<IntVar*>& next_vars,
1340 const std::vector<IntVar*>& path_vars, int number_of_base_nodes,
1341 bool skip_locally_optimal_paths, bool accept_path_end_base,
1342 std::function<int(int64_t)> start_empty_path_class)
1343 : PathOperator(
1344 next_vars, path_vars,
1345 {number_of_base_nodes, skip_locally_optimal_paths,
1346 accept_path_end_base, std::move(start_empty_path_class)}) {}
~PathOperator()1347 ~PathOperator() override {}
1348 virtual bool MakeNeighbor() = 0;
1349 void Reset() override;
1350
1351 // TODO(user): Make the following methods protected.
1352 bool SkipUnchanged(int index) const override;
1353
1354 /// Returns the node after node in the current delta.
Next(int64_t node)1355 int64_t Next(int64_t node) const {
1356 DCHECK(!IsPathEnd(node));
1357 return Value(node);
1358 }
1359
1360 /// Returns the node before node in the current delta.
Prev(int64_t node)1361 int64_t Prev(int64_t node) const {
1362 DCHECK(!IsPathStart(node));
1363 DCHECK_EQ(Next(InverseValue(node)), node);
1364 return InverseValue(node);
1365 }
1366
1367 /// Returns the index of the path to which node belongs in the current delta.
1368 /// Only returns a valid value if path variables are taken into account.
Path(int64_t node)1369 int64_t Path(int64_t node) const {
1370 return ignore_path_vars_ ? 0LL : Value(node + number_of_nexts_);
1371 }
1372
1373 /// Number of next variables.
number_of_nexts()1374 int number_of_nexts() const { return number_of_nexts_; }
1375
1376 protected:
1377 /// This method should not be overridden. Override MakeNeighbor() instead.
1378 bool MakeOneNeighbor() override;
1379 /// Called by OnStart() after initializing node information. Should be
1380 /// overridden instead of OnStart() to avoid calling PathOperator::OnStart
1381 /// explicitly.
OnNodeInitialization()1382 virtual void OnNodeInitialization() {}
1383
1384 /// Returns the ith base node of the operator.
BaseNode(int i)1385 int64_t BaseNode(int i) const { return base_nodes_[i]; }
1386 /// Returns the alternative for the ith base node.
BaseAlternative(int i)1387 int BaseAlternative(int i) const { return base_alternatives_[i]; }
1388 /// Returns the alternative node for the ith base node.
BaseAlternativeNode(int i)1389 int64_t BaseAlternativeNode(int i) const {
1390 if (!ConsiderAlternatives(i)) return BaseNode(i);
1391 const int alternative_index = alternative_index_[BaseNode(i)];
1392 return alternative_index >= 0
1393 ? alternative_sets_[alternative_index][base_alternatives_[i]]
1394 : BaseNode(i);
1395 }
1396 /// Returns the alternative for the sibling of the ith base node.
BaseSiblingAlternative(int i)1397 int BaseSiblingAlternative(int i) const {
1398 return base_sibling_alternatives_[i];
1399 }
1400 /// Returns the alternative node for the sibling of the ith base node.
BaseSiblingAlternativeNode(int i)1401 int64_t BaseSiblingAlternativeNode(int i) const {
1402 if (!ConsiderAlternatives(i)) return BaseNode(i);
1403 const int sibling_alternative_index =
1404 GetSiblingAlternativeIndex(BaseNode(i));
1405 return sibling_alternative_index >= 0
1406 ? alternative_sets_[sibling_alternative_index]
1407 [base_sibling_alternatives_[i]]
1408 : BaseNode(i);
1409 }
1410 /// Returns the start node of the ith base node.
StartNode(int i)1411 int64_t StartNode(int i) const { return path_starts_[base_paths_[i]]; }
1412 /// Returns the vector of path start nodes.
path_starts()1413 const std::vector<int64_t>& path_starts() const { return path_starts_; }
1414 /// Returns the class of the path of the ith base node.
PathClass(int i)1415 int PathClass(int i) const {
1416 return iteration_parameters_.start_empty_path_class != nullptr
1417 ? iteration_parameters_.start_empty_path_class(StartNode(i))
1418 : StartNode(i);
1419 }
1420
1421 /// When the operator is being synchronized with a new solution (when Start()
1422 /// is called), returns true to restart the exploration of the neighborhood
1423 /// from the start of the last paths explored; returns false to restart the
1424 /// exploration at the last nodes visited.
1425 /// This is used to avoid restarting on base nodes which have changed paths,
1426 /// leading to potentially skipping neighbors.
1427 // TODO(user): remove this when automatic detection of such cases in done.
RestartAtPathStartOnSynchronize()1428 virtual bool RestartAtPathStartOnSynchronize() { return false; }
1429 /// Returns true if a base node has to be on the same path as the "previous"
1430 /// base node (base node of index base_index - 1).
1431 /// Useful to limit neighborhood exploration to nodes on the same path.
1432 // TODO(user): ideally this should be OnSamePath(int64_t node1, int64_t
1433 // node2);
1434 /// it's currently way more complicated to implement.
OnSamePathAsPreviousBase(int64_t base_index)1435 virtual bool OnSamePathAsPreviousBase(int64_t base_index) { return false; }
1436 /// Returns the index of the node to which the base node of index base_index
1437 /// must be set to when it reaches the end of a path.
1438 /// By default, it is set to the start of the current path.
1439 /// When this method is called, one can only assume that base nodes with
1440 /// indices < base_index have their final position.
GetBaseNodeRestartPosition(int base_index)1441 virtual int64_t GetBaseNodeRestartPosition(int base_index) {
1442 return StartNode(base_index);
1443 }
1444 /// Set the next base to increment on next iteration. All base > base_index
1445 /// will be reset to their start value.
SetNextBaseToIncrement(int64_t base_index)1446 virtual void SetNextBaseToIncrement(int64_t base_index) {
1447 next_base_to_increment_ = base_index;
1448 }
1449 /// Indicates if alternatives should be considered when iterating over base
1450 /// nodes.
ConsiderAlternatives(int64_t base_index)1451 virtual bool ConsiderAlternatives(int64_t base_index) const { return false; }
1452
OldNext(int64_t node)1453 int64_t OldNext(int64_t node) const {
1454 DCHECK(!IsPathEnd(node));
1455 return OldValue(node);
1456 }
1457
OldPrev(int64_t node)1458 int64_t OldPrev(int64_t node) const {
1459 DCHECK(!IsPathStart(node));
1460 return OldInverseValue(node);
1461 }
1462
OldPath(int64_t node)1463 int64_t OldPath(int64_t node) const {
1464 return ignore_path_vars_ ? 0LL : OldValue(node + number_of_nexts_);
1465 }
1466
1467 /// Moves the chain starting after the node before_chain and ending at the
1468 /// node chain_end after the node destination
1469 bool MoveChain(int64_t before_chain, int64_t chain_end, int64_t destination);
1470
1471 /// Reverses the chain starting after before_chain and ending before
1472 /// after_chain
1473 bool ReverseChain(int64_t before_chain, int64_t after_chain,
1474 int64_t* chain_last);
1475
1476 /// Insert the inactive node after destination.
1477 bool MakeActive(int64_t node, int64_t destination);
1478 /// Makes the nodes on the chain starting after before_chain and ending at
1479 /// chain_end inactive.
1480 bool MakeChainInactive(int64_t before_chain, int64_t chain_end);
1481 /// Replaces active by inactive in the current path, making active inactive.
1482 bool SwapActiveAndInactive(int64_t active, int64_t inactive);
1483
1484 /// Sets 'to' to be the node after 'from' on the given path.
SetNext(int64_t from,int64_t to,int64_t path)1485 void SetNext(int64_t from, int64_t to, int64_t path) {
1486 DCHECK_LT(from, number_of_nexts_);
1487 SetValue(from, to);
1488 SetInverseValue(to, from);
1489 if (!ignore_path_vars_) {
1490 DCHECK_LT(from + number_of_nexts_, Size());
1491 SetValue(from + number_of_nexts_, path);
1492 }
1493 }
1494
1495 /// Returns true if node is the last node on the path; defined by the fact
1496 /// that node is outside the range of the variable array.
IsPathEnd(int64_t node)1497 bool IsPathEnd(int64_t node) const { return node >= number_of_nexts_; }
1498
1499 /// Returns true if node is the first node on the path.
IsPathStart(int64_t node)1500 bool IsPathStart(int64_t node) const { return OldInverseValue(node) == -1; }
1501
1502 /// Returns true if node is inactive.
IsInactive(int64_t node)1503 bool IsInactive(int64_t node) const {
1504 return !IsPathEnd(node) && inactives_[node];
1505 }
1506
1507 /// Returns true if the operator needs to restart its initial position at each
1508 /// call to Start()
InitPosition()1509 virtual bool InitPosition() const { return false; }
1510 /// Reset the position of the operator to its position when Start() was last
1511 /// called; this can be used to let an operator iterate more than once over
1512 /// the paths.
ResetPosition()1513 void ResetPosition() { just_started_ = true; }
1514
1515 /// Handling node alternatives.
1516 /// Adds a set of node alternatives to the neighborhood. No node can be in
1517 /// two altrnatives.
AddAlternativeSet(const std::vector<int64_t> & alternative_set)1518 int AddAlternativeSet(const std::vector<int64_t>& alternative_set) {
1519 const int alternative = alternative_sets_.size();
1520 for (int64_t node : alternative_set) {
1521 DCHECK_EQ(-1, alternative_index_[node]);
1522 alternative_index_[node] = alternative;
1523 }
1524 alternative_sets_.push_back(alternative_set);
1525 sibling_alternative_.push_back(-1);
1526 return alternative;
1527 }
1528 #ifndef SWIG
1529 /// Adds all sets of node alternatives of a vector of alternative pairs. No
1530 /// node can be in two altrnatives.
AddPairAlternativeSets(const std::vector<std::pair<std::vector<int64_t>,std::vector<int64_t>>> & pair_alternative_sets)1531 void AddPairAlternativeSets(
1532 const std::vector<std::pair<std::vector<int64_t>, std::vector<int64_t>>>&
1533 pair_alternative_sets) {
1534 for (const auto& pair_alternative_set : pair_alternative_sets) {
1535 const int alternative = AddAlternativeSet(pair_alternative_set.first);
1536 sibling_alternative_.back() = alternative + 1;
1537 AddAlternativeSet(pair_alternative_set.second);
1538 }
1539 }
1540 #endif // SWIG
1541 /// Returns the active node in the given alternative set.
GetActiveInAlternativeSet(int alternative_index)1542 int64_t GetActiveInAlternativeSet(int alternative_index) const {
1543 return alternative_index >= 0
1544 ? active_in_alternative_set_[alternative_index]
1545 : -1;
1546 }
1547 /// Returns the active node in the alternative set of the given node.
GetActiveAlternativeNode(int node)1548 int64_t GetActiveAlternativeNode(int node) const {
1549 return GetActiveInAlternativeSet(alternative_index_[node]);
1550 }
1551 /// Returns the index of the alternative set of the sibling of node.
GetSiblingAlternativeIndex(int node)1552 int GetSiblingAlternativeIndex(int node) const {
1553 if (node >= alternative_index_.size()) return -1;
1554 const int alternative = alternative_index_[node];
1555 return alternative >= 0 ? sibling_alternative_[alternative] : -1;
1556 }
1557 /// Returns the active node in the alternative set of the sibling of the given
1558 /// node.
GetActiveAlternativeSibling(int node)1559 int64_t GetActiveAlternativeSibling(int node) const {
1560 if (node >= alternative_index_.size()) return -1;
1561 const int alternative = alternative_index_[node];
1562 const int sibling_alternative =
1563 alternative >= 0 ? sibling_alternative_[alternative] : -1;
1564 return GetActiveInAlternativeSet(sibling_alternative);
1565 }
1566 /// Returns true if the chain is a valid path without cycles from before_chain
1567 /// to chain_end and does not contain exclude.
1568 bool CheckChainValidity(int64_t before_chain, int64_t chain_end,
1569 int64_t exclude) const;
1570
1571 const int number_of_nexts_;
1572 const bool ignore_path_vars_;
1573 int next_base_to_increment_;
1574 int num_paths_ = 0;
1575 std::vector<int64_t> start_to_path_;
1576
1577 private:
1578 void OnStart() override;
1579 /// Returns true if two nodes are on the same path in the current assignment.
1580 bool OnSamePath(int64_t node1, int64_t node2) const;
1581
CheckEnds()1582 bool CheckEnds() const {
1583 const int base_node_size = base_nodes_.size();
1584 for (int i = base_node_size - 1; i >= 0; --i) {
1585 if (base_nodes_[i] != end_nodes_[i]) {
1586 return true;
1587 }
1588 }
1589 return false;
1590 }
1591 bool IncrementPosition();
1592 void InitializePathStarts();
1593 void InitializeInactives();
1594 void InitializeBaseNodes();
1595 void InitializeAlternatives();
1596 void Synchronize();
1597
1598 std::vector<int> base_nodes_;
1599 std::vector<int> base_alternatives_;
1600 std::vector<int> base_sibling_alternatives_;
1601 std::vector<int> end_nodes_;
1602 std::vector<int> base_paths_;
1603 std::vector<int64_t> path_starts_;
1604 std::vector<bool> inactives_;
1605 bool just_started_;
1606 bool first_start_;
1607 IterationParameters iteration_parameters_;
1608 bool optimal_paths_enabled_;
1609 std::vector<int> path_basis_;
1610 std::vector<bool> optimal_paths_;
1611 /// Node alternative data.
1612 #ifndef SWIG
1613 std::vector<std::vector<int64_t>> alternative_sets_;
1614 #endif // SWIG
1615 std::vector<int> alternative_index_;
1616 std::vector<int64_t> active_in_alternative_set_;
1617 std::vector<int> sibling_alternative_;
1618 };
1619
1620 /// Operator Factories.
1621 template <class T>
1622 LocalSearchOperator* MakeLocalSearchOperator(
1623 Solver* solver, const std::vector<IntVar*>& vars,
1624 const std::vector<IntVar*>& secondary_vars,
1625 std::function<int(int64_t)> start_empty_path_class);
1626
1627 /// Classes to which this template function can be applied to as of 04/2014.
1628 /// Usage: LocalSearchOperator* op = MakeLocalSearchOperator<Relocate>(...);
1629 /// class TwoOpt;
1630 /// class Relocate;
1631 /// class Exchange;
1632 /// class Cross;
1633 /// class MakeActiveOperator;
1634 /// class MakeInactiveOperator;
1635 /// class MakeChainInactiveOperator;
1636 /// class SwapActiveOperator;
1637 /// class ExtendedSwapActiveOperator;
1638 /// class MakeActiveAndRelocate;
1639 /// class RelocateAndMakeActiveOperator;
1640 /// class RelocateAndMakeInactiveOperator;
1641
1642 #if !defined(SWIG)
1643 // A LocalSearchState is a container for variables with bounds that can be
1644 // relaxed and tightened, saved and restored. It represents the solution state
1645 // of a local search engine, and allows it to go from solution to solution by
1646 // relaxing some variables to form a new subproblem, then tightening those
1647 // variables to move to a new solution representation. That state may be saved
1648 // to an internal copy, or reverted to the last saved internal copy.
1649 // Relaxing a variable returns its bounds to their initial state.
1650 // Tightening a variable's bounds may make its min larger than its max,
1651 // in that case, the tightening function will return false, and the state will
1652 // be marked as invalid. No other operations than Revert() can be called on an
1653 // invalid state: in particular, an invalid state cannot be saved.
1654 class LocalSearchVariable;
1655
1656 class LocalSearchState {
1657 public:
1658 LocalSearchVariable AddVariable(int64_t initial_min, int64_t initial_max);
1659 void Commit();
1660 void Revert();
StateIsValid()1661 bool StateIsValid() const { return state_is_valid_; }
1662
1663 private:
1664 friend class LocalSearchVariable;
1665
1666 struct Bounds {
1667 int64_t min;
1668 int64_t max;
1669 };
1670
1671 void RelaxVariableBounds(int variable_index);
1672 bool TightenVariableMin(int variable_index, int64_t value);
1673 bool TightenVariableMax(int variable_index, int64_t value);
1674 int64_t VariableMin(int variable_index) const;
1675 int64_t VariableMax(int variable_index) const;
1676
1677 std::vector<Bounds> initial_variable_bounds_;
1678 std::vector<Bounds> variable_bounds_;
1679 std::vector<std::pair<Bounds, int>> saved_variable_bounds_trail_;
1680 std::vector<bool> variable_is_relaxed_;
1681 bool state_is_valid_ = true;
1682 };
1683
1684 // A LocalSearchVariable can only be created by a LocalSearchState, then it is
1685 // meant to be passed by copy. If at some point the duplication of
1686 // LocalSearchState pointers is too expensive, we could switch to index only,
1687 // and the user would have to know the relevant state. The present setup allows
1688 // to ensure that variable users will not misuse the state.
1689 class LocalSearchVariable {
1690 public:
Min()1691 int64_t Min() const { return state_->VariableMin(variable_index_); }
Max()1692 int64_t Max() const { return state_->VariableMax(variable_index_); }
SetMin(int64_t new_min)1693 bool SetMin(int64_t new_min) {
1694 return state_->TightenVariableMin(variable_index_, new_min);
1695 }
SetMax(int64_t new_max)1696 bool SetMax(int64_t new_max) {
1697 return state_->TightenVariableMax(variable_index_, new_max);
1698 }
Relax()1699 void Relax() { state_->RelaxVariableBounds(variable_index_); }
1700
1701 private:
1702 // Only LocalSearchState can construct LocalSearchVariables.
1703 friend class LocalSearchState;
1704
LocalSearchVariable(LocalSearchState * state,int variable_index)1705 LocalSearchVariable(LocalSearchState* state, int variable_index)
1706 : state_(state), variable_index_(variable_index) {}
1707
1708 LocalSearchState* const state_;
1709 const int variable_index_;
1710 };
1711 #endif // !defined(SWIG)
1712
1713 /// Local Search Filters are used for fast neighbor pruning.
1714 /// Filtering a move is done in several phases:
1715 /// - in the Relax phase, filters determine which parts of their internals
1716 /// will be changed by the candidate, and modify intermediary State
1717 /// - in the Accept phase, filters check that the candidate is feasible,
1718 /// - if the Accept phase succeeds, the solver may decide to trigger a
1719 /// Synchronize phase that makes filters change their internal representation
1720 /// to the last candidate,
1721 /// - otherwise (Accept fails or the solver does not want to synchronize),
1722 /// a Revert phase makes filters erase any intermediary State generated by the
1723 /// Relax and Accept phases.
1724 /// A given filter has phases called with the following pattern:
1725 /// (Relax.Accept.Synchronize | Relax.Accept.Revert | Relax.Revert)*.
1726 /// Filters's Revert() is always called in the reverse order their Accept() was
1727 /// called, to allow late filters to use state done/undone by early filters'
1728 /// Accept()/Revert().
1729 class LocalSearchFilter : public BaseObject {
1730 public:
1731 /// Lets the filter know what delta and deltadelta will be passed in the next
1732 /// Accept().
Relax(const Assignment * delta,const Assignment * deltadelta)1733 virtual void Relax(const Assignment* delta, const Assignment* deltadelta) {}
1734 /// Dual of Relax(), lets the filter know that the delta was accepted.
Commit(const Assignment * delta,const Assignment * deltadelta)1735 virtual void Commit(const Assignment* delta, const Assignment* deltadelta) {}
1736
1737 /// Accepts a "delta" given the assignment with which the filter has been
1738 /// synchronized; the delta holds the variables which have been modified and
1739 /// their new value.
1740 /// If the filter represents a part of the global objective, its contribution
1741 /// must be between objective_min and objective_max.
1742 /// Sample: supposing one wants to maintain a[0,1] + b[0,1] <= 1,
1743 /// for the assignment (a,1), (b,0), the delta (b,1) will be rejected
1744 /// but the delta (a,0) will be accepted.
1745 /// TODO(user): Remove arguments when there are no more need for those.
1746 virtual bool Accept(const Assignment* delta, const Assignment* deltadelta,
1747 int64_t objective_min, int64_t objective_max) = 0;
IsIncremental()1748 virtual bool IsIncremental() const { return false; }
1749
1750 /// Synchronizes the filter with the current solution, delta being the
1751 /// difference with the solution passed to the previous call to Synchronize()
1752 /// or IncrementalSynchronize(). 'delta' can be used to incrementally
1753 /// synchronizing the filter with the new solution by only considering the
1754 /// changes in delta.
1755 virtual void Synchronize(const Assignment* assignment,
1756 const Assignment* delta) = 0;
1757 /// Cancels the changes made by the last Relax()/Accept() calls.
Revert()1758 virtual void Revert() {}
1759
1760 /// Sets the filter to empty solution.
Reset()1761 virtual void Reset() {}
1762
1763 /// Objective value from last time Synchronize() was called.
GetSynchronizedObjectiveValue()1764 virtual int64_t GetSynchronizedObjectiveValue() const { return 0LL; }
1765 /// Objective value from the last time Accept() was called and returned true.
1766 // If the last Accept() call returned false, returns an undefined value.
GetAcceptedObjectiveValue()1767 virtual int64_t GetAcceptedObjectiveValue() const { return 0LL; }
1768 };
1769
1770 /// Filter manager: when a move is made, filters are executed to decide whether
1771 /// the solution is feasible and compute parts of the new cost. This class
1772 /// schedules filter execution and composes costs as a sum.
1773 class LocalSearchFilterManager : public BaseObject {
1774 public:
1775 // This class is responsible for calling filters methods in a correct order.
1776 // For now, an order is specified explicitly by the user.
1777 enum FilterEventType { kAccept, kRelax };
1778 struct FilterEvent {
1779 LocalSearchFilter* filter;
1780 FilterEventType event_type;
1781 };
1782
DebugString()1783 std::string DebugString() const override {
1784 return "LocalSearchFilterManager";
1785 }
1786 // Builds a manager that calls filter methods using an explicit ordering.
1787 explicit LocalSearchFilterManager(std::vector<FilterEvent> filter_events);
1788 // Builds a manager that calls filter methods using the following ordering:
1789 // first Relax() in vector order, then Accept() in vector order.
1790 // Note that some filters might appear only once, if their Relax() or Accept()
1791 // are trivial.
1792 explicit LocalSearchFilterManager(std::vector<LocalSearchFilter*> filters);
1793
1794 // Calls Revert() of filters, in reverse order of Relax events.
1795 void Revert();
1796 /// Returns true iff all filters return true, and the sum of their accepted
1797 /// objectives is between objective_min and objective_max.
1798 /// The monitor has its Begin/EndFiltering events triggered.
1799 bool Accept(LocalSearchMonitor* const monitor, const Assignment* delta,
1800 const Assignment* deltadelta, int64_t objective_min,
1801 int64_t objective_max);
1802 /// Synchronizes all filters to assignment.
1803 void Synchronize(const Assignment* assignment, const Assignment* delta);
GetSynchronizedObjectiveValue()1804 int64_t GetSynchronizedObjectiveValue() const { return synchronized_value_; }
GetAcceptedObjectiveValue()1805 int64_t GetAcceptedObjectiveValue() const { return accepted_value_; }
1806
1807 private:
1808 void InitializeForcedEvents();
1809
1810 std::vector<FilterEvent> filter_events_;
1811 int last_event_called_ = -1;
1812 // If a filter is incremental, its Relax() and Accept() must be called for
1813 // every candidate, even if a previous Accept() rejected it.
1814 // To ensure that those filters have consistent inputs, all intermediate
1815 // Relax events are also triggered. All those events are called 'forced'.
1816 std::vector<int> next_forced_events_;
1817 int64_t synchronized_value_;
1818 int64_t accepted_value_;
1819 };
1820
1821 class IntVarLocalSearchFilter : public LocalSearchFilter {
1822 public:
1823 explicit IntVarLocalSearchFilter(const std::vector<IntVar*>& vars);
1824 ~IntVarLocalSearchFilter() override;
1825 /// This method should not be overridden. Override OnSynchronize() instead
1826 /// which is called before exiting this method.
1827 void Synchronize(const Assignment* assignment,
1828 const Assignment* delta) override;
1829
FindIndex(IntVar * const var,int64_t * index)1830 bool FindIndex(IntVar* const var, int64_t* index) const {
1831 DCHECK(index != nullptr);
1832 const int var_index = var->index();
1833 *index = (var_index < var_index_to_index_.size())
1834 ? var_index_to_index_[var_index]
1835 : kUnassigned;
1836 return *index != kUnassigned;
1837 }
1838
1839 /// Add variables to "track" to the filter.
1840 void AddVars(const std::vector<IntVar*>& vars);
Size()1841 int Size() const { return vars_.size(); }
Var(int index)1842 IntVar* Var(int index) const { return vars_[index]; }
Value(int index)1843 int64_t Value(int index) const {
1844 DCHECK(IsVarSynced(index));
1845 return values_[index];
1846 }
IsVarSynced(int index)1847 bool IsVarSynced(int index) const { return var_synced_[index]; }
1848
1849 protected:
OnSynchronize(const Assignment * delta)1850 virtual void OnSynchronize(const Assignment* delta) {}
1851 void SynchronizeOnAssignment(const Assignment* assignment);
1852
1853 private:
1854 std::vector<IntVar*> vars_;
1855 std::vector<int64_t> values_;
1856 std::vector<bool> var_synced_;
1857 std::vector<int> var_index_to_index_;
1858 static const int kUnassigned;
1859 };
1860
1861 class PropagationMonitor : public SearchMonitor {
1862 public:
1863 explicit PropagationMonitor(Solver* const solver);
1864 ~PropagationMonitor() override;
DebugString()1865 std::string DebugString() const override { return "PropagationMonitor"; }
1866
1867 /// Propagation events.
1868 virtual void BeginConstraintInitialPropagation(
1869 Constraint* const constraint) = 0;
1870 virtual void EndConstraintInitialPropagation(
1871 Constraint* const constraint) = 0;
1872 virtual void BeginNestedConstraintInitialPropagation(
1873 Constraint* const parent, Constraint* const nested) = 0;
1874 virtual void EndNestedConstraintInitialPropagation(
1875 Constraint* const parent, Constraint* const nested) = 0;
1876 virtual void RegisterDemon(Demon* const demon) = 0;
1877 virtual void BeginDemonRun(Demon* const demon) = 0;
1878 virtual void EndDemonRun(Demon* const demon) = 0;
1879 virtual void StartProcessingIntegerVariable(IntVar* const var) = 0;
1880 virtual void EndProcessingIntegerVariable(IntVar* const var) = 0;
1881 virtual void PushContext(const std::string& context) = 0;
1882 virtual void PopContext() = 0;
1883 /// IntExpr modifiers.
1884 virtual void SetMin(IntExpr* const expr, int64_t new_min) = 0;
1885 virtual void SetMax(IntExpr* const expr, int64_t new_max) = 0;
1886 virtual void SetRange(IntExpr* const expr, int64_t new_min,
1887 int64_t new_max) = 0;
1888 /// IntVar modifiers.
1889 virtual void SetMin(IntVar* const var, int64_t new_min) = 0;
1890 virtual void SetMax(IntVar* const var, int64_t new_max) = 0;
1891 virtual void SetRange(IntVar* const var, int64_t new_min,
1892 int64_t new_max) = 0;
1893 virtual void RemoveValue(IntVar* const var, int64_t value) = 0;
1894 virtual void SetValue(IntVar* const var, int64_t value) = 0;
1895 virtual void RemoveInterval(IntVar* const var, int64_t imin,
1896 int64_t imax) = 0;
1897 virtual void SetValues(IntVar* const var,
1898 const std::vector<int64_t>& values) = 0;
1899 virtual void RemoveValues(IntVar* const var,
1900 const std::vector<int64_t>& values) = 0;
1901 /// IntervalVar modifiers.
1902 virtual void SetStartMin(IntervalVar* const var, int64_t new_min) = 0;
1903 virtual void SetStartMax(IntervalVar* const var, int64_t new_max) = 0;
1904 virtual void SetStartRange(IntervalVar* const var, int64_t new_min,
1905 int64_t new_max) = 0;
1906 virtual void SetEndMin(IntervalVar* const var, int64_t new_min) = 0;
1907 virtual void SetEndMax(IntervalVar* const var, int64_t new_max) = 0;
1908 virtual void SetEndRange(IntervalVar* const var, int64_t new_min,
1909 int64_t new_max) = 0;
1910 virtual void SetDurationMin(IntervalVar* const var, int64_t new_min) = 0;
1911 virtual void SetDurationMax(IntervalVar* const var, int64_t new_max) = 0;
1912 virtual void SetDurationRange(IntervalVar* const var, int64_t new_min,
1913 int64_t new_max) = 0;
1914 virtual void SetPerformed(IntervalVar* const var, bool value) = 0;
1915 /// SequenceVar modifiers
1916 virtual void RankFirst(SequenceVar* const var, int index) = 0;
1917 virtual void RankNotFirst(SequenceVar* const var, int index) = 0;
1918 virtual void RankLast(SequenceVar* const var, int index) = 0;
1919 virtual void RankNotLast(SequenceVar* const var, int index) = 0;
1920 virtual void RankSequence(SequenceVar* const var,
1921 const std::vector<int>& rank_first,
1922 const std::vector<int>& rank_last,
1923 const std::vector<int>& unperformed) = 0;
1924 /// Install itself on the solver.
1925 void Install() override;
1926 };
1927
1928 class LocalSearchMonitor : public SearchMonitor {
1929 // TODO(user): Add monitoring of local search filters.
1930 public:
1931 explicit LocalSearchMonitor(Solver* const solver);
1932 ~LocalSearchMonitor() override;
DebugString()1933 std::string DebugString() const override { return "LocalSearchMonitor"; }
1934
1935 /// Local search operator events.
1936 virtual void BeginOperatorStart() = 0;
1937 virtual void EndOperatorStart() = 0;
1938 virtual void BeginMakeNextNeighbor(const LocalSearchOperator* op) = 0;
1939 virtual void EndMakeNextNeighbor(const LocalSearchOperator* op,
1940 bool neighbor_found, const Assignment* delta,
1941 const Assignment* deltadelta) = 0;
1942 virtual void BeginFilterNeighbor(const LocalSearchOperator* op) = 0;
1943 virtual void EndFilterNeighbor(const LocalSearchOperator* op,
1944 bool neighbor_found) = 0;
1945 virtual void BeginAcceptNeighbor(const LocalSearchOperator* op) = 0;
1946 virtual void EndAcceptNeighbor(const LocalSearchOperator* op,
1947 bool neighbor_found) = 0;
1948 virtual void BeginFiltering(const LocalSearchFilter* filter) = 0;
1949 virtual void EndFiltering(const LocalSearchFilter* filter, bool reject) = 0;
1950
1951 /// Install itself on the solver.
1952 void Install() override;
1953 };
1954
1955 class BooleanVar : public IntVar {
1956 public:
1957 static const int kUnboundBooleanVarValue;
1958
1959 explicit BooleanVar(Solver* const s, const std::string& name = "")
IntVar(s,name)1960 : IntVar(s, name), value_(kUnboundBooleanVarValue) {}
1961
~BooleanVar()1962 ~BooleanVar() override {}
1963
Min()1964 int64_t Min() const override { return (value_ == 1); }
1965 void SetMin(int64_t m) override;
Max()1966 int64_t Max() const override { return (value_ != 0); }
1967 void SetMax(int64_t m) override;
1968 void SetRange(int64_t mi, int64_t ma) override;
Bound()1969 bool Bound() const override { return (value_ != kUnboundBooleanVarValue); }
Value()1970 int64_t Value() const override {
1971 CHECK_NE(value_, kUnboundBooleanVarValue) << "variable is not bound";
1972 return value_;
1973 }
1974 void RemoveValue(int64_t v) override;
1975 void RemoveInterval(int64_t l, int64_t u) override;
1976 void WhenBound(Demon* d) override;
WhenRange(Demon * d)1977 void WhenRange(Demon* d) override { WhenBound(d); }
WhenDomain(Demon * d)1978 void WhenDomain(Demon* d) override { WhenBound(d); }
1979 uint64_t Size() const override;
1980 bool Contains(int64_t v) const override;
1981 IntVarIterator* MakeHoleIterator(bool reversible) const override;
1982 IntVarIterator* MakeDomainIterator(bool reversible) const override;
1983 std::string DebugString() const override;
VarType()1984 int VarType() const override { return BOOLEAN_VAR; }
1985
1986 IntVar* IsEqual(int64_t constant) override;
1987 IntVar* IsDifferent(int64_t constant) override;
1988 IntVar* IsGreaterOrEqual(int64_t constant) override;
1989 IntVar* IsLessOrEqual(int64_t constant) override;
1990
1991 virtual void RestoreValue() = 0;
BaseName()1992 std::string BaseName() const override { return "BooleanVar"; }
1993
RawValue()1994 int RawValue() const { return value_; }
1995
1996 protected:
1997 int value_;
1998 SimpleRevFIFO<Demon*> bound_demons_;
1999 SimpleRevFIFO<Demon*> delayed_bound_demons_;
2000 };
2001
2002 class SymmetryManager;
2003
2004 /// A symmetry breaker is an object that will visit a decision and
2005 /// create the 'symmetrical' decision in return.
2006 /// Each symmetry breaker represents one class of symmetry.
2007 class SymmetryBreaker : public DecisionVisitor {
2008 public:
SymmetryBreaker()2009 SymmetryBreaker()
2010 : symmetry_manager_(nullptr), index_in_symmetry_manager_(-1) {}
~SymmetryBreaker()2011 ~SymmetryBreaker() override {}
2012
2013 void AddIntegerVariableEqualValueClause(IntVar* const var, int64_t value);
2014 void AddIntegerVariableGreaterOrEqualValueClause(IntVar* const var,
2015 int64_t value);
2016 void AddIntegerVariableLessOrEqualValueClause(IntVar* const var,
2017 int64_t value);
2018
2019 private:
2020 friend class SymmetryManager;
set_symmetry_manager_and_index(SymmetryManager * manager,int index)2021 void set_symmetry_manager_and_index(SymmetryManager* manager, int index) {
2022 CHECK(symmetry_manager_ == nullptr);
2023 CHECK_EQ(-1, index_in_symmetry_manager_);
2024 symmetry_manager_ = manager;
2025 index_in_symmetry_manager_ = index;
2026 }
symmetry_manager()2027 SymmetryManager* symmetry_manager() const { return symmetry_manager_; }
index_in_symmetry_manager()2028 int index_in_symmetry_manager() const { return index_in_symmetry_manager_; }
2029
2030 SymmetryManager* symmetry_manager_;
2031 /// Index of the symmetry breaker when used inside the symmetry manager.
2032 int index_in_symmetry_manager_;
2033 };
2034
2035 /// The base class of all search logs that periodically outputs information when
2036 /// the search is running.
2037 class SearchLog : public SearchMonitor {
2038 public:
2039 SearchLog(Solver* const s, OptimizeVar* const obj, IntVar* const var,
2040 double scaling_factor, double offset,
2041 std::function<std::string()> display_callback,
2042 bool display_on_new_solutions_only, int period);
2043 ~SearchLog() override;
2044 void EnterSearch() override;
2045 void ExitSearch() override;
2046 bool AtSolution() override;
2047 void BeginFail() override;
2048 void NoMoreSolutions() override;
2049 void AcceptUncheckedNeighbor() override;
2050 void ApplyDecision(Decision* const decision) override;
2051 void RefuteDecision(Decision* const decision) override;
2052 void OutputDecision();
2053 void Maintain();
2054 void BeginInitialPropagation() override;
2055 void EndInitialPropagation() override;
2056 std::string DebugString() const override;
2057
2058 protected:
2059 /* Bottleneck function used for all UI related output. */
2060 virtual void OutputLine(const std::string& line);
2061
2062 private:
2063 static std::string MemoryUsage();
2064
2065 const int period_;
2066 std::unique_ptr<WallTimer> timer_;
2067 IntVar* const var_;
2068 OptimizeVar* const obj_;
2069 const double scaling_factor_;
2070 const double offset_;
2071 std::function<std::string()> display_callback_;
2072 const bool display_on_new_solutions_only_;
2073 int nsol_;
2074 int64_t tick_;
2075 int64_t objective_min_;
2076 int64_t objective_max_;
2077 int min_right_depth_;
2078 int max_depth_;
2079 int sliding_min_depth_;
2080 int sliding_max_depth_;
2081 };
2082
2083 /// Implements a complete cache for model elements: expressions and
2084 /// constraints. Caching is based on the signatures of the elements, as
2085 /// well as their types. This class is used internally to avoid creating
2086 /// duplicate objects.
2087 class ModelCache {
2088 public:
2089 enum VoidConstraintType {
2090 VOID_FALSE_CONSTRAINT = 0,
2091 VOID_TRUE_CONSTRAINT,
2092 VOID_CONSTRAINT_MAX,
2093 };
2094
2095 enum VarConstantConstraintType {
2096 VAR_CONSTANT_EQUALITY = 0,
2097 VAR_CONSTANT_GREATER_OR_EQUAL,
2098 VAR_CONSTANT_LESS_OR_EQUAL,
2099 VAR_CONSTANT_NON_EQUALITY,
2100 VAR_CONSTANT_CONSTRAINT_MAX,
2101 };
2102
2103 enum VarConstantConstantConstraintType {
2104 VAR_CONSTANT_CONSTANT_BETWEEN = 0,
2105 VAR_CONSTANT_CONSTANT_CONSTRAINT_MAX,
2106 };
2107
2108 enum ExprExprConstraintType {
2109 EXPR_EXPR_EQUALITY = 0,
2110 EXPR_EXPR_GREATER,
2111 EXPR_EXPR_GREATER_OR_EQUAL,
2112 EXPR_EXPR_LESS,
2113 EXPR_EXPR_LESS_OR_EQUAL,
2114 EXPR_EXPR_NON_EQUALITY,
2115 EXPR_EXPR_CONSTRAINT_MAX,
2116 };
2117
2118 enum ExprExpressionType {
2119 EXPR_OPPOSITE = 0,
2120 EXPR_ABS,
2121 EXPR_SQUARE,
2122 EXPR_EXPRESSION_MAX,
2123 };
2124
2125 enum ExprExprExpressionType {
2126 EXPR_EXPR_DIFFERENCE = 0,
2127 EXPR_EXPR_PROD,
2128 EXPR_EXPR_DIV,
2129 EXPR_EXPR_MAX,
2130 EXPR_EXPR_MIN,
2131 EXPR_EXPR_SUM,
2132 EXPR_EXPR_IS_LESS,
2133 EXPR_EXPR_IS_LESS_OR_EQUAL,
2134 EXPR_EXPR_IS_EQUAL,
2135 EXPR_EXPR_IS_NOT_EQUAL,
2136 EXPR_EXPR_EXPRESSION_MAX,
2137 };
2138
2139 enum ExprExprConstantExpressionType {
2140 EXPR_EXPR_CONSTANT_CONDITIONAL = 0,
2141 EXPR_EXPR_CONSTANT_EXPRESSION_MAX,
2142 };
2143
2144 enum ExprConstantExpressionType {
2145 EXPR_CONSTANT_DIFFERENCE = 0,
2146 EXPR_CONSTANT_DIVIDE,
2147 EXPR_CONSTANT_PROD,
2148 EXPR_CONSTANT_MAX,
2149 EXPR_CONSTANT_MIN,
2150 EXPR_CONSTANT_SUM,
2151 EXPR_CONSTANT_IS_EQUAL,
2152 EXPR_CONSTANT_IS_NOT_EQUAL,
2153 EXPR_CONSTANT_IS_GREATER_OR_EQUAL,
2154 EXPR_CONSTANT_IS_LESS_OR_EQUAL,
2155 EXPR_CONSTANT_EXPRESSION_MAX,
2156 };
2157 enum VarConstantConstantExpressionType {
2158 VAR_CONSTANT_CONSTANT_SEMI_CONTINUOUS = 0,
2159 VAR_CONSTANT_CONSTANT_EXPRESSION_MAX,
2160 };
2161
2162 enum VarConstantArrayExpressionType {
2163 VAR_CONSTANT_ARRAY_ELEMENT = 0,
2164 VAR_CONSTANT_ARRAY_EXPRESSION_MAX,
2165 };
2166
2167 enum VarArrayConstantArrayExpressionType {
2168 VAR_ARRAY_CONSTANT_ARRAY_SCAL_PROD = 0,
2169 VAR_ARRAY_CONSTANT_ARRAY_EXPRESSION_MAX,
2170 };
2171
2172 enum VarArrayExpressionType {
2173 VAR_ARRAY_MAX = 0,
2174 VAR_ARRAY_MIN,
2175 VAR_ARRAY_SUM,
2176 VAR_ARRAY_EXPRESSION_MAX,
2177 };
2178
2179 enum VarArrayConstantExpressionType {
2180 VAR_ARRAY_CONSTANT_INDEX = 0,
2181 VAR_ARRAY_CONSTANT_EXPRESSION_MAX,
2182 };
2183
2184 explicit ModelCache(Solver* const solver);
2185 virtual ~ModelCache();
2186
2187 virtual void Clear() = 0;
2188
2189 /// Void constraints.
2190
2191 virtual Constraint* FindVoidConstraint(VoidConstraintType type) const = 0;
2192
2193 virtual void InsertVoidConstraint(Constraint* const ct,
2194 VoidConstraintType type) = 0;
2195
2196 /// Var Constant Constraints.
2197 virtual Constraint* FindVarConstantConstraint(
2198 IntVar* const var, int64_t value,
2199 VarConstantConstraintType type) const = 0;
2200
2201 virtual void InsertVarConstantConstraint(Constraint* const ct,
2202 IntVar* const var, int64_t value,
2203 VarConstantConstraintType type) = 0;
2204
2205 /// Var Constant Constant Constraints.
2206
2207 virtual Constraint* FindVarConstantConstantConstraint(
2208 IntVar* const var, int64_t value1, int64_t value2,
2209 VarConstantConstantConstraintType type) const = 0;
2210
2211 virtual void InsertVarConstantConstantConstraint(
2212 Constraint* const ct, IntVar* const var, int64_t value1, int64_t value2,
2213 VarConstantConstantConstraintType type) = 0;
2214
2215 /// Expr Expr Constraints.
2216
2217 virtual Constraint* FindExprExprConstraint(
2218 IntExpr* const expr1, IntExpr* const expr2,
2219 ExprExprConstraintType type) const = 0;
2220
2221 virtual void InsertExprExprConstraint(Constraint* const ct,
2222 IntExpr* const expr1,
2223 IntExpr* const expr2,
2224 ExprExprConstraintType type) = 0;
2225
2226 /// Expr Expressions.
2227
2228 virtual IntExpr* FindExprExpression(IntExpr* const expr,
2229 ExprExpressionType type) const = 0;
2230
2231 virtual void InsertExprExpression(IntExpr* const expression,
2232 IntExpr* const expr,
2233 ExprExpressionType type) = 0;
2234
2235 /// Expr Constant Expressions.
2236
2237 virtual IntExpr* FindExprConstantExpression(
2238 IntExpr* const expr, int64_t value,
2239 ExprConstantExpressionType type) const = 0;
2240
2241 virtual void InsertExprConstantExpression(
2242 IntExpr* const expression, IntExpr* const var, int64_t value,
2243 ExprConstantExpressionType type) = 0;
2244
2245 /// Expr Expr Expressions.
2246
2247 virtual IntExpr* FindExprExprExpression(
2248 IntExpr* const var1, IntExpr* const var2,
2249 ExprExprExpressionType type) const = 0;
2250
2251 virtual void InsertExprExprExpression(IntExpr* const expression,
2252 IntExpr* const var1,
2253 IntExpr* const var2,
2254 ExprExprExpressionType type) = 0;
2255
2256 /// Expr Expr Constant Expressions.
2257
2258 virtual IntExpr* FindExprExprConstantExpression(
2259 IntExpr* const var1, IntExpr* const var2, int64_t constant,
2260 ExprExprConstantExpressionType type) const = 0;
2261
2262 virtual void InsertExprExprConstantExpression(
2263 IntExpr* const expression, IntExpr* const var1, IntExpr* const var2,
2264 int64_t constant, ExprExprConstantExpressionType type) = 0;
2265
2266 /// Var Constant Constant Expressions.
2267
2268 virtual IntExpr* FindVarConstantConstantExpression(
2269 IntVar* const var, int64_t value1, int64_t value2,
2270 VarConstantConstantExpressionType type) const = 0;
2271
2272 virtual void InsertVarConstantConstantExpression(
2273 IntExpr* const expression, IntVar* const var, int64_t value1,
2274 int64_t value2, VarConstantConstantExpressionType type) = 0;
2275
2276 /// Var Constant Array Expressions.
2277
2278 virtual IntExpr* FindVarConstantArrayExpression(
2279 IntVar* const var, const std::vector<int64_t>& values,
2280 VarConstantArrayExpressionType type) const = 0;
2281
2282 virtual void InsertVarConstantArrayExpression(
2283 IntExpr* const expression, IntVar* const var,
2284 const std::vector<int64_t>& values,
2285 VarConstantArrayExpressionType type) = 0;
2286
2287 /// Var Array Expressions.
2288
2289 virtual IntExpr* FindVarArrayExpression(
2290 const std::vector<IntVar*>& vars, VarArrayExpressionType type) const = 0;
2291
2292 virtual void InsertVarArrayExpression(IntExpr* const expression,
2293 const std::vector<IntVar*>& vars,
2294 VarArrayExpressionType type) = 0;
2295
2296 /// Var Array Constant Array Expressions.
2297
2298 virtual IntExpr* FindVarArrayConstantArrayExpression(
2299 const std::vector<IntVar*>& vars, const std::vector<int64_t>& values,
2300 VarArrayConstantArrayExpressionType type) const = 0;
2301
2302 virtual void InsertVarArrayConstantArrayExpression(
2303 IntExpr* const expression, const std::vector<IntVar*>& var,
2304 const std::vector<int64_t>& values,
2305 VarArrayConstantArrayExpressionType type) = 0;
2306
2307 /// Var Array Constant Expressions.
2308
2309 virtual IntExpr* FindVarArrayConstantExpression(
2310 const std::vector<IntVar*>& vars, int64_t value,
2311 VarArrayConstantExpressionType type) const = 0;
2312
2313 virtual void InsertVarArrayConstantExpression(
2314 IntExpr* const expression, const std::vector<IntVar*>& var, int64_t value,
2315 VarArrayConstantExpressionType type) = 0;
2316
2317 Solver* solver() const;
2318
2319 private:
2320 Solver* const solver_;
2321 };
2322
2323 /// Argument Holder: useful when visiting a model.
2324 #if !defined(SWIG)
2325 class ArgumentHolder {
2326 public:
2327 /// Type of the argument.
2328 const std::string& TypeName() const;
2329 void SetTypeName(const std::string& type_name);
2330
2331 /// Setters.
2332 void SetIntegerArgument(const std::string& arg_name, int64_t value);
2333 void SetIntegerArrayArgument(const std::string& arg_name,
2334 const std::vector<int64_t>& values);
2335 void SetIntegerMatrixArgument(const std::string& arg_name,
2336 const IntTupleSet& values);
2337 void SetIntegerExpressionArgument(const std::string& arg_name,
2338 IntExpr* const expr);
2339 void SetIntegerVariableArrayArgument(const std::string& arg_name,
2340 const std::vector<IntVar*>& vars);
2341 void SetIntervalArgument(const std::string& arg_name, IntervalVar* const var);
2342 void SetIntervalArrayArgument(const std::string& arg_name,
2343 const std::vector<IntervalVar*>& vars);
2344 void SetSequenceArgument(const std::string& arg_name, SequenceVar* const var);
2345 void SetSequenceArrayArgument(const std::string& arg_name,
2346 const std::vector<SequenceVar*>& vars);
2347
2348 /// Checks if arguments exist.
2349 bool HasIntegerExpressionArgument(const std::string& arg_name) const;
2350 bool HasIntegerVariableArrayArgument(const std::string& arg_name) const;
2351
2352 /// Getters.
2353 int64_t FindIntegerArgumentWithDefault(const std::string& arg_name,
2354 int64_t def) const;
2355 int64_t FindIntegerArgumentOrDie(const std::string& arg_name) const;
2356 const std::vector<int64_t>& FindIntegerArrayArgumentOrDie(
2357 const std::string& arg_name) const;
2358 const IntTupleSet& FindIntegerMatrixArgumentOrDie(
2359 const std::string& arg_name) const;
2360
2361 IntExpr* FindIntegerExpressionArgumentOrDie(
2362 const std::string& arg_name) const;
2363 const std::vector<IntVar*>& FindIntegerVariableArrayArgumentOrDie(
2364 const std::string& arg_name) const;
2365
2366 private:
2367 std::string type_name_;
2368 absl::flat_hash_map<std::string, int64_t> integer_argument_;
2369 absl::flat_hash_map<std::string, std::vector<int64_t>>
2370 integer_array_argument_;
2371 absl::flat_hash_map<std::string, IntTupleSet> matrix_argument_;
2372 absl::flat_hash_map<std::string, IntExpr*> integer_expression_argument_;
2373 absl::flat_hash_map<std::string, IntervalVar*> interval_argument_;
2374 absl::flat_hash_map<std::string, SequenceVar*> sequence_argument_;
2375 absl::flat_hash_map<std::string, std::vector<IntVar*>>
2376 integer_variable_array_argument_;
2377 absl::flat_hash_map<std::string, std::vector<IntervalVar*>>
2378 interval_array_argument_;
2379 absl::flat_hash_map<std::string, std::vector<SequenceVar*>>
2380 sequence_array_argument_;
2381 };
2382
2383 /// Model Parser
2384 class ModelParser : public ModelVisitor {
2385 public:
2386 ModelParser();
2387
2388 ~ModelParser() override;
2389
2390 /// Header/footers.
2391 void BeginVisitModel(const std::string& solver_name) override;
2392 void EndVisitModel(const std::string& solver_name) override;
2393 void BeginVisitConstraint(const std::string& type_name,
2394 const Constraint* const constraint) override;
2395 void EndVisitConstraint(const std::string& type_name,
2396 const Constraint* const constraint) override;
2397 void BeginVisitIntegerExpression(const std::string& type_name,
2398 const IntExpr* const expr) override;
2399 void EndVisitIntegerExpression(const std::string& type_name,
2400 const IntExpr* const expr) override;
2401 void VisitIntegerVariable(const IntVar* const variable,
2402 IntExpr* const delegate) override;
2403 void VisitIntegerVariable(const IntVar* const variable,
2404 const std::string& operation, int64_t value,
2405 IntVar* const delegate) override;
2406 void VisitIntervalVariable(const IntervalVar* const variable,
2407 const std::string& operation, int64_t value,
2408 IntervalVar* const delegate) override;
2409 void VisitSequenceVariable(const SequenceVar* const variable) override;
2410 /// Integer arguments
2411 void VisitIntegerArgument(const std::string& arg_name,
2412 int64_t value) override;
2413 void VisitIntegerArrayArgument(const std::string& arg_name,
2414 const std::vector<int64_t>& values) override;
2415 void VisitIntegerMatrixArgument(const std::string& arg_name,
2416 const IntTupleSet& values) override;
2417 /// Variables.
2418 void VisitIntegerExpressionArgument(const std::string& arg_name,
2419 IntExpr* const argument) override;
2420 void VisitIntegerVariableArrayArgument(
2421 const std::string& arg_name,
2422 const std::vector<IntVar*>& arguments) override;
2423 /// Visit interval argument.
2424 void VisitIntervalArgument(const std::string& arg_name,
2425 IntervalVar* const argument) override;
2426 void VisitIntervalArrayArgument(
2427 const std::string& arg_name,
2428 const std::vector<IntervalVar*>& arguments) override;
2429 /// Visit sequence argument.
2430 void VisitSequenceArgument(const std::string& arg_name,
2431 SequenceVar* const argument) override;
2432 void VisitSequenceArrayArgument(
2433 const std::string& arg_name,
2434 const std::vector<SequenceVar*>& arguments) override;
2435
2436 protected:
2437 void PushArgumentHolder();
2438 void PopArgumentHolder();
2439 ArgumentHolder* Top() const;
2440
2441 private:
2442 std::vector<ArgumentHolder*> holders_;
2443 };
2444
2445 template <class T>
2446 class ArrayWithOffset : public BaseObject {
2447 public:
ArrayWithOffset(int64_t index_min,int64_t index_max)2448 ArrayWithOffset(int64_t index_min, int64_t index_max)
2449 : index_min_(index_min),
2450 index_max_(index_max),
2451 values_(new T[index_max - index_min + 1]) {
2452 DCHECK_LE(index_min, index_max);
2453 }
2454
~ArrayWithOffset()2455 ~ArrayWithOffset() override {}
2456
Evaluate(int64_t index)2457 virtual T Evaluate(int64_t index) const {
2458 DCHECK_GE(index, index_min_);
2459 DCHECK_LE(index, index_max_);
2460 return values_[index - index_min_];
2461 }
2462
SetValue(int64_t index,T value)2463 void SetValue(int64_t index, T value) {
2464 DCHECK_GE(index, index_min_);
2465 DCHECK_LE(index, index_max_);
2466 values_[index - index_min_] = value;
2467 }
2468
DebugString()2469 std::string DebugString() const override { return "ArrayWithOffset"; }
2470
2471 private:
2472 const int64_t index_min_;
2473 const int64_t index_max_;
2474 std::unique_ptr<T[]> values_;
2475 };
2476 #endif // SWIG
2477
2478 /// This class is a reversible growing array. In can grow in both
2479 /// directions, and even accept negative indices. The objects stored
2480 /// have a type T. As it relies on the solver for reversibility, these
2481 /// objects can be up-casted to 'C' when using Solver::SaveValue().
2482 template <class T, class C>
2483 class RevGrowingArray {
2484 public:
RevGrowingArray(int64_t block_size)2485 explicit RevGrowingArray(int64_t block_size)
2486 : block_size_(block_size), block_offset_(0) {
2487 CHECK_GT(block_size, 0);
2488 }
2489
~RevGrowingArray()2490 ~RevGrowingArray() {
2491 for (int i = 0; i < elements_.size(); ++i) {
2492 delete[] elements_[i];
2493 }
2494 }
2495
At(int64_t index)2496 T At(int64_t index) const {
2497 const int64_t block_index = ComputeBlockIndex(index);
2498 const int64_t relative_index = block_index - block_offset_;
2499 if (relative_index < 0 || relative_index >= elements_.size()) {
2500 return T();
2501 }
2502 const T* block = elements_[relative_index];
2503 return block != nullptr ? block[index - block_index * block_size_] : T();
2504 }
2505
RevInsert(Solver * const solver,int64_t index,T value)2506 void RevInsert(Solver* const solver, int64_t index, T value) {
2507 const int64_t block_index = ComputeBlockIndex(index);
2508 T* const block = GetOrCreateBlock(block_index);
2509 const int64_t residual = index - block_index * block_size_;
2510 solver->SaveAndSetValue(reinterpret_cast<C*>(&block[residual]),
2511 reinterpret_cast<C>(value));
2512 }
2513
2514 private:
NewBlock()2515 T* NewBlock() const {
2516 T* const result = new T[block_size_];
2517 for (int i = 0; i < block_size_; ++i) {
2518 result[i] = T();
2519 }
2520 return result;
2521 }
2522
GetOrCreateBlock(int block_index)2523 T* GetOrCreateBlock(int block_index) {
2524 if (elements_.size() == 0) {
2525 block_offset_ = block_index;
2526 GrowUp(block_index);
2527 } else if (block_index < block_offset_) {
2528 GrowDown(block_index);
2529 } else if (block_index - block_offset_ >= elements_.size()) {
2530 GrowUp(block_index);
2531 }
2532 T* block = elements_[block_index - block_offset_];
2533 if (block == nullptr) {
2534 block = NewBlock();
2535 elements_[block_index - block_offset_] = block;
2536 }
2537 return block;
2538 }
2539
ComputeBlockIndex(int64_t value)2540 int64_t ComputeBlockIndex(int64_t value) const {
2541 return value >= 0 ? value / block_size_
2542 : (value - block_size_ + 1) / block_size_;
2543 }
2544
GrowUp(int64_t block_index)2545 void GrowUp(int64_t block_index) {
2546 elements_.resize(block_index - block_offset_ + 1);
2547 }
2548
GrowDown(int64_t block_index)2549 void GrowDown(int64_t block_index) {
2550 const int64_t delta = block_offset_ - block_index;
2551 block_offset_ = block_index;
2552 DCHECK_GT(delta, 0);
2553 elements_.insert(elements_.begin(), delta, nullptr);
2554 }
2555
2556 const int64_t block_size_;
2557 std::vector<T*> elements_;
2558 int block_offset_;
2559 };
2560
2561 /// This is a special class to represent a 'residual' set of T. T must
2562 /// be an integer type. You fill it at first, and then during search,
2563 /// you can efficiently remove an element, and query the removed
2564 /// elements.
2565 template <class T>
2566 class RevIntSet {
2567 public:
2568 static constexpr int kNoInserted = -1;
2569
2570 /// Capacity is the fixed size of the set (it cannot grow).
RevIntSet(int capacity)2571 explicit RevIntSet(int capacity)
2572 : elements_(new T[capacity]),
2573 num_elements_(0),
2574 capacity_(capacity),
2575 position_(new int[capacity]),
2576 delete_position_(true) {
2577 for (int i = 0; i < capacity; ++i) {
2578 position_[i] = kNoInserted;
2579 }
2580 }
2581
2582 /// Capacity is the fixed size of the set (it cannot grow).
RevIntSet(int capacity,int * shared_positions,int shared_positions_size)2583 RevIntSet(int capacity, int* shared_positions, int shared_positions_size)
2584 : elements_(new T[capacity]),
2585 num_elements_(0),
2586 capacity_(capacity),
2587 position_(shared_positions),
2588 delete_position_(false) {
2589 for (int i = 0; i < shared_positions_size; ++i) {
2590 position_[i] = kNoInserted;
2591 }
2592 }
2593
~RevIntSet()2594 ~RevIntSet() {
2595 if (delete_position_) {
2596 delete[] position_;
2597 }
2598 }
2599
Size()2600 int Size() const { return num_elements_.Value(); }
2601
Capacity()2602 int Capacity() const { return capacity_; }
2603
Element(int i)2604 T Element(int i) const {
2605 DCHECK_GE(i, 0);
2606 DCHECK_LT(i, num_elements_.Value());
2607 return elements_[i];
2608 }
2609
RemovedElement(int i)2610 T RemovedElement(int i) const {
2611 DCHECK_GE(i, 0);
2612 DCHECK_LT(i + num_elements_.Value(), capacity_);
2613 return elements_[i + num_elements_.Value()];
2614 }
2615
Insert(Solver * const solver,const T & elt)2616 void Insert(Solver* const solver, const T& elt) {
2617 const int position = num_elements_.Value();
2618 DCHECK_LT(position, capacity_); /// Valid.
2619 DCHECK(NotAlreadyInserted(elt));
2620 elements_[position] = elt;
2621 position_[elt] = position;
2622 num_elements_.Incr(solver);
2623 }
2624
Remove(Solver * const solver,const T & value_index)2625 void Remove(Solver* const solver, const T& value_index) {
2626 num_elements_.Decr(solver);
2627 SwapTo(value_index, num_elements_.Value());
2628 }
2629
Restore(Solver * const solver,const T & value_index)2630 void Restore(Solver* const solver, const T& value_index) {
2631 SwapTo(value_index, num_elements_.Value());
2632 num_elements_.Incr(solver);
2633 }
2634
Clear(Solver * const solver)2635 void Clear(Solver* const solver) { num_elements_.SetValue(solver, 0); }
2636
2637 /// Iterators on the indices.
2638 typedef const T* const_iterator;
begin()2639 const_iterator begin() const { return elements_.get(); }
end()2640 const_iterator end() const { return elements_.get() + num_elements_.Value(); }
2641
2642 private:
2643 /// Used in DCHECK.
NotAlreadyInserted(const T & elt)2644 bool NotAlreadyInserted(const T& elt) {
2645 for (int i = 0; i < num_elements_.Value(); ++i) {
2646 if (elt == elements_[i]) {
2647 return false;
2648 }
2649 }
2650 return true;
2651 }
2652
SwapTo(T value_index,int next_position)2653 void SwapTo(T value_index, int next_position) {
2654 const int current_position = position_[value_index];
2655 if (current_position != next_position) {
2656 const T next_value_index = elements_[next_position];
2657 elements_[current_position] = next_value_index;
2658 elements_[next_position] = value_index;
2659 position_[value_index] = next_position;
2660 position_[next_value_index] = current_position;
2661 }
2662 }
2663
2664 /// Set of elements.
2665 std::unique_ptr<T[]> elements_;
2666 /// Number of elements in the set.
2667 NumericalRev<int> num_elements_;
2668 /// Number of elements in the set.
2669 const int capacity_;
2670 /// Reverse mapping.
2671 int* position_;
2672 /// Does the set owns the position array.
2673 const bool delete_position_;
2674 };
2675
2676 /// ----- RevPartialSequence -----
2677
2678 class RevPartialSequence {
2679 public:
RevPartialSequence(const std::vector<int> & items)2680 explicit RevPartialSequence(const std::vector<int>& items)
2681 : elements_(items),
2682 first_ranked_(0),
2683 last_ranked_(items.size() - 1),
2684 size_(items.size()),
2685 position_(new int[size_]) {
2686 for (int i = 0; i < size_; ++i) {
2687 elements_[i] = items[i];
2688 position_[i] = i;
2689 }
2690 }
2691
RevPartialSequence(int size)2692 explicit RevPartialSequence(int size)
2693 : elements_(size),
2694 first_ranked_(0),
2695 last_ranked_(size - 1),
2696 size_(size),
2697 position_(new int[size_]) {
2698 for (int i = 0; i < size_; ++i) {
2699 elements_[i] = i;
2700 position_[i] = i;
2701 }
2702 }
2703
~RevPartialSequence()2704 ~RevPartialSequence() {}
2705
NumFirstRanked()2706 int NumFirstRanked() const { return first_ranked_.Value(); }
2707
NumLastRanked()2708 int NumLastRanked() const { return size_ - 1 - last_ranked_.Value(); }
2709
Size()2710 int Size() const { return size_; }
2711
2712 #if !defined(SWIG)
2713 const int& operator[](int index) const {
2714 DCHECK_GE(index, 0);
2715 DCHECK_LT(index, size_);
2716 return elements_[index];
2717 }
2718 #endif
2719
RankFirst(Solver * const solver,int elt)2720 void RankFirst(Solver* const solver, int elt) {
2721 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
2722 SwapTo(elt, first_ranked_.Value());
2723 first_ranked_.Incr(solver);
2724 }
2725
RankLast(Solver * const solver,int elt)2726 void RankLast(Solver* const solver, int elt) {
2727 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
2728 SwapTo(elt, last_ranked_.Value());
2729 last_ranked_.Decr(solver);
2730 }
2731
IsRanked(int elt)2732 bool IsRanked(int elt) const {
2733 const int position = position_[elt];
2734 return (position < first_ranked_.Value() ||
2735 position > last_ranked_.Value());
2736 }
2737
DebugString()2738 std::string DebugString() const {
2739 std::string result = "[";
2740 for (int i = 0; i < first_ranked_.Value(); ++i) {
2741 absl::StrAppend(&result, elements_[i]);
2742 if (i != first_ranked_.Value() - 1) {
2743 result.append("-");
2744 }
2745 }
2746 result.append("|");
2747 for (int i = first_ranked_.Value(); i <= last_ranked_.Value(); ++i) {
2748 absl::StrAppend(&result, elements_[i]);
2749 if (i != last_ranked_.Value()) {
2750 result.append("-");
2751 }
2752 }
2753 result.append("|");
2754 for (int i = last_ranked_.Value() + 1; i < size_; ++i) {
2755 absl::StrAppend(&result, elements_[i]);
2756 if (i != size_ - 1) {
2757 result.append("-");
2758 }
2759 }
2760 result.append("]");
2761 return result;
2762 }
2763
2764 private:
SwapTo(int elt,int next_position)2765 void SwapTo(int elt, int next_position) {
2766 const int current_position = position_[elt];
2767 if (current_position != next_position) {
2768 const int next_elt = elements_[next_position];
2769 elements_[current_position] = next_elt;
2770 elements_[next_position] = elt;
2771 position_[elt] = next_position;
2772 position_[next_elt] = current_position;
2773 }
2774 }
2775
2776 /// Set of elements.
2777 std::vector<int> elements_;
2778 /// Position of the element after the last element ranked from the start.
2779 NumericalRev<int> first_ranked_;
2780 /// Position of the element before the last element ranked from the end.
2781 NumericalRev<int> last_ranked_;
2782 /// Number of elements in the sequence.
2783 const int size_;
2784 /// Reverse mapping.
2785 std::unique_ptr<int[]> position_;
2786 };
2787
2788 /// This class represents a reversible bitset. It is meant to represent a set of
2789 /// active bits. It does not offer direct access, but just methods that can
2790 /// reversibly subtract another bitset, or check if the current active bitset
2791 /// intersects with another bitset.
2792 class UnsortedNullableRevBitset {
2793 public:
2794 /// Size is the number of bits to store in the bitset.
2795 explicit UnsortedNullableRevBitset(int bit_size);
2796
~UnsortedNullableRevBitset()2797 ~UnsortedNullableRevBitset() {}
2798
2799 /// This methods overwrites the active bitset with the mask. This method
2800 /// should be called only once.
2801 void Init(Solver* const solver, const std::vector<uint64_t>& mask);
2802
2803 /// This method subtracts the mask from the active bitset. It returns true if
2804 /// the active bitset was changed in the process.
2805 bool RevSubtract(Solver* const solver, const std::vector<uint64_t>& mask);
2806
2807 /// This method ANDs the mask with the active bitset. It returns true if
2808 /// the active bitset was changed in the process.
2809 bool RevAnd(Solver* const solver, const std::vector<uint64_t>& mask);
2810
2811 /// This method returns the number of non null 64 bit words in the bitset
2812 /// representation.
ActiveWordSize()2813 int ActiveWordSize() const { return active_words_.Size(); }
2814
2815 /// This method returns true if the active bitset is null.
Empty()2816 bool Empty() const { return active_words_.Size() == 0; }
2817
2818 /// This method returns true iff the mask and the active bitset have a non
2819 /// null intersection. support_index is used as an accelerator:
2820 /// - The first word tested to check the intersection will be the
2821 /// '*support_index'th one.
2822 /// - If the intersection is not null, the support_index will be filled with
2823 /// the index of the word that does intersect with the mask. This can be
2824 /// reused later to speed-up the check.
2825 bool Intersects(const std::vector<uint64_t>& mask, int* support_index);
2826
2827 /// Returns the number of bits given in the constructor of the bitset.
bit_size()2828 int64_t bit_size() const { return bit_size_; }
2829 /// Returns the number of 64 bit words used to store the bitset.
word_size()2830 int64_t word_size() const { return word_size_; }
2831 /// Returns the set of active word indices.
active_words()2832 const RevIntSet<int>& active_words() const { return active_words_; }
2833
2834 private:
2835 void CleanUpActives(Solver* const solver);
2836
2837 const int64_t bit_size_;
2838 const int64_t word_size_;
2839 RevArray<uint64_t> bits_;
2840 RevIntSet<int> active_words_;
2841 std::vector<int> to_remove_;
2842 };
2843
2844 template <class T>
IsArrayConstant(const std::vector<T> & values,const T & value)2845 bool IsArrayConstant(const std::vector<T>& values, const T& value) {
2846 for (int i = 0; i < values.size(); ++i) {
2847 if (values[i] != value) {
2848 return false;
2849 }
2850 }
2851 return true;
2852 }
2853
2854 template <class T>
IsArrayBoolean(const std::vector<T> & values)2855 bool IsArrayBoolean(const std::vector<T>& values) {
2856 for (int i = 0; i < values.size(); ++i) {
2857 if (values[i] != 0 && values[i] != 1) {
2858 return false;
2859 }
2860 }
2861 return true;
2862 }
2863
2864 template <class T>
AreAllOnes(const std::vector<T> & values)2865 bool AreAllOnes(const std::vector<T>& values) {
2866 return IsArrayConstant(values, T(1));
2867 }
2868
2869 template <class T>
AreAllNull(const std::vector<T> & values)2870 bool AreAllNull(const std::vector<T>& values) {
2871 return IsArrayConstant(values, T(0));
2872 }
2873
2874 template <class T>
AreAllGreaterOrEqual(const std::vector<T> & values,const T & value)2875 bool AreAllGreaterOrEqual(const std::vector<T>& values, const T& value) {
2876 for (const T& current_value : values) {
2877 if (current_value < value) {
2878 return false;
2879 }
2880 }
2881 return true;
2882 }
2883
2884 template <class T>
AreAllLessOrEqual(const std::vector<T> & values,const T & value)2885 bool AreAllLessOrEqual(const std::vector<T>& values, const T& value) {
2886 for (const T& current_value : values) {
2887 if (current_value > value) {
2888 return false;
2889 }
2890 }
2891 return true;
2892 }
2893
2894 template <class T>
AreAllPositive(const std::vector<T> & values)2895 bool AreAllPositive(const std::vector<T>& values) {
2896 return AreAllGreaterOrEqual(values, T(0));
2897 }
2898
2899 template <class T>
AreAllNegative(const std::vector<T> & values)2900 bool AreAllNegative(const std::vector<T>& values) {
2901 return AreAllLessOrEqual(values, T(0));
2902 }
2903
2904 template <class T>
AreAllStrictlyPositive(const std::vector<T> & values)2905 bool AreAllStrictlyPositive(const std::vector<T>& values) {
2906 return AreAllGreaterOrEqual(values, T(1));
2907 }
2908
2909 template <class T>
AreAllStrictlyNegative(const std::vector<T> & values)2910 bool AreAllStrictlyNegative(const std::vector<T>& values) {
2911 return AreAllLessOrEqual(values, T(-1));
2912 }
2913
2914 template <class T>
IsIncreasingContiguous(const std::vector<T> & values)2915 bool IsIncreasingContiguous(const std::vector<T>& values) {
2916 for (int i = 0; i < values.size() - 1; ++i) {
2917 if (values[i + 1] != values[i] + 1) {
2918 return false;
2919 }
2920 }
2921 return true;
2922 }
2923
2924 template <class T>
IsIncreasing(const std::vector<T> & values)2925 bool IsIncreasing(const std::vector<T>& values) {
2926 for (int i = 0; i < values.size() - 1; ++i) {
2927 if (values[i + 1] < values[i]) {
2928 return false;
2929 }
2930 }
2931 return true;
2932 }
2933
2934 template <class T>
IsArrayInRange(const std::vector<IntVar * > & vars,T range_min,T range_max)2935 bool IsArrayInRange(const std::vector<IntVar*>& vars, T range_min,
2936 T range_max) {
2937 for (int i = 0; i < vars.size(); ++i) {
2938 if (vars[i]->Min() < range_min || vars[i]->Max() > range_max) {
2939 return false;
2940 }
2941 }
2942 return true;
2943 }
2944
AreAllBound(const std::vector<IntVar * > & vars)2945 inline bool AreAllBound(const std::vector<IntVar*>& vars) {
2946 for (int i = 0; i < vars.size(); ++i) {
2947 if (!vars[i]->Bound()) {
2948 return false;
2949 }
2950 }
2951 return true;
2952 }
2953
AreAllBooleans(const std::vector<IntVar * > & vars)2954 inline bool AreAllBooleans(const std::vector<IntVar*>& vars) {
2955 return IsArrayInRange(vars, 0, 1);
2956 }
2957
2958 /// Returns true if all the variables are assigned to a single value,
2959 /// or if their corresponding value is null.
2960 template <class T>
AreAllBoundOrNull(const std::vector<IntVar * > & vars,const std::vector<T> & values)2961 bool AreAllBoundOrNull(const std::vector<IntVar*>& vars,
2962 const std::vector<T>& values) {
2963 for (int i = 0; i < vars.size(); ++i) {
2964 if (values[i] != 0 && !vars[i]->Bound()) {
2965 return false;
2966 }
2967 }
2968 return true;
2969 }
2970
2971 /// Returns true if all variables are assigned to 'value'.
AreAllBoundTo(const std::vector<IntVar * > & vars,int64_t value)2972 inline bool AreAllBoundTo(const std::vector<IntVar*>& vars, int64_t value) {
2973 for (int i = 0; i < vars.size(); ++i) {
2974 if (!vars[i]->Bound() || vars[i]->Min() != value) {
2975 return false;
2976 }
2977 }
2978 return true;
2979 }
2980
MaxVarArray(const std::vector<IntVar * > & vars)2981 inline int64_t MaxVarArray(const std::vector<IntVar*>& vars) {
2982 DCHECK(!vars.empty());
2983 int64_t result = kint64min;
2984 for (int i = 0; i < vars.size(); ++i) {
2985 /// The std::max<int64_t> is needed for compilation on MSVC.
2986 result = std::max<int64_t>(result, vars[i]->Max());
2987 }
2988 return result;
2989 }
2990
MinVarArray(const std::vector<IntVar * > & vars)2991 inline int64_t MinVarArray(const std::vector<IntVar*>& vars) {
2992 DCHECK(!vars.empty());
2993 int64_t result = kint64max;
2994 for (int i = 0; i < vars.size(); ++i) {
2995 /// The std::min<int64_t> is needed for compilation on MSVC.
2996 result = std::min<int64_t>(result, vars[i]->Min());
2997 }
2998 return result;
2999 }
3000
FillValues(const std::vector<IntVar * > & vars,std::vector<int64_t> * const values)3001 inline void FillValues(const std::vector<IntVar*>& vars,
3002 std::vector<int64_t>* const values) {
3003 values->clear();
3004 values->resize(vars.size());
3005 for (int i = 0; i < vars.size(); ++i) {
3006 (*values)[i] = vars[i]->Value();
3007 }
3008 }
3009
PosIntDivUp(int64_t e,int64_t v)3010 inline int64_t PosIntDivUp(int64_t e, int64_t v) {
3011 DCHECK_GT(v, 0);
3012 return (e < 0 || e % v == 0) ? e / v : e / v + 1;
3013 }
3014
PosIntDivDown(int64_t e,int64_t v)3015 inline int64_t PosIntDivDown(int64_t e, int64_t v) {
3016 DCHECK_GT(v, 0);
3017 return (e >= 0 || e % v == 0) ? e / v : e / v - 1;
3018 }
3019
3020 std::vector<int64_t> ToInt64Vector(const std::vector<int>& input);
3021
3022 #if !defined(SWIG)
3023 // A PathState represents a set of paths and changed made on it.
3024 //
3025 // More accurately, let us define P_{num_nodes, starts, ends}-graphs the set of
3026 // directed graphs with nodes [0, num_nodes) whose connected components are
3027 // paths from starts[i] to ends[i] (for the same i) and loops.
3028 // Let us fix num_nodes, starts and ends so we call these P-graphs.
3029 //
3030 // Let us define some notions on graphs with the same set of nodes:
3031 // tails(D) is the set of nodes that are the tail of some arc of D.
3032 // P0 inter P1 is the graph of all arcs both in P0 and P1.
3033 // P0 union P1 is the graph of all arcs either in P0 or P1.
3034 // P1 - P0 is the graph with arcs in P1 and not in P0.
3035 // P0 |> D is the graph with arcs of P0 whose tail is not in tails(D).
3036 // P0 + D is (P0 |> D) union D.
3037 //
3038 // Now suppose P0 and P1 are P-graphs.
3039 // P0 + (P1 - P0) is exactly P1.
3040 // Moreover, note that P0 |> D is not a union of paths from some starts[i] to
3041 // ends[i] and loops like P0, because the operation removes arcs from P0.
3042 // P0 |> D is a union of generic paths, loops, and isolated nodes.
3043 // Let us call the generic paths and isolated nodes "chains".
3044 // Then the paths of P0 + D are chains linked by arcs of D.
3045 // Those chains are particularly interesting when examining a P-graph change.
3046 //
3047 // A PathState represents a P-graph for a fixed {num_nodes, starts, ends}.
3048 // The value of a PathState can be changed incrementally from P0 to P1
3049 // by passing the arcs of P1 - P0 to ChangeNext() and marking the end of the
3050 // change with a call to CutChains().
3051 // If P0 + D is not a P-graph, the behaviour is undefined.
3052 // TODO(user): check whether we want to have a DCHECK that P0 + D
3053 // is a P-graph or if CutChains() should return false.
3054 //
3055 // After CutChains(), tails(D) can be traversed using an iterator,
3056 // and the chains of P0 |> D can be browsed by chain-based iterators.
3057 // An iterator allows to browse the set of paths that have changed.
3058 // Then Commit() or Revert() can be called: Commit() changes the PathState to
3059 // represent P1 = P0 + D, all further changes are made from P1; Revert() changes
3060 // the PathState to forget D completely and return the state to P0.
3061 //
3062 // After a Commit(), Revert() or at initial state, the same iterators are
3063 // available and represent the change by an empty D: the set of changed paths
3064 // and the set of changed nodes is empty. Still, the chain-based iterator allows
3065 // to browse paths: each path has exactly one chain.
3066 class PathState {
3067 public:
3068 // A Chain allows to iterate on all nodes of a chain, and access some data:
3069 // first node, last node, number of nodes in the chain.
3070 // Chain is a range, its iterator ChainNodeIterator, its value type int.
3071 // Chains are returned by PathChainIterator's operator*().
3072 class Chain;
3073 // A ChainRange allows to iterate on all chains of a path.
3074 // ChainRange is a range, its iterator Chain*, its value type Chain.
3075 class ChainRange;
3076 // A NodeRange allows to iterate on all nodes of a path.
3077 // NodeRange is a range, its iterator PathNodeIterator, its value type int.
3078 class NodeRange;
3079
3080 // Path constructor: path_start and path_end must be disjoint,
3081 // their values in [0, num_nodes).
3082 PathState(int num_nodes, std::vector<int> path_start,
3083 std::vector<int> path_end);
3084
3085 // Instance-constant accessors.
3086
3087 // Returns the number of nodes in the underlying graph.
NumNodes()3088 int NumNodes() const { return num_nodes_; }
3089 // Returns the number of paths (empty paths included).
NumPaths()3090 int NumPaths() const { return num_paths_; }
3091 // Returns the start of a path.
Start(int path)3092 int Start(int path) const { return path_start_end_[path].start; }
3093 // Returns the end of a path.
End(int path)3094 int End(int path) const { return path_start_end_[path].end; }
3095
3096 // State-dependent accessors.
3097
3098 // Returns the committed path of a given node, -1 if it is a loop.
Path(int node)3099 int Path(int node) const {
3100 return committed_nodes_[committed_index_[node]].path;
3101 }
3102 // Returns the set of arcs that have been added,
3103 // i.e. that were changed and were not in the committed state.
ChangedArcs()3104 const std::vector<std::pair<int, int>>& ChangedArcs() const {
3105 return changed_arcs_;
3106 }
3107 // Returns the set of paths that actually changed,
3108 // i.e. that have an arc in ChangedArcs().
ChangedPaths()3109 const std::vector<int>& ChangedPaths() const { return changed_paths_; }
3110 // Returns the current range of chains of path.
3111 ChainRange Chains(int path) const;
3112 // Returns the current range of nodes of path.
3113 NodeRange Nodes(int path) const;
3114
3115 // State modifiers.
3116
3117 // Adds arc (node, new_next) to the changed state, more formally,
3118 // changes the state from (P0, D) to (P0, D + (node, new_next)).
ChangeNext(int node,int new_next)3119 void ChangeNext(int node, int new_next) {
3120 changed_arcs_.emplace_back(node, new_next);
3121 }
3122 // Marks the end of ChangeNext() sequence, more formally,
3123 // changes the state from (P0, D) to (P0 |> D, D).
3124 void CutChains();
3125 // Makes the current temporary state permanent, more formally,
3126 // changes the state from (P0 |> D, D) to (P0 + D, \emptyset),
3127 void Commit();
3128 // Erase incremental changes made by ChangeNext() and CutChains(),
3129 // more formally, changes the state from (P0 |> D, D) to (P0, \emptyset).
3130 void Revert();
3131
3132 // LNS Operators may not fix variables,
3133 // in which case we mark the candidate invalid.
SetInvalid()3134 void SetInvalid() { is_invalid_ = true; }
IsInvalid()3135 bool IsInvalid() const { return is_invalid_; }
3136
3137 private:
3138 // Most structs below are named pairs of ints, for typing purposes.
3139
3140 // Start and end are stored together to optimize (likely) simultaneous access.
3141 struct PathStartEnd {
PathStartEndPathStartEnd3142 PathStartEnd(int start, int end) : start(start), end(end) {}
3143 int start;
3144 int end;
3145 };
3146 // Paths are ranges of chains, which are ranges of committed nodes, see below.
3147 struct PathBounds {
3148 int begin_index;
3149 int end_index;
3150 };
3151 struct ChainBounds {
3152 ChainBounds() = default;
ChainBoundsChainBounds3153 ChainBounds(int begin_index, int end_index)
3154 : begin_index(begin_index), end_index(end_index) {}
3155 int begin_index;
3156 int end_index;
3157 };
3158 struct CommittedNode {
CommittedNodeCommittedNode3159 CommittedNode(int node, int path) : node(node), path(path) {}
3160 int node;
3161 // Path of node in the committed state, -1 for loop nodes.
3162 // TODO(user): check if path would be better stored
3163 // with committed_index_, or in its own vector, or just recomputed.
3164 int path;
3165 };
3166 // Used in temporary structures, see below.
3167 struct TailHeadIndices {
3168 int tail_index;
3169 int head_index;
3170 };
3171 struct IndexArc {
3172 int index;
3173 int arc;
3174 bool operator<(const IndexArc& other) const { return index < other.index; }
3175 };
3176
3177 // From changed_paths_ and changed_arcs_, fill chains_ and paths_.
3178 // Selection-based algorithm in O(n^2), to use for small change sets.
3179 void MakeChainsFromChangedPathsAndArcsWithSelectionAlgorithm();
3180 // From changed_paths_ and changed_arcs_, fill chains_ and paths_.
3181 // Generic algorithm in O(std::sort(n)+n), to use for larger change sets.
3182 void MakeChainsFromChangedPathsAndArcsWithGenericAlgorithm();
3183
3184 // Copies nodes in chains of path at the end of nodes,
3185 // and sets those nodes' path member to value path.
3186 void CopyNewPathAtEndOfNodes(int path);
3187 // Commits paths in O(#{changed paths' nodes}) time,
3188 // increasing this object's space usage by O(|changed path nodes|).
3189 void IncrementalCommit();
3190 // Commits paths in O(num_nodes + num_paths) time,
3191 // reducing this object's space usage to O(num_nodes + num_paths).
3192 void FullCommit();
3193
3194 // Instance-constant data.
3195 const int num_nodes_;
3196 const int num_paths_;
3197 std::vector<PathStartEnd> path_start_end_;
3198
3199 // Representation of the committed and changed paths.
3200 // A path is a range of chains, which is a range of nodes.
3201 // Ranges are represented internally by indices in vectors:
3202 // ChainBounds are indices in committed_nodes_. PathBounds are indices in
3203 // chains_. When committed (after construction, Revert() or Commit()):
3204 // - path ranges are [path, path+1): they have one chain.
3205 // - chain ranges don't overlap, chains_ has an empty sentinel at the end.
3206 // - committed_nodes_ contains all nodes and old duplicates may appear,
3207 // the current version of a node is at the index given by
3208 // committed_index_[node]. A Commit() can add nodes at the end of
3209 // committed_nodes_ in a space/time tradeoff, but if committed_nodes_' size
3210 // is above num_nodes_threshold_, Commit() must reclaim useless duplicates'
3211 // space by rewriting the path/chain/nodes structure.
3212 // When changed (after CutChains()), new chains are computed,
3213 // and the structure is updated accordingly:
3214 // - path ranges that were changed have nonoverlapping values [begin, end)
3215 // where begin is >= num_paths_ + 1, i.e. new chains are stored after
3216 // committed state.
3217 // - additional chain ranges are stored after the committed chains
3218 // to represent the new chains resulting from the changes.
3219 // Those chains do not overlap with each other or with unchanged chains.
3220 // An empty sentinel chain is added at the end of additional chains.
3221 // - committed_nodes_ are not modified, and still represent the committed
3222 // paths.
3223 // committed_index_ is not modified either.
3224 std::vector<CommittedNode> committed_nodes_;
3225 std::vector<int> committed_index_;
3226 const int num_nodes_threshold_;
3227 std::vector<ChainBounds> chains_;
3228 std::vector<PathBounds> paths_;
3229
3230 // Incremental information: indices of nodes whose successor have changed,
3231 // path that have changed nodes.
3232 std::vector<std::pair<int, int>> changed_arcs_;
3233 std::vector<int> changed_paths_;
3234 std::vector<bool> path_has_changed_;
3235
3236 // Temporary structures, since they will be reused heavily,
3237 // those are members in order to be allocated once and for all.
3238 std::vector<TailHeadIndices> tail_head_indices_;
3239 std::vector<IndexArc> arcs_by_tail_index_;
3240 std::vector<IndexArc> arcs_by_head_index_;
3241 std::vector<int> next_arc_;
3242
3243 // See IsInvalid() and SetInvalid().
3244 bool is_invalid_ = false;
3245 };
3246
3247 // A Chain is a range of committed nodes.
3248 class PathState::Chain {
3249 public:
3250 class Iterator {
3251 public:
3252 Iterator& operator++() {
3253 ++current_node_;
3254 return *this;
3255 }
3256 int operator*() const { return current_node_->node; }
3257 bool operator!=(Iterator other) const {
3258 return current_node_ != other.current_node_;
3259 }
3260
3261 private:
3262 // Only a Chain can construct its iterator.
3263 friend class PathState::Chain;
Iterator(const CommittedNode * node)3264 explicit Iterator(const CommittedNode* node) : current_node_(node) {}
3265 const CommittedNode* current_node_;
3266 };
3267
3268 // Chains hold CommittedNode* values, a Chain may be invalidated
3269 // if the underlying vector is modified.
Chain(const CommittedNode * begin_node,const CommittedNode * end_node)3270 Chain(const CommittedNode* begin_node, const CommittedNode* end_node)
3271 : begin_(begin_node), end_(end_node) {}
3272
NumNodes()3273 int NumNodes() const { return end_ - begin_; }
First()3274 int First() const { return begin_->node; }
Last()3275 int Last() const { return (end_ - 1)->node; }
begin()3276 Iterator begin() const { return Iterator(begin_); }
end()3277 Iterator end() const { return Iterator(end_); }
3278
3279 private:
3280 const CommittedNode* const begin_;
3281 const CommittedNode* const end_;
3282 };
3283
3284 // A ChainRange is a range of Chains, committed or not.
3285 class PathState::ChainRange {
3286 public:
3287 class Iterator {
3288 public:
3289 Iterator& operator++() {
3290 ++current_chain_;
3291 return *this;
3292 }
3293 Chain operator*() const {
3294 return {first_node_ + current_chain_->begin_index,
3295 first_node_ + current_chain_->end_index};
3296 }
3297 bool operator!=(Iterator other) const {
3298 return current_chain_ != other.current_chain_;
3299 }
3300
3301 private:
3302 // Only a ChainRange can construct its Iterator.
3303 friend class ChainRange;
Iterator(const ChainBounds * chain,const CommittedNode * const first_node)3304 Iterator(const ChainBounds* chain, const CommittedNode* const first_node)
3305 : current_chain_(chain), first_node_(first_node) {}
3306 const ChainBounds* current_chain_;
3307 const CommittedNode* const first_node_;
3308 };
3309
3310 // ChainRanges hold ChainBounds* and CommittedNode*,
3311 // a ChainRange may be invalidated if on of the underlying vector is modified.
ChainRange(const ChainBounds * const begin_chain,const ChainBounds * const end_chain,const CommittedNode * const first_node)3312 ChainRange(const ChainBounds* const begin_chain,
3313 const ChainBounds* const end_chain,
3314 const CommittedNode* const first_node)
3315 : begin_(begin_chain), end_(end_chain), first_node_(first_node) {}
3316
begin()3317 Iterator begin() const { return {begin_, first_node_}; }
end()3318 Iterator end() const { return {end_, first_node_}; }
3319
3320 private:
3321 const ChainBounds* const begin_;
3322 const ChainBounds* const end_;
3323 const CommittedNode* const first_node_;
3324 };
3325
3326 // A NodeRange allows to iterate on all nodes of a path,
3327 // by a two-level iteration on ChainBounds* and CommittedNode* of a PathState.
3328 class PathState::NodeRange {
3329 public:
3330 class Iterator {
3331 public:
3332 Iterator& operator++() {
3333 ++current_node_;
3334 if (current_node_ == end_node_) {
3335 ++current_chain_;
3336 // Note: dereferencing bounds is valid because there is a sentinel
3337 // value at the end of PathState::chains_ to that intent.
3338 const ChainBounds bounds = *current_chain_;
3339 current_node_ = first_node_ + bounds.begin_index;
3340 end_node_ = first_node_ + bounds.end_index;
3341 }
3342 return *this;
3343 }
3344 int operator*() const { return current_node_->node; }
3345 bool operator!=(Iterator other) const {
3346 return current_chain_ != other.current_chain_;
3347 }
3348
3349 private:
3350 // Only a NodeRange can construct its Iterator.
3351 friend class NodeRange;
Iterator(const ChainBounds * current_chain,const CommittedNode * const first_node)3352 Iterator(const ChainBounds* current_chain,
3353 const CommittedNode* const first_node)
3354 : current_node_(first_node + current_chain->begin_index),
3355 end_node_(first_node + current_chain->end_index),
3356 current_chain_(current_chain),
3357 first_node_(first_node) {}
3358 const CommittedNode* current_node_;
3359 const CommittedNode* end_node_;
3360 const ChainBounds* current_chain_;
3361 const CommittedNode* const first_node_;
3362 };
3363
3364 // NodeRanges hold ChainBounds* and CommittedNode*,
3365 // a NodeRange may be invalidated if on of the underlying vector is modified.
NodeRange(const ChainBounds * begin_chain,const ChainBounds * end_chain,const CommittedNode * first_node)3366 NodeRange(const ChainBounds* begin_chain, const ChainBounds* end_chain,
3367 const CommittedNode* first_node)
3368 : begin_chain_(begin_chain),
3369 end_chain_(end_chain),
3370 first_node_(first_node) {}
begin()3371 Iterator begin() const { return {begin_chain_, first_node_}; }
3372 // Note: there is a sentinel value at the end of PathState::chains_,
3373 // so dereferencing chain_range_.end()->begin_ is always valid.
end()3374 Iterator end() const { return {end_chain_, first_node_}; }
3375
3376 private:
3377 const ChainBounds* begin_chain_;
3378 const ChainBounds* end_chain_;
3379 const CommittedNode* const first_node_;
3380 };
3381
3382 // This checker enforces unary dimension requirements.
3383 // A unary dimension requires that there is some valuation of
3384 // node_capacity and demand such that for all paths,
3385 // if arc A -> B is on a path of path_class p,
3386 // then node_capacity[A] + demand[p][A] = node_capacity[B].
3387 // Moreover, all node_capacities of a path must be inside interval
3388 // path_capacity[path].
3389 // Note that Intervals have two meanings:
3390 // - for demand and node_capacity, those are values allowed for each associated
3391 // decision variable.
3392 // - for path_capacity, those are set of values that node_capacities of the path
3393 // must respect.
3394 // If the path capacity of a path is [kint64min, kint64max],
3395 // then the unary dimension requirements are not enforced on this path.
3396 class UnaryDimensionChecker {
3397 public:
3398 struct Interval {
3399 int64_t min;
3400 int64_t max;
3401 };
3402
3403 UnaryDimensionChecker(const PathState* path_state,
3404 std::vector<Interval> path_capacity,
3405 std::vector<int> path_class,
3406 std::vector<std::vector<Interval>> demand,
3407 std::vector<Interval> node_capacity);
3408
3409 // Given the change made in PathState, checks that the unary dimension
3410 // constraint is still feasible.
3411 bool Check() const;
3412
3413 // Commits to the changes made in PathState,
3414 // must be called before PathState::Commit().
3415 void Commit();
3416
3417 private:
3418 // Range min/max query on partial_demand_sums_.
3419 // The first_node and last_node MUST form a subpath in the committed state.
3420 // Nodes first_node and last_node are passed by their index in precomputed
3421 // data, they must be committed in some path, and it has to be the same path.
3422 // See partial_demand_sums_.
3423 Interval GetMinMaxPartialDemandSum(int first_node_index,
3424 int last_node_index) const;
3425
3426 // Queries whether all nodes in the committed subpath [first_node, last_node]
3427 // have fixed demands and trivial node_capacity [kint64min, kint64max].
3428 // first_node and last_node MUST form a subpath in the committed state.
3429 // Nodes are passed by their index in precomputed data.
3430 bool SubpathOnlyHasTrivialNodes(int first_node_index,
3431 int last_node_index) const;
3432
3433 // Commits to the current solution and rebuilds structures from scratch.
3434 void FullCommit();
3435 // Commits to the current solution and only build structures for paths that
3436 // changed, using additional space to do so in a time-memory tradeoff.
3437 void IncrementalCommit();
3438 // Adds sums of given path to the bottom layer of the RMQ structure,
3439 // updates index_ and previous_nontrivial_index_.
3440 void AppendPathDemandsToSums(int path);
3441 // Updates the RMQ structure from its bottom layer,
3442 // with [begin_index, end_index) the range of the change,
3443 // which must be at the end of the bottom layer.
3444 // Supposes that requests overlapping the range will be inside the range,
3445 // to avoid updating all layers.
3446 void UpdateRMQStructure(int begin_index, int end_index);
3447
3448 const PathState* const path_state_;
3449 const std::vector<Interval> path_capacity_;
3450 const std::vector<int> path_class_;
3451 const std::vector<std::vector<Interval>> demand_;
3452 const std::vector<Interval> node_capacity_;
3453
3454 // Precomputed data.
3455 // Maps nodes to their pre-computed data, except for isolated nodes,
3456 // which do not have precomputed data.
3457 // Only valid for nodes that are in some path in the committed state.
3458 std::vector<int> index_;
3459 // Implementation of a <O(n log n), O(1)> range min/max query, n = #nodes.
3460 // partial_demand_sums_rmq_[0][index_[node]] contains the sum of demands
3461 // from the start of the node's path to the node.
3462 // If node is the start of path, the sum is demand_[path_class_[path]][node],
3463 // moreover partial_demand_sums_rmq_[0][index_[node]-1] is {0, 0}.
3464 // partial_demand_sums_rmq_[layer][index] contains an interval
3465 // [min_value, max_value] such that min_value is
3466 // min(partial_demand_sums_rmq_[0][index+i].min | i in [0, 2^layer)),
3467 // similarly max_value is the maximum of .max on the same range.
3468 std::vector<std::vector<Interval>> partial_demand_sums_rmq_;
3469 // The incremental branch of Commit() may waste space in the layers of the
3470 // RMQ structure. This is the upper limit of a layer's size.
3471 const int maximum_partial_demand_layer_size_;
3472 // previous_nontrivial_index_[index_[node]] has the index of the previous
3473 // node on its committed path that has nonfixed demand or nontrivial node
3474 // capacity. This allows for O(1) queries that all nodes on a subpath
3475 // are nonfixed and nontrivial.
3476 std::vector<int> previous_nontrivial_index_;
3477 };
3478
3479 // Make a filter that takes ownership of a PathState and synchronizes it with
3480 // solver events. The solver represents a graph with array of variables 'nexts'.
3481 // Solver events are embodied by Assignment* deltas, that are translated to node
3482 // changes during Relax(), committed during Synchronize(), and reverted on
3483 // Revert().
3484 LocalSearchFilter* MakePathStateFilter(Solver* solver,
3485 std::unique_ptr<PathState> path_state,
3486 const std::vector<IntVar*>& nexts);
3487
3488 // Make a filter that translates solver events to the input checker's interface.
3489 // Since UnaryDimensionChecker has a PathState, the filter returned by this
3490 // must be synchronized to the corresponding PathStateFilter:
3491 // - Relax() must be called after the PathStateFilter's.
3492 // - Accept() must be called after.
3493 // - Synchronize() must be called before.
3494 // - Revert() must be called before.
3495 LocalSearchFilter* MakeUnaryDimensionFilter(
3496 Solver* solver, std::unique_ptr<UnaryDimensionChecker> checker,
3497 const std::string& dimension_name);
3498
3499 #endif // !defined(SWIG)
3500
3501 } // namespace operations_research
3502
3503 #endif // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
3504