68#ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
69#define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
83#include "absl/base/attributes.h"
84#include "absl/base/log_severity.h"
85#include "absl/container/flat_hash_map.h"
86#include "absl/container/flat_hash_set.h"
87#include "absl/flags/declare.h"
88#include "absl/flags/flag.h"
89#include "absl/log/check.h"
90#include "absl/random/random.h"
91#include "absl/strings/str_format.h"
92#include "absl/strings/string_view.h"
93#include "absl/time/time.h"
94#include "absl/types/span.h"
99#include "ortools/constraint_solver/search_stats.pb.h"
100#include "ortools/constraint_solver/solver_parameters.pb.h"
116class AssignmentProto;
121class DecisionBuilder;
122class DecisionVisitor;
126class DisjunctiveConstraint;
127class ImprovementSearchLimit;
130class IntVarAssignment;
131class IntVarLocalSearchFilter;
133class IntervalVarAssignment;
135class LocalSearchFilter;
136class LocalSearchFilterManager;
137class LocalSearchMonitor;
138class LocalSearchOperator;
139class LocalSearchPhaseParameters;
140class LocalSearchProfiler;
143class ObjectiveMonitor;
144class BaseObjectiveMonitor;
147class ProfiledDecisionBuilder;
148class PropagationBaseObject;
149class PropagationMonitor;
152class RegularLimitParameters;
158class SequenceVarAssignment;
159class SolutionCollector;
161class SymmetryBreaker;
167class LightIntFunctionElementCt;
169class LightIntIntFunctionElementCt;
171class LightIntIntIntFunctionElementCt;
174 return absl::GetFlag(FLAGS_cp_random_seed) == -1
175 ? absl::Uniform<int64_t>(absl::BitGen(), 0,
kint64max)
176 :
absl::GetFlag(FLAGS_cp_random_seed);
264 struct IntegerCastInfo {
795 typedef std::function<int64_t(
Solver* solver,
796 const std::vector<IntVar*>& vars,
797 int64_t first_unbound, int64_t last_unbound)>
800 typedef std::function<int64_t(
const IntVar* v, int64_t
id)>
802 typedef std::function<bool(int64_t, int64_t, int64_t)>
807 typedef std::function<void()>
Closure;
810 explicit Solver(
const std::string& name);
822 ConstraintSolverParameters
parameters()
const {
return parameters_; }
838 InternalSaveValue(o);
853 template <
typename T>
855 return reinterpret_cast<T*
>(SafeRevAlloc(
object));
864 template <
typename T>
866 return reinterpret_cast<T*
>(SafeRevAllocArray(
object));
970 const std::vector<SearchMonitor*>& monitors);
993 const std::vector<SearchMonitor*>& monitors);
1033 absl::Time
Now()
const;
1040 int64_t
branches()
const {
return branches_; }
1052 int64_t
failures()
const {
return fails_; }
1055 int64_t
neighbors()
const {
return neighbors_; }
1070 uint64_t
stamp()
const;
1079 const std::string&
context()
const {
return context_; }
1083 return optimization_direction_;
1086 optimization_direction_ = direction;
1092 std::function<int64_t(int64_t, int64_t, int64_t)> penalty_callback) {
1093 penalty_callback_ = std::move(penalty_callback);
1097 return (penalty_callback_ ==
nullptr) ? 0 : penalty_callback_(i, j, k);
1113 const std::string& name);
1116 IntVar*
MakeIntVar(
const std::vector<int>& values,
const std::string& name);
1143 const std::string& name, std::vector<IntVar*>* vars);
1147 std::vector<IntVar*>* vars);
1150 const std::string& name);
1156 std::vector<IntVar*>* vars);
1174 const std::vector<int64_t>& coefs);
1177 const std::vector<int>& coefs);
1229 int64_t range_end,
IntVar* argument);
1243 template <
typename F>
1245 std::function<
bool()> deep_serialize =
nullptr) {
1247 this, var, index, std::move(values), std::move(deep_serialize)));
1256 template <
typename F>
1259 std::function<
bool()> deep_serialize =
nullptr) {
1261 this, var, index1, index2, std::move(values),
1262 std::move(deep_serialize)));
1269 template <
typename F>
1274 this, var, index1, index2, index3, std::move(values)));
1305 int64_t early_date, int64_t late_date,
1330 int64_t unperformed_value);
1438 const std::vector<int64_t>& coefficients,
1441 const std::vector<int>& coefficients,
1444 const std::vector<int64_t>& coefficients,
1447 const std::vector<int>& coefficients,
1450 const std::vector<int64_t>& coeffs,
1453 const std::vector<int>& coeffs,
1456 const std::vector<int64_t>& coefficients,
1459 const std::vector<int>& coefficients,
1474 IntVar* index, int64_t target);
1482 IntVar* index, int64_t target);
1522 const std::vector<int64_t>& values);
1527 std::vector<int64_t> ends);
1530 std::vector<int> ends);
1557 const std::vector<int64_t>& values,
1558 const std::vector<IntVar*>& cards);
1561 const std::vector<int>& values,
1562 const std::vector<IntVar*>& cards);
1565 const std::vector<IntVar*>& cards);
1569 int64_t card_max, int64_t card_size);
1574 const std::vector<int64_t>& card_min,
1575 const std::vector<int64_t>& card_max);
1580 const std::vector<int>& card_min,
1581 const std::vector<int>& card_max);
1586 const std::vector<int64_t>& values,
1587 const std::vector<int64_t>& card_min,
1588 const std::vector<int64_t>& card_max);
1593 const std::vector<int>& values,
1594 const std::vector<int>& card_min,
1595 const std::vector<int>& card_max);
1602 IntVar* deviation_var, int64_t total_sum);
1612 bool stronger_propagation);
1617 int64_t escape_value);
1636 const std::vector<IntVar*>& sorted);
1644 const std::vector<IntVar*>& right);
1649 const std::vector<IntVar*>& right);
1656 std::vector<IntVar*> right,
1657 std::vector<int64_t> offsets);
1661 std::vector<IntVar*> left, std::vector<IntVar*> right,
1662 std::vector<int64_t> offsets,
IntVar* boolvar);
1669 const std::vector<IntVar*>& left,
const std::vector<IntVar*>& right);
1674 IntVar* index,
const std::vector<IntVar*>& vars);
1679 IntVar* index,
const std::vector<IntVar*>& vars);
1686 const std::vector<IntVar*>& second_vars);
1694 const std::vector<IntVar*>& second_vars,
1695 int64_t escape_value);
1710 const std::vector<IntVar*>& active,
1713 const std::vector<IntVar*>& active,
1728 const std::vector<IntVar*>& active,
1729 const std::vector<IntVar*>& cumuls,
1730 const std::vector<IntVar*>& transits);
1735 const std::vector<IntVar*>& active,
1736 const std::vector<IntVar*>& cumuls,
1737 const std::vector<IntVar*>& transits);
1745 const std::vector<IntVar*>& active,
1746 const std::vector<IntVar*>& cumuls,
1756 const std::vector<IntVar*>& active,
1757 const std::vector<IntVar*>& cumuls,
1758 const std::vector<IntVar*>& slacks,
1765 std::vector<int64_t> sources,
1766 std::vector<int64_t> sinks,
1767 std::vector<IntVar*> status);
1775 std::vector<IntVar*> nexts,
1776 const std::vector<std::pair<int, int>>& precedences);
1786 std::vector<IntVar*> nexts,
1787 const std::vector<std::pair<int, int>>& precedences,
1788 absl::Span<const int> lifo_path_starts,
1789 absl::Span<const int> fifo_path_starts);
1793 std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1794 const std::vector<std::pair<int, int>>& precedences);
1822 std::vector<IntVar*>
nexts;
1823 std::vector<IntVar*>
paths;
1824 std::vector<IntVar*>
forces;
1830 std::vector<IntVar*>
costs;
1838 Constraint* MakeMapDomain(IntVar* var, const std::vector<IntVar*>& actives);
1855 const std::vector<IntVar*>& vars,
const IntTupleSet& transition_table,
1856 int64_t initial_state,
const std::vector<int64_t>& final_states);
1867 int64_t initial_state,
1868 const std::vector<int>& final_states);
1870#if defined(SWIGPYTHON)
1873 const std::vector<IntVar*>& vars,
1874 const std::vector<std::vector<int64_t> >& raw_tuples) {
1876 tuples.InsertAll(raw_tuples);
1881 const std::vector<IntVar*>& vars,
1882 const std::vector<std::vector<int64_t> >&
1884 int64_t initial_state,
const std::vector<int>& final_states) {
1886 transitions.InsertAll(raw_transitions);
1901 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1902 const std::vector<IntVar*>& x_size,
const std::vector<IntVar*>& y_size);
1904 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1905 absl::Span<const int64_t> x_size, absl::Span<const int64_t> y_size);
1907 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1908 absl::Span<const int> x_size, absl::Span<const int> y_size);
1919 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1920 const std::vector<IntVar*>& x_size,
const std::vector<IntVar*>& y_size);
1922 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1923 absl::Span<const int64_t> x_size, absl::Span<const int64_t> y_size);
1925 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1926 absl::Span<const int> x_size, absl::Span<const int> y_size);
1933 Pack*
MakePack(
const std::vector<IntVar*>& vars,
int number_of_bins);
1940 int64_t start_max, int64_t duration,
1942 const std::string& name);
1947 int64_t start_max, int64_t duration,
1948 bool optional, absl::string_view name,
1949 std::vector<IntervalVar*>* array);
1955 const std::string& name);
1961 IntVar* performed_variable,
1962 const std::string& name);
1967 const std::vector<IntVar*>& start_variables, int64_t duration,
1968 absl::string_view name, std::vector<IntervalVar*>* array);
1973 const std::vector<IntVar*>& start_variables,
1974 absl::Span<const int64_t> durations, absl::string_view name,
1975 std::vector<IntervalVar*>* array);
1979 const std::vector<IntVar*>& start_variables,
1980 absl::Span<const int> durations, absl::string_view name,
1981 std::vector<IntervalVar*>* array);
1986 const std::vector<IntVar*>& start_variables,
1987 absl::Span<const int64_t> durations,
1988 const std::vector<IntVar*>& performed_variables, absl::string_view name,
1989 std::vector<IntervalVar*>* array);
1994 const std::vector<IntVar*>& start_variables,
1995 absl::Span<const int> durations,
1996 const std::vector<IntVar*>& performed_variables, absl::string_view name,
1997 std::vector<IntervalVar*>* array);
2001 const std::string& name);
2006 int64_t duration_min, int64_t duration_max,
2007 int64_t end_min, int64_t end_max,
bool optional,
2008 const std::string& name);
2013 int64_t duration_min, int64_t duration_max,
2014 int64_t end_min, int64_t end_max,
bool optional,
2015 absl::string_view name,
2016 std::vector<IntervalVar*>* array);
2027 IntervalVar* interval_var, int64_t duration, int64_t offset);
2034 IntervalVar* interval_var, int64_t duration, int64_t offset);
2041 IntervalVar* interval_var, int64_t duration, int64_t offset);
2048 IntervalVar* interval_var, int64_t duration, int64_t offset);
2118 const std::vector<IntervalVar*>& intervals,
const std::string& name);
2124 const std::vector<IntervalVar*>& intervals,
const std::string& name);
2136 const std::vector<int64_t>& demands,
2137 int64_t capacity,
const std::string& name);
2149 const std::vector<int>& demands, int64_t capacity,
2150 const std::string& name);
2162 const std::vector<int64_t>& demands,
2163 IntVar* capacity, absl::string_view name);
2175 const std::vector<int>& demands,
IntVar* capacity,
2176 const std::string& name);
2186 const std::vector<IntVar*>& demands,
2187 int64_t capacity,
const std::string& name);
2197 const std::vector<IntVar*>& demands,
2198 IntVar* capacity,
const std::string& name);
2234 const Assignment* assignment,
bool maximize);
2238 const Assignment* assignment, std::vector<bool> maximize);
2248 std::vector<bool> maximize);
2254 const Assignment* assignment,
int solution_count,
bool maximize);
2260 const Assignment* assignment,
int solution_count,
2261 std::vector<bool> maximize);
2263 int solution_count, std::vector<bool> maximize);
2283 const std::vector<int64_t>& weights,
2289 const std::vector<int>& weights,
2294 const std::vector<int64_t>& weights,
2299 const std::vector<int>& weights,
2304 const std::vector<IntVar*>& sub_objectives,
2305 const std::vector<int64_t>& weights,
2310 const std::vector<IntVar*>& sub_objectives,
2311 const std::vector<int>& weights,
2317 std::vector<IntVar*> variables,
2318 std::vector<int64_t> steps);
2340 const std::vector<IntVar*>& vars,
2341 int64_t keep_tenure, int64_t forbid_tenure,
2342 double tabu_factor);
2345 const std::vector<bool>& maximize, std::vector<IntVar*> objectives,
2346 std::vector<int64_t> steps,
const std::vector<IntVar*>& vars,
2347 int64_t keep_tenure, int64_t forbid_tenure,
double tabu_factor);
2353 const std::vector<IntVar*>& tabu_vars,
2354 int64_t forbid_tenure);
2360 int64_t initial_temperature);
2362 const std::vector<bool>& maximize, std::vector<IntVar*> vars,
2363 std::vector<int64_t> steps, std::vector<int64_t> initial_temperatures);
2370 int64_t step,
const std::vector<IntVar*>& vars,
double penalty_factor,
2371 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>
2372 get_equivalent_pairs =
nullptr,
2373 bool reset_penalties_on_new_best_solution =
false);
2376 int64_t step,
const std::vector<IntVar*>& vars,
2377 const std::vector<IntVar*>& secondary_vars,
double penalty_factor,
2378 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>
2379 get_equivalent_pairs =
nullptr,
2380 bool reset_penalties_on_new_best_solution =
false);
2388 std::vector<BaseObjectiveMonitor*> monitors,
2389 int num_max_local_optima_before_metaheuristic_switch);
2403 ABSL_DEPRECATED(
"Use the version taking absl::Duration() as argument")
2407 ? absl::InfiniteDuration()
2408 : absl::Milliseconds(time_in_ms));
2427 ABSL_MUST_USE_RESULT RegularLimit*
MakeLimit(absl::Duration time,
2431 bool smart_time_check =
false,
2432 bool cumulative =
false);
2434 ABSL_MUST_USE_RESULT RegularLimit*
MakeLimit(
2435 const RegularLimitParameters& proto);
2438 ABSL_DEPRECATED(
"Use other MakeLimit() versions")
2443 bool smart_time_check =
false,
2444 bool cumulative =
false);
2460 IntVar* objective_var,
bool maximize,
double objective_scaling_factor,
2461 double objective_offset,
double improvement_rate_coefficient,
2462 int improvement_rate_solutions_distance);
2467 std::vector<IntVar*> objective_vars, std::vector<bool> maximize,
2468 std::vector<double> objective_scaling_factors,
2469 std::vector<double> objective_offsets,
2470 double improvement_rate_coefficient,
2471 int improvement_rate_solutions_distance);
2476 std::function<
bool()> limiter);
2490 std::function<std::string()> display_callback);
2495 std::function<std::string()> display_callback);
2500 std::function<std::string()> display_callback);
2509 std::function<std::string()> display_callback);
2551 absl::flat_hash_map<const IntVar*, int>* map);
2556 const std::vector<SymmetryBreaker*>& visitors);
2569 bool start_with_lower_half);
2573 const std::vector<int64_t>& values);
2575 const std::vector<IntVar*>& vars,
const std::vector<int64_t>& values);
2577 const std::vector<int64_t>& values);
2720 const std::vector<IntVar*>& vars);
2742 const std::vector<SearchMonitor*>& monitors);
2752 bool maximize, int64_t step);
2754 bool maximize, int64_t step,
2757 bool maximize, int64_t step,
2761 bool maximize, int64_t step,
2766 bool maximize, int64_t step,
2773 const std::vector<SearchMonitor*>& monitors);
2786 std::function<
const std::vector<int>&(
int,
int)> get_incoming_neighbors =
2788 std::function<
const std::vector<int>&(
int,
int)> get_outgoing_neighbors =
2791 const std::vector<IntVar*>& vars,
2793 std::function<
const std::vector<int>&(
int,
int)> get_incoming_neighbors =
2795 std::function<
const std::vector<int>&(
int,
int)> get_outgoing_neighbors =
2803 const std::vector<IntVar*>& secondary_vars,
2815 int number_of_variables);
2817 int number_of_variables,
2834 const std::vector<IntVar*>& variables,
2835 const std::vector<int64_t>& target_values);
2868 const std::vector<LocalSearchOperator*>& ops);
2870 const std::vector<LocalSearchOperator*>& ops,
bool restart);
2872 const std::vector<LocalSearchOperator*>& ops,
2873 std::function<int64_t(
int,
int)> evaluator);
2877 const std::vector<LocalSearchOperator*>& ops);
2883 const std::vector<LocalSearchOperator*>& ops, int32_t seed);
2893 const std::vector<LocalSearchOperator*>& ops,
double memory_coefficient,
2894 double exploration_coefficient,
bool maximize);
2953 const std::vector<SearchMonitor*>& monitors,
RegularLimit* limit,
2954 absl::flat_hash_set<IntVar*>* touched =
nullptr);
2990 const std::vector<IntVar*>& vars,
3030 InternalSaveValue(adr);
3039 InternalSaveValue(adr);
3045 int64_t
Rand64(int64_t size) {
3047 return absl::Uniform<int64_t>(random_, 0, size);
3051 int32_t
Rand32(int32_t size) {
3053 return absl::Uniform<int32_t>(random_, 0, size);
3057 void ReSeed(int32_t seed) { random_.seed(seed); }
3082 int constraints()
const {
return constraints_list_.size(); }
3092 fail_intercept_ = std::move(fail_intercept);
3102 use_fast_local_search_ = use_fast_local_search;
3176 template <
class K,
class V>
3204 if (!should_fail_)
return;
3205 should_fail_ =
false;
3216 void PushSentinel(
int magic_code);
3217 void BacktrackToSentinel(
int magic_code);
3218 void ProcessConstraints();
3220 void JumpToSentinelWhenNested();
3221 void JumpToSentinel();
3222 void check_alloc_state();
3228 void UnfreezeQueue();
3229 void reset_action_on_fail();
3230 void set_action_on_fail(
Action a);
3231 void set_variable_to_clean_on_fail(
IntVar* v);
3232 void IncrementUncheckedSolutionCounter();
3233 bool IsUncheckedSolutionLimitReached();
3235 void InternalSaveValue(
int* valptr);
3236 void InternalSaveValue(int64_t* valptr);
3237 void InternalSaveValue(uint64_t* valptr);
3238 void InternalSaveValue(
double* valptr);
3239 void InternalSaveValue(
bool* valptr);
3240 void InternalSaveValue(
void** valptr);
3241 void InternalSaveValue(int64_t** valptr) {
3242 InternalSaveValue(
reinterpret_cast<void**
>(valptr));
3247 int* SafeRevAllocArray(
int* ptr);
3248 int64_t* SafeRevAllocArray(int64_t* ptr);
3249 uint64_t* SafeRevAllocArray(uint64_t* ptr);
3250 double* SafeRevAllocArray(
double* ptr);
3257 void* UnsafeRevAllocAux(
void* ptr);
3259 T* UnsafeRevAlloc(T* ptr) {
3260 return reinterpret_cast<T*
>(
3261 UnsafeRevAllocAux(
reinterpret_cast<void*
>(ptr)));
3263 void** UnsafeRevAllocArrayAux(
void** ptr);
3265 T** UnsafeRevAllocArray(T** ptr) {
3266 return reinterpret_cast<T**
>(
3267 UnsafeRevAllocArrayAux(
reinterpret_cast<void**
>(ptr)));
3270 void InitCachedIntConstants();
3271 void InitCachedConstraint();
3276 Search* TopLevelSearch()
const {
return searches_.at(1); }
3280 Search* ParentSearch()
const {
3281 const size_t search_size = searches_.size();
3282 DCHECK_GT(search_size, 1);
3283 return searches_[search_size - 2];
3286 template <
bool is_profile_active>
3287 Assignment* RunUncheckedLocalSearchInternal(
3288 const Assignment* initial_solution,
3289 LocalSearchFilterManager* filter_manager,
3290 LocalSearchOperator* ls_operator,
3291 const std::vector<SearchMonitor*>& monitors, RegularLimit* limit,
3292 absl::flat_hash_set<IntVar*>* touched);
3300 int GetNewIntVarIndex() {
return num_int_vars_++; }
3303 bool IsADifference(IntExpr* expr, IntExpr** left, IntExpr** right);
3305 const std::string name_;
3306 const ConstraintSolverParameters parameters_;
3307 absl::flat_hash_map<const PropagationBaseObject*, std::string>
3308 propagation_object_names_;
3309 absl::flat_hash_map<const PropagationBaseObject*, IntegerCastInfo>
3311 absl::flat_hash_set<const Constraint*> cast_constraints_;
3312 const std::string empty_name_;
3313 std::unique_ptr<Queue> queue_;
3314 std::unique_ptr<Trail> trail_;
3315 std::vector<Constraint*> constraints_list_;
3316 std::vector<Constraint*> additional_constraints_list_;
3317 std::vector<int> additional_constraints_parent_list_;
3324 int64_t filtered_neighbors_;
3325 int64_t accepted_neighbors_;
3326 std::string context_;
3328 std::unique_ptr<ClockTimer> timer_;
3329 std::vector<Search*> searches_;
3330 std::mt19937 random_;
3331 uint64_t fail_stamp_;
3332 std::unique_ptr<Decision> balancing_decision_;
3334 std::function<void()> fail_intercept_;
3338 bool use_fast_local_search_;
3342 std::unique_ptr<Assignment> local_search_state_;
3345 enum { MIN_CACHED_INT_CONST = -8, MAX_CACHED_INT_CONST = 8 };
3346 IntVar* cached_constants_[MAX_CACHED_INT_CONST + 1 - MIN_CACHED_INT_CONST];
3352 std::unique_ptr<Decision> fail_decision_;
3353 int constraint_index_;
3354 int additional_constraint_index_;
3357 std::unique_ptr<ModelCache> model_cache_;
3358 std::unique_ptr<PropagationMonitor> propagation_monitor_;
3359 PropagationMonitor* print_trace_;
3360 std::unique_ptr<LocalSearchMonitor> local_search_monitor_;
3361 int anonymous_variable_index_;
3364 std::function<int64_t(int64_t, int64_t, int64_t)> penalty_callback_;
3372inline int64_t
Zero() {
return 0; }
3375inline int64_t
One() {
return 1; }
3390 virtual std::string
DebugString()
const {
return "BaseObject"; }
3410 if (
name().empty()) {
3411 return "PropagationBaseObject";
3413 return absl::StrFormat(
"PropagationBaseObject: %s",
name());
3416 Solver*
solver()
const {
return solver_; }
3430 void EnqueueVar(Demon*
const d) { solver_->EnqueueVar(d); }
3438 solver_->set_action_on_fail(std::move(a));
3447 solver_->set_variable_to_clean_on_fail(v);
3451 virtual std::string
name()
const;
3481 std::string
DebugString()
const override {
return "Decision"; }
3500 bool start_with_lower_half);
3532 std::vector<SearchMonitor*>* extras);
3535 void set_name(absl::string_view name) { name_ = name; }
3547 const std::string&
name()
const {
return name_; }
3548 double seconds()
const {
return seconds_; }
3549 Decision*
Next(Solver* solver)
override;
3552 std::vector<SearchMonitor*>* extras)
override;
3557 const std::string name_;
3576 Demon() : stamp_(uint64_t{0}) {}
3604 void set_stamp(int64_t stamp) { stamp_ = stamp; }
3605 uint64_t stamp()
const {
return stamp_; }
3613 static const char kAbs[];
3614 static const char kAbsEqual[];
3615 static const char kAllDifferent[];
3616 static const char kAllowedAssignments[];
3617 static const char kAtMost[];
3618 static const char kIndexOf[];
3619 static const char kBetween[];
3620 static const char kConditionalExpr[];
3621 static const char kCircuit[];
3622 static const char kConvexPiecewise[];
3623 static const char kCountEqual[];
3624 static const char kCover[];
3625 static const char kCumulative[];
3626 static const char kDeviation[];
3627 static const char kDifference[];
3628 static const char kDisjunctive[];
3629 static const char kDistribute[];
3630 static const char kDivide[];
3631 static const char kDurationExpr[];
3632 static const char kElement[];
3633 static const char kLightElementEqual[];
3634 static const char kElementEqual[];
3635 static const char kEndExpr[];
3636 static const char kEquality[];
3637 static const char kFalseConstraint[];
3638 static const char kGlobalCardinality[];
3639 static const char kGreater[];
3640 static const char kGreaterOrEqual[];
3641 static const char kIntegerVariable[];
3642 static const char kIntervalBinaryRelation[];
3643 static const char kIntervalDisjunction[];
3644 static const char kIntervalUnaryRelation[];
3645 static const char kIntervalVariable[];
3646 static const char kInversePermutation[];
3647 static const char kIsBetween[];
3648 static const char kIsDifferent[];
3649 static const char kIsEqual[];
3650 static const char kIsGreater[];
3651 static const char kIsGreaterOrEqual[];
3652 static const char kIsLess[];
3653 static const char kIsLessOrEqual[];
3654 static const char kIsMember[];
3655 static const char kLess[];
3656 static const char kLessOrEqual[];
3657 static const char kLexLess[];
3658 static const char kLinkExprVar[];
3659 static const char kMapDomain[];
3660 static const char kMax[];
3661 static const char kMaxEqual[];
3662 static const char kMember[];
3663 static const char kMin[];
3664 static const char kMinEqual[];
3665 static const char kModulo[];
3805 const std::string& operation, int64_t value,
3808 const std::string& operation,
3815 const std::vector<int64_t>& values);
3824 const std::string& arg_name,
const std::vector<IntVar*>& arguments);
3831 const std::string& arg_name,
const std::vector<IntervalVar*>& arguments);
3837 const std::string& arg_name,
const std::vector<SequenceVar*>& arguments);
3848 int64_t index_min, int64_t index_max);
3851 const std::string& arg_name, int64_t index_max);
3874 virtual void Post() = 0;
3886 virtual void Accept(ModelVisitor* visitor)
const;
3894 virtual IntVar*
Var();
4002 virtual void Accept(ModelVisitor* visitor)
const;
4009 Solver*
solver()
const {
return solver_; }
4015 Solver*
const solver_;
4026 explicit Rev(
const T& val) : stamp_(0), value_(val) {}
4028 const T&
Value()
const {
return value_; }
4030 void SetValue(Solver*
const s,
const T& val) {
4031 if (val != value_) {
4032 if (stamp_ < s->stamp()) {
4033 s->SaveValue(&value_);
4034 stamp_ = s->stamp();
4051 void Add(
Solver*
const s,
const T& to_add) {
4055 void Incr(Solver*
const s) {
Add(s, 1); }
4069 : stamps_(
new uint64_t[
size]), values_(
new T[
size]), size_(
size) {
4070 for (
int i = 0; i <
size; ++i) {
4078 int64_t
size()
const {
return size_; }
4080 const T&
Value(
int index)
const {
return values_[index]; }
4087 DCHECK_LT(index, size_);
4088 if (val != values_[index]) {
4089 if (stamps_[index] < s->
stamp()) {
4091 stamps_[index] = s->
stamp();
4093 values_[index] = val;
4098 std::unique_ptr<uint64_t[]> stamps_;
4099 std::unique_ptr<T[]> values_;
4109 void Add(
Solver*
const s,
int index,
const T& to_add) {
4115 void Decr(
Solver*
const s,
int index) {
Add(s, index, -1); }
4136 virtual int64_t
Min()
const = 0;
4138 virtual int64_t
Max()
const = 0;
4139 virtual void SetMax(int64_t m) = 0;
4143 virtual void Range(int64_t* l, int64_t* u) {
4148 virtual void SetRange(int64_t l, int64_t u) {
4157 virtual bool Bound()
const {
return (
Min() ==
Max()); }
4160 virtual bool IsVar()
const {
return false; }
4214 virtual bool Ok()
const = 0;
4223 std::string
DebugString()
const override {
return "IntVar::Iterator"; }
4236 : it_(it), begin_was_called_(
false) {
4243 DCHECK(!begin_was_called_);
4244 begin_was_called_ =
true;
4252 static Iterator
Begin(IntVarIterator* it) {
4253 return Iterator(it,
false);
4255 static Iterator
End(IntVarIterator* it) {
4256 return Iterator(it,
true);
4269 DCHECK(other.it == it);
4270 DCHECK(other.is_end);
4275 Iterator(
IntVarIterator* it,
bool is_end) : it(it), is_end(is_end) {}
4283 bool begin_was_called_;
4303 bool IsVar()
const override {
return true; }
4318 virtual void RemoveValues(
const std::vector<int64_t>& values);
4357 virtual uint64_t
Size()
const = 0;
4374 virtual int64_t
OldMin()
const = 0;
4377 virtual int64_t
OldMax()
const = 0;
4391 int index()
const {
return index_; }
4413 std::string
DebugString()
const override {
return "SolutionCollector"; }
4417 void Add(
const std::vector<IntVar*>& vars);
4419 void Add(
const std::vector<IntervalVar*>& vars);
4421 void Add(
const std::vector<SequenceVar*>& vars);
4523 virtual int64_t
Step(
int index)
const = 0;
4524 virtual bool Maximize(
int index)
const = 0;
4525 virtual int64_t
BestValue(
int index)
const = 0;
4526 virtual int Size()
const = 0;
4527 bool is_active()
const {
return is_active_; }
4531 bool is_active_ =
true;
4539 std::vector<IntVar*> vars, std::vector<int64_t> steps);
4546 return objective_vars_[index];
4549 return minimization_vars_[index];
4551 int64_t
Step(
int index)
const override {
return steps_[index]; }
4552 bool Maximize(
int index)
const override {
4555 int64_t
BestValue(
int index)
const override {
4559 int Size()
const override {
return objective_vars_.size(); }
4566 const std::vector<IntVar*>&
objective_vars()
const {
return objective_vars_; }
4568 return minimization_vars_;
4572 return current_values_[index];
4575 current_values_[index] = value;
4577 template <
typename T>
4584 upper_bounds_[i] =
solver->MakeIntConst(upper_bounds(i));
4587 minimization_vars_, upper_bounds_, steps_));
4590 template <
typename T>
4592 const T& upper_bounds) {
4599 for (
int i = 0; i <
Size(); ++i) {
4600 upper_bounds_[i] =
solver->MakeIntConst(upper_bounds(i));
4603 minimization_vars_, upper_bounds_, steps_, status));
4613 const std::vector<IntVar*> objective_vars_;
4614 std::vector<IntVar*> minimization_vars_;
4615 std::vector<IntVar*> upper_bounds_;
4616 std::vector<int64_t> steps_;
4617 std::vector<int64_t> best_values_;
4618 std::vector<int64_t> current_values_;
4630 std::vector<IntVar*> vars, std::vector<int64_t> steps);
4646 virtual std::string
Name()
const;
4665 bool crossed()
const {
return crossed_; }
4677 virtual void Init() = 0;
4692 return absl::StrFormat(
"SearchLimit(crossed = %i)", crossed_);
4697 void TopPeriodicCheck();
4714 void Init()
override;
4720 return duration_limit_ == absl::InfiniteDuration()
4724 int64_t
branches()
const {
return branches_; }
4725 int64_t
failures()
const {
return failures_; }
4726 int64_t
solutions()
const {
return solutions_; }
4733 return solver_time_at_limit_start_ + duration_limit_;
4739 bool CheckTime(absl::Duration offset);
4740 absl::Duration TimeElapsed();
4741 static int64_t GetPercent(int64_t value, int64_t offset, int64_t total) {
4742 return (total > 0 && total <
kint64max) ? 100 * (value - offset) / total
4746 absl::Duration duration_limit_;
4747 absl::Time solver_time_at_limit_start_;
4748 absl::Duration last_time_elapsed_;
4749 int64_t check_count_;
4750 int64_t next_check_;
4751 bool smart_time_check_;
4753 int64_t branches_offset_;
4755 int64_t failures_offset_;
4757 int64_t solutions_offset_;
4781 double objective_scaling_factor,
4782 double objective_offset,
4783 double improvement_rate_coefficient,
4784 int improvement_rate_solutions_distance);
4786 std::vector<bool> maximize,
4787 std::vector<double> objective_scaling_factors,
4788 std::vector<double> objective_offsets,
4789 double improvement_rate_coefficient,
4790 int improvement_rate_solutions_distance);
4796 void Init()
override;
4800 std::vector<IntVar*> objective_vars_;
4801 std::vector<bool> maximize_;
4802 std::vector<double> objective_scaling_factors_;
4803 std::vector<double> objective_offsets_;
4804 double improvement_rate_coefficient_;
4805 int improvement_rate_solutions_distance_;
4807 std::vector<double> best_objectives_;
4809 std::vector<std::deque<std::pair<double, int64_t> > > improvements_;
4811 std::vector<double> thresholds_;
4812 bool objective_updated_;
4813 bool gradient_stage_;
4829 static const int64_t kMinValidValue;
4831 static const int64_t kMaxValidValue;
4846 virtual int64_t StartMin()
const = 0;
4847 virtual int64_t StartMax()
const = 0;
4848 virtual void SetStartMin(int64_t m) = 0;
4849 virtual void SetStartMax(int64_t m) = 0;
4850 virtual void SetStartRange(int64_t mi, int64_t ma) = 0;
4851 virtual int64_t OldStartMin()
const = 0;
4852 virtual int64_t OldStartMax()
const = 0;
4853 virtual void WhenStartRange(
Demon* d) = 0;
4855 WhenStartRange(solver()->MakeClosureDemon(std::move(closure)));
4858 void WhenStartRange(Solver::Action action) {
4859 WhenStartRange(solver()->MakeActionDemon(std::move(action)));
4862 virtual void WhenStartBound(Demon* d) = 0;
4863 void WhenStartBound(Solver::Closure closure) {
4864 WhenStartBound(solver()->MakeClosureDemon(std::move(closure)));
4867 void WhenStartBound(Solver::Action action) {
4868 WhenStartBound(solver()->MakeActionDemon(std::move(action)));
4873 virtual int64_t DurationMin()
const = 0;
4874 virtual int64_t DurationMax()
const = 0;
4875 virtual void SetDurationMin(int64_t m) = 0;
4876 virtual void SetDurationMax(int64_t m) = 0;
4877 virtual void SetDurationRange(int64_t mi, int64_t ma) = 0;
4878 virtual int64_t OldDurationMin()
const = 0;
4879 virtual int64_t OldDurationMax()
const = 0;
4880 virtual void WhenDurationRange(Demon* d) = 0;
4881 void WhenDurationRange(Solver::Closure closure) {
4882 WhenDurationRange(solver()->MakeClosureDemon(std::move(closure)));
4895 WhenDurationBound(solver()->MakeActionDemon(std::move(action)));
4900 virtual int64_t
EndMin()
const = 0;
4904 virtual void SetEndRange(int64_t mi, int64_t ma) = 0;
4916 virtual void WhenEndBound(
Demon* d) = 0;
4931 bool IsPerformedBound()
const {
4986 const std::vector<IntVar*>& nexts,
const std::string&
name);
5028 std::vector<int>* possible_lasts);
5036 const std::vector<int>& rank_last,
5037 const std::vector<int>& unperformed);
5047 void FillSequence(std::vector<int>* rank_first, std::vector<int>* rank_last,
5048 std::vector<int>* unperformed)
const;
5057 int64_t
size()
const {
return intervals_.size(); }
5063 int ComputeForwardFrontier();
5064 int ComputeBackwardFrontier();
5065 void UpdatePrevious()
const;
5067 const std::vector<IntervalVar*> intervals_;
5068 const std::vector<IntVar*> nexts_;
5069 mutable std::vector<int> previous_;
5072class AssignmentElement {
5076 void Activate() { activated_ =
true; }
5078 bool Activated()
const {
return activated_; }
5088 void Reset(IntVar* var);
5091 IntVar*
Var()
const {
return var_; }
5097 if (var_ !=
nullptr) {
5098 var_->SetRange(min_, max_);
5101 void LoadFromProto(
const IntVarAssignment& int_var_assignment_proto);
5102 void WriteToProto(IntVarAssignment* int_var_assignment_proto)
const;
5104 int64_t
Min()
const {
return min_; }
5105 void SetMin(int64_t m) { min_ = m; }
5106 int64_t
Max()
const {
return max_; }
5107 void SetMax(int64_t m) { max_ = m; }
5108 int64_t
Value()
const {
5109 DCHECK_EQ(min_, max_);
5113 bool Bound()
const {
return (max_ == min_); }
5114 void SetRange(int64_t l, int64_t u) {
5126 return !(*
this == element);
5146 const IntervalVarAssignment& interval_var_assignment_proto);
5147 void WriteToProto(IntervalVarAssignment* interval_var_assignment_proto)
const;
5149 int64_t
StartMin()
const {
return start_min_; }
5152 CHECK_EQ(start_max_, start_min_);
5156 int64_t
DurationMax()
const {
return duration_max_; }
5158 CHECK_EQ(duration_max_, duration_min_);
5159 return duration_max_;
5161 int64_t
EndMin()
const {
return end_min_; }
5162 int64_t
EndMax()
const {
return end_max_; }
5164 CHECK_EQ(end_max_, end_min_);
5168 int64_t
PerformedMax()
const {
return performed_max_; }
5170 CHECK_EQ(performed_max_, performed_min_);
5171 return performed_max_;
5193 void SetEndMin(int64_t m) { end_min_ = m; }
5206 performed_min_ = mi;
5207 performed_max_ = ma;
5213 bool Bound()
const {
5214 return (start_min_ == start_max_ && duration_min_ == duration_max_ &&
5215 end_min_ == end_max_ && performed_min_ == performed_max_);
5220 return !(*
this == element);
5226 int64_t duration_min_;
5227 int64_t duration_max_;
5230 int64_t performed_min_;
5231 int64_t performed_max_;
5259 const SequenceVarAssignment& sequence_var_assignment_proto);
5260 void WriteToProto(SequenceVarAssignment* sequence_var_assignment_proto)
const;
5265 void SetSequence(
const std::vector<int>& forward_sequence,
5266 const std::vector<int>& backward_sequence,
5267 const std::vector<int>& unperformed);
5271 bool Bound()
const {
5272 return forward_sequence_.size() + unperformed_.size() == var_->size();
5279 return !(*
this == element);
5283 bool CheckClassInvariants();
5286 std::vector<int> forward_sequence_;
5287 std::vector<int> backward_sequence_;
5288 std::vector<int> unperformed_;
5291template <
class V,
class E>
5292class AssignmentContainer {
5296 CHECK(var !=
nullptr);
5298 if (!Find(var, &index)) {
5301 return &elements_[index];
5306 DCHECK(var !=
nullptr);
5307 elements_.emplace_back(var);
5308 return &elements_.back();
5313 elements_[position].Reset(var);
5314 return &elements_[position];
5318 if (!elements_map_.empty()) {
5319 elements_map_.clear();
5324 void Resize(
size_t size) { elements_.resize(size); }
5325 bool Empty()
const {
return elements_.empty(); }
5329 for (
int i = 0;
i < container.elements_.size(); ++
i) {
5330 const E& element = container.elements_[i];
5331 const V*
const var = element.Var();
5333 if (i < elements_.size() && elements_[i].Var() == var) {
5335 }
else if (!Find(var, &index)) {
5338 DCHECK_GE(index, 0);
5339 E*
const local_element = &elements_[index];
5340 local_element->Copy(element);
5341 if (element.Activated()) {
5342 local_element->Activate();
5344 local_element->Deactivate();
5352 for (
int i = 0; i < container.elements_.size(); ++i) {
5353 const E& element = container.elements_[i];
5357 bool Contains(
const V*
const var)
const {
5359 return Find(var, &index);
5363 DCHECK(element !=
nullptr)
5364 <<
"Unknown variable " << var->DebugString() <<
" in solution";
5369 if (Find(var, &index)) {
5374 const E&
Element(
const V*
const var)
const {
5376 DCHECK(element !=
nullptr)
5377 <<
"Unknown variable " << var->DebugString() <<
" in solution";
5382 if (Find(var, &index)) {
5387 const std::vector<E>&
elements()
const {
return elements_; }
5389 const E&
Element(
int index)
const {
return elements_[index]; }
5390 int Size()
const {
return elements_.size(); }
5392 for (E& element : elements_) {
5397 for (E& element : elements_) {
5398 if (element.Activated()) {
5404 for (
const E& element : elements_) {
5405 if (!element.Bound())
return false;
5415 if (
Size() != container.Size()) {
5419 EnsureMapIsUpToDate();
5423 for (
const E& element : container.elements_) {
5424 const int position =
5426 if (position < 0 || elements_[position] != element) {
5433 return !(*
this == container);
5437 void EnsureMapIsUpToDate()
const {
5438 absl::flat_hash_map<const V*, int>* map =
5439 const_cast<absl::flat_hash_map<const V*, int>*
>(&elements_map_);
5440 for (
int i = map->size(); i < elements_.size(); ++i) {
5441 (*map)[elements_[i].Var()] = i;
5444 bool Find(
const V*
const var,
int* index)
const {
5446 const size_t kMaxSizeForLinearAccess = 11;
5447 if (
Size() <= kMaxSizeForLinearAccess) {
5451 for (
int i = 0; i < elements_.size(); ++i) {
5452 if (var == elements_[i].Var()) {
5459 EnsureMapIsUpToDate();
5460 DCHECK_EQ(elements_map_.size(), elements_.size());
5465 std::vector<E> elements_;
5466 absl::flat_hash_map<const V*, int> elements_map_;
5492 return int_var_container_.
Empty() && interval_var_container_.
Empty() &&
5493 sequence_var_container_.
Empty();
5499 int NumIntervalVars()
const {
return interval_var_container_.Size(); }
5500 int NumSequenceVars()
const {
return sequence_var_container_.Size(); }
5506 bool Load(
const std::string& filename);
5508 bool Load(File* file);
5510 void Load(
const AssignmentProto& assignment_proto);
5512 bool Save(
const std::string& filename)
const;
5514 bool Save(File* file)
const;
5516 void Save(AssignmentProto* assignment_proto)
const;
5522 objective_elements_.reserve(vars.size());
5523 for (IntVar*
const var : vars) {
5524 if (var !=
nullptr) {
5525 objective_elements_.emplace_back(var);
5538 return index < objective_elements_.size();
5568 objective_elements_[index].SetMin(m);
5573 objective_elements_[index].SetMax(m);
5578 objective_elements_[index].SetValue(value);
5583 objective_elements_[index].SetRange(l, u);
5587 IntVarElement*
Add(IntVar* var);
5588 void Add(
const std::vector<IntVar*>& vars);
5601 void Add(
const std::vector<IntervalVar*>& vars);
5634 void Add(
const std::vector<SequenceVar*>& vars);
5641 const std::vector<int>& forward_sequence,
5642 const std::vector<int>& backward_sequence,
5643 const std::vector<int>& unperformed);
5645 const std::vector<int>& forward_sequence);
5647 const std::vector<int>& backward_sequence);
5649 const std::vector<int>& unperformed);
5668 objective_elements_[index].Activate();
5673 objective_elements_[index].Deactivate();
5684 return int_var_container_.AreAllElementsBound() &&
5685 interval_var_container_.AreAllElementsBound() &&
5686 sequence_var_container_.AreAllElementsBound();
5689 bool Contains(
const IntVar* var)
const;
5690 bool Contains(
const IntervalVar* var)
const;
5691 bool Contains(
const SequenceVar* var)
const;
5703 return interval_var_container_;
5706 return &interval_var_container_;
5709 return sequence_var_container_;
5712 return &sequence_var_container_;
5715 return int_var_container_ == assignment.int_var_container_ &&
5716 interval_var_container_ == assignment.interval_var_container_ &&
5717 sequence_var_container_ == assignment.sequence_var_container_ &&
5718 objective_elements_ == assignment.objective_elements_;
5721 return !(*
this == assignment);
5728 std::vector<IntVarElement> objective_elements_;
5740 const std::vector<IntVar*>& target_vars,
5742 const std::vector<IntVar*>& source_vars);
5746 Pack(
Solver* s,
const std::vector<IntVar*>& vars,
int number_of_bins);
5759 const std::vector<int64_t>& weights,
const std::vector<int64_t>& bounds);
5778 const std::vector<IntVar*>& loads);
5784 const std::vector<IntVar*>& loads);
5796 const std::vector<IntVar*>& usage,
const std::vector<int64_t>& capacity);
5811 void Post()
override;
5818 bool IsUndecided(
int var_index,
int bin_index)
const;
5820 void Assign(
int var_index,
int bin_index);
5822 bool IsPossible(
int var_index,
int bin_index)
const;
5834 bool IsInProcess()
const;
5835 const std::vector<IntVar*> vars_;
5837 std::vector<Dimension*> dims_;
5838 std::unique_ptr<RevBitMatrix> unprocessed_;
5839 std::vector<std::vector<int>> forced_;
5840 std::vector<std::vector<int>> removed_;
5841 std::vector<IntVarIterator*> holes_;
5844 std::vector<std::pair<int, int>> to_set_;
5845 std::vector<std::pair<int, int>> to_unset_;
5852 const std::string&
name);
5877 virtual const std::vector<IntVar*>&
nexts()
const = 0;
5878 virtual const std::vector<IntVar*>&
actives()
const = 0;
5879 virtual const std::vector<IntVar*>&
time_cumuls()
const = 0;
5880 virtual const std::vector<IntVar*>&
time_slacks()
const = 0;
5897 virtual void Initialize(Assignment* assignment) = 0;
const E & Element(const V *const var) const
E * FastAdd(V *var)
Adds element without checking its presence in the container.
bool AreAllElementsBound() const
void Copy(const AssignmentContainer< V, E > &container)
bool operator!=(const AssignmentContainer< V, E > &container) const
E * MutableElementOrNull(const V *const var)
E * MutableElement(const V *const var)
E * AddAtPosition(V *var, int position)
bool operator==(const AssignmentContainer< V, E > &container) const
void CopyIntersection(const AssignmentContainer< V, E > &container)
const std::vector< E > & elements() const
bool Contains(const V *const var) const
const E * ElementPtrOrNull(const V *const var) const
void Activate(const IntVar *var)
Assignment(Solver *solver)
void SetPerformedRange(const IntervalVar *var, int64_t mi, int64_t ma)
AssignmentContainer< SequenceVar, SequenceVarElement > SequenceContainer
int64_t Value(const IntVar *var) const
void SetStartMax(const IntervalVar *var, int64_t m)
void SetMax(const IntVar *var, int64_t m)
void SetForwardSequence(const SequenceVar *var, const std::vector< int > &forward_sequence)
int64_t EndMin(const IntervalVar *var) const
bool Activated(const IntVar *var) const
IntContainer * MutableIntVarContainer()
int64_t ObjectiveValueFromIndex(int index) const
int64_t DurationMax(const IntervalVar *var) const
void SetObjectiveMax(int64_t m)
int64_t PerformedMin(const IntervalVar *var) const
int64_t Max(const IntVar *var) const
void SetBackwardSequence(const SequenceVar *var, const std::vector< int > &backward_sequence)
int64_t Min(const IntVar *var) const
void SetEndValue(const IntervalVar *var, int64_t value)
bool Contains(const IntVar *var) const
bool HasObjective() const
void SetValue(const IntVar *var, int64_t value)
bool ObjectiveBoundFromIndex(int index) const
void SetEndMin(const IntervalVar *var, int64_t m)
void AddObjectives(const std::vector< IntVar * > &vars)
bool Load(const std::string &filename)
int64_t EndValue(const IntervalVar *var) const
void SetMin(const IntVar *var, int64_t m)
bool operator==(const Assignment &assignment) const
void DeactivateObjectiveFromIndex(int index)
const std::vector< int > & Unperformed(const SequenceVar *var) const
void SetPerformedValue(const IntervalVar *var, int64_t value)
int64_t PerformedValue(const IntervalVar *var) const
IntervalContainer * MutableIntervalVarContainer()
int64_t StartValue(const IntervalVar *var) const
bool ObjectiveBound() const
void SetObjectiveRange(int64_t l, int64_t u)
void SetObjectiveValue(int64_t value)
IntVarElement * Add(IntVar *var)
const IntervalContainer & IntervalVarContainer() const
const SequenceContainer & SequenceVarContainer() const
void SetPerformedMax(const IntervalVar *var, int64_t m)
void ActivateObjectiveFromIndex(int index)
int64_t ObjectiveMinFromIndex(int index) const
void SetObjectiveMinFromIndex(int index, int64_t m)
std::string DebugString() const override
bool AreAllElementsBound() const
int64_t EndMax(const IntervalVar *var) const
int64_t StartMin(const IntervalVar *var) const
IntVarElement * FastAdd(IntVar *var)
Adds without checking if variable has been previously added.
bool ActivatedObjective() const
void Deactivate(const IntVar *var)
int NumIntervalVars() const
void Copy(const Assignment *assignment)
int64_t ObjectiveMin() const
const std::vector< int > & ForwardSequence(const SequenceVar *var) const
AssignmentContainer< IntVar, IntVarElement > IntContainer
IntVar * Objective() const
void SetRange(const IntVar *var, int64_t l, int64_t u)
int64_t ObjectiveMaxFromIndex(int index) const
int64_t ObjectiveMax() const
bool ActivatedObjectiveFromIndex(int index) const
int64_t DurationMin(const IntervalVar *var) const
int NumObjectives() const
const IntContainer & IntVarContainer() const
void SetObjectiveMaxFromIndex(int index, int64_t m)
bool Bound(const IntVar *var) const
void DeactivateObjective()
int64_t DurationValue(const IntervalVar *var) const
AssignmentContainer< IntervalVar, IntervalVarElement > IntervalContainer
void SetSequence(const SequenceVar *var, const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
int NumSequenceVars() const
void SetStartMin(const IntervalVar *var, int64_t m)
void SetDurationMin(const IntervalVar *var, int64_t m)
void SetStartValue(const IntervalVar *var, int64_t value)
void SetDurationMax(const IntervalVar *var, int64_t m)
Assignment & operator=(const Assignment &)=delete
void SetEndMax(const IntervalVar *var, int64_t m)
int64_t ObjectiveValue() const
void SetStartRange(const IntervalVar *var, int64_t mi, int64_t ma)
void SetDurationValue(const IntervalVar *var, int64_t value)
void CopyIntersection(const Assignment *assignment)
void SetEndRange(const IntervalVar *var, int64_t mi, int64_t ma)
void AddObjective(IntVar *const v)
void SetDurationRange(const IntervalVar *var, int64_t mi, int64_t ma)
bool operator!=(const Assignment &assignment) const
SequenceContainer * MutableSequenceVarContainer()
bool HasObjectiveFromIndex(int index) const
int64_t StartMax(const IntervalVar *var) const
IntVar * ObjectiveFromIndex(int index) const
void SetObjectiveValueFromIndex(int index, int64_t value)
bool Save(const std::string &filename) const
Saves the assignment to a file.
const std::vector< int > & BackwardSequence(const SequenceVar *var) const
void SetPerformedMin(const IntervalVar *var, int64_t m)
void SetObjectiveRangeFromIndex(int index, int64_t l, int64_t u)
void SetObjectiveMin(int64_t m)
void SetUnperformed(const SequenceVar *var, const std::vector< int > &unperformed)
int64_t PerformedMax(const IntervalVar *var) const
BaseObject & operator=(const BaseObject &)=delete
virtual std::string DebugString() const
virtual IntVar * ObjectiveVar(int index) const =0
virtual bool Maximize(int index) const =0
virtual IntVar * MinimizationVar(int index) const =0
virtual int64_t BestValue(int index) const =0
BaseObjectiveMonitor & operator=(const BaseObjectiveMonitor &)=delete
void set_active(bool is_active)
BaseObjectiveMonitor(Solver *solver)
virtual int64_t Step(int index) const =0
virtual int Size() const =0
~BaseObjectiveMonitor() override
IntVar * target_var() const
CastConstraint(Solver *const solver, IntVar *const target_var)
~CastConstraint() override
IntVar *const target_var_
Constraint & operator=(const Constraint &)=delete
std::string DebugString() const override
--------------— Constraint class ----------------—
virtual void InitialPropagate()=0
bool IsCastConstraint() const
Is the constraint created by a cast from expression to integer variable?
Constraint(Solver *const solver)
virtual void Accept(ModelVisitor *visitor) const
Accepts the given visitor.
DecisionBuilder & operator=(const DecisionBuilder &)=delete
void set_name(absl::string_view name)
virtual void Accept(ModelVisitor *visitor) const
virtual void AppendMonitors(Solver *solver, std::vector< SearchMonitor * > *extras)
std::string GetName() const
std::string DebugString() const override
-------— Decision Builder -------—
~DecisionBuilder() override
virtual void VisitRankFirstInterval(SequenceVar *sequence, int index)
virtual void VisitSetVariableValue(IntVar *var, int64_t value)
virtual void VisitScheduleOrPostpone(IntervalVar *var, int64_t est)
~DecisionVisitor() override
virtual void VisitRankLastInterval(SequenceVar *sequence, int index)
virtual void VisitUnknownDecision()
virtual void VisitScheduleOrExpedite(IntervalVar *var, int64_t est)
DecisionVisitor & operator=(const DecisionVisitor &)=delete
virtual void VisitSplitVariableDomain(IntVar *var, int64_t value, bool start_with_lower_half)
virtual void Refute(Solver *s)=0
Refute will be called after a backtrack.
std::string DebugString() const override
virtual void Apply(Solver *s)=0
Apply will be called first when the decision is executed.
Decision & operator=(const Decision &)=delete
virtual void Accept(DecisionVisitor *visitor) const
Accepts the given visitor.
Demon & operator=(const Demon &)=delete
virtual Solver::DemonPriority priority() const
---------------— Demon class -------------—
std::string DebugString() const override
void desinhibit(Solver *s)
This method un-inhibits the demon that was previously inhibited.
virtual const std::vector< IntVar * > & time_slacks() const =0
virtual SequenceVar * MakeSequenceVar()=0
Creates a sequence variable from the constraint.
DisjunctiveConstraint(Solver *s, const std::vector< IntervalVar * > &intervals, const std::string &name)
Sequence Constraint.
virtual const std::vector< IntVar * > & time_cumuls() const =0
Solver::IndexEvaluator2 transition_time_
virtual const std::vector< IntVar * > & actives() const =0
int64_t TransitionTime(int before_index, int after_index)
DisjunctiveConstraint & operator=(const DisjunctiveConstraint &)=delete
const std::vector< IntervalVar * > intervals_
virtual const std::vector< IntVar * > & nexts() const =0
~DisjunctiveConstraint() override
void SetTransitionTime(Solver::IndexEvaluator2 transition_time)
bool CheckWithOffset(absl::Duration offset) override
~ImprovementSearchLimit() override
ImprovementSearchLimit(Solver *solver, IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
--— Improvement Search Limit --—
void Init() override
This method is called when the search limit is initialized.
void Install() override
A search monitors adds itself on the active search.
void Copy(const SearchLimit *limit) override
bool AtSolution() override
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
InitAndGetValues(IntVarIterator *it)
virtual void SetValue(int64_t v)
This method sets the value of the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual void SetMax(int64_t m)=0
virtual bool IsVar() const
Returns true if the expression is indeed a variable.
virtual void SetRange(int64_t l, int64_t u)
This method sets both the min and the max of the expression.
virtual int64_t Min() const =0
IntExpr & operator=(const IntExpr &)=delete
virtual void SetMin(int64_t m)=0
virtual void WhenRange(Demon *d)=0
Attach a demon that will watch the min or the max of the expression.
virtual void Range(int64_t *l, int64_t *u)
IntVar * VarWithName(const std::string &name)
-------— IntExpr -------—
virtual IntVar * Var()=0
Creates a variable from the expression.
virtual int64_t Max() const =0
virtual void Accept(ModelVisitor *visitor) const
Accepts the given visitor.
--— Main IntTupleSet class --—
bool operator==(const IntVarElement &element) const
void SetRange(int64_t l, int64_t u)
bool operator!=(const IntVarElement &element) const
IntVarElement()
--------------— Solutions ---------------------—
std::string DebugString() const
void Copy(const IntVarElement &element)
void WriteToProto(IntVarAssignment *int_var_assignment_proto) const
void LoadFromProto(const IntVarAssignment &int_var_assignment_proto)
virtual bool Ok() const =0
This method indicates if we can call Value() or not.
virtual int64_t Value() const =0
This method returns the current value of the iterator.
virtual void Next()=0
This method moves the iterator to the next value.
~IntVarIterator() override
virtual void Init()=0
This method must be called before each loop.
std::string DebugString() const override
Pretty Print.
virtual void WhenBound(Demon *d)=0
virtual void WhenDomain(Demon *d)=0
bool IsVar() const override
Returns true if the expression is indeed a variable.
virtual void SetValues(const std::vector< int64_t > &values)
This method intersects the current domain with the values in the array.
void Accept(ModelVisitor *visitor) const override
Accepts the given visitor.
virtual IntVar * IsDifferent(int64_t constant)=0
int index() const
Returns the index of the variable.
IntVar(Solver *s)
-------— IntVar -------—
virtual IntVarIterator * MakeDomainIterator(bool reversible) const =0
virtual int64_t OldMax() const =0
Returns the previous max.
IntVar * Var() override
Creates a variable from the expression.
virtual IntVar * IsLessOrEqual(int64_t constant)=0
IntVar & operator=(const IntVar &)=delete
virtual bool Contains(int64_t v) const =0
virtual int64_t Value() const =0
virtual int VarType() const
------— IntVar ------—
virtual void RemoveValue(int64_t v)=0
This method removes the value 'v' from the domain of the variable.
virtual uint64_t Size() const =0
This method returns the number of values in the domain of the variable.
virtual IntVarIterator * MakeHoleIterator(bool reversible) const =0
virtual IntVar * IsGreaterOrEqual(int64_t constant)=0
virtual IntVar * IsEqual(int64_t constant)=0
IsEqual.
virtual void RemoveInterval(int64_t l, int64_t u)=0
virtual int64_t OldMin() const =0
Returns the previous min.
virtual void RemoveValues(const std::vector< int64_t > &values)
This method remove the values from the domain of the variable.
void SetStartValue(int64_t v)
void SetDurationValue(int64_t v)
int64_t PerformedValue() const
IntervalVar * Var() const
void SetEndMin(int64_t m)
void SetDurationRange(int64_t mi, int64_t ma)
void SetStartMax(int64_t m)
void SetPerformedMin(int64_t m)
IntervalVarElement * Clone()
void SetStartMin(int64_t m)
std::string DebugString() const
void WriteToProto(IntervalVarAssignment *interval_var_assignment_proto) const
void SetPerformedMax(int64_t m)
void SetPerformedValue(int64_t v)
void SetEndMax(int64_t m)
bool operator!=(const IntervalVarElement &element) const
void Reset(IntervalVar *var)
void Copy(const IntervalVarElement &element)
int64_t DurationMax() const
void SetEndRange(int64_t mi, int64_t ma)
void SetDurationMax(int64_t m)
IntervalVarElement()
--— IntervalVarElement --—
int64_t PerformedMin() const
bool operator==(const IntervalVarElement &element) const
void SetStartRange(int64_t mi, int64_t ma)
int64_t DurationMin() const
void SetPerformedRange(int64_t mi, int64_t ma)
void LoadFromProto(const IntervalVarAssignment &interval_var_assignment_proto)
int64_t PerformedMax() const
int64_t DurationValue() const
void SetEndValue(int64_t v)
void SetDurationMin(int64_t m)
int64_t StartValue() const
virtual IntExpr * PerformedExpr()=0
virtual bool WasPerformedBound() const =0
virtual void WhenEndRange(Demon *d)=0
virtual void SetEndRange(int64_t mi, int64_t ma)=0
virtual int64_t OldEndMax() const =0
virtual int64_t EndMax() const =0
virtual IntExpr * StartExpr()=0
virtual int64_t EndMin() const =0
These methods query, set, and watch the end position of the interval var.
virtual void SetEndMax(int64_t m)=0
virtual void SetPerformed(bool val)=0
bool CannotBePerformed() const
void WhenAnything(Demon *d)
Attaches a demon awakened when anything about this interval changes.
virtual int64_t OldEndMin() const =0
virtual bool MayBePerformed() const =0
virtual void WhenDurationBound(Demon *d)=0
virtual IntExpr * SafeStartExpr(int64_t unperformed_value)=0
virtual IntExpr * SafeDurationExpr(int64_t unperformed_value)=0
virtual IntExpr * SafeEndExpr(int64_t unperformed_value)=0
virtual IntExpr * DurationExpr()=0
virtual void WhenDurationRange(Demon *d)=0
virtual void WhenEndBound(Demon *d)=0
virtual void SetEndMin(int64_t m)=0
virtual IntExpr * EndExpr()=0
virtual void Accept(ModelVisitor *visitor) const =0
Accepts the given visitor.
virtual void WhenPerformedBound(Demon *d)=0
virtual bool MustBePerformed() const =0
--— LightIntFunctionElementCt --—
--— LightIntIntFunctionElementCt --—
--— LightIntIntIntFunctionElementCt --—
-------— Local Search Phase Parameters -------—
static const char kCumulsArgument[]
static const char kStartMaxArgument[]
static const char kVarValueWatcher[]
static const char kScalProdGreaterOrEqual[]
static const char kStepArgument[]
virtual void VisitSequenceVariable(const SequenceVar *variable)
static const char kSolutionLimitArgument[]
static const char kNullIntersect[]
static const char kStartExpr[]
virtual void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments)
virtual void VisitIntervalArgument(const std::string &arg_name, IntervalVar *argument)
Visit interval argument.
static const char kVariableUsageLessConstantExtension[]
static const char kSequenceArgument[]
static const char kAssumePathsArgument[]
void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64_t index_min, int64_t index_max)
--— Helpers --—
static const char kDifferenceOperation[]
static const char kInitialState[]
static const char kTraceOperation[]
static const char kSearchLimitExtension[]
static const char kEndsArgument[]
static const char kRelaxedMinOperation[]
static const char kFixedChargeArgument[]
static const char kDurationMaxArgument[]
void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1 &eval, const std::string &arg_name, int64_t index_max)
Expands function as array when index min is 0.
static const char kSumOperation[]
static const char kFinalStatesArgument[]
static const char kNoCycle[]
static const char kSequenceVariable[]
static const char kTuplesArgument[]
static const char kFailuresLimitArgument[]
static const char kMirrorOperation[]
Operations.
static const char kEarlyCostArgument[]
static const char kInt64ToInt64Extension[]
static const char kNotBetween[]
static const char kOpposite[]
static const char kTransition[]
static const char kActiveArgument[]
argument names:
static const char kObjectiveExtension[]
virtual void BeginVisitModel(const std::string &type_name)
--— Virtual methods for visitors --—
static const char kDurationMinArgument[]
virtual void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *expr)
static const char kNextsArgument[]
static const char kProduct[]
virtual void VisitIntegerArgument(const std::string &arg_name, int64_t value)
Visit integer arguments.
static const char kRangeArgument[]
static const char kLateCostArgument[]
static const char kEndMinArgument[]
static const char kMinArgument[]
virtual void VisitIntegerVariable(const IntVar *variable, IntExpr *delegate)
virtual void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments)
static const char kCoefficientsArgument[]
virtual void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &tuples)
static const char kExpressionArgument[]
static const char kTrace[]
virtual void VisitIntegerVariableEvaluatorArgument(const std::string &arg_name, const Solver::Int64ToIntVar &arguments)
Helpers.
static const char kTargetArgument[]
static const char kStartsArgument[]
static const char kPositionXArgument[]
static const char kStartSyncOnStartOperation[]
static const char kRelationArgument[]
static const char kSortingConstraint[]
static const char kSizeArgument[]
static const char kSumGreaterOrEqual[]
static const char kMaxArgument[]
virtual void EndVisitModel(const std::string &type_name)
static const char kProductOperation[]
static const char kTransitsArgument[]
static const char kPerformedExpr[]
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *argument)
Visit integer expression argument.
static const char kNotMember[]
static const char kValueArgument[]
static const char kLateDateArgument[]
static const char kRightArgument[]
static const char kEarlyDateArgument[]
static const char kScalProdLessOrEqual[]
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
static const char kCapacityArgument[]
static const char kSumLessOrEqual[]
static const char kModuloArgument[]
static const char kVarBoundWatcher[]
static const char kScalProdEqual[]
static const char kSizeYArgument[]
static const char kSequencesArgument[]
static const char kEndMaxArgument[]
static const char kVariableGroupExtension[]
virtual void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64_t > &values)
static const char kValuesArgument[]
static const char kIndexArgument[]
static const char kPack[]
static const char kPathCumul[]
static const char kRelaxedMaxOperation[]
static const char kScalProd[]
static const char kStartSyncOnEndOperation[]
static const char kUsageLessConstantExtension[]
static const char kMaximizeArgument[]
static const char kCumulativeArgument[]
static const char kSquare[]
static const char kIntervalArgument[]
static const char kPositionYArgument[]
static const char kVarsArgument[]
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *constraint)
static const char kVariableArgument[]
static const char kBranchesLimitArgument[]
static const char kIndex2Argument[]
static const char kSumEqual[]
virtual void EndVisitExtension(const std::string &type)
static const char kUsageEqualVariableExtension[]
static const char kSemiContinuous[]
static const char kDemandsArgument[]
static const char kNonEqual[]
static const char kSizeXArgument[]
static const char kLeftArgument[]
static const char kCountAssignedItemsExtension[]
Extension names:
virtual void VisitIntervalVariable(const IntervalVar *variable, const std::string &operation, int64_t value, IntervalVar *delegate)
static const char kCountUsedBinsExtension[]
static const char kStartMinArgument[]
static const char kOptionalArgument[]
static const char kCountArgument[]
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64_t index_min, int64_t index_max)
static const char kTrueConstraint[]
static const char kPartialArgument[]
static const char kDelayedPathCumul[]
virtual void BeginVisitExtension(const std::string &type)
static const char kIndex3Argument[]
static const char kWeightedSumOfAssignedEqualVariableExtension[]
static const char kInt64ToBoolExtension[]
virtual void VisitSequenceArgument(const std::string &arg_name, SequenceVar *argument)
Visit sequence argument.
static const char kEvaluatorArgument[]
virtual void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *expr)
static const char kSmartTimeCheckArgument[]
static const char kCardsArgument[]
static const char kTimeLimitArgument[]
static const char kPower[]
static const char kIntervalsArgument[]
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *constraint)
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 Incr(Solver *const s)
void Decr(Solver *const s)
void Add(Solver *const s, const T &to_add)
bool CurrentInternalValuesAreConstraining() const
const std::vector< IntVar * > & minimization_vars() const
const std::vector< IntVar * > & objective_vars() const
~ObjectiveMonitor() override
int64_t Step(int index) const override
int Size() const override
void SetCurrentInternalValue(int index, int64_t value)
void MakeMinimizationVarsLessOrEqualWithSteps(const T &upper_bounds)
int64_t BestInternalValue(int index) const
bool found_initial_solution_
int64_t CurrentInternalValue(int index) const
bool Maximize(int index) const override
bool AcceptDelta(Assignment *delta, Assignment *deltadelta) override
void Accept(ModelVisitor *visitor) const override
Accepts the given model visitor.
int64_t BestValue(int index) const override
bool AtSolution() override
ObjectiveMonitor(Solver *solver, const std::vector< bool > &maximize, std::vector< IntVar * > vars, std::vector< int64_t > steps)
IntVar * MakeMinimizationVarsLessOrEqualWithStepsStatus(const T &upper_bounds)
void EnterSearch() override
Beginning of the search.
ObjectiveMonitor & operator=(const ObjectiveMonitor &)=delete
IntVar * ObjectiveVar(int index) const override
IntVar * MinimizationVar(int index) const override
void BeginNextDecision(DecisionBuilder *db) override
Internal methods.
int64_t best() const
Returns the best value found during search.
void RefuteDecision(Decision *d) override
Before refuting the decision.
bool AtSolution() override
IntVar * var() const
Returns the variable that is optimized.
OptimizeVar(Solver *solver, bool maximize, IntVar *var, int64_t step)
std::string DebugString() const override
bool AcceptSolution() override
virtual std::string Name() const
void SetUnassigned(int var_index)
void SetAssigned(int var_index)
void Assign(int var_index, int bin_index)
bool IsPossible(int var_index, int bin_index) const
void AddCountUsedBinDimension(IntVar *count_var)
Pack(Solver *s, const std::vector< IntVar * > &vars, int number_of_bins)
--— Pack --—
void AddWeightedSumLessOrEqualConstantDimension(const std::vector< int64_t > &weights, const std::vector< int64_t > &bounds)
-------— API -------—
void AddSumVariableWeightsLessOrEqualConstantDimension(const std::vector< IntVar * > &usage, const std::vector< int64_t > &capacity)
void AddCountAssignedItemsDimension(IntVar *count_var)
void UnassignAllRemainingItems()
void AssignAllRemainingItems()
std::string DebugString() const override
--------------— Constraint class ----------------—
void AssignAllPossibleToBin(int bin_index)
void Accept(ModelVisitor *visitor) const override
Accepts the given visitor.
IntVar * AssignVar(int var_index, int bin_index) const
bool IsAssignedStatusKnown(int var_index) const
void AssignFirstPossibleToBin(int bin_index)
void AddWeightedSumEqualVarDimension(const std::vector< int64_t > &weights, const std::vector< IntVar * > &loads)
void RemoveAllPossibleFromBin(int bin_index)
void AddWeightedSumOfAssignedDimension(const std::vector< int64_t > &weights, IntVar *cost_var)
void InitialPropagate() override
void SetImpossible(int var_index, int bin_index)
void OneDomain(int var_index)
bool IsUndecided(int var_index, int bin_index) const
ProfiledDecisionBuilder(DecisionBuilder *db)
--------------— ProfiledDecisionBuilder ---------—
std::string DebugString() const override
-------— Decision Builder -------—
void Accept(ModelVisitor *visitor) const override
const std::string & name() const
void AppendMonitors(Solver *solver, std::vector< SearchMonitor * > *extras) override
~ProfiledDecisionBuilder() override
PropagationBaseObject & operator=(const PropagationBaseObject &)=delete
void EnqueueVar(Demon *const d)
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
virtual std::string name() const
Object naming.
void set_variable_to_clean_on_fail(IntVar *v)
Shortcut for variable cleaner.
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
void set_action_on_fail(Solver::Action a)
void EnqueueDelayedDemon(Demon *const d)
~PropagationBaseObject() override
virtual std::string BaseName() const
Returns a base name for automatic naming.
void set_name(absl::string_view name)
void reset_action_on_fail()
This method clears the failure callback.
std::string DebugString() const override
bool HasName() const
Returns whether the object has been named or not.
PropagationBaseObject(Solver *const s)
absl::Duration duration_limit() const
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
bool IsUncheckedSolutionLimitReached() override
void Install() override
A search monitors adds itself on the active search.
bool CheckWithOffset(absl::Duration offset) override
int64_t wall_time() const
void Init() override
This method is called when the search limit is initialized.
int64_t solutions() const
int ProgressPercent() override
std::string DebugString() const override
void Accept(ModelVisitor *visitor) const override
Accepts the given model visitor.
void ExitSearch() override
End of the search.
absl::Time AbsoluteSolverDeadline() const
RegularLimit(Solver *s, absl::Duration time, int64_t branches, int64_t failures, int64_t solutions, bool smart_time_check, bool cumulative)
--— Regular Limit --—
void Copy(const SearchLimit *limit) override
void UpdateLimits(absl::Duration time, int64_t branches, int64_t failures, int64_t solutions)
RegularLimit * MakeIdenticalClone() const
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
void SetValue(Solver *const s, const T &val)
Base class of all search limits.
~SearchLimit() override
-------— Search Limits -------—
std::string DebugString() const override
void BeginNextDecision(DecisionBuilder *b) override
Before calling DecisionBuilder::Next.
void PeriodicCheck() override
Periodic call to check limits in long running methods.
bool crossed() const
Returns true if the limit has been crossed.
virtual void Copy(const SearchLimit *limit)=0
void EnterSearch() override
Internal methods.
virtual void Init()=0
This method is called when the search limit is initialized.
void Install() override
A search monitors adds itself on the active search.
SearchLimit & operator=(const SearchLimit &)=delete
virtual bool CheckWithOffset(absl::Duration offset)=0
SearchLimit(Solver *const s)
void RefuteDecision(Decision *d) override
Before refuting the decision.
virtual SearchLimit * MakeClone() const =0
Allocates a clone of the limit.
A search monitor is a simple set of callbacks to monitor all search events.
static constexpr int kNoProgress
virtual void Install()
A search monitors adds itself on the active search.
~SearchMonitor() override
virtual bool AtSolution()
virtual void BeginInitialPropagation()
Before the initial propagation.
virtual void EndFail()
After completing the backtrack.
virtual void RestartSearch()
Restart the search.
virtual void EndInitialPropagation()
After the initial propagation.
virtual bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
virtual void BeginNextDecision(DecisionBuilder *b)
Before calling DecisionBuilder::Next.
virtual void RefuteDecision(Decision *d)
Before refuting the decision.
virtual int ProgressPercent()
virtual void EndNextDecision(DecisionBuilder *b, Decision *d)
After calling DecisionBuilder::Next, along with the returned decision.
virtual void ApplyDecision(Decision *d)
Before applying the decision.
virtual void Accept(ModelVisitor *visitor) const
Accepts the given model visitor.
virtual bool IsUncheckedSolutionLimitReached()
virtual void ExitSearch()
End of the search.
virtual bool LocalOptimum()
SearchMonitor(Solver *const s)
virtual void PeriodicCheck()
Periodic call to check limits in long running methods.
virtual void NoMoreSolutions()
When the search tree is finished.
void ListenToEvent(Solver::MonitorEvent event)
virtual void BeginFail()
Just when the failure occurs.
virtual bool AcceptSolution()
virtual void EnterSearch()
Beginning of the search.
virtual void AfterDecision(Decision *d, bool apply)
virtual void AcceptNeighbor()
After accepting a neighbor during local search.
virtual void AcceptUncheckedNeighbor()
After accepting an unchecked neighbor during local search.
---------------— Search class --------------—
void Reset(SequenceVar *var)
void WriteToProto(SequenceVarAssignment *sequence_var_assignment_proto) const
bool operator==(const SequenceVarElement &element) const
std::string DebugString() const
SequenceVarElement * Clone()
SequenceVarElement()
--— SequenceVarElement --—
void SetUnperformed(const std::vector< int > &unperformed)
const std::vector< int > & ForwardSequence() const
void Copy(const SequenceVarElement &element)
void SetBackwardSequence(const std::vector< int > &backward_sequence)
const std::vector< int > & BackwardSequence() const
void SetSequence(const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
void SetForwardSequence(const std::vector< int > &forward_sequence)
SequenceVar * Var() const
void LoadFromProto(const SequenceVarAssignment &sequence_var_assignment_proto)
const std::vector< int > & Unperformed() const
void RankNotFirst(int index)
void HorizonRange(int64_t *hmin, int64_t *hmax) const
virtual void Accept(ModelVisitor *visitor) const
Accepts the given visitor.
void RankNotLast(int index)
void RankSequence(const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)
IntervalVar * Interval(int index) const
Returns the index_th interval of the sequence.
void ComputePossibleFirstsAndLasts(std::vector< int > *possible_firsts, std::vector< int > *possible_lasts)
int64_t size() const
Returns the number of interval vars in the sequence.
SequenceVar(Solver *s, const std::vector< IntervalVar * > &intervals, const std::vector< IntVar * > &nexts, const std::string &name)
--— SequenceVar --—
void RankFirst(int index)
void ComputeStatistics(int *ranked, int *not_ranked, int *unperformed) const
Compute statistics on the sequence.
void FillSequence(std::vector< int > *rank_first, std::vector< int > *rank_last, std::vector< int > *unperformed) const
std::string DebugString() const override
void ActiveHorizonRange(int64_t *hmin, int64_t *hmax) const
void DurationRange(int64_t *dmin, int64_t *dmax) const
std::string DebugString() const override
int64_t branches(int n) const
Returns the number of branches when the nth solution was found.
SolutionData BuildSolutionDataForCurrentState()
void AddObjectives(const std::vector< IntVar * > &objectives)
const std::vector< int > & ForwardSequence(int n, SequenceVar *var) const
int64_t objective_value(int n) const
Returns the objective value of the nth solution.
~SolutionCollector() override
void Add(IntVar *var)
Add API.
SolutionCollector & operator=(const SolutionCollector &)=delete
std::vector< std::unique_ptr< Assignment > > solution_pool_
int64_t PerformedValue(int n, IntervalVar *var) const
This is a shortcut to get the PerformedValue of 'var' in the nth solution.
void EnterSearch() override
Beginning of the search.
void FreeSolution(Assignment *solution)
void Push(const SolutionData &data)
void PopSolution()
Remove and delete the last popped solution.
const std::vector< int > & Unperformed(int n, SequenceVar *var) const
void AddObjective(IntVar *objective)
bool has_solution() const
Returns whether any solutions were stored during the search.
void check_index(int n) const
int solution_count() const
Returns how many solutions were stored during the search.
void Install() override
A search monitors adds itself on the active search.
int64_t wall_time(int n) const
Returns the wall time in ms for the nth solution.
void PushSolution()
Push the current state as a new solution.
int64_t DurationValue(int n, IntervalVar *var) const
This is a shortcut to get the DurationValue of 'var' in the nth solution.
int64_t ObjectiveValueFromIndex(int n, int index) const
Returns the value of the index-th objective of the nth solution.
int64_t failures(int n) const
const std::vector< int > & BackwardSequence(int n, SequenceVar *var) const
int64_t StartValue(int n, IntervalVar *var) const
This is a shortcut to get the StartValue of 'var' in the nth solution.
SolutionCollector(Solver *solver, const Assignment *assignment)
-------— Solution Collectors --------—
Assignment * solution(int n) const
Returns the nth solution.
int64_t Value(int n, IntVar *var) const
This is a shortcut to get the Value of 'var' in the nth solution.
std::vector< Assignment * > recycle_solutions_
std::vector< SolutionData > solution_data_
std::unique_ptr< Assignment > prototype_
Assignment * last_solution_or_null() const
Returns the last solution if there are any, nullptr otherwise.
int64_t EndValue(int n, IntervalVar *var) const
This is a shortcut to get the EndValue of 'var' in the nth solution.
virtual bool SyncNeeded(Assignment *local_assignment)=0
virtual void Initialize(Assignment *assignment)=0
virtual void RegisterNewSolution(Assignment *assignment)=0
virtual void GetNextSolution(Assignment *assignment)=0
For the time being, Solver is neither MT_SAFE nor MT_HOT.
Constraint * MakeIsLexicalLessOrEqualWithOffsetsCt(std::vector< IntVar * > left, std::vector< IntVar * > right, std::vector< int64_t > offsets, IntVar *boolvar)
Semi-reified version of the above: boolvar -> LexLE(left, right, offsets).
static ConstraintSolverParameters DefaultSolverParameters()
--— ConstraintSolverParameters --—
Constraint * MakeDistribute(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values, const std::vector< IntVar * > &cards)
Aggregated version of count: |{i | v[i] == values[j]}| == cards[j].
std::function< int64_t(Solver *solver, const std::vector< IntVar * > &vars, int64_t first_unbound, int64_t last_unbound)> VariableIndexSelector
void SetBranchSelector(BranchSelector bs)
Sets the given branch selector on the current active search.
IntervalVar * MakeMirrorInterval(IntervalVar *interval_var)
--— API --—
IntExpr * MakeElement(const std::vector< int64_t > &values, IntVar *index)
values[index]
OptimizationDirection optimization_direction() const
The direction of optimization, getter and setter.
Constraint * MakePathConnected(std::vector< IntVar * > nexts, std::vector< int64_t > sources, std::vector< int64_t > sinks, std::vector< IntVar * > status)
bool CurrentlyInSolve() const
Constraint * MakeIsLessOrEqualCt(IntExpr *left, IntExpr *right, IntVar *b)
b == (left <= right)
Decision * MakeAssignVariablesValuesOrDoNothing(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values)
Demon * RegisterDemon(Demon *demon)
Adds a new demon and wraps it inside a DemonProfiler if necessary.
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
Constraint * MakeScalProdLessOrEqual(const std::vector< IntVar * > &vars, const std::vector< int64_t > &coefficients, int64_t cst)
Constraint * MakeIsEqualCstCt(IntExpr *var, int64_t value, IntVar *boolvar)
boolvar == (var == value)
Demon * MakeClosureDemon(Closure closure)
Creates a demon from a closure.
IntExpr * MakeScalProd(const std::vector< IntVar * > &vars, const std::vector< int64_t > &coefs)
scalar product
IntVar * MakeIsGreaterOrEqualVar(IntExpr *left, IntExpr *right)
status var of (left >= right)
IntExpr * MakeDiv(IntExpr *expr, int64_t value)
expr / value (integer division)
Constraint * MakeSortingConstraint(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &sorted)
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
void ExportProfilingOverview(const std::string &filename)
Constraint * MakeLexicalLess(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
bool NextSolution()
Search for the next solution in the search tree.
Constraint * MakeSumEquality(const std::vector< IntVar * > &vars, int64_t cst)
DecisionBuilder * MakeSolveOnce(DecisionBuilder *db)
uint64_t fail_stamp() const
The fail_stamp() is incremented after each backtrack.
int64_t accepted_neighbors() const
The number of accepted neighbors.
DecisionBuilder * MakeApplyBranchSelector(BranchSelector bs)
Creates a decision builder that will set the branch selector.
Constraint * MakeNotMemberCt(IntExpr *expr, const std::vector< int64_t > &values)
expr not in set.
void set_fail_intercept(std::function< void()> fail_intercept)
Internal.
friend class DemonProfiler
Constraint * MakeIsGreaterCt(IntExpr *left, IntExpr *right, IntVar *b)
b == (left > right)
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Constraint * MakeIsGreaterOrEqualCt(IntExpr *left, IntExpr *right, IntVar *b)
b == (left >= right)
SearchMonitor * MakeEnterSearchCallback(std::function< void()> callback)
--— Callback-based search monitors --—
LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)
void IncrementNeighbors()
Constraint * MakeIsEqualCt(IntExpr *v1, IntExpr *v2, IntVar *b)
b == (v1 == v2)
IntVar * MakeIsMemberVar(IntExpr *expr, const std::vector< int64_t > &values)
Decision * MakeAssignVariableValueOrFail(IntVar *var, int64_t value)
Constraint * MakeNonEquality(IntExpr *left, IntExpr *right)
left != right
IntVar * MakeIsEqualCstVar(IntExpr *var, int64_t value)
status var of (var == value)
Constraint * MakeSubCircuit(const std::vector< IntVar * > &nexts)
Decision * MakeVariableLessOrEqualValue(IntVar *var, int64_t value)
IntExpr * MakeMax(const std::vector< IntVar * > &vars)
std::max(vars)
SearchMonitor * MakeLubyRestart(int scale_factor)
int64_t branches() const
The number of branches explored since the creation of the solver.
OptimizeVar * MakeWeightedOptimize(bool maximize, const std::vector< IntVar * > &sub_objectives, const std::vector< int64_t > &weights, int64_t step)
Creates a weighted objective with a given sense (true = maximization).
IntervalVar * MakeFixedDurationStartSyncedOnEndIntervalVar(IntervalVar *interval_var, int64_t duration, int64_t offset)
LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
IntExpr * MakeDifference(IntExpr *left, IntExpr *right)
left - right
SearchMonitor * MakeConstantRestart(int frequency)
int64_t solutions() const
The number of solutions found since the start of the search.
LocalSearchFilter * MakeVariableDomainFilter()
bool NameAllVariables() const
Returns whether all variables should be named.
DecisionBuilder * MakeNestedOptimize(DecisionBuilder *db, Assignment *solution, bool maximize, int64_t step)
Constraint * MakeMemberCt(IntExpr *expr, const std::vector< int64_t > &values)
--— Member and related constraints --—
ABSL_MUST_USE_RESULT RegularLimit * MakeSolutionsLimit(int64_t solutions)
Constraint * MakeGreaterOrEqual(IntExpr *left, IntExpr *right)
left >= right
void AddPropagationMonitor(PropagationMonitor *monitor)
Decision * MakeRankLastInterval(SequenceVar *sequence, int index)
IntVar * MakeBoolVar()
MakeBoolVar will create a variable with a {0, 1} domain.
LocalSearchPhaseParameters * MakeLocalSearchPhaseParameters(IntVar *objective, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder)
Local Search Phase Parameters.
void MakeIntervalVarArray(int count, int64_t start_min, int64_t start_max, int64_t duration_min, int64_t duration_max, int64_t end_min, int64_t end_max, bool optional, absl::string_view name, std::vector< IntervalVar * > *array)
SolutionCollector * MakeBestValueSolutionCollector(const Assignment *assignment, bool maximize)
IntVar * MakeIsLessOrEqualCstVar(IntExpr *var, int64_t value)
status var of (var <= value)
Constraint * MakeIfThenElseCt(IntVar *condition, IntExpr *then_expr, IntExpr *else_expr, IntVar *target_var)
Special cases with arrays of size two.
Solver & operator=(const Solver &)=delete
IntExpr * MakeSum(IntExpr *left, IntExpr *right)
--— Integer Expressions --—
Constraint * MakeCumulative(const std::vector< IntervalVar * > &intervals, const std::vector< int64_t > &demands, int64_t capacity, const std::string &name)
Demands are constant.
ABSL_MUST_USE_RESULT SearchLimit * MakeCustomLimit(std::function< bool()> limiter)
Constraint * MakeScalProdEquality(const std::vector< IntVar * > &vars, const std::vector< int64_t > &coefficients, int64_t cst)
Constraint * MakeIsMemberCt(IntExpr *expr, const std::vector< int64_t > &values, IntVar *boolvar)
boolvar == (expr in set)
static constexpr int kNumPriorities
Number of priorities for demons.
IntExpr * MakeMin(const std::vector< IntVar * > &vars)
std::min(vars)
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
Constraint * MakePathCumul(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, const std::vector< IntVar * > &cumuls, const std::vector< IntVar * > &transits)
const ConstraintSolverParameters & const_parameters() const
Read-only.
IntVar * MakeIsDifferentVar(IntExpr *v1, IntExpr *v2)
status var of (v1 != v2)
IntervalVar * MakeIntervalVar(int64_t start_min, int64_t start_max, int64_t duration_min, int64_t duration_max, int64_t end_min, int64_t end_max, bool optional, const std::string &name)
Variable Duration Interval Var.
ABSL_MUST_USE_RESULT RegularLimit * MakeFailuresLimit(int64_t failures)
Decision * balancing_decision() const
int64_t demon_runs(DemonPriority p) const
The number of demons executed during search for a given priority.
@ NORMAL_PRIORITY
NORMAL_PRIORITY is the highest priority: Demons will be processed first.
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
OptimizeVar * MakeWeightedMinimize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64_t > &weights, int64_t step)
void NewSearch(DecisionBuilder *db, const std::vector< SearchMonitor * > &monitors)
Opens a new top level search.
IntVarLocalSearchFilter * MakeSumObjectiveFilter(const std::vector< IntVar * > &vars, IndexEvaluator2 values, Solver::LocalSearchFilterBound filter_enum)
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)
DecisionBuilder * MakeProfiledDecisionBuilderWrapper(DecisionBuilder *db)
Activates profiling on a decision builder.
bool UseFastLocalSearch() const
Returns true if fast local search is enabled.
IntVar * MakeIsGreaterVar(IntExpr *left, IntExpr *right)
status var of (left > right)
Decision * MakeVariableGreaterOrEqualValue(IntVar *var, int64_t value)
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
friend class RevImmutableMultiMap
Assignment * RunUncheckedLocalSearch(const Assignment *initial_solution, LocalSearchFilterManager *filter_manager, LocalSearchOperator *ls_operator, const std::vector< SearchMonitor * > &monitors, RegularLimit *limit, absl::flat_hash_set< IntVar * > *touched=nullptr)
IntVar * MakeIsLessVar(IntExpr *left, IntExpr *right)
status var of (left < right)
ABSL_MUST_USE_RESULT RegularLimit * MakeTimeLimit(absl::Duration time)
Creates a search limit that constrains the running time.
void clear_fail_intercept()
const std::string & context() const
Gets the current context of the search.
Constraint * MakeCircuit(const std::vector< IntVar * > &nexts)
Force the "nexts" variable to create a complete Hamiltonian path.
Constraint * MakeDeviation(const std::vector< IntVar * > &vars, IntVar *deviation_var, int64_t total_sum)
int SearchLeftDepth() const
std::function< int64_t(int64_t)> IndexEvaluator1
Callback typedefs.
SolverState
This enum represents the state of the solver w.r.t. the search.
@ IN_SEARCH
Executing the search code.
@ IN_ROOT_NODE
Executing the root node.
@ PROBLEM_INFEASIBLE
After search, the model is infeasible.
@ NO_MORE_SOLUTIONS
After failed NextSolution and before EndSearch.
@ OUTSIDE_SEARCH
Before search, after search.
@ AT_SOLUTION
After successful NextSolution and before EndSearch.
std::function< int64_t(int64_t, int64_t, int64_t)> IndexEvaluator3
void set_context(absl::string_view context)
Sets the current context of the search.
DisjunctiveConstraint * MakeDisjunctiveConstraint(const std::vector< IntervalVar * > &intervals, const std::string &name)
-------— Factory methods -------—
friend class LocalSearchProfiler
LocalSearchStatistics GetLocalSearchStatistics() const
Returns detailed local search statistics.
void SaveAndAdd(T *adr, T val)
All-in-one SaveAndAdd_value.
IntVar * RegisterIntVar(IntVar *var)
Registers a new IntVar and wraps it inside a TraceIntVar if necessary.
Constraint * MakeIsGreaterCstCt(IntExpr *v, int64_t c, IntVar *b)
b == (v > c)
DecisionBuilder * Compose(DecisionBuilder *db1, DecisionBuilder *db2)
ObjectiveMonitor * MakeTabuSearch(bool maximize, IntVar *objective, int64_t step, const std::vector< IntVar * > &vars, int64_t keep_tenure, int64_t forbid_tenure, double tabu_factor)
MetaHeuristics which try to get the search out of local optima.
std::string LocalSearchProfile() const
IntervalVar * MakeFixedDurationEndSyncedOnStartIntervalVar(IntervalVar *interval_var, int64_t duration, int64_t offset)
Constraint * MakeAllDifferentExcept(const std::vector< IntVar * > &vars, int64_t escape_value)
DecisionBuilder * MakePhase(const std::vector< IntVar * > &vars, IntVarStrategy var_str, IntValueStrategy val_str)
IntVar * MakeIsGreaterCstVar(IntExpr *var, int64_t value)
status var of (var > value)
bool CheckAssignment(Assignment *solution)
Checks whether the given assignment satisfies all relevant constraints.
LocalSearchOperator * RandomConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
bool IsBooleanVar(IntExpr *expr, IntVar **inner_var, bool *is_negated) const
void AddBacktrackAction(Action a, bool fast)
void MakeFixedDurationIntervalVarArray(int count, int64_t start_min, int64_t start_max, int64_t duration, bool optional, absl::string_view name, std::vector< IntervalVar * > *array)
friend class FindOneNeighbor
Decision * MakeAssignVariableValue(IntVar *var, int64_t val)
Decisions.
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
std::string model_name() const
Returns the name of the model.
LocalSearchFilter * MakeAcceptFilter()
Local Search Filters.
IntExpr * MakeMonotonicElement(IndexEvaluator1 values, bool increasing, IntVar *index)
Decision * MakeAssignVariablesValuesOrFail(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values)
Decision * MakeScheduleOrExpedite(IntervalVar *var, int64_t est, int64_t *marker)
Constraint * MakeSumLessOrEqual(const std::vector< IntVar * > &vars, int64_t cst)
Variation on arrays.
Constraint * MakeIsLessCstCt(IntExpr *v, int64_t c, IntVar *b)
b == (v < c)
std::function< DecisionModification()> BranchSelector
SolutionPool * MakeDefaultSolutionPool()
Solution Pool.
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)
LocalSearchOperator * MakeNeighborhoodLimit(LocalSearchOperator *op, int64_t limit)
ConstraintSolverStatistics GetConstraintSolverStatistics() const
Returns detailed cp search statistics.
void SetGuidedLocalSearchPenaltyCallback(std::function< int64_t(int64_t, int64_t, int64_t)> penalty_callback)
Constraint * MakePathEnergyCostConstraint(PathEnergyCostConstraintSpecification specification)
Decision * MakeSplitVariableDomain(IntVar *var, int64_t val, bool start_with_lower_half)
Constraint * MakeSumGreaterOrEqual(const std::vector< IntVar * > &vars, int64_t cst)
Constraint * MakeTemporalDisjunction(IntervalVar *t1, IntervalVar *t2, IntVar *alt)
Constraint * MakeAllowedAssignments(const std::vector< IntVar * > &vars, const IntTupleSet &tuples)
------— API -------—
Constraint * MakePathPrecedenceConstraint(std::vector< IntVar * > nexts, const std::vector< std::pair< int, int > > &precedences)
IntervalVar * MakeFixedDurationIntervalVar(int64_t start_min, int64_t start_max, int64_t duration, bool optional, const std::string &name)
DecisionBuilder * MakeLocalSearchPhase(Assignment *assignment, LocalSearchPhaseParameters *parameters)
Constraint * MakeLightElement(F values, IntVar *const var, IntVar *const index, std::function< bool()> deep_serialize=nullptr)
Constraint * MakeLess(IntExpr *left, IntExpr *right)
left < right
IntExpr * CastExpression(const IntVar *var) const
!defined(SWIG)
ModelCache * Cache() const
Returns the cache of the model.
IntExpr * MakeOpposite(IntExpr *expr)
-expr
Constraint * MakeAtMost(std::vector< IntVar * > vars, int64_t value, int64_t max_count)
|{i | vars[i] == value}| <= max_count
ABSL_MUST_USE_RESULT ImprovementSearchLimit * MakeLexicographicImprovementLimit(std::vector< IntVar * > objective_vars, std::vector< bool > maximize, std::vector< double > objective_scaling_factors, std::vector< double > objective_offsets, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
Constraint * MakeAbsEquality(IntVar *var, IntVar *abs_var)
Creates the constraint abs(var) == abs_var.
OptimizeVar * MakeOptimize(bool maximize, IntVar *v, int64_t step)
Creates a objective with a given sense (true = maximization).
void MakeBoolVarArray(int var_count, const std::string &name, std::vector< IntVar * > *vars)
friend class SimpleRevFIFO
DecisionBuilder * MakeConstraintAdder(Constraint *ct)
@ STARTS_BEFORE
t starts before 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.
@ ENDS_BEFORE
t ends before d, i.e. End(t) <= d.
@ STARTS_AT
t starts at d, i.e. Start(t) == d.
@ ENDS_AFTER
t ends after d, i.e. End(t) >= d.
IntExpr * MakePiecewiseLinearExpr(IntExpr *expr, const PiecewiseLinearFunction &f)
IntExpr * RegisterIntExpr(IntExpr *expr)
Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
int64_t neighbors() const
The number of neighbors created.
Constraint * MakeIsDifferentCt(IntExpr *v1, IntExpr *v2, IntVar *b)
b == (v1 != v2)
Constraint * MakeNullIntersectExcept(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars, int64_t escape_value)
IntExpr * MakeModulo(IntExpr *x, int64_t mod)
Modulo expression x % mod (with the python convention for modulo).
std::function< void(Solver *)> Action
Constraint * MakeGreater(IntExpr *left, IntExpr *right)
left > right
DisjunctiveConstraint * MakeStrictDisjunctiveConstraint(const std::vector< IntervalVar * > &intervals, const std::string &name)
Constraint * MakeLexicalLessOrEqual(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
OptimizationDirection
Optimization directions.
IntVar * MakeIsEqualVar(IntExpr *v1, IntExpr *v2)
status var of (v1 == v2)
IntVar * MakeIsDifferentCstVar(IntExpr *var, int64_t value)
status var of (var != value)
LocalSearchOperator * MakeOperator(const std::vector< IntVar * > &vars, LocalSearchOperators op, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)
Local Search Operators.
SearchMonitor * MakeAtSolutionCallback(std::function< void()> callback)
Constraint * MakeCount(const std::vector< IntVar * > &vars, int64_t value, int64_t max_count)
|{i | vars[i] == value}| == max_count
@ CHOOSE_MIN_SIZE_LOWEST_MIN
@ CHOOSE_RANDOM
Randomly select one of the remaining unbound variables.
@ CHOOSE_MIN_SIZE_LOWEST_MAX
@ INT_VAR_DEFAULT
The default behavior is CHOOSE_FIRST_UNBOUND.
@ INT_VAR_SIMPLE
The simple selection is CHOOSE_FIRST_UNBOUND.
@ CHOOSE_MIN_SIZE_HIGHEST_MAX
@ CHOOSE_MAX_REGRET_ON_MIN
@ CHOOSE_MIN_SIZE_HIGHEST_MIN
IntVar * MakeIsBetweenVar(IntExpr *v, int64_t l, int64_t u)
Constraint * MakeElementEquality(const std::vector< int64_t > &vals, IntVar *index, IntVar *target)
IntervalVar * MakeFixedInterval(int64_t start, int64_t duration, const std::string &name)
Creates a fixed and performed interval.
Pack * MakePack(const std::vector< IntVar * > &vars, int number_of_bins)
@ LE
Move is accepted when the current objective value <= objective.Max.
@ GE
Move is accepted when the current objective value >= objective.Min.
DecisionBuilder * Try(DecisionBuilder *db1, DecisionBuilder *db2)
std::function< int64_t(int64_t, int64_t)> IndexEvaluator2
T * RevAllocArray(T *object)
SolutionCollector * MakeAllSolutionCollector()
DecisionBuilder * MakeDefaultPhase(const std::vector< IntVar * > &vars)
SequenceStrategy
Used for scheduling. Not yet implemented.
@ CHOOSE_RANDOM_RANK_FORWARD
@ CHOOSE_MIN_SLACK_RANK_FORWARD
LocalSearchFilter * MakeRejectFilter()
IntervalVar * RegisterIntervalVar(IntervalVar *var)
int64_t unchecked_solutions() const
The number of unchecked solutions found by local search.
IntVar * MakeIsGreaterOrEqualCstVar(IntExpr *var, int64_t value)
status var of (var >= value)
Constraint * MakeMinEquality(const std::vector< IntVar * > &vars, IntVar *min_var)
Decision * MakeDecision(Action apply, Action refute)
Constraint * MakeIsLessCt(IntExpr *left, IntExpr *right, IntVar *b)
b == (left < right)
ObjectiveMonitor * MakeLexicographicSimulatedAnnealing(const std::vector< bool > &maximize, std::vector< IntVar * > vars, std::vector< int64_t > steps, std::vector< int64_t > initial_temperatures)
SolutionCollector * MakeFirstSolutionCollector()
Constraint * MakeIndexOfConstraint(const std::vector< IntVar * > &vars, IntVar *index, int64_t target)
int32_t Rand32(int32_t size)
Returns a random value between 0 and 'size' - 1;.
void FinishCurrentSearch()
Tells the solver to kill or restart the current search.
Constraint * MakeDelayedPathCumul(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, const std::vector< IntVar * > &cumuls, const std::vector< IntVar * > &transits)
std::function< bool(int64_t)> IndexFilter1
void Accept(ModelVisitor *visitor) const
Accepts the given model visitor.
Constraint * MakeIndexOfFirstMinValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
IntExpr * MakeAbs(IntExpr *expr)
expr
Decision * MakeRankFirstInterval(SequenceVar *sequence, int index)
IntExpr * MakeSquare(IntExpr *expr)
expr * expr
std::vector< int64_t > tmp_vector_
SolutionCollector * MakeLastSolutionCollector()
ModelVisitor * MakeVariableDegreeVisitor(absl::flat_hash_map< const IntVar *, int > *map)
Compute the number of constraints a variable is attached to.
Constraint * MakeNoCycle(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, IndexFilter1 sink_handler=nullptr)
bool IsProfilingEnabled() const
Returns whether we are profiling the solver.
MonitorEvent
Search monitor events.
@ kIsUncheckedSolutionLimitReached
@ kAcceptUncheckedNeighbor
@ kLast
Dummy event whose underlying int is the number of MonitorEvent enums.
@ kBeginInitialPropagation
std::function< void()> Closure
friend class SearchMonitor
Constraint * MakeIndexOfFirstMaxValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
Constraint * MakeScalProdGreaterOrEqual(const std::vector< IntVar * > &vars, const std::vector< int64_t > &coeffs, int64_t cst)
IntExpr * MakeIndexExpression(const std::vector< IntVar * > &vars, int64_t value)
std::string SearchContext() const
@ STARTS_AT_START
t1 starts at t2 start, i.e. Start(t1) == Start(t2) + delay.
@ 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.
@ ENDS_AT_END
t1 ends at t2 end, i.e. End(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_END
t1 starts at t2 end, i.e. Start(t1) == End(t2) + delay.
friend class RoutingModel
SolutionCollector * MakeBestLexicographicValueSolutionCollector(const Assignment *assignment, std::vector< bool > maximize)
SearchMonitor * MakeExitSearchCallback(std::function< void()> callback)
LocalSearchOperator * MultiArmedBanditConcatenateOperators(const std::vector< LocalSearchOperator * > &ops, double memory_coefficient, double exploration_coefficient, bool maximize)
SearchMonitor * MakeSearchTrace(const std::string &prefix)
Decision * MakeAssignVariablesValues(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values)
SolutionCollector * MakeNBestValueSolutionCollector(const Assignment *assignment, int solution_count, bool maximize)
Constraint * MakeMaxEquality(const std::vector< IntVar * > &vars, IntVar *max_var)
void ClearLocalSearchState()
Clears the local search state.
std::function< IntVar *(int64_t)> Int64ToIntVar
Constraint * MakeEquality(IntExpr *left, IntExpr *right)
left == right
IntervalVar * MakeIntervalRelaxedMax(IntervalVar *interval_var)
IntVar * MakeIsLessOrEqualVar(IntExpr *left, IntExpr *right)
status var of (left <= right)
ObjectiveMonitor * MakeLexicographicTabuSearch(const std::vector< bool > &maximize, std::vector< IntVar * > objectives, std::vector< int64_t > steps, const std::vector< IntVar * > &vars, int64_t keep_tenure, int64_t forbid_tenure, double tabu_factor)
Assignment * MakeAssignment()
This method creates an empty assignment.
DecisionBuilder * MakeDecisionBuilderFromAssignment(Assignment *assignment, DecisionBuilder *db, const std::vector< IntVar * > &vars)
EvaluatorLocalSearchOperators
int64_t wall_time() const
ABSL_MUST_USE_RESULT RegularLimit * MakeBranchesLimit(int64_t branches)
@ RELOCATE
Relocate neighborhood with length of 1 (see OROPT comment).
Constraint * MakeTrueConstraint()
This constraint always succeeds.
Decision * MakeScheduleOrPostpone(IntervalVar *var, int64_t est, int64_t *marker)
Demon * MakeDelayedConstraintInitialPropagateCallback(Constraint *ct)
SearchMonitor * MakeSearchLog(int branch_period)
friend class PropagationBaseObject
ObjectiveMonitor * MakeSimulatedAnnealing(bool maximize, IntVar *v, int64_t step, int64_t initial_temperature)
Constraint * MakeLessOrEqual(IntExpr *left, IntExpr *right)
left <= right
bool HasName(const PropagationBaseObject *object) const
Returns whether the object has been named or not.
Constraint * MakeIsGreaterOrEqualCstCt(IntExpr *var, int64_t value, IntVar *boolvar)
boolvar == (var >= value)
int64_t GetGuidedLocalSearchPenalty(int64_t i, int64_t j, int64_t k) const
Returns the current (Guided Local Search)penalty of the given arc tuple.
OptimizeVar * MakeMinimize(IntVar *v, int64_t step)
Creates a minimization objective.
void SetSearchContext(Search *search, absl::string_view search_context)
void RestartCurrentSearch()
ObjectiveMonitor * MakeGuidedLocalSearch(bool maximize, IntVar *objective, IndexEvaluator2 objective_function, int64_t step, const std::vector< IntVar * > &vars, double penalty_factor, std::function< std::vector< std::pair< int64_t, int64_t > >(int64_t, int64_t)> get_equivalent_pairs=nullptr, bool reset_penalties_on_new_best_solution=false)
IntervalVar * MakeFixedDurationEndSyncedOnEndIntervalVar(IntervalVar *interval_var, int64_t duration, int64_t offset)
Constraint * MakeLexicalLessOrEqualWithOffsets(std::vector< IntVar * > left, std::vector< IntVar * > right, std::vector< int64_t > offsets)
std::string DebugString() const
!defined(SWIG)
Constraint * MakeBetweenCt(IntExpr *expr, int64_t l, int64_t u)
--— Between and related constraints --—
DemonProfiler * demon_profiler() const
Access to demon profiler.
Demon * MakeConstraintInitialPropagateCallback(Constraint *ct)
void MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax, const std::string &name, std::vector< IntVar * > *vars)
ABSL_MUST_USE_RESULT RegularLimit * MakeLimit(absl::Duration time, int64_t branches, int64_t failures, int64_t solutions, bool smart_time_check=false, bool cumulative=false)
OptimizeVar * MakeWeightedMaximize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64_t > &weights, int64_t step)
Creates a maximization weigthed objective.
int64_t filtered_neighbors() const
The number of filtered neighbors (neighbors accepted by filters).
Decision * MakeAssignVariableValueOrDoNothing(IntVar *var, int64_t value)
SolverState state() const
State of the solver.
SolutionCollector * MakeNBestLexicographicValueSolutionCollector(const Assignment *assignment, int solution_count, std::vector< bool > maximize)
int64_t Rand64(int64_t size)
Returns a random value between 0 and 'size' - 1;.
IntVar * MakeIntVar(int64_t min, int64_t max, const std::string &name)
--— Int Variables and Constants --—
ConstraintSolverParameters parameters() const
Stored Parameters.
Constraint * MakeAllDifferent(const std::vector< IntVar * > &vars)
Constraint * MakeIntervalVarRelationWithDelay(IntervalVar *t1, BinaryIntervalRelation r, IntervalVar *t2, int64_t delay)
std::function< bool(int64_t, int64_t, int64_t)> VariableValueComparator
bool Solve(DecisionBuilder *db, const std::vector< SearchMonitor * > &monitors)
ModelVisitor * MakePrintModelVisitor()
Prints the model.
void SaveValue(T *o)
reversibility
Constraint * MakeFalseConstraint()
This constraint always fails.
friend void InternalSaveBooleanVarValue(Solver *, IntVar *)
ObjectiveMonitor * MakeGenericTabuSearch(bool maximize, IntVar *v, int64_t step, const std::vector< IntVar * > &tabu_vars, int64_t forbid_tenure)
void ReSeed(int32_t seed)
Reseed the solver random generator.
@ INTERVAL_SET_TIMES_FORWARD
@ INTERVAL_DEFAULT
The default is INTERVAL_SET_TIMES_FORWARD.
@ INTERVAL_SET_TIMES_BACKWARD
@ INTERVAL_SIMPLE
The simple is INTERVAL_SET_TIMES_FORWARD.
bool IsProduct(IntExpr *expr, IntExpr **inner_expr, int64_t *coefficient)
IntExpr * MakeConvexPiecewiseExpr(IntExpr *expr, int64_t early_cost, int64_t early_date, int64_t late_date, int64_t late_cost)
Convex piecewise function.
Assignment * GetOrCreateLocalSearchState()
IntervalVar * MakeFixedDurationStartSyncedOnStartIntervalVar(IntervalVar *interval_var, int64_t duration, int64_t offset)
Synced Interval Vars.
void set_optimization_direction(OptimizationDirection direction)
IntExpr * MakePower(IntExpr *expr, int64_t n)
expr ^ n (n > 0)
IntExpr * MakeConditionalExpression(IntVar *condition, IntExpr *expr, int64_t unperformed_value)
Conditional Expr condition ? expr : unperformed_value.
@ ASSIGN_MAX_VALUE
Selects the max value of the selected variable.
@ INT_VALUE_DEFAULT
The default behavior is ASSIGN_MIN_VALUE.
@ INT_VALUE_SIMPLE
The simple selection is ASSIGN_MIN_VALUE.
@ 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.
OptimizeVar * MakeLexicographicOptimize(std::vector< bool > maximize, std::vector< IntVar * > variables, std::vector< int64_t > steps)
SearchMonitor * MakeSymmetryManager(const std::vector< SymmetryBreaker * > &visitors)
Symmetry Breaking.
IntVar * MakeIsLessCstVar(IntExpr *var, int64_t value)
status var of (var < value)
IntervalVar * MakeIntervalRelaxedMin(IntervalVar *interval_var)
int64_t failures() const
The number of failures encountered since the creation of the solver.
bool CheckConstraint(Constraint *ct)
RegularLimitParameters MakeDefaultRegularLimitParameters() const
Creates a regular limit proto containing default values.
bool InstrumentsDemons() const
Returns whether we are instrumenting demons.
Constraint * MakeIsBetweenCt(IntExpr *expr, int64_t l, int64_t u, IntVar *b)
b == (l <= expr <= u)
Constraint * MakeIsLessOrEqualCstCt(IntExpr *var, int64_t value, IntVar *boolvar)
boolvar == (var <= value)
PropagationMonitor * GetPropagationMonitor() const
Returns the propagation monitor.
Constraint * MakeTransitionConstraint(const std::vector< IntVar * > &vars, const IntTupleSet &transition_table, int64_t initial_state, const std::vector< int64_t > &final_states)
Decision * MakeFailDecision()
IntExpr * MakeProd(IntExpr *left, IntExpr *right)
left * right
IntVar * MakeIntConst(int64_t val, const std::string &name)
IntConst will create a constant expression.
Constraint * MakeIntervalVarRelation(IntervalVar *t, UnaryIntervalRelation r, int64_t d)
Demon * MakeActionDemon(Action action)
Creates a demon from a callback.
Constraint * MakeNullIntersect(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars)
Solver(const std::string &name)
Solver API.
bool InstrumentsVariables() const
Returns whether we are tracing variables.
Constraint * MakeNotBetweenCt(IntExpr *expr, int64_t l, int64_t u)
void AddLocalSearchMonitor(LocalSearchMonitor *monitor)
BaseObjectiveMonitor * MakeRoundRobinCompoundObjectiveMonitor(std::vector< BaseObjectiveMonitor * > monitors, int num_max_local_optima_before_metaheuristic_switch)
Constraint * MakePathTransitPrecedenceConstraint(std::vector< IntVar * > nexts, std::vector< IntVar * > transits, const std::vector< std::pair< int, int > > &precedences)
static int64_t MemoryUsage()
Current memory usage in bytes.
Constraint * MakeCover(const std::vector< IntervalVar * > &vars, IntervalVar *target_var)
void AddConstraint(Constraint *c)
LocalSearchOperator * MakeRandomLnsOperator(const std::vector< IntVar * > &vars, int number_of_variables)
Constraint * MakeInversePermutationConstraint(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
void SetUseFastLocalSearch(bool use_fast_local_search)
OptimizeVar * MakeMaximize(IntVar *v, int64_t step)
Creates a maximization objective.
@ CHOOSE_DYNAMIC_GLOBAL_BEST
@ CHOOSE_STATIC_GLOBAL_BEST
Constraint * MakeIsDifferentCstCt(IntExpr *var, int64_t value, IntVar *boolvar)
boolvar == (var != value)
IntExpr * MakeSemiContinuousExpr(IntExpr *expr, int64_t fixed_charge, int64_t step)
ABSL_MUST_USE_RESULT ImprovementSearchLimit * MakeImprovementLimit(IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
std::function< int64_t(const IntVar *v, int64_t id)> VariableValueSelector
bool SolveAndCommit(DecisionBuilder *db, const std::vector< SearchMonitor * > &monitors)
void AddCastConstraint(CastConstraint *constraint, IntVar *target_var, IntExpr *expr)
OR_DLL ABSL_DECLARE_FLAG(int64_t, cp_random_seed)
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
const MapUtilMappedT< Collection > & FindWithDefault(const Collection &collection, const KeyType &key, const MapUtilMappedT< Collection > &value)
dual_gradient T(y - `dual_solution`) class DiagonalTrustRegionProblemFromQp
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
int64_t CapSub(int64_t x, int64_t y)
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
int64_t One()
This method returns 1.
void SetAssignmentFromAssignment(Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
NOLINT.
int64_t CapOpp(int64_t v)
Note(user): -kint64min != kint64max, but kint64max == ~kint64min.
bool use_last_conflict
Should we use last conflict method. The default is false.
DecisionBuilder * decision_builder
When defined, this overrides the default impact based decision builder.
int initialization_splits
int heuristic_num_failures_limit
The failure limit for each heuristic that we run.
DisplayLevel display_level
@ CHOOSE_MAX_VALUE_IMPACT
@ CHOOSE_MAX_AVERAGE_IMPACT
ValueSelection value_selection_schema
This parameter describes which value to select for a given var.
int random_seed
Seed used to initialize the random part in some heuristics.
VariableSelection var_selection_schema
static Iterator End(IntVarIterator *it)
bool operator!=(const Iterator &other) const
static Iterator Begin(IntVarIterator *it)
These are the only way to construct an Iterator.
int64_t operator*() const
int64_t ObjectiveValue() const
bool operator<(const SolutionData &other) const
int64_t ObjectiveValueFromIndex(int index) const
int64_t cost_per_unit_above_threshold
int64_t cost_per_unit_below_threshold
std::vector< IntVar * > paths
std::vector< IntVar * > nexts
std::vector< EnergyCost > path_energy_costs
std::vector< bool > path_used_when_empty
std::vector< IntVar * > forces
std::vector< int64_t > path_starts
std::vector< IntVar * > costs
std::vector< int64_t > path_ends
std::vector< IntVar * > distances
Creates a search monitor from logging parameters.
std::vector< double > scaling_factors
std::vector< double > offsets
std::function< std::string()> display_callback
bool display_on_new_solutions_only
std::vector< IntVar * > variables
---------------— StateMarker / StateInfo struct --------—
CycleTimer SimpleCycleTimer
static const int64_t kint64max