49#ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
50#define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_
60#include "absl/container/flat_hash_map.h"
61#include "absl/strings/str_cat.h"
62#include "absl/strings/str_format.h"
63#include "absl/strings/str_join.h"
80class CPConstraintProto;
81class CPIntegerExpressionProto;
82class CPIntervalVariableProto;
147 enum { CHUNK_SIZE = 16 };
150 const Chunk*
const next_;
151 explicit Chunk(
const Chunk*
next) : next_(
next) {}
159 : chunk_(l->chunks_), value_(l->
Last()) {}
160 bool ok()
const {
return (value_ !=
nullptr); }
164 if (value_ == chunk_->data_ + CHUNK_SIZE) {
165 chunk_ = chunk_->next_;
166 value_ = chunk_ ? chunk_->data_ :
nullptr;
178 if (pos_.
Value() == 0) {
179 Chunk*
const chunk = s->UnsafeRevAlloc(
new Chunk(chunks_));
181 reinterpret_cast<void*
>(chunk));
186 chunks_->data_[pos_.
Value()] = val;
191 if (chunks_ ==
nullptr ||
LastValue() != val) {
198 return chunks_ ? &chunks_->data_[pos_.
Value()] :
nullptr;
206 return chunks_->data_[pos_.
Value()];
212 chunks_->data_[pos_.
Value()] = v;
235 a = (
a + 0x7ed55d16) + (
a << 12);
236 a = (
a ^ 0xc761c23c) ^ (
a >> 19);
237 a = (
a + 0x165667b1) + (
a << 5);
238 a = (
a + 0xd3a2646c) ^ (
a << 9);
239 a = (
a + 0xfd7046c5) + (
a << 3);
240 a = (
a ^ 0xb55a4f09) ^ (
a >> 16);
249#if defined(__x86_64__) || defined(_M_X64) || defined(__powerpc64__) || \
259 if (ptrs.empty())
return 0;
260 if (ptrs.size() == 1)
return Hash1(ptrs[0]);
262 for (
int i = 1; i < ptrs.size(); ++i) {
269 if (ptrs.empty())
return 0;
270 if (ptrs.size() == 1)
return Hash1(ptrs[0]);
272 for (
int i = 1; i < ptrs.size(); ++i) {
280template <
class K,
class V>
285 array_(solver->UnsafeRevAllocArray(new Cell*[initial_size])),
288 memset(array_, 0,
sizeof(*array_) * size_.
Value());
298 Cell* tmp = array_[code];
300 if (tmp->key() == key) {
313 Cell* tmp = array_[code];
315 if (tmp->key() == key) {
320 return default_value;
325 const int position =
Hash1(key) % size_.
Value();
327 solver_->UnsafeRevAlloc(
new Cell(key,
value, array_[position]));
329 reinterpret_cast<void*
>(cell));
330 num_items_.
Incr(solver_);
339 Cell(
const K& key,
const V&
value, Cell*
const next)
340 : key_(key), value_(
value), next_(
next) {}
342 void SetRevNext(Solver*
const solver, Cell*
const next) {
343 solver->SaveAndSetValue(
reinterpret_cast<void**
>(&next_),
344 reinterpret_cast<void*
>(
next));
347 Cell*
next()
const {
return next_; }
349 const K& key()
const {
return key_; }
351 const V&
value()
const {
return value_; }
360 Cell**
const old_cell_array = array_;
361 const int old_size = size_.
Value();
364 reinterpret_cast<void**
>(&array_),
365 reinterpret_cast<void*
>(
366 solver_->UnsafeRevAllocArray(
new Cell*[size_.
Value()])));
367 memset(array_, 0, size_.
Value() *
sizeof(*array_));
368 for (
int i = 0; i < old_size; ++i) {
369 Cell* tmp = old_cell_array[i];
370 while (tmp !=
nullptr) {
371 Cell*
const to_reinsert = tmp;
374 to_reinsert->SetRevNext(solver_, array_[new_position]);
376 reinterpret_cast<void**
>(&array_[new_position]),
377 reinterpret_cast<void*
>(to_reinsert));
382 Solver*
const solver_;
384 NumericalRev<int> size_;
385 NumericalRev<int> num_items_;
455 void Save(
Solver*
const solver,
int offset);
494 const int64 columns_;
508 : constraint_(
ct), method_(method), name_(
name) {}
512 void Run(
Solver*
const s)
override { (constraint_->*method_)(); }
515 return "CallMethod_" + name_ +
"(" + constraint_->DebugString() +
")";
519 T*
const constraint_;
520 void (T::*
const method_)();
521 const std::string name_;
526 const std::string&
name) {
532 return absl::StrCat(param);
538 return param->DebugString();
542template <
class T,
class P>
547 : constraint_(
ct), method_(method), name_(
name), param1_(param1) {}
551 void Run(
Solver*
const s)
override { (constraint_->*method_)(param1_); }
554 return absl::StrCat(
"CallMethod_", name_,
"(", constraint_->DebugString(),
559 T*
const constraint_;
560 void (T::*
const method_)(P);
561 const std::string name_;
565template <
class T,
class P>
567 const std::string&
name, P param1) {
572template <
class T,
class P,
class Q>
586 (constraint_->*method_)(param1_, param2_);
590 return absl::StrCat(absl::StrCat(
"CallMethod_", name_),
591 absl::StrCat(
"(", constraint_->DebugString()),
597 T*
const constraint_;
598 void (T::*
const method_)(P, Q);
599 const std::string name_;
604template <
class T,
class P,
class Q>
606 void (T::*method)(P, Q),
const std::string&
name,
607 P param1, Q param2) {
612template <
class T,
class P,
class Q,
class R>
616 P param1, Q param2, R param3)
627 (constraint_->*method_)(param1_, param2_, param3_);
631 return absl::StrCat(absl::StrCat(
"CallMethod_", name_),
632 absl::StrCat(
"(", constraint_->DebugString()),
639 T*
const constraint_;
640 void (T::*
const method_)(P, Q, R);
641 const std::string name_;
647template <
class T,
class P,
class Q,
class R>
649 void (T::*method)(P, Q, R),
const std::string&
name,
650 P param1, Q param2, R param3) {
666 : constraint_(
ct), method_(method), name_(
name) {}
670 void Run(
Solver*
const s)
override { (constraint_->*method_)(); }
677 return "DelayedCallMethod_" + name_ +
"(" + constraint_->DebugString() +
682 T*
const constraint_;
683 void (T::*
const method_)();
684 const std::string name_;
690 const std::string&
name) {
695template <
class T,
class P>
700 : constraint_(
ct), method_(method), name_(
name), param1_(param1) {}
704 void Run(
Solver*
const s)
override { (constraint_->*method_)(param1_); }
711 return absl::StrCat(
"DelayedCallMethod_", name_,
"(",
712 constraint_->DebugString(),
", ",
717 T*
const constraint_;
718 void (T::*
const method_)(P);
719 const std::string name_;
723template <
class T,
class P>
725 void (T::*method)(P),
726 const std::string&
name, P param1) {
731template <
class T,
class P,
class Q>
735 const std::string&
name, P param1, Q param2)
745 (constraint_->*method_)(param1_, param2_);
753 return absl::StrCat(absl::StrCat(
"DelayedCallMethod_", name_),
754 absl::StrCat(
"(", constraint_->DebugString()),
760 T*
const constraint_;
761 void (T::*
const method_)(P, Q);
762 const std::string name_;
767template <
class T,
class P,
class Q>
769 void (T::*method)(P, Q),
770 const std::string&
name, P param1,
813template <
class V,
class Val,
class Handler>
827 const int size =
Size();
829 <<
"Assignment contains fewer variables than operator";
830 for (
int i = 0; i < size; ++i) {
903 vars_.insert(
vars_.end(), vars.begin(), vars.end());
953 std::vector<int>* assignment_indices,
int64 index,
958 if (assignment_indices !=
nullptr) {
959 if ((*assignment_indices)[
index] == -1) {
960 (*assignment_indices)[
index] = container->
Size();
998#if defined(SWIGPYTHON)
1000%unignore VarLocalSearchOperator<IntVar,
int64,
1001 IntVarLocalSearchHandler>::Size;
1002%unignore VarLocalSearchOperator<IntVar,
int64,
1003 IntVarLocalSearchHandler>
::Value;
1004%unignore VarLocalSearchOperator<IntVar,
int64,
1005 IntVarLocalSearchHandler>::OldValue;
1006%unignore VarLocalSearchOperator<IntVar,
int64,
1007 IntVarLocalSearchHandler>::SetValue;
1008%feature(
"director") VarLocalSearchOperator<IntVar,
int64,
1009 IntVarLocalSearchHandler>::IsIncremental;
1010%feature("director") VarLocalSearchOperator<IntVar,
int64,
1011 IntVarLocalSearchHandler>::OnStart;
1012%unignore VarLocalSearchOperator<IntVar,
int64,
1013 IntVarLocalSearchHandler>::IsIncremental;
1014%unignore VarLocalSearchOperator<IntVar,
int64,
1015 IntVarLocalSearchHandler>::OnStart;
1020%rename(IntVarLocalSearchOperatorTemplate)
1021 VarLocalSearchOperator<IntVar, int64, IntVarLocalSearchHandler>;
1022%
template(IntVarLocalSearchOperatorTemplate)
1023 VarLocalSearchOperator<IntVar, int64, IntVarLocalSearchHandler>;
1035 bool keep_inverse_values =
false)
1038 max_inverse_value_(keep_inverse_values ? vars.size() - 1 : -1) {
1040 if (keep_inverse_values) {
1041 int64 max_value = -1;
1045 inverse_values_.resize(max_value + 1, -1);
1046 old_inverse_values_.resize(max_value + 1, -1);
1065 virtual bool MakeOneNeighbor();
1069 return index <= max_inverse_value_;
1075 return old_inverse_values_[
index];
1087 const int64 max_inverse_value_;
1088 std::vector<int64> old_inverse_values_;
1089 std::vector<int64> inverse_values_;
1096 if (element->
Var() !=
var) {
1098 <<
"Assignment does not contain operator variable " <<
var;
1127 bool active, std::vector<int>* assignment_indices,
1146 SequenceVar, std::vector<int>, SequenceVarLocalSearchHandler>;
1148 SequenceVar, std::vector<int>, SequenceVarLocalSearchHandler>;
1152typedef VarLocalSearchOperator<SequenceVar, std::vector<int>,
1153 SequenceVarLocalSearchHandler>
1188 std::vector<int>* assignment_indices,
int64 index,
1193 if (assignment_indices !=
nullptr) {
1194 if ((*assignment_indices)[
index] == -1) {
1195 (*assignment_indices)[
index] = container->
Size();
1214 std::vector<int>*
value) {
1218 if (element->
Var() !=
var) {
1220 <<
"Assignment does not contain operator variable " <<
var;
1226 *
value = element_value;
1268 explicit BaseLns(
const std::vector<IntVar*>& vars);
1282 void OnStart()
override;
1283 std::vector<int> fragment_;
1292 explicit ChangeValue(
const std::vector<IntVar*>& vars);
1301 void OnStart()
override;
1335 const std::vector<IntVar*>& path_vars,
int number_of_base_nodes,
1336 bool skip_locally_optimal_paths,
bool accept_path_end_base,
1337 std::function<
int(
int64)> start_empty_path_class);
1340 void Reset()
override;
1382 const int alternative_index = alternative_index_[
BaseNode(i)];
1383 return alternative_index >= 0
1384 ? alternative_sets_[alternative_index][base_alternatives_[i]]
1389 return base_sibling_alternatives_[i];
1394 const int sibling_alternative_index =
1396 return sibling_alternative_index >= 0
1397 ? alternative_sets_[sibling_alternative_index]
1398 [base_sibling_alternatives_[i]]
1404 const std::vector<int64>&
path_starts()
const {
return path_starts_; }
1407 return start_empty_path_class_ !=
nullptr
1493 return !
IsPathEnd(node) && inactives_[node];
1508 const int alternative = alternative_sets_.size();
1509 for (
int64 node : alternative_set) {
1510 DCHECK_EQ(-1, alternative_index_[node]);
1511 alternative_index_[node] = alternative;
1513 alternative_sets_.push_back(alternative_set);
1514 sibling_alternative_.push_back(-1);
1521 const std::vector<std::pair<std::vector<int64>, std::vector<int64>>>&
1522 pair_alternative_sets) {
1523 for (
const auto& pair_alternative_set : pair_alternative_sets) {
1525 sibling_alternative_.back() = alternative + 1;
1531 int64 GetActiveInAlternativeSet(int alternative_index) const {
1532 return alternative_index >= 0
1533 ? active_in_alternative_set_[alternative_index]
1538 return GetActiveInAlternativeSet(alternative_index_[node]);
1542 if (node >= alternative_index_.size())
return -1;
1543 const int alternative = alternative_index_[node];
1544 return alternative >= 0 ? sibling_alternative_[alternative] : -1;
1549 if (node >= alternative_index_.size())
return -1;
1550 const int alternative = alternative_index_[node];
1551 const int sibling_alternative =
1552 alternative >= 0 ? sibling_alternative_[alternative] : -1;
1553 return GetActiveInAlternativeSet(sibling_alternative);
1557 bool CheckChainValidity(
int64 before_chain,
int64 chain_end,
1558 int64 exclude)
const;
1567 void OnStart()
override;
1569 bool OnSamePath(
int64 node1,
int64 node2)
const;
1571 bool CheckEnds()
const {
1572 const int base_node_size = base_nodes_.size();
1573 for (
int i = base_node_size - 1; i >= 0; --i) {
1574 if (base_nodes_[i] != end_nodes_[i]) {
1580 bool IncrementPosition();
1581 void InitializePathStarts();
1582 void InitializeInactives();
1583 void InitializeBaseNodes();
1584 void InitializeAlternatives();
1587 std::vector<int> base_nodes_;
1588 std::vector<int> base_alternatives_;
1589 std::vector<int> base_sibling_alternatives_;
1590 std::vector<int> end_nodes_;
1591 std::vector<int> base_paths_;
1592 std::vector<int64> path_starts_;
1593 std::vector<bool> inactives_;
1596 const bool accept_path_end_base_;
1597 std::function<int(
int64)> start_empty_path_class_;
1598 bool skip_locally_optimal_paths_;
1599 bool optimal_paths_enabled_;
1600 std::vector<int> path_basis_;
1601 std::vector<bool> optimal_paths_;
1604 std::vector<std::vector<int64>> alternative_sets_;
1606 std::vector<int> alternative_index_;
1607 std::vector<int64> active_in_alternative_set_;
1608 std::vector<int> sibling_alternative_;
1614 Solver* solver,
const std::vector<IntVar*>& vars,
1615 const std::vector<IntVar*>& secondary_vars,
1616 std::function<
int(
int64)> start_empty_path_class);
1624class MakeActiveOperator;
1625class MakeInactiveOperator;
1626class MakeChainInactiveOperator;
1627class SwapActiveOperator;
1628class ExtendedSwapActiveOperator;
1629class MakeActiveAndRelocate;
1630class RelocateAndMakeActiveOperator;
1631class RelocateAndMakeInactiveOperator;
1645class LocalSearchVariable;
1661 void RelaxVariableBounds(
int variable_index);
1662 bool TightenVariableMin(
int variable_index,
int64 value);
1663 bool TightenVariableMax(
int variable_index,
int64 value);
1664 int64 VariableMin(
int variable_index)
const;
1665 int64 VariableMax(
int variable_index)
const;
1667 std::vector<Bounds> initial_variable_bounds_;
1668 std::vector<Bounds> variable_bounds_;
1669 std::vector<std::pair<Bounds, int>> saved_variable_bounds_trail_;
1670 std::vector<bool> variable_is_relaxed_;
1671 bool state_is_valid_ =
true;
1681 int64 Min()
const {
return state_->VariableMin(variable_index_); }
1682 int64 Max()
const {
return state_->VariableMax(variable_index_); }
1684 return state_->TightenVariableMin(variable_index_, new_min);
1687 return state_->TightenVariableMax(variable_index_, new_max);
1689 void Relax() { state_->RelaxVariableBounds(variable_index_); }
1696 : state_(state), variable_index_(variable_index) {}
1699 const int variable_index_;
1737 int64 objective_min,
int64 objective_max) = 0;
1774 return "LocalSearchFilterManager";
1791 int64 objective_max);
1798 void InitializeForcedEvents();
1800 std::vector<FilterEvent> filter_events_;
1801 int last_event_called_ = -1;
1806 std::vector<int> next_forced_events_;
1807 int64 synchronized_value_;
1808 int64 accepted_value_;
1817 void Synchronize(
const Assignment* assignment,
1822 const int var_index =
var->index();
1823 *
index = (var_index < var_index_to_index_.size())
1824 ? var_index_to_index_[var_index]
1830 void AddVars(
const std::vector<IntVar*>& vars);
1835 return values_[
index];
1841 void SynchronizeOnAssignment(
const Assignment* assignment);
1844 std::vector<IntVar*>
vars_;
1845 std::vector<int64> values_;
1846 std::vector<bool> var_synced_;
1847 std::vector<int> var_index_to_index_;
1855 std::string
DebugString()
const override {
return "PropagationMonitor"; }
1885 const std::vector<int64>& values) = 0;
1887 const std::vector<int64>& values) = 0;
1908 const std::vector<int>& rank_first,
1909 const std::vector<int>& rank_last,
1910 const std::vector<int>& unperformed) = 0;
1912 void Install()
override;
1920 std::string
DebugString()
const override {
return "LocalSearchMonitor"; }
1931 bool neighbor_found) = 0;
1934 bool neighbor_found) = 0;
1939 void Install()
override;
1947 :
IntVar(s,
name), value_(kUnboundBooleanVarValue) {}
1952 void SetMin(
int64 m)
override;
1954 void SetMax(
int64 m)
override;
1956 bool Bound()
const override {
return (value_ != kUnboundBooleanVarValue); }
1958 CHECK_NE(value_, kUnboundBooleanVarValue) <<
"variable is not bound";
1961 void RemoveValue(
int64 v)
override;
1962 void RemoveInterval(
int64 l,
int64 u)
override;
1963 void WhenBound(
Demon* d)
override;
1966 uint64 Size()
const override;
1967 bool Contains(
int64 v)
const override;
1968 IntVarIterator* MakeHoleIterator(
bool reversible)
const override;
1969 IntVarIterator* MakeDomainIterator(
bool reversible)
const override;
1970 std::string DebugString()
const override;
1975 IntVar* IsGreaterOrEqual(
int64 constant)
override;
1979 std::string
BaseName()
const override {
return "BooleanVar"; }
1997 : symmetry_manager_(nullptr), index_in_symmetry_manager_(-1) {}
2001 void AddIntegerVariableGreaterOrEqualValueClause(
IntVar*
const var,
2008 CHECK(symmetry_manager_ ==
nullptr);
2009 CHECK_EQ(-1, index_in_symmetry_manager_);
2010 symmetry_manager_ = manager;
2011 index_in_symmetry_manager_ =
index;
2013 SymmetryManager* symmetry_manager()
const {
return symmetry_manager_; }
2014 int index_in_symmetry_manager()
const {
return index_in_symmetry_manager_; }
2016 SymmetryManager* symmetry_manager_;
2018 int index_in_symmetry_manager_;
2026 double scaling_factor,
double offset,
2027 std::function<std::string()> display_callback,
2028 bool display_on_new_solutions_only,
int period);
2030 void EnterSearch()
override;
2031 void ExitSearch()
override;
2032 bool AtSolution()
override;
2033 void BeginFail()
override;
2034 void NoMoreSolutions()
override;
2036 void ApplyDecision(
Decision*
const decision)
override;
2037 void RefuteDecision(
Decision*
const decision)
override;
2038 void OutputDecision();
2040 void BeginInitialPropagation()
override;
2041 void EndInitialPropagation()
override;
2042 std::string DebugString()
const override;
2046 virtual void OutputLine(
const std::string& line);
2052 std::unique_ptr<WallTimer> timer_;
2055 const double scaling_factor_;
2057 std::function<std::string()> display_callback_;
2058 const bool display_on_new_solutions_only_;
2061 int64 objective_min_;
2062 int64 objective_max_;
2063 int min_right_depth_;
2065 int sliding_min_depth_;
2066 int sliding_max_depth_;
2076 VOID_FALSE_CONSTRAINT = 0,
2082 VAR_CONSTANT_EQUALITY = 0,
2090 VAR_CONSTANT_CONSTANT_BETWEEN = 0,
2095 EXPR_EXPR_EQUALITY = 0,
2112 EXPR_EXPR_DIFFERENCE = 0,
2126 EXPR_EXPR_CONSTANT_CONDITIONAL = 0,
2131 EXPR_CONSTANT_DIFFERENCE = 0,
2144 VAR_CONSTANT_CONSTANT_SEMI_CONTINUOUS = 0,
2149 VAR_CONSTANT_ARRAY_ELEMENT = 0,
2154 VAR_ARRAY_CONSTANT_ARRAY_SCAL_PROD = 0,
2166 VAR_ARRAY_CONSTANT_INDEX = 0,
2264 IntVar*
const var,
const std::vector<int64>& values,
2269 const std::vector<int64>& values,
2278 const std::vector<IntVar*>& vars,
2284 const std::vector<IntVar*>& vars,
const std::vector<int64>& values,
2288 IntExpr*
const expression,
const std::vector<IntVar*>&
var,
2289 const std::vector<int64>& values,
2295 const std::vector<IntVar*>& vars,
int64 value,
2313 const std::string& TypeName()
const;
2314 void SetTypeName(
const std::string& type_name);
2317 void SetIntegerArgument(
const std::string& arg_name,
int64 value);
2318 void SetIntegerArrayArgument(
const std::string& arg_name,
2319 const std::vector<int64>& values);
2320 void SetIntegerMatrixArgument(
const std::string& arg_name,
2322 void SetIntegerExpressionArgument(
const std::string& arg_name,
2324 void SetIntegerVariableArrayArgument(
const std::string& arg_name,
2325 const std::vector<IntVar*>& vars);
2326 void SetIntervalArgument(
const std::string& arg_name,
IntervalVar*
const var);
2327 void SetIntervalArrayArgument(
const std::string& arg_name,
2328 const std::vector<IntervalVar*>& vars);
2329 void SetSequenceArgument(
const std::string& arg_name,
SequenceVar*
const var);
2330 void SetSequenceArrayArgument(
const std::string& arg_name,
2331 const std::vector<SequenceVar*>& vars);
2334 bool HasIntegerExpressionArgument(
const std::string& arg_name)
const;
2335 bool HasIntegerVariableArrayArgument(
const std::string& arg_name)
const;
2338 int64 FindIntegerArgumentWithDefault(
const std::string& arg_name,
2340 int64 FindIntegerArgumentOrDie(
const std::string& arg_name)
const;
2341 const std::vector<int64>& FindIntegerArrayArgumentOrDie(
2342 const std::string& arg_name)
const;
2343 const IntTupleSet& FindIntegerMatrixArgumentOrDie(
2344 const std::string& arg_name)
const;
2346 IntExpr* FindIntegerExpressionArgumentOrDie(
2347 const std::string& arg_name)
const;
2348 const std::vector<IntVar*>& FindIntegerVariableArrayArgumentOrDie(
2349 const std::string& arg_name)
const;
2352 std::string type_name_;
2353 absl::flat_hash_map<std::string, int64> integer_argument_;
2354 absl::flat_hash_map<std::string, std::vector<int64>> integer_array_argument_;
2355 absl::flat_hash_map<std::string, IntTupleSet> matrix_argument_;
2356 absl::flat_hash_map<std::string, IntExpr*> integer_expression_argument_;
2357 absl::flat_hash_map<std::string, IntervalVar*> interval_argument_;
2358 absl::flat_hash_map<std::string, SequenceVar*> sequence_argument_;
2359 absl::flat_hash_map<std::string, std::vector<IntVar*>>
2360 integer_variable_array_argument_;
2361 absl::flat_hash_map<std::string, std::vector<IntervalVar*>>
2362 interval_array_argument_;
2363 absl::flat_hash_map<std::string, std::vector<SequenceVar*>>
2364 sequence_array_argument_;
2375 void BeginVisitModel(
const std::string& solver_name)
override;
2376 void EndVisitModel(
const std::string& solver_name)
override;
2377 void BeginVisitConstraint(
const std::string& type_name,
2378 const Constraint*
const constraint)
override;
2379 void EndVisitConstraint(
const std::string& type_name,
2380 const Constraint*
const constraint)
override;
2381 void BeginVisitIntegerExpression(
const std::string& type_name,
2382 const IntExpr*
const expr)
override;
2383 void EndVisitIntegerExpression(
const std::string& type_name,
2384 const IntExpr*
const expr)
override;
2385 void VisitIntegerVariable(
const IntVar*
const variable,
2386 IntExpr*
const delegate)
override;
2387 void VisitIntegerVariable(
const IntVar*
const variable,
2389 IntVar*
const delegate)
override;
2390 void VisitIntervalVariable(
const IntervalVar*
const variable,
2393 void VisitSequenceVariable(
const SequenceVar*
const variable)
override;
2395 void VisitIntegerArgument(
const std::string& arg_name,
int64 value)
override;
2396 void VisitIntegerArrayArgument(
const std::string& arg_name,
2397 const std::vector<int64>& values)
override;
2398 void VisitIntegerMatrixArgument(
const std::string& arg_name,
2401 void VisitIntegerExpressionArgument(
const std::string& arg_name,
2402 IntExpr*
const argument)
override;
2403 void VisitIntegerVariableArrayArgument(
2404 const std::string& arg_name,
2405 const std::vector<IntVar*>& arguments)
override;
2407 void VisitIntervalArgument(
const std::string& arg_name,
2409 void VisitIntervalArrayArgument(
2410 const std::string& arg_name,
2411 const std::vector<IntervalVar*>& arguments)
override;
2413 void VisitSequenceArgument(
const std::string& arg_name,
2415 void VisitSequenceArrayArgument(
2416 const std::string& arg_name,
2417 const std::vector<SequenceVar*>& arguments)
override;
2420 void PushArgumentHolder();
2421 void PopArgumentHolder();
2425 std::vector<ArgumentHolder*> holders_;
2432 : index_min_(index_min),
2433 index_max_(index_max),
2434 values_(new T[index_max - index_min + 1]) {
2443 return values_[
index - index_min_];
2452 std::string
DebugString()
const override {
return "ArrayWithOffset"; }
2455 const int64 index_min_;
2456 const int64 index_max_;
2457 std::unique_ptr<T[]> values_;
2465template <
class T,
class C>
2469 : block_size_(block_size), block_offset_(0) {
2474 for (
int i = 0; i < elements_.size(); ++i) {
2475 delete[] elements_[i];
2480 const int64 block_index = ComputeBlockIndex(
index);
2481 const int64 relative_index = block_index - block_offset_;
2482 if (relative_index < 0 || relative_index >= elements_.size()) {
2485 const T* block = elements_[relative_index];
2486 return block !=
nullptr ? block[
index - block_index * block_size_] : T();
2490 const int64 block_index = ComputeBlockIndex(
index);
2491 T*
const block = GetOrCreateBlock(block_index);
2492 const int64 residual =
index - block_index * block_size_;
2494 reinterpret_cast<C
>(
value));
2498 T* NewBlock()
const {
2499 T*
const result =
new T[block_size_];
2500 for (
int i = 0; i < block_size_; ++i) {
2506 T* GetOrCreateBlock(
int block_index) {
2507 if (elements_.size() == 0) {
2508 block_offset_ = block_index;
2509 GrowUp(block_index);
2510 }
else if (block_index < block_offset_) {
2511 GrowDown(block_index);
2512 }
else if (block_index - block_offset_ >= elements_.size()) {
2513 GrowUp(block_index);
2515 T* block = elements_[block_index - block_offset_];
2516 if (block ==
nullptr) {
2518 elements_[block_index - block_offset_] = block;
2525 : (
value - block_size_ + 1) / block_size_;
2528 void GrowUp(
int64 block_index) {
2529 elements_.resize(block_index - block_offset_ + 1);
2532 void GrowDown(
int64 block_index) {
2533 const int64 delta = block_offset_ - block_index;
2534 block_offset_ = block_index;
2536 elements_.insert(elements_.begin(),
delta,
nullptr);
2539 const int64 block_size_;
2540 std::vector<T*> elements_;
2551 static constexpr int kNoInserted = -1;
2559 delete_position_(true) {
2560 for (
int i = 0; i <
capacity; ++i) {
2561 position_[i] = kNoInserted;
2570 position_(shared_positions),
2571 delete_position_(false) {
2572 for (
int i = 0; i < shared_positions_size; ++i) {
2573 position_[i] = kNoInserted;
2578 if (delete_position_) {
2583 int Size()
const {
return num_elements_.Value(); }
2590 return elements_[i];
2595 DCHECK_LT(i + num_elements_.Value(), capacity_);
2596 return elements_[i + num_elements_.Value()];
2600 const int position = num_elements_.Value();
2602 DCHECK(NotAlreadyInserted(elt));
2603 elements_[position] = elt;
2604 position_[elt] = position;
2605 num_elements_.Incr(solver);
2609 num_elements_.Decr(solver);
2610 SwapTo(value_index, num_elements_.Value());
2614 SwapTo(value_index, num_elements_.Value());
2615 num_elements_.Incr(solver);
2618 void Clear(
Solver*
const solver) { num_elements_.SetValue(solver, 0); }
2627 bool NotAlreadyInserted(
const T& elt) {
2628 for (
int i = 0; i < num_elements_.Value(); ++i) {
2629 if (elt == elements_[i]) {
2636 void SwapTo(T value_index,
int next_position) {
2637 const int current_position = position_[value_index];
2638 if (current_position != next_position) {
2639 const T next_value_index = elements_[next_position];
2640 elements_[current_position] = next_value_index;
2641 elements_[next_position] = value_index;
2642 position_[value_index] = next_position;
2643 position_[next_value_index] = current_position;
2648 std::unique_ptr<T[]> elements_;
2650 NumericalRev<int> num_elements_;
2652 const int capacity_;
2656 const bool delete_position_;
2666 last_ranked_(items.size() - 1),
2667 size_(items.size()),
2668 position_(new int[size_]) {
2669 for (
int i = 0; i < size_; ++i) {
2670 elements_[i] = items[i];
2678 last_ranked_(size - 1),
2680 position_(new int[size_]) {
2681 for (
int i = 0; i < size_; ++i) {
2699 return elements_[
index];
2704 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
2705 SwapTo(elt, first_ranked_.Value());
2706 first_ranked_.Incr(solver);
2710 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());
2711 SwapTo(elt, last_ranked_.Value());
2712 last_ranked_.Decr(solver);
2716 const int position = position_[elt];
2717 return (position < first_ranked_.Value() ||
2718 position > last_ranked_.Value());
2722 std::string result =
"[";
2723 for (
int i = 0; i < first_ranked_.Value(); ++i) {
2724 absl::StrAppend(&result, elements_[i]);
2725 if (i != first_ranked_.Value() - 1) {
2730 for (
int i = first_ranked_.Value(); i <= last_ranked_.Value(); ++i) {
2731 absl::StrAppend(&result, elements_[i]);
2732 if (i != last_ranked_.Value()) {
2737 for (
int i = last_ranked_.Value() + 1; i < size_; ++i) {
2738 absl::StrAppend(&result, elements_[i]);
2739 if (i != size_ - 1) {
2748 void SwapTo(
int elt,
int next_position) {
2749 const int current_position = position_[elt];
2750 if (current_position != next_position) {
2751 const int next_elt = elements_[next_position];
2752 elements_[current_position] = next_elt;
2753 elements_[next_position] = elt;
2754 position_[elt] = next_position;
2755 position_[next_elt] = current_position;
2760 std::vector<int> elements_;
2762 NumericalRev<int> first_ranked_;
2764 NumericalRev<int> last_ranked_;
2768 std::unique_ptr<int[]> position_;
2784 void Init(
Solver*
const solver,
const std::vector<uint64>& mask);
2788 bool RevSubtract(
Solver*
const solver,
const std::vector<uint64>& mask);
2792 bool RevAnd(
Solver*
const solver,
const std::vector<uint64>& mask);
2799 bool Empty()
const {
return active_words_.Size() == 0; }
2808 bool Intersects(
const std::vector<uint64>& mask,
int* support_index);
2818 void CleanUpActives(
Solver*
const solver);
2820 const int64 bit_size_;
2821 const int64 word_size_;
2829 for (
int i = 0; i < values.size(); ++i) {
2830 if (values[i] !=
value) {
2839 for (
int i = 0; i < values.size(); ++i) {
2840 if (values[i] != 0 && values[i] != 1) {
2859 for (
const T& current_value : values) {
2860 if (current_value <
value) {
2869 for (
const T& current_value : values) {
2870 if (current_value >
value) {
2899 for (
int i = 0; i < values.size() - 1; ++i) {
2900 if (values[i + 1] != values[i] + 1) {
2909 for (
int i = 0; i < values.size() - 1; ++i) {
2910 if (values[i + 1] < values[i]) {
2920 for (
int i = 0; i < vars.size(); ++i) {
2921 if (vars[i]->Min() < range_min || vars[i]->Max() > range_max) {
2929 for (
int i = 0; i < vars.size(); ++i) {
2930 if (!vars[i]->Bound()) {
2945 const std::vector<T>& values) {
2946 for (
int i = 0; i < vars.size(); ++i) {
2947 if (values[i] != 0 && !vars[i]->Bound()) {
2956 for (
int i = 0; i < vars.size(); ++i) {
2957 if (!vars[i]->Bound() || vars[i]->Min() !=
value) {
2967 for (
int i = 0; i < vars.size(); ++i) {
2969 result = std::max<int64>(result, vars[i]->Max());
2977 for (
int i = 0; i < vars.size(); ++i) {
2979 result = std::min<int64>(result, vars[i]->Min());
2985 std::vector<int64>*
const values) {
2987 values->resize(vars.size());
2988 for (
int i = 0; i < vars.size(); ++i) {
2989 (*values)[i] = vars[i]->Value();
2995 return (e < 0 || e % v == 0) ? e / v : e / v + 1;
3000 return (e >= 0 || e % v == 0) ? e / v : e / v - 1;
3065 PathState(
int num_nodes, std::vector<int> path_start,
3066 std::vector<int> path_end);
3075 int Start(
int path)
const {
return path_start_end_[path].start; }
3077 int End(
int path)
const {
return path_start_end_[path].end; }
3083 return committed_nodes_[committed_index_[node]].path;
3088 return changed_arcs_;
3094 ChainRange Chains(
int path)
const;
3096 NodeRange Nodes(
int path)
const;
3103 changed_arcs_.emplace_back(node, new_next);
3124 struct PathStartEnd {
3125 PathStartEnd(
int start,
int end) : start(start), end(end) {}
3134 struct ChainBounds {
3135 ChainBounds() =
default;
3136 ChainBounds(
int begin_index,
int end_index)
3137 : begin_index(begin_index), end_index(end_index) {}
3141 struct CommittedNode {
3142 CommittedNode(
int node,
int path) : node(node), path(path) {}
3150 struct TailHeadIndices {
3157 bool operator<(
const IndexArc& other)
const {
return index < other.index; }
3162 void MakeChainsFromChangedPathsAndArcsWithSelectionAlgorithm();
3165 void MakeChainsFromChangedPathsAndArcsWithGenericAlgorithm();
3169 void CopyNewPathAtEndOfNodes(
int path);
3172 void IncrementalCommit();
3178 const int num_nodes_;
3179 const int num_paths_;
3180 std::vector<PathStartEnd> path_start_end_;
3207 std::vector<CommittedNode> committed_nodes_;
3208 std::vector<int> committed_index_;
3209 const int num_nodes_threshold_;
3210 std::vector<ChainBounds> chains_;
3211 std::vector<PathBounds> paths_;
3215 std::vector<std::pair<int, int>> changed_arcs_;
3216 std::vector<int> changed_paths_;
3217 std::vector<bool> path_has_changed_;
3221 std::vector<TailHeadIndices> tail_head_indices_;
3222 std::vector<IndexArc> arcs_by_tail_index_;
3223 std::vector<IndexArc> arcs_by_head_index_;
3224 std::vector<int> next_arc_;
3227 bool is_invalid_ =
false;
3241 return current_node_ != other.current_node_;
3247 explicit Iterator(
const CommittedNode* node) : current_node_(node) {}
3248 const CommittedNode* current_node_;
3253 Chain(
const CommittedNode* begin_node,
const CommittedNode* end_node)
3254 : begin_(begin_node), end_(end_node) {}
3257 int First()
const {
return begin_->node; }
3258 int Last()
const {
return (end_ - 1)->node; }
3263 const CommittedNode*
const begin_;
3264 const CommittedNode*
const end_;
3277 return {first_node_ + current_chain_->begin_index,
3278 first_node_ + current_chain_->end_index};
3281 return current_chain_ != other.current_chain_;
3287 Iterator(
const ChainBounds* chain,
const CommittedNode*
const first_node)
3288 : current_chain_(chain), first_node_(first_node) {}
3289 const ChainBounds* current_chain_;
3290 const CommittedNode*
const first_node_;
3296 const ChainBounds*
const end_chain,
3297 const CommittedNode*
const first_node)
3298 : begin_(begin_chain), end_(end_chain), first_node_(first_node) {}
3304 const ChainBounds*
const begin_;
3305 const ChainBounds*
const end_;
3306 const CommittedNode*
const first_node_;
3317 if (current_node_ == end_node_) {
3321 const ChainBounds
bounds = *current_chain_;
3322 current_node_ = first_node_ +
bounds.begin_index;
3323 end_node_ = first_node_ +
bounds.end_index;
3329 return current_chain_ != other.current_chain_;
3335 Iterator(
const ChainBounds* current_chain,
3336 const CommittedNode*
const first_node)
3337 : current_node_(first_node + current_chain->begin_index),
3338 end_node_(first_node + current_chain->end_index),
3339 current_chain_(current_chain),
3340 first_node_(first_node) {}
3341 const CommittedNode* current_node_;
3342 const CommittedNode* end_node_;
3343 const ChainBounds* current_chain_;
3344 const CommittedNode*
const first_node_;
3349 NodeRange(
const ChainBounds* begin_chain,
const ChainBounds* end_chain,
3350 const CommittedNode* first_node)
3351 : begin_chain_(begin_chain),
3352 end_chain_(end_chain),
3353 first_node_(first_node) {}
3360 const ChainBounds* begin_chain_;
3361 const ChainBounds* end_chain_;
3362 const CommittedNode*
const first_node_;
3387 std::vector<Interval> path_capacity,
3388 std::vector<int> path_class,
3389 std::vector<std::vector<Interval>>
demand,
3390 std::vector<Interval> node_capacity);
3406 Interval GetMinMaxPartialDemandSum(
int first_node_index,
3407 int last_node_index)
const;
3413 bool SubpathOnlyHasTrivialNodes(
int first_node_index,
3414 int last_node_index)
const;
3420 void IncrementalCommit();
3423 void AppendPathDemandsToSums(
int path);
3429 void UpdateRMQStructure(
int begin_index,
int end_index);
3432 const std::vector<Interval> path_capacity_;
3433 const std::vector<int> path_class_;
3434 const std::vector<std::vector<Interval>> demand_;
3435 const std::vector<Interval> node_capacity_;
3441 std::vector<int> index_;
3451 std::vector<std::vector<Interval>> partial_demand_sums_rmq_;
3454 const int maximum_partial_demand_layer_size_;
3459 std::vector<int> previous_nontrivial_index_;
3468 std::unique_ptr<PathState> path_state,
3469 const std::vector<IntVar*>& nexts);
3479 Solver* solver, std::unique_ptr<UnaryDimensionChecker> checker);
const std::vector< IntVar * > vars_
#define DCHECK_LE(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK_GE(val1, val2)
#define CHECK_NE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define CHECK_LE(val1, val2)
#define DCHECK_EQ(val1, val2)
int64 MemoryUsage(int unused)
Argument Holder: useful when visiting a model.
ArrayWithOffset(int64 index_min, int64 index_max)
virtual T Evaluate(int64 index) const
~ArrayWithOffset() override
void SetValue(int64 index, T value)
std::string DebugString() const override
bool Contains(const V *const var) const
const E & Element(const V *const var) const
E * MutableElement(const V *const var)
An Assignment is a variable -> domains mapping, used to report solutions to the user.
SequenceContainer * MutableSequenceVarContainer()
const SequenceContainer & SequenceVarContainer() const
IntContainer * MutableIntVarContainer()
const IntContainer & IntVarContainer() const
IntVarElement * FastAdd(IntVar *const var)
Adds without checking if variable has been previously added.
This is the base class for all expressions that are not variables.
BaseIntExpr(Solver *const s)
virtual IntVar * CastToVar()
IntVar * Var() override
Creates a variable from the expression.
This is the base class for building an Lns operator.
virtual bool NextFragment()=0
bool HasFragments() const override
void AppendToFragment(int index)
BaseLns(const std::vector< IntVar * > &vars)
bool MakeOneNeighbor() override
This method should not be overridden. Override NextFragment() instead.
virtual void InitFragments()
A BaseObject is the root of all reversibly allocated objects.
void SetContentFromBitsetOfSameSize(const Bitset64< OtherIndexType > &other)
void Resize(IndexType size)
void CopyBucket(const Bitset64< IndexType > &other, IndexType i)
int VarType() const override
virtual void RestoreValue()=0
bool Bound() const override
Returns true if the min and the max of the expression are equal.
void WhenRange(Demon *d) override
Attach a demon that will watch the min or the max of the expression.
SimpleRevFIFO< Demon * > delayed_bound_demons_
int64 Value() const override
This method returns the value of the variable.
void WhenDomain(Demon *d) override
This method attaches a demon that will watch any domain modification of the domain of the variable.
int64 Min() const override
static const int kUnboundBooleanVarValue
SimpleRevFIFO< Demon * > bound_demons_
std::string BaseName() const override
Returns a base name for automatic naming.
BooleanVar(Solver *const s, const std::string &name="")
int64 Max() const override
Demon proxy to a method on the constraint with no arguments.
CallMethod0(T *const ct, void(T::*method)(), const std::string &name)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
Demon proxy to a method on the constraint with one argument.
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
CallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)
Demon proxy to a method on the constraint with two arguments.
CallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
Demon proxy to a method on the constraint with three arguments.
CallMethod3(T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
Defines operators which change the value of variables; each neighbor corresponds to one modified vari...
ChangeValue(const std::vector< IntVar * > &vars)
virtual int64 ModifyValue(int64 index, int64 value)=0
bool MakeOneNeighbor() override
This method should not be overridden. Override ModifyValue() instead.
A constraint is the main modeling object.
A Decision represents a choice point in the search tree.
A DecisionVisitor is used to inspect a decision.
Low-priority demon proxy to a method on the constraint with no arguments.
Solver::DemonPriority priority() const override
This method returns the priority of the demon.
~DelayedCallMethod0() override
void Run(Solver *const s) override
This is the main callback of the demon.
DelayedCallMethod0(T *const ct, void(T::*method)(), const std::string &name)
std::string DebugString() const override
Low-priority demon proxy to a method on the constraint with one argument.
Solver::DemonPriority priority() const override
This method returns the priority of the demon.
DelayedCallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
~DelayedCallMethod1() override
Low-priority demon proxy to a method on the constraint with two arguments.
Solver::DemonPriority priority() const override
This method returns the priority of the demon.
~DelayedCallMethod2() override
DelayedCallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
void Run(Solver *const s) override
This is the main callback of the demon.
std::string DebugString() const override
A Demon is the base element of a propagation queue.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual int64 Max() const =0
The class IntVar is a subset of IntExpr.
The class Iterator has two direct subclasses.
virtual void OnSynchronize(const Assignment *delta)
bool FindIndex(IntVar *const var, int64 *index) const
IntVar * Var(int index) const
int64 Value(int index) const
bool IsVarSynced(int index) const
void OnRevertChanges(int64 index, int64 value)
IntVarLocalSearchHandler()
IntVarLocalSearchHandler(const IntVarLocalSearchHandler &other)
bool ValueFromAssignment(const Assignment &assignment, IntVar *var, int64 index, int64 *value)
IntVarLocalSearchHandler(IntVarLocalSearchOperator *op)
void AddToAssignment(IntVar *var, int64 value, bool active, std::vector< int > *assignment_indices, int64 index, Assignment *assignment) const
Specialization of LocalSearchOperator built from an array of IntVars which specifies the scope of the...
int64 InverseValue(int64 index) const
void SetOldInverseValue(int64 index, int64 value)
void SetInverseValue(int64 index, int64 value)
friend class IntVarLocalSearchHandler
~IntVarLocalSearchOperator() override
bool IsInverseValue(int64 index) const
IntVarLocalSearchOperator()
IntVarLocalSearchOperator(const std::vector< IntVar * > &vars, bool keep_inverse_values=false)
int64 OldInverseValue(int64 index) const
Interval variables are often used in scheduling.
Local Search Filters are used for fast neighbor pruning.
virtual void Synchronize(const Assignment *assignment, const Assignment *delta)=0
Synchronizes the filter with the current solution, delta being the difference with the solution passe...
virtual int64 GetSynchronizedObjectiveValue() const
Objective value from last time Synchronize() was called.
virtual bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max)=0
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
virtual void Reset()
Sets the filter to empty solution.
virtual void Relax(const Assignment *delta, const Assignment *deltadelta)
Lets the filter know what delta and deltadelta will be passed in the next Accept().
virtual bool IsIncremental() const
virtual void Revert()
Cancels the changes made by the last Relax()/Accept() calls.
virtual void Commit(const Assignment *delta, const Assignment *deltadelta)
Dual of Relax(), lets the filter know that the delta was accepted.
virtual int64 GetAcceptedObjectiveValue() const
Objective value from the last time Accept() was called and returned true.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
int64 GetSynchronizedObjectiveValue() const
int64 GetAcceptedObjectiveValue() const
std::string DebugString() const override
virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0
virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
virtual void EndOperatorStart()=0
virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0
virtual void BeginOperatorStart()=0
Local search operator events.
virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0
virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0
virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0
virtual void BeginFiltering(const LocalSearchFilter *filter)=0
virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0
std::string DebugString() const override
The base class for all local search operators.
virtual bool HasFragments() const
virtual bool HoldsDelta() const
virtual const LocalSearchOperator * Self() const
virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0
virtual void Start(const Assignment *assignment)=0
~LocalSearchOperator() override
bool StateIsValid() const
bool SetMax(int64 new_max)
bool SetMin(int64 new_min)
Implements a complete cache for model elements: expressions and constraints.
virtual IntExpr * FindVarArrayExpression(const std::vector< IntVar * > &vars, VarArrayExpressionType type) const =0
Var Array Expressions.
virtual IntExpr * FindVarConstantArrayExpression(IntVar *const var, const std::vector< int64 > &values, VarConstantArrayExpressionType type) const =0
Var Constant Array Expressions.
ExprConstantExpressionType
@ EXPR_CONSTANT_EXPRESSION_MAX
@ EXPR_CONSTANT_IS_GREATER_OR_EQUAL
@ EXPR_CONSTANT_IS_NOT_EQUAL
@ EXPR_CONSTANT_IS_LESS_OR_EQUAL
virtual Constraint * FindVarConstantConstraint(IntVar *const var, int64 value, VarConstantConstraintType type) const =0
Var Constant Constraints.
VarConstantConstraintType
@ VAR_CONSTANT_GREATER_OR_EQUAL
@ VAR_CONSTANT_NON_EQUALITY
@ VAR_CONSTANT_CONSTRAINT_MAX
@ VAR_CONSTANT_LESS_OR_EQUAL
virtual void InsertExprConstantExpression(IntExpr *const expression, IntExpr *const var, int64 value, ExprConstantExpressionType type)=0
virtual void InsertVarConstantConstantConstraint(Constraint *const ct, IntVar *const var, int64 value1, int64 value2, VarConstantConstantConstraintType type)=0
virtual IntExpr * FindExprExpression(IntExpr *const expr, ExprExpressionType type) const =0
Expr Expressions.
virtual IntExpr * FindVarArrayConstantExpression(const std::vector< IntVar * > &vars, int64 value, VarArrayConstantExpressionType type) const =0
Var Array Constant Expressions.
virtual void InsertExprExprExpression(IntExpr *const expression, IntExpr *const var1, IntExpr *const var2, ExprExprExpressionType type)=0
VarArrayConstantArrayExpressionType
@ VAR_ARRAY_CONSTANT_ARRAY_EXPRESSION_MAX
virtual void InsertVarConstantConstraint(Constraint *const ct, IntVar *const var, int64 value, VarConstantConstraintType type)=0
VarConstantConstantExpressionType
@ VAR_CONSTANT_CONSTANT_EXPRESSION_MAX
virtual IntExpr * FindVarArrayConstantArrayExpression(const std::vector< IntVar * > &vars, const std::vector< int64 > &values, VarArrayConstantArrayExpressionType type) const =0
Var Array Constant Array Expressions.
VarConstantConstantConstraintType
@ VAR_CONSTANT_CONSTANT_CONSTRAINT_MAX
virtual void InsertVarArrayConstantExpression(IntExpr *const expression, const std::vector< IntVar * > &var, int64 value, VarArrayConstantExpressionType type)=0
virtual IntExpr * FindExprExprConstantExpression(IntExpr *const var1, IntExpr *const var2, int64 constant, ExprExprConstantExpressionType type) const =0
Expr Expr Constant Expressions.
virtual void InsertVoidConstraint(Constraint *const ct, VoidConstraintType type)=0
@ EXPR_EXPR_EXPRESSION_MAX
@ EXPR_EXPR_IS_LESS_OR_EQUAL
virtual void InsertExprExprConstantExpression(IntExpr *const expression, IntExpr *const var1, IntExpr *const var2, int64 constant, ExprExprConstantExpressionType type)=0
@ EXPR_EXPR_GREATER_OR_EQUAL
@ EXPR_EXPR_CONSTRAINT_MAX
@ EXPR_EXPR_LESS_OR_EQUAL
virtual void InsertVarArrayExpression(IntExpr *const expression, const std::vector< IntVar * > &vars, VarArrayExpressionType type)=0
virtual IntExpr * FindVarConstantConstantExpression(IntVar *const var, int64 value1, int64 value2, VarConstantConstantExpressionType type) const =0
Var Constant Constant Expressions.
virtual Constraint * FindVoidConstraint(VoidConstraintType type) const =0
Void constraints.
virtual void InsertVarArrayConstantArrayExpression(IntExpr *const expression, const std::vector< IntVar * > &var, const std::vector< int64 > &values, VarArrayConstantArrayExpressionType type)=0
virtual void InsertVarConstantConstantExpression(IntExpr *const expression, IntVar *const var, int64 value1, int64 value2, VarConstantConstantExpressionType type)=0
ExprExprConstantExpressionType
@ EXPR_EXPR_CONSTANT_EXPRESSION_MAX
virtual IntExpr * FindExprConstantExpression(IntExpr *const expr, int64 value, ExprConstantExpressionType type) const =0
Expr Constant Expressions.
VarArrayConstantExpressionType
@ VAR_ARRAY_CONSTANT_EXPRESSION_MAX
@ VAR_ARRAY_EXPRESSION_MAX
virtual IntExpr * FindExprExprExpression(IntExpr *const var1, IntExpr *const var2, ExprExprExpressionType type) const =0
Expr Expr Expressions.
VarConstantArrayExpressionType
@ VAR_CONSTANT_ARRAY_EXPRESSION_MAX
virtual Constraint * FindVarConstantConstantConstraint(IntVar *const var, int64 value1, int64 value2, VarConstantConstantConstraintType type) const =0
Var Constant Constant Constraints.
virtual Constraint * FindExprExprConstraint(IntExpr *const expr1, IntExpr *const expr2, ExprExprConstraintType type) const =0
Expr Expr Constraints.
virtual void InsertVarConstantArrayExpression(IntExpr *const expression, IntVar *const var, const std::vector< int64 > &values, VarConstantArrayExpressionType type)=0
virtual void InsertExprExpression(IntExpr *const expression, IntExpr *const expr, ExprExpressionType type)=0
virtual void InsertExprExprConstraint(Constraint *const ct, IntExpr *const expr1, IntExpr *const expr2, ExprExprConstraintType type)=0
void Decr(Solver *const s)
void Incr(Solver *const s)
This class encapsulates an objective.
Base class of the local search operators dedicated to path modifications (a path is a set of nodes li...
int64 BaseAlternativeNode(int i) const
Returns the alternative node for the ith base node.
void AddPairAlternativeSets(const std::vector< std::pair< std::vector< int64 >, std::vector< int64 > > > &pair_alternative_sets)
Adds all sets of node alternatives of a vector of alternative pairs.
virtual bool MakeNeighbor()=0
bool SwapActiveAndInactive(int64 active, int64 inactive)
Replaces active by inactive in the current path, making active inactive.
int PathClass(int i) const
Returns the class of the path of the ith base node.
virtual void OnNodeInitialization()
Called by OnStart() after initializing node information.
int64 BaseNode(int i) const
Returns the ith base node of the operator.
bool IsInactive(int64 node) const
Returns true if node is inactive.
int number_of_nexts() const
Number of next variables.
bool IsPathEnd(int64 node) const
Returns true if node is the last node on the path; defined by the fact that node is outside the range...
virtual void SetNextBaseToIncrement(int64 base_index)
Set the next base to increment on next iteration.
virtual bool ConsiderAlternatives(int64 base_index) const
Indicates if alternatives should be considered when iterating over base nodes.
virtual bool RestartAtPathStartOnSynchronize()
When the operator is being synchronized with a new solution (when Start() is called),...
int64 OldPath(int64 node) const
std::vector< int64 > start_to_path_
const std::vector< int64 > & path_starts() const
Returns the vector of path start nodes.
int BaseSiblingAlternative(int i) const
Returns the alternative for the sibling of the ith base node.
bool ReverseChain(int64 before_chain, int64 after_chain, int64 *chain_last)
Reverses the chain starting after before_chain and ending before after_chain.
int64 OldNext(int64 node) const
int BaseAlternative(int i) const
Returns the alternative for the ith base node.
void SetNext(int64 from, int64 to, int64 path)
Sets 'to' to be the node after 'from' on the given path.
bool MakeActive(int64 node, int64 destination)
Insert the inactive node after destination.
int AddAlternativeSet(const std::vector< int64 > &alternative_set)
Handling node alternatives.
int64 Prev(int64 node) const
Returns the node before node in the current delta.
int64 GetActiveAlternativeNode(int node) const
Returns the active node in the alternative set of the given node.
int64 StartNode(int i) const
Returns the start node of the ith base node.
bool SkipUnchanged(int index) const override
int64 Next(int64 node) const
Returns the node after node in the current delta.
const int number_of_nexts_
void ResetPosition()
Reset the position of the operator to its position when Start() was last called; this can be used to ...
bool IsPathStart(int64 node) const
Returns true if node is the first node on the path.
int64 BaseSiblingAlternativeNode(int i) const
Returns the alternative node for the sibling of the ith base node.
int next_base_to_increment_
virtual int64 GetBaseNodeRestartPosition(int base_index)
Returns the index of the node to which the base node of index base_index must be set to when it reach...
int GetSiblingAlternativeIndex(int node) const
Returns the index of the alternative set of the sibling of node.
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
virtual bool OnSamePathAsPreviousBase(int64 base_index)
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
bool MakeChainInactive(int64 before_chain, int64 chain_end)
Makes the nodes on the chain starting after before_chain and ending at chain_end inactive.
virtual bool InitPosition() const
Returns true if the operator needs to restart its initial position at each call to Start()
int64 Path(int64 node) const
Returns the index of the path to which node belongs in the current delta.
const bool ignore_path_vars_
int64 OldPrev(int64 node) const
int64 GetActiveAlternativeSibling(int node) const
Returns the active node in the alternative set of the sibling of the given node.
PathOperator(const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, int number_of_base_nodes, bool skip_locally_optimal_paths, bool accept_path_end_base, std::function< int(int64)> start_empty_path_class)
Builds an instance of PathOperator from next and path variables.
bool MoveChain(int64 before_chain, int64 chain_end, int64 destination)
Moves the chain starting after the node before_chain and ending at the node chain_end after the node ...
bool operator!=(Iterator other) const
Chain(const CommittedNode *begin_node, const CommittedNode *end_node)
bool operator!=(Iterator other) const
ChainRange(const ChainBounds *const begin_chain, const ChainBounds *const end_chain, const CommittedNode *const first_node)
bool operator!=(Iterator other) const
NodeRange(const ChainBounds *begin_chain, const ChainBounds *end_chain, const CommittedNode *first_node)
const std::vector< int > & ChangedPaths() const
const std::vector< std::pair< int, int > > & ChangedArcs() const
int Start(int path) const
void ChangeNext(int node, int new_next)
virtual void SetMin(IntVar *const var, int64 new_min)=0
IntVar modifiers.
virtual void RankLast(SequenceVar *const var, int index)=0
virtual void SetEndMin(IntervalVar *const var, int64 new_min)=0
virtual void EndConstraintInitialPropagation(Constraint *const constraint)=0
virtual void SetValues(IntVar *const var, const std::vector< int64 > &values)=0
virtual void SetRange(IntVar *const var, int64 new_min, int64 new_max)=0
virtual void SetMax(IntVar *const var, int64 new_max)=0
virtual void RemoveValue(IntVar *const var, int64 value)=0
virtual void SetEndMax(IntervalVar *const var, int64 new_max)=0
virtual void RankNotLast(SequenceVar *const var, int index)=0
virtual void RankNotFirst(SequenceVar *const var, int index)=0
virtual void BeginDemonRun(Demon *const demon)=0
virtual void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)=0
virtual void PushContext(const std::string &context)=0
virtual void RemoveInterval(IntVar *const var, int64 imin, int64 imax)=0
virtual void RemoveValues(IntVar *const var, const std::vector< int64 > &values)=0
virtual void SetStartMin(IntervalVar *const var, int64 new_min)=0
IntervalVar modifiers.
virtual void SetValue(IntVar *const var, int64 value)=0
virtual void SetStartRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
virtual void BeginNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
virtual void EndNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested)=0
virtual void SetRange(IntExpr *const expr, int64 new_min, int64 new_max)=0
virtual void SetPerformed(IntervalVar *const var, bool value)=0
virtual void StartProcessingIntegerVariable(IntVar *const var)=0
virtual void SetDurationRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
virtual void BeginConstraintInitialPropagation(Constraint *const constraint)=0
Propagation events.
virtual void SetDurationMin(IntervalVar *const var, int64 new_min)=0
virtual void SetMax(IntExpr *const expr, int64 new_max)=0
virtual void SetStartMax(IntervalVar *const var, int64 new_max)=0
virtual void EndDemonRun(Demon *const demon)=0
virtual void RegisterDemon(Demon *const demon)=0
virtual void EndProcessingIntegerVariable(IntVar *const var)=0
virtual void PopContext()=0
virtual void SetDurationMax(IntervalVar *const var, int64 new_max)=0
virtual void SetMin(IntExpr *const expr, int64 new_min)=0
IntExpr modifiers.
std::string DebugString() const override
virtual void RankFirst(SequenceVar *const var, int index)=0
SequenceVar modifiers.
virtual void SetEndRange(IntervalVar *const var, int64 new_min, int64 new_max)=0
Matrix version of the RevBitSet class.
bool IsSet(int64 row, int64 column) const
Returns whether the 'column' bit in the 'row' row is set.
int64 GetFirstBit(int row, int start) const
Returns the first bit in the row 'row' which position is >= 'start'.
void SetToOne(Solver *const solver, int64 row, int64 column)
Sets the 'column' bit in the 'row' row.
void ClearAll(Solver *const solver)
Cleans all bits.
void SetToZero(Solver *const solver, int64 row, int64 column)
Erases the 'column' bit in the 'row' row.
This class represents a reversible bitset.
bool IsCardinalityOne() const
Does it contains only one bit set?
bool IsSet(int64 index) const
Returns whether the 'index' bit is set.
void SetToOne(Solver *const solver, int64 index)
Sets the 'index' bit.
int64 GetFirstBit(int start) const
Gets the index of the first bit set starting from start.
void ClearAll(Solver *const solver)
Cleans all bits.
friend class RevBitMatrix
bool IsCardinalityZero() const
Is bitset null?
int64 Cardinality() const
Returns the number of bits set to one.
void SetToZero(Solver *const solver, int64 index)
Erases the 'index' bit.
This class is a reversible growing array.
void RevInsert(Solver *const solver, int64 index, T value)
RevGrowingArray(int64 block_size)
void SetValue(Solver *const s, const T &val)
Reversible Immutable MultiMap class.
void Insert(const K &key, const V &value)
Inserts (key, value) in the multi-map.
RevImmutableMultiMap(Solver *const solver, int initial_size)
const V & FindWithDefault(const K &key, const V &default_value) const
Returns one value attached to 'key', or 'default_value' if 'key' is not in the multi-map.
bool ContainsKey(const K &key) const
Returns true if the multi-map contains at least one instance of 'key'.
This is a special class to represent a 'residual' set of T.
void Insert(Solver *const solver, const T &elt)
RevIntSet(int capacity)
Capacity is the fixed size of the set (it cannot grow).
const_iterator begin() const
const T * const_iterator
Iterators on the indices.
T RemovedElement(int i) const
RevIntSet(int capacity, int *shared_positions, int shared_positions_size)
Capacity is the fixed size of the set (it cannot grow).
void Restore(Solver *const solver, const T &value_index)
const_iterator end() const
void Remove(Solver *const solver, const T &value_index)
void Clear(Solver *const solver)
--— RevPartialSequence --—
int NumLastRanked() const
RevPartialSequence(int size)
int NumFirstRanked() const
bool IsRanked(int elt) const
std::string DebugString() const
void RankLast(Solver *const solver, int elt)
const int & operator[](int index) const
void RankFirst(Solver *const solver, int elt)
RevPartialSequence(const std::vector< int > &items)
A reversible switch that can switch once from false to true.
void Switch(Solver *const solver)
The base class of all search logs that periodically outputs information when the search is running.
A search monitor is a simple set of callbacks to monitor all search events.
The SequenceVarElement stores a partial representation of ranked interval variables in the underlying...
void SetBackwardSequence(const std::vector< int > &backward_sequence)
const std::vector< int > & ForwardSequence() const
void SetForwardSequence(const std::vector< int > &forward_sequence)
SequenceVar * Var() const
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
SequenceVarLocalSearchHandler(const SequenceVarLocalSearchHandler &other)
SequenceVarLocalSearchHandler()
SequenceVarLocalSearchHandler(SequenceVarLocalSearchOperator *op)
bool ValueFromAssignment(const Assignment &assignment, SequenceVar *var, int64 index, std::vector< int > *value)
void OnRevertChanges(int64 index, const std::vector< int > &value)
void AddToAssignment(SequenceVar *var, const std::vector< int > &value, bool active, std::vector< int > *assignment_indices, int64 index, Assignment *assignment) const
~SequenceVarLocalSearchOperator() override
const std::vector< int > & Sequence(int64 index) const
Returns the value in the current assignment of the variable of given index.
const std::vector< int > & OldSequence(int64 index) const
std::vector< std::vector< int > > backward_values_
void SetBackwardSequence(int64 index, const std::vector< int > &value)
SequenceVarLocalSearchOperator(const std::vector< SequenceVar * > &vars)
void SetForwardSequence(int64 index, const std::vector< int > &value)
SequenceVarLocalSearchOperator()
This iterator is not stable with respect to deletion.
Iterator(const SimpleRevFIFO< T > *l)
This class represent a reversible FIFO structure.
void SetLastValue(const T &v)
Sets the last value in the FIFO.
const T * Last() const
Returns the last item of the FIFO.
const T & LastValue() const
Returns the last value in the FIFO.
void PushIfNotTop(Solver *const s, T val)
Pushes the var on top if is not a duplicate of the current top object.
void Push(Solver *const s, T val)
This class represents a small reversible bitset (size <= 64).
void SetToZero(Solver *const solver, int64 pos)
Erases the 'pos' bit.
bool IsCardinalityOne() const
Does it contains only one bit set?
void SetToOne(Solver *const solver, int64 pos)
Sets the 'pos' bit.
int64 GetFirstOne() const
Gets the index of the first bit set starting from 0.
bool IsCardinalityZero() const
Is bitset null?
SmallRevBitSet(int64 size)
int64 Cardinality() const
Returns the number of bits set to one.
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
T * RevAlloc(T *object)
Registers the given object as being reversible.
void Set(IntegerType index)
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
void ClearAndResize(IntegerType size)
A symmetry breaker is an object that will visit a decision and create the 'symmetrical' decision in r...
~SymmetryBreaker() override
This class represents a reversible bitset.
int64 word_size() const
Returns the number of 64 bit words used to store the bitset.
~UnsortedNullableRevBitset()
const RevIntSet< int > & active_words() const
Returns the set of active word indices.
int64 bit_size() const
Returns the number of bits given in the constructor of the bitset.
bool Empty() const
This method returns true if the active bitset is null.
int ActiveWordSize() const
This method returns the number of non null 64 bit words in the bitset representation.
Base operator class for operators manipulating variables.
void RevertChanges(bool incremental)
std::vector< Val > old_values_
virtual bool SkipUnchanged(int index) const
bool HoldsDelta() const override
std::vector< Val > values_
V * Var(int64 index) const
Returns the variable of given index.
const Val & OldValue(int64 index) const
SparseBitset delta_changes_
std::vector< Val > prev_values_
std::vector< int > assignment_indices_
void MarkChange(int64 index)
OnStart() should really be protected, but then SWIG doesn't see it.
virtual bool IsIncremental() const
bool ApplyChanges(Assignment *delta, Assignment *deltadelta) const
VarLocalSearchOperator(Handler var_handler)
virtual void OnStart()
Called by Start() after synchronizing the operator with the current assignment.
void Deactivate(int64 index)
~VarLocalSearchOperator() override
void AddVars(const std::vector< V * > &vars)
const Val & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
void Start(const Assignment *assignment) override
This method should not be overridden.
void Activate(int64 index)
void SetValue(int64 index, const Val &value)
bool Activated(int64 index) const
std::vector< int64 > to_remove_
SharedBoundsManager * bounds
GurobiMPCallbackContext * context
static const int64 kint64max
static const int64 kint64min
std::function< int64(const Model &)> Value(IntegerVariable v)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool AreAllStrictlyNegative(const std::vector< T > &values)
bool IsArrayInRange(const std::vector< IntVar * > &vars, T range_min, T range_max)
Demon * MakeConstraintDemon3(Solver *const s, T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
int64 PosIntDivUp(int64 e, int64 v)
int64 MinVarArray(const std::vector< IntVar * > &vars)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
bool AreAllBound(const std::vector< IntVar * > &vars)
bool AreAllNegative(const std::vector< T > &values)
int64 PosIntDivDown(int64 e, int64 v)
Demon * MakeConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
bool AreAllPositive(const std::vector< T > &values)
VarTypes
This enum is used internally to do dynamic typing on subclasses of integer variables.
bool AreAllBooleans(const std::vector< IntVar * > &vars)
bool AreAllLessOrEqual(const std::vector< T > &values, const T &value)
void FillValues(const std::vector< IntVar * > &vars, std::vector< int64 > *const values)
bool IsArrayConstant(const std::vector< T > &values, const T &value)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
bool IsIncreasingContiguous(const std::vector< T > &values)
uint64 Hash1(uint64 value)
Hash functions.
bool AreAllStrictlyPositive(const std::vector< T > &values)
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
int64 MaxVarArray(const std::vector< IntVar * > &vars)
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
LocalSearchFilter * MakeUnaryDimensionFilter(Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)
bool AreAllNull(const std::vector< T > &values)
bool AreAllBoundTo(const std::vector< IntVar * > &vars, int64 value)
Returns true if all variables are assigned to 'value'.
std::string ParameterDebugString(P param)
Demon * MakeDelayedConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
VarLocalSearchOperator< SequenceVar, std::vector< int >, SequenceVarLocalSearchHandler > SequenceVarLocalSearchOperatorTemplate
LocalSearchOperator * MakeLocalSearchOperator(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
Operator Factories.
bool AreAllOnes(const std::vector< T > &values)
bool IsIncreasing(const std::vector< T > &values)
static const int kUnassigned
LocalSearchFilter * MakePathStateFilter(Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)
bool IsArrayBoolean(const std::vector< T > &values)
bool AreAllGreaterOrEqual(const std::vector< T > &values, const T &value)
bool AreAllBoundOrNull(const std::vector< IntVar * > &vars, const std::vector< T > &values)
Returns true if all the variables are assigned to a single value, or if their corresponding value is ...
void AcceptUncheckedNeighbor(Search *const search)
static int input(yyscan_t yyscanner)
LocalSearchFilter * filter
FilterEventType event_type