49#ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
50#define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
63#include "absl/algorithm/container.h"
64#include "absl/container/flat_hash_map.h"
65#include "absl/container/flat_hash_set.h"
66#include "absl/log/check.h"
67#include "absl/strings/str_cat.h"
68#include "absl/strings/str_format.h"
69#include "absl/time/time.h"
70#include "absl/types/span.h"
115 IntVar*
Var()
override;
148 enum { CHUNK_SIZE = 16 };
151 const Chunk*
const next;
152 explicit Chunk(
const Chunk* next) : next(next) {}
160 : chunk_(l->chunks_), value_(l->
Last()) {}
161 bool ok()
const {
return (value_ !=
nullptr); }
165 if (value_ == chunk_->data + CHUNK_SIZE) {
166 chunk_ = chunk_->next;
167 value_ = chunk_ ? chunk_->data :
nullptr;
179 if (pos_.
Value() == 0) {
180 Chunk*
const chunk = s->UnsafeRevAlloc(
new Chunk(chunks_));
182 reinterpret_cast<void*
>(chunk));
183 pos_.SetValue(s, CHUNK_SIZE - 1);
187 chunks_->data[pos_.
Value()] = val;
192 if (chunks_ ==
nullptr ||
LastValue() != val) {
199 return chunks_ ? &chunks_->data[pos_.Value()] :
nullptr;
202 T*
MutableLast() {
return chunks_ ? &chunks_->data[pos_.
Value()] :
nullptr; }
207 return chunks_->data[pos_.Value()];
213 chunks_->data[pos_.Value()] = v;
223inline uint64_t
Hash1(uint64_t value) {
224 value = (~value) + (value << 21);
225 value ^= value >> 24;
226 value += (value << 3) + (value << 8);
227 value ^= value >> 14;
228 value += (value << 2) + (value << 4);
229 value ^= value >> 28;
230 value += (value << 31);
234inline uint64_t
Hash1(uint32_t value) {
236 a = (a + 0x7ed55d16) + (a << 12);
237 a = (a ^ 0xc761c23c) ^ (a >> 19);
238 a = (a + 0x165667b1) + (a << 5);
239 a = (a + 0xd3a2646c) ^ (a << 9);
240 a = (a + 0xfd7046c5) + (a << 3);
241 a = (a ^ 0xb55a4f09) ^ (a >> 16);
245inline uint64_t
Hash1(int64_t value) {
246 return Hash1(
static_cast<uint64_t
>(value));
249inline uint64_t
Hash1(
int value) {
return Hash1(
static_cast<uint32_t
>(value)); }
251inline uint64_t
Hash1(
void*
const ptr) {
252#if defined(__x86_64__) || defined(_M_X64) || defined(__powerpc64__) || \
253 defined(__aarch64__) || (defined(_MIPS_SZPTR) && (_MIPS_SZPTR == 64))
254 return Hash1(
reinterpret_cast<uint64_t
>(ptr));
256 return Hash1(
reinterpret_cast<uint32_t
>(ptr));
261uint64_t
Hash1(
const std::vector<T*>& ptrs) {
262 if (ptrs.empty())
return 0;
263 if (ptrs.size() == 1)
return Hash1(ptrs[0]);
264 uint64_t hash =
Hash1(ptrs[0]);
265 for (
int i = 1; i < ptrs.size(); ++i) {
266 hash = hash * i +
Hash1(ptrs[i]);
271inline uint64_t
Hash1(
const std::vector<int64_t>& ptrs) {
272 if (ptrs.empty())
return 0;
273 if (ptrs.size() == 1)
return Hash1(ptrs[0]);
274 uint64_t hash =
Hash1(ptrs[0]);
275 for (
int i = 1; i < ptrs.size(); ++i) {
276 hash = hash * i +
Hash1(ptrs[i]);
283template <
class K,
class V>
284class RevImmutableMultiMap {
288 array_(solver->UnsafeRevAllocArray(
new Cell*[initial_size])),
291 memset(array_, 0,
sizeof(*array_) * size_.Value());
301 Cell* tmp = array_[code];
303 if (tmp->key() == key) {
316 Cell* tmp = array_[code];
318 if (tmp->key() == key) {
323 return default_value;
327 void Insert(
const K& key,
const V& value) {
328 const int position =
Hash1(key) % size_.
Value();
330 solver_->UnsafeRevAlloc(
new Cell(key, value, array_[position]));
332 reinterpret_cast<void*
>(cell));
333 num_items_.
Incr(solver_);
334 if (num_items_.Value() > 2 * size_.Value()) {
342 Cell(
const K& key,
const V& value, Cell*
const next)
343 : key_(key), value_(value), next_(next) {}
345 void SetRevNext(Solver*
const solver, Cell*
const next) {
346 solver->SaveAndSetValue(
reinterpret_cast<void**
>(&next_),
347 reinterpret_cast<void*
>(next));
350 Cell* next()
const {
return next_; }
352 const K& key()
const {
return key_; }
354 const V& value()
const {
return value_; }
363 Cell**
const old_cell_array = array_;
364 const int old_size = size_.Value();
365 size_.SetValue(solver_, size_.Value() * 2);
366 solver_->SaveAndSetValue(
367 reinterpret_cast<void**
>(&array_),
368 reinterpret_cast<void*
>(
369 solver_->UnsafeRevAllocArray(
new Cell*[size_.Value()])));
370 memset(array_, 0, size_.Value() *
sizeof(*array_));
371 for (
int i = 0;
i < old_size; ++
i) {
372 Cell* tmp = old_cell_array[
i];
373 while (tmp !=
nullptr) {
374 Cell*
const to_reinsert = tmp;
376 const uint64_t new_position =
Hash1(to_reinsert->key()) % size_.Value();
377 to_reinsert->SetRevNext(solver_, array_[new_position]);
378 solver_->SaveAndSetValue(
379 reinterpret_cast<void**
>(&array_[new_position]),
380 reinterpret_cast<void*
>(to_reinsert));
385 Solver*
const solver_;
387 NumericalRev<int> size_;
388 NumericalRev<int> num_items_;
396 bool Switched()
const {
return value_; }
398 void Switch(Solver*
const solver) { solver->SaveAndSetValue(&value_,
true); }
441 bool IsSet(int64_t index)
const;
458 void Save(
Solver* solver,
int offset);
460 const int64_t length_;
476 bool IsSet(int64_t row, int64_t column)
const {
478 DCHECK_LT(row, rows_);
479 DCHECK_GE(column, 0);
480 DCHECK_LT(column, columns_);
497 const int64_t columns_;
510 CallMethod0(T*
const ct,
void (T::*method)(),
const std::string& name)
511 : constraint_(ct), method_(method), name_(name) {}
515 void Run(
Solver*
const)
override { (constraint_->*method_)(); }
518 return "CallMethod_" + name_ +
"(" + constraint_->DebugString() +
")";
522 T*
const constraint_;
523 void (T::*
const method_)();
524 const std::string name_;
529 const std::string& name) {
535 return absl::StrCat(param);
541 return param->DebugString();
545template <
class T,
class P>
546class CallMethod1 :
public Demon {
548 CallMethod1(T*
const ct,
void (T::*method)(P),
const std::string& name,
550 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
554 void Run(
Solver*
const)
override { (constraint_->*method_)(param1_); }
557 return absl::StrCat(
"CallMethod_", name_,
"(", constraint_->DebugString(),
562 T*
const constraint_;
563 void (T::*
const method_)(P);
564 const std::string name_;
568template <
class T,
class P>
570 const std::string& name, P param1) {
575template <
class T,
class P,
class Q>
578 CallMethod2(T*
const ct,
void (T::*method)(P, Q),
const std::string& name,
589 (constraint_->*method_)(param1_, param2_);
593 return absl::StrCat(
"CallMethod_", name_,
"(", constraint_->DebugString(),
599 T*
const constraint_;
600 void (T::*
const method_)(P, Q);
601 const std::string name_;
606template <
class T,
class P,
class Q>
608 void (T::*method)(P, Q),
const std::string& name,
609 P param1, Q param2) {
614template <
class T,
class P,
class Q,
class R>
617 CallMethod3(T*
const ct,
void (T::*method)(P, Q, R),
const std::string& name,
618 P param1, Q param2, R param3)
628 void Run(Solver*
const)
override {
629 (constraint_->*method_)(param1_, param2_, param3_);
633 return absl::StrCat(absl::StrCat(
"CallMethod_", name_),
634 absl::StrCat(
"(", constraint_->DebugString()),
641 T*
const constraint_;
642 void (T::*
const method_)(P, Q, R);
643 const std::string name_;
649template <
class T,
class P,
class Q,
class R>
651 void (T::*method)(P, Q, R),
const std::string& name,
652 P param1, Q param2, R param3) {
668 : constraint_(ct), method_(method), name_(name) {}
672 void Run(
Solver*
const)
override { (constraint_->*method_)(); }
679 return "DelayedCallMethod_" + name_ +
"(" + constraint_->DebugString() +
684 T*
const constraint_;
685 void (T::*
const method_)();
686 const std::string name_;
692 const std::string& name) {
697template <
class T,
class P>
702 : constraint_(ct), method_(method), name_(name), param1_(param1) {}
706 void Run(
Solver*
const)
override { (constraint_->*method_)(param1_); }
713 return absl::StrCat(
"DelayedCallMethod_", name_,
"(",
714 constraint_->DebugString(),
", ",
719 T*
const constraint_;
720 void (T::*
const method_)(P);
721 const std::string name_;
725template <
class T,
class P>
727 void (T::*method)(P),
728 const std::string& name, P param1) {
733template <
class T,
class P,
class Q>
737 const std::string& name, P param1, Q param2)
747 (constraint_->*method_)(param1_, param2_);
755 return absl::StrCat(absl::StrCat(
"DelayedCallMethod_", name_),
756 absl::StrCat(
"(", constraint_->DebugString()),
762 T*
const constraint_;
763 void (T::*
const method_)(P, Q);
764 const std::string name_;
769template <
class T,
class P,
class Q>
771 void (T::*method)(P, Q),
772 const std::string& name, P param1,
787 IntVar*
const index, F values,
788 std::function<
bool()> deep_serialize)
792 values_(std::move(values)),
793 deep_serialize_(std::move(deep_serialize)) {}
796 void Post()
override {
798 solver(),
this, &LightIntFunctionElementCt::IndexBound,
"IndexBound");
803 if (index_->Bound()) {
809 return absl::StrFormat(
"LightIntFunctionElementCt(%s, %s)",
810 var_->DebugString(), index_->DebugString());
820 if (deep_serialize_ ==
nullptr || deep_serialize_()) {
828 void IndexBound() { var_->
SetValue(values_(index_->
Min())); }
831 IntVar*
const index_;
833 std::function<bool()> deep_serialize_;
842 IntVar*
const index1, IntVar*
const index2,
843 F values, std::function<
bool()> deep_serialize)
848 values_(
std::move(values)),
849 deep_serialize_(
std::move(deep_serialize)) {}
851 void Post()
override {
853 solver(),
this, &LightIntIntFunctionElementCt::IndexBound,
861 return "LightIntIntFunctionElementCt";
864 void Accept(ModelVisitor*
const visitor)
const override {
873 const int64_t index1_min = index1_->Min();
874 const int64_t index1_max = index1_->Max();
877 if (deep_serialize_ ==
nullptr || deep_serialize_()) {
878 for (
int i = index1_min; i <= index1_max; ++i) {
879 visitor->VisitInt64ToInt64Extension(
880 [
this, i](int64_t j) {
return values_(i, j); }, index2_->Min(),
895 IntVar*
const index1_;
896 IntVar*
const index2_;
898 std::function<bool()> deep_serialize_;
907 IntVar*
const index1, IntVar*
const index2,
908 IntVar*
const index3, F values)
914 values_(
std::move(values)) {}
916 void Post()
override {
918 solver(),
this, &LightIntIntIntFunctionElementCt::IndexBound,
922 index3_->WhenBound(demon);
927 return "LightIntIntFunctionElementCt";
930 void Accept(ModelVisitor*
const visitor)
const override {
951 IntVar*
const index1_;
952 IntVar*
const index2_;
953 IntVar*
const index3_;
980 virtual bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) = 0;
982 virtual void Start(
const Assignment* assignment) = 0;
983 virtual void Reset() {}
988 virtual bool HoldsDelta()
const {
return false; }
996 max_inversible_index_ = candidate_values_.size();
997 candidate_value_to_index_.resize(max_value + 1, -1);
998 committed_value_to_index_.resize(max_value + 1, -1);
1004 DCHECK_LT(index, candidate_values_.size());
1005 return candidate_values_[index];
1008 return committed_values_[index];
1011 return checkpoint_values_[index];
1014 candidate_values_[index] = value;
1015 if (index < max_inversible_index_) {
1016 candidate_value_to_index_[value] = index;
1022 return candidate_is_active_[index];
1026 candidate_is_active_.Set(index);
1028 candidate_is_active_.Clear(index);
1034 for (
const int64_t index : changes_.PositionsSetAtLeastOnce()) {
1035 const int64_t value = candidate_values_[index];
1036 committed_values_[index] = value;
1037 if (index < max_inversible_index_) {
1038 committed_value_to_index_[value] = index;
1040 committed_is_active_.
CopyBucket(candidate_is_active_, index);
1046 void CheckPoint() { checkpoint_values_ = committed_values_; }
1048 void Revert(
bool only_incremental) {
1050 if (only_incremental)
return;
1053 const int64_t committed_value = committed_values_[index];
1054 candidate_values_[index] = committed_value;
1055 if (index < max_inversible_index_) {
1056 candidate_value_to_index_[committed_value] = index;
1058 candidate_is_active_.
CopyBucket(committed_is_active_, index);
1067 return incremental_changes_.PositionsSetAtLeastOnce();
1071 candidate_values_.resize(size);
1072 committed_values_.resize(size);
1073 checkpoint_values_.resize(size);
1074 candidate_is_active_.Resize(size);
1075 committed_is_active_.Resize(size);
1076 changes_.ClearAndResize(size);
1077 incremental_changes_.ClearAndResize(size);
1081 return candidate_value_to_index_[value];
1084 return committed_value_to_index_[value];
1088 void MarkChange(int64_t index) {
1089 incremental_changes_.
Set(index);
1090 changes_.
Set(index);
1093 std::vector<int64_t> candidate_values_;
1094 std::vector<int64_t> committed_values_;
1095 std::vector<int64_t> checkpoint_values_;
1103 int64_t max_inversible_index_ = -1;
1104 std::vector<int64_t> candidate_value_to_index_;
1105 std::vector<int64_t> committed_value_to_index_;
1119 bool keep_inverse_values =
false) {
1121 if (keep_inverse_values) {
1122 int64_t max_value = -1;
1123 for (
const IntVar*
const var : vars) {
1124 max_value = std::max(max_value, var->Max());
1131 bool HoldsDelta()
const override {
return true; }
1134 void Start(
const Assignment* assignment)
override {
1137 const int size =
Size();
1138 CHECK_LE(size, assignment->Size())
1139 <<
"Assignment contains fewer variables than operator";
1141 for (
int i = 0; i < size; ++i) {
1143 if (element->
Var() != vars_[i]) {
1144 CHECK(container.
Contains(vars_[i]))
1145 <<
"Assignment does not contain operator variable " << vars_[i];
1146 element = &(container.
Element(vars_[i]));
1156 int Size()
const {
return vars_.size(); }
1159 int64_t
Value(int64_t index)
const {
1160 DCHECK_LT(index, vars_.size());
1161 return state_.CandidateValue(index);
1164 IntVar*
Var(int64_t index)
const {
return vars_[index]; }
1168 return state_.CheckPointValue(index);
1171 state_.SetCandidateValue(index, value);
1176 void Activate(int64_t index) { state_.SetCandidateActive(index,
true); }
1177 void Deactivate(int64_t index) { state_.SetCandidateActive(index,
false); }
1181 for (
const int64_t index : state_.IncrementalIndicesChanged()) {
1183 const int64_t value =
Value(index);
1191 for (
const int64_t index : state_.CandidateIndicesChanged()) {
1192 const int64_t value =
Value(index);
1193 const bool activated =
Activated(index);
1204 candidate_has_changes_ = change_was_incremental &&
IsIncremental();
1206 if (!candidate_has_changes_) {
1207 for (
const int64_t index : state_.CandidateIndicesChanged()) {
1208 assignment_indices_[index] = -1;
1211 state_.Revert(candidate_has_changes_);
1215 if (!vars.empty()) {
1216 vars_.insert(vars_.end(), vars.begin(), vars.end());
1217 const int64_t size =
Size();
1218 assignment_indices_.resize(size, -1);
1219 state_.Resize(size);
1247 return state_.CandidateInverseValue(index);
1254 std::vector<int>* assignment_indices, int64_t index,
1255 Assignment* assignment)
const {
1257 assignment->MutableIntVarContainer();
1259 if (assignment_indices !=
nullptr) {
1260 if ((*assignment_indices)[index] == -1) {
1261 (*assignment_indices)[index] = container->Size();
1262 element = assignment->FastAdd(var);
1264 element = container->MutableElement((*assignment_indices)[index]);
1267 element = assignment->FastAdd(var);
1278 std::vector<IntVar*> vars_;
1279 mutable std::vector<int> assignment_indices_;
1280 bool candidate_has_changes_ =
false;
1282 LocalSearchOperatorState state_;
1314 explicit BaseLns(
const std::vector<IntVar*>& vars);
1329 std::vector<int> fragment_;
1338 explicit ChangeValue(
const std::vector<IntVar*>& vars);
1340 virtual int64_t
ModifyValue(int64_t index, int64_t value) = 0;
1357 : use_sibling_(use_sibling) {}
1359 template <
class PathOperator>
1363 const int64_t base_node = path_operator.
BaseNode(base_index_reference);
1364 const int alternative_index =
1368 alternative_index >= 0
1369 ? absl::Span<const int64_t>(
1370 path_operator.alternative_sets_[alternative_index])
1371 :
absl::Span<const int64_t>();
1373 bool Next() {
return ++index_ < alternative_set_.size(); }
1375 return (index_ >= alternative_set_.size()) ? -1 : alternative_set_[index_];
1379 const bool use_sibling_;
1381 absl::Span<const int64_t> alternative_set_;
1384class NodeNeighborIterator {
1388 template <
class PathOperator>
1390 using Span = absl::Span<const int>;
1392 const int64_t base_node = path_operator.
BaseNode(base_index_reference);
1393 const int64_t start_node = path_operator.
StartNode(base_index_reference);
1394 const auto& get_incoming_neighbors =
1396 incoming_neighbors_ =
1397 path_operator.
IsPathStart(base_node) || !get_incoming_neighbors
1399 : Span(get_incoming_neighbors(base_node, start_node));
1400 const auto& get_outgoing_neighbors =
1402 outgoing_neighbors_ =
1403 path_operator.
IsPathEnd(base_node) || !get_outgoing_neighbors
1405 : Span(get_outgoing_neighbors(base_node, start_node));
1408 return ++index_ < incoming_neighbors_.size() + outgoing_neighbors_.size();
1411 if (index_ < incoming_neighbors_.size()) {
1412 return incoming_neighbors_[index_];
1414 const int index = index_ - incoming_neighbors_.size();
1415 return (index >= outgoing_neighbors_.size()) ? -1
1416 : outgoing_neighbors_[index];
1419 return index_ < incoming_neighbors_.size();
1422 return index_ >= incoming_neighbors_.size();
1427 absl::Span<const int> incoming_neighbors_;
1428 absl::Span<const int> outgoing_neighbors_;
1431template <
class PathOperator>
1435 : path_operator_(*path_operator),
1436 base_index_reference_(base_index_reference) {}
1438 DCHECK(!alternatives_.empty());
1440 return alternatives_[0].get();
1443 DCHECK(!alternatives_.empty());
1445 return alternatives_[1].get();
1450 return neighbors_.get();
1454 alternatives_.push_back(std::make_unique<AlternativeNodeIterator>(
1456 alternatives_.push_back(std::make_unique<AlternativeNodeIterator>(
1460 neighbors_ = std::make_unique<NodeNeighborIterator>();
1463 void Reset(
bool update_end_nodes =
false) {
1465 for (
auto& alternative_iterator : alternatives_) {
1466 alternative_iterator->Reset(path_operator_, base_index_reference_);
1469 neighbors_->Reset(path_operator_, base_index_reference_);
1470 if (update_end_nodes) neighbor_end_node_ = neighbors_->GetValue();
1475 for (
auto& alternative_iterator : alternatives_) {
1476 if (alternative_iterator->Next())
return true;
1477 alternative_iterator->Reset(path_operator_, base_index_reference_);
1480 if (neighbors_->Next())
return true;
1481 neighbors_->Reset(path_operator_, base_index_reference_);
1488 if (!neighbors_)
return true;
1489 return neighbor_end_node_ == neighbors_->GetValue();
1494 int base_index_reference_ = -1;
1496 std::vector<std::unique_ptr<AlternativeNodeIterator>> alternatives_;
1498 std::unique_ptr<NodeNeighborIterator> neighbors_;
1499 int neighbor_end_node_ = -1;
1500 bool finished_ =
false;
1516template <
bool ignore_path_vars>
1520 struct IterationParameters {
1541 std::function<const std::vector<int>&(
1544 std::function<const std::vector<int>&(
1550 const std::vector<IntVar*>& path_vars,
1562 just_started_(false),
1564 next_base_to_increment_(iteration_parameters.number_of_base_nodes),
1565 iteration_parameters_(
std::move(iteration_parameters)),
1566 optimal_paths_enabled_(false),
1568 alternative_index_(next_vars.size(), -1) {
1569 DCHECK_GT(iteration_parameters_.number_of_base_nodes, 0);
1570 for (
int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
1573 if constexpr (!ignore_path_vars) {
1576 path_basis_.push_back(0);
1577 for (
int i = 1; i < iteration_parameters_.number_of_base_nodes; ++i) {
1580 if ((path_basis_.size() > 2) ||
1581 (!next_vars.empty() && !next_vars.back()
1584 .skip_locally_optimal_paths())) {
1585 iteration_parameters_.skip_locally_optimal_paths =
false;
1589 const std::vector<IntVar*>& next_vars,
1590 const std::vector<IntVar*>& path_vars,
int number_of_base_nodes,
1591 bool skip_locally_optimal_paths,
bool accept_path_end_base,
1592 std::function<
int(int64_t)> start_empty_path_class,
1593 std::function<
const std::vector<int>&(
int,
int)> get_incoming_neighbors,
1594 std::function<
const std::vector<int>&(
int,
int)> get_outgoing_neighbors)
1596 {number_of_base_nodes, skip_locally_optimal_paths,
1597 accept_path_end_base, std::move(start_empty_path_class),
1598 std::move(get_incoming_neighbors),
1599 std::move(get_outgoing_neighbors)}) {}
1603 first_start_ =
true;
1606 void Reset()
override {
1607 active_paths_.Clear();
1613 if constexpr (ignore_path_vars)
return true;
1623 int64_t
Next(int64_t node)
const {
1629 int64_t
Prev(int64_t node)
const {
1638 if constexpr (ignore_path_vars)
return 0LL;
1648 while (IncrementPosition()) {
1670 int64_t
BaseNode(
int i)
const {
return base_nodes_[i]; }
1673 return GetNodeWithDefault(base_node_iterators_[i].GetAlternativeIterator(),
1678 return GetNodeWithDefault(
1679 base_node_iterators_[i].GetSiblingAlternativeIterator(),
BaseNode(i));
1682 int64_t
StartNode(
int i)
const {
return path_starts_[base_paths_[i]]; }
1684 int64_t
EndNode(
int i)
const {
return path_ends_[base_paths_[i]]; }
1686 const std::vector<int64_t>&
path_starts()
const {
return path_starts_; }
1691 ? iteration_parameters_.start_empty_path_class(start_node)
1721 next_base_to_increment_ = base_index;
1727 int64_t
OldNext(int64_t node)
const {
1732 int64_t
PrevNext(int64_t node)
const {
1737 int64_t
OldPrev(int64_t node)
const {
1742 int64_t
OldPath(int64_t node)
const {
1743 if constexpr (ignore_path_vars)
return 0LL;
1748 return node_path_starts_[node];
1755 bool MoveChain(int64_t before_chain, int64_t chain_end, int64_t destination) {
1756 if (destination == before_chain || destination == chain_end)
return false;
1759 const int64_t destination_path =
Path(destination);
1760 const int64_t after_chain =
Next(chain_end);
1762 if constexpr (!ignore_path_vars) {
1763 int current = destination;
1764 int next =
Next(before_chain);
1765 while (current != chain_end) {
1766 SetNext(current, next, destination_path);
1771 SetNext(destination,
Next(before_chain), destination_path);
1773 SetNext(before_chain, after_chain,
Path(before_chain));
1779 bool ReverseChain(int64_t before_chain, int64_t after_chain,
1780 int64_t* chain_last) {
1782 int64_t path =
Path(before_chain);
1783 int64_t current =
Next(before_chain);
1784 if (current == after_chain) {
1787 int64_t current_next =
Next(current);
1788 SetNext(current, after_chain, path);
1789 while (current_next != after_chain) {
1790 const int64_t next =
Next(current_next);
1791 SetNext(current_next, current, path);
1792 current = current_next;
1793 current_next = next;
1795 SetNext(before_chain, current, path);
1796 *chain_last = current;
1803 bool SwapNodes(int64_t node1, int64_t node2) {
1808 if (node1 == node2)
return false;
1809 const int64_t prev_node1 =
Prev(node1);
1815 bool MakeActive(int64_t node, int64_t destination) {
1816 if (
IsPathEnd(destination))
return false;
1817 const int64_t destination_path =
Path(destination);
1818 SetNext(node,
Next(destination), destination_path);
1819 SetNext(destination, node, destination_path);
1825 const int64_t kNoPath = -1;
1828 const int64_t after_chain =
Next(chain_end);
1829 int64_t current =
Next(before_chain);
1830 while (current != after_chain) {
1831 const int64_t next =
Next(current);
1832 SetNext(current, current, kNoPath);
1835 SetNext(before_chain, after_chain,
Path(before_chain));
1843 if (active == inactive)
return false;
1844 const int64_t prev =
Prev(active);
1850 absl::Span<const int64_t> inactive_chain) {
1851 if (active_chain.empty())
return false;
1852 if (active_chain == inactive_chain)
return false;
1853 const int before_active_chain =
Prev(active_chain.front());
1857 for (
auto it = inactive_chain.crbegin(); it != inactive_chain.crend();
1859 if (!
MakeActive(*it, before_active_chain))
return false;
1865 void SetNext(int64_t from, int64_t
to, int64_t path) {
1868 if constexpr (!ignore_path_vars) {
1883 return !
IsPathEnd(node) && inactives_[node];
1898 const int alternative = alternative_sets_.size();
1899 for (int64_t node : alternative_set) {
1900 DCHECK_EQ(-1, alternative_index_[node]);
1901 alternative_index_[node] = alternative;
1903 alternative_sets_.push_back(alternative_set);
1904 sibling_alternative_.push_back(-1);
1910 template <
typename PairType>
1912 const std::vector<PairType>& pair_alternative_sets) {
1913 for (
const auto& [alternative_set, sibling_alternative_set] :
1914 pair_alternative_sets) {
1921 int64_t GetActiveInAlternativeSet(int alternative_index) const {
1922 return alternative_index >= 0
1923 ? active_in_alternative_set_[alternative_index]
1927 int64_t GetActiveAlternativeNode(
int node)
const {
1928 return GetActiveInAlternativeSet(alternative_index_[node]);
1931 int GetSiblingAlternativeIndex(
int node)
const {
1932 const int alternative = GetAlternativeIndex(node);
1933 return alternative >= 0 ? sibling_alternative_[alternative] : -1;
1937 return (node >= alternative_index_.size()) ? -1 : alternative_index_[node];
1950 int64_t exclude)
const {
1951 if (before_chain == chain_end || before_chain == exclude)
return false;
1952 int64_t current = before_chain;
1954 while (current != chain_end) {
1957 current =
Next(current);
1959 if (current == exclude)
return false;
1965 return iteration_parameters_.get_incoming_neighbors !=
nullptr ||
1966 iteration_parameters_.get_outgoing_neighbors !=
nullptr;
1976 Neighbor GetNeighborForBaseNode(int64_t base_index)
const {
1977 auto* iterator = base_node_iterators_[base_index].GetNeighborIterator();
1978 return {.neighbor = iterator->GetValue(),
1979 .outgoing = iterator->IsOutgoingNeighbor()};
1982 const int number_of_nexts_;
1985 template <
class NodeIterator>
1986 static int GetNodeWithDefault(
const NodeIterator* node_iterator,
1987 int default_value) {
1988 const int node = node_iterator->GetValue();
1989 return node >= 0 ? node : default_value;
1992 void OnStart()
override {
1993 optimal_paths_enabled_ =
false;
1994 if (!iterators_initialized_) {
1995 iterators_initialized_ =
true;
1996 for (
int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {
1997 base_node_iterators_[i].Initialize();
2000 InitializeBaseNodes();
2001 InitializeAlternatives();
2002 OnNodeInitialization();
2006 bool OnSamePath(int64_t node1, int64_t node2)
const {
2007 if (IsInactive(node1) != IsInactive(node2)) {
2010 for (
int node = node1; !IsPathEnd(node); node = OldNext(node)) {
2011 if (node == node2) {
2015 for (
int node = node2; !IsPathEnd(node); node = OldNext(node)) {
2016 if (node == node1) {
2023 bool CheckEnds()
const {
2024 for (
int i = iteration_parameters_.number_of_base_nodes - 1; i >= 0; --i) {
2025 if (base_nodes_[i] != end_nodes_[i] ||
2026 !base_node_iterators_[i].HasReachedEnd()) {
2032 bool IncrementPosition() {
2033 const int base_node_size = iteration_parameters_.number_of_base_nodes;
2035 if (just_started_) {
2036 just_started_ =
false;
2039 const int number_of_paths = path_starts_.size();
2045 int last_restarted = base_node_size;
2046 for (
int i = base_node_size - 1;
i >= 0; --
i) {
2047 if (base_nodes_[i] < number_of_nexts_ && i <= next_base_to_increment_) {
2048 if (base_node_iterators_[i].Increment())
break;
2049 base_nodes_[
i] = OldNext(base_nodes_[i]);
2050 base_node_iterators_[
i].Reset();
2051 if (iteration_parameters_.accept_path_end_base ||
2052 !IsPathEnd(base_nodes_[i])) {
2056 base_nodes_[
i] = StartNode(i);
2057 base_node_iterators_[
i].Reset();
2060 next_base_to_increment_ = base_node_size;
2070 for (
int i = last_restarted;
i < base_node_size; ++
i) {
2071 base_nodes_[
i] = GetBaseNodeRestartPosition(i);
2072 base_node_iterators_[
i].Reset();
2074 if (last_restarted > 0) {
2080 if (optimal_paths_enabled_ &&
2081 iteration_parameters_.skip_locally_optimal_paths) {
2082 if (path_basis_.size() > 1) {
2083 for (
int i = 1;
i < path_basis_.size(); ++
i) {
2084 active_paths_.DeactivatePathPair(StartNode(path_basis_[i - 1]),
2085 StartNode(path_basis_[i]));
2088 active_paths_.DeactivatePathPair(StartNode(path_basis_[0]),
2089 StartNode(path_basis_[0]));
2092 std::vector<int> current_starts(base_node_size);
2093 for (
int i = 0;
i < base_node_size; ++
i) {
2094 current_starts[
i] = StartNode(i);
2098 optimal_paths_enabled_ =
true;
2100 for (
int i = base_node_size - 1;
i >= 0; --
i) {
2101 const int next_path_index = base_paths_[
i] + 1;
2102 if (next_path_index < number_of_paths) {
2103 base_paths_[
i] = next_path_index;
2104 base_nodes_[
i] = path_starts_[next_path_index];
2105 base_node_iterators_[
i].Reset();
2106 if (i == 0 || !OnSamePathAsPreviousBase(i)) {
2111 base_nodes_[
i] = path_starts_[0];
2112 base_node_iterators_[
i].Reset();
2115 if (!iteration_parameters_.skip_locally_optimal_paths)
return CheckEnds();
2118 if (path_basis_.size() > 1) {
2119 for (
int j = 1; j < path_basis_.size(); ++j) {
2120 if (active_paths_.IsPathPairActive(StartNode(path_basis_[j - 1]),
2121 StartNode(path_basis_[j]))) {
2126 if (active_paths_.IsPathPairActive(StartNode(path_basis_[0]),
2127 StartNode(path_basis_[0]))) {
2133 if (!CheckEnds())
return false;
2135 for (
int i = 0;
i < base_node_size; ++
i) {
2136 if (StartNode(i) != current_starts[i]) {
2141 if (stop)
return false;
2146 void InitializePathStarts() {
2150 std::vector<bool> has_prevs(number_of_nexts_,
false);
2151 for (
int i = 0;
i < number_of_nexts_; ++
i) {
2152 const int next = OldNext(i);
2153 if (next < number_of_nexts_) {
2154 has_prevs[next] =
true;
2156 max_next = std::max(max_next, next);
2159 if (iteration_parameters_.skip_locally_optimal_paths) {
2160 active_paths_.Initialize(
2161 [&has_prevs](
int node) {
return !has_prevs[node]; });
2162 for (
int i = 0;
i < number_of_nexts_; ++
i) {
2163 if (!has_prevs[i]) {
2165 while (!IsPathEnd(current)) {
2166 if ((OldNext(current) != PrevNext(current))) {
2167 active_paths_.ActivatePath(i);
2170 current = OldNext(current);
2177 std::vector<bool> empty_found(number_of_nexts_,
false);
2178 std::vector<int64_t> new_path_starts;
2179 for (
int i = 0;
i < number_of_nexts_; ++
i) {
2180 if (!has_prevs[i]) {
2181 if (IsPathEnd(OldNext(i))) {
2182 if (iteration_parameters_.start_empty_path_class !=
nullptr) {
2183 if (empty_found[iteration_parameters_.start_empty_path_class(i)])
2185 empty_found[iteration_parameters_.start_empty_path_class(i)] =
true;
2188 new_path_starts.push_back(i);
2191 if (!first_start_) {
2196 std::vector<int> node_paths(max_next + 1, -1);
2197 for (
int i = 0;
i < path_starts_.size(); ++
i) {
2198 int node = path_starts_[
i];
2199 while (!IsPathEnd(node)) {
2200 node_paths[node] =
i;
2201 node = OldNext(node);
2203 node_paths[node] =
i;
2205 for (
int j = 0; j < iteration_parameters_.number_of_base_nodes; ++j) {
2206 if (IsInactive(base_nodes_[j]) || node_paths[base_nodes_[j]] == -1) {
2209 base_nodes_[j] = GetBaseNodeRestartPosition(j);
2210 base_paths_[j] = node_paths[base_nodes_[j]];
2212 base_paths_[j] = node_paths[base_nodes_[j]];
2215 base_node_iterators_[j].Reset();
2221 absl::flat_hash_set<int> found_bases;
2222 for (
int i = 0;
i < path_starts_.size(); ++
i) {
2223 int index = new_index;
2225 while (index < new_path_starts.size() &&
2226 new_path_starts[index] < path_starts_[i]) {
2229 const bool found = (index < new_path_starts.size() &&
2230 new_path_starts[index] == path_starts_[i]);
2234 for (
int j = 0; j < iteration_parameters_.number_of_base_nodes; ++j) {
2235 if (base_paths_[j] == i && !found_bases.contains(j)) {
2236 found_bases.insert(j);
2237 base_paths_[j] = new_index;
2241 base_nodes_[j] = new_path_starts[new_index];
2247 path_starts_.swap(new_path_starts);
2251 path_ends_.reserve(path_starts_.size());
2252 int64_t max_node_index = number_of_nexts_ - 1;
2253 for (
const int start_node : path_starts_) {
2254 int64_t node = start_node;
2255 while (!IsPathEnd(node)) node = OldNext(node);
2256 path_ends_.push_back(node);
2257 max_node_index = std::max(max_node_index, node);
2259 node_path_starts_.assign(max_node_index + 1, -1);
2260 node_path_ends_.assign(max_node_index + 1, -1);
2261 for (
int i = 0;
i < path_starts_.size(); ++
i) {
2262 const int64_t start_node = path_starts_[
i];
2263 const int64_t end_node = path_ends_[
i];
2264 int64_t node = start_node;
2265 while (!IsPathEnd(node)) {
2266 node_path_starts_[node] = start_node;
2267 node_path_ends_[node] = end_node;
2268 node = OldNext(node);
2270 node_path_starts_[node] = start_node;
2271 node_path_ends_[node] = end_node;
2274 void InitializeInactives() {
2276 for (
int i = 0;
i < number_of_nexts_; ++
i) {
2277 inactives_.push_back(OldNext(i) == i);
2280 void InitializeBaseNodes() {
2282 InitializeInactives();
2283 InitializePathStarts();
2284 if (first_start_ || InitPosition()) {
2287 for (
int i = 0;
i < iteration_parameters_.number_of_base_nodes; ++
i) {
2289 base_nodes_[
i] = path_starts_[0];
2291 first_start_ =
false;
2293 for (
int i = 0;
i < iteration_parameters_.number_of_base_nodes; ++
i) {
2295 int64_t base_node = base_nodes_[
i];
2296 if (RestartAtPathStartOnSynchronize() || IsInactive(base_node)) {
2297 base_node = path_starts_[base_paths_[
i]];
2298 base_nodes_[
i] = base_node;
2300 end_nodes_[
i] = base_node;
2304 for (
int i = 1;
i < iteration_parameters_.number_of_base_nodes; ++
i) {
2305 if (OnSamePathAsPreviousBase(i) &&
2306 !OnSamePath(base_nodes_[i - 1], base_nodes_[i])) {
2307 const int64_t base_node = base_nodes_[
i - 1];
2308 base_nodes_[
i] = base_node;
2309 end_nodes_[
i] = base_node;
2310 base_paths_[
i] = base_paths_[
i - 1];
2313 for (
int i = 0;
i < iteration_parameters_.number_of_base_nodes; ++
i) {
2314 base_node_iterators_[
i].Reset(
true);
2316 just_started_ =
true;
2318 void InitializeAlternatives() {
2319 active_in_alternative_set_.resize(alternative_sets_.size(), -1);
2320 for (
int i = 0;
i < alternative_sets_.size(); ++
i) {
2321 const int64_t current_active = active_in_alternative_set_[
i];
2322 if (current_active >= 0 && !IsInactive(current_active))
continue;
2323 for (int64_t index : alternative_sets_[i]) {
2324 if (!IsInactive(index)) {
2325 active_in_alternative_set_[
i] = index;
2334 explicit ActivePaths(
int num_nodes) : start_to_path_(num_nodes, -1) {}
2335 void Clear() { to_reset_ =
true; }
2336 template <
typename T>
2337 void Initialize(T is_start) {
2338 if (is_path_pair_active_.empty()) {
2340 absl::c_fill(start_to_path_, -1);
2341 for (
int i = 0;
i < start_to_path_.size(); ++
i) {
2343 start_to_path_[
i] = num_paths_;
2349 void DeactivatePathPair(
int start1,
int start2) {
2350 if (to_reset_) Reset();
2351 is_path_pair_active_[start_to_path_[start1] * num_paths_ +
2352 start_to_path_[start2]] =
false;
2354 void ActivatePath(
int start) {
2355 if (to_reset_) Reset();
2356 const int p1 = start_to_path_[start];
2357 const int p1_block = num_paths_ * p1;
2358 for (
int p2 = 0; p2 < num_paths_; ++p2) {
2359 is_path_pair_active_[p1_block + p2] =
true;
2361 for (
int p2_block = 0; p2_block < is_path_pair_active_.size();
2362 p2_block += num_paths_) {
2363 is_path_pair_active_[p2_block + p1] =
true;
2366 bool IsPathPairActive(
int start1,
int start2)
const {
2367 if (to_reset_)
return true;
2368 return is_path_pair_active_[start_to_path_[start1] * num_paths_ +
2369 start_to_path_[start2]];
2374 if (!to_reset_)
return;
2375 is_path_pair_active_.assign(num_paths_ * num_paths_,
true);
2379 bool to_reset_ =
true;
2381 std::vector<int64_t> start_to_path_;
2382 std::vector<bool> is_path_pair_active_;
2385 std::unique_ptr<int[]> base_nodes_;
2386 std::unique_ptr<int[]> end_nodes_;
2387 std::unique_ptr<int[]> base_paths_;
2388 std::vector<int> node_path_starts_;
2389 std::vector<int> node_path_ends_;
2390 bool iterators_initialized_ =
false;
2392 std::vector<BaseNodeIterators<PathOperator>> base_node_iterators_;
2394 std::vector<int64_t> path_starts_;
2395 std::vector<int64_t> path_ends_;
2396 std::vector<bool> inactives_;
2399 int next_base_to_increment_;
2400 IterationParameters iteration_parameters_;
2401 bool optimal_paths_enabled_;
2402 std::vector<int> path_basis_;
2403 ActivePaths active_paths_;
2406 std::vector<std::vector<int64_t>> alternative_sets_;
2408 std::vector<int> alternative_index_;
2409 std::vector<int64_t> active_in_alternative_set_;
2410 std::vector<int> sibling_alternative_;
2430 Solver* solver,
const std::vector<IntVar*>& vars,
2431 const std::vector<IntVar*>& secondary_vars,
2432 std::function<
int(int64_t)> start_empty_path_class,
2433 std::function<
const std::vector<int>&(
int,
int)> get_incoming_neighbors =
2435 std::function<
const std::vector<int>&(
int,
int)> get_outgoing_neighbors =
2454 Solver* solver,
const std::vector<IntVar*>& vars,
2455 const std::vector<IntVar*>& secondary_vars,
2456 std::function<
int(int64_t)> start_empty_path_class,
2457 std::function<
const std::vector<int>&(
int,
int)> get_incoming_neighbors =
2459 std::function<
const std::vector<int>&(
int,
int)> get_outgoing_neighbors =
2461 int64_t chain_length = 1LL,
bool single_path =
false,
2462 const std::string& name =
"Relocate");
2475 Solver* solver,
const std::vector<IntVar*>& vars,
2476 const std::vector<IntVar*>& secondary_vars,
2477 std::function<
int(int64_t)> start_empty_path_class,
2478 std::function<
const std::vector<int>&(
int,
int)> get_incoming_neighbors =
2480 std::function<
const std::vector<int>&(
int,
int)> get_outgoing_neighbors =
2496 Solver* solver,
const std::vector<IntVar*>& vars,
2497 const std::vector<IntVar*>& secondary_vars,
2498 std::function<
int(int64_t)> start_empty_path_class,
2499 std::function<
const std::vector<int>&(
int,
int)> get_incoming_neighbors =
2501 std::function<
const std::vector<int>&(
int,
int)> get_outgoing_neighbors =
2514 Solver* solver,
const std::vector<IntVar*>& vars,
2515 const std::vector<IntVar*>& secondary_vars,
2516 std::function<
int(int64_t)> start_empty_path_class,
2517 std::function<
const std::vector<int>&(
int,
int)> get_incoming_neighbors =
2519 std::function<
const std::vector<int>&(
int,
int)> get_outgoing_neighbors =
2532 Solver* solver,
const std::vector<IntVar*>& vars,
2533 const std::vector<IntVar*>& secondary_vars,
2534 std::function<
int(int64_t)> start_empty_path_class);
2552 Solver* solver,
const std::vector<IntVar*>& vars,
2553 const std::vector<IntVar*>& secondary_vars,
2554 std::function<
int(int64_t)> start_empty_path_class);
2573 Solver* solver,
const std::vector<IntVar*>& vars,
2574 const std::vector<IntVar*>& secondary_vars,
2575 std::function<
int(int64_t)> start_empty_path_class);
2584 Solver* solver,
const std::vector<IntVar*>& vars,
2585 const std::vector<IntVar*>& secondary_vars,
2586 std::function<
int(int64_t)> start_empty_path_class);
2597 Solver* solver,
const std::vector<IntVar*>& vars,
2598 const std::vector<IntVar*>& secondary_vars,
2599 std::function<
int(int64_t)> start_empty_path_class);
2610 Solver* solver,
const std::vector<IntVar*>& vars,
2611 const std::vector<IntVar*>& secondary_vars,
2612 std::function<
int(int64_t)> start_empty_path_class);
2624 Solver* solver,
const std::vector<IntVar*>& vars,
2625 const std::vector<IntVar*>& secondary_vars,
2626 std::function<
int(int64_t)> start_empty_path_class);
2637 Solver* solver,
const std::vector<IntVar*>& vars,
2638 const std::vector<IntVar*>& secondary_vars,
2639 std::function<
int(int64_t)> start_empty_path_class);
2644 Solver* solver,
const std::vector<IntVar*>& vars,
2645 const std::vector<IntVar*>& secondary_vars,
2646 std::function<
int(int64_t)> start_empty_path_class,
int max_chain_size);
2662 Solver* solver,
const std::vector<IntVar*>& vars,
2663 const std::vector<IntVar*>& secondary_vars,
2664 std::function<
int(int64_t)> start_empty_path_class);
2676 const std::vector<IntVar*>& vars,
2677 const std::vector<IntVar*>& secondary_vars,
2690 const std::vector<IntVar*>& vars,
2691 const std::vector<IntVar*>& secondary_vars,
2698 Solver* solver,
const std::vector<IntVar*>& vars,
2699 const std::vector<IntVar*>& secondary_vars,
2709 const std::vector<IntVar*>& vars,
2710 const std::vector<IntVar*>& secondary_vars,
2711 int number_of_chunks,
int chunk_size,
2712 bool unactive_fragments);
2741 DCHECK(!graph_was_built_);
2742 num_nodes_ = std::max(num_nodes_, std::max(tail.value(), head.value()) + 1);
2743 const ArcId arc_id(arcs_.size());
2744 arcs_.push_back({.tail = tail, .head = head, .arc_id = arc_id});
2757 bool HasDirectedCycle()
const;
2763 bool operator<(
const Arc& other)
const {
2764 return std::tie(tail, arc_id) < std::tie(other.tail, other.arc_id);
2768 std::vector<Arc> arcs_;
2774 bool graph_was_built_ =
false;
2778 std::vector<NodeId> nodes_to_visit_;
2780 std::vector<ArcId> sorted_arcs_;
2794class LocalSearchState {
2800 VariableDomainId AddVariableDomain(int64_t relaxed_min, int64_t relaxed_max);
2802 bool RelaxVariableDomain(VariableDomainId domain_id);
2803 bool TightenVariableDomainMin(VariableDomainId domain_id, int64_t value);
2804 bool TightenVariableDomainMax(VariableDomainId domain_id, int64_t value);
2805 int64_t VariableDomainMin(VariableDomainId domain_id)
const;
2806 int64_t VariableDomainMax(VariableDomainId domain_id)
const;
2807 void ChangeRelaxedVariableDomain(VariableDomainId domain_id, int64_t min,
2825 return state_domains_are_all_nonempty_ && num_committed_empty_domains_ == 0;
2828 void AddWeightedSumConstraint(
2829 const std::vector<VariableDomainId>& input_domain_ids,
2830 const std::vector<int64_t>& input_weights, int64_t input_offset,
2834 void CompileConstraints();
2840 struct VariableDomain {
2844 bool IntersectionIsEmpty(
const VariableDomain& d1,
2845 const VariableDomain& d2)
const {
2846 return d1.max < d2.min || d2.max < d1.min;
2850 struct TrailedVariableDomain {
2851 VariableDomain committed_domain;
2852 VariableDomainId domain_id;
2854 std::vector<TrailedVariableDomain> trailed_domains_;
2855 util_intops::StrongVector<VariableDomainId, bool> domain_is_trailed_;
2857 bool state_domains_are_all_nonempty_ =
true;
2858 bool state_has_relaxed_domains_ =
false;
2861 int num_committed_empty_domains_ = 0;
2862 int trailed_num_committed_empty_domains_ = 0;
2867 void TrailConstraint(Constraint* constraint) {
2868 trailed_constraints_.push_back(constraint);
2870 std::vector<Constraint*> trailed_constraints_;
2874 class DependencyGraph {
2876 DependencyGraph() {}
2885 ConstraintId constraint_id;
2888 void AddDomainsConstraintDependencies(
2889 const std::vector<VariableDomainId>& domain_ids,
2890 ConstraintId constraint_id);
2892 void AddConstraintDomainDependency(ConstraintId constraint_id,
2893 VariableDomainId domain_id);
2896 void BuildDependencyDAG(
int num_domains);
2900 const std::vector<Dependency>& ComputeSortedDependencies(
2904 using ArcId = SubDagComputer::ArcId;
2905 using NodeId = SubDagComputer::NodeId;
2912 NodeId GetOrCreateNodeOfConstraintId(ConstraintId
constraint_id);
2923 int num_dag_nodes_ = 1;
2925 std::vector<Dependency> sorted_dependencies_;
2927 DependencyGraph dependency_graph_;
2933 Constraint* constraint;
2939 std::vector<Trigger> triggers_;
2947 virtual ~Constraint() =
default;
2948 virtual LocalSearchState::VariableDomain Propagate(
int input_index) = 0;
2950 virtual void Commit() = 0;
2951 virtual void Revert() = 0;
2955 class WeightedSum final :
public Constraint {
2958 const std::vector<VariableDomainId>& input_domain_ids,
2959 const std::vector<int64_t>& input_weights, int64_t input_offset,
2961 ~WeightedSum()
override =
default;
2962 LocalSearchState::VariableDomain Propagate(
int input_index)
override;
2963 void Commit()
override;
2964 void Revert()
override;
2970 struct WeightedVariable {
2973 int64_t committed_min;
2974 int64_t committed_max;
2976 VariableDomainId domain;
2979 committed_min = min;
2980 committed_max = max;
2984 min = committed_min;
2985 max = committed_max;
2989 std::vector<WeightedVariable> inputs_;
2990 std::vector<WeightedVariable*> trailed_inputs_;
2994 int64_t num_neg_inf;
2998 int64_t num_pos_inf;
3002 Invariants invariants_;
3003 Invariants committed_invariants_;
3006 LocalSearchState*
const state_;
3007 bool constraint_is_trailed_ =
false;
3010 util_intops::StrongVector<ConstraintId, std::unique_ptr<Constraint>>
3019class LocalSearchState::Variable {
3022 int64_t Min()
const {
3024 return state_->VariableDomainMin(domain_id_);
3026 int64_t Max()
const {
3028 return state_->VariableDomainMax(domain_id_);
3032 bool SetMin(int64_t new_min)
const {
3033 if (!
Exists())
return true;
3034 return state_->TightenVariableDomainMin(domain_id_, new_min) &&
3035 state_->PropagateTighten(domain_id_);
3039 bool SetMax(int64_t new_max)
const {
3040 if (!
Exists())
return true;
3041 return state_->TightenVariableDomainMax(domain_id_, new_max) &&
3042 state_->PropagateTighten(domain_id_);
3044 void Relax()
const {
3045 if (state_ ==
nullptr)
return;
3046 if (state_->RelaxVariableDomain(domain_id_)) {
3047 state_->PropagateRelax(domain_id_);
3050 bool Exists()
const {
return state_ !=
nullptr; }
3057 : state_(state), domain_id_(domain_id) {}
3098 int64_t objective_min, int64_t objective_max) = 0;
3118 virtual int64_t GetAcceptedObjectiveValue()
const {
return 0LL; }
3128 enum FilterEventType { kAccept, kRelax };
3129 struct FilterEvent {
3131 FilterEventType event_type;
3135 std::string DebugString()
const override {
3136 return "LocalSearchFilterManager";
3152 const Assignment* deltadelta, int64_t objective_min,
3153 int64_t objective_max);
3157 int64_t GetAcceptedObjectiveValue()
const {
return accepted_value_; }
3162 void FindIncrementalEventEnd();
3164 std::vector<FilterEvent> events_;
3165 int last_event_called_ = -1;
3170 int incremental_events_end_ = 0;
3171 int64_t synchronized_value_;
3172 int64_t accepted_value_;
3184 bool FindIndex(
IntVar*
const var, int64_t* index)
const {
3185 DCHECK(index !=
nullptr);
3186 const int var_index = var->
index();
3187 *index = (var_index < var_index_to_index_.size())
3188 ? var_index_to_index_[var_index]
3190 return *index != kUnassigned;
3194 void AddVars(
const std::vector<IntVar*>& vars);
3195 int Size()
const {
return vars_.size(); }
3196 IntVar* Var(
int index)
const {
return vars_[index]; }
3197 int64_t
Value(
int index)
const {
3198 DCHECK(IsVarSynced(index));
3199 return values_[index];
3201 bool IsVarSynced(
int index)
const {
return var_synced_[index]; }
3204 virtual void OnSynchronize(
const Assignment*) {}
3205 void SynchronizeOnAssignment(
const Assignment* assignment);
3208 std::vector<IntVar*> vars_;
3209 std::vector<int64_t> values_;
3210 std::vector<bool> var_synced_;
3211 std::vector<int> var_index_to_index_;
3212 static const int kUnassigned;
3219 std::string
DebugString()
const override {
return "PropagationMonitor"; }
3222 virtual void BeginConstraintInitialPropagation(
Constraint* constraint) = 0;
3223 virtual void EndConstraintInitialPropagation(
Constraint* constraint) = 0;
3224 virtual void BeginNestedConstraintInitialPropagation(
Constraint* parent,
3226 virtual void EndNestedConstraintInitialPropagation(
Constraint* parent,
3229 virtual void BeginDemonRun(
Demon* demon) = 0;
3233 virtual void PushContext(
const std::string& context) = 0;
3242 virtual void SetRange(
IntVar* var, int64_t new_min, int64_t new_max) = 0;
3248 const std::vector<int64_t>& values) = 0;
3253 int64_t new_max) = 0;
3257 int64_t new_max) = 0;
3261 int64_t new_max) = 0;
3269 const std::vector<int>& rank_first,
3270 const std::vector<int>& rank_last,
3271 const std::vector<int>& unperformed) = 0;
3281 std::string
DebugString()
const override {
return "LocalSearchMonitor"; }
3284 virtual void BeginOperatorStart() = 0;
3285 virtual void EndOperatorStart() = 0;
3288 bool neighbor_found,
const Assignment* delta,
3292 bool neighbor_found) = 0;
3295 bool neighbor_found) = 0;
3307 static const int kUnboundBooleanVarValue;
3310 :
IntVar(s, name), value_(kUnboundBooleanVarValue) {}
3314 int64_t Min()
const override {
return (value_ == 1); }
3315 void SetMin(int64_t m)
override;
3316 int64_t Max()
const override {
return (value_ != 0); }
3317 void SetMax(int64_t m)
override;
3318 void SetRange(int64_t mi, int64_t ma)
override;
3319 bool Bound()
const override {
return (value_ != kUnboundBooleanVarValue); }
3328 void WhenDomain(
Demon* d)
override { WhenBound(d); }
3330 bool Contains(int64_t v)
const override;
3342 std::string
BaseName()
const override {
return "BooleanVar"; }
3360 : symmetry_manager_(nullptr), index_in_symmetry_manager_(-1) {}
3363 void AddIntegerVariableEqualValueClause(
IntVar* var, int64_t value);
3364 void AddIntegerVariableGreaterOrEqualValueClause(
IntVar* var, int64_t value);
3365 void AddIntegerVariableLessOrEqualValueClause(
IntVar* var, int64_t value);
3370 CHECK(symmetry_manager_ ==
nullptr);
3371 CHECK_EQ(-1, index_in_symmetry_manager_);
3372 symmetry_manager_ = manager;
3373 index_in_symmetry_manager_ = index;
3375 SymmetryManager* symmetry_manager()
const {
return symmetry_manager_; }
3376 int index_in_symmetry_manager()
const {
return index_in_symmetry_manager_; }
3380 int index_in_symmetry_manager_;
3387 SearchLog(
Solver* solver, std::vector<IntVar*> vars, std::string vars_name,
3388 std::vector<double> scaling_factors, std::vector<double> offsets,
3389 std::function<std::string()> display_callback,
3390 bool display_on_new_solutions_only,
int period);
3392 void EnterSearch()
override;
3393 void ExitSearch()
override;
3394 bool AtSolution()
override;
3395 void BeginFail()
override;
3396 void NoMoreSolutions()
override;
3398 void ApplyDecision(
Decision* decision)
override;
3399 void RefuteDecision(
Decision* decision)
override;
3408 virtual void OutputLine(
const std::string& line);
3414 std::unique_ptr<WallTimer> timer_;
3415 const std::vector<IntVar*> vars_;
3416 const std::string vars_name_;
3417 const std::vector<double> scaling_factors_;
3418 const std::vector<double> offsets_;
3419 std::function<std::string()> display_callback_;
3420 const bool display_on_new_solutions_only_;
3422 absl::Duration tick_;
3423 std::vector<int64_t> objective_min_;
3424 std::vector<int64_t> objective_max_;
3425 std::vector<int64_t> last_objective_value_;
3426 absl::Duration last_objective_timestamp_;
3427 int min_right_depth_;
3429 int sliding_min_depth_;
3430 int sliding_max_depth_;
3431 int neighbors_offset_ = 0;
3440 enum VoidConstraintType {
3441 VOID_FALSE_CONSTRAINT = 0,
3442 VOID_TRUE_CONSTRAINT,
3443 VOID_CONSTRAINT_MAX,
3446 enum VarConstantConstraintType {
3447 VAR_CONSTANT_EQUALITY = 0,
3448 VAR_CONSTANT_GREATER_OR_EQUAL,
3449 VAR_CONSTANT_LESS_OR_EQUAL,
3450 VAR_CONSTANT_NON_EQUALITY,
3451 VAR_CONSTANT_CONSTRAINT_MAX,
3490 enum ExprExprConstantExpressionType {
3508 enum VarConstantConstantExpressionType {
3509 VAR_CONSTANT_CONSTANT_SEMI_CONTINUOUS = 0,
3558 IntVar* var, int64_t value1, int64_t value2,
3613 IntVar* var, int64_t value1, int64_t value2,
3623 IntVar* var,
const std::vector<int64_t>& values,
3636 const std::vector<IntVar*>& vars,
3642 const std::vector<IntVar*>& vars,
const std::vector<int64_t>& values,
3646 IntExpr* expression,
const std::vector<IntVar*>& var,
3647 const std::vector<int64_t>& values,
3653 const std::vector<IntVar*>& vars, int64_t value,
3657 IntExpr* expression,
const std::vector<IntVar*>& var, int64_t value,
3671 const std::string& TypeName()
const;
3672 void SetTypeName(
const std::string& type_name);
3675 void SetIntegerArgument(
const std::string& arg_name, int64_t value);
3676 void SetIntegerArrayArgument(
const std::string& arg_name,
3677 const std::vector<int64_t>& values);
3678 void SetIntegerMatrixArgument(
const std::string& arg_name,
3680 void SetIntegerExpressionArgument(
const std::string& arg_name,
IntExpr* expr);
3681 void SetIntegerVariableArrayArgument(
const std::string& arg_name,
3682 const std::vector<IntVar*>& vars);
3685 const std::vector<IntervalVar*>& vars);
3688 const std::vector<SequenceVar*>& vars);
3699 const std::string& arg_name)
const;
3701 const std::string& arg_name)
const;
3704 const std::string& arg_name)
const;
3706 const std::string& arg_name)
const;
3709 std::string type_name_;
3710 absl::flat_hash_map<std::string, int64_t> integer_argument_;
3711 absl::flat_hash_map<std::string, std::vector<int64_t>>
3712 integer_array_argument_;
3713 absl::flat_hash_map<std::string, IntTupleSet> matrix_argument_;
3714 absl::flat_hash_map<std::string, IntExpr*> integer_expression_argument_;
3715 absl::flat_hash_map<std::string, IntervalVar*> interval_argument_;
3716 absl::flat_hash_map<std::string, SequenceVar*> sequence_argument_;
3717 absl::flat_hash_map<std::string, std::vector<IntVar*>>
3718 integer_variable_array_argument_;
3719 absl::flat_hash_map<std::string, std::vector<IntervalVar*>>
3720 interval_array_argument_;
3721 absl::flat_hash_map<std::string, std::vector<SequenceVar*>>
3722 sequence_array_argument_;
3733 void BeginVisitModel(
const std::string& solver_name)
override;
3734 void EndVisitModel(
const std::string& solver_name)
override;
3735 void BeginVisitConstraint(
const std::string& type_name,
3737 void EndVisitConstraint(
const std::string& type_name,
3739 void BeginVisitIntegerExpression(
const std::string& type_name,
3740 const IntExpr* expr)
override;
3742 const IntExpr* expr)
override;
3745 const std::string& operation, int64_t value,
3746 IntVar* delegate)
override;
3748 const std::string& operation, int64_t value,
3753 int64_t value)
override;
3755 const std::vector<int64_t>& values)
override;
3762 const std::string& arg_name,
3763 const std::vector<IntVar*>& arguments)
override;
3768 const std::string& arg_name,
3769 const std::vector<IntervalVar*>& arguments)
override;
3774 const std::string& arg_name,
3775 const std::vector<SequenceVar*>& arguments)
override;
3783 std::vector<ArgumentHolder*> holders_;
3790 : index_min_(index_min),
3791 index_max_(index_max),
3792 values_(new T[index_max - index_min + 1]) {
3793 DCHECK_LE(index_min, index_max);
3796 ~ArrayWithOffset()
override {}
3798 virtual T Evaluate(int64_t index)
const {
3799 DCHECK_GE(index, index_min_);
3800 DCHECK_LE(index, index_max_);
3801 return values_[index - index_min_];
3805 DCHECK_GE(index, index_min_);
3806 DCHECK_LE(index, index_max_);
3807 values_[index - index_min_] = value;
3810 std::string DebugString()
const override {
return "ArrayWithOffset"; }
3813 const int64_t index_min_;
3814 const int64_t index_max_;
3815 std::unique_ptr<T[]> values_;
3823template <
class T,
class C>
3827 : block_size_(block_size), block_offset_(0) {
3828 CHECK_GT(block_size, 0);
3832 for (
int i = 0; i < elements_.size(); ++i) {
3833 delete[] elements_[i];
3837 T At(int64_t index)
const {
3838 const int64_t block_index = ComputeBlockIndex(index);
3839 const int64_t relative_index = block_index - block_offset_;
3840 if (relative_index < 0 || relative_index >= elements_.size()) {
3843 const T* block = elements_[relative_index];
3844 return block !=
nullptr ? block[index - block_index * block_size_] : T();
3848 const int64_t block_index = ComputeBlockIndex(index);
3849 T*
const block = GetOrCreateBlock(block_index);
3850 const int64_t residual = index - block_index * block_size_;
3852 reinterpret_cast<C
>(value));
3856 T* NewBlock()
const {
3857 T*
const result =
new T[block_size_];
3858 for (
int i = 0; i < block_size_; ++i) {
3864 T* GetOrCreateBlock(
int block_index) {
3865 if (elements_.size() == 0) {
3866 block_offset_ = block_index;
3867 GrowUp(block_index);
3868 }
else if (block_index < block_offset_) {
3869 GrowDown(block_index);
3870 }
else if (block_index - block_offset_ >= elements_.size()) {
3871 GrowUp(block_index);
3873 T* block = elements_[block_index - block_offset_];
3874 if (block ==
nullptr) {
3876 elements_[block_index - block_offset_] = block;
3881 int64_t ComputeBlockIndex(int64_t value)
const {
3882 return value >= 0 ? value / block_size_
3883 : (value - block_size_ + 1) / block_size_;
3886 void GrowUp(int64_t block_index) {
3887 elements_.resize(block_index - block_offset_ + 1);
3890 void GrowDown(int64_t block_index) {
3891 const int64_t delta = block_offset_ - block_index;
3892 block_offset_ = block_index;
3893 DCHECK_GT(delta, 0);
3894 elements_.insert(elements_.begin(), delta,
nullptr);
3897 const int64_t block_size_;
3898 std::vector<T*> elements_;
3909 static constexpr int kNoInserted = -1;
3912 explicit RevIntSet(
int capacity)
3913 : elements_(new
T[capacity]),
3915 capacity_(capacity),
3916 position_(new int[capacity]),
3917 delete_position_(
true) {
3918 for (
int i = 0;
i < capacity; ++
i) {
3919 position_[
i] = kNoInserted;
3924 RevIntSet(
int capacity,
int* shared_positions,
int shared_positions_size)
3925 : elements_(new T[capacity]),
3927 capacity_(capacity),
3928 position_(shared_positions),
3929 delete_position_(false) {
3930 for (
int i = 0; i < shared_positions_size; ++i) {
3936 if (delete_position_) {
3941 int Size()
const {
return num_elements_.Value(); }
3943 int Capacity()
const {
return capacity_; }
3945 T Element(
int i)
const {
3947 DCHECK_LT(i, num_elements_.Value());
3948 return elements_[
i];
3953 DCHECK_LT(i + num_elements_.Value(), capacity_);
3954 return elements_[i + num_elements_.Value()];
3958 const int position = num_elements_.Value();
3959 DCHECK_LT(position, capacity_);
3960 DCHECK(NotAlreadyInserted(elt));
3961 elements_[position] = elt;
3962 position_[elt] = position;
3963 num_elements_.Incr(solver);
3967 num_elements_.Decr(solver);
3968 SwapTo(value_index, num_elements_.Value());
3971 void Restore(
Solver*
const solver,
const T& value_index) {
3972 SwapTo(value_index, num_elements_.Value());
3973 num_elements_.Incr(solver);
3976 void Clear(
Solver*
const solver) { num_elements_.SetValue(solver, 0); }
3979 typedef const T* const_iterator;
3980 const_iterator begin()
const {
return elements_.get(); }
3985 bool NotAlreadyInserted(
const T& elt) {
3986 for (
int i = 0; i < num_elements_.Value(); ++i) {
3987 if (elt == elements_[i]) {
3994 void SwapTo(T value_index,
int next_position) {
3995 const int current_position = position_[value_index];
3996 if (current_position != next_position) {
3997 const T next_value_index = elements_[next_position];
3998 elements_[current_position] = next_value_index;
3999 elements_[next_position] = value_index;
4000 position_[value_index] = next_position;
4001 position_[next_value_index] = current_position;
4006 std::unique_ptr<T[]> elements_;
4008 NumericalRev<int> num_elements_;
4010 const int capacity_;
4014 const bool delete_position_;
4019class RevPartialSequence {
4021 explicit RevPartialSequence(
const std::vector<int>& items)
4024 last_ranked_(items.size() - 1),
4025 size_(items.size()),
4026 position_(new int[size_]) {
4027 for (
int i = 0;
i < size_; ++
i) {
4028 elements_[
i] = items[
i];
4033 explicit RevPartialSequence(
int size)
4036 last_ranked_(size - 1),
4038 position_(new int[size_]) {
4039 for (
int i = 0; i < size_; ++i) {
4047 int NumFirstRanked()
const {
return first_ranked_.Value(); }
4049 int NumLastRanked()
const {
return size_ - 1 - last_ranked_.Value(); }
4051 int Size()
const {
return size_; }
4054 const int& operator[](
int index)
const {
4055 DCHECK_GE(index, 0);
4056 DCHECK_LT(index, size_);
4057 return elements_[index];
4062 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
4063 SwapTo(elt, first_ranked_.Value());
4064 first_ranked_.Incr(solver);
4068 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
4069 SwapTo(elt, last_ranked_.Value());
4070 last_ranked_.Decr(solver);
4073 bool IsRanked(
int elt)
const {
4074 const int position = position_[elt];
4075 return (position < first_ranked_.Value() ||
4076 position > last_ranked_.Value());
4079 std::string DebugString()
const {
4080 std::string result =
"[";
4081 for (
int i = 0; i < first_ranked_.Value(); ++i) {
4082 absl::StrAppend(&result, elements_[i]);
4083 if (i != first_ranked_.Value() - 1) {
4088 for (
int i = first_ranked_.Value(); i <= last_ranked_.Value(); ++i) {
4089 absl::StrAppend(&result, elements_[i]);
4090 if (i != last_ranked_.Value()) {
4095 for (
int i = last_ranked_.Value() + 1; i < size_; ++i) {
4096 absl::StrAppend(&result, elements_[i]);
4097 if (i != size_ - 1) {
4106 void SwapTo(
int elt,
int next_position) {
4107 const int current_position = position_[elt];
4108 if (current_position != next_position) {
4109 const int next_elt = elements_[next_position];
4110 elements_[current_position] = next_elt;
4111 elements_[next_position] = elt;
4112 position_[elt] = next_position;
4113 position_[next_elt] = current_position;
4118 std::vector<int> elements_;
4120 NumericalRev<int> first_ranked_;
4122 NumericalRev<int> last_ranked_;
4126 std::unique_ptr<int[]> position_;
4133class UnsortedNullableRevBitset {
4136 explicit UnsortedNullableRevBitset(
int bit_size);
4138 ~UnsortedNullableRevBitset() {}
4142 void Init(Solver* solver,
const std::vector<uint64_t>& mask);
4146 bool RevSubtract(Solver* solver,
const std::vector<uint64_t>& mask);
4150 bool RevAnd(
Solver* solver,
const std::vector<uint64_t>& mask);
4157 bool Empty()
const {
return active_words_.Size() == 0; }
4166 bool Intersects(
const std::vector<uint64_t>& mask,
int* support_index);
4171 int64_t word_size()
const {
return word_size_; }
4176 void CleanUpActives(
Solver* solver);
4178 const int64_t bit_size_;
4179 const int64_t word_size_;
4182 std::vector<int> to_remove_;
4187 for (
int i = 0; i < values.size(); ++i) {
4188 if (values[i] != value) {
4197 for (
int i = 0;
i < values.size(); ++
i) {
4198 if (values[i] != 0 && values[i] != 1) {
4206bool AreAllOnes(
const std::vector<T>& values) {
4216bool AreAllGreaterOrEqual(
const std::vector<T>& values,
const T& value) {
4217 for (
const T& current_value : values) {
4218 if (current_value < value) {
4227 for (
const T& current_value : values) {
4228 if (current_value > value) {
4246bool AreAllStrictlyPositive(
const std::vector<T>& values) {
4247 return AreAllGreaterOrEqual(values, T(1));
4257 for (
int i = 0; i < values.size() - 1; ++i) {
4258 if (values[i + 1] != values[i] + 1) {
4267 for (
int i = 0; i < values.size() - 1; ++i) {
4268 if (values[i + 1] < values[i]) {
4276bool IsArrayInRange(
const std::vector<IntVar*>& vars, T range_min,
4278 for (
int i = 0;
i < vars.size(); ++
i) {
4279 if (vars[
i]->Min() < range_min || vars[
i]->Max() > range_max) {
4286inline bool AreAllBound(
const std::vector<IntVar*>& vars) {
4287 for (
int i = 0;
i < vars.size(); ++
i) {
4288 if (!vars[
i]->Bound()) {
4303 const std::vector<T>& values) {
4304 for (
int i = 0; i < vars.size(); ++i) {
4305 if (values[i] != 0 && !vars[i]->Bound()) {
4313inline bool AreAllBoundTo(
const std::vector<IntVar*>& vars, int64_t value) {
4314 for (
int i = 0; i < vars.size(); ++i) {
4315 if (!vars[i]->Bound() || vars[i]->Min() != value) {
4322inline int64_t
MaxVarArray(
const std::vector<IntVar*>& vars) {
4323 DCHECK(!vars.empty());
4325 for (
int i = 0;
i < vars.size(); ++
i) {
4327 result = std::max<int64_t>(result, vars[
i]->Max());
4332inline int64_t
MinVarArray(
const std::vector<IntVar*>& vars) {
4333 DCHECK(!vars.empty());
4335 for (
int i = 0;
i < vars.size(); ++
i) {
4337 result = std::min<int64_t>(result, vars[i]->Min());
4342inline void FillValues(
const std::vector<IntVar*>& vars,
4343 std::vector<int64_t>*
const values) {
4345 values->resize(vars.size());
4346 for (
int i = 0;
i < vars.size(); ++
i) {
4347 (*values)[i] = vars[i]->Value();
4353 return (e < 0 || e % v == 0) ? e / v : e / v + 1;
4358 return (e >= 0 || e % v == 0) ? e / v : e / v - 1;
4361std::vector<int64_t> ToInt64Vector(
const std::vector<int>&
input);
int64_t MemoryUsage(int unused)
Iterators on nodes used by Pathoperator to traverse the search space.
AlternativeNodeIterator(bool use_sibling)
void Reset(const PathOperator &path_operator, int base_index_reference)
~AlternativeNodeIterator()
Argument Holder: useful when visiting a model.
const IntTupleSet & FindIntegerMatrixArgumentOrDie(const std::string &arg_name) const
void SetIntervalArgument(const std::string &arg_name, IntervalVar *var)
void SetIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &vars)
IntExpr * FindIntegerExpressionArgumentOrDie(const std::string &arg_name) const
bool HasIntegerExpressionArgument(const std::string &arg_name) const
Checks if arguments exist.
const std::vector< IntVar * > & FindIntegerVariableArrayArgumentOrDie(const std::string &arg_name) const
void SetSequenceArgument(const std::string &arg_name, SequenceVar *var)
bool HasIntegerVariableArrayArgument(const std::string &arg_name) const
const std::vector< int64_t > & FindIntegerArrayArgumentOrDie(const std::string &arg_name) const
int64_t FindIntegerArgumentOrDie(const std::string &arg_name) const
void SetSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &vars)
int64_t FindIntegerArgumentWithDefault(const std::string &arg_name, int64_t def) const
Getters.
void SetValue(int64_t index, T value)
const E & Element(const V *const var) const
bool Contains(const V *const var) const
AssignmentContainer< IntVar, IntVarElement > IntContainer
virtual IntVar * CastToVar()
IntVar * Var() override
Creates a variable from the expression.
BaseIntExpr(Solver *const s)
void AppendToFragment(int index)
bool HasFragments() const override
virtual void InitFragments()
BaseLns(const std::vector< IntVar * > &vars)
--— Base Large Neighborhood Search operator --—
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
virtual bool NextFragment()=0
BaseNodeIterators(const PathOperator *path_operator, int base_index_reference)
AlternativeNodeIterator * GetAlternativeIterator() const
NodeNeighborIterator * GetNeighborIterator() const
void Reset(bool update_end_nodes=false)
AlternativeNodeIterator * GetSiblingAlternativeIterator() const
bool HasReachedEnd() const
virtual std::string DebugString() const
void CopyBucket(const Bitset64< IndexType > &other, IndexType i)
Copies bucket containing bit i from "other" to "this".
bool Contains(int64_t v) const override
IntVarIterator * MakeDomainIterator(bool reversible) const override
IntVar * IsGreaterOrEqual(int64_t constant) override
IntVarIterator * MakeHoleIterator(bool reversible) const override
--— Misc --—
IntVar * IsEqual(int64_t constant) override
IsEqual.
void RemoveValue(int64_t v) override
This method removes the value 'v' from the domain of the variable.
int64_t Value() const override
IntVar * IsDifferent(int64_t constant) override
SimpleRevFIFO< Demon * > delayed_bound_demons_
void RemoveInterval(int64_t l, int64_t u) override
virtual void RestoreValue()=0
uint64_t Size() const override
This method returns the number of values in the domain of the variable.
static const int kUnboundBooleanVarValue
--— Boolean variable --—
void WhenBound(Demon *d) override
int VarType() const override
------— IntVar ------—
IntVar * IsLessOrEqual(int64_t constant) override
std::string BaseName() const override
Returns a base name for automatic naming.
void WhenRange(Demon *d) override
Attach a demon that will watch the min or the max of the expression.
Demon proxy to a method on the constraint with no arguments.
std::string DebugString() const override
CallMethod0(T *const ct, void(T::*method)(), const std::string &name)
Demon proxy to a method on the constraint with one argument.
CallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)
std::string DebugString() const override
Demon proxy to a method on the constraint with two arguments.
std::string DebugString() const override
CallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
Demon proxy to a method on the constraint with three arguments.
CallMethod3(T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
std::string DebugString() const override
virtual int64_t ModifyValue(int64_t index, int64_t value)=0
bool MakeOneNeighbor() override
This method should not be overridden. Override ModifyValue() instead.
ChangeValue(const std::vector< IntVar * > &vars)
--— ChangeValue Operators --—
Constraint(Solver *const solver)
Low-priority demon proxy to a method on the constraint with no arguments.
~DelayedCallMethod0() override
DelayedCallMethod0(T *const ct, void(T::*method)(), const std::string &name)
std::string DebugString() const override
Solver::DemonPriority priority() const override
---------------— Demon class -------------—
Low-priority demon proxy to a method on the constraint with one argument.
~DelayedCallMethod1() override
DelayedCallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)
Solver::DemonPriority priority() const override
---------------— Demon class -------------—
std::string DebugString() const override
Low-priority demon proxy to a method on the constraint with two arguments.
std::string DebugString() const override
Solver::DemonPriority priority() const override
---------------— Demon class -------------—
DelayedCallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
~DelayedCallMethod2() override
virtual void SetValue(int64_t v)
This method sets the value of the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual int64_t Min() const =0
--— Main IntTupleSet class --—
int64_t OldInverseValue(int64_t index) const
void AddToAssignment(IntVar *var, int64_t value, bool active, std::vector< int > *assignment_indices, int64_t index, Assignment *assignment) const
virtual bool SkipUnchanged(int) const
virtual bool IsIncremental() const
bool Activated(int64_t index) const
void SetValue(int64_t index, int64_t value)
void Start(const Assignment *assignment) override
void RevertChanges(bool change_was_incremental)
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
--— Base operator class for operators manipulating IntVars --—
void AddVars(const std::vector< IntVar * > &vars)
void Deactivate(int64_t index)
IntVar * Var(int64_t index) const
Returns the variable of given index.
int64_t Value(int64_t index) const
int64_t InverseValue(int64_t index) const
bool ApplyChanges(Assignment *delta, Assignment *deltadelta) const
int64_t PrevValue(int64_t index) const
bool HoldsDelta() const override
IntVarLocalSearchOperator(const std::vector< IntVar * > &vars, bool keep_inverse_values=false)
void Activate(int64_t index)
int64_t OldValue(int64_t index) const
virtual bool MakeOneNeighbor()
~IntVarLocalSearchOperator() override
virtual void WhenBound(Demon *d)=0
int index() const
Returns the index of the variable.
IntVar(Solver *s)
-------— IntVar -------—
--— LightIntFunctionElementCt --—
LightIntFunctionElementCt(Solver *const solver, IntVar *const var, IntVar *const index, F values, std::function< bool()> deep_serialize)
~LightIntFunctionElementCt() override
void InitialPropagate() override
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
std::string DebugString() const override
--------------— Constraint class ----------------—
--— LightIntIntFunctionElementCt --—
~LightIntIntFunctionElementCt() override
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
void InitialPropagate() override
LightIntIntFunctionElementCt(Solver *const solver, IntVar *const var, IntVar *const index1, IntVar *const index2, F values, std::function< bool()> deep_serialize)
std::string DebugString() const override
--------------— Constraint class ----------------—
--— LightIntIntIntFunctionElementCt --—
LightIntIntIntFunctionElementCt(Solver *const solver, IntVar *const var, IntVar *const index1, IntVar *const index2, IntVar *const index3, F values)
std::string DebugString() const override
--------------— Constraint class ----------------—
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
~LightIntIntIntFunctionElementCt() override
void InitialPropagate() override
LocalSearchFilterManager(std::vector< FilterEvent > filter_events)
void Revert()
Calls Revert() of filters, in reverse order of Relax events.
int64_t GetSynchronizedObjectiveValue() const
void Synchronize(const Assignment *assignment, const Assignment *delta)
Synchronizes all filters to assignment.
bool Accept(LocalSearchMonitor *monitor, const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max)
virtual bool IsIncremental() const
virtual void Reset()
Sets the filter to empty solution.
virtual void Revert()
Cancels the changes made by the last Relax()/Accept() calls.
virtual bool Accept(const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max)=0
virtual int64_t GetSynchronizedObjectiveValue() const
Objective value from last time Synchronize() was called.
virtual void Synchronize(const Assignment *assignment, const Assignment *delta)=0
virtual bool IsActive() const =0
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
void Install() override
Install itself on the solver.
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
int64_t CheckPointValue(int64_t index) const
void SetCandidateActive(int64_t index, bool active)
void SetCurrentDomainInjectiveAndKeepInverseValues(int max_value)
void Revert(bool only_incremental)
int64_t CandidateValue(int64_t index) const
LocalSearchOperatorState()
void SetCandidateValue(int64_t index, int64_t value)
const std::vector< int64_t > & IncrementalIndicesChanged() const
const std::vector< int64_t > & CandidateIndicesChanged() const
int64_t CommittedInverseValue(int64_t value) const
int64_t CommittedValue(int64_t index) const
bool CandidateIsActive(int64_t index) const
int64_t CandidateInverseValue(int64_t value) const
virtual bool HoldsDelta() const
virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0
virtual const LocalSearchOperator * Self() const
virtual void EnterSearch()
virtual bool HasFragments() const
~LocalSearchOperator() override
virtual void Start(const Assignment *assignment)=0
bool SetMax(int64_t new_max) const
friend class LocalSearchState
Only LocalSearchState can construct LocalSearchVariables.
bool StateIsFeasible() const
void PropagateRelax(VariableDomainId domain_id)
Propagation of all events.
static Variable DummyVariable()
Makes a variable with no state, this is meant as a placeholder.
Variable MakeVariable(VariableDomainId domain_id)
Variable MakeVariableWithRelaxedDomain(int64_t min, int64_t max)
bool PropagateTighten(VariableDomainId domain_id)
virtual void InsertVarArrayConstantArrayExpression(IntExpr *expression, const std::vector< IntVar * > &var, const std::vector< int64_t > &values, VarArrayConstantArrayExpressionType type)=0
VarArrayConstantExpressionType
@ VAR_ARRAY_CONSTANT_INDEX
@ VAR_ARRAY_CONSTANT_EXPRESSION_MAX
VarArrayConstantArrayExpressionType
@ VAR_ARRAY_CONSTANT_ARRAY_EXPRESSION_MAX
@ VAR_ARRAY_CONSTANT_ARRAY_SCAL_PROD
virtual void InsertVarConstantConstraint(Constraint *ct, IntVar *var, int64_t value, VarConstantConstraintType type)=0
virtual IntExpr * FindExprExprExpression(IntExpr *var1, IntExpr *var2, ExprExprExpressionType type) const =0
Expr Expr Expressions.
virtual Constraint * FindExprExprConstraint(IntExpr *expr1, IntExpr *expr2, ExprExprConstraintType type) const =0
Expr Expr Constraints.
virtual Constraint * FindVoidConstraint(VoidConstraintType type) const =0
Void constraints.
virtual IntExpr * FindVarArrayConstantArrayExpression(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values, VarArrayConstantArrayExpressionType type) const =0
Var Array Constant Array Expressions.
virtual IntExpr * FindVarArrayExpression(const std::vector< IntVar * > &vars, VarArrayExpressionType type) const =0
Var Array Expressions.
virtual IntExpr * FindExprExpression(IntExpr *expr, ExprExpressionType type) const =0
Expr Expressions.
VarConstantConstraintType
virtual void InsertExprExprConstraint(Constraint *ct, IntExpr *expr1, IntExpr *expr2, ExprExprConstraintType type)=0
ExprConstantExpressionType
@ EXPR_CONSTANT_IS_NOT_EQUAL
@ EXPR_CONSTANT_IS_GREATER_OR_EQUAL
@ EXPR_CONSTANT_IS_LESS_OR_EQUAL
@ EXPR_CONSTANT_DIFFERENCE
@ EXPR_CONSTANT_EXPRESSION_MAX
virtual void InsertExprExpression(IntExpr *expression, IntExpr *expr, ExprExpressionType type)=0
VarConstantArrayExpressionType
@ VAR_CONSTANT_ARRAY_EXPRESSION_MAX
@ VAR_CONSTANT_ARRAY_ELEMENT
virtual void InsertVoidConstraint(Constraint *ct, VoidConstraintType type)=0
virtual void InsertExprExprExpression(IntExpr *expression, IntExpr *var1, IntExpr *var2, ExprExprExpressionType type)=0
virtual void InsertVarConstantArrayExpression(IntExpr *expression, IntVar *var, const std::vector< int64_t > &values, VarConstantArrayExpressionType type)=0
@ EXPR_EXPR_EXPRESSION_MAX
@ EXPR_EXPR_IS_LESS_OR_EQUAL
virtual IntExpr * FindVarArrayConstantExpression(const std::vector< IntVar * > &vars, int64_t value, VarArrayConstantExpressionType type) const =0
Var Array Constant Expressions.
virtual void InsertExprConstantExpression(IntExpr *expression, IntExpr *var, int64_t value, ExprConstantExpressionType type)=0
VarConstantConstantExpressionType
@ VAR_CONSTANT_CONSTANT_EXPRESSION_MAX
virtual void InsertVarConstantConstantConstraint(Constraint *ct, IntVar *var, int64_t value1, int64_t value2, VarConstantConstantConstraintType type)=0
virtual void InsertVarArrayConstantExpression(IntExpr *expression, const std::vector< IntVar * > &var, int64_t value, VarArrayConstantExpressionType type)=0
virtual void InsertVarConstantConstantExpression(IntExpr *expression, IntVar *var, int64_t value1, int64_t value2, VarConstantConstantExpressionType type)=0
ExprExprConstantExpressionType
@ EXPR_EXPR_CONSTANT_CONDITIONAL
@ EXPR_EXPR_CONSTANT_EXPRESSION_MAX
virtual Constraint * FindVarConstantConstraint(IntVar *var, int64_t value, VarConstantConstraintType type) const =0
Var Constant Constraints.
virtual IntExpr * FindVarConstantArrayExpression(IntVar *var, const std::vector< int64_t > &values, VarConstantArrayExpressionType type) const =0
Var Constant Array Expressions.
@ VAR_ARRAY_EXPRESSION_MAX
@ EXPR_EXPR_GREATER_OR_EQUAL
@ EXPR_EXPR_LESS_OR_EQUAL
@ EXPR_EXPR_CONSTRAINT_MAX
ModelCache(Solver *solver)
--— ModelCache --—
virtual IntExpr * FindExprConstantExpression(IntExpr *expr, int64_t value, ExprConstantExpressionType type) const =0
Expr Constant Expressions.
virtual void InsertExprExprConstantExpression(IntExpr *expression, IntExpr *var1, IntExpr *var2, int64_t constant, ExprExprConstantExpressionType type)=0
virtual IntExpr * FindExprExprConstantExpression(IntExpr *var1, IntExpr *var2, int64_t constant, ExprExprConstantExpressionType type) const =0
Expr Expr Constant Expressions.
virtual IntExpr * FindVarConstantConstantExpression(IntVar *var, int64_t value1, int64_t value2, VarConstantConstantExpressionType type) const =0
Var Constant Constant Expressions.
virtual Constraint * FindVarConstantConstantConstraint(IntVar *var, int64_t value1, int64_t value2, VarConstantConstantConstraintType type) const =0
Var Constant Constant Constraints.
virtual void InsertVarArrayExpression(IntExpr *expression, const std::vector< IntVar * > &vars, VarArrayExpressionType type)=0
VarConstantConstantConstraintType
@ VAR_CONSTANT_CONSTANT_CONSTRAINT_MAX
@ VAR_CONSTANT_CONSTANT_BETWEEN
void VisitIntervalArgument(const std::string &arg_name, IntervalVar *argument) override
Visit interval argument.
void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments) override
void VisitIntervalVariable(const IntervalVar *variable, const std::string &operation, int64_t value, IntervalVar *delegate) override
void VisitIntegerArgument(const std::string &arg_name, int64_t value) override
Integer arguments.
void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64_t > &values) override
void VisitSequenceVariable(const SequenceVar *variable) override
void VisitSequenceArgument(const std::string &arg_name, SequenceVar *argument) override
Visit sequence argument.
void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments) override
void VisitIntegerVariable(const IntVar *variable, IntExpr *delegate) override
void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments) override
void PushArgumentHolder()
ArgumentHolder * Top() const
void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &values) override
void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *expr) override
void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *argument) override
Variables.
static const char kMinArgument[]
static const char kTargetArgument[]
static const char kMaxArgument[]
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *argument)
Visit integer expression argument.
static const char kIndexArgument[]
static const char kLightElementEqual[]
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *constraint)
static const char kIndex2Argument[]
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64_t index_min, int64_t index_max)
static const char kIndex3Argument[]
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *constraint)
bool IsIncomingNeighbor() const
bool IsOutgoingNeighbor() const
void Reset(const PathOperator &path_operator, int base_index_reference)
Subclass of Rev<T> which adds numerical operations.
void Incr(Solver *const s)
bool HasNeighbors() const
int number_of_nexts() const
Number of next variables.
bool SkipUnchanged(int index) const override
bool MakeChainInactive(int64_t before_chain, int64_t chain_end)
int64_t Prev(int64_t node) const
Returns the node before node in the current delta.
bool SwapActiveAndInactive(int64_t active, int64_t inactive)
Replaces active by inactive in the current path, making active inactive.
int PathClassFromStartNode(int64_t start_node) const
int64_t Path(int64_t node) const
void AddPairAlternativeSets(const std::vector< PairType > &pair_alternative_sets)
bool MakeActive(int64_t node, int64_t destination)
Insert the inactive node after destination.
int64_t OldNext(int64_t node) const
virtual void ResetIncrementalism()
virtual bool ConsiderAlternatives(int64_t) const
bool SwapNodes(int64_t node1, int64_t node2)
Swaps the nodes node1 and node2.
int64_t BaseSiblingAlternativeNode(int i) const
Returns the alternative node for the sibling of the ith base node.
void SetNext(int64_t from, int64_t to, int64_t path)
Sets 'to' to be the node after 'from' on the given path.
const int number_of_nexts_
virtual bool OnSamePathAsPreviousBase(int64_t)
virtual int64_t GetBaseNodeRestartPosition(int base_index)
int CurrentNodePathStart(int64_t node) const
int GetSiblingAlternativeIndex(int node) const
Returns the index of the alternative set of the sibling of node.
int64_t OldPath(int64_t node) const
int GetAlternativeIndex(int node) const
Returns the index of the alternative set of the node.
int64_t PrevNext(int64_t node) const
virtual bool InitPosition() const
int64_t OldPrev(int64_t node) const
virtual void OnNodeInitialization()
int AddAlternativeSet(const std::vector< int64_t > &alternative_set)
int64_t GetActiveAlternativeSibling(int node) const
bool IsPathStart(int64_t node) const
Returns true if node is the first node on the path.
bool MoveChain(int64_t before_chain, int64_t chain_end, int64_t destination)
bool IsPathEnd(int64_t node) const
bool SwapActiveAndInactiveChains(absl::Span< const int64_t > active_chain, absl::Span< const int64_t > inactive_chain)
virtual bool MakeNeighbor()=0
int64_t EndNode(int i) const
Returns the end node of the ith base node.
int64_t GetActiveInAlternativeSet(int alternative_index) const
Returns the active node in the given alternative set.
PathOperator(const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, IterationParameters iteration_parameters)
Builds an instance of PathOperator from next and path variables.
virtual bool RestartAtPathStartOnSynchronize()
bool IsInactive(int64_t node) const
Returns true if node is inactive.
const std::vector< int64_t > & path_starts() const
Returns the vector of path start nodes.
bool CheckChainValidity(int64_t before_chain, int64_t chain_end, int64_t exclude) const
bool ReverseChain(int64_t before_chain, int64_t after_chain, int64_t *chain_last)
int PathClass(int i) const
Returns the class of the path of the ith base node.
void EnterSearch() override
virtual void SetNextBaseToIncrement(int64_t base_index)
int64_t BaseAlternativeNode(int i) const
Returns the alternative node for the ith base node.
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
int64_t StartNode(int i) const
Returns the start node of the ith base node.
int64_t BaseNode(int i) const
Returns the ith base node of the operator.
int CurrentNodePathEnd(int64_t node) const
virtual void SetValues(IntVar *var, const std::vector< int64_t > &values)=0
virtual void SetDurationMax(IntervalVar *var, int64_t new_max)=0
virtual void SetStartMax(IntervalVar *var, int64_t new_max)=0
virtual void SetStartMin(IntervalVar *var, int64_t new_min)=0
IntervalVar modifiers.
virtual void PopContext()=0
virtual void RankSequence(SequenceVar *var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)=0
virtual void RankNotFirst(SequenceVar *var, int index)=0
std::string DebugString() const override
virtual void RankNotLast(SequenceVar *var, int index)=0
virtual void PushContext(const std::string &context)=0
virtual void SetPerformed(IntervalVar *var, bool value)=0
virtual void SetEndMax(IntervalVar *var, int64_t new_max)=0
virtual void RemoveValue(IntVar *var, int64_t value)=0
virtual void EndDemonRun(Demon *demon)=0
virtual void SetDurationMin(IntervalVar *var, int64_t new_min)=0
virtual void SetMin(IntExpr *expr, int64_t new_min)=0
IntExpr modifiers.
virtual void SetEndMin(IntervalVar *var, int64_t new_min)=0
virtual void RankFirst(SequenceVar *var, int index)=0
SequenceVar modifiers.
virtual void SetMax(IntExpr *expr, int64_t new_max)=0
virtual void RankLast(SequenceVar *var, int index)=0
virtual void SetDurationRange(IntervalVar *var, int64_t new_min, int64_t new_max)=0
virtual void StartProcessingIntegerVariable(IntVar *var)=0
virtual void EndProcessingIntegerVariable(IntVar *var)=0
void Install() override
Install itself on the solver.
virtual void RemoveInterval(IntVar *var, int64_t imin, int64_t imax)=0
virtual void SetRange(IntExpr *expr, int64_t new_min, int64_t new_max)=0
virtual void RemoveValues(IntVar *var, const std::vector< int64_t > &values)=0
virtual void SetStartRange(IntervalVar *var, int64_t new_min, int64_t new_max)=0
virtual void SetValue(IntVar *var, int64_t value)=0
virtual void SetEndRange(IntervalVar *var, int64_t new_min, int64_t new_max)=0
Matrix version of the RevBitSet class.
bool IsSet(int64_t row, int64_t column) const
Returns whether the 'column' bit in the 'row' row is set.
void ClearAll(Solver *solver)
Cleans all bits.
int64_t GetFirstBit(int row, int start) const
void SetToZero(Solver *solver, int64_t row, int64_t column)
Erases the 'column' bit in the 'row' row.
void SetToOne(Solver *solver, int64_t row, int64_t column)
Sets the 'column' bit in the 'row' row.
int64_t Cardinality() const
Returns the number of bits set to one.
void ClearAll(Solver *solver)
Cleans all bits.
RevBitSet(int64_t size)
-------— RevBitSet -------—
void SetToZero(Solver *solver, int64_t index)
Erases the 'index' bit.
bool IsCardinalityOne() const
Does it contains only one bit set?
void SetToOne(Solver *solver, int64_t index)
Sets the 'index' bit.
friend class RevBitMatrix
bool IsSet(int64_t index) const
Returns whether the 'index' bit is set.
int64_t GetFirstBit(int start) const
bool IsCardinalityZero() const
Is bitset null?
void RevInsert(Solver *const solver, int64_t index, T value)
void Insert(const K &key, const V &value)
Inserts (key, value) in the multi-map.
bool ContainsKey(const K &key) const
Returns true if the multi-map contains at least one instance of 'key'.
RevImmutableMultiMap(Solver *const solver, int initial_size)
const V & FindWithDefault(const K &key, const V &default_value) const
RevIntSet(int capacity)
Capacity is the fixed size of the set (it cannot grow).
void Remove(Solver *const solver, const T &value_index)
const T * const_iterator
Iterators on the indices.
void Insert(Solver *const solver, const T &elt)
T RemovedElement(int i) const
const_iterator end() const
static constexpr int kNoInserted
--— RevPartialSequence --—
void RankLast(Solver *const solver, int elt)
int NumLastRanked() const
void RankFirst(Solver *const solver, int elt)
A reversible switch that can switch once from false to true.
void Switch(Solver *const solver)
virtual void OutputLine(const std::string &line)
void EndInitialPropagation() override
After the initial propagation.
void BeginInitialPropagation() override
Before the initial propagation.
std::string DebugString() const override
A search monitor is a simple set of callbacks to monitor all search events.
SearchMonitor(Solver *const s)
Iterator(const SimpleRevFIFO< T > *l)
void SetLastValue(const T &v)
Sets the last value in the FIFO.
const T * Last() const
Returns the last item of the FIFO.
void Push(Solver *const s, T val)
void PushIfNotTop(Solver *const s, T val)
Pushes the var on top if is not a duplicate of the current top object.
const T & LastValue() const
Returns the last value in the FIFO.
void SetToZero(Solver *solver, int64_t pos)
Erases the 'pos' bit.
SmallRevBitSet(int64_t size)
-------— SmallRevBitSet -------—
void SetToOne(Solver *solver, int64_t pos)
Sets the 'pos' bit.
bool IsCardinalityZero() const
Is bitset null?
int64_t Cardinality() const
Returns the number of bits set to one.
int64_t GetFirstOne() const
bool IsCardinalityOne() const
Does it contains only one bit set?
For the time being, Solver is neither MT_SAFE nor MT_HOT.
std::function< int64_t(int64_t, int64_t, int64_t)> IndexEvaluator3
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
void Set(IntegerType index)
const std::vector< ArcId > & ComputeSortedSubDagArcs(NodeId node)
void BuildGraph(int num_nodes)
-------— Symmetry Breaking -------—
int64_t bit_size() const
Returns the number of bits given in the constructor of the bitset.
const RevIntSet< int > & active_words() const
Returns the set of active word indices.
int ActiveWordSize() const
bool RevAnd(Solver *solver, const std::vector< uint64_t > &mask)
absl::Status Exists(absl::string_view path, Options options)
For infeasible and unbounded see Not checked if options check_solutions_if_inf_or_unbounded and the If options first_solution_only is false
problem is infeasible or unbounded (default).
dual_gradient T(y - `dual_solution`) class DiagonalTrustRegionProblemFromQp
std::function< int64_t(const Model &)> Value(IntegerVariable v)
This checks that the variable is fixed.
In SWIG mode, we don't want anything besides these top-level includes.
LocalSearchOperator * MakeExtendedSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExtendedSwapActive --—
std::string ParameterDebugString(P param)
bool IsArrayConstant(const std::vector< T > &values, const T &value)
bool AreAllLessOrEqual(const std::vector< T > &values, const T &value)
LocalSearchOperator * RelocateAndMakeInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— RelocateAndMakeInactive --—
LocalSearchOperator * MakeTSPOpt(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)
--— TSP-based operators --—
LocalSearchOperator * MakeCross(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— Cross --—
SubDagComputer::ArcId ArcId
Demon * MakeConstraintDemon3(Solver *const s, T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
LocalSearchOperator * MakeSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— SwapActive --—
LocalSearchOperator * ExchangeAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExchangeAndMakeActive --—
bool AreAllNegative(const std::vector< T > &values)
bool AreAllGreaterOrEqual(const std::vector< T > &values, const T &value)
bool IsIncreasing(const std::vector< T > &values)
bool IsArrayBoolean(const std::vector< T > &values)
LocalSearchOperator * MakeExchange(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— Exchange --—
void AcceptUncheckedNeighbor(Search *search)
LocalSearchOperator * MakeActiveAndRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeActiveAndRelocate --—
bool AreAllBoundOrNull(const std::vector< IntVar * > &vars, const std::vector< T > &values)
int64_t MaxVarArray(const std::vector< IntVar * > &vars)
LocalSearchOperator * MakeTSPLns(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)
Demon * MakeConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
Demon * MakeDelayedConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
LocalSearchOperator * MakeRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr, int64_t chain_length=1LL, bool single_path=false, const std::string &name="Relocate")
--— Relocate --—
LocalSearchOperator * RelocateAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
-— RelocateAndMakeActive --—
void FillValues(const std::vector< IntVar * > &vars, std::vector< int64_t > *const values)
bool AreAllBooleans(const std::vector< IntVar * > &vars)
bool AreAllStrictlyNegative(const std::vector< T > &values)
LocalSearchOperator * MakePathLns(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments)
--— Path-based Large Neighborhood Search --—
int64_t MinVarArray(const std::vector< IntVar * > &vars)
LocalSearchOperator * MakeInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeInactive --—
void RegisterDemon(Solver *const solver, Demon *const demon, DemonProfiler *const monitor)
--— Exported Methods for Unit Tests --—
LocalSearchOperator * MakeTwoOpt(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— 2Opt --—
LocalSearchOperator * MakeChainInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— MakeChainInactive --—
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
static const int kUnassigned
--— Routing model --—
bool IsIncreasingContiguous(const std::vector< T > &values)
bool AreAllNull(const std::vector< T > &values)
bool AreAllPositive(const std::vector< T > &values)
LocalSearchOperator * ExchangePathStartEndsAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)
--— ExchangePathEndsAndMakeActive --—
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
LocalSearchOperator * MakeSwapActiveChain(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int max_chain_size)
--— SwapActiveChain --—
LocalSearchOperator * MakeLinKernighan(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)
--— Lin-Kernighan --—
LocalSearchState::VariableDomainId VariableDomainId
int64_t PosIntDivDown(int64_t e, int64_t v)
bool IsArrayInRange(const std::vector< IntVar * > &vars, T range_min, T range_max)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
bool AreAllOnes(const std::vector< T > &values)
bool AreAllBound(const std::vector< IntVar * > &vars)
uint64_t Hash1(uint64_t value)
LocalSearchOperator * MakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
--— MakeActive --—
int64_t PosIntDivUp(int64_t e, int64_t v)
SubDagComputer::NodeId NodeId
trees with all degrees equal to
static int input(yyscan_t yyscanner)
#define DEFINE_STRONG_INT_TYPE(type_name, value_type)
ConstraintId constraint_id
VariableDomainId domain_id
Set of parameters used to configure how the neighborhood is traversed.
bool accept_path_end_base
True if path ends should be considered when iterating over neighbors.
std::function< int(int64_t)> start_empty_path_class
std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors
bool skip_locally_optimal_paths
int number_of_base_nodes
Number of nodes needed to define a neighbor.
std::function< const std::vector< int > &(int, int)> get_incoming_neighbors
static const int64_t kint64max
static const int64_t kint64min