68 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
69 #define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
79 #include "absl/base/macros.h"
80 #include "absl/container/flat_hash_map.h"
81 #include "absl/container/flat_hash_set.h"
82 #include "absl/random/distributions.h"
83 #include "absl/random/random.h"
84 #include "absl/strings/str_format.h"
93 #include "ortools/constraint_solver/routing_parameters.pb.h"
94 #include "ortools/constraint_solver/search_stats.pb.h"
95 #include "ortools/constraint_solver/solver_parameters.pb.h"
109 class AssignmentProto;
113 class CpIntegerExpression;
114 class CpIntervalVariable;
115 class CpSequenceVariable;
116 class CastConstraint;
119 class DecisionBuilder;
120 class DecisionVisitor;
123 class LocalSearchProfiler;
125 class DisjunctiveConstraint;
126 class ExpressionCache;
130 class IntVarAssignment;
133 class IntervalVarAssignment;
134 class IntervalVarElement;
135 class IntVarLocalSearchFilter;
136 class LocalSearchFilter;
137 class LocalSearchFilterManager;
138 class LocalSearchOperator;
139 class LocalSearchPhaseParameters;
144 class PropagationBaseObject;
145 class PropagationMonitor;
146 class LocalSearchMonitor;
151 class RegularLimitParameters;
153 class ImprovementSearchLimit;
157 class SequenceVarAssignment;
158 class SolutionCollector;
161 class ConstraintSolverParameters;
162 class SymmetryBreaker;
169 return absl::GetFlag(FLAGS_cp_random_seed) == -1
170 ? absl::Uniform<int64>(absl::BitGen(), 0,
kint64max)
171 : absl::GetFlag(FLAGS_cp_random_seed);
751 typedef std::function<
int64(
Solver* solver,
const std::vector<IntVar*>& vars,
768 ConstraintSolverParameters
parameters()
const {
return parameters_; }
780 InternalSaveValue(o);
795 template <
typename T>
797 return reinterpret_cast<T*
>(SafeRevAlloc(
object));
806 template <
typename T>
808 return reinterpret_cast<T*
>(SafeRevAllocArray(
object));
893 const std::vector<SearchMonitor*>& monitors);
915 const std::vector<SearchMonitor*>& monitors);
940 const std::vector<SearchMonitor*>& monitors);
980 absl::Time
Now()
const;
1019 return optimization_direction_;
1022 optimization_direction_ = direction;
1067 const std::string&
name, std::vector<IntVar*>* vars);
1071 std::vector<IntVar*>* vars);
1074 const std::string&
name);
1080 std::vector<IntVar*>* vars);
1098 const std::vector<int64>& coefs);
1101 const std::vector<int>& coefs);
1165 IntVar*
const target_var);
1213 int64 unperformed_value);
1340 const std::vector<int64>& coeffs,
1343 const std::vector<int>& coeffs,
1409 const std::vector<int64>& values);
1414 const std::vector<int64>& values);
1416 const std::vector<int>& values);
1420 std::vector<int64> ends);
1423 std::vector<int> ends);
1432 const std::vector<int64>& values,
1435 const std::vector<int>& values,
1438 const std::vector<int64>& values);
1449 IntVar*
const max_count);
1453 const std::vector<int64>& values,
1454 const std::vector<IntVar*>& cards);
1457 const std::vector<int>& values,
1458 const std::vector<IntVar*>& cards);
1461 const std::vector<IntVar*>& cards);
1470 const std::vector<int64>& card_min,
1471 const std::vector<int64>& card_max);
1476 const std::vector<int>& card_min,
1477 const std::vector<int>& card_max);
1482 const std::vector<int64>& values,
1483 const std::vector<int64>& card_min,
1484 const std::vector<int64>& card_max);
1489 const std::vector<int>& values,
1490 const std::vector<int>& card_min,
1491 const std::vector<int>& card_max);
1508 bool stronger_propagation);
1513 int64 escape_value);
1532 const std::vector<IntVar*>& sorted);
1540 const std::vector<IntVar*>& right);
1545 const std::vector<IntVar*>& right);
1552 const std::vector<IntVar*>& left,
const std::vector<IntVar*>& right);
1569 const std::vector<IntVar*>& second_vars);
1577 const std::vector<IntVar*>& second_vars,
1578 int64 escape_value);
1593 const std::vector<IntVar*>& active,
1596 const std::vector<IntVar*>& active,
1611 const std::vector<IntVar*>& active,
1612 const std::vector<IntVar*>& cumuls,
1613 const std::vector<IntVar*>& transits);
1618 const std::vector<IntVar*>& active,
1619 const std::vector<IntVar*>& cumuls,
1620 const std::vector<IntVar*>& transits);
1628 const std::vector<IntVar*>& active,
1629 const std::vector<IntVar*>& cumuls,
1639 const std::vector<IntVar*>& active,
1640 const std::vector<IntVar*>& cumuls,
1641 const std::vector<IntVar*>& slacks,
1648 std::vector<int64> sources,
1649 std::vector<int64> sinks,
1650 std::vector<IntVar*> status);
1658 std::vector<IntVar*> nexts,
1659 const std::vector<std::pair<int, int>>& precedences);
1669 std::vector<IntVar*> nexts,
1670 const std::vector<std::pair<int, int>>& precedences,
1671 const std::vector<int>& lifo_path_starts,
1672 const std::vector<int>& fifo_path_starts);
1676 std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1677 const std::vector<std::pair<int, int>>& precedences);
1682 Constraint* MakeMapDomain(IntVar* const var,
1683 const std::vector<IntVar*>& actives);
1701 int64 initial_state,
1702 const std::vector<int64>& final_states);
1713 int64 initial_state,
1714 const std::vector<int>& final_states);
1716 #if defined(SWIGPYTHON)
1719 const std::vector<IntVar*>& vars,
1720 const std::vector<std::vector<int64> >& raw_tuples) {
1722 tuples.InsertAll(raw_tuples);
1727 const std::vector<IntVar*>& vars,
1728 const std::vector<std::vector<int64> >& raw_transitions,
1729 int64 initial_state,
const std::vector<int>& final_states) {
1730 IntTupleSet transitions(3);
1731 transitions.InsertAll(raw_transitions);
1746 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1747 const std::vector<IntVar*>& x_size,
const std::vector<IntVar*>& y_size);
1749 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1750 const std::vector<int64>& x_size,
const std::vector<int64>& y_size);
1752 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1753 const std::vector<int>& x_size,
const std::vector<int>& y_size);
1764 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1765 const std::vector<IntVar*>& x_size,
const std::vector<IntVar*>& y_size);
1767 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1768 const std::vector<int64>& x_size,
const std::vector<int64>& y_size);
1770 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1771 const std::vector<int>& x_size,
const std::vector<int>& y_size);
1778 Pack*
MakePack(
const std::vector<IntVar*>& vars,
int number_of_bins);
1785 int64 duration,
bool optional,
1786 const std::string&
name);
1792 bool optional,
const std::string&
name,
1793 std::vector<IntervalVar*>*
const array);
1799 const std::string&
name);
1805 IntVar*
const performed_variable,
1806 const std::string&
name);
1811 const std::vector<IntVar*>& start_variables,
int64 duration,
1812 const std::string&
name, std::vector<IntervalVar*>*
const array);
1817 const std::vector<IntVar*>& start_variables,
1818 const std::vector<int64>& durations,
const std::string&
name,
1819 std::vector<IntervalVar*>*
const array);
1823 const std::vector<IntVar*>& start_variables,
1824 const std::vector<int>& durations,
const std::string&
name,
1825 std::vector<IntervalVar*>*
const array);
1830 const std::vector<IntVar*>& start_variables,
1831 const std::vector<int64>& durations,
1832 const std::vector<IntVar*>& performed_variables,
const std::string&
name,
1833 std::vector<IntervalVar*>*
const array);
1838 const std::vector<IntVar*>& start_variables,
1839 const std::vector<int>& durations,
1840 const std::vector<IntVar*>& performed_variables,
const std::string&
name,
1841 std::vector<IntervalVar*>*
const array);
1845 const std::string&
name);
1852 const std::string&
name);
1859 const std::string&
name,
1860 std::vector<IntervalVar*>*
const array);
1871 IntervalVar*
const interval_var,
int64 duration,
int64 offset);
1878 IntervalVar*
const interval_var,
int64 duration,
int64 offset);
1885 IntervalVar*
const interval_var,
int64 duration,
int64 offset);
1892 IntervalVar*
const interval_var,
int64 duration,
int64 offset);
1940 IntervalVar*
const t2);
1948 IntervalVar*
const t2,
1955 IntervalVar*
const t2,
IntVar*
const alt);
1960 IntervalVar*
const t2);
1965 const std::vector<IntervalVar*>& intervals,
const std::string&
name);
1971 const std::vector<IntervalVar*>& intervals,
const std::string&
name);
1984 const std::string&
name);
1997 const std::string&
name);
2009 const std::vector<int64>& demands,
2022 const std::vector<int>& demands,
2033 const std::vector<IntVar*>& demands,
2044 const std::vector<IntVar*>& demands,
2053 IntervalVar*
const target_var);
2066 const Assignment*
const assignment);
2073 const Assignment*
const assignment);
2083 const Assignment*
const assignment,
bool maximize);
2095 const Assignment*
const assignment,
int solution_count,
bool maximize);
2101 const Assignment*
const assignment);
2118 const std::vector<int64>& weights,
2124 const std::vector<int>& weights,
2129 const std::vector<int64>& weights,
2134 const std::vector<int>& weights,
2139 const std::vector<IntVar*>& sub_objectives,
2140 const std::vector<int64>& weights,
2145 const std::vector<IntVar*>& sub_objectives,
2146 const std::vector<int>& weights,
2168 const std::vector<IntVar*>& vars,
2170 double tabu_factor);
2176 const std::vector<IntVar*>& tabu_vars,
2177 int64 forbid_tenure);
2189 const std::vector<IntVar*>& vars,
2190 double penalty_factor);
2192 bool maximize,
IntVar*
const objective,
2194 const std::vector<IntVar*>& vars,
2195 const std::vector<IntVar*>& secondary_vars,
double penalty_factor);
2209 ABSL_DEPRECATED(
"Use the version taking absl::Duration() as argument")
2213 ? absl::InfiniteDuration()
2214 : absl::Milliseconds(time_in_ms));
2235 bool cumulative =
false);
2240 ABSL_DEPRECATED(
"Use other MakeLimit() versions")
2244 bool cumulative =
false);
2260 IntVar* objective_var,
bool maximize,
double objective_scaling_factor,
2261 double objective_offset,
double improvement_rate_coefficient,
2262 int improvement_rate_solutions_distance);
2280 std::function<std::string()> display_callback);
2285 std::function<std::string()> display_callback);
2294 std::function<std::string()> display_callback);
2336 absl::flat_hash_map<const IntVar*, int>*
const map);
2341 const std::vector<SymmetryBreaker*>& visitors);
2358 bool start_with_lower_half);
2362 const std::vector<int64>& values);
2463 int64*
const marker);
2471 int64*
const marker);
2511 const std::vector<IntVar*>& vars);
2537 const std::vector<SearchMonitor*>& monitors);
2570 int64 step,
const std::vector<SearchMonitor*>& monitors);
2584 const std::vector<IntVar*>& secondary_vars,
2592 const std::vector<IntVar*>& secondary_vars,
2604 int number_of_variables);
2606 int number_of_variables,
2623 const std::vector<IntVar*>& variables,
2624 const std::vector<int64>& target_values);
2657 const std::vector<LocalSearchOperator*>& ops);
2659 const std::vector<LocalSearchOperator*>& ops,
bool restart);
2661 const std::vector<LocalSearchOperator*>& ops,
2662 std::function<
int64(
int,
int)> evaluator);
2666 const std::vector<LocalSearchOperator*>& ops);
2672 const std::vector<LocalSearchOperator*>& ops,
int32 seed);
2682 const std::vector<LocalSearchOperator*>& ops,
double memory_coefficient,
2683 double exploration_coefficient,
bool maximize);
2724 const std::vector<IntVar*>& vars,
DecisionBuilder*
const first_solution,
2728 const std::vector<IntVar*>& vars,
DecisionBuilder*
const first_solution,
2732 const std::vector<SequenceVar*>& vars,
2773 const std::vector<IntVar*>& vars,
2813 InternalSaveValue(adr);
2822 InternalSaveValue(adr);
2830 return absl::Uniform<int64>(random_, 0, size);
2836 return absl::Uniform<int32>(random_, 0, size);
2875 fail_intercept_ = std::move(fail_intercept);
2885 use_fast_local_search_ = use_fast_local_search;
2958 template <
class K,
class V>
2966 bool* is_negated)
const;
2987 if (!should_fail_)
return;
2988 should_fail_ =
false;
2996 void PushSentinel(
int magic_code);
2997 void BacktrackToSentinel(
int magic_code);
2998 void ProcessConstraints();
2999 bool BacktrackOneLevel(
Decision** fail_decision);
3000 void JumpToSentinelWhenNested();
3001 void JumpToSentinel();
3002 void check_alloc_state();
3004 void EnqueueVar(
Demon*
const d);
3005 void EnqueueDelayedDemon(
Demon*
const d);
3008 void UnfreezeQueue();
3009 void reset_action_on_fail();
3010 void set_action_on_fail(
Action a);
3011 void set_variable_to_clean_on_fail(
IntVar* v);
3012 void IncrementUncheckedSolutionCounter();
3013 bool IsUncheckedSolutionLimitReached();
3015 void InternalSaveValue(
int* valptr);
3016 void InternalSaveValue(
int64* valptr);
3017 void InternalSaveValue(
uint64* valptr);
3018 void InternalSaveValue(
double* valptr);
3019 void InternalSaveValue(
bool* valptr);
3020 void InternalSaveValue(
void** valptr);
3021 void InternalSaveValue(
int64** valptr) {
3022 InternalSaveValue(
reinterpret_cast<void**
>(valptr));
3025 BaseObject* SafeRevAlloc(BaseObject* ptr);
3027 int* SafeRevAllocArray(
int* ptr);
3030 double* SafeRevAllocArray(
double* ptr);
3031 BaseObject** SafeRevAllocArray(BaseObject** ptr);
3033 IntExpr** SafeRevAllocArray(IntExpr** ptr);
3037 void* UnsafeRevAllocAux(
void* ptr);
3039 T* UnsafeRevAlloc(T* ptr) {
3040 return reinterpret_cast<T*
>(
3041 UnsafeRevAllocAux(
reinterpret_cast<void*
>(ptr)));
3043 void** UnsafeRevAllocArrayAux(
void** ptr);
3045 T** UnsafeRevAllocArray(T** ptr) {
3046 return reinterpret_cast<T**
>(
3047 UnsafeRevAllocArrayAux(
reinterpret_cast<void**
>(ptr)));
3050 void InitCachedIntConstants();
3051 void InitCachedConstraint();
3056 Search* TopLevelSearch()
const {
return searches_.at(1); }
3060 Search* ParentSearch()
const {
3061 const size_t search_size = searches_.size();
3063 return searches_[search_size - 2];
3072 int GetNewIntVarIndex() {
return num_int_vars_++; }
3075 bool IsADifference(IntExpr* expr, IntExpr**
const left,
3076 IntExpr**
const right);
3078 const std::string name_;
3079 const ConstraintSolverParameters parameters_;
3080 absl::flat_hash_map<const PropagationBaseObject*, std::string>
3081 propagation_object_names_;
3082 absl::flat_hash_map<const PropagationBaseObject*, IntegerCastInfo>
3084 absl::flat_hash_set<const Constraint*> cast_constraints_;
3085 const std::string empty_name_;
3086 std::unique_ptr<Queue> queue_;
3087 std::unique_ptr<Trail> trail_;
3088 std::vector<Constraint*> constraints_list_;
3089 std::vector<Constraint*> additional_constraints_list_;
3090 std::vector<int> additional_constraints_parent_list_;
3097 int64 filtered_neighbors_;
3098 int64 accepted_neighbors_;
3100 std::unique_ptr<ClockTimer> timer_;
3101 std::vector<Search*> searches_;
3102 std::mt19937 random_;
3104 std::unique_ptr<Decision> balancing_decision_;
3106 std::function<void()> fail_intercept_;
3110 bool use_fast_local_search_;
3114 std::unique_ptr<Assignment> local_search_state_;
3117 enum { MIN_CACHED_INT_CONST = -8, MAX_CACHED_INT_CONST = 8 };
3118 IntVar* cached_constants_[MAX_CACHED_INT_CONST + 1 - MIN_CACHED_INT_CONST];
3124 std::unique_ptr<Decision> fail_decision_;
3125 int constraint_index_;
3126 int additional_constraint_index_;
3129 std::unique_ptr<ModelCache> model_cache_;
3130 std::unique_ptr<PropagationMonitor> propagation_monitor_;
3131 PropagationMonitor* print_trace_;
3132 std::unique_ptr<LocalSearchMonitor> local_search_monitor_;
3133 int anonymous_variable_index_;
3139 std::ostream&
operator<<(std::ostream& out,
const Solver*
const s);
3162 std::ostream&
operator<<(std::ostream& out,
const BaseObject* o);
3173 if (
name().empty()) {
3174 return "PropagationBaseObject";
3176 return absl::StrFormat(
"PropagationBaseObject: %s",
name());
3201 solver_->set_action_on_fail(std::move(
a));
3210 solver_->set_variable_to_clean_on_fail(v);
3214 virtual std::string
name()
const;
3219 virtual std::string
BaseName()
const;
3244 DISALLOW_COPY_AND_ASSIGN(
Decision);
3255 bool start_with_lower_half);
3284 std::vector<SearchMonitor*>*
const extras);
3538 const std::vector<int64>& values);
3547 const std::string& arg_name,
const std::vector<IntVar*>& arguments);
3554 const std::string& arg_name,
const std::vector<IntervalVar*>& arguments);
3560 const std::string& arg_name,
const std::vector<SequenceVar*>& arguments);
3574 const std::string& arg_name,
int64 index_max);
3737 explicit Rev(
const T& val) : stamp_(0), value_(val) {}
3739 const T&
Value()
const {
return value_; }
3742 if (val != value_) {
3743 if (stamp_ < s->stamp()) {
3745 stamp_ = s->
stamp();
3781 for (
int i = 0; i <
size; ++i) {
3799 if (val != values_[
index]) {
3804 values_[
index] = val;
3809 std::unique_ptr<uint64[]> stamps_;
3810 std::unique_ptr<T[]> values_;
3865 virtual bool IsVar()
const {
return false; }
3894 DISALLOW_COPY_AND_ASSIGN(
IntExpr);
3922 virtual bool Ok()
const = 0;
3931 std::string
DebugString()
const override {
return "IntVar::Iterator"; }
3944 : it_(it), begin_was_called_(false) {
3950 DCHECK(!begin_was_called_);
3951 begin_was_called_ =
true;
3968 return it_->
Value();
3976 DCHECK(other.it_ == it_);
3989 IntVarIterator*
const it_;
3990 bool begin_was_called_;
4003 bool IsVar()
const override {
return true; }
4018 virtual void RemoveValues(
const std::vector<int64>& values);
4021 virtual void SetValues(
const std::vector<int64>& values);
4095 DISALLOW_COPY_AND_ASSIGN(
IntVar);
4106 std::string
DebugString()
const override {
return "SolutionCollector"; }
4110 void Add(
const std::vector<IntVar*>& vars);
4112 void Add(
const std::vector<IntervalVar*>& vars);
4114 void Add(
const std::vector<SequenceVar*>& vars);
4221 virtual std::string
Print()
const;
4269 return absl::StrFormat(
"SearchLimit(crossed = %i)", crossed_);
4273 void TopPeriodicCheck();
4290 bool Check()
override;
4291 void Init()
override;
4297 return duration_limit_ == absl::InfiniteDuration()
4309 return solver_time_at_limit_start_ + duration_limit_;
4316 absl::Duration TimeElapsed();
4318 return (total > 0 && total <
kint64max) ? 100 * (
value - offset) / total
4322 absl::Duration duration_limit_;
4323 absl::Time solver_time_at_limit_start_;
4324 absl::Duration last_time_elapsed_;
4327 bool smart_time_check_;
4329 int64 branches_offset_;
4331 int64 failures_offset_;
4333 int64 solutions_offset_;
4356 double objective_scaling_factor,
4357 double objective_offset,
4358 double improvement_rate_coefficient,
4359 int improvement_rate_solutions_distance);
4363 bool Check()
override;
4365 void Init()
override;
4370 double objective_scaling_factor_;
4371 double objective_offset_;
4372 double improvement_rate_coefficient_;
4373 int improvement_rate_solutions_distance_;
4375 double best_objective_;
4377 std::deque<std::pair<double, int64> > improvements_;
4380 bool objective_updated_;
4381 bool gradient_stage_;
4551 const std::vector<IntVar*>& nexts,
const std::string&
name);
4572 int*
const unperformed)
const;
4594 std::vector<int>*
const possible_lasts);
4602 const std::vector<int>& rank_last,
4603 const std::vector<int>& unperformed);
4614 std::vector<int>*
const rank_last,
4615 std::vector<int>*
const unperformed)
const;
4630 int ComputeForwardFrontier();
4631 int ComputeBackwardFrontier();
4632 void UpdatePrevious()
const;
4634 const std::vector<IntervalVar*> intervals_;
4635 const std::vector<IntVar*> nexts_;
4636 mutable std::vector<int> previous_;
4664 if (var_ !=
nullptr) {
4668 void LoadFromProto(
const IntVarAssignment& int_var_assignment_proto);
4669 void WriteToProto(IntVarAssignment* int_var_assignment_proto)
const;
4680 bool Bound()
const {
return (max_ == min_); }
4693 return !(*
this == element);
4713 const IntervalVarAssignment& interval_var_assignment_proto);
4714 void WriteToProto(IntervalVarAssignment* interval_var_assignment_proto)
const;
4725 CHECK_EQ(duration_max_, duration_min_);
4726 return duration_max_;
4737 CHECK_EQ(performed_max_, performed_min_);
4738 return performed_max_;
4773 performed_min_ = mi;
4774 performed_max_ = ma;
4781 return (start_min_ == start_max_ && duration_min_ == duration_max_ &&
4782 end_min_ == end_max_ && performed_min_ == performed_max_);
4787 return !(*
this == element);
4793 int64 duration_min_;
4794 int64 duration_max_;
4797 int64 performed_min_;
4798 int64 performed_max_;
4826 const SequenceVarAssignment& sequence_var_assignment_proto);
4827 void WriteToProto(SequenceVarAssignment* sequence_var_assignment_proto)
const;
4832 void SetSequence(
const std::vector<int>& forward_sequence,
4833 const std::vector<int>& backward_sequence,
4834 const std::vector<int>& unperformed);
4839 return forward_sequence_.size() + unperformed_.size() == var_->
size();
4846 return !(*
this == element);
4850 bool CheckClassInvariants();
4853 std::vector<int> forward_sequence_;
4854 std::vector<int> backward_sequence_;
4855 std::vector<int> unperformed_;
4858 template <
class V,
class E>
4868 return &elements_[
index];
4874 elements_.emplace_back(
var);
4875 return &elements_.back();
4880 elements_[position].Reset(
var);
4881 return &elements_[position];
4885 if (!elements_map_.empty()) {
4886 elements_map_.clear();
4891 void Resize(
size_t size) { elements_.resize(size); }
4892 bool Empty()
const {
return elements_.empty(); }
4896 for (
int i = 0; i < container.elements_.size(); ++i) {
4897 const E& element = container.elements_[i];
4898 const V*
const var = element.Var();
4900 if (i < elements_.size() && elements_[i].Var() ==
var) {
4906 E*
const local_element = &elements_[
index];
4907 local_element->Copy(element);
4908 if (element.Activated()) {
4909 local_element->Activate();
4911 local_element->Deactivate();
4919 for (
int i = 0; i < container.elements_.size(); ++i) {
4920 const E& element = container.elements_[i];
4921 FastAdd(element.Var())->Copy(element);
4930 DCHECK(element !=
nullptr)
4931 <<
"Unknown variable " <<
var->DebugString() <<
" in solution";
4943 DCHECK(element !=
nullptr)
4944 <<
"Unknown variable " <<
var->DebugString() <<
" in solution";
4954 const std::vector<E>&
elements()
const {
return elements_; }
4957 int Size()
const {
return elements_.size(); }
4959 for (E& element : elements_) {
4964 for (E& element : elements_) {
4965 if (element.Activated()) {
4971 for (
const E& element : elements_) {
4972 if (!element.Bound())
return false;
4986 EnsureMapIsUpToDate();
4990 for (
const E& element : container.elements_) {
4991 const int position =
4993 if (position < 0 || elements_[position] != element) {
5000 return !(*
this == container);
5004 void EnsureMapIsUpToDate()
const {
5005 absl::flat_hash_map<const V*, int>* map =
5006 const_cast<absl::flat_hash_map<const V*, int>*
>(&elements_map_);
5007 for (
int i = map->size(); i < elements_.size(); ++i) {
5008 (*map)[elements_[i].Var()] = i;
5011 bool Find(
const V*
const var,
int*
index)
const {
5013 const size_t kMaxSizeForLinearAccess = 11;
5014 if (
Size() <= kMaxSizeForLinearAccess) {
5018 for (
int i = 0; i < elements_.size(); ++i) {
5019 if (
var == elements_[i].Var()) {
5026 EnsureMapIsUpToDate();
5027 DCHECK_EQ(elements_map_.size(), elements_.size());
5032 std::vector<E> elements_;
5033 absl::flat_hash_map<const V*, int> elements_map_;
5052 return int_var_container_.
Empty() && interval_var_container_.
Empty() &&
5053 sequence_var_container_.
Empty();
5066 bool Load(
const std::string& filename);
5070 void Load(
const AssignmentProto& assignment_proto);
5072 bool Save(
const std::string& filename)
const;
5076 void Save(AssignmentProto*
const assignment_proto)
const;
5092 void Add(
const std::vector<IntVar*>& vars);
5105 void Add(
const std::vector<IntervalVar*>& vars);
5138 void Add(
const std::vector<SequenceVar*>& vars);
5145 const std::vector<int>& forward_sequence,
5146 const std::vector<int>& backward_sequence,
5147 const std::vector<int>& unperformed);
5149 const std::vector<int>& forward_sequence);
5151 const std::vector<int>& backward_sequence);
5153 const std::vector<int>& unperformed);
5192 return interval_var_container_;
5195 return &interval_var_container_;
5198 return sequence_var_container_;
5201 return &sequence_var_container_;
5204 return int_var_container_ == assignment.int_var_container_ &&
5205 interval_var_container_ == assignment.interval_var_container_ &&
5206 sequence_var_container_ == assignment.sequence_var_container_ &&
5207 objective_element_ == assignment.objective_element_;
5210 return !(*
this == assignment);
5222 const Assignment& assignment);
5230 const std::vector<IntVar*>& target_vars,
5231 const Assignment* source_assignment,
5232 const std::vector<IntVar*>& source_vars);
5236 Pack(
Solver*
const s,
const std::vector<IntVar*>& vars,
int number_of_bins);
5249 const std::vector<int64>& weights,
const std::vector<int64>&
bounds);
5268 const std::vector<IntVar*>& loads);
5274 const std::vector<IntVar*>& loads);
5286 const std::vector<IntVar*>& usage,
const std::vector<int64>&
capacity);
5301 void Post()
override;
5308 bool IsUndecided(
int var_index,
int bin_index)
const;
5310 void Assign(
int var_index,
int bin_index);
5312 bool IsPossible(
int var_index,
int bin_index)
const;
5324 bool IsInProcess()
const;
5325 const std::vector<IntVar*> vars_;
5327 std::vector<Dimension*> dims_;
5328 std::unique_ptr<RevBitMatrix> unprocessed_;
5329 std::vector<std::vector<int>> forced_;
5330 std::vector<std::vector<int>> removed_;
5331 std::vector<IntVarIterator*> holes_;
5334 std::vector<std::pair<int, int>> to_set_;
5335 std::vector<std::pair<int, int>> to_unset_;
5342 const std::vector<IntervalVar*>& intervals,
5343 const std::string&
name);
5361 virtual const std::vector<IntVar*>&
nexts()
const = 0;
5362 virtual const std::vector<IntVar*>&
actives()
const = 0;
#define CHECK_EQ(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
bool AreAllElementsBound() const
E * MutableElement(const V *const var)
E * MutableElementOrNull(const V *const var)
bool operator==(const AssignmentContainer< V, E > &container) const
Returns true if this and 'container' both represent the same V* -> E map.
const E * ElementPtrOrNull(const V *const var) const
const std::vector< E > & elements() const
bool Contains(const V *const var) const
E * AddAtPosition(V *var, int position)
Advanced usage: Adds element at a given position; position has to have been allocated with Assignment...
const E & Element(int index) const
void Copy(const AssignmentContainer< V, E > &container)
Copies all the elements of 'container' to this container, clearing its previous content.
bool operator!=(const AssignmentContainer< V, E > &container) const
E * MutableElement(int index)
const E & Element(const V *const var) const
void CopyIntersection(const AssignmentContainer< V, E > &container)
Copies the elements of 'container' which are already in the calling container.
void Resize(size_t size)
Advanced usage: Resizes the container, potentially adding elements with null variables.
E * FastAdd(V *var)
Adds element without checking its presence in the container.
An Assignment is a variable -> domains mapping, used to report solutions to the user.
bool ActivatedObjective() const
const std::vector< int > & Unperformed(const SequenceVar *const var) const
int64 DurationMin(const IntervalVar *const var) const
void SetForwardSequence(const SequenceVar *const var, const std::vector< int > &forward_sequence)
int64 Value(const IntVar *const var) const
void Deactivate(const IntVar *const var)
void SetStartMin(const IntervalVar *const var, int64 m)
IntContainer * MutableIntVarContainer()
void SetBackwardSequence(const SequenceVar *const var, const std::vector< int > &backward_sequence)
void SetObjectiveRange(int64 l, int64 u)
const IntContainer & IntVarContainer() const
const std::vector< int > & BackwardSequence(const SequenceVar *const var) const
bool AreAllElementsBound() const
int64 ObjectiveMin() const
void SetDurationValue(const IntervalVar *const var, int64 value)
void SetEndMax(const IntervalVar *const var, int64 m)
Assignment(Solver *const s)
const SequenceContainer & SequenceVarContainer() const
int64 EndMax(const IntervalVar *const var) const
int64 StartValue(const IntervalVar *const var) const
AssignmentContainer< SequenceVar, SequenceVarElement > SequenceContainer
void SetStartMax(const IntervalVar *const var, int64 m)
int NumSequenceVars() const
void SetPerformedValue(const IntervalVar *const var, int64 value)
IntVar * Objective() const
int64 PerformedMin(const IntervalVar *const var) const
bool Load(const std::string &filename)
Loads an assignment from a file; does not add variables to the assignment (only the variables contain...
int64 Min(const IntVar *const var) const
bool Contains(const IntVar *const var) const
bool Activated(const IntVar *const var) const
bool Save(const std::string &filename) const
Saves the assignment to a file.
int64 EndMin(const IntervalVar *const var) const
void SetMax(const IntVar *const var, int64 m)
void SetPerformedRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetEndMin(const IntervalVar *const var, int64 m)
const std::vector< int > & ForwardSequence(const SequenceVar *const var) const
bool HasObjective() const
void AddObjective(IntVar *const v)
int64 ObjectiveValue() const
int64 StartMin(const IntervalVar *const var) const
void Activate(const IntVar *const var)
void SetPerformedMin(const IntervalVar *const var, int64 m)
void DeactivateObjective()
void SetMin(const IntVar *const var, int64 m)
SequenceContainer * MutableSequenceVarContainer()
void SetPerformedMax(const IntervalVar *const var, int64 m)
int64 Max(const IntVar *const var) const
IntervalContainer * MutableIntervalVarContainer()
void SetEndValue(const IntervalVar *const var, int64 value)
void SetUnperformed(const SequenceVar *const var, const std::vector< int > &unperformed)
int64 DurationMax(const IntervalVar *const var) const
void SetObjectiveMax(int64 m)
bool operator==(const Assignment &assignment) const
void SetStartValue(const IntervalVar *const var, int64 value)
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
int NumIntervalVars() const
bool ObjectiveBound() const
void SetDurationMax(const IntervalVar *const var, int64 m)
AssignmentContainer< IntervalVar, IntervalVarElement > IntervalContainer
void SetStartRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetObjectiveMin(int64 m)
void SetValue(const IntVar *const var, int64 value)
void Copy(const Assignment *assignment)
Copies 'assignment' to the current assignment, clearing its previous content.
int64 PerformedMax(const IntervalVar *const var) const
AssignmentContainer< IntVar, IntVarElement > IntContainer
void SetSequence(const SequenceVar *const var, const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
int64 DurationValue(const IntervalVar *const var) const
void SetDurationMin(const IntervalVar *const var, int64 m)
int64 ObjectiveMax() const
int64 StartMax(const IntervalVar *const var) const
int64 EndValue(const IntervalVar *const var) const
int64 PerformedValue(const IntervalVar *const var) const
IntVarElement * Add(IntVar *const var)
void SetEndRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetDurationRange(const IntervalVar *const var, int64 mi, int64 ma)
const IntervalContainer & IntervalVarContainer() const
bool Bound(const IntVar *const var) const
std::string DebugString() const override
void SetObjectiveValue(int64 value)
IntVarElement * FastAdd(IntVar *const var)
Adds without checking if variable has been previously added.
void SetRange(const IntVar *const var, int64 l, int64 u)
bool operator!=(const Assignment &assignment) const
This is the base class for all expressions that are not variables.
A BaseObject is the root of all reversibly allocated objects.
virtual std::string DebugString() const
Cast constraints are special channeling constraints designed to keep a variable in sync with an expre...
IntVar * target_var() const
~CastConstraint() override
IntVar *const target_var_
CastConstraint(Solver *const solver, IntVar *const target_var)
A constraint is the main modeling object.
void PostAndPropagate()
Calls Post and then Propagate to initialize the constraints.
bool IsCastConstraint() const
Is the constraint created by a cast from expression to integer variable?
virtual void InitialPropagate()=0
This method performs the initial propagation of the constraint.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
virtual IntVar * Var()
Creates a Boolean variable representing the status of the constraint (false = constraint is violated,...
Constraint(Solver *const solver)
std::string DebugString() const override
virtual void Post()=0
This method is called when the constraint is processed by the solver.
A DecisionBuilder is responsible for creating the search tree.
virtual Decision * Next(Solver *const s)=0
This is the main method of the decision builder class.
virtual void Accept(ModelVisitor *const visitor) const
virtual void AppendMonitors(Solver *const solver, std::vector< SearchMonitor * > *const extras)
This method will be called at the start of the search.
~DecisionBuilder() override
std::string DebugString() const override
A Decision represents a choice point in the search tree.
virtual void Accept(DecisionVisitor *const visitor) const
Accepts the given visitor.
virtual void Apply(Solver *const s)=0
Apply will be called first when the decision is executed.
virtual void Refute(Solver *const s)=0
Refute will be called after a backtrack.
std::string DebugString() const override
A DecisionVisitor is used to inspect a decision.
virtual void VisitSplitVariableDomain(IntVar *const var, int64 value, bool start_with_lower_half)
~DecisionVisitor() override
virtual void VisitRankFirstInterval(SequenceVar *const sequence, int index)
virtual void VisitUnknownDecision()
virtual void VisitScheduleOrPostpone(IntervalVar *const var, int64 est)
virtual void VisitScheduleOrExpedite(IntervalVar *const var, int64 est)
virtual void VisitRankLastInterval(SequenceVar *const sequence, int index)
virtual void VisitSetVariableValue(IntVar *const var, int64 value)
A Demon is the base element of a propagation queue.
void inhibit(Solver *const s)
This method inhibits the demon in the search tree below the current position.
Demon()
This indicates the priority of a demon.
void desinhibit(Solver *const s)
This method un-inhibits the demon that was previously inhibited.
virtual Solver::DemonPriority priority() const
This method returns the priority of the demon.
std::string DebugString() const override
virtual void Run(Solver *const s)=0
This is the main callback of the demon.
const std::vector< IntervalVar * > intervals_
virtual const std::vector< IntVar * > & time_cumuls() const =0
virtual const std::vector< IntVar * > & actives() const =0
virtual SequenceVar * MakeSequenceVar()=0
Creates a sequence variable from the constraint.
int64 TransitionTime(int before_index, int after_index)
~DisjunctiveConstraint() override
virtual const std::vector< IntVar * > & nexts() const =0
DisjunctiveConstraint(Solver *const s, const std::vector< IntervalVar * > &intervals, const std::string &name)
void SetTransitionTime(Solver::IndexEvaluator2 transition_time)
Add a transition time between intervals.
virtual const std::vector< IntVar * > & time_slacks() const =0
Solver::IndexEvaluator2 transition_time_
bool Check() override
This method is called to check the status of the limit.
void Init() override
This method is called when the search limit is initialized.
~ImprovementSearchLimit() override
void Copy(const SearchLimit *const limit) override
Copy a limit.
bool AtSolution() override
This method is called when a valid solution is found.
ImprovementSearchLimit(Solver *const s, IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Utility class to encapsulate an IntVarIterator and use it in a range-based loop.
InitAndGetValues(IntVarIterator *it)
The class IntExpr is the base of all integer expressions in constraint programming.
virtual void SetMax(int64 m)=0
virtual IntVar * Var()=0
Creates a variable from the expression.
void WhenRange(Solver::Closure closure)
Attach a demon that will watch the min or the max of the expression.
virtual void SetRange(int64 l, int64 u)
This method sets both the min and the max of the expression.
virtual void SetValue(int64 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 void SetMin(int64 m)=0
virtual bool IsVar() const
Returns true if the expression is indeed a variable.
virtual void Range(int64 *l, int64 *u)
By default calls Min() and Max(), but can be redefined when Min and Max code can be factorized.
virtual int64 Max() const =0
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
IntVar * VarWithName(const std::string &name)
Creates a variable from the expression and set the name of the resulting var.
virtual int64 Min() const =0
virtual void WhenRange(Demon *d)=0
Attach a demon that will watch the min or the max of the expression.
void WhenRange(Solver::Action action)
Attach a demon that will watch the min or the max of the expression.
void Copy(const IntVarElement &element)
bool operator!=(const IntVarElement &element) const
void Reset(IntVar *const var)
bool operator==(const IntVarElement &element) const
std::string DebugString() const
void WriteToProto(IntVarAssignment *int_var_assignment_proto) const
void SetRange(int64 l, int64 u)
void LoadFromProto(const IntVarAssignment &int_var_assignment_proto)
The class IntVar is a subset of IntExpr.
virtual int64 OldMax() const =0
Returns the previous max.
IntVar * Var() override
Creates a variable from the expression.
void WhenBound(Solver::Closure closure)
This method attaches a closure that will be awakened when the variable is bound.
virtual void RemoveValue(int64 v)=0
This method removes the value 'v' from the domain of the variable.
virtual IntVar * IsDifferent(int64 constant)=0
virtual void SetValues(const std::vector< int64 > &values)
This method intersects the current domain with the values in the array.
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
virtual bool Contains(int64 v) const =0
This method returns whether the value 'v' is in the domain of the variable.
void WhenDomain(Solver::Closure closure)
This method attaches a closure that will watch any domain modification of the domain of the variable.
virtual IntVarIterator * MakeHoleIterator(bool reversible) const =0
Creates a hole iterator.
virtual IntVar * IsEqual(int64 constant)=0
IsEqual.
void WhenDomain(Solver::Action action)
This method attaches an action that will watch any domain modification of the domain of the variable.
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
virtual void RemoveValues(const std::vector< int64 > &values)
This method remove the values from the domain of the variable.
virtual IntVarIterator * MakeDomainIterator(bool reversible) const =0
Creates a domain iterator.
virtual IntVar * IsLessOrEqual(int64 constant)=0
virtual void WhenDomain(Demon *d)=0
This method attaches a demon that will watch any domain modification of the domain of the variable.
virtual int64 Value() const =0
This method returns the value of the variable.
virtual void RemoveInterval(int64 l, int64 u)=0
This method removes the interval 'l' .
int index() const
Returns the index of the variable.
virtual uint64 Size() const =0
This method returns the number of values in the domain of the variable.
virtual IntVar * IsGreaterOrEqual(int64 constant)=0
void WhenBound(Solver::Action action)
This method attaches an action that will be awakened when the variable is bound.
bool IsVar() const override
Returns true if the expression is indeed a variable.
virtual int VarType() const
virtual int64 OldMin() const =0
Returns the previous min.
The class Iterator has two direct subclasses.
virtual void Init()=0
This method must be called before each loop.
virtual void Next()=0
This method moves the iterator to the next value.
virtual int64 Value() const =0
This method returns the current value of the iterator.
~IntVarIterator() override
std::string DebugString() const override
Pretty Print.
virtual bool Ok() const =0
This method indicates if we can call Value() or not.
IntervalVarElement * Clone()
void SetPerformedValue(int64 v)
void LoadFromProto(const IntervalVarAssignment &interval_var_assignment_proto)
void SetPerformedRange(int64 mi, int64 ma)
void SetStartValue(int64 v)
bool operator!=(const IntervalVarElement &element) const
void Reset(IntervalVar *const var)
void SetPerformedMin(int64 m)
int64 DurationMin() const
void SetDurationValue(int64 v)
void SetStartMax(int64 m)
void SetEndValue(int64 v)
void SetEndRange(int64 mi, int64 ma)
int64 DurationValue() const
std::string DebugString() const
int64 DurationMax() const
void SetStartRange(int64 mi, int64 ma)
int64 PerformedValue() const
void SetStartMin(int64 m)
void SetDurationRange(int64 mi, int64 ma)
bool operator==(const IntervalVarElement &element) const
void Copy(const IntervalVarElement &element)
void SetDurationMin(int64 m)
void WriteToProto(IntervalVarAssignment *interval_var_assignment_proto) const
void SetPerformedMax(int64 m)
void SetDurationMax(int64 m)
int64 PerformedMin() const
int64 PerformedMax() const
IntervalVar * Var() const
Interval variables are often used in scheduling.
virtual int64 OldStartMin() const =0
virtual int64 StartMax() const =0
void WhenDurationRange(Solver::Closure closure)
void WhenAnything(Solver::Closure closure)
Attaches a closure awakened when anything about this interval changes.
virtual int64 OldEndMin() const =0
static const int64 kMaxValidValue
The largest acceptable value to be returned by EndMax()
void WhenStartBound(Solver::Closure closure)
virtual void WhenStartBound(Demon *const d)=0
void WhenEndRange(Solver::Closure closure)
virtual IntExpr * SafeDurationExpr(int64 unperformed_value)=0
void WhenAnything(Demon *const d)
Attaches a demon awakened when anything about this interval changes.
virtual int64 DurationMax() const =0
virtual void SetPerformed(bool val)=0
virtual int64 EndMax() const =0
void WhenEndBound(Solver::Action action)
virtual void SetEndMax(int64 m)=0
virtual void WhenEndRange(Demon *const d)=0
virtual void SetStartMin(int64 m)=0
virtual void SetDurationMin(int64 m)=0
virtual void WhenDurationBound(Demon *const d)=0
virtual int64 OldDurationMin() const =0
virtual void SetEndMin(int64 m)=0
virtual bool WasPerformedBound() const =0
void WhenStartRange(Solver::Action action)
virtual void SetEndRange(int64 mi, int64 ma)=0
virtual void WhenDurationRange(Demon *const d)=0
static const int64 kMinValidValue
The smallest acceptable value to be returned by StartMin()
virtual void WhenEndBound(Demon *const d)=0
virtual void Accept(ModelVisitor *const visitor) const =0
Accepts the given visitor.
void WhenDurationBound(Solver::Action action)
virtual bool MustBePerformed() const =0
These methods query, set, and watch the performed status of the interval var.
IntervalVar(Solver *const solver, const std::string &name)
virtual void WhenPerformedBound(Demon *const d)=0
virtual IntExpr * EndExpr()=0
virtual void SetStartMax(int64 m)=0
virtual int64 OldEndMax() const =0
virtual int64 StartMin() const =0
These methods query, set, and watch the start position of the interval var.
void WhenStartBound(Solver::Action action)
virtual void SetStartRange(int64 mi, int64 ma)=0
void WhenAnything(Solver::Action action)
Attaches an action awakened when anything about this interval changes.
virtual IntExpr * PerformedExpr()=0
virtual int64 OldDurationMax() const =0
virtual IntExpr * DurationExpr()=0
void WhenEndRange(Solver::Action action)
void WhenStartRange(Solver::Closure closure)
virtual int64 EndMin() const =0
These methods query, set, and watch the end position of the interval var.
virtual void WhenStartRange(Demon *const d)=0
virtual IntExpr * StartExpr()=0
These methods create expressions encapsulating the start, end and duration of the interval var.
virtual IntExpr * SafeEndExpr(int64 unperformed_value)=0
virtual IntExpr * SafeStartExpr(int64 unperformed_value)=0
These methods create expressions encapsulating the start, end and duration of the interval var.
bool IsPerformedBound() const
virtual int64 DurationMin() const =0
These methods query, set, and watch the duration of the interval var.
virtual void SetDurationRange(int64 mi, int64 ma)=0
virtual void SetDurationMax(int64 m)=0
void WhenPerformedBound(Solver::Action action)
void WhenPerformedBound(Solver::Closure closure)
virtual int64 OldStartMax() const =0
void WhenEndBound(Solver::Closure closure)
virtual bool MayBePerformed() const =0
void WhenDurationRange(Solver::Action action)
bool CannotBePerformed() const
void WhenDurationBound(Solver::Closure closure)
Local Search Filters are used for fast neighbor pruning.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
The base class for all local search operators.
Implements a complete cache for model elements: expressions and constraints.
static const char kDurationMinArgument[]
static const char kIntervalArgument[]
virtual void VisitIntervalVariable(const IntervalVar *const variable, const std::string &operation, int64 value, IntervalVar *const delegate)
static const char kSolutionLimitArgument[]
static const char kSizeArgument[]
static const char kIsMember[]
static const char kCountUsedBinsExtension[]
static const char kIntervalVariable[]
static const char kObjectiveExtension[]
static const char kPower[]
static const char kEarlyDateArgument[]
static const char kMaximizeArgument[]
static const char kLateDateArgument[]
static const char kFinalStatesArgument[]
static const char kIndex2Argument[]
static const char kStartExpr[]
static const char kMinArgument[]
static const char kEndsArgument[]
static const char kSequenceVariable[]
static const char kDeviation[]
static const char kMirrorOperation[]
Operations.
static const char kAbs[]
Constraint and Expression types.
static const char kMember[]
static const char kDelayedPathCumul[]
virtual void VisitSequenceVariable(const SequenceVar *const variable)
static const char kVariableUsageLessConstantExtension[]
virtual void VisitIntegerVariable(const IntVar *const variable, IntExpr *const delegate)
static const char kSumEqual[]
static const char kSortingConstraint[]
static const char kElementEqual[]
static const char kPack[]
static const char kIsBetween[]
static const char kRangeArgument[]
static const char kLess[]
static const char kAtMost[]
static const char kDisjunctive[]
static const char kTargetArgument[]
static const char kActiveArgument[]
argument names:
static const char kRelaxedMaxOperation[]
static const char kSequenceArgument[]
static const char kAbsEqual[]
static const char kTimeLimitArgument[]
static const char kIntegerVariable[]
static const char kNullIntersect[]
virtual void VisitIntervalArgument(const std::string &arg_name, IntervalVar *const argument)
Visit interval argument.
static const char kConvexPiecewise[]
static const char kBranchesLimitArgument[]
static const char kMaxArgument[]
static const char kModulo[]
static const char kCapacityArgument[]
static const char kProductOperation[]
static const char kBetween[]
static const char kIntervalsArgument[]
static const char kIntervalUnaryRelation[]
static const char kScalProd[]
static const char kTrueConstraint[]
static const char kOpposite[]
virtual void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
virtual void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
static const char kEvaluatorArgument[]
static const char kPositionXArgument[]
static const char kCumulsArgument[]
static const char kCircuit[]
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64 index_min, int64 index_max)
static const char kWeightedSumOfAssignedEqualVariableExtension[]
virtual void VisitIntegerVariableEvaluatorArgument(const std::string &arg_name, const Solver::Int64ToIntVar &arguments)
Helpers.
static const char kRelaxedMinOperation[]
static const char kMapDomain[]
static const char kLessOrEqual[]
static const char kSizeXArgument[]
static const char kModuloArgument[]
static const char kEndMaxArgument[]
static const char kSmartTimeCheckArgument[]
static const char kValueArgument[]
static const char kIntervalDisjunction[]
static const char kDemandsArgument[]
static const char kTraceOperation[]
static const char kSemiContinuous[]
static const char kIsGreater[]
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *const constraint)
static const char kRelationArgument[]
static const char kEarlyCostArgument[]
static const char kVarValueWatcher[]
static const char kDurationExpr[]
static const char kIsDifferent[]
static const char kGreaterOrEqual[]
static const char kLeftArgument[]
static const char kGlobalCardinality[]
static const char kLexLess[]
virtual void BeginVisitExtension(const std::string &type)
static const char kNextsArgument[]
static const char kTransitsArgument[]
static const char kTransition[]
static const char kStartSyncOnStartOperation[]
static const char kStartMinArgument[]
static const char kUsageLessConstantExtension[]
virtual void EndVisitExtension(const std::string &type)
static const char kCumulativeArgument[]
static const char kStepArgument[]
static const char kLateCostArgument[]
static const char kMaxEqual[]
virtual void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64 > &values)
static const char kSumLessOrEqual[]
static const char kTuplesArgument[]
static const char kCountArgument[]
static const char kUsageEqualVariableExtension[]
virtual void VisitIntegerArgument(const std::string &arg_name, int64 value)
Visit integer arguments.
static const char kStartMaxArgument[]
static const char kAllowedAssignments[]
virtual void EndVisitModel(const std::string &type_name)
static const char kIsGreaterOrEqual[]
static const char kPathCumul[]
static const char kDifferenceOperation[]
static const char kVarsArgument[]
static const char kSumOperation[]
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
static const char kTrace[]
static const char kRightArgument[]
static const char kIsLess[]
static const char kIsLessOrEqual[]
static const char kVariableGroupExtension[]
static const char kIndexOf[]
static const char kEndExpr[]
static const char kNotMember[]
static const char kStartsArgument[]
static const char kElement[]
static const char kSizeYArgument[]
static const char kCountEqual[]
static const char kPartialArgument[]
static const char kExpressionArgument[]
static const char kDistribute[]
static const char kFailuresLimitArgument[]
static const char kScalProdGreaterOrEqual[]
static const char kPositionYArgument[]
static const char kVarBoundWatcher[]
virtual void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments)
static const char kDivide[]
static const char kInt64ToBoolExtension[]
static const char kIntervalBinaryRelation[]
virtual void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &tuples)
static const char kCardsArgument[]
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *const argument)
Visit integer expression argument.
static const char kNoCycle[]
static const char kGreater[]
virtual void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments)
static const char kCover[]
void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64 index_min, int64 index_max)
Using SWIG on callbacks is troublesome, so we hide these methods during the wrapping.
static const char kNotBetween[]
static const char kCoefficientsArgument[]
static const char kScalProdLessOrEqual[]
static const char kEndMinArgument[]
static const char kVariableArgument[]
static const char kValuesArgument[]
static const char kMinEqual[]
static const char kEquality[]
static const char kInt64ToInt64Extension[]
static const char kSequencesArgument[]
static const char kSumGreaterOrEqual[]
static const char kFixedChargeArgument[]
void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1 &eval, const std::string &arg_name, int64 index_max)
Expands function as array when index min is 0.
static const char kDurationMaxArgument[]
static const char kLinkExprVar[]
static const char kScalProdEqual[]
static const char kProduct[]
static const char kDifference[]
static const char kCumulative[]
static const char kAllDifferent[]
static const char kSquare[]
static const char kAssumePathsArgument[]
static const char kInitialState[]
static const char kNonEqual[]
static const char kConditionalExpr[]
static const char kIsEqual[]
static const char kStartSyncOnEndOperation[]
static const char kOptionalArgument[]
static const char kIndexArgument[]
static const char kFalseConstraint[]
static const char kPerformedExpr[]
virtual void VisitSequenceArgument(const std::string &arg_name, SequenceVar *const argument)
Visit sequence argument.
static const char kSearchLimitExtension[]
virtual void BeginVisitModel(const std::string &type_name)
--— Virtual methods for visitors --—
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *const constraint)
static const char kInversePermutation[]
static const char kCountAssignedItemsExtension[]
Extension names:
Subclass of RevArray<T> which adds numerical operations.
void Decr(Solver *const s, int index)
NumericalRevArray(int size, const T &val)
void Add(Solver *const s, int index, const T &to_add)
void Incr(Solver *const s, int index)
Subclass of Rev<T> which adds numerical operations.
NumericalRev(const T &val)
void Decr(Solver *const s)
void Incr(Solver *const s)
void Add(Solver *const s, const T &to_add)
This class encapsulates an objective.
void EnterSearch() override
Beginning of the search.
int64 best() const
Returns the best value found during search.
void BeginNextDecision(DecisionBuilder *const db) override
Before calling DecisionBuilder::Next.
bool found_initial_solution_
IntVar * Var() const
Returns the variable that is optimized.
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
bool AcceptSolution() override
This method is called when a solution is found.
virtual std::string Print() const
bool AtSolution() override
This method is called when a valid solution is found.
void RefuteDecision(Decision *const d) override
Before refuting the decision.
OptimizeVar(Solver *const s, bool maximize, IntVar *const a, int64 step)
bool AcceptDelta(Assignment *delta, Assignment *deltadelta) override
Internal methods.
std::string DebugString() const override
void AddWeightedSumOfAssignedDimension(const std::vector< int64 > &weights, IntVar *const cost_var)
This dimension enforces that cost_var == sum of weights[i] for all objects 'i' assigned to a bin.
bool IsAssignedStatusKnown(int var_index) const
void Post() override
This method is called when the constraint is processed by the solver.
void AddCountAssignedItemsDimension(IntVar *const count_var)
This dimension links 'count_var' to the actual number of items assigned to a bin in the pack.
void InitialPropagate() override
This method performs the initial propagation of the constraint.
Pack(Solver *const s, const std::vector< IntVar * > &vars, int number_of_bins)
void SetImpossible(int var_index, int bin_index)
void SetAssigned(int var_index)
void AddWeightedSumEqualVarDimension(const std::vector< int64 > &weights, const std::vector< IntVar * > &loads)
This dimension imposes that for all bins b, the weighted sum (weights[i]) of all objects i assigned t...
bool IsUndecided(int var_index, int bin_index) const
bool IsPossible(int var_index, int bin_index) const
void AssignFirstPossibleToBin(int bin_index)
void AddCountUsedBinDimension(IntVar *const count_var)
This dimension links 'count_var' to the actual number of bins used in the pack.
void OneDomain(int var_index)
void SetUnassigned(int var_index)
void AddSumVariableWeightsLessOrEqualConstantDimension(const std::vector< IntVar * > &usage, const std::vector< int64 > &capacity)
This dimension imposes: forall b in bins, sum (i in items: usage[i] * is_assigned(i,...
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
void AssignAllPossibleToBin(int bin_index)
void Assign(int var_index, int bin_index)
void UnassignAllRemainingItems()
std::string DebugString() const override
void AssignAllRemainingItems()
void AddWeightedSumLessOrEqualConstantDimension(const std::vector< int64 > &weights, const std::vector< int64 > &bounds)
Dimensions are additional constraints than can restrict what is possible with the pack constraint.
IntVar * AssignVar(int var_index, int bin_index) const
void RemoveAllPossibleFromBin(int bin_index)
void EnqueueDelayedDemon(Demon *const d)
This method pushes the demon onto the propagation queue.
virtual std::string name() const
Object naming.
void reset_action_on_fail()
This method clears the failure callback.
bool HasName() const
Returns whether the object has been named or not.
void set_action_on_fail(Solver::Action a)
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
void EnqueueVar(Demon *const d)
void FreezeQueue()
This method freezes the propagation queue.
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
virtual std::string BaseName() const
Returns a base name for automatic naming.
~PropagationBaseObject() override
void set_variable_to_clean_on_fail(IntVar *v)
Shortcut for variable cleaner.
PropagationBaseObject(Solver *const s)
void set_name(const std::string &name)
void UnfreezeQueue()
This method unfreezes the propagation queue.
std::string DebugString() const override
Usual limit based on wall_time, number of explored branches and number of failures in the search tree...
bool Check() override
This method is called to check the status of the limit.
absl::Duration duration_limit() const
bool IsUncheckedSolutionLimitReached() override
Returns true if the limit of solutions has been reached including unchecked solutions.
void Init() override
This method is called when the search limit is initialized.
void ExitSearch() override
End of the search.
RegularLimit(Solver *const s, absl::Duration time, int64 branches, int64 failures, int64 solutions, bool smart_time_check, bool cumulative)
int ProgressPercent() override
Returns a percentage representing the propress of the search before reaching limits.
absl::Time AbsoluteSolverDeadline() const
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
void Copy(const SearchLimit *const limit) override
Copy a limit.
void UpdateLimits(absl::Duration time, int64 branches, int64 failures, int64 solutions)
RegularLimit * MakeIdenticalClone() const
std::string DebugString() const override
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Reversible array of POD types.
const T & Value(int index) const
RevArray(int size, const T &val)
void SetValue(Solver *const s, int index, const T &val)
const T & operator[](int index) const
This class adds reversibility to a POD type.
void SetValue(Solver *const s, const T &val)
Reversible Immutable MultiMap class.
Base class of all search limits.
void EnterSearch() override
Internal methods.
SearchLimit(Solver *const s)
void PeriodicCheck() override
Periodic call to check limits in long running methods.
virtual void Init()=0
This method is called when the search limit is initialized.
void BeginNextDecision(DecisionBuilder *const b) override
Before calling DecisionBuilder::Next.
virtual void Copy(const SearchLimit *const limit)=0
Copy a limit.
virtual SearchLimit * MakeClone() const =0
Allocates a clone of the limit.
void RefuteDecision(Decision *const d) override
Before refuting the decision.
bool crossed() const
Returns true if the limit has been crossed.
std::string DebugString() const override
virtual bool Check()=0
This method is called to check the status of the limit.
A search monitor is a simple set of callbacks to monitor all search events.
virtual void RefuteDecision(Decision *const d)
Before refuting the decision.
SearchMonitor(Solver *const s)
virtual void ApplyDecision(Decision *const d)
Before applying the decision.
virtual void RestartSearch()
Restart the search.
virtual void ExitSearch()
End of the search.
virtual bool IsUncheckedSolutionLimitReached()
Returns true if the limit of solutions has been reached including unchecked solutions.
virtual bool LocalOptimum()
When a local optimum is reached.
virtual int ProgressPercent()
Returns a percentage representing the propress of the search before reaching limits.
virtual void NoMoreSolutions()
When the search tree is finished.
virtual void BeginFail()
Just when the failure occurs.
virtual void AfterDecision(Decision *const d, bool apply)
Just after refuting or applying the decision, apply is true after Apply.
virtual void BeginInitialPropagation()
Before the initial propagation.
virtual void BeginNextDecision(DecisionBuilder *const b)
Before calling DecisionBuilder::Next.
virtual void PeriodicCheck()
Periodic call to check limits in long running methods.
virtual void EnterSearch()
Beginning of the search.
~SearchMonitor() override
virtual void EndNextDecision(DecisionBuilder *const b, Decision *const d)
After calling DecisionBuilder::Next, along with the returned decision.
virtual void EndFail()
After completing the backtrack.
virtual void EndInitialPropagation()
After the initial propagation.
static constexpr int kNoProgress
virtual void AcceptUncheckedNeighbor()
After accepting an unchecked neighbor during local search.
virtual bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
virtual bool AtSolution()
This method is called when a valid solution is found.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
virtual void AcceptNeighbor()
After accepting a neighbor during local search.
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
virtual bool AcceptSolution()
This method is called when a solution is found.
The SequenceVarElement stores a partial representation of ranked interval variables in the underlying...
void SetSequence(const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
void Reset(SequenceVar *const var)
bool operator==(const SequenceVarElement &element) const
const std::vector< int > & BackwardSequence() const
bool operator!=(const SequenceVarElement &element) const
void SetBackwardSequence(const std::vector< int > &backward_sequence)
const std::vector< int > & Unperformed() const
void SetUnperformed(const std::vector< int > &unperformed)
std::string DebugString() const
SequenceVarElement * Clone()
SequenceVar * Var() const
const std::vector< int > & ForwardSequence() const
void Copy(const SequenceVarElement &element)
void LoadFromProto(const SequenceVarAssignment &sequence_var_assignment_proto)
void WriteToProto(SequenceVarAssignment *sequence_var_assignment_proto) const
void SetForwardSequence(const std::vector< int > &forward_sequence)
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
void ComputePossibleFirstsAndLasts(std::vector< int > *const possible_firsts, std::vector< int > *const possible_lasts)
Computes the set of indices of interval variables that can be ranked first in the set of unranked act...
void FillSequence(std::vector< int > *const rank_first, std::vector< int > *const rank_last, std::vector< int > *const unperformed) const
Clears 'rank_first' and 'rank_last', and fills them with the intervals in the order of the ranks.
void RankSequence(const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)
Applies the following sequence of ranks, ranks first, then rank last.
void ComputeStatistics(int *const ranked, int *const not_ranked, int *const unperformed) const
Compute statistics on the sequence.
void ActiveHorizonRange(int64 *const hmin, int64 *const hmax) const
Returns the minimum start min and the maximum end max of all unranked interval vars in the sequence.
void HorizonRange(int64 *const hmin, int64 *const hmax) const
Returns the minimum start min and the maximum end max of all interval vars in the sequence.
int64 size() const
Returns the number of interval vars in the sequence.
IntVar * Next(int index) const
Returns the next of the index_th interval of the sequence.
IntervalVar * Interval(int index) const
Returns the index_th interval of the sequence.
void RankLast(int index)
Ranks the index_th interval var first of all unranked interval vars.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
void DurationRange(int64 *const dmin, int64 *const dmax) const
Returns the minimum and maximum duration of combined interval vars in the sequence.
void RankFirst(int index)
Ranks the index_th interval var first of all unranked interval vars.
void RankNotLast(int index)
Indicates that the index_th interval var will not be ranked first of all currently unranked interval ...
void RankNotFirst(int index)
Indicates that the index_th interval var will not be ranked first of all currently unranked interval ...
SequenceVar(Solver *const s, const std::vector< IntervalVar * > &intervals, const std::vector< IntVar * > &nexts, const std::string &name)
std::string DebugString() const override
This class represent a reversible FIFO structure.
This class is the root class of all solution collectors.
void check_index(int n) const
void EnterSearch() override
Beginning of the search.
int64 Value(int n, IntVar *const var) const
This is a shortcut to get the Value of 'var' in the nth solution.
int64 failures(int n) const
Returns the number of failures encountered at the time of the nth solution.
~SolutionCollector() override
void Push(const SolutionData &data)
void PushSolution()
Push the current state as a new solution.
void AddObjective(IntVar *const objective)
std::vector< Assignment * > recycle_solutions_
std::vector< SolutionData > solution_data_
void Add(IntVar *const var)
Add API.
int solution_count() const
Returns how many solutions were stored during the search.
int64 DurationValue(int n, IntervalVar *const var) const
This is a shortcut to get the DurationValue of 'var' in the nth solution.
int64 PerformedValue(int n, IntervalVar *const var) const
This is a shortcut to get the PerformedValue of 'var' in the nth solution.
const std::vector< int > & Unperformed(int n, SequenceVar *const var) const
This is a shortcut to get the list of unperformed of 'var' in the nth solution.
SolutionData BuildSolutionDataForCurrentState()
Assignment * solution(int n) const
Returns the nth solution.
int64 wall_time(int n) const
Returns the wall time in ms for the nth solution.
int64 EndValue(int n, IntervalVar *const var) const
This is a shortcut to get the EndValue of 'var' in the nth solution.
const std::vector< int > & ForwardSequence(int n, SequenceVar *const var) const
This is a shortcut to get the ForwardSequence of 'var' in the nth solution.
int64 objective_value(int n) const
Returns the objective value of the nth solution.
void FreeSolution(Assignment *solution)
std::unique_ptr< Assignment > prototype_
SolutionCollector(Solver *const solver, const Assignment *assignment)
int64 branches(int n) const
Returns the number of branches when the nth solution was found.
void PopSolution()
Remove and delete the last popped solution.
std::string DebugString() const override
const std::vector< int > & BackwardSequence(int n, SequenceVar *const var) const
This is a shortcut to get the BackwardSequence of 'var' in the nth solution.
int64 StartValue(int n, IntervalVar *const var) const
This is a shortcut to get the StartValue of 'var' in the nth solution.
This class is used to manage a pool of solutions.
virtual bool SyncNeeded(Assignment *const local_assignment)=0
This method checks if the local solution needs to be updated with an external one.
virtual void RegisterNewSolution(Assignment *const assignment)=0
This method is called when a new solution has been accepted by the local search.
virtual void GetNextSolution(Assignment *const assignment)=0
This method is called when the local search starts a new neighborhood to initialize the default assig...
virtual void Initialize(Assignment *const assignment)=0
This method is called to initialize the solution pool with the assignment from the local search.
SolverState state() const
State of the solver.
Decision * MakeDecision(Action apply, Action refute)
std::function< bool(int64)> IndexFilter1
IntExpr * MakeElement(const std::vector< int64 > &values, IntVar *const index)
values[index]
SearchMonitor * MakeLubyRestart(int scale_factor)
This search monitor will restart the search periodically.
Constraint * MakeMemberCt(IntExpr *const expr, const std::vector< int64 > &values)
expr in set.
void SaveValue(T *o)
reversibility
SolutionCollector * MakeAllSolutionCollector()
Collect all solutions of the search.
DecisionModification
The Solver is responsible for creating the search tree.
@ NO_CHANGE
Keeps the default behavior, i.e.
@ SWITCH_BRANCHES
Applies right branch first.
@ KEEP_RIGHT
Left branches are ignored.
@ KEEP_LEFT
Right branches are ignored.
@ KILL_BOTH
Backtracks to the previous decisions, i.e.
bool IsBooleanVar(IntExpr *const expr, IntVar **inner_var, bool *is_negated) const
Returns true if expr represents either boolean_var or 1 - boolean_var.
RegularLimit * MakeLimit(absl::Duration time, int64 branches, int64 failures, int64 solutions, bool smart_time_check=false, bool cumulative=false)
Limits the search with the 'time', 'branches', 'failures' and 'solutions' limits.
void MakeBoolVarArray(int var_count, const std::string &name, std::vector< IntVar * > *vars)
This method will append the vector vars with 'var_count' boolean variables having name "name<i>" wher...
LocalSearchFilter * MakeVariableDomainFilter()
Decision * MakeSplitVariableDomain(IntVar *const var, int64 val, bool start_with_lower_half)
bool HasName(const PropagationBaseObject *object) const
Returns whether the object has been named or not.
Constraint * MakeDeviation(const std::vector< IntVar * > &vars, IntVar *const deviation_var, int64 total_sum)
Deviation constraint: sum_i |n * vars[i] - total_sum| <= deviation_var and sum_i vars[i] == total_sum...
std::vector< int64 > tmp_vector_
Unsafe temporary vector.
void ClearLocalSearchState()
Clears the local search state.
OptimizeVar * MakeWeightedMaximize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a maximization weigthed objective.
DemonProfiler * demon_profiler() const
Access to demon profiler.
SolutionCollector * MakeLastSolutionCollector()
Collect the last solution of the search.
RegularLimit * MakeSolutionsLimit(int64 solutions)
Creates a search limit that constrains the number of solutions found during the search.
Decision * MakeAssignVariableValue(IntVar *const var, int64 val)
Decisions.
SearchMonitor * MakeAtSolutionCallback(std::function< void()> callback)
IntExpr * RegisterIntExpr(IntExpr *const expr)
Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
IntVar * MakeIsGreaterOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var >= value)
void RestartCurrentSearch()
SearchLimit * MakeCustomLimit(std::function< bool()> limiter)
Callback-based search limit.
friend class DemonProfiler
Constraint * MakeNullIntersectExcept(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars, int64 escape_value)
Creates a constraint that states that all variables in the first vector are different from all variab...
bool SolveAndCommit(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolveAndCommit using a decision builder and up to three search monitors, usually one for the objectiv...
Constraint * MakeLess(IntExpr *const left, IntExpr *const right)
left < right
Constraint * MakeIntervalVarRelation(IntervalVar *const t, UnaryIntervalRelation r, int64 d)
This method creates a relation between an interval var and a date.
friend void InternalSaveBooleanVarValue(Solver *const, IntVar *const)
LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)
Creates a local search operator that tries to move the assignment of some variables toward a target.
Constraint * MakeSubCircuit(const std::vector< IntVar * > &nexts)
Force the "nexts" variable to create a complete Hamiltonian path for those that do not loop upon them...
IntExpr * MakeAbs(IntExpr *const expr)
|expr|
Constraint * MakeFalseConstraint()
This constraint always fails.
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
Constraint * MakeIsDifferentCt(IntExpr *const v1, IntExpr *const v2, IntVar *const b)
b == (v1 != v2)
Constraint * MakeLessOrEqual(IntExpr *const left, IntExpr *const right)
left <= right
IntExpr * MakePiecewiseLinearExpr(IntExpr *expr, const PiecewiseLinearFunction &f)
General piecewise-linear function expression, built from f(x) where f is piecewise-linear.
int64 solutions() const
The number of solutions found since the start of the search.
ConstraintSolverStatistics GetConstraintSolverStatistics() const
Returns detailed cp search statistics.
Constraint * MakeNullIntersect(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars)
Creates a constraint that states that all variables in the first vector are different from all variab...
DisjunctiveConstraint * MakeStrictDisjunctiveConstraint(const std::vector< IntervalVar * > &intervals, const std::string &name)
This constraint forces all interval vars into an non-overlapping sequence.
IntVar * MakeIsGreaterVar(IntExpr *const left, IntExpr *const right)
status var of (left > right)
LocalSearchStatistics GetLocalSearchStatistics() const
Returns detailed local search statistics.
IntExpr * MakeMin(const std::vector< IntVar * > &vars)
std::min(vars)
Constraint * MakeIsLessCstCt(IntExpr *const v, int64 c, IntVar *const b)
b == (v < c)
static constexpr int kNumPriorities
Number of priorities for demons.
Decision * MakeAssignVariableValueOrFail(IntVar *const var, int64 value)
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
@ NORMAL_PRIORITY
NORMAL_PRIORITY is the highest priority: Demons will be processed first.
OptimizeVar * MakeMaximize(IntVar *const v, int64 step)
Creates a maximization objective.
ConstraintSolverParameters parameters() const
Stored Parameters.
int64 failures() const
The number of failures encountered since the creation of the solver.
Constraint * MakeIndexOfFirstMinValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
Creates a constraint that binds the index variable to the index of the first variable with the minimu...
SearchMonitor * MakeSymmetryManager(const std::vector< SymmetryBreaker * > &visitors)
Symmetry Breaking.
SolverState
This enum represents the state of the solver w.r.t. the search.
@ AT_SOLUTION
After successful NextSolution and before EndSearch.
@ PROBLEM_INFEASIBLE
After search, the model is infeasible.
@ OUTSIDE_SEARCH
Before search, after search.
@ IN_ROOT_NODE
Executing the root node.
@ NO_MORE_SOLUTIONS
After failed NextSolution and before EndSearch.
@ IN_SEARCH
Executing the search code.
int64 demon_runs(DemonPriority p) const
The number of demons executed during search for a given priority.
Constraint * MakeAbsEquality(IntVar *const var, IntVar *const abs_var)
Creates the constraint abs(var) == abs_var.
std::function< bool(int64, int64, int64)> VariableValueComparator
std::string SearchContext() const
bool CheckAssignment(Assignment *const solution)
Checks whether the given assignment satisfies all relevant constraints.
IntVar * RegisterIntVar(IntVar *const var)
Registers a new IntVar and wraps it inside a TraceIntVar if necessary.
SearchMonitor * MakeGenericTabuSearch(bool maximize, IntVar *const v, int64 step, const std::vector< IntVar * > &tabu_vars, int64 forbid_tenure)
Creates a Tabu Search based on the vars |vars|.
SearchMonitor * MakeSimulatedAnnealing(bool maximize, IntVar *const v, int64 step, int64 initial_temperature)
Creates a Simulated Annealing monitor.
absl::Time Now() const
The 'absolute time' as seen by the solver.
IntVar * MakeIsDifferentVar(IntExpr *const v1, IntExpr *const v2)
status var of (v1 != v2)
IntVar * MakeIsEqualVar(IntExpr *const v1, IntExpr *v2)
status var of (v1 == v2)
Constraint * MakeNotBetweenCt(IntExpr *const expr, int64 l, int64 u)
(expr < l || expr > u) This constraint is lazy as it will not make holes in the domain of variables.
DecisionBuilder * MakeConstraintAdder(Constraint *const ct)
Returns a decision builder that will add the given constraint to the model.
Constraint * MakeCircuit(const std::vector< IntVar * > &nexts)
Force the "nexts" variable to create a complete Hamiltonian path.
OptimizationDirection
Optimization directions.
IntervalStrategy
This enum describes the straregy used to select the next interval variable and its value to be fixed.
@ INTERVAL_SET_TIMES_FORWARD
Selects the variable with the lowest starting time of all variables, and fixes its starting time to t...
@ INTERVAL_SIMPLE
The simple is INTERVAL_SET_TIMES_FORWARD.
@ INTERVAL_SET_TIMES_BACKWARD
Selects the variable with the highest ending time of all variables, and fixes the ending time to this...
@ INTERVAL_DEFAULT
The default is INTERVAL_SET_TIMES_FORWARD.
Constraint * MakeGreater(IntExpr *const left, IntExpr *const right)
left > right
Pack * MakePack(const std::vector< IntVar * > &vars, int number_of_bins)
This constraint packs all variables onto 'number_of_bins' variables.
Assignment * GetOrCreateLocalSearchState()
Returns (or creates) an assignment representing the state of local search.
Constraint * MakeTransitionConstraint(const std::vector< IntVar * > &vars, const IntTupleSet &transition_table, int64 initial_state, const std::vector< int64 > &final_states)
This constraint create a finite automaton that will check the sequence of variables vars.
bool IsProfilingEnabled() const
Returns whether we are profiling the solver.
Demon * MakeActionDemon(Action action)
Creates a demon from a callback.
DecisionBuilder * Try(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which will create a search tree where each decision builder is called from...
uint64 fail_stamp() const
The fail_stamp() is incremented after each backtrack.
Constraint * MakeLexicalLess(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that left is lexicographically less than right.
void AddPropagationMonitor(PropagationMonitor *const monitor)
Adds the propagation monitor to the solver.
Constraint * MakeBetweenCt(IntExpr *const expr, int64 l, int64 u)
(l <= expr <= u)
Constraint * MakeIsEqualCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var == value)
RegularLimit * MakeFailuresLimit(int64 failures)
Creates a search limit that constrains the number of failures that can happen when exploring the sear...
SearchMonitor * MakeSearchLog(int branch_period)
The SearchMonitors below will display a periodic search log on LOG(INFO) every branch_period branches...
IntValueStrategy
This enum describes the strategy used to select the next variable value to set.
@ INT_VALUE_SIMPLE
The simple selection is ASSIGN_MIN_VALUE.
@ ASSIGN_CENTER_VALUE
Selects the first possible value which is the closest to the center of the domain of the selected var...
@ SPLIT_UPPER_HALF
Split the domain in two around the center, and choose the lower part first.
@ ASSIGN_MIN_VALUE
Selects the min value of the selected variable.
@ ASSIGN_RANDOM_VALUE
Selects randomly one of the possible values of the selected variable.
@ INT_VALUE_DEFAULT
The default behavior is ASSIGN_MIN_VALUE.
@ ASSIGN_MAX_VALUE
Selects the max value of the selected variable.
@ SPLIT_LOWER_HALF
Split the domain in two around the center, and choose the lower part first.
IntExpr * MakePower(IntExpr *const expr, int64 n)
expr ^ n (n > 0)
UnaryIntervalRelation
This enum is used in Solver::MakeIntervalVarRelation to specify the temporal relation between an inte...
@ ENDS_BEFORE
t ends before d, i.e. End(t) <= d.
@ AVOID_DATE
STARTS_AFTER or ENDS_BEFORE, i.e.
@ ENDS_AFTER
t ends after d, i.e. End(t) >= d.
@ STARTS_BEFORE
t starts before d, i.e. Start(t) <= d.
@ STARTS_AT
t starts at d, i.e. Start(t) == d.
@ ENDS_AT
t ends at d, i.e. End(t) == d.
@ STARTS_AFTER
t starts after d, i.e. Start(t) >= d.
@ CROSS_DATE
STARTS_BEFORE and ENDS_AFTER at the same time, i.e.
Constraint * MakeDelayedPathCumul(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, const std::vector< IntVar * > &cumuls, const std::vector< IntVar * > &transits)
Delayed version of the same constraint: propagation on the nexts variables is delayed until all const...
bool CheckConstraint(Constraint *const ct)
Checks whether adding this constraint will lead to an immediate failure.
IntVar * MakeIsDifferentCstVar(IntExpr *const var, int64 value)
status var of (var != value)
Constraint * MakeCover(const std::vector< IntervalVar * > &vars, IntervalVar *const target_var)
This constraint states that the target_var is the convex hull of the intervals.
void SetSearchContext(Search *search, const std::string &search_context)
Constraint * MakeIsGreaterCstCt(IntExpr *const v, int64 c, IntVar *const b)
b == (v > c)
Decision * MakeAssignVariablesValues(const std::vector< IntVar * > &vars, const std::vector< int64 > &values)
Constraint * MakeCumulative(const std::vector< IntervalVar * > &intervals, const std::vector< int64 > &demands, int64 capacity, const std::string &name)
This constraint forces that, for any integer t, the sum of the demands corresponding to an interval c...
Constraint * MakeNonOverlappingBoxesConstraint(const std::vector< IntVar * > &x_vars, const std::vector< IntVar * > &y_vars, const std::vector< IntVar * > &x_size, const std::vector< IntVar * > &y_size)
This constraint states that all the boxes must not overlap.
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
DecisionBuilder * MakeApplyBranchSelector(BranchSelector bs)
Creates a decision builder that will set the branch selector.
Constraint * MakeAllDifferentExcept(const std::vector< IntVar * > &vars, int64 escape_value)
All variables are pairwise different, unless they are assigned to the escape value.
int64 Rand64(int64 size)
Returns a random value between 0 and 'size' - 1;.
void SetUseFastLocalSearch(bool use_fast_local_search)
enabled for metaheuristics.
Decision * MakeAssignVariableValueOrDoNothing(IntVar *const var, int64 value)
IntervalVar * MakeIntervalRelaxedMin(IntervalVar *const interval_var)
Creates and returns an interval variable that wraps around the given one, relaxing the min start and ...
RegularLimit * MakeTimeLimit(int64 time_in_ms)
IntervalVar * MakeFixedDurationEndSyncedOnEndIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose end is synchronized with the end of another inter...
Constraint * MakePathConnected(std::vector< IntVar * > nexts, std::vector< int64 > sources, std::vector< int64 > sinks, std::vector< IntVar * > status)
Constraint enforcing that status[i] is true iff there's a path defined on next variables from sources...
Demon * MakeClosureDemon(Closure closure)
!defined(SWIG)
void AddConstraint(Constraint *const c)
Adds the constraint 'c' to the model.
DecisionBuilder * MakeSolveOnce(DecisionBuilder *const db)
SolveOnce will collapse a search tree described by a decision builder 'db' and a set of monitors and ...
LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Creates a local search operator which concatenates a vector of operators.
IntervalVar * MakeFixedInterval(int64 start, int64 duration, const std::string &name)
Creates a fixed and performed interval.
LocalSearchFilter * MakeRejectFilter()
LocalSearchFilter * MakeAcceptFilter()
Local Search Filters.
LocalSearchOperator * MakeRandomLnsOperator(const std::vector< IntVar * > &vars, int number_of_variables)
Creates a large neighborhood search operator which creates fragments (set of relaxed variables) with ...
friend class LocalSearchProfiler
Constraint * MakeIsLessCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left < right)
Decision * MakeVariableLessOrEqualValue(IntVar *const var, int64 value)
DisjunctiveConstraint * MakeDisjunctiveConstraint(const std::vector< IntervalVar * > &intervals, const std::string &name)
This constraint forces all interval vars into an non-overlapping sequence.
void ShouldFail()
These methods are only useful for the SWIG wrappers, which need a way to externally cause the Solver ...
int SearchDepth() const
Gets the search depth of the current active search.
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
IntVar * MakeIsMemberVar(IntExpr *const expr, const std::vector< int64 > &values)
void AddLocalSearchMonitor(LocalSearchMonitor *monitor)
Adds the local search monitor to the solver.
LocalSearchOperator * RandomConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Randomized version of local search concatenator; calls a random operator at each call to MakeNextNeig...
IntVar * MakeIsEqualCstVar(IntExpr *const var, int64 value)
status var of (var == value)
Constraint * MakeScalProdLessOrEqual(const std::vector< IntVar * > &vars, const std::vector< int64 > &coefficients, int64 cst)
Constraint * MakeNotMemberCt(IntExpr *const expr, const std::vector< int64 > &values)
expr not in set.
BinaryIntervalRelation
This enum is used in Solver::MakeIntervalVarRelation to specify the temporal relation between the two...
@ ENDS_AFTER_END
t1 ends after t2 end, i.e. End(t1) >= End(t2) + delay.
@ ENDS_AFTER_START
t1 ends after t2 start, i.e. End(t1) >= Start(t2) + delay.
@ STAYS_IN_SYNC
STARTS_AT_START and ENDS_AT_END at the same time.
@ ENDS_AT_END
t1 ends at t2 end, i.e. End(t1) == End(t2) + delay.
@ STARTS_AT_END
t1 starts at t2 end, i.e. Start(t1) == End(t2) + delay.
@ ENDS_AT_START
t1 ends at t2 start, i.e. End(t1) == Start(t2) + delay.
@ STARTS_AFTER_END
t1 starts after t2 end, i.e. Start(t1) >= End(t2) + delay.
@ STARTS_AFTER_START
t1 starts after t2 start, i.e. Start(t1) >= Start(t2) + delay.
@ STARTS_AT_START
t1 starts at t2 start, i.e. Start(t1) == Start(t2) + delay.
Constraint * MakeMaxEquality(const std::vector< IntVar * > &vars, IntVar *const max_var)
LocalSearchOperators
This enum is used in Solver::MakeOperator to specify the neighborhood to create.
@ EXCHANGE
Operator which exchanges the positions of two nodes.
@ MAKEINACTIVE
Operator which makes path nodes inactive.
@ RELOCATE
Relocate neighborhood with length of 1 (see OROPT comment).
@ SWAPACTIVE
Operator which replaces an active node by an inactive one.
@ SIMPLELNS
Operator which defines one neighbor per variable.
@ INCREMENT
Operator which defines one neighbor per variable.
@ MAKECHAININACTIVE
Operator which makes a "chain" of path nodes inactive.
@ TWOOPT
Operator which reverses a sub-chain of a path.
@ FULLPATHLNS
Operator which relaxes one entire path and all inactive nodes, thus defining num_paths neighbors.
@ EXTENDEDSWAPACTIVE
Operator which makes an inactive node active and an active one inactive.
@ OROPT
Relocate: OROPT and RELOCATE.
@ PATHLNS
Operator which relaxes two sub-chains of three consecutive arcs each.
@ UNACTIVELNS
Operator which relaxes all inactive nodes and one sub-chain of six consecutive arcs.
@ MAKEACTIVE
Operator which inserts an inactive node into a path.
@ DECREMENT
Operator which defines a neighborhood to decrement values.
@ CROSS
Operator which cross exchanges the starting chains of 2 paths, including exchanging the whole paths.
Constraint * MakeIsEqualCt(IntExpr *const v1, IntExpr *v2, IntVar *const b)
b == (v1 == v2)
LocalSearchPhaseParameters * MakeLocalSearchPhaseParameters(IntVar *objective, LocalSearchOperator *const ls_operator, DecisionBuilder *const sub_decision_builder)
Local Search Phase Parameters.
IntExpr * MakeOpposite(IntExpr *const expr)
-expr
void PushState()
The PushState and PopState methods manipulates the states of the reversible objects.
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
OptimizeVar * MakeWeightedOptimize(bool maximize, const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a weighted objective with a given sense (true = maximization).
IntVarLocalSearchFilter * MakeSumObjectiveFilter(const std::vector< IntVar * > &vars, IndexEvaluator2 values, Solver::LocalSearchFilterBound filter_enum)
LocalSearchOperator * MakeNeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
Creates a local search operator that wraps another local search operator and limits the number of nei...
Constraint * MakeIfThenElseCt(IntVar *const condition, IntExpr *const then_expr, IntExpr *const else_expr, IntVar *const target_var)
Special cases with arrays of size two.
Decision * MakeScheduleOrExpedite(IntervalVar *const var, int64 est, int64 *const marker)
Returns a decision that tries to schedule a task at a given time.
Demon * MakeConstraintInitialPropagateCallback(Constraint *const ct)
This method is a specialized case of the MakeConstraintDemon method to call the InitiatePropagate of ...
std::string DebugString() const
!defined(SWIG)
Constraint * MakeTrueConstraint()
This constraint always succeeds.
IntervalVar * MakeFixedDurationEndSyncedOnStartIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose end is synchronized with the start of another int...
Demon * RegisterDemon(Demon *const demon)
Adds a new demon and wraps it inside a DemonProfiler if necessary.
IntExpr * MakeModulo(IntExpr *const x, int64 mod)
Modulo expression x % mod (with the python convention for modulo).
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
IntExpr * MakeConditionalExpression(IntVar *const condition, IntExpr *const expr, int64 unperformed_value)
Conditional Expr condition ? expr : unperformed_value.
Constraint * MakeIsBetweenCt(IntExpr *const expr, int64 l, int64 u, IntVar *const b)
b == (l <= expr <= u)
IntervalVar * MakeIntervalRelaxedMax(IntervalVar *const interval_var)
Creates and returns an interval variable that wraps around the given one, relaxing the max start and ...
int64 wall_time() const
DEPRECATED: Use Now() instead.
Constraint * MakeDistribute(const std::vector< IntVar * > &vars, const std::vector< int64 > &values, const std::vector< IntVar * > &cards)
Aggregated version of count: |{i | v[i] == values[j]}| == cards[j].
RegularLimit * MakeBranchesLimit(int64 branches)
Creates a search limit that constrains the number of branches explored in the search tree.
ImprovementSearchLimit * MakeImprovementLimit(IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
Limits the search based on the improvements of 'objective_var'.
Constraint * MakeAtMost(std::vector< IntVar * > vars, int64 value, int64 max_count)
|{i | vars[i] == value}| <= max_count
ModelVisitor * MakeVariableDegreeVisitor(absl::flat_hash_map< const IntVar *, int > *const map)
Compute the number of constraints a variable is attached to.
int64 accepted_neighbors() const
The number of accepted neighbors.
SearchMonitor * MakeConstantRestart(int frequency)
This search monitor will restart the search periodically after 'frequency' failures.
std::function< int64(int64, int64, int64)> IndexEvaluator3
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
int constraints() const
Counts the number of constraints that have been added to the solver before the search.
Constraint * MakeSumEquality(const std::vector< IntVar * > &vars, int64 cst)
Constraint * MakeLexicalLessOrEqual(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that left is lexicographically less than or equal to right.
void MakeFixedDurationIntervalVarArray(int count, int64 start_min, int64 start_max, int64 duration, bool optional, const std::string &name, std::vector< IntervalVar * > *const array)
This method fills the vector with 'count' interval variables built with the corresponding parameters.
EvaluatorStrategy
This enum is used by Solver::MakePhase to specify how to select variables and values during the searc...
@ CHOOSE_STATIC_GLOBAL_BEST
Pairs are compared at the first call of the selector, and results are cached.
@ CHOOSE_DYNAMIC_GLOBAL_BEST
Pairs are compared each time a variable is selected.
void set_optimization_direction(OptimizationDirection direction)
int SolveDepth() const
Gets the number of nested searches.
int64 neighbors() const
The number of neighbors created.
PropagationMonitor * GetPropagationMonitor() const
Returns the propagation monitor.
Decision * MakeRankFirstInterval(SequenceVar *const sequence, int index)
Returns a decision that tries to rank first the ith interval var in the sequence variable.
IntExpr * MakeMax(const std::vector< IntVar * > &vars)
std::max(vars)
Constraint * MakeIsLessOrEqualCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left <= right)
bool Solve(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolutionPool * MakeDefaultSolutionPool()
Solution Pool.
void clear_fail_intercept()
Constraint * MakeIntervalVarRelationWithDelay(IntervalVar *const t1, BinaryIntervalRelation r, IntervalVar *const t2, int64 delay)
This method creates a relation between two interval vars.
Constraint * MakeScalProdGreaterOrEqual(const std::vector< IntVar * > &vars, const std::vector< int64 > &coeffs, int64 cst)
IntExpr * MakeDifference(IntExpr *const left, IntExpr *const right)
left - right
std::string model_name() const
Returns the name of the model.
void MakeIntVarArray(int var_count, int64 vmin, int64 vmax, const std::string &name, std::vector< IntVar * > *vars)
This method will append the vector vars with 'var_count' variables having bounds vmin and vmax and ha...
RegularLimitParameters MakeDefaultRegularLimitParameters() const
Creates a regular limit proto containing default values.
RegularLimit * MakeTimeLimit(absl::Duration time)
Creates a search limit that constrains the running time.
Decision * MakeVariableGreaterOrEqualValue(IntVar *const var, int64 value)
IntVar * MakeBoolVar()
MakeBoolVar will create a variable with a {0, 1} domain.
bool UseFastLocalSearch() const
Returns true if fast local search is enabled.
bool InstrumentsVariables() const
Returns whether we are tracing variables.
Decision * MakeScheduleOrPostpone(IntervalVar *const var, int64 est, int64 *const marker)
Returns a decision that tries to schedule a task at a given time.
SearchMonitor * MakeSearchTrace(const std::string &prefix)
Creates a search monitor that will trace precisely the behavior of the search.
IntExpr * MakeDiv(IntExpr *const expr, int64 value)
expr / value (integer division)
SearchMonitor * MakeGuidedLocalSearch(bool maximize, IntVar *const objective, IndexEvaluator2 objective_function, int64 step, const std::vector< IntVar * > &vars, double penalty_factor)
Creates a Guided Local Search monitor.
int64 filtered_neighbors() const
The number of filtered neighbors (neighbors accepted by filters).
std::function< int64(int64)> IndexEvaluator1
Callback typedefs.
Constraint * MakeNonEquality(IntExpr *const left, IntExpr *const right)
left != right
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
IntVar * MakeIsLessVar(IntExpr *const left, IntExpr *const right)
status var of (left < right)
LocalSearchOperator * MakeOperator(const std::vector< IntVar * > &vars, LocalSearchOperators op)
Local Search Operators.
friend class SearchMonitor
std::string LocalSearchProfile() const
Returns local search profiling information in a human readable format.
void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
int SearchLeftDepth() const
Gets the search left depth of the current active search.
void AddBacktrackAction(Action a, bool fast)
When SaveValue() is not the best way to go, one can create a reversible action that will be called up...
Constraint * MakeTemporalDisjunction(IntervalVar *const t1, IntervalVar *const t2, IntVar *const alt)
This constraint implements a temporal disjunction between two interval vars t1 and t2.
void MakeIntervalVarArray(int count, int64 start_min, int64 start_max, int64 duration_min, int64 duration_max, int64 end_min, int64 end_max, bool optional, const std::string &name, std::vector< IntervalVar * > *const array)
This method fills the vector with 'count' interval var built with the corresponding parameters.
int TopProgressPercent()
Returns a percentage representing the propress of the search before reaching the limits of the top-le...
IntVar * MakeIsBetweenVar(IntExpr *const v, int64 l, int64 u)
void ReSeed(int32 seed)
Reseed the solver random generator.
bool CurrentlyInSolve() const
Returns true whether the current search has been created using a Solve() call instead of a NewSearch ...
IntervalVar * MakeFixedDurationIntervalVar(int64 start_min, int64 start_max, int64 duration, bool optional, const std::string &name)
Creates an interval var with a fixed duration.
Constraint * MakeIsMemberCt(IntExpr *const expr, const std::vector< int64 > &values, IntVar *const boolvar)
boolvar == (expr in set)
T * RevAlloc(T *object)
Registers the given object as being reversible.
IntVarStrategy
This enum describes the strategy used to select the next branching variable at each node during the s...
@ CHOOSE_RANDOM
Randomly select one of the remaining unbound variables.
@ CHOOSE_MIN_SIZE
Among unbound variables, select the variable with the smallest size.
@ CHOOSE_FIRST_UNBOUND
Select the first unbound variable.
@ CHOOSE_PATH
Selects the next unbound variable on a path, the path being defined by the variables: var[i] correspo...
@ CHOOSE_HIGHEST_MAX
Among unbound variables, select the variable with the highest maximal value.
@ CHOOSE_MIN_SIZE_LOWEST_MIN
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ INT_VAR_DEFAULT
The default behavior is CHOOSE_FIRST_UNBOUND.
@ CHOOSE_MIN_SIZE_HIGHEST_MAX
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_MAX_REGRET_ON_MIN
Among unbound variables, select the variable with the largest gap between the first and the second va...
@ CHOOSE_MIN_SIZE_HIGHEST_MIN
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_MAX_SIZE
Among unbound variables, select the variable with the highest size.
@ INT_VAR_SIMPLE
The simple selection is CHOOSE_FIRST_UNBOUND.
@ CHOOSE_MIN_SIZE_LOWEST_MAX
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_LOWEST_MIN
Among unbound variables, select the variable with the smallest minimal value.
DecisionBuilder * MakePhase(const std::vector< IntVar * > &vars, IntVarStrategy var_str, IntValueStrategy val_str)
Phases on IntVar arrays.
SequenceStrategy
Used for scheduling. Not yet implemented.
@ CHOOSE_MIN_SLACK_RANK_FORWARD
@ CHOOSE_RANDOM_RANK_FORWARD
Solver(const std::string &name)
Solver API.
std::function< int64(int64, int64)> IndexEvaluator2
Constraint * MakeInversePermutationConstraint(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that 'left' and 'right' both represent permutations of [0....
IntervalVar * MakeFixedDurationStartSyncedOnEndIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose start is synchronized with the end of another int...
DecisionBuilder * MakeNestedOptimize(DecisionBuilder *const db, Assignment *const solution, bool maximize, int64 step)
NestedOptimize will collapse a search tree described by a decision builder 'db' and a set of monitors...
ModelCache * Cache() const
Returns the cache of the model.
Constraint * MakeCount(const std::vector< IntVar * > &vars, int64 value, int64 max_count)
|{i | vars[i] == value}| == max_count
Decision * MakeRankLastInterval(SequenceVar *const sequence, int index)
Returns a decision that tries to rank last the ith interval var in the sequence variable.
Constraint * MakeAllDifferent(const std::vector< IntVar * > &vars)
All variables are pairwise different.
Constraint * MakeSortingConstraint(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &sorted)
Creates a constraint binding the arrays of variables "vars" and "sorted_vars": sorted_vars[0] must be...
DecisionBuilder * MakeLocalSearchPhase(Assignment *const assignment, LocalSearchPhaseParameters *const parameters)
Local Search decision builders factories.
IntExpr * MakeSemiContinuousExpr(IntExpr *const expr, int64 fixed_charge, int64 step)
Semi continuous Expression (x <= 0 -> f(x) = 0; x > 0 -> f(x) = ax + b) a >= 0 and b >= 0.
Demon * MakeDelayedConstraintInitialPropagateCallback(Constraint *const ct)
This method is a specialized case of the MakeConstraintDemon method to call the InitiatePropagate of ...
IntExpr * MakeScalProd(const std::vector< IntVar * > &vars, const std::vector< int64 > &coefs)
scalar product
Constraint * MakeNonOverlappingNonStrictBoxesConstraint(const std::vector< IntVar * > &x_vars, const std::vector< IntVar * > &y_vars, const std::vector< IntVar * > &x_size, const std::vector< IntVar * > &y_size)
This constraint states that all the boxes must not overlap.
bool NameAllVariables() const
Returns whether all variables should be named.
T * RevAllocArray(T *object)
Like RevAlloc() above, but for an array of objects: the array must have been allocated with the new[]...
Constraint * MakePathTransitPrecedenceConstraint(std::vector< IntVar * > nexts, std::vector< IntVar * > transits, const std::vector< std::pair< int, int >> &precedences)
Same as MakePathPrecedenceConstraint but will force i to be before j if the sum of transits on the pa...
int64 unchecked_solutions() const
The number of unchecked solutions found by local search.
IntExpr * MakeSum(IntExpr *const left, IntExpr *const right)
left + right.
IntExpr * CastExpression(const IntVar *const var) const
!defined(SWIG)
SearchMonitor * MakeEnterSearchCallback(std::function< void()> callback)
--— Callback-based search monitors --—
IntExpr * MakeIndexExpression(const std::vector< IntVar * > &vars, int64 value)
Returns the expression expr such that vars[expr] == value.
Constraint * MakeIsDifferentCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var != value)
void SetBranchSelector(BranchSelector bs)
Sets the given branch selector on the current active search.
SearchMonitor * MakeTabuSearch(bool maximize, IntVar *const v, int64 step, const std::vector< IntVar * > &vars, int64 keep_tenure, int64 forbid_tenure, double tabu_factor)
MetaHeuristics which try to get the search out of local optima.
friend class PropagationBaseObject
IntExpr * MakeSquare(IntExpr *const expr)
expr * expr
IntervalVar * MakeFixedDurationStartSyncedOnStartIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose start is synchronized with the start of another i...
OptimizeVar * MakeWeightedMinimize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a minimization weighted objective.
int64 branches() const
The number of branches explored since the creation of the solver.
std::function< int64(Solver *solver, const std::vector< IntVar * > &vars, int64 first_unbound, int64 last_unbound)> VariableIndexSelector
IntervalVar * MakeMirrorInterval(IntervalVar *const interval_var)
Creates an interval var that is the mirror image of the given one, that is, the interval var obtained...
uint64 stamp() const
The stamp indicates how many moves in the search tree we have performed.
LocalSearchOperator * MultiArmedBanditConcatenateOperators(const std::vector< LocalSearchOperator * > &ops, double memory_coefficient, double exploration_coefficient, bool maximize)
Creates a local search operator which concatenates a vector of operators.
Constraint * MakeSumLessOrEqual(const std::vector< IntVar * > &vars, int64 cst)
Variation on arrays.
Constraint * MakeIsGreaterCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left > right)
Assignment * MakeAssignment()
This method creates an empty assignment.
ModelVisitor * MakePrintModelVisitor()
Prints the model.
std::function< void()> Closure
Constraint * MakePathCumul(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, const std::vector< IntVar * > &cumuls, const std::vector< IntVar * > &transits)
Creates a constraint which accumulates values along a path such that: cumuls[next[i]] = cumuls[i] + t...
IntVar * MakeIntVar(int64 min, int64 max, const std::string &name)
MakeIntVar will create the best range based int var for the bounds given.
std::function< void(Solver *)> Action
SolutionCollector * MakeFirstSolutionCollector()
Collect the first solution of the search.
int32 Rand32(int32 size)
Returns a random value between 0 and 'size' - 1;.
Constraint * MakeIndexOfConstraint(const std::vector< IntVar * > &vars, IntVar *const index, int64 target)
This constraint is a special case of the element constraint with an array of integer variables,...
void ExportProfilingOverview(const std::string &filename)
Exports the profiling information in a human readable overview.
DecisionBuilder * Compose(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which sequentially composes decision builders.
std::function< IntVar *(int64)> Int64ToIntVar
Constraint * MakeElementEquality(const std::vector< int64 > &vals, IntVar *const index, IntVar *const target)
Constraint * MakeIndexOfFirstMaxValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
Creates a constraint that binds the index variable to the index of the first variable with the maximu...
IntExpr * MakeConvexPiecewiseExpr(IntExpr *expr, int64 early_cost, int64 early_date, int64 late_date, int64 late_cost)
Convex piecewise function.
IntVar * MakeIsLessCstVar(IntExpr *const var, int64 value)
status var of (var < value)
MarkerType
This enum is used internally in private methods Solver::PushState and Solver::PopState to tag states ...
SolutionCollector * MakeBestValueSolutionCollector(const Assignment *const assignment, bool maximize)
Collect the solution corresponding to the optimal value of the objective of 'assignment'; if 'assignm...
IntVar * MakeIsGreaterCstVar(IntExpr *const var, int64 value)
status var of (var > value)
Constraint * MakeMinEquality(const std::vector< IntVar * > &vars, IntVar *const min_var)
void AddCastConstraint(CastConstraint *const constraint, IntVar *const target_var, IntExpr *const expr)
Adds 'constraint' to the solver and marks it as a cast constraint, that is, a constraint created call...
IntervalVar * MakeIntervalVar(int64 start_min, int64 start_max, int64 duration_min, int64 duration_max, int64 end_min, int64 end_max, bool optional, const std::string &name)
Creates an interval var by specifying the bounds on start, duration, and end.
IntVar * MakeIsLessOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var <= value)
OptimizeVar * MakeMinimize(IntVar *const v, int64 step)
Creates a minimization objective.
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which stores an Assignment (calls void Assignment::Store())
Constraint * MakeIsLessOrEqualCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var <= value)
Constraint * MakePathPrecedenceConstraint(std::vector< IntVar * > nexts, const std::vector< std::pair< int, int >> &precedences)
Contraint enforcing, for each pair (i,j) in precedences, i to be before j in paths defined by next va...
std::function< DecisionModification()> BranchSelector
bool InstrumentsDemons() const
Returns whether we are instrumenting demons.
std::function< int64(const IntVar *v, int64 id)> VariableValueSelector
SearchMonitor * MakeExitSearchCallback(std::function< void()> callback)
static int64 MemoryUsage()
Current memory usage in bytes.
DecisionBuilder * MakeDefaultPhase(const std::vector< IntVar * > &vars)
IntExpr * MakeProd(IntExpr *const left, IntExpr *const right)
left * right
DecisionBuilder * MakeDecisionBuilderFromAssignment(Assignment *const assignment, DecisionBuilder *const db, const std::vector< IntVar * > &vars)
Returns a decision builder for which the left-most leaf corresponds to assignment,...
void set_fail_intercept(std::function< void()> fail_intercept)
Internal.
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
Decision * MakeFailDecision()
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
Constraint * MakeGreaterOrEqual(IntExpr *const left, IntExpr *const right)
left >= right
OptimizeVar * MakeOptimize(bool maximize, IntVar *const v, int64 step)
Creates a objective with a given sense (true = maximization).
Constraint * MakeIsGreaterOrEqualCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var >= value)
IntVar * MakeIsGreaterOrEqualVar(IntExpr *const left, IntExpr *const right)
status var of (left >= right)
Constraint * MakeIsGreaterOrEqualCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left >= right)
Constraint * MakeSumGreaterOrEqual(const std::vector< IntVar * > &vars, int64 cst)
Constraint * MakeAllowedAssignments(const std::vector< IntVar * > &vars, const IntTupleSet &tuples)
This method creates a constraint where the graph of the relation between the variables is given in ex...
void FinishCurrentSearch()
Tells the solver to kill or restart the current search.
bool IsProduct(IntExpr *const expr, IntExpr **inner_expr, int64 *coefficient)
Returns true if expr represents a product of a expr and a constant.
void NewSearch(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
IntExpr * MakeMonotonicElement(IndexEvaluator1 values, bool increasing, IntVar *const index)
Function based element.
Constraint * MakeNoCycle(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, IndexFilter1 sink_handler=nullptr)
Prevent cycles.
IntVar * MakeIntConst(int64 val, const std::string &name)
IntConst will create a constant expression.
SolutionCollector * MakeNBestValueSolutionCollector(const Assignment *const assignment, int solution_count, bool maximize)
Same as MakeBestValueSolutionCollector but collects the best solution_count solutions.
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
Decision * balancing_decision() const
IntVar * MakeIsLessOrEqualVar(IntExpr *const left, IntExpr *const right)
status var of (left <= right)
IntervalVar * RegisterIntervalVar(IntervalVar *const var)
Registers a new IntervalVar and wraps it inside a TraceIntervalVar if necessary.
EvaluatorLocalSearchOperators
This enum is used in Solver::MakeOperator associated with an evaluator to specify the neighborhood to...
@ TSPOPT
Sliding TSP operator.
@ LK
Lin-Kernighan local search.
LocalSearchFilterBound
This enum is used in Solver::MakeLocalSearchObjectiveFilter.
@ GE
Move is accepted when the current objective value >= objective.Min.
@ LE
Move is accepted when the current objective value <= objective.Max.
@ EQ
Move is accepted when the current objective value is in the interval objective.Min .
Constraint * MakeScalProdEquality(const std::vector< IntVar * > &vars, const std::vector< int64 > &coefficients, int64 cst)
OptimizationDirection optimization_direction() const
The direction of optimization, getter and setter.
void SaveAndAdd(T *adr, T val)
All-in-one SaveAndAdd_value.
This class represents a sorted list of disjoint, closed intervals.
A symmetry breaker is an object that will visit a decision and create the 'symmetrical' decision in r...
ABSL_DECLARE_FLAG(int64, cp_random_seed)
Declaration of the core objects for the constraint solver.
SharedBoundsManager * bounds
static const int64 kint64max
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
void SetAssignmentFromAssignment(Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
NOLINT.
int64 One()
This method returns 1.
std::vector< double > coefficients
This struct holds all parameters for the default search.
int heuristic_num_failures_limit
The failure limit for each heuristic that we run.
int initialization_splits
Maximum number of intervals that the initialization of impacts will scan per variable.
DecisionBuilder * decision_builder
When defined, this overrides the default impact based decision builder.
DisplayLevel display_level
This represents the amount of information displayed by the default search.
ValueSelection value_selection_schema
This parameter describes which value to select for a given var.
@ CHOOSE_MAX_VALUE_IMPACT
@ CHOOSE_MAX_AVERAGE_IMPACT
VariableSelection var_selection_schema
This parameter describes how the next variable to instantiate will be chosen.
bool persistent_impact
Whether to keep the impact from the first search for other searches, or to recompute the impact for e...
bool use_last_conflict
Should we use last conflict method. The default is false.
int heuristic_period
The distance in nodes between each run of the heuristics.
int random_seed
Seed used to initialize the random part in some heuristics.
bool run_all_heuristics
The default phase will run heuristics periodically.
static Iterator Begin(IntVarIterator *it)
These are the only way to construct an Iterator.
bool operator!=(const Iterator &other) const
static Iterator End(IntVarIterator *it)
bool operator<(const SolutionData &other) const
Holds semantic information stating that the 'expression' has been cast into 'variable' using the Var(...
IntegerCastInfo(IntVar *const v, IntExpr *const e, Constraint *const c)
Creates a search monitor from logging parameters.
int branch_period
SearchMonitors will display a periodic search log every branch_period branches explored.
OptimizeVar * objective
SearchMonitors will display values of objective or variable (both cannot be used together).
std::function< std::string()> display_callback
SearchMonitors will display the result of display_callback at each new solution found and when the se...
double scaling_factor
When displayed, objective or var values will be scaled and offset by the given values in the followin...
bool display_on_new_solutions_only
To be used to protect from cases where display_callback assumes variables are instantiated,...