Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
constraint_solver.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
67
68#ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
69#define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
70
71#include <stddef.h>
72#include <stdint.h>
73
74#include <deque>
75#include <functional>
76#include <memory>
77#include <ostream>
78#include <random>
79#include <string>
80#include <utility>
81#include <vector>
82
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"
97#include "ortools/base/timer.h"
98#include "ortools/base/types.h"
99#include "ortools/constraint_solver/search_stats.pb.h"
100#include "ortools/constraint_solver/solver_parameters.pb.h"
105
106#if !defined(SWIG)
107OR_DLL ABSL_DECLARE_FLAG(int64_t, cp_random_seed);
108OR_DLL ABSL_DECLARE_FLAG(bool, cp_disable_solve);
109#endif // !defined(SWIG)
110
111class File;
112
113namespace operations_research {
114
115class Assignment;
116class AssignmentProto;
117class BaseObject;
118class CastConstraint;
119class Constraint;
120class Decision;
121class DecisionBuilder;
122class DecisionVisitor;
123class Demon;
124class DemonProfiler;
125class Dimension;
126class DisjunctiveConstraint;
127class ImprovementSearchLimit;
128class IntExpr;
129class IntVar;
130class IntVarAssignment;
131class IntVarLocalSearchFilter;
132class IntervalVar;
133class IntervalVarAssignment;
134class LocalSearch;
135class LocalSearchFilter;
136class LocalSearchFilterManager;
137class LocalSearchMonitor;
138class LocalSearchOperator;
139class LocalSearchPhaseParameters;
140class LocalSearchProfiler;
141class ModelCache;
142class ModelVisitor;
143class ObjectiveMonitor;
144class BaseObjectiveMonitor;
145class OptimizeVar;
146class Pack;
147class ProfiledDecisionBuilder;
148class PropagationBaseObject;
149class PropagationMonitor;
150class Queue;
151class RegularLimit;
152class RegularLimitParameters;
153class RevBitMatrix;
154class Search;
155class SearchLimit;
156class SearchMonitor;
157class SequenceVar;
158class SequenceVarAssignment;
159class SolutionCollector;
160class SolutionPool;
161class SymmetryBreaker;
162struct StateInfo;
163struct Trail;
164template <class T>
165class SimpleRevFIFO;
166template <typename F>
167class LightIntFunctionElementCt;
168template <typename F>
169class LightIntIntFunctionElementCt;
170template <typename F>
171class LightIntIntIntFunctionElementCt;
172
173inline int64_t CpRandomSeed() {
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);
177}
178
188 };
189
190 enum ValueSelection {
249
258class Solver {
259 public:
264 struct IntegerCastInfo {
266 : variable(nullptr), expression(nullptr), maintainer(nullptr) {}
267 IntegerCastInfo(IntVar* const v, IntExpr* const e, Constraint* const c)
268 : variable(v), expression(e), maintainer(c) {}
272 };
273
275 static constexpr int kNumPriorities = 3;
277 /// This enum describes the strategy used to select the next branching
278 /// variable at each node during the search.
285
290
291 /// Randomly select one of the remaining unbound variables.
309
317
325
331
337
347
351
355 };
356 // TODO(user): add HIGHEST_MIN and LOWEST_MAX.
357
360 enum IntValueStrategy {
363
369
401
406
425
427 /// The simple is INTERVAL_SET_TIMES_FORWARD.
433
435 };
448
449 TWOOPT,
450
451 /// Relocate: OROPT and RELOCATE.
452 /// Operator which moves a sub-chain of a path to another position; the
453 /// specified chain length is the fixed length of the chains being moved.
454 /// When this length is 1, the operator simply moves a node to another
455 /// position.
456 /// Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5, for a chain
457 /// length of 2 (where (1, 5) are first and last nodes of the path and can
458 /// therefore not be moved):
459 /// 1 -> 4 -> [2 -> 3] -> 5
460 /// 1 -> [3 -> 4] -> 2 -> 5
461 ///
462 /// Using Relocate with chain lengths of 1, 2 and 3 together is equivalent
463 /// to the OrOpt operator on a path. The OrOpt operator is a limited
464 /// version of 3Opt (breaks 3 arcs on a path).
465 OROPT,
466
468 RELOCATE,
469
477 EXCHANGE,
488 CROSS,
489
497
504
512
519
527
547 PATHLNS,
548
552
557
566 INCREMENT,
567
571 DECREMENT,
572
581 };
582
590 LK,
591
595
599
606 TSPLNS
607 };
608
615 GE,
617 LE,
620 EQ
621 };
622
635 NORMAL_PRIORITY = 2,
636 };
637
639 /// temporal relation between the two intervals t1 and t2.
643
646
649
650
652
653 /// t1 starts after t2 end, i.e. Start(t1) >= End(t2) + delay.
669 };
678 ENDS_AT,
679
682
683
685
686 /// t starts at d, i.e. Start(t) == d.
687 STARTS_AT,
696
701 };
702
711 NO_CHANGE,
712
715
716 KEEP_LEFT,
717
744
767 kEndFail,
781 // Dummy event whose underlying int is the number of MonitorEvent enums.
783 };
784#endif // SWIG
787 typedef std::function<int64_t(int64_t)> IndexEvaluator1;
788 typedef std::function<int64_t(int64_t, int64_t)> IndexEvaluator2;
789 typedef std::function<int64_t(int64_t, int64_t, int64_t)> IndexEvaluator3;
791 typedef std::function<bool(int64_t)> IndexFilter1;
793 typedef std::function<IntVar*(int64_t)> Int64ToIntVar;
794
795 typedef std::function<int64_t(Solver* solver,
796 const std::vector<IntVar*>& vars,
797 int64_t first_unbound, int64_t last_unbound)>
799
800 typedef std::function<int64_t(const IntVar* v, int64_t id)>
802 typedef std::function<bool(int64_t, int64_t, int64_t)>
804 typedef std::function<DecisionModification()> BranchSelector;
805 // TODO(user): wrap in swig.
806 typedef std::function<void(Solver*)> Action;
807 typedef std::function<void()> Closure;
808
810 explicit Solver(const std::string& name);
811 Solver(const std::string& name, const ConstraintSolverParameters& parameters);
812
813#ifndef SWIG
814 // This type is neither copyable nor movable.
815 Solver(const Solver&) = delete;
816 Solver& operator=(const Solver&) = delete;
817#endif
818
822 ConstraintSolverParameters parameters() const { return parameters_; }
823 // Read-only.
824 const ConstraintSolverParameters& const_parameters() const {
825 return parameters_;
826 }
828 // TODO(user): Move to constraint_solver_parameters.h.
829 static ConstraintSolverParameters DefaultSolverParameters();
830
832
836 template <class T>
837 void SaveValue(T* o) {
838 InternalSaveValue(o);
839 }
840
850 /// BaseObject: for all subclasses predefined in the library, the
851 /// corresponding factory methods (e.g., MakeIntVar(...),
852 /// MakeAllDifferent(...) already take care of the registration.
853 template <typename T>
854 T* RevAlloc(T* object) {
855 return reinterpret_cast<T*>(SafeRevAlloc(object));
856 }
857
864 template <typename T>
865 T* RevAllocArray(T* object) {
866 return reinterpret_cast<T*>(SafeRevAllocArray(object));
867 }
868
869 /// Adds the constraint 'c' to the model.
870 ///
871 /// After calling this method, and until there is a backtrack that undoes the
872 /// addition, any assignment of variables to values must satisfy the given
873 /// constraint in order to be considered feasible. There are two fairly
874 /// different use cases:
875 ///
876 /// - the most common use case is modeling: the given constraint is really
877 /// part of the problem that the user is trying to solve. In this use case,
878 /// AddConstraint is called outside of search (i.e., with <tt>state() ==
879 /// OUTSIDE_SEARCH</tt>). Most users should only use AddConstraint in this
880 /// way. In this case, the constraint will belong to the model forever: it
881 /// cannot be removed by backtracking.
882 ///
883 /// - a rarer use case is that 'c' is not a real constraint of the model. It
884 /// may be a constraint generated by a branching decision (a constraint whose
885 /// goal is to restrict the search space), a symmetry breaking constraint (a
886 /// constraint that does restrict the search space, but in a way that cannot
887 /// have an impact on the quality of the solutions in the subtree), or an
888 /// inferred constraint that, while having no semantic value to the model (it
889 /// does not restrict the set of solutions), is worth having because we
890 /// believe it may strengthen the propagation. In these cases, it happens
891 /// that the constraint is added during the search (i.e., with state() ==
892 /// IN_SEARCH or state() == IN_ROOT_NODE). When a constraint is
893 /// added during a search, it applies only to the subtree of the search tree
894 /// rooted at the current node, and will be automatically removed by
895 /// backtracking.
896 ///
897 /// This method does not take ownership of the constraint. If the constraint
898 /// has been created by any factory method (Solver::MakeXXX), it will
899 /// automatically be deleted. However, power users who implement their own
900 /// constraints should do: solver.AddConstraint(solver.RevAlloc(new
901 /// MyConstraint(...));
902 void AddConstraint(Constraint* c);
906 void AddCastConstraint(CastConstraint* constraint, IntVar* target_var,
907 IntExpr* expr);
908
950 bool Solve(DecisionBuilder* db, const std::vector<SearchMonitor*>& monitors);
951 bool Solve(DecisionBuilder* db);
952 bool Solve(DecisionBuilder* db, SearchMonitor* m1);
955 SearchMonitor* m3);
959
968
969 void NewSearch(DecisionBuilder* db,
970 const std::vector<SearchMonitor*>& monitors);
971 void NewSearch(DecisionBuilder* db);
975 SearchMonitor* m3);
978
979 bool NextSolution();
980 void RestartSearch();
981 void EndSearch();
983
993 const std::vector<SearchMonitor*>& monitors);
997 SearchMonitor* m2);
999 SearchMonitor* m3);
1000
1003
1007 bool CheckConstraint(Constraint* ct);
1008
1010 SolverState state() const { return state_; }
1011
1013 void Fail();
1014
1015#if !defined(SWIG)
1020 void AddBacktrackAction(Action a, bool fast);
1021#endif
1022
1024 std::string DebugString() const;
1025
1027 static int64_t MemoryUsage();
1028
1033 absl::Time Now() const;
1034
1037 int64_t wall_time() const;
1038
1040 int64_t branches() const { return branches_; }
1041
1043 int64_t solutions() const;
1044
1046 int64_t unchecked_solutions() const;
1047
1049 int64_t demon_runs(DemonPriority p) const { return demon_runs_[p]; }
1050
1052 int64_t failures() const { return fails_; }
1053
1055 int64_t neighbors() const { return neighbors_; }
1056
1059 void ClearNeighbors() { neighbors_ = 0; }
1060 void IncrementNeighbors() { ++neighbors_; }
1061
1063 int64_t filtered_neighbors() const { return filtered_neighbors_; }
1064
1066 int64_t accepted_neighbors() const { return accepted_neighbors_; }
1070 uint64_t stamp() const;
1071
1073 uint64_t fail_stamp() const;
1074
1076 void set_context(absl::string_view context) { context_ = context; }
1077
1079 const std::string& context() const { return context_; }
1080
1083 return optimization_direction_;
1084 }
1086 optimization_direction_ = direction;
1088
1089 // An internal method called by Guided Local Search to share current
1090 // penalties with the solver.
1092 std::function<int64_t(int64_t, int64_t, int64_t)> penalty_callback) {
1093 penalty_callback_ = std::move(penalty_callback);
1094 }
1095 // Returns the current (Guided Local Search)penalty of the given arc tuple.
1096 int64_t GetGuidedLocalSearchPenalty(int64_t i, int64_t j, int64_t k) const {
1097 return (penalty_callback_ == nullptr) ? 0 : penalty_callback_(i, j, k);
1098 }
1099
1100 // All factories (MakeXXX methods) encapsulate creation of objects
1101 // through RevAlloc(). Hence, the Solver used for allocating the
1102 // returned object will retain ownership of the allocated memory.
1103 // Destructors are called upon backtrack, or when the Solver is
1104 // itself destructed.
1105
1106 // ----- Int Variables and Constants -----
1107
1109 IntVar* MakeIntVar(int64_t min, int64_t max, const std::string& name);
1110
1112 IntVar* MakeIntVar(const std::vector<int64_t>& values,
1113 const std::string& name);
1114
1115
1116 IntVar* MakeIntVar(const std::vector<int>& values, const std::string& name);
1117
1118 /// MakeIntVar will create the best range based int var for the bounds given.
1119 IntVar* MakeIntVar(int64_t min, int64_t max);
1120
1122 IntVar* MakeIntVar(const std::vector<int64_t>& values);
1125 IntVar* MakeIntVar(const std::vector<int>& values);
1126
1128 IntVar* MakeBoolVar(const std::string& name);
1129
1132
1134 IntVar* MakeIntConst(int64_t val, const std::string& name);
1135
1137 IntVar* MakeIntConst(int64_t val);
1138
1142 void MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax,
1143 const std::string& name, std::vector<IntVar*>* vars);
1146 void MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax,
1147 std::vector<IntVar*>* vars);
1149 IntVar** MakeIntVarArray(int var_count, int64_t vmin, int64_t vmax,
1150 const std::string& name);
1151
1155 void MakeBoolVarArray(int var_count, const std::string& name,
1156 std::vector<IntVar*>* vars);
1159 void MakeBoolVarArray(int var_count, std::vector<IntVar*>* vars);
1161 IntVar** MakeBoolVarArray(int var_count, const std::string& name);
1162
1163 // ----- Integer Expressions -----
1164
1166 IntExpr* MakeSum(IntExpr* left, IntExpr* right);
1168 IntExpr* MakeSum(IntExpr* expr, int64_t value);
1170 IntExpr* MakeSum(const std::vector<IntVar*>& vars);
1171
1173 IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1174 const std::vector<int64_t>& coefs);
1176 IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1177 const std::vector<int>& coefs);
1178
1180 IntExpr* MakeDifference(IntExpr* left, IntExpr* right);
1182 IntExpr* MakeDifference(int64_t value, IntExpr* expr);
1185
1187 IntExpr* MakeProd(IntExpr* left, IntExpr* right);
1189 IntExpr* MakeProd(IntExpr* expr, int64_t value);
1190
1192 IntExpr* MakeDiv(IntExpr* expr, int64_t value);
1194 IntExpr* MakeDiv(IntExpr* numerator, IntExpr* denominator);
1195
1197 IntExpr* MakeAbs(IntExpr* expr);
1199 IntExpr* MakeSquare(IntExpr* expr);
1201 IntExpr* MakePower(IntExpr* expr, int64_t n);
1202
1204 IntExpr* MakeElement(const std::vector<int64_t>& values, IntVar* index);
1206 IntExpr* MakeElement(const std::vector<int>& values, IntVar* index);
1207
1211 IntExpr* MakeElement(IndexEvaluator1 values, IntVar* index);
1218 IntExpr* MakeMonotonicElement(IndexEvaluator1 values, bool increasing,
1219 IntVar* index);
1221 IntExpr* MakeElement(IndexEvaluator2 values, IntVar* index1, IntVar* index2);
1222
1224 IntExpr* MakeElement(const std::vector<IntVar*>& vars, IntVar* index);
1225
1226#if !defined(SWIG)
1228 IntExpr* MakeElement(Int64ToIntVar vars, int64_t range_start,
1229 int64_t range_end, IntVar* argument);
1230#endif // SWIG
1231
1236
1243 template <typename F>
1244 Constraint* MakeLightElement(F values, IntVar* const var, IntVar* const index,
1245 std::function<bool()> deep_serialize = nullptr) {
1247 this, var, index, std::move(values), std::move(deep_serialize)));
1248 }
1249
1256 template <typename F>
1257 Constraint* MakeLightElement(F values, IntVar* const var,
1258 IntVar* const index1, IntVar* const index2,
1259 std::function<bool()> deep_serialize = nullptr) {
1261 this, var, index1, index2, std::move(values),
1262 std::move(deep_serialize)));
1263 }
1264
1269 template <typename F>
1270 Constraint* MakeLightElement(F values, IntVar* const var,
1271 IntVar* const index1, IntVar* const index2,
1272 IntVar* const index3) {
1274 this, var, index1, index2, index3, std::move(values)));
1275 }
1276
1279 IntExpr* MakeIndexExpression(const std::vector<IntVar*>& vars, int64_t value);
1280
1282 Constraint* MakeIfThenElseCt(IntVar* condition, IntExpr* then_expr,
1283 IntExpr* else_expr, IntVar* target_var);
1286 IntExpr* MakeMin(const std::vector<IntVar*>& vars);
1288 IntExpr* MakeMin(IntExpr* left, IntExpr* right);
1290 IntExpr* MakeMin(IntExpr* expr, int64_t value);
1291
1292 IntExpr* MakeMin(IntExpr* expr, int value);
1293
1295 IntExpr* MakeMax(const std::vector<IntVar*>& vars);
1299 IntExpr* MakeMax(IntExpr* expr, int64_t value);
1301 IntExpr* MakeMax(IntExpr* expr, int value);
1302
1303
1304 IntExpr* MakeConvexPiecewiseExpr(IntExpr* expr, int64_t early_cost,
1305 int64_t early_date, int64_t late_date,
1306 int64_t late_cost);
1307
1310 IntExpr* MakeSemiContinuousExpr(IntExpr* expr, int64_t fixed_charge,
1311 int64_t step);
1312
1315 // TODO(user): Investigate if we can merge all three piecewise linear
1317#ifndef SWIG
1319 const PiecewiseLinearFunction& f);
1320#endif
1321
1323 IntExpr* MakeModulo(IntExpr* x, int64_t mod);
1324
1326 IntExpr* MakeModulo(IntExpr* x, IntExpr* mod);
1327
1330 int64_t unperformed_value);
1331
1336 Constraint* MakeFalseConstraint(const std::string& explanation);
1337
1339 Constraint* MakeIsEqualCstCt(IntExpr* var, int64_t value, IntVar* boolvar);
1341 IntVar* MakeIsEqualCstVar(IntExpr* var, int64_t value);
1347 Constraint* MakeEquality(IntExpr* left, IntExpr* right);
1349 Constraint* MakeEquality(IntExpr* expr, int64_t value);
1351 Constraint* MakeEquality(IntExpr* expr, int value);
1352
1354 Constraint* MakeIsDifferentCstCt(IntExpr* var, int64_t value,
1355 IntVar* boolvar);
1357 IntVar* MakeIsDifferentCstVar(IntExpr* var, int64_t value);
1363 Constraint* MakeNonEquality(IntExpr* left, IntExpr* right);
1365 Constraint* MakeNonEquality(IntExpr* expr, int64_t value);
1367 Constraint* MakeNonEquality(IntExpr* expr, int value);
1368
1370 Constraint* MakeIsLessOrEqualCstCt(IntExpr* var, int64_t value,
1371 IntVar* boolvar);
1373 IntVar* MakeIsLessOrEqualCstVar(IntExpr* var, int64_t value);
1379 Constraint* MakeLessOrEqual(IntExpr* left, IntExpr* right);
1381 Constraint* MakeLessOrEqual(IntExpr* expr, int64_t value);
1383 Constraint* MakeLessOrEqual(IntExpr* expr, int value);
1384
1386 Constraint* MakeIsGreaterOrEqualCstCt(IntExpr* var, int64_t value,
1387 IntVar* boolvar);
1389 IntVar* MakeIsGreaterOrEqualCstVar(IntExpr* var, int64_t value);
1397 Constraint* MakeGreaterOrEqual(IntExpr* expr, int64_t value);
1399 Constraint* MakeGreaterOrEqual(IntExpr* expr, int value);
1400
1402 Constraint* MakeIsGreaterCstCt(IntExpr* v, int64_t c, IntVar* b);
1404 IntVar* MakeIsGreaterCstVar(IntExpr* var, int64_t value);
1406 IntVar* MakeIsGreaterVar(IntExpr* left, IntExpr* right);
1408 Constraint* MakeIsGreaterCt(IntExpr* left, IntExpr* right, IntVar* b);
1410 Constraint* MakeGreater(IntExpr* left, IntExpr* right);
1412 Constraint* MakeGreater(IntExpr* expr, int64_t value);
1414 Constraint* MakeGreater(IntExpr* expr, int value);
1415
1417 Constraint* MakeIsLessCstCt(IntExpr* v, int64_t c, IntVar* b);
1419 IntVar* MakeIsLessCstVar(IntExpr* var, int64_t value);
1421 IntVar* MakeIsLessVar(IntExpr* left, IntExpr* right);
1423 Constraint* MakeIsLessCt(IntExpr* left, IntExpr* right, IntVar* b);
1425 Constraint* MakeLess(IntExpr* left, IntExpr* right);
1427 Constraint* MakeLess(IntExpr* expr, int64_t value);
1429 Constraint* MakeLess(IntExpr* expr, int value);
1430
1432 Constraint* MakeSumLessOrEqual(const std::vector<IntVar*>& vars, int64_t cst);
1433 Constraint* MakeSumGreaterOrEqual(const std::vector<IntVar*>& vars,
1434 int64_t cst);
1435 Constraint* MakeSumEquality(const std::vector<IntVar*>& vars, int64_t cst);
1436 Constraint* MakeSumEquality(const std::vector<IntVar*>& vars, IntVar* var);
1437 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1438 const std::vector<int64_t>& coefficients,
1439 int64_t cst);
1440 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1441 const std::vector<int>& coefficients,
1442 int64_t cst);
1443 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1444 const std::vector<int64_t>& coefficients,
1445 IntVar* target);
1446 Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1447 const std::vector<int>& coefficients,
1448 IntVar* target);
1449 Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1450 const std::vector<int64_t>& coeffs,
1451 int64_t cst);
1452 Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1453 const std::vector<int>& coeffs,
1454 int64_t cst);
1455 Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1456 const std::vector<int64_t>& coefficients,
1457 int64_t cst);
1458 Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1459 const std::vector<int>& coefficients,
1460 int64_t cst);
1461
1462 Constraint* MakeMinEquality(const std::vector<IntVar*>& vars,
1463 IntVar* min_var);
1464 Constraint* MakeMaxEquality(const std::vector<IntVar*>& vars,
1465 IntVar* max_var);
1466
1467 Constraint* MakeElementEquality(const std::vector<int64_t>& vals,
1468 IntVar* index, IntVar* target);
1469 Constraint* MakeElementEquality(const std::vector<int>& vals, IntVar* index,
1470 IntVar* target);
1471 Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1472 IntVar* index, IntVar* target);
1473 Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1474 IntVar* index, int64_t target);
1476 Constraint* MakeAbsEquality(IntVar* var, IntVar* abs_var);
1481 Constraint* MakeIndexOfConstraint(const std::vector<IntVar*>& vars,
1482 IntVar* index, int64_t target);
1483
1491#if !defined(SWIG)
1493 Demon* MakeActionDemon(Action action);
1494#endif
1496 Demon* MakeClosureDemon(Closure closure);
1497
1498 // ----- Between and related constraints -----
1499
1501 Constraint* MakeBetweenCt(IntExpr* expr, int64_t l, int64_t u);
1502
1507 Constraint* MakeNotBetweenCt(IntExpr* expr, int64_t l, int64_t u);
1508
1510 Constraint* MakeIsBetweenCt(IntExpr* expr, int64_t l, int64_t u, IntVar* b);
1511 IntVar* MakeIsBetweenVar(IntExpr* v, int64_t l, int64_t u);
1512
1513 // ----- Member and related constraints -----
1514
1517 Constraint* MakeMemberCt(IntExpr* expr, const std::vector<int64_t>& values);
1518 Constraint* MakeMemberCt(IntExpr* expr, const std::vector<int>& values);
1519
1522 const std::vector<int64_t>& values);
1523 Constraint* MakeNotMemberCt(IntExpr* expr, const std::vector<int>& values);
1524
1526 Constraint* MakeNotMemberCt(IntExpr* expr, std::vector<int64_t> starts,
1527 std::vector<int64_t> ends);
1529 Constraint* MakeNotMemberCt(IntExpr* expr, std::vector<int> starts,
1530 std::vector<int> ends);
1531#if !defined(SWIG)
1534 SortedDisjointIntervalList intervals);
1535#endif // !defined(SWIG)
1536
1538 Constraint* MakeIsMemberCt(IntExpr* expr, const std::vector<int64_t>& values,
1539 IntVar* boolvar);
1540 Constraint* MakeIsMemberCt(IntExpr* expr, const std::vector<int>& values,
1541 IntVar* boolvar);
1542 IntVar* MakeIsMemberVar(IntExpr* expr, const std::vector<int64_t>& values);
1543 IntVar* MakeIsMemberVar(IntExpr* expr, const std::vector<int>& values);
1544
1546 Constraint* MakeAtMost(std::vector<IntVar*> vars, int64_t value,
1547 int64_t max_count);
1549 Constraint* MakeCount(const std::vector<IntVar*>& vars, int64_t value,
1550 int64_t max_count);
1552 Constraint* MakeCount(const std::vector<IntVar*>& vars, int64_t value,
1553 IntVar* max_count);
1554
1556 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1557 const std::vector<int64_t>& values,
1558 const std::vector<IntVar*>& cards);
1560 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1561 const std::vector<int>& values,
1562 const std::vector<IntVar*>& cards);
1564 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1565 const std::vector<IntVar*>& cards);
1568 Constraint* MakeDistribute(const std::vector<IntVar*>& vars, int64_t card_min,
1569 int64_t card_max, int64_t card_size);
1573 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1574 const std::vector<int64_t>& card_min,
1575 const std::vector<int64_t>& card_max);
1579 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1580 const std::vector<int>& card_min,
1581 const std::vector<int>& card_max);
1585 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1586 const std::vector<int64_t>& values,
1587 const std::vector<int64_t>& card_min,
1588 const std::vector<int64_t>& card_max);
1592 Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1593 const std::vector<int>& values,
1594 const std::vector<int>& card_min,
1595 const std::vector<int>& card_max);
1596
1601 Constraint* MakeDeviation(const std::vector<IntVar*>& vars,
1602 IntVar* deviation_var, int64_t total_sum);
1603
1606 Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars);
1607
1611 Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars,
1612 bool stronger_propagation);
1613
1616 Constraint* MakeAllDifferentExcept(const std::vector<IntVar*>& vars,
1617 int64_t escape_value);
1618 // TODO(user): Do we need a version with an array of escape values.
1619
1635 Constraint* MakeSortingConstraint(const std::vector<IntVar*>& vars,
1636 const std::vector<IntVar*>& sorted);
1637 // TODO(user): Add void MakeSortedArray(
1638 // const std::vector<IntVar*>& vars,
1639 // std::vector<IntVar*>* const sorted);
1640
1643 Constraint* MakeLexicalLess(const std::vector<IntVar*>& left,
1644 const std::vector<IntVar*>& right);
1645
1648 Constraint* MakeLexicalLessOrEqual(const std::vector<IntVar*>& left,
1649 const std::vector<IntVar*>& right);
1650
1655 Constraint* MakeLexicalLessOrEqualWithOffsets(std::vector<IntVar*> left,
1656 std::vector<IntVar*> right,
1657 std::vector<int64_t> offsets);
1658
1659 // Semi-reified version of the above: boolvar -> LexLE(left, right, offsets).
1661 std::vector<IntVar*> left, std::vector<IntVar*> right,
1662 std::vector<int64_t> offsets, IntVar* boolvar);
1663
1669 const std::vector<IntVar*>& left, const std::vector<IntVar*>& right);
1670
1674 IntVar* index, const std::vector<IntVar*>& vars);
1675
1679 IntVar* index, const std::vector<IntVar*>& vars);
1680
1685 Constraint* MakeNullIntersect(const std::vector<IntVar*>& first_vars,
1686 const std::vector<IntVar*>& second_vars);
1687
1693 Constraint* MakeNullIntersectExcept(const std::vector<IntVar*>& first_vars,
1694 const std::vector<IntVar*>& second_vars,
1695 int64_t escape_value);
1696
1697 // TODO(user): Implement MakeAllNullIntersect taking an array of
1698 // variable vectors.
1699
1709 Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1710 const std::vector<IntVar*>& active,
1711 IndexFilter1 sink_handler = nullptr);
1712 Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1713 const std::vector<IntVar*>& active,
1714 IndexFilter1 sink_handler, bool assume_paths);
1715
1717 Constraint* MakeCircuit(const std::vector<IntVar*>& nexts);
1718
1721 Constraint* MakeSubCircuit(const std::vector<IntVar*>& nexts);
1722
1727 Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1728 const std::vector<IntVar*>& active,
1729 const std::vector<IntVar*>& cumuls,
1730 const std::vector<IntVar*>& transits);
1733 // TODO(user): Merge with other path-cumuls constraints.
1734 Constraint* MakeDelayedPathCumul(const std::vector<IntVar*>& nexts,
1735 const std::vector<IntVar*>& active,
1736 const std::vector<IntVar*>& cumuls,
1737 const std::vector<IntVar*>& transits);
1744 Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1745 const std::vector<IntVar*>& active,
1746 const std::vector<IntVar*>& cumuls,
1747 IndexEvaluator2 transit_evaluator);
1748
1755 Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1756 const std::vector<IntVar*>& active,
1757 const std::vector<IntVar*>& cumuls,
1758 const std::vector<IntVar*>& slacks,
1759 IndexEvaluator2 transit_evaluator);
1762 // TODO(user): Only does checking on WhenBound events on next variables.
1764 Constraint* MakePathConnected(std::vector<IntVar*> nexts,
1765 std::vector<int64_t> sources,
1766 std::vector<int64_t> sinks,
1767 std::vector<IntVar*> status);
1768#ifndef SWIG
1771 // TODO(user): This constraint does not make holes in variable domains;
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);
1813 struct EnergyCost {
1814 int64_t threshold;
1817 bool IsNull() const {
1818 return (cost_per_unit_below_threshold == 0 || threshold == 0) &&
1820 }
1821 };
1822 std::vector<IntVar*> nexts;
1823 std::vector<IntVar*> paths;
1824 std::vector<IntVar*> forces;
1825 std::vector<IntVar*> distances;
1826 std::vector<EnergyCost> path_energy_costs;
1827 std::vector<bool> path_used_when_empty;
1828 std::vector<int64_t> path_starts;
1829 std::vector<int64_t> path_ends;
1830 std::vector<IntVar*> costs;
1831 };
1834#endif // !SWIG
1838 Constraint* MakeMapDomain(IntVar* var, const std::vector<IntVar*>& actives);
1839
1842 /// variables involved in the relation and the graph is given by a
1843 /// integer tuple set.
1844 Constraint* MakeAllowedAssignments(const std::vector<IntVar*>& vars,
1845 const IntTupleSet& tuples);
1847 /// This constraint create a finite automaton that will check the
1848 /// sequence of variables vars. It uses a transition table called
1849 /// 'transition_table'. Each transition is a triple
1850 /// (current_state, variable_value, new_state).
1851 /// The initial state is given, and the set of accepted states is decribed
1852 /// by 'final_states'. These states are hidden inside the constraint.
1853 /// Only the transitions (i.e. the variables) are visible.
1855 const std::vector<IntVar*>& vars, const IntTupleSet& transition_table,
1856 int64_t initial_state, const std::vector<int64_t>& final_states);
1862
1865 Constraint* MakeTransitionConstraint(const std::vector<IntVar*>& vars,
1866 const IntTupleSet& transition_table,
1867 int64_t initial_state,
1868 const std::vector<int>& final_states);
1869
1870#if defined(SWIGPYTHON)
1873 const std::vector<IntVar*>& vars,
1874 const std::vector<std::vector<int64_t> /*keep for swig*/>& raw_tuples) {
1875 IntTupleSet tuples(vars.size());
1876 tuples.InsertAll(raw_tuples);
1877 return MakeAllowedAssignments(vars, tuples);
1878 }
1879
1881 const std::vector<IntVar*>& vars,
1882 const std::vector<std::vector<int64_t> /*keep for swig*/>&
1883 raw_transitions,
1884 int64_t initial_state, const std::vector<int>& final_states) {
1885 IntTupleSet transitions(3);
1886 transitions.InsertAll(raw_transitions);
1887 return MakeTransitionConstraint(vars, transitions, initial_state,
1888 final_states);
1889 }
1890#endif
1891
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);
1909
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);
1927
1933 Pack* MakePack(const std::vector<IntVar*>& vars, int number_of_bins);
1934
1939 IntervalVar* MakeFixedDurationIntervalVar(int64_t start_min,
1940 int64_t start_max, int64_t duration,
1941 bool optional,
1942 const std::string& name);
1943
1946 void MakeFixedDurationIntervalVarArray(int count, int64_t start_min,
1947 int64_t start_max, int64_t duration,
1948 bool optional, absl::string_view name,
1949 std::vector<IntervalVar*>* array);
1950
1954 int64_t duration,
1955 const std::string& name);
1956
1960 int64_t duration,
1961 IntVar* performed_variable,
1962 const std::string& name);
1963
1967 const std::vector<IntVar*>& start_variables, int64_t duration,
1968 absl::string_view name, std::vector<IntervalVar*>* array);
1969
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);
1982
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);
1990
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);
1998
2000 IntervalVar* MakeFixedInterval(int64_t start, int64_t duration,
2001 const std::string& name);
2002
2005 IntervalVar* MakeIntervalVar(int64_t start_min, int64_t start_max,
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);
2009
2012 void MakeIntervalVarArray(int count, int64_t start_min, int64_t start_max,
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);
2017
2021
2027 IntervalVar* interval_var, int64_t duration, int64_t offset);
2028
2034 IntervalVar* interval_var, int64_t duration, int64_t offset);
2035
2041 IntervalVar* interval_var, int64_t duration, int64_t offset);
2042
2048 IntervalVar* interval_var, int64_t duration, int64_t offset);
2049
2068
2087
2091 int64_t d);
2092
2095 IntervalVar* t2);
2096
2103 IntervalVar* t2, int64_t delay);
2104
2109 IntVar* alt);
2110
2114
2118 const std::vector<IntervalVar*>& intervals, const std::string& name);
2119
2124 const std::vector<IntervalVar*>& intervals, const std::string& name);
2125
2135 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2136 const std::vector<int64_t>& demands,
2137 int64_t capacity, const std::string& name);
2138
2148 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2149 const std::vector<int>& demands, int64_t capacity,
2150 const std::string& name);
2151
2161 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2162 const std::vector<int64_t>& demands,
2163 IntVar* capacity, absl::string_view name);
2164
2174 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2175 const std::vector<int>& demands, IntVar* capacity,
2176 const std::string& name);
2177
2185 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2186 const std::vector<IntVar*>& demands,
2187 int64_t capacity, const std::string& name);
2188
2196 Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2197 const std::vector<IntVar*>& demands,
2198 IntVar* capacity, const std::string& name);
2199
2205 Constraint* MakeCover(const std::vector<IntervalVar*>& vars,
2206 IntervalVar* target_var);
2207
2210
2213
2216
2222
2228
2234 const Assignment* assignment, bool maximize);
2238 const Assignment* assignment, std::vector<bool> maximize);
2248 std::vector<bool> maximize);
2249
2254 const Assignment* assignment, int solution_count, bool maximize);
2256 bool maximize);
2260 const Assignment* assignment, int solution_count,
2261 std::vector<bool> maximize);
2263 int solution_count, std::vector<bool> maximize);
2264
2270
2272 OptimizeVar* MakeMinimize(IntVar* v, int64_t step);
2273
2275 OptimizeVar* MakeMaximize(IntVar* v, int64_t step);
2276
2278 OptimizeVar* MakeOptimize(bool maximize, IntVar* v, int64_t step);
2279
2282 OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2283 const std::vector<int64_t>& weights,
2284 int64_t step);
2285
2288 OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2289 const std::vector<int>& weights,
2290 int64_t step);
2291
2293 OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2294 const std::vector<int64_t>& weights,
2295 int64_t step);
2296
2298 OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2299 const std::vector<int>& weights,
2300 int64_t step);
2301
2303 OptimizeVar* MakeWeightedOptimize(bool maximize,
2304 const std::vector<IntVar*>& sub_objectives,
2305 const std::vector<int64_t>& weights,
2306 int64_t step);
2307
2309 OptimizeVar* MakeWeightedOptimize(bool maximize,
2310 const std::vector<IntVar*>& sub_objectives,
2311 const std::vector<int>& weights,
2312 int64_t step);
2313
2316 OptimizeVar* MakeLexicographicOptimize(std::vector<bool> maximize,
2317 std::vector<IntVar*> variables,
2318 std::vector<int64_t> steps);
2319
2321
2337
2338 ObjectiveMonitor* MakeTabuSearch(bool maximize, IntVar* objective,
2339 int64_t step,
2340 const std::vector<IntVar*>& vars,
2341 int64_t keep_tenure, int64_t forbid_tenure,
2342 double tabu_factor);
2343
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);
2348
2352 int64_t step,
2353 const std::vector<IntVar*>& tabu_vars,
2354 int64_t forbid_tenure);
2355
2357 // TODO(user): document behavior
2359 int64_t step,
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);
2364
2367#ifndef SWIG
2369 bool maximize, IntVar* objective, IndexEvaluator2 objective_function,
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);
2375 bool maximize, IntVar* objective, IndexEvaluator3 objective_function,
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);
2381#endif
2382
2383 // Creates a composite objective monitor which alternates between objective
2384 // monitors every time the search reaches a local optimum local optimium
2385 // reached. This will stop if all monitors return false when LocalOptimium is
2386 // called.
2388 std::vector<BaseObjectiveMonitor*> monitors,
2389 int num_max_local_optima_before_metaheuristic_switch);
2390
2394 SearchMonitor* MakeLubyRestart(int scale_factor);
2395
2398 SearchMonitor* MakeConstantRestart(int frequency);
2399
2401 ABSL_MUST_USE_RESULT RegularLimit* MakeTimeLimit(absl::Duration time);
2402#if !defined(SWIG)
2403 ABSL_DEPRECATED("Use the version taking absl::Duration() as argument")
2404#endif // !defined(SWIG)
2405 ABSL_MUST_USE_RESULT RegularLimit* MakeTimeLimit(int64_t time_in_ms) {
2406 return MakeTimeLimit(time_in_ms == kint64max
2407 ? absl::InfiniteDuration()
2408 : absl::Milliseconds(time_in_ms));
2409 }
2410
2413 ABSL_MUST_USE_RESULT RegularLimit* MakeBranchesLimit(int64_t branches);
2414
2417 ABSL_MUST_USE_RESULT RegularLimit* MakeFailuresLimit(int64_t failures);
2418
2421 ABSL_MUST_USE_RESULT RegularLimit* MakeSolutionsLimit(int64_t solutions);
2422
2425 // timer by estimating the number of remaining calls, and 'cumulative' means
2426 // that the limit applies cumulatively, instead of search-by-search.
2427 ABSL_MUST_USE_RESULT RegularLimit* MakeLimit(absl::Duration time,
2428 int64_t branches,
2429 int64_t failures,
2430 int64_t solutions,
2431 bool smart_time_check = false,
2432 bool cumulative = false);
2434 ABSL_MUST_USE_RESULT RegularLimit* MakeLimit(
2435 const RegularLimitParameters& proto);
2436
2437#if !defined(SWIG)
2438 ABSL_DEPRECATED("Use other MakeLimit() versions")
2439#endif // !defined(SWIG)
2440 ABSL_MUST_USE_RESULT RegularLimit* MakeLimit(int64_t time, int64_t branches,
2441 int64_t failures,
2442 int64_t solutions,
2443 bool smart_time_check = false,
2444 bool cumulative = false);
2445
2447 RegularLimitParameters MakeDefaultRegularLimitParameters() const;
2448
2451 /// argument limits.
2452 ABSL_MUST_USE_RESULT SearchLimit* MakeLimit(SearchLimit* limit_1,
2453 SearchLimit* limit_2);
2454
2456
2459 ABSL_MUST_USE_RESULT ImprovementSearchLimit* MakeImprovementLimit(
2460 IntVar* objective_var, bool maximize, double objective_scaling_factor,
2461 double objective_offset, double improvement_rate_coefficient,
2462 int improvement_rate_solutions_distance);
2465 ABSL_MUST_USE_RESULT ImprovementSearchLimit*
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);
2472
2475 ABSL_MUST_USE_RESULT SearchLimit* MakeCustomLimit(
2476 std::function<bool()> limiter);
2477
2478 // TODO(user): DEPRECATE API of MakeSearchLog(.., IntVar* var,..).
2479
2482 SearchMonitor* MakeSearchLog(int branch_period);
2483
2485 SearchMonitor* MakeSearchLog(int branch_period, IntVar* var);
2486
2489 SearchMonitor* MakeSearchLog(int branch_period,
2490 std::function<std::string()> display_callback);
2491
2494 SearchMonitor* MakeSearchLog(int branch_period, IntVar* var,
2495 std::function<std::string()> display_callback);
2496
2499 SearchMonitor* MakeSearchLog(int branch_period, std::vector<IntVar*> vars,
2500 std::function<std::string()> display_callback);
2501
2504 SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* opt_var);
2505
2508 SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* opt_var,
2509 std::function<std::string()> display_callback);
2510
2512 struct SearchLogParameters {
2515 int branch_period = 1;
2518 OptimizeVar* objective = nullptr;
2519 std::vector<IntVar*> variables;
2523 std::vector<double> scaling_factors;
2524 std::vector<double> offsets;
2528 std::function<std::string()> display_callback;
2532 };
2533 SearchMonitor* MakeSearchLog(SearchLogParameters parameters);
2534
2537 SearchMonitor* MakeSearchTrace(const std::string& prefix);
2538
2540 SearchMonitor* MakeEnterSearchCallback(std::function<void()> callback);
2541 SearchMonitor* MakeExitSearchCallback(std::function<void()> callback);
2542 SearchMonitor* MakeAtSolutionCallback(std::function<void()> callback);
2543
2548#if !defined(SWIG)
2551 absl::flat_hash_map<const IntVar*, int>* map);
2552#endif // !defined(SWIG)
2553
2556 const std::vector<SymmetryBreaker*>& visitors);
2560 SymmetryBreaker* v3);
2563
2566 Decision* MakeVariableLessOrEqualValue(IntVar* var, int64_t value);
2567 Decision* MakeVariableGreaterOrEqualValue(IntVar* var, int64_t value);
2568 Decision* MakeSplitVariableDomain(IntVar* var, int64_t val,
2569 bool start_with_lower_half);
2572 Decision* MakeAssignVariablesValues(const std::vector<IntVar*>& vars,
2573 const std::vector<int64_t>& values);
2575 const std::vector<IntVar*>& vars, const std::vector<int64_t>& values);
2576 Decision* MakeAssignVariablesValuesOrFail(const std::vector<IntVar*>& vars,
2577 const std::vector<int64_t>& values);
2579 Decision* MakeDecision(Action apply, Action refute);
2580
2591 DecisionBuilder* db3);
2593 DecisionBuilder* db3, DecisionBuilder* db4);
2594 DecisionBuilder* Compose(const std::vector<DecisionBuilder*>& dbs);
2595
2607 // TODO(user): The search tree can be balanced by using binary
2614 DecisionBuilder* db3);
2616 DecisionBuilder* db3, DecisionBuilder* db4);
2617 DecisionBuilder* Try(const std::vector<DecisionBuilder*>& dbs);
2618
2620 // TODO(user): name each of them differently, and document them (and do that
2622 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2623 IntVarStrategy var_str, IntValueStrategy val_str);
2624 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2625 IndexEvaluator1 var_evaluator,
2626 IntValueStrategy val_str);
2627
2628 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2629 IntVarStrategy var_str,
2630 IndexEvaluator2 value_evaluator);
2631
2634 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2635 IntVarStrategy var_str,
2636 VariableValueComparator var_val1_val2_comparator);
2637
2638 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2639 IndexEvaluator1 var_evaluator,
2640 IndexEvaluator2 value_evaluator);
2641
2642 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2643 IntVarStrategy var_str,
2644 IndexEvaluator2 value_evaluator,
2645 IndexEvaluator1 tie_breaker);
2646
2647 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2648 IndexEvaluator1 var_evaluator,
2649 IndexEvaluator2 value_evaluator,
2650 IndexEvaluator1 tie_breaker);
2651
2652 DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars);
2653 DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars,
2655
2658 IntValueStrategy val_str);
2660 IntValueStrategy val_str);
2662 IntVarStrategy var_str, IntValueStrategy val_str);
2663 DecisionBuilder* MakePhase(IntVar* v0, IntVar* v1, IntVar* v2, IntVar* v3,
2664 IntVarStrategy var_str, IntValueStrategy val_str);
2665
2671 Decision* MakeScheduleOrPostpone(IntervalVar* var, int64_t est,
2672 int64_t* marker);
2673
2679 Decision* MakeScheduleOrExpedite(IntervalVar* var, int64_t est,
2680 int64_t* marker);
2681
2684 Decision* MakeRankFirstInterval(SequenceVar* sequence, int index);
2685
2688 Decision* MakeRankLastInterval(SequenceVar* sequence, int index);
2689
2695 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2697
2705 DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2706 IndexEvaluator2 eval, IndexEvaluator1 tie_breaker,
2707 EvaluatorStrategy str);
2708
2710 DecisionBuilder* MakePhase(const std::vector<IntervalVar*>& intervals,
2711 IntervalStrategy str);
2712
2713 DecisionBuilder* MakePhase(const std::vector<SequenceVar*>& sequences,
2714 SequenceStrategy str);
2715
2719 Assignment* assignment, DecisionBuilder* db,
2720 const std::vector<IntVar*>& vars);
2721
2725
2733 SearchMonitor* monitor2);
2735 SearchMonitor* monitor2,
2736 SearchMonitor* monitor3);
2738 SearchMonitor* monitor2,
2739 SearchMonitor* monitor3,
2740 SearchMonitor* monitor4);
2742 const std::vector<SearchMonitor*>& monitors);
2743
2752 bool maximize, int64_t step);
2754 bool maximize, int64_t step,
2755 SearchMonitor* monitor1);
2757 bool maximize, int64_t step,
2758 SearchMonitor* monitor1,
2759 SearchMonitor* monitor2);
2761 bool maximize, int64_t step,
2762 SearchMonitor* monitor1,
2763 SearchMonitor* monitor2,
2764 SearchMonitor* monitor3);
2766 bool maximize, int64_t step,
2767 SearchMonitor* monitor1,
2768 SearchMonitor* monitor2,
2769 SearchMonitor* monitor3,
2770 SearchMonitor* monitor4);
2772 DecisionBuilder* db, Assignment* solution, bool maximize, int64_t step,
2773 const std::vector<SearchMonitor*>& monitors);
2774
2778
2782
2785 const std::vector<IntVar*>& vars, LocalSearchOperators op,
2786 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2787 nullptr,
2788 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2789 nullptr);
2791 const std::vector<IntVar*>& vars,
2792 const std::vector<IntVar*>& secondary_vars, LocalSearchOperators op,
2793 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =
2794 nullptr,
2795 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =
2796 nullptr);
2797 // TODO(user): Make the callback an IndexEvaluator2 when there are no
2798 // secondary variables.
2799 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2800 IndexEvaluator3 evaluator,
2802 LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2803 const std::vector<IntVar*>& secondary_vars,
2804 IndexEvaluator3 evaluator,
2806
2814 LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2815 int number_of_variables);
2816 LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2817 int number_of_variables,
2818 int32_t seed);
2819
2826
2834 const std::vector<IntVar*>& variables,
2835 const std::vector<int64_t>& target_values);
2836
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);
2878
2883 const std::vector<LocalSearchOperator*>& ops, int32_t seed);
2884
2893 const std::vector<LocalSearchOperator*>& ops, double memory_coefficient,
2894 double exploration_coefficient, bool maximize);
2895
2902 int64_t limit);
2903
2928 // TODO(user): Make a variant which runs a local search after each
2929 // solution found in a DFS.
2930
2933 DecisionBuilder* MakeLocalSearchPhase(const std::vector<IntVar*>& vars,
2934 DecisionBuilder* first_solution,
2938 const std::vector<IntVar*>& vars, DecisionBuilder* first_solution,
2939 DecisionBuilder* first_solution_sub_decision_builder,
2941 DecisionBuilder* MakeLocalSearchPhase(const std::vector<SequenceVar*>& vars,
2942 DecisionBuilder* first_solution,
2944
2950 const Assignment* initial_solution,
2951 LocalSearchFilterManager* filter_manager,
2952 LocalSearchOperator* ls_operator,
2953 const std::vector<SearchMonitor*>& monitors, RegularLimit* limit,
2954 absl::flat_hash_set<IntVar*>* touched = nullptr);
2955
2958
2961 IntVar* objective, LocalSearchOperator* ls_operator,
2962 DecisionBuilder* sub_decision_builder);
2964 IntVar* objective, LocalSearchOperator* ls_operator,
2965 DecisionBuilder* sub_decision_builder, RegularLimit* limit);
2967 IntVar* objective, LocalSearchOperator* ls_operator,
2968 DecisionBuilder* sub_decision_builder, RegularLimit* limit,
2969 LocalSearchFilterManager* filter_manager);
2970
2972 IntVar* objective, SolutionPool* pool, LocalSearchOperator* ls_operator,
2973 DecisionBuilder* sub_decision_builder);
2975 IntVar* objective, SolutionPool* pool, LocalSearchOperator* ls_operator,
2976 DecisionBuilder* sub_decision_builder, RegularLimit* limit);
2978 IntVar* objective, SolutionPool* pool, LocalSearchOperator* ls_operator,
2979 DecisionBuilder* sub_decision_builder, RegularLimit* limit,
2980 LocalSearchFilterManager* filter_manager);
2981
2987 const std::vector<IntVar*>& vars, IndexEvaluator2 values,
2988 Solver::LocalSearchFilterBound filter_enum);
2990 const std::vector<IntVar*>& vars,
2991 const std::vector<IntVar*>& secondary_vars, IndexEvaluator3 values,
2992 Solver::LocalSearchFilterBound filter_enum);
2993
2996 void TopPeriodicCheck();
3000 int TopProgressPercent();
3001
3005 void PushState();
3006 void PopState();
3007
3010 int SearchDepth() const;
3011
3014 int SearchLeftDepth() const;
3015
3018 int SolveDepth() const;
3019
3022
3025
3027 template <class T>
3028 void SaveAndSetValue(T* adr, T val) {
3029 if (*adr != val) {
3030 InternalSaveValue(adr);
3031 *adr = val;
3032 }
3033 }
3034
3036 template <class T>
3037 void SaveAndAdd(T* adr, T val) {
3038 if (val != 0) {
3039 InternalSaveValue(adr);
3040 (*adr) += val;
3041 }
3042 }
3043
3045 int64_t Rand64(int64_t size) {
3046 DCHECK_GT(size, 0);
3047 return absl::Uniform<int64_t>(random_, 0, size);
3048 }
3049
3051 int32_t Rand32(int32_t size) {
3052 DCHECK_GT(size, 0);
3053 return absl::Uniform<int32_t>(random_, 0, size);
3054 }
3055
3057 void ReSeed(int32_t seed) { random_.seed(seed); }
3058
3062 void ExportProfilingOverview(const std::string& filename);
3063
3065 // TODO(user): Merge demon and local search profiles.
3066 std::string LocalSearchProfile() const;
3067
3068#if !defined(SWIG)
3070 ConstraintSolverStatistics GetConstraintSolverStatistics() const;
3072 LocalSearchStatistics GetLocalSearchStatistics() const;
3073#endif // !defined(SWIG)
3074
3078 bool CurrentlyInSolve() const;
3079
3082 int constraints() const { return constraints_list_.size(); }
3083
3084 /// Accepts the given model visitor.
3085 void Accept(ModelVisitor* visitor) const;
3086
3087 Decision* balancing_decision() const { return balancing_decision_.get(); }
3088
3090#if !defined(SWIG)
3091 void set_fail_intercept(std::function<void()> fail_intercept) {
3092 fail_intercept_ = std::move(fail_intercept);
3094#endif // !defined(SWIG)
3095 void clear_fail_intercept() { fail_intercept_ = nullptr; }
3097 DemonProfiler* demon_profiler() const { return demon_profiler_; }
3098 // TODO(user): Get rid of the following methods once fast local search is
3099
3101 void SetUseFastLocalSearch(bool use_fast_local_search) {
3102 use_fast_local_search_ = use_fast_local_search;
3103 }
3105 bool UseFastLocalSearch() const { return use_fast_local_search_; }
3107 bool HasName(const PropagationBaseObject* object) const;
3109 Demon* RegisterDemon(Demon* demon);
3117
3119 Search* ActiveSearch() const;
3121 ModelCache* Cache() const;
3123 bool InstrumentsDemons() const;
3125 bool IsProfilingEnabled() const;
3127 bool IsLocalSearchProfilingEnabled() const;
3129 bool InstrumentsVariables() const;
3131 bool NameAllVariables() const;
3133 std::string model_name() const;
3144 void SetSearchContext(Search* search, absl::string_view search_context);
3145 std::string SearchContext() const;
3146 std::string SearchContext(const Search* search) const;
3147 /// Returns (or creates) an assignment representing the state of local search.
3148 // TODO(user): Investigate if this should be moved to Search.
3150
3151 void ClearLocalSearchState() { local_search_state_.reset(nullptr); }
3152
3157 std::vector<int64_t> tmp_vector_;
3158
3159 friend class BaseIntExpr;
3160 friend class Constraint;
3161 friend class DemonProfiler;
3162 friend class FindOneNeighbor;
3163 friend class IntVar;
3164 friend class PropagationBaseObject;
3165 friend class Queue;
3166 friend class SearchMonitor;
3167 friend class SearchLimit;
3168 friend class RoutingModel;
3169 friend class LocalSearch;
3170 friend class LocalSearchProfiler;
3171
3172#if !defined(SWIG)
3174 template <class>
3175 friend class SimpleRevFIFO;
3176 template <class K, class V>
3177 friend class RevImmutableMultiMap;
3178
3183 bool IsBooleanVar(IntExpr* expr, IntVar** inner_var, bool* is_negated) const;
3184
3189 bool IsProduct(IntExpr* expr, IntExpr** inner_expr, int64_t* coefficient);
3190#endif
3191
3194 IntExpr* CastExpression(const IntVar* var) const;
3195
3197 void FinishCurrentSearch();
3198 void RestartCurrentSearch();
3199
3202 void ShouldFail() { should_fail_ = true; }
3203 void CheckFail() {
3204 if (!should_fail_) return;
3205 should_fail_ = false;
3206 Fail();
3208
3211
3212 private:
3213 void Init();
3214 void PushState(MarkerType t, const StateInfo& info);
3216 void PushSentinel(int magic_code);
3217 void BacktrackToSentinel(int magic_code);
3218 void ProcessConstraints();
3219 bool BacktrackOneLevel(Decision** fail_decision);
3220 void JumpToSentinelWhenNested();
3221 void JumpToSentinel();
3222 void check_alloc_state();
3223 void FreezeQueue();
3224 void EnqueueVar(Demon* d);
3225 void EnqueueDelayedDemon(Demon* d);
3226 void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
3227 void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
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();
3234
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));
3243 }
3244
3245 BaseObject* SafeRevAlloc(BaseObject* ptr);
3246
3247 int* SafeRevAllocArray(int* ptr);
3248 int64_t* SafeRevAllocArray(int64_t* ptr);
3249 uint64_t* SafeRevAllocArray(uint64_t* ptr);
3250 double* SafeRevAllocArray(double* ptr);
3251 BaseObject** SafeRevAllocArray(BaseObject** ptr);
3252 IntVar** SafeRevAllocArray(IntVar** ptr);
3253 IntExpr** SafeRevAllocArray(IntExpr** ptr);
3254 Constraint** SafeRevAllocArray(Constraint** ptr);
3257 void* UnsafeRevAllocAux(void* ptr);
3258 template <class T>
3259 T* UnsafeRevAlloc(T* ptr) {
3260 return reinterpret_cast<T*>(
3261 UnsafeRevAllocAux(reinterpret_cast<void*>(ptr)));
3262 }
3263 void** UnsafeRevAllocArrayAux(void** ptr);
3264 template <class T>
3265 T** UnsafeRevAllocArray(T** ptr) {
3266 return reinterpret_cast<T**>(
3267 UnsafeRevAllocArrayAux(reinterpret_cast<void**>(ptr)));
3268 }
3269
3270 void InitCachedIntConstants();
3271 void InitCachedConstraint();
3272
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];
3284 }
3285
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);
3293
3295 std::string GetName(const PropagationBaseObject* object);
3296 void SetName(const PropagationBaseObject* object, absl::string_view name);
3297
3300 int GetNewIntVarIndex() { return num_int_vars_++; }
3301
3303 bool IsADifference(IntExpr* expr, IntExpr** left, IntExpr** right);
3304
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>
3310 cast_information_;
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_;
3318 SolverState state_;
3319 int64_t branches_;
3320 int64_t fails_;
3321 int64_t decisions_;
3322 int64_t demon_runs_[kNumPriorities];
3323 int64_t neighbors_;
3324 int64_t filtered_neighbors_;
3325 int64_t accepted_neighbors_;
3326 std::string context_;
3327 OptimizationDirection optimization_direction_;
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_;
3336 DemonProfiler* const demon_profiler_;
3338 bool use_fast_local_search_;
3340 LocalSearchProfiler* const local_search_profiler_;
3342 std::unique_ptr<Assignment> local_search_state_;
3343
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];
3347
3349 Constraint* true_constraint_;
3350 Constraint* false_constraint_;
3351
3352 std::unique_ptr<Decision> fail_decision_;
3353 int constraint_index_;
3354 int additional_constraint_index_;
3355 int num_int_vars_;
3356
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_;
3362 bool should_fail_;
3363
3364 std::function<int64_t(int64_t, int64_t, int64_t)> penalty_callback_;
3365};
3366
3367std::ostream& operator<<(std::ostream& out, const Solver* const s);
3368
3372inline int64_t Zero() { return 0; }
3373
3375inline int64_t One() { return 1; }
3376
3380class BaseObject {
3381 public:
3382 BaseObject() {}
3383
3384#ifndef SWIG
3385 // This type is neither copyable nor movable.
3386 BaseObject(const BaseObject&) = delete;
3387 BaseObject& operator=(const BaseObject&) = delete;
3388#endif
3389 virtual ~BaseObject() {}
3390 virtual std::string DebugString() const { return "BaseObject"; }
3391};
3392
3393std::ostream& operator<<(std::ostream& out, const BaseObject* o);
3394
3398class PropagationBaseObject : public BaseObject {
3399 public:
3400 explicit PropagationBaseObject(Solver* const s) : solver_(s) {}
3401
3402#ifndef SWIG
3403 // This type is neither copyable nor movable.
3406#endif
3407 ~PropagationBaseObject() override {};
3408
3409 std::string DebugString() const override {
3410 if (name().empty()) {
3411 return "PropagationBaseObject";
3412 } else {
3413 return absl::StrFormat("PropagationBaseObject: %s", name());
3414 }
3415 }
3416 Solver* solver() const { return solver_; }
3417
3420 void FreezeQueue() { solver_->FreezeQueue(); }
3421
3422
3424 void UnfreezeQueue() { solver_->UnfreezeQueue(); }
3425
3429 void EnqueueDelayedDemon(Demon* const d) { solver_->EnqueueDelayedDemon(d); }
3430 void EnqueueVar(Demon* const d) { solver_->EnqueueVar(d); }
3432 void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
3433
3434#if !defined(SWIG)
3435 // This method sets a callback that will be called if a failure
3436 // happens during the propagation of the queue.
3438 solver_->set_action_on_fail(std::move(a));
3439 }
3440#endif // !defined(SWIG)
3441
3443 void reset_action_on_fail() { solver_->reset_action_on_fail(); }
3444
3447 solver_->set_variable_to_clean_on_fail(v);
3448 }
3449
3451 virtual std::string name() const;
3452 void set_name(absl::string_view name);
3454 bool HasName() const;
3456 virtual std::string BaseName() const;
3457
3458 private:
3459 Solver* const solver_;
3464class Decision : public BaseObject {
3465 public:
3466 Decision() {}
3467
3468#ifndef SWIG
3469 // This type is neither copyable nor movable.
3470 Decision(const Decision&) = delete;
3471 Decision& operator=(const Decision&) = delete;
3472#endif
3473 ~Decision() override {}
3474
3476 virtual void Apply(Solver* s) = 0;
3477
3479 virtual void Refute(Solver* s) = 0;
3481 std::string DebugString() const override { return "Decision"; }
3483 virtual void Accept(DecisionVisitor* visitor) const;
3484};
3488class DecisionVisitor : public BaseObject {
3489 public:
3490 DecisionVisitor() {}
3491
3492#ifndef SWIG
3493 // This type is neither copyable nor movable.
3494 DecisionVisitor(const DecisionVisitor&) = delete;
3495 DecisionVisitor& operator=(const DecisionVisitor&) = delete;
3496#endif
3497 ~DecisionVisitor() override {}
3498 virtual void VisitSetVariableValue(IntVar* var, int64_t value);
3499 virtual void VisitSplitVariableDomain(IntVar* var, int64_t value,
3500 bool start_with_lower_half);
3501 virtual void VisitScheduleOrPostpone(IntervalVar* var, int64_t est);
3502 virtual void VisitScheduleOrExpedite(IntervalVar* var, int64_t est);
3503 virtual void VisitRankFirstInterval(SequenceVar* sequence, int index);
3504 virtual void VisitRankLastInterval(SequenceVar* sequence, int index);
3505 virtual void VisitUnknownDecision();
3506};
3507
3510class DecisionBuilder : public BaseObject {
3511 public:
3512 DecisionBuilder() {}
3513
3514#ifndef SWIG
3515 // This type is neither copyable nor movable.
3516 DecisionBuilder(const DecisionBuilder&) = delete;
3517 DecisionBuilder& operator=(const DecisionBuilder&) = delete;
3518#endif
3519 ~DecisionBuilder() override {}
3520 /// This is the main method of the decision builder class. It must
3521 /// return a decision (an instance of the class Decision). If it
3522 /// returns nullptr, this means that the decision builder has finished
3523 /// its work.
3524 virtual Decision* Next(Solver* s) = 0;
3525 std::string DebugString() const override;
3526#if !defined(SWIG)
3531 virtual void AppendMonitors(Solver* solver,
3532 std::vector<SearchMonitor*>* extras);
3533 virtual void Accept(ModelVisitor* visitor) const;
3534#endif
3535 void set_name(absl::string_view name) { name_ = name; }
3536 std::string GetName() const;
3538 private:
3539 std::string name_;
3540};
3541
3542#if !defined(SWIG)
3544 public:
3547 const std::string& name() const { return name_; }
3548 double seconds() const { return seconds_; }
3549 Decision* Next(Solver* solver) override;
3550 std::string DebugString() const override;
3552 std::vector<SearchMonitor*>* extras) override;
3553 void Accept(ModelVisitor* visitor) const override;
3554
3555 private:
3556 DecisionBuilder* const db_;
3557 const std::string name_;
3558 SimpleCycleTimer timer_;
3559 double seconds_;
3560};
3561#endif
3562
3563
3566/// of the variables. The main concept is that demons are listeners that are
3567/// attached to the variables and listen to their modifications.
3568/// There are two methods:
3569/// - Run() is the actual method called when the demon is processed.
3570/// - priority() returns its priority. Standard priorities are slow, normal
3571/// or fast. "immediate" is reserved for variables and is treated separately.
3572class Demon : public BaseObject {
3573 public:
3576 Demon() : stamp_(uint64_t{0}) {}
3577
3578#ifndef SWIG
3579 // This type is neither copyable nor movable.
3580 Demon(const Demon&) = delete;
3581 Demon& operator=(const Demon&) = delete;
3582#endif
3583 ~Demon() override {}
3584
3586 virtual void Run(Solver* s) = 0;
3587
3592
3593 std::string DebugString() const override;
3594
3597 void inhibit(Solver* s);
3598
3599 /// This method un-inhibits the demon that was previously inhibited.
3600 void desinhibit(Solver* s);
3601
3602 private:
3603 friend class Queue;
3604 void set_stamp(int64_t stamp) { stamp_ = stamp; }
3605 uint64_t stamp() const { return stamp_; }
3606 uint64_t stamp_;
3607};
3608
3610class OR_DLL ModelVisitor : public BaseObject {
3611 public:
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[];
3666 static const char kNoCycle[];
3667 static const char kNonEqual[];
3668 static const char kNotBetween[];
3669 static const char kNotMember[];
3670 static const char kNullIntersect[];
3671 static const char kOpposite[];
3672 static const char kPack[];
3673 static const char kPathCumul[];
3674 static const char kDelayedPathCumul[];
3675 static const char kPerformedExpr[];
3676 static const char kPower[];
3677 static const char kProduct[];
3678 static const char kScalProd[];
3679 static const char kScalProdEqual[];
3680 static const char kScalProdGreaterOrEqual[];
3681 static const char kScalProdLessOrEqual[];
3682 static const char kSemiContinuous[];
3683 static const char kSequenceVariable[];
3684 static const char kSortingConstraint[];
3685 static const char kSquare[];
3686 static const char kStartExpr[];
3687 static const char kSum[];
3688 static const char kSumEqual[];
3689 static const char kSumGreaterOrEqual[];
3690 static const char kSumLessOrEqual[];
3691 static const char kTrace[];
3692 static const char kTransition[];
3693 static const char kTrueConstraint[];
3694 static const char kVarBoundWatcher[];
3695 static const char kVarValueWatcher[];
3698 static const char kCountAssignedItemsExtension[];
3699 static const char kCountUsedBinsExtension[];
3700 static const char kInt64ToBoolExtension[];
3701 static const char kInt64ToInt64Extension[];
3702 static const char kObjectiveExtension[];
3703 static const char kSearchLimitExtension[];
3704 static const char kUsageEqualVariableExtension[];
3706 static const char kUsageLessConstantExtension[];
3707 static const char kVariableGroupExtension[];
3712 static const char kActiveArgument[];
3713 static const char kAssumePathsArgument[];
3714 static const char kBranchesLimitArgument[];
3715 static const char kCapacityArgument[];
3716 static const char kCardsArgument[];
3717 static const char kCoefficientsArgument[];
3718 static const char kCountArgument[];
3719 static const char kCumulativeArgument[];
3720 static const char kCumulsArgument[];
3721 static const char kDemandsArgument[];
3722 static const char kDurationMaxArgument[];
3723 static const char kDurationMinArgument[];
3724 static const char kEarlyCostArgument[];
3725 static const char kEarlyDateArgument[];
3726 static const char kEndMaxArgument[];
3727 static const char kEndMinArgument[];
3728 static const char kEndsArgument[];
3729 static const char kExpressionArgument[];
3730 static const char kFailuresLimitArgument[];
3731 static const char kFinalStatesArgument[];
3732 static const char kFixedChargeArgument[];
3733 static const char kIndex2Argument[];
3734 static const char kIndex3Argument[];
3735 static const char kIndexArgument[];
3736 static const char kInitialState[];
3737 static const char kIntervalArgument[];
3738 static const char kIntervalsArgument[];
3739 static const char kLateCostArgument[];
3740 static const char kLateDateArgument[];
3741 static const char kLeftArgument[];
3742 static const char kMaxArgument[];
3743 static const char kMaximizeArgument[];
3744 static const char kMinArgument[];
3745 static const char kModuloArgument[];
3746 static const char kNextsArgument[];
3747 static const char kOptionalArgument[];
3748 static const char kPartialArgument[];
3749 static const char kPositionXArgument[];
3750 static const char kPositionYArgument[];
3751 static const char kRangeArgument[];
3752 static const char kRelationArgument[];
3753 static const char kRightArgument[];
3754 static const char kSequenceArgument[];
3755 static const char kSequencesArgument[];
3756 static const char kSizeArgument[];
3757 static const char kSizeXArgument[];
3758 static const char kSizeYArgument[];
3759 static const char kSmartTimeCheckArgument[];
3760 static const char kSolutionLimitArgument[];
3761 static const char kStartMaxArgument[];
3762 static const char kStartMinArgument[];
3763 static const char kStartsArgument[];
3764 static const char kStepArgument[];
3765 static const char kTargetArgument[];
3766 static const char kTimeLimitArgument[];
3767 static const char kTransitsArgument[];
3768 static const char kTuplesArgument[];
3769 static const char kValueArgument[];
3770 static const char kValuesArgument[];
3771 static const char kVariableArgument[];
3772 static const char kVarsArgument[];
3773 static const char kEvaluatorArgument[];
3776 static const char kMirrorOperation[];
3777 static const char kRelaxedMaxOperation[];
3778 static const char kRelaxedMinOperation[];
3779 static const char kSumOperation[];
3780 static const char kDifferenceOperation[];
3781 static const char kProductOperation[];
3782 static const char kStartSyncOnStartOperation[];
3783 static const char kStartSyncOnEndOperation[];
3784 static const char kTraceOperation[];
3786 ~ModelVisitor() override;
3791 virtual void BeginVisitModel(const std::string& type_name);
3792 virtual void EndVisitModel(const std::string& type_name);
3793 virtual void BeginVisitConstraint(const std::string& type_name,
3794 const Constraint* constraint);
3795 virtual void EndVisitConstraint(const std::string& type_name,
3796 const Constraint* constraint);
3797 virtual void BeginVisitExtension(const std::string& type);
3798 virtual void EndVisitExtension(const std::string& type);
3799 virtual void BeginVisitIntegerExpression(const std::string& type_name,
3800 const IntExpr* expr);
3801 virtual void EndVisitIntegerExpression(const std::string& type_name,
3802 const IntExpr* expr);
3803 virtual void VisitIntegerVariable(const IntVar* variable, IntExpr* delegate);
3804 virtual void VisitIntegerVariable(const IntVar* variable,
3805 const std::string& operation, int64_t value,
3806 IntVar* delegate);
3807 virtual void VisitIntervalVariable(const IntervalVar* variable,
3808 const std::string& operation,
3809 int64_t value, IntervalVar* delegate);
3810 virtual void VisitSequenceVariable(const SequenceVar* variable);
3813 virtual void VisitIntegerArgument(const std::string& arg_name, int64_t value);
3814 virtual void VisitIntegerArrayArgument(const std::string& arg_name,
3815 const std::vector<int64_t>& values);
3816 virtual void VisitIntegerMatrixArgument(const std::string& arg_name,
3817 const IntTupleSet& tuples);
3820 virtual void VisitIntegerExpressionArgument(const std::string& arg_name,
3821 IntExpr* argument);
3824 const std::string& arg_name, const std::vector<IntVar*>& arguments);
3827 virtual void VisitIntervalArgument(const std::string& arg_name,
3828 IntervalVar* argument);
3830 virtual void VisitIntervalArrayArgument(
3831 const std::string& arg_name, const std::vector<IntervalVar*>& arguments);
3833 virtual void VisitSequenceArgument(const std::string& arg_name,
3834 SequenceVar* argument);
3837 const std::string& arg_name, const std::vector<SequenceVar*>& arguments);
3838#if !defined(SWIG)
3841 const std::string& arg_name, const Solver::Int64ToIntVar& arguments);
3842
3845 void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64_t index_min,
3846 int64_t index_max);
3848 int64_t index_min, int64_t index_max);
3851 const std::string& arg_name, int64_t index_max);
3852#endif // #if !defined(SWIG)
3853};
3854
3861class Constraint : public PropagationBaseObject {
3862 public:
3863 explicit Constraint(Solver* const solver) : PropagationBaseObject(solver) {}
3864
3865#ifndef SWIG
3866 // This type is neither copyable nor movable.
3867 Constraint(const Constraint&) = delete;
3868 Constraint& operator=(const Constraint&) = delete;
3869#endif
3870 ~Constraint() override {}
3871
3874 virtual void Post() = 0;
3875
3878 virtual void InitialPropagate() = 0;
3879 std::string DebugString() const override;
3880
3883 void PostAndPropagate();
3884
3886 virtual void Accept(ModelVisitor* visitor) const;
3887
3889 bool IsCastConstraint() const;
3890
3894 virtual IntVar* Var();
3895};
3896
3900class CastConstraint : public Constraint {
3901 public:
3902 CastConstraint(Solver* const solver, IntVar* const target_var)
3904 CHECK(target_var != nullptr);
3905 }
3906 ~CastConstraint() override {}
3907
3908 IntVar* target_var() const { return target_var_; }
3909
3910 protected:
3911 IntVar* const target_var_;
3912};
3913
3915class SearchMonitor : public BaseObject {
3916 public:
3917 static constexpr int kNoProgress = -1;
3918
3919 explicit SearchMonitor(Solver* const s) : solver_(s) {}
3920
3921#ifndef SWIG
3922 // This type is neither copyable nor movable.
3925#endif
3926 ~SearchMonitor() override {}
3928 virtual void EnterSearch();
3929
3931 virtual void RestartSearch();
3932
3934 virtual void ExitSearch();
3935
3937 virtual void BeginNextDecision(DecisionBuilder* b);
3938
3940 virtual void EndNextDecision(DecisionBuilder* b, Decision* d);
3941
3943 virtual void ApplyDecision(Decision* d);
3944
3946 virtual void RefuteDecision(Decision* d);
3947
3950 virtual void AfterDecision(Decision* d, bool apply);
3951
3952
3953 virtual void BeginFail();
3954
3956 virtual void EndFail();
3957
3958 /// Before the initial propagation.
3959 virtual void BeginInitialPropagation();
3960
3963
3967 virtual bool AcceptSolution();
3968
3969
3971 /// is false, then search will stop there.
3972 virtual bool AtSolution();
3975 virtual void NoMoreSolutions();
3976
3979 virtual bool LocalOptimum();
3982 virtual bool AcceptDelta(Assignment* delta, Assignment* deltadelta);
3983
3985 virtual void AcceptNeighbor();
3986
3988 virtual void AcceptUncheckedNeighbor();
3989
3992 virtual bool IsUncheckedSolutionLimitReached() { return false; }
3993
3995 virtual void PeriodicCheck();
3996
3999 virtual int ProgressPercent() { return kNoProgress; }
4000
4002 virtual void Accept(ModelVisitor* visitor) const;
4003
4007 virtual void Install();
4008
4009 Solver* solver() const { return solver_; }
4010
4011 protected:
4013
4014 private:
4015 Solver* const solver_;
4016};
4017
4023template <class T>
4024class Rev {
4025 public:
4026 explicit Rev(const T& val) : stamp_(0), value_(val) {}
4027
4028 const T& Value() const { return value_; }
4029
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();
4035 }
4036 value_ = val;
4037 }
4038 }
4039
4040 private:
4041 uint64_t stamp_;
4042 T value_;
4043};
4044
4046template <class T>
4047class NumericalRev : public Rev<T> {
4048 public:
4049 explicit NumericalRev(const T& val) : Rev<T>(val) {}
4050
4051 void Add(Solver* const s, const T& to_add) {
4052 this->SetValue(s, this->Value() + to_add);
4053 }
4054
4055 void Incr(Solver* const s) { Add(s, 1); }
4057 void Decr(Solver* const s) { Add(s, -1); }
4058};
4059
4065template <class T>
4067 public:
4068 RevArray(int size, const T& val)
4069 : stamps_(new uint64_t[size]), values_(new T[size]), size_(size) {
4070 for (int i = 0; i < size; ++i) {
4071 stamps_[i] = 0;
4072 values_[i] = val;
4073 }
4074 }
4075
4076 ~RevArray() {}
4077
4078 int64_t size() const { return size_; }
4079
4080 const T& Value(int index) const { return values_[index]; }
4082#if !defined(SWIG)
4083 const T& operator[](int index) const { return values_[index]; }
4084#endif
4086 void SetValue(Solver* const s, int index, const T& val) {
4087 DCHECK_LT(index, size_);
4088 if (val != values_[index]) {
4089 if (stamps_[index] < s->stamp()) {
4090 s->SaveValue(&values_[index]);
4091 stamps_[index] = s->stamp();
4092 }
4093 values_[index] = val;
4094 }
4095 }
4096
4097 private:
4098 std::unique_ptr<uint64_t[]> stamps_;
4099 std::unique_ptr<T[]> values_;
4100 const int size_;
4101};
4102
4104template <class T>
4105class NumericalRevArray : public RevArray<T> {
4106 public:
4107 NumericalRevArray(int size, const T& val) : RevArray<T>(size, val) {}
4109 void Add(Solver* const s, int index, const T& to_add) {
4110 this->SetValue(s, index, this->Value(index) + to_add);
4111 }
4113 void Incr(Solver* const s, int index) { Add(s, index, 1); }
4115 void Decr(Solver* const s, int index) { Add(s, index, -1); }
4116};
4117
4123/// - listening to events modifying its bounds
4124/// - casting it into a variable (instance of IntVar)
4126 public:
4127 explicit IntExpr(Solver* const s) : PropagationBaseObject(s) {}
4128
4129#ifndef SWIG
4130 // This type is neither copyable nor movable.
4131 IntExpr(const IntExpr&) = delete;
4132 IntExpr& operator=(const IntExpr&) = delete;
4133#endif
4134 ~IntExpr() override {}
4136 virtual int64_t Min() const = 0;
4137 virtual void SetMin(int64_t m) = 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) {
4144 *l = Min();
4145 *u = Max();
4146 }
4148 virtual void SetRange(int64_t l, int64_t u) {
4149 SetMin(l);
4150 SetMax(u);
4151 }
4152
4153
4154 virtual void SetValue(int64_t v) { SetRange(v, v); }
4155
4157 virtual bool Bound() const { return (Min() == Max()); }
4158
4159
4160 virtual bool IsVar() const { return false; }
4161
4162 /// Creates a variable from the expression.
4163 virtual IntVar* Var() = 0;
4166 /// resulting var. If the expression is already a variable, then it
4167 /// will set the name of the expression, possibly overwriting it.
4168 /// This is just a shortcut to Var() followed by set_name().
4169 IntVar* VarWithName(const std::string& name);
4172 virtual void WhenRange(Demon* d) = 0;
4174 void WhenRange(Solver::Closure closure) {
4175 WhenRange(solver()->MakeClosureDemon(std::move(closure)));
4176 }
4177
4178#if !defined(SWIG)
4180 void WhenRange(Solver::Action action) {
4181 WhenRange(solver()->MakeActionDemon(std::move(action)));
4183#endif // SWIG
4186 virtual void Accept(ModelVisitor* visitor) const;
4187};
4199
4200/// IntVar* current_var;
4201/// std::unique_ptr<IntVarIterator> it(current_var->MakeHoleIterator(false));
4202/// for (const int64_t hole : InitAndGetValues(it)) {
4203/// /// use the hole
4204/// }
4206class IntVarIterator : public BaseObject {
4207 public:
4208 ~IntVarIterator() override {}
4209
4211 virtual void Init() = 0;
4212
4214 virtual bool Ok() const = 0;
4215
4217 virtual int64_t Value() const = 0;
4218
4220 virtual void Next() = 0;
4221
4223 std::string DebugString() const override { return "IntVar::Iterator"; }
4224};
4225
4226#ifndef SWIG
4231/// same iterator instance isn't being iterated on in multiple places
4232/// simultaneously.
4233class InitAndGetValues {
4234 public:
4235 explicit InitAndGetValues(IntVarIterator* it)
4236 : it_(it), begin_was_called_(false) {
4237 it_->Init();
4238 }
4239 struct Iterator;
4240
4241 Iterator begin() {
4242 if (DEBUG_MODE) {
4243 DCHECK(!begin_was_called_);
4244 begin_was_called_ = true;
4245 }
4246 return Iterator::Begin(it_);
4247 }
4248 Iterator end() { return Iterator::End(it_); }
4249
4250 struct Iterator {
4252 static Iterator Begin(IntVarIterator* it) {
4253 return Iterator(it, /*is_end=*/false);
4254 }
4255 static Iterator End(IntVarIterator* it) {
4256 return Iterator(it, /*is_end=*/true);
4257 }
4258
4259 int64_t operator*() const {
4260 DCHECK(it->Ok());
4261 return it->Value();
4262 }
4263 Iterator& operator++() {
4264 DCHECK(it->Ok());
4265 it->Next();
4266 return *this;
4267 }
4268 bool operator!=(const Iterator& other) const {
4269 DCHECK(other.it == it);
4270 DCHECK(other.is_end);
4271 return it->Ok();
4272 }
4273
4274 private:
4275 Iterator(IntVarIterator* it, bool is_end) : it(it), is_end(is_end) {}
4276
4278 const bool is_end;
4279 };
4281 private:
4282 IntVarIterator* const it_;
4283 bool begin_was_called_;
4284};
4285#endif // SWIG
4286
4290class IntVar : public IntExpr {
4291 public:
4292 explicit IntVar(Solver* s);
4293 IntVar(Solver* s, const std::string& name);
4294
4295#ifndef SWIG
4296 // This type is neither copyable nor movable.
4297 IntVar(const IntVar&) = delete;
4298 IntVar& operator=(const IntVar&) = delete;
4299#endif
4300
4301 ~IntVar() override {};
4302
4303 bool IsVar() const override { return true; }
4304 IntVar* Var() override { return this; }
4305
4306
4308 virtual int64_t Value() const = 0;
4309
4310 /// This method removes the value 'v' from the domain of the variable.
4311 virtual void RemoveValue(int64_t v) = 0;
4312
4313
4313 /// This method removes the interval 'l' .. 'u' from the domain of
4314 /// the variable. It assumes that 'l' <= 'u'.
4315 virtual void RemoveInterval(int64_t l, int64_t u) = 0;
4316
4317 /// This method remove the values from the domain of the variable.
4318 virtual void RemoveValues(const std::vector<int64_t>& values);
4319
4321 virtual void SetValues(const std::vector<int64_t>& values);
4322
4325 virtual void WhenBound(Demon* d) = 0;
4326
4326 /// This method attaches a closure that will be awakened when the
4327 /// variable is bound.
4328 void WhenBound(Solver::Closure closure) {
4329 WhenBound(solver()->MakeClosureDemon(std::move(closure)));
4330 }
4331
4332#if !defined(SWIG)
4335 void WhenBound(Solver::Action action) {
4336 WhenBound(solver()->MakeActionDemon(std::move(action)));
4337 }
4338#endif // SWIG
4339
4342 virtual void WhenDomain(Demon* d) = 0;
4343
4345 void WhenDomain(Solver::Closure closure) {
4346 WhenDomain(solver()->MakeClosureDemon(std::move(closure)));
4347 }
4348#if !defined(SWIG)
4351 void WhenDomain(Solver::Action action) {
4352 WhenDomain(solver()->MakeActionDemon(std::move(action)));
4353 }
4354#endif // SWIG
4357 virtual uint64_t Size() const = 0;
4358
4361 virtual bool Contains(int64_t v) const = 0;
4366 virtual IntVarIterator* MakeHoleIterator(bool reversible) const = 0;
4367
4371 virtual IntVarIterator* MakeDomainIterator(bool reversible) const = 0;
4372
4374 virtual int64_t OldMin() const = 0;
4375
4377 virtual int64_t OldMax() const = 0;
4378
4379 virtual int VarType() const;
4380
4382 void Accept(ModelVisitor* visitor) const override;
4385 virtual IntVar* IsEqual(int64_t constant) = 0;
4386 virtual IntVar* IsDifferent(int64_t constant) = 0;
4387 virtual IntVar* IsGreaterOrEqual(int64_t constant) = 0;
4388 virtual IntVar* IsLessOrEqual(int64_t constant) = 0;
4389
4391 int index() const { return index_; }
4392
4393 private:
4394 const int index_;
4395};
4396
4401 public:
4402 SolutionCollector(Solver* solver, const Assignment* assignment);
4404
4405#ifndef SWIG
4406 // This type is neither copyable nor movable.
4407 SolutionCollector(const SolutionCollector&) = delete;
4409#endif
4410
4411 ~SolutionCollector() override;
4412 void Install() override;
4413 std::string DebugString() const override { return "SolutionCollector"; }
4414
4416 void Add(IntVar* var);
4417 void Add(const std::vector<IntVar*>& vars);
4418 void Add(IntervalVar* var);
4419 void Add(const std::vector<IntervalVar*>& vars);
4420 void Add(SequenceVar* var);
4421 void Add(const std::vector<SequenceVar*>& vars);
4422 void AddObjective(IntVar* objective);
4423 void AddObjectives(const std::vector<IntVar*>& objectives);
4426 void EnterSearch() override;
4427
4429 int solution_count() const;
4430
4432 bool has_solution() const;
4433
4435 Assignment* solution(int n) const;
4436
4439
4441 int64_t wall_time(int n) const;
4442
4444 int64_t branches(int n) const;
4448 int64_t failures(int n) const;
4451 int64_t objective_value(int n) const;
4452
4454 int64_t ObjectiveValueFromIndex(int n, int index) const;
4455
4457 int64_t Value(int n, IntVar* var) const;
4460 int64_t StartValue(int n, IntervalVar* var) const;
4461
4463 int64_t EndValue(int n, IntervalVar* var) const;
4464
4466 int64_t DurationValue(int n, IntervalVar* var) const;
4467
4469 int64_t PerformedValue(int n, IntervalVar* var) const;
4470
4474 const std::vector<int>& ForwardSequence(int n, SequenceVar* var) const;
4478 const std::vector<int>& BackwardSequence(int n, SequenceVar* var) const;
4481 const std::vector<int>& Unperformed(int n, SequenceVar* var) const;
4482
4483 protected:
4484 struct SolutionData {
4486 int64_t time;
4487 int64_t branches;
4488 int64_t failures;
4489 int64_t ObjectiveValue() const;
4490 int64_t ObjectiveValueFromIndex(int index) const;
4491 bool operator<(const SolutionData& other) const;
4492 };
4493
4495 void PushSolution();
4496 void Push(const SolutionData& data) { solution_data_.push_back(data); }
4498 void PopSolution();
4499 SolutionData BuildSolutionDataForCurrentState();
4500 void FreeSolution(Assignment* solution);
4501 void check_index(int n) const;
4502
4503 std::unique_ptr<Assignment> prototype_;
4504 std::vector<SolutionData> solution_data_;
4505 std::vector<Assignment*> recycle_solutions_;
4506#if !defined(SWIG)
4507 std::vector<std::unique_ptr<Assignment>> solution_pool_;
4508#endif // SWIG
4509};
4510
4511// Base objective monitor class. All metaheuristics and metaheuristic combiners
4512// derive from this.
4513class BaseObjectiveMonitor : public SearchMonitor {
4514 public:
4515 explicit BaseObjectiveMonitor(Solver* solver) : SearchMonitor(solver) {}
4516 ~BaseObjectiveMonitor() override {}
4517#ifndef SWIG
4520#endif // SWIG
4521 virtual IntVar* ObjectiveVar(int index) const = 0;
4522 virtual IntVar* MinimizationVar(int index) const = 0;
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_; }
4528 void set_active(bool is_active) { is_active_ = is_active; }
4529
4530 private:
4531 bool is_active_ = true;
4532};
4533
4534// Base atomic objective monitor class. All non-composite metaheuristics derive
4535// from this.
4537 public:
4538 ObjectiveMonitor(Solver* solver, const std::vector<bool>& maximize,
4539 std::vector<IntVar*> vars, std::vector<int64_t> steps);
4540 ~ObjectiveMonitor() override {}
4541#ifndef SWIG
4544#endif // SWIG
4545 IntVar* ObjectiveVar(int index) const override {
4546 return objective_vars_[index];
4547 }
4548 IntVar* MinimizationVar(int index) const override {
4549 return minimization_vars_[index];
4550 }
4551 int64_t Step(int index) const override { return steps_[index]; }
4552 bool Maximize(int index) const override {
4553 return ObjectiveVar(index) != MinimizationVar(index);
4555 int64_t BestValue(int index) const override {
4556 return Maximize(index) ? CapOpp(BestInternalValue(index))
4557 : BestInternalValue(index);
4558 }
4559 int Size() const override { return objective_vars_.size(); }
4560 void EnterSearch() override;
4561 bool AtSolution() override;
4562 bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;
4563 void Accept(ModelVisitor* visitor) const override;
4564
4565 protected:
4566 const std::vector<IntVar*>& objective_vars() const { return objective_vars_; }
4567 const std::vector<IntVar*>& minimization_vars() const {
4568 return minimization_vars_;
4569 }
4570 int64_t BestInternalValue(int index) const { return best_values_[index]; }
4571 int64_t CurrentInternalValue(int index) const {
4572 return current_values_[index];
4574 void SetCurrentInternalValue(int index, int64_t value) {
4575 current_values_[index] = value;
4577 template <typename T>
4578 void MakeMinimizationVarsLessOrEqualWithSteps(const T& upper_bounds) {
4579 if (Size() == 1) {
4580 MinimizationVar(0)->SetMax(CapSub(upper_bounds(0), Step(0)));
4581 } else {
4582 Solver* const solver = this->solver();
4583 for (int i = 0; i < Size(); ++i) {
4584 upper_bounds_[i] = solver->MakeIntConst(upper_bounds(i));
4586 solver->AddConstraint(solver->MakeLexicalLessOrEqualWithOffsets(
4587 minimization_vars_, upper_bounds_, steps_));
4588 }
4589 }
4590 template <typename T>
4592 const T& upper_bounds) {
4593 Solver* const solver = this->solver();
4594 IntVar* status = solver->MakeBoolVar();
4595 if (Size() == 1) {
4596 solver->AddConstraint(solver->MakeIsLessOrEqualCstCt(
4597 MinimizationVar(0), CapSub(upper_bounds(0), Step(0)), status));
4598 } else {
4599 for (int i = 0; i < Size(); ++i) {
4600 upper_bounds_[i] = solver->MakeIntConst(upper_bounds(i));
4603 minimization_vars_, upper_bounds_, steps_, status));
4604 }
4605 return status;
4608
4611 private:
4612 friend class Solver;
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_;
4619};
4620
4625 public:
4626 OptimizeVar(Solver* solver, bool maximize, IntVar* var, int64_t step);
4627 // Specifies a lexicographic objective. Each objective is specified in
4628 // decreasing order with the corresponding direction and step.
4629 OptimizeVar(Solver* solver, const std::vector<bool>& maximize,
4630 std::vector<IntVar*> vars, std::vector<int64_t> steps);
4631#ifndef SWIG
4632 ~OptimizeVar() override {}
4633#endif // SIWG
4634
4635
4636 int64_t best() const { return BestValue(0); }
4637
4639 IntVar* var() const { return Size() == 0 ? nullptr : ObjectiveVar(0); }
4640
4642 void BeginNextDecision(DecisionBuilder* db) override;
4643 void RefuteDecision(Decision* d) override;
4644 bool AtSolution() override;
4645 bool AcceptSolution() override;
4646 virtual std::string Name() const;
4647 std::string DebugString() const override;
4648
4650};
4651
4653class SearchLimit : public SearchMonitor {
4654 public:
4655 explicit SearchLimit(Solver* const s) : SearchMonitor(s), crossed_(false) {}
4656
4657#ifndef SWIG
4658 // This type is neither copyable nor movable.
4659 SearchLimit(const SearchLimit&) = delete;
4660 SearchLimit& operator=(const SearchLimit&) = delete;
4661#endif
4662 ~SearchLimit() override;
4663
4665 bool crossed() const { return crossed_; }
4666
4671 bool Check() { return CheckWithOffset(absl::ZeroDuration()); }
4674 virtual bool CheckWithOffset(absl::Duration offset) = 0;
4675
4677 virtual void Init() = 0;
4678
4681 virtual void Copy(const SearchLimit* limit) = 0;
4684 virtual SearchLimit* MakeClone() const = 0;
4685
4687 void EnterSearch() override;
4688 void BeginNextDecision(DecisionBuilder* b) override;
4689 void PeriodicCheck() override;
4690 void RefuteDecision(Decision* d) override;
4691 std::string DebugString() const override {
4692 return absl::StrFormat("SearchLimit(crossed = %i)", crossed_);
4693 }
4694 void Install() override;
4695
4696 private:
4697 void TopPeriodicCheck();
4698
4699 bool crossed_;
4700};
4701
4704class RegularLimit : public SearchLimit {
4705 public:
4706 RegularLimit(Solver* s, absl::Duration time, int64_t branches,
4707 int64_t failures, int64_t solutions, bool smart_time_check,
4708 bool cumulative);
4709 ~RegularLimit() override;
4710 void Copy(const SearchLimit* limit) override;
4711 SearchLimit* MakeClone() const override;
4713 bool CheckWithOffset(absl::Duration offset) override;
4714 void Init() override;
4715 void ExitSearch() override;
4716 void UpdateLimits(absl::Duration time, int64_t branches, int64_t failures,
4717 int64_t solutions);
4718 absl::Duration duration_limit() const { return duration_limit_; }
4719 int64_t wall_time() const {
4720 return duration_limit_ == absl::InfiniteDuration()
4721 ? kint64max
4722 : absl::ToInt64Milliseconds(duration_limit());
4724 int64_t branches() const { return branches_; }
4725 int64_t failures() const { return failures_; }
4726 int64_t solutions() const { return solutions_; }
4727 bool IsUncheckedSolutionLimitReached() override;
4728 int ProgressPercent() override;
4729 std::string DebugString() const override;
4730 void Install() override;
4731
4732 absl::Time AbsoluteSolverDeadline() const {
4733 return solver_time_at_limit_start_ + duration_limit_;
4734 }
4736 void Accept(ModelVisitor* visitor) const override;
4737
4738 private:
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
4743 : -1;
4744 }
4745
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_;
4752 int64_t branches_;
4753 int64_t branches_offset_;
4754 int64_t failures_;
4755 int64_t failures_offset_;
4756 int64_t solutions_;
4757 int64_t solutions_offset_;
4759
4762 /// depending on context:
4763 /// - within a search, it's an offset to be subtracted from the current value
4764 /// - outside of search, it's the amount consumed in previous searches
4765 bool cumulative_;
4766};
4767
4768// Limit based on the improvement rate of 'objective_var' or a lexicographic
4769// objective composed of 'objective_vars'.
4770// This limit proceeds in two stages:
4771// 1) During the phase of the search in which the objective is strictly
4772// improving, a threshold value is computed as the minimum improvement rate of
4773// the objective, based on the 'improvement_rate_coefficient' and
4774// 'improvement_rate_solutions_distance' parameters.
4775// 2) Then, if the search continues beyond this phase of strict improvement, the
4776// limit stops the search when the improvement rate of the objective gets below
4777// this threshold value.
4778class ImprovementSearchLimit : public SearchLimit {
4779 public:
4780 ImprovementSearchLimit(Solver* solver, IntVar* objective_var, bool maximize,
4781 double objective_scaling_factor,
4782 double objective_offset,
4783 double improvement_rate_coefficient,
4784 int improvement_rate_solutions_distance);
4785 ImprovementSearchLimit(Solver* solver, std::vector<IntVar*> objective_vars,
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);
4791 ~ImprovementSearchLimit() override;
4792 void Copy(const SearchLimit* limit) override;
4793 SearchLimit* MakeClone() const override;
4794 bool CheckWithOffset(absl::Duration offset) override;
4795 bool AtSolution() override;
4796 void Init() override;
4797 void Install() override;
4798
4799 private:
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_;
4806
4807 std::vector<double> best_objectives_;
4808 // clang-format off
4809 std::vector<std::deque<std::pair<double, int64_t> > > improvements_;
4810 // clang-format on
4811 std::vector<double> thresholds_;
4812 bool objective_updated_;
4813 bool gradient_stage_;
4814};
4815
4825
4827 public:
4829 static const int64_t kMinValidValue;
4831 static const int64_t kMaxValidValue;
4832 IntervalVar(Solver* const solver, const std::string& name)
4833 : PropagationBaseObject(solver) {
4834 set_name(name);
4835 }
4837#ifndef SWIG
4838 // This type is neither copyable nor movable.
4839 IntervalVar(const IntervalVar&) = delete;
4840 IntervalVar& operator=(const IntervalVar&) = delete;
4841#endif
4842 ~IntervalVar() override {}
4843
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;
4854 void WhenStartRange(Solver::Closure closure) {
4855 WhenStartRange(solver()->MakeClosureDemon(std::move(closure)));
4856 }
4857#if !defined(SWIG)
4858 void WhenStartRange(Solver::Action action) {
4859 WhenStartRange(solver()->MakeActionDemon(std::move(action)));
4860 }
4861#endif // SWIG
4862 virtual void WhenStartBound(Demon* d) = 0;
4863 void WhenStartBound(Solver::Closure closure) {
4864 WhenStartBound(solver()->MakeClosureDemon(std::move(closure)));
4865 }
4866#if !defined(SWIG)
4867 void WhenStartBound(Solver::Action action) {
4868 WhenStartBound(solver()->MakeActionDemon(std::move(action)));
4869 }
4870#endif // SWIG
4871
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)));
4883 }
4884#if !defined(SWIG)
4886 WhenDurationRange(solver()->MakeActionDemon(std::move(action)));
4887 }
4888#endif // SWIG
4889 virtual void WhenDurationBound(Demon* d) = 0;
4891 WhenDurationBound(solver()->MakeClosureDemon(std::move(closure)));
4892 }
4893#if !defined(SWIG)
4894 void WhenDurationBound(Solver::Action action) {
4895 WhenDurationBound(solver()->MakeActionDemon(std::move(action)));
4896 }
4897#endif // SWIG
4900 virtual int64_t EndMin() const = 0;
4901 virtual int64_t EndMax() const = 0;
4902 virtual void SetEndMin(int64_t m) = 0;
4903 virtual void SetEndMax(int64_t m) = 0;
4904 virtual void SetEndRange(int64_t mi, int64_t ma) = 0;
4905 virtual int64_t OldEndMin() const = 0;
4906 virtual int64_t OldEndMax() const = 0;
4907 virtual void WhenEndRange(Demon* d) = 0;
4909 WhenEndRange(solver()->MakeClosureDemon(std::move(closure)));
4911#if !defined(SWIG)
4913 WhenEndRange(solver()->MakeActionDemon(std::move(action)));
4914 }
4915#endif // SWIG
4916 virtual void WhenEndBound(Demon* d) = 0;
4918 WhenEndBound(solver()->MakeClosureDemon(std::move(closure)));
4919 }
4920#if !defined(SWIG)
4922 WhenEndBound(solver()->MakeActionDemon(std::move(action)));
4923 }
4924#endif // SWIG
4925
4926 /// These methods query, set, and watch the performed status of the
4927 /// interval var.
4928 virtual bool MustBePerformed() const = 0;
4929 virtual bool MayBePerformed() const = 0;
4930 bool CannotBePerformed() const { return !MayBePerformed(); }
4931 bool IsPerformedBound() const {
4934 virtual void SetPerformed(bool val) = 0;
4935 virtual bool WasPerformedBound() const = 0;
4936 virtual void WhenPerformedBound(Demon* d) = 0;
4938 WhenPerformedBound(solver()->MakeClosureDemon(std::move(closure)));
4940#if !defined(SWIG)
4941 void WhenPerformedBound(Solver::Action action) {
4942 WhenPerformedBound(solver()->MakeActionDemon(std::move(action)));
4943 }
4944#endif // SWIG
4945
4947 void WhenAnything(Demon* d);
4950 WhenAnything(solver()->MakeClosureDemon(std::move(closure)));
4951 }
4952#if !defined(SWIG)
4953 /// Attaches an action awakened when anything about this interval changes.
4954 void WhenAnything(Solver::Action action) {
4955 WhenAnything(solver()->MakeActionDemon(std::move(action)));
4956 }
4957#endif // SWIG
4958
4962 virtual IntExpr* StartExpr() = 0;
4963 virtual IntExpr* DurationExpr() = 0;
4964 virtual IntExpr* EndExpr() = 0;
4965 virtual IntExpr* PerformedExpr() = 0;
4967 /// and duration of the interval var. If the interval var is
4968 /// unperformed, they will return the unperformed_value.
4969 virtual IntExpr* SafeStartExpr(int64_t unperformed_value) = 0;
4970 virtual IntExpr* SafeDurationExpr(int64_t unperformed_value) = 0;
4971 virtual IntExpr* SafeEndExpr(int64_t unperformed_value) = 0;
4972
4974 virtual void Accept(ModelVisitor* visitor) const = 0;
4979
4980/// returns the list of interval variables that can be ranked first or
4981/// last; and RankFirst/RankNotFirst/RankLast/RankNotLast, which can be
4982/// used to create the search decision.
4983class SequenceVar : public PropagationBaseObject {
4984 public:
4985 SequenceVar(Solver* s, const std::vector<IntervalVar*>& intervals,
4986 const std::vector<IntVar*>& nexts, const std::string& name);
4988 ~SequenceVar() override;
4990 std::string DebugString() const override;
4991
4992#if !defined(SWIG)
4993
4995 void DurationRange(int64_t* dmin, int64_t* dmax) const;
4999 void HorizonRange(int64_t* hmin, int64_t* hmax) const;
5003 void ActiveHorizonRange(int64_t* hmin, int64_t* hmax) const;
5004
5006 void ComputeStatistics(int* ranked, int* not_ranked, int* unperformed) const;
5007#endif // !defined(SWIG)
5011 void RankFirst(int index);
5012
5013 /// Indicates that the index_th interval var will not be ranked first
5014 /// of all currently unranked interval vars.
5015 void RankNotFirst(int index);
5016
5019 void RankLast(int index);
5020
5023 void RankNotLast(int index);
5027 void ComputePossibleFirstsAndLasts(std::vector<int>* possible_firsts,
5028 std::vector<int>* possible_lasts);
5035 void RankSequence(const std::vector<int>& rank_first,
5036 const std::vector<int>& rank_last,
5037 const std::vector<int>& unperformed);
5038
5042 /// contain none.
5043 /// 'unperformed' will contains all such interval variables.
5044 /// rank_first and rank_last represents different directions.
5045 /// rank_first[0] corresponds to the first interval of the sequence.
5046 /// rank_last[0] corresponds to the last interval of the sequence.
5047 void FillSequence(std::vector<int>* rank_first, std::vector<int>* rank_last,
5048 std::vector<int>* unperformed) const;
5049
5051 IntervalVar* Interval(int index) const;
5052
5054 IntVar* Next(int index) const;
5055
5057 int64_t size() const { return intervals_.size(); }
5058
5060 virtual void Accept(ModelVisitor* visitor) const;
5061
5062 private:
5063 int ComputeForwardFrontier();
5064 int ComputeBackwardFrontier();
5065 void UpdatePrevious() const;
5066
5067 const std::vector<IntervalVar*> intervals_;
5068 const std::vector<IntVar*> nexts_;
5069 mutable std::vector<int> previous_;
5070};
5071
5072class AssignmentElement {
5073 public:
5074 AssignmentElement() : activated_(true) {}
5075
5076 void Activate() { activated_ = true; }
5077 void Deactivate() { activated_ = false; }
5078 bool Activated() const { return activated_; }
5079
5080 private:
5081 bool activated_;
5082};
5083
5084class IntVarElement : public AssignmentElement {
5085 public:
5086 IntVarElement();
5087 explicit IntVarElement(IntVar* var);
5088 void Reset(IntVar* var);
5090 void Copy(const IntVarElement& element);
5091 IntVar* Var() const { return var_; }
5092 void Store() {
5093 min_ = var_->Min();
5094 max_ = var_->Max();
5095 }
5096 void Restore() {
5097 if (var_ != nullptr) {
5098 var_->SetRange(min_, max_);
5099 }
5100 }
5101 void LoadFromProto(const IntVarAssignment& int_var_assignment_proto);
5102 void WriteToProto(IntVarAssignment* int_var_assignment_proto) const;
5103
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_);
5110 // Get the value from an unbound int var assignment element.
5111 return min_;
5112 }
5113 bool Bound() const { return (max_ == min_); }
5114 void SetRange(int64_t l, int64_t u) {
5115 min_ = l;
5116 max_ = u;
5117 }
5118 void SetValue(int64_t v) {
5119 min_ = v;
5120 max_ = v;
5121 }
5122 std::string DebugString() const;
5123
5124 bool operator==(const IntVarElement& element) const;
5125 bool operator!=(const IntVarElement& element) const {
5126 return !(*this == element);
5127 }
5128
5129 private:
5130 IntVar* var_;
5131 int64_t min_;
5132 int64_t max_;
5134
5136 public:
5138 explicit IntervalVarElement(IntervalVar* var);
5139 void Reset(IntervalVar* var);
5141 void Copy(const IntervalVarElement& element);
5142 IntervalVar* Var() const { return var_; }
5143 void Store();
5144 void Restore();
5145 void LoadFromProto(
5146 const IntervalVarAssignment& interval_var_assignment_proto);
5147 void WriteToProto(IntervalVarAssignment* interval_var_assignment_proto) const;
5148
5149 int64_t StartMin() const { return start_min_; }
5150 int64_t StartMax() const { return start_max_; }
5151 int64_t StartValue() const {
5152 CHECK_EQ(start_max_, start_min_);
5153 return start_max_;
5154 }
5155 int64_t DurationMin() const { return duration_min_; }
5156 int64_t DurationMax() const { return duration_max_; }
5157 int64_t DurationValue() const {
5158 CHECK_EQ(duration_max_, duration_min_);
5159 return duration_max_;
5160 }
5161 int64_t EndMin() const { return end_min_; }
5162 int64_t EndMax() const { return end_max_; }
5163 int64_t EndValue() const {
5164 CHECK_EQ(end_max_, end_min_);
5165 return end_max_;
5167 int64_t PerformedMin() const { return performed_min_; }
5168 int64_t PerformedMax() const { return performed_max_; }
5169 int64_t PerformedValue() const {
5170 CHECK_EQ(performed_max_, performed_min_);
5171 return performed_max_;
5173 void SetStartMin(int64_t m) { start_min_ = m; }
5174 void SetStartMax(int64_t m) { start_max_ = m; }
5175 void SetStartRange(int64_t mi, int64_t ma) {
5176 start_min_ = mi;
5177 start_max_ = ma;
5178 }
5179 void SetStartValue(int64_t v) {
5180 start_min_ = v;
5181 start_max_ = v;
5182 }
5183 void SetDurationMin(int64_t m) { duration_min_ = m; }
5184 void SetDurationMax(int64_t m) { duration_max_ = m; }
5185 void SetDurationRange(int64_t mi, int64_t ma) {
5186 duration_min_ = mi;
5187 duration_max_ = ma;
5188 }
5189 void SetDurationValue(int64_t v) {
5190 duration_min_ = v;
5191 duration_max_ = v;
5192 }
5193 void SetEndMin(int64_t m) { end_min_ = m; }
5194 void SetEndMax(int64_t m) { end_max_ = m; }
5195 void SetEndRange(int64_t mi, int64_t ma) {
5196 end_min_ = mi;
5197 end_max_ = ma;
5198 }
5199 void SetEndValue(int64_t v) {
5200 end_min_ = v;
5201 end_max_ = v;
5202 }
5203 void SetPerformedMin(int64_t m) { performed_min_ = m; }
5204 void SetPerformedMax(int64_t m) { performed_max_ = m; }
5205 void SetPerformedRange(int64_t mi, int64_t ma) {
5206 performed_min_ = mi;
5207 performed_max_ = ma;
5209 void SetPerformedValue(int64_t v) {
5210 performed_min_ = v;
5211 performed_max_ = v;
5212 }
5213 bool Bound() const {
5214 return (start_min_ == start_max_ && duration_min_ == duration_max_ &&
5215 end_min_ == end_max_ && performed_min_ == performed_max_);
5217 std::string DebugString() const;
5218 bool operator==(const IntervalVarElement& element) const;
5219 bool operator!=(const IntervalVarElement& element) const {
5220 return !(*this == element);
5223 private:
5224 int64_t start_min_;
5225 int64_t start_max_;
5226 int64_t duration_min_;
5227 int64_t duration_max_;
5228 int64_t end_min_;
5229 int64_t end_max_;
5230 int64_t performed_min_;
5231 int64_t performed_max_;
5238
5238/// - the forward sequence. That is the list of interval variables
5239/// ranked first in the sequence. The first element of the backward
5240/// sequence is the first interval in the sequence variable.
5241/// - the backward sequence. That is the list of interval variables
5242/// ranked last in the sequence. The first element of the backward
5243/// sequence is the last interval in the sequence variable.
5244/// - The list of unperformed interval variables.
5245/// Furthermore, if all performed variables are ranked, then by
5246/// convention, the forward_sequence will contain all such variables
5247/// and the backward_sequence will be empty.
5249 public:
5251 explicit SequenceVarElement(SequenceVar* var);
5252 void Reset(SequenceVar* var);
5254 void Copy(const SequenceVarElement& element);
5255 SequenceVar* Var() const { return var_; }
5256 void Store();
5257 void Restore();
5259 const SequenceVarAssignment& sequence_var_assignment_proto);
5260 void WriteToProto(SequenceVarAssignment* sequence_var_assignment_proto) const;
5261
5262 const std::vector<int>& ForwardSequence() const;
5263 const std::vector<int>& BackwardSequence() const;
5264 const std::vector<int>& Unperformed() const;
5265 void SetSequence(const std::vector<int>& forward_sequence,
5266 const std::vector<int>& backward_sequence,
5267 const std::vector<int>& unperformed);
5268 void SetForwardSequence(const std::vector<int>& forward_sequence);
5269 void SetBackwardSequence(const std::vector<int>& backward_sequence);
5270 void SetUnperformed(const std::vector<int>& unperformed);
5271 bool Bound() const {
5272 return forward_sequence_.size() + unperformed_.size() == var_->size();
5273 }
5274
5275 std::string DebugString() const;
5276
5277 bool operator==(const SequenceVarElement& element) const;
5278 bool operator!=(const SequenceVarElement& element) const {
5279 return !(*this == element);
5280 }
5281
5282 private:
5283 bool CheckClassInvariants();
5284
5285 SequenceVar* var_;
5286 std::vector<int> forward_sequence_;
5287 std::vector<int> backward_sequence_;
5288 std::vector<int> unperformed_;
5289};
5290
5291template <class V, class E>
5292class AssignmentContainer {
5293 public:
5295 E* Add(V* var) {
5296 CHECK(var != nullptr);
5297 int index = -1;
5298 if (!Find(var, &index)) {
5299 return FastAdd(var);
5300 } else {
5301 return &elements_[index];
5302 }
5303 }
5305 E* FastAdd(V* var) {
5306 DCHECK(var != nullptr);
5307 elements_.emplace_back(var);
5308 return &elements_.back();
5309 }
5312 E* AddAtPosition(V* var, int position) {
5313 elements_[position].Reset(var);
5314 return &elements_[position];
5315 }
5316 void Clear() {
5317 elements_.clear();
5318 if (!elements_map_.empty()) {
5319 elements_map_.clear();
5320 }
5321 }
5324 void Resize(size_t size) { elements_.resize(size); }
5325 bool Empty() const { return elements_.empty(); }
5328 void CopyIntersection(const AssignmentContainer<V, E>& container) {
5329 for (int i = 0; i < container.elements_.size(); ++i) {
5330 const E& element = container.elements_[i];
5331 const V* const var = element.Var();
5332 int index = -1;
5333 if (i < elements_.size() && elements_[i].Var() == var) {
5334 index = i;
5335 } else if (!Find(var, &index)) {
5336 continue;
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();
5343 } else {
5344 local_element->Deactivate();
5345 }
5346 }
5347 }
5349
5350 void Copy(const AssignmentContainer<V, E>& container) {
5352 for (int i = 0; i < container.elements_.size(); ++i) {
5353 const E& element = container.elements_[i];
5354 FastAdd(element.Var())->Copy(element);
5355 }
5356 }
5357 bool Contains(const V* const var) const {
5358 int index;
5359 return Find(var, &index);
5360 }
5361 E* MutableElement(const V* const var) {
5362 E* const element = MutableElementOrNull(var);
5363 DCHECK(element != nullptr)
5364 << "Unknown variable " << var->DebugString() << " in solution";
5365 return element;
5366 }
5367 E* MutableElementOrNull(const V* const var) {
5368 int index = -1;
5369 if (Find(var, &index)) {
5370 return MutableElement(index);
5372 return nullptr;
5373 }
5374 const E& Element(const V* const var) const {
5375 const E* const element = ElementPtrOrNull(var);
5376 DCHECK(element != nullptr)
5377 << "Unknown variable " << var->DebugString() << " in solution";
5378 return *element;
5379 }
5380 const E* ElementPtrOrNull(const V* const var) const {
5381 int index = -1;
5382 if (Find(var, &index)) {
5383 return &Element(index);
5385 return nullptr;
5386 }
5387 const std::vector<E>& elements() const { return elements_; }
5388 E* MutableElement(int index) { return &elements_[index]; }
5389 const E& Element(int index) const { return elements_[index]; }
5390 int Size() const { return elements_.size(); }
5391 void Store() {
5392 for (E& element : elements_) {
5393 element.Store();
5394 }
5395 }
5396 void Restore() {
5397 for (E& element : elements_) {
5398 if (element.Activated()) {
5399 element.Restore();
5400 }
5401 }
5402 }
5403 bool AreAllElementsBound() const {
5404 for (const E& element : elements_) {
5405 if (!element.Bound()) return false;
5406 }
5407 return true;
5408 }
5413 bool operator==(const AssignmentContainer<V, E>& container) const {
5415 if (Size() != container.Size()) {
5416 return false;
5417 }
5419 EnsureMapIsUpToDate();
5420
5420 /// Do not use the hash_map::== operator! It
5421 /// compares both content and how the map is hashed (e.g., number of
5422 /// buckets). This is not what we want.
5423 for (const E& element : container.elements_) {
5424 const int position =
5425 gtl::FindWithDefault(elements_map_, element.Var(), -1);
5426 if (position < 0 || elements_[position] != element) {
5427 return false;
5428 }
5429 }
5430 return true;
5431 }
5432 bool operator!=(const AssignmentContainer<V, E>& container) const {
5433 return !(*this == container);
5434 }
5435
5436 private:
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;
5442 }
5443 }
5444 bool Find(const V* const var, int* index) const {
5446 const size_t kMaxSizeForLinearAccess = 11;
5447 if (Size() <= kMaxSizeForLinearAccess) {
5450 /// hash table.
5451 for (int i = 0; i < elements_.size(); ++i) {
5452 if (var == elements_[i].Var()) {
5453 *index = i;
5454 return true;
5456 }
5457 return false;
5458 } else {
5459 EnsureMapIsUpToDate();
5460 DCHECK_EQ(elements_map_.size(), elements_.size());
5461 return gtl::FindCopy(elements_map_, var, index);
5463 }
5464
5465 std::vector<E> elements_;
5466 absl::flat_hash_map<const V*, int> elements_map_;
5467};
5468
5471class Assignment : public PropagationBaseObject {
5472 public:
5478
5479 explicit Assignment(Solver* solver);
5480 explicit Assignment(const Assignment* copy);
5481
5482#ifndef SWIG
5483 // This type is neither copyable nor movable.
5484 Assignment(const Assignment&) = delete;
5485 Assignment& operator=(const Assignment&) = delete;
5486#endif
5487
5488 ~Assignment() override;
5489
5490 void Clear();
5491 bool Empty() const {
5492 return int_var_container_.Empty() && interval_var_container_.Empty() &&
5493 sequence_var_container_.Empty();
5494 }
5495 int Size() const {
5497 }
5498 int NumIntVars() const { return int_var_container_.Size(); }
5499 int NumIntervalVars() const { return interval_var_container_.Size(); }
5500 int NumSequenceVars() const { return sequence_var_container_.Size(); }
5501 void Store();
5502 void Restore();
5503
5506 bool Load(const std::string& filename);
5507#if !defined(SWIG)
5508 bool Load(File* file);
5509#endif
5510 void Load(const AssignmentProto& assignment_proto);
5512 bool Save(const std::string& filename) const;
5513#if !defined(SWIG)
5514 bool Save(File* file) const;
5515#endif // #if !defined(SWIG)
5516 void Save(AssignmentProto* assignment_proto) const;
5517
5518 void AddObjective(IntVar* const v) { AddObjectives({v}); }
5519 void AddObjectives(const std::vector<IntVar*>& vars) {
5520 // Objective can only set once.
5521 DCHECK(!HasObjective());
5522 objective_elements_.reserve(vars.size());
5523 for (IntVar* const var : vars) {
5524 if (var != nullptr) {
5525 objective_elements_.emplace_back(var);
5526 }
5527 }
5528 }
5529 void ClearObjective() { objective_elements_.clear(); }
5530 int NumObjectives() const { return objective_elements_.size(); }
5531 IntVar* Objective() const { return ObjectiveFromIndex(0); }
5532 IntVar* ObjectiveFromIndex(int index) const {
5533 return HasObjectiveFromIndex(index) ? objective_elements_[index].Var()
5534 : nullptr;
5535 }
5536 bool HasObjective() const { return !objective_elements_.empty(); }
5537 bool HasObjectiveFromIndex(int index) const {
5538 return index < objective_elements_.size();
5539 }
5540 int64_t ObjectiveMin() const { return ObjectiveMinFromIndex(0); }
5541 int64_t ObjectiveMax() const { return ObjectiveMaxFromIndex(0); }
5542 int64_t ObjectiveValue() const { return ObjectiveValueFromIndex(0); }
5543 bool ObjectiveBound() const { return ObjectiveBoundFromIndex(0); }
5545 void SetObjectiveMax(int64_t m) { SetObjectiveMaxFromIndex(0, m); }
5546 void SetObjectiveValue(int64_t value) {
5548 }
5549 void SetObjectiveRange(int64_t l, int64_t u) {
5551 }
5552 int64_t ObjectiveMinFromIndex(int index) const {
5553 return HasObjectiveFromIndex(index) ? objective_elements_[index].Min() : 0;
5555 int64_t ObjectiveMaxFromIndex(int index) const {
5556 return HasObjectiveFromIndex(index) ? objective_elements_[index].Max() : 0;
5558 int64_t ObjectiveValueFromIndex(int index) const {
5559 return HasObjectiveFromIndex(index) ? objective_elements_[index].Value()
5560 : 0;
5561 }
5562 bool ObjectiveBoundFromIndex(int index) const {
5563 return HasObjectiveFromIndex(index) ? objective_elements_[index].Bound()
5564 : true;
5565 }
5566 void SetObjectiveMinFromIndex(int index, int64_t m) {
5567 if (HasObjectiveFromIndex(index)) {
5568 objective_elements_[index].SetMin(m);
5569 }
5570 }
5571 void SetObjectiveMaxFromIndex(int index, int64_t m) {
5572 if (HasObjectiveFromIndex(index)) {
5573 objective_elements_[index].SetMax(m);
5574 }
5575 }
5576 void SetObjectiveValueFromIndex(int index, int64_t value) {
5578 objective_elements_[index].SetValue(value);
5579 }
5580 }
5581 void SetObjectiveRangeFromIndex(int index, int64_t l, int64_t u) {
5582 if (HasObjectiveFromIndex(index)) {
5583 objective_elements_[index].SetRange(l, u);
5584 }
5585 }
5586
5587 IntVarElement* Add(IntVar* var);
5588 void Add(const std::vector<IntVar*>& vars);
5591 int64_t Min(const IntVar* var) const;
5592 int64_t Max(const IntVar* var) const;
5593 int64_t Value(const IntVar* var) const;
5594 bool Bound(const IntVar* var) const;
5595 void SetMin(const IntVar* var, int64_t m);
5596 void SetMax(const IntVar* var, int64_t m);
5597 void SetRange(const IntVar* var, int64_t l, int64_t u);
5598 void SetValue(const IntVar* var, int64_t value);
5601 void Add(const std::vector<IntervalVar*>& vars);
5604 int64_t StartMin(const IntervalVar* var) const;
5605 int64_t StartMax(const IntervalVar* var) const;
5606 int64_t StartValue(const IntervalVar* var) const;
5607 int64_t DurationMin(const IntervalVar* var) const;
5608 int64_t DurationMax(const IntervalVar* var) const;
5609 int64_t DurationValue(const IntervalVar* var) const;
5610 int64_t EndMin(const IntervalVar* var) const;
5611 int64_t EndMax(const IntervalVar* var) const;
5612 int64_t EndValue(const IntervalVar* var) const;
5613 int64_t PerformedMin(const IntervalVar* var) const;
5614 int64_t PerformedMax(const IntervalVar* var) const;
5615 int64_t PerformedValue(const IntervalVar* var) const;
5616 void SetStartMin(const IntervalVar* var, int64_t m);
5617 void SetStartMax(const IntervalVar* var, int64_t m);
5618 void SetStartRange(const IntervalVar* var, int64_t mi, int64_t ma);
5619 void SetStartValue(const IntervalVar* var, int64_t value);
5620 void SetDurationMin(const IntervalVar* var, int64_t m);
5621 void SetDurationMax(const IntervalVar* var, int64_t m);
5622 void SetDurationRange(const IntervalVar* var, int64_t mi, int64_t ma);
5623 void SetDurationValue(const IntervalVar* var, int64_t value);
5624 void SetEndMin(const IntervalVar* var, int64_t m);
5625 void SetEndMax(const IntervalVar* var, int64_t m);
5626 void SetEndRange(const IntervalVar* var, int64_t mi, int64_t ma);
5627 void SetEndValue(const IntervalVar* var, int64_t value);
5628 void SetPerformedMin(const IntervalVar* var, int64_t m);
5629 void SetPerformedMax(const IntervalVar* var, int64_t m);
5630 void SetPerformedRange(const IntervalVar* var, int64_t mi, int64_t ma);
5631 void SetPerformedValue(const IntervalVar* var, int64_t value);
5632
5634 void Add(const std::vector<SequenceVar*>& vars);
5635
5635 /// Adds without checking if the variable had been previously added.
5637 const std::vector<int>& ForwardSequence(const SequenceVar* var) const;
5638 const std::vector<int>& BackwardSequence(const SequenceVar* var) const;
5639 const std::vector<int>& Unperformed(const SequenceVar* var) const;
5640 void SetSequence(const SequenceVar* var,
5641 const std::vector<int>& forward_sequence,
5642 const std::vector<int>& backward_sequence,
5643 const std::vector<int>& unperformed);
5644 void SetForwardSequence(const SequenceVar* var,
5645 const std::vector<int>& forward_sequence);
5646 void SetBackwardSequence(const SequenceVar* var,
5647 const std::vector<int>& backward_sequence);
5648 void SetUnperformed(const SequenceVar* var,
5649 const std::vector<int>& unperformed);
5650
5651 void Activate(const IntVar* var);
5652 void Deactivate(const IntVar* var);
5653 bool Activated(const IntVar* var) const;
5654
5655 void Activate(const IntervalVar* var);
5656 void Deactivate(const IntervalVar* var);
5657 bool Activated(const IntervalVar* var) const;
5658
5659 void Activate(const SequenceVar* var);
5660 void Deactivate(const SequenceVar* var);
5661 bool Activated(const SequenceVar* var) const;
5662
5665 bool ActivatedObjective() const { return ActivatedObjectiveFromIndex(0); }
5666 void ActivateObjectiveFromIndex(int index) {
5667 if (HasObjectiveFromIndex(index)) {
5668 objective_elements_[index].Activate();
5669 }
5670 }
5671 void DeactivateObjectiveFromIndex(int index) {
5672 if (HasObjectiveFromIndex(index)) {
5673 objective_elements_[index].Deactivate();
5674 }
5675 }
5676 bool ActivatedObjectiveFromIndex(int index) const {
5677 return HasObjectiveFromIndex(index) ? objective_elements_[index].Activated()
5678 : true;
5679 }
5680
5681 std::string DebugString() const override;
5682
5683 bool AreAllElementsBound() const {
5684 return int_var_container_.AreAllElementsBound() &&
5685 interval_var_container_.AreAllElementsBound() &&
5686 sequence_var_container_.AreAllElementsBound();
5687 }
5688
5689 bool Contains(const IntVar* var) const;
5690 bool Contains(const IntervalVar* var) const;
5691 bool Contains(const SequenceVar* var) const;
5694 void CopyIntersection(const Assignment* assignment);
5697 void Copy(const Assignment* assignment);
5698
5699 // TODO(user): Add element iterators to avoid exposing container class.
5700 const IntContainer& IntVarContainer() const { return int_var_container_; }
5701 IntContainer* MutableIntVarContainer() { return &int_var_container_; }
5703 return interval_var_container_;
5704 }
5706 return &interval_var_container_;
5707 }
5709 return sequence_var_container_;
5710 }
5712 return &sequence_var_container_;
5713 }
5714 bool operator==(const Assignment& assignment) const {
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_;
5719 }
5720 bool operator!=(const Assignment& assignment) const {
5721 return !(*this == assignment);
5724 private:
5725 IntContainer int_var_container_;
5726 IntervalContainer interval_var_container_;
5727 SequenceContainer sequence_var_container_;
5728 std::vector<IntVarElement> objective_elements_;
5729};
5731std::ostream& operator<<(std::ostream& out,
5732 const Assignment& assignment);
5733
5735
5735/// all IntVars in "target_vars", with the values of the variables set according
5736/// to the corresponding values of "source_vars" in "source_assignment".
5737/// source_vars and target_vars must have the same number of elements.
5738/// The source and target assignments can belong to different Solvers.
5739void SetAssignmentFromAssignment(Assignment* target_assignment,
5740 const std::vector<IntVar*>& target_vars,
5741 const Assignment* source_assignment,
5742 const std::vector<IntVar*>& source_vars);
5743
5744class Pack : public Constraint {
5745 public:
5746 Pack(Solver* s, const std::vector<IntVar*>& vars, int number_of_bins);
5747
5748 ~Pack() override;
5749
5754
5759 const std::vector<int64_t>& weights, const std::vector<int64_t>& bounds);
5761 /// This dimension imposes that for all bins b, the weighted sum
5762 /// (weights->Run(i)) of all objects i assigned to 'b' is less or
5763 /// equal to 'bounds[b]'. Ownership of the callback is transferred to
5764 /// the pack constraint.
5766 Solver::IndexEvaluator1 weights, const std::vector<int64_t>& bounds);
5770
5770 /// equal to 'bounds[b]'. Ownership of the callback is transferred to
5771 /// the pack constraint.
5773 Solver::IndexEvaluator2 weights, const std::vector<int64_t>& bounds);
5774
5777 void AddWeightedSumEqualVarDimension(const std::vector<int64_t>& weights,
5778 const std::vector<IntVar*>& loads);
5782
5784 const std::vector<IntVar*>& loads);
5785
5789
5796 const std::vector<IntVar*>& usage, const std::vector<int64_t>& capacity);
5797
5800 void AddWeightedSumOfAssignedDimension(const std::vector<int64_t>& weights,
5801 IntVar* cost_var);
5802
5803 /// This dimension links 'count_var' to the actual number of bins used in the
5804 /// pack.
5805 void AddCountUsedBinDimension(IntVar* count_var);
5806
5809 void AddCountAssignedItemsDimension(IntVar* count_var);
5810
5811 void Post() override;
5812 void ClearAll();
5813 void PropagateDelayed();
5814 void InitialPropagate() override;
5815 void Propagate();
5816 void OneDomain(int var_index);
5817 std::string DebugString() const override;
5818 bool IsUndecided(int var_index, int bin_index) const;
5819 void SetImpossible(int var_index, int bin_index);
5820 void Assign(int var_index, int bin_index);
5821 bool IsAssignedStatusKnown(int var_index) const;
5822 bool IsPossible(int var_index, int bin_index) const;
5823 IntVar* AssignVar(int var_index, int bin_index) const;
5824 void SetAssigned(int var_index);
5825 void SetUnassigned(int var_index);
5826 void RemoveAllPossibleFromBin(int bin_index);
5827 void AssignAllPossibleToBin(int bin_index);
5828 void AssignFirstPossibleToBin(int bin_index);
5831 void Accept(ModelVisitor* visitor) const override;
5832
5833 private:
5834 bool IsInProcess() const;
5835 const std::vector<IntVar*> vars_;
5836 const int bins_;
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_;
5842 uint64_t stamp_;
5843 Demon* demon_;
5844 std::vector<std::pair<int, int>> to_set_;
5845 std::vector<std::pair<int, int>> to_unset_;
5846 bool in_process_;
5847};
5848
5849class DisjunctiveConstraint : public Constraint {
5850 public:
5851 DisjunctiveConstraint(Solver* s, const std::vector<IntervalVar*>& intervals,
5852 const std::string& name);
5853
5854#ifndef SWIG
5855 // This type is neither copyable nor movable.
5858#endif
5859
5860 ~DisjunctiveConstraint() override;
5861
5863 virtual SequenceVar* MakeSequenceVar() = 0;
5864
5869 void SetTransitionTime(Solver::IndexEvaluator2 transition_time);
5870
5871 int64_t TransitionTime(int before_index, int after_index) {
5872 DCHECK(transition_time_);
5873 return transition_time_(before_index, after_index);
5874 }
5875
5876#if !defined(SWIG)
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;
5881#endif // !defined(SWIG)
5882
5883 protected:
5884 const std::vector<IntervalVar*> intervals_;
5886};
5887
5890class SolutionPool : public BaseObject {
5891 public:
5892 SolutionPool() {}
5893 ~SolutionPool() override {}
5894
5897 virtual void Initialize(Assignment* assignment) = 0;
5898
5901 virtual void RegisterNewSolution(Assignment* assignment) = 0;
5902
5905 virtual void GetNextSolution(Assignment* assignment) = 0;
5906
5908
5909 virtual bool SyncNeeded(Assignment* local_assignment) = 0;
5910};
5911} // namespace operations_research
5912
5913#endif // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
#define OR_DLL
Definition base_export.h:27
Definition file.h:30
const E & Element(const V *const var) const
E * FastAdd(V *var)
Adds element without checking its presence in the container.
void Copy(const AssignmentContainer< V, E > &container)
bool operator!=(const AssignmentContainer< V, E > &container) const
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)
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
int64_t ObjectiveValueFromIndex(int index) const
int64_t DurationMax(const IntervalVar *var) const
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
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
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
void SetObjectiveRange(int64_t l, int64_t u)
IntVarElement * Add(IntVar *var)
const IntervalContainer & IntervalVarContainer() const
const SequenceContainer & SequenceVarContainer() const
void SetPerformedMax(const IntervalVar *var, int64_t m)
int64_t ObjectiveMinFromIndex(int index) const
void SetObjectiveMinFromIndex(int index, int64_t m)
std::string DebugString() const override
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.
void Deactivate(const IntVar *var)
void Copy(const Assignment *assignment)
const std::vector< int > & ForwardSequence(const SequenceVar *var) const
AssignmentContainer< IntVar, IntVarElement > IntContainer
void SetRange(const IntVar *var, int64_t l, int64_t u)
int64_t ObjectiveMaxFromIndex(int index) const
bool ActivatedObjectiveFromIndex(int index) const
int64_t DurationMin(const IntervalVar *var) const
const IntContainer & IntVarContainer() const
void SetObjectiveMaxFromIndex(int index, int64_t m)
bool Bound(const IntVar *var) const
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)
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)
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 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 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
virtual int64_t Step(int index) const =0
CastConstraint(Solver *const solver, 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?
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 DebugString() const override
-------— Decision Builder -------—
virtual void VisitRankFirstInterval(SequenceVar *sequence, int index)
virtual void VisitSetVariableValue(IntVar *var, int64_t value)
virtual void VisitScheduleOrPostpone(IntervalVar *var, int64_t est)
virtual void VisitRankLastInterval(SequenceVar *sequence, int index)
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.
Definition resource.cc:2585
virtual const std::vector< IntVar * > & time_cumuls() const =0
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
void SetTransitionTime(Solver::IndexEvaluator2 transition_time)
Definition resource.cc:2597
bool CheckWithOffset(absl::Duration offset) override
Definition search.cc:4808
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 --—
Definition search.cc:4736
void Init() override
This method is called when the search limit is initialized.
Definition search.cc:4774
void Install() override
A search monitors adds itself on the active search.
Definition search.cc:4769
void Copy(const SearchLimit *limit) override
Definition search.cc:4784
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Definition search.cc:4801
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 --—
Definition tuple_set.h:47
bool operator==(const IntVarElement &element) const
Definition assignment.cc:75
void SetRange(int64_t l, int64_t u)
bool operator!=(const IntVarElement &element) const
IntVarElement()
--------------— Solutions ---------------------—
Definition assignment.cc:38
std::string DebugString() const
Definition assignment.cc:98
void Copy(const IntVarElement &element)
Definition assignment.cc:54
void WriteToProto(IntVarAssignment *int_var_assignment_proto) const
Definition assignment.cc:90
void LoadFromProto(const IntVarAssignment &int_var_assignment_proto)
Definition assignment.cc:64
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.
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 SetDurationRange(int64_t mi, int64_t ma)
void WriteToProto(IntervalVarAssignment *interval_var_assignment_proto) const
bool operator!=(const IntervalVarElement &element) const
void Copy(const IntervalVarElement &element)
void SetEndRange(int64_t mi, int64_t ma)
IntervalVarElement()
--— IntervalVarElement --—
bool operator==(const IntervalVarElement &element) const
void SetStartRange(int64_t mi, int64_t ma)
void SetPerformedRange(int64_t mi, int64_t ma)
void LoadFromProto(const IntervalVarAssignment &interval_var_assignment_proto)
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
void WhenAnything(Demon *d)
Attaches a demon awakened when anything about this interval changes.
Definition interval.cc:2272
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 -------—
virtual void VisitSequenceVariable(const SequenceVar *variable)
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[]
void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64_t index_min, int64_t index_max)
--— Helpers --—
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 kMirrorOperation[]
Operations.
static const char kActiveArgument[]
argument names:
virtual void BeginVisitModel(const std::string &type_name)
--— Virtual methods for visitors --—
virtual void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *expr)
virtual void VisitIntegerArgument(const std::string &arg_name, int64_t value)
Visit integer arguments.
virtual void VisitIntegerVariable(const IntVar *variable, IntExpr *delegate)
virtual void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments)
virtual void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &tuples)
virtual void VisitIntegerVariableEvaluatorArgument(const std::string &arg_name, const Solver::Int64ToIntVar &arguments)
Helpers.
static const char kStartSyncOnStartOperation[]
virtual void EndVisitModel(const std::string &type_name)
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *argument)
Visit integer expression argument.
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
virtual void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64_t > &values)
static const char kUsageLessConstantExtension[]
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *constraint)
virtual void EndVisitExtension(const std::string &type)
static const char kUsageEqualVariableExtension[]
static const char kCountAssignedItemsExtension[]
Extension names:
virtual void VisitIntervalVariable(const IntervalVar *variable, const std::string &operation, int64_t value, IntervalVar *delegate)
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64_t index_min, int64_t index_max)
virtual void BeginVisitExtension(const std::string &type)
static const char kWeightedSumOfAssignedEqualVariableExtension[]
virtual void VisitSequenceArgument(const std::string &arg_name, SequenceVar *argument)
Visit sequence argument.
virtual void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *expr)
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)
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.
void Add(Solver *const s, const T &to_add)
bool CurrentInternalValuesAreConstraining() const
Definition search.cc:3183
const std::vector< IntVar * > & minimization_vars() const
const std::vector< IntVar * > & objective_vars() const
int64_t Step(int index) const override
void SetCurrentInternalValue(int index, int64_t value)
void MakeMinimizationVarsLessOrEqualWithSteps(const T &upper_bounds)
int64_t CurrentInternalValue(int index) const
bool Maximize(int index) const override
bool AcceptDelta(Assignment *delta, Assignment *deltadelta) override
Definition search.cc:3133
void Accept(ModelVisitor *visitor) const override
Accepts the given model visitor.
Definition search.cc:3173
int64_t BestValue(int index) const override
ObjectiveMonitor(Solver *solver, const std::vector< bool > &maximize, std::vector< IntVar * > vars, std::vector< int64_t > steps)
Definition search.cc:3075
IntVar * MakeMinimizationVarsLessOrEqualWithStepsStatus(const T &upper_bounds)
void EnterSearch() override
Beginning of the search.
Definition search.cc:3109
ObjectiveMonitor & operator=(const ObjectiveMonitor &)=delete
IntVar * ObjectiveVar(int index) const override
IntVar * MinimizationVar(int index) const override
void BeginNextDecision(DecisionBuilder *db) override
Internal methods.
Definition search.cc:3205
int64_t best() const
Returns the best value found during search.
void RefuteDecision(Decision *d) override
Before refuting the decision.
Definition search.cc:3218
IntVar * var() const
Returns the variable that is optimized.
OptimizeVar(Solver *solver, bool maximize, IntVar *var, int64_t step)
Definition search.cc:3196
std::string DebugString() const override
Definition search.cc:3247
virtual std::string Name() const
Definition search.cc:3245
void SetUnassigned(int var_index)
Definition pack.cc:445
void SetAssigned(int var_index)
Definition pack.cc:437
void Assign(int var_index, int bin_index)
Definition pack.cc:417
bool IsPossible(int var_index, int bin_index) const
Definition pack.cc:429
void Post() override
Definition pack.cc:128
void AddCountUsedBinDimension(IntVar *count_var)
Definition pack.cc:1599
Pack(Solver *s, const std::vector< IntVar * > &vars, int number_of_bins)
--— Pack --—
Definition pack.cc:109
void AddWeightedSumLessOrEqualConstantDimension(const std::vector< int64_t > &weights, const std::vector< int64_t > &bounds)
-------— API -------—
Definition pack.cc:1530
void AddSumVariableWeightsLessOrEqualConstantDimension(const std::vector< IntVar * > &usage, const std::vector< int64_t > &capacity)
Definition pack.cc:1589
void AddCountAssignedItemsDimension(IntVar *count_var)
Definition pack.cc:1606
void UnassignAllRemainingItems()
Definition pack.cc:494
void AssignAllRemainingItems()
Definition pack.cc:484
std::string DebugString() const override
--------------— Constraint class ----------------—
Definition pack.cc:381
void AssignAllPossibleToBin(int bin_index)
Definition pack.cc:467
void Accept(ModelVisitor *visitor) const override
Accepts the given visitor.
Definition pack.cc:394
IntVar * AssignVar(int var_index, int bin_index) const
Definition pack.cc:433
bool IsAssignedStatusKnown(int var_index) const
Definition pack.cc:425
void AssignFirstPossibleToBin(int bin_index)
Definition pack.cc:477
void AddWeightedSumEqualVarDimension(const std::vector< int64_t > &weights, const std::vector< IntVar * > &loads)
Definition pack.cc:1560
void RemoveAllPossibleFromBin(int bin_index)
Definition pack.cc:457
void AddWeightedSumOfAssignedDimension(const std::vector< int64_t > &weights, IntVar *cost_var)
Definition pack.cc:1580
void InitialPropagate() override
Definition pack.cc:191
void SetImpossible(int var_index, int bin_index)
Definition pack.cc:409
void OneDomain(int var_index)
Definition pack.cc:335
bool IsUndecided(int var_index, int bin_index) const
Definition pack.cc:405
ProfiledDecisionBuilder(DecisionBuilder *db)
--------------— ProfiledDecisionBuilder ---------—
std::string DebugString() const override
-------— Decision Builder -------—
void Accept(ModelVisitor *visitor) const override
void AppendMonitors(Solver *solver, std::vector< SearchMonitor * > *extras) override
PropagationBaseObject & operator=(const PropagationBaseObject &)=delete
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)
virtual std::string BaseName() const
Returns a base name for automatic naming.
void reset_action_on_fail()
This method clears the failure callback.
bool HasName() const
Returns whether the object has been named or not.
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Definition search.cc:4560
bool IsUncheckedSolutionLimitReached() override
Definition search.cc:4620
void Install() override
A search monitors adds itself on the active search.
Definition search.cc:4541
bool CheckWithOffset(absl::Duration offset) override
Definition search.cc:4568
void Init() override
This method is called when the search limit is initialized.
Definition search.cc:4589
std::string DebugString() const override
Definition search.cc:4626
void Accept(ModelVisitor *visitor) const override
Accepts the given model visitor.
Definition search.cc:4634
void ExitSearch() override
End of the search.
Definition search.cc:4600
RegularLimit(Solver *s, absl::Duration time, int64_t branches, int64_t failures, int64_t solutions, bool smart_time_check, bool cumulative)
--— Regular Limit --—
Definition search.cc:4520
void Copy(const SearchLimit *limit) override
Definition search.cc:4549
void UpdateLimits(absl::Duration time, int64_t branches, int64_t failures, int64_t solutions)
Definition search.cc:4611
RegularLimit * MakeIdenticalClone() const
Definition search.cc:4562
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 -------—
Definition search.cc:4481
std::string DebugString() const override
void BeginNextDecision(DecisionBuilder *b) override
Before calling DecisionBuilder::Next.
Definition search.cc:4495
void PeriodicCheck() override
Periodic call to check limits in long running methods.
Definition search.cc:4505
bool crossed() const
Returns true if the limit has been crossed.
virtual void Copy(const SearchLimit *limit)=0
void EnterSearch() override
Internal methods.
Definition search.cc:4490
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.
Definition search.cc:4483
SearchLimit & operator=(const SearchLimit &)=delete
virtual bool CheckWithOffset(absl::Duration offset)=0
void RefuteDecision(Decision *d) override
Before refuting the decision.
Definition search.cc:4500
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.
virtual void Install()
A search monitors adds itself on the active search.
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 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 void ExitSearch()
End of the search.
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 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 WriteToProto(SequenceVarAssignment *sequence_var_assignment_proto) const
bool operator==(const SequenceVarElement &element) const
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)
void LoadFromProto(const SequenceVarAssignment &sequence_var_assignment_proto)
const std::vector< int > & Unperformed() const
void HorizonRange(int64_t *hmin, int64_t *hmax) const
virtual void Accept(ModelVisitor *visitor) const
Accepts the given visitor.
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 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.
Definition search.cc:2492
SolutionData BuildSolutionDataForCurrentState()
Definition search.cc:2442
void AddObjectives(const std::vector< IntVar * > &objectives)
Definition search.cc:2419
const std::vector< int > & ForwardSequence(int n, SequenceVar *var) const
Definition search.cc:2532
int64_t objective_value(int n) const
Returns the objective value of the nth solution.
Definition search.cc:2502
void Add(IntVar *var)
Add API.
Definition search.cc:2377
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.
Definition search.cc:2528
void EnterSearch() override
Beginning of the search.
Definition search.cc:2425
void FreeSolution(Assignment *solution)
Definition search.cc:2463
void Push(const SolutionData &data)
void PopSolution()
Remove and delete the last popped solution.
Definition search.cc:2434
const std::vector< int > & Unperformed(int n, SequenceVar *var) const
Definition search.cc:2542
void AddObjective(IntVar *objective)
Definition search.cc:2413
bool has_solution() const
Returns whether any solutions were stored during the search.
Definition search.cc:2485
int solution_count() const
Returns how many solutions were stored during the search.
Definition search.cc:2483
void Install() override
A search monitors adds itself on the active search.
Definition search.cc:2373
int64_t wall_time(int n) const
Returns the wall time in ms for the nth solution.
Definition search.cc:2487
void PushSolution()
Push the current state as a new solution.
Definition search.cc:2430
int64_t DurationValue(int n, IntervalVar *var) const
This is a shortcut to get the DurationValue of 'var' in the nth solution.
Definition search.cc:2520
int64_t ObjectiveValueFromIndex(int n, int index) const
Returns the value of the index-th objective of the nth solution.
Definition search.cc:2507
const std::vector< int > & BackwardSequence(int n, SequenceVar *var) const
Definition search.cc:2537
int64_t StartValue(int n, IntervalVar *var) const
This is a shortcut to get the StartValue of 'var' in the nth solution.
Definition search.cc:2516
SolutionCollector(Solver *solver, const Assignment *assignment)
-------— Solution Collectors --------—
Definition search.cc:2335
Assignment * solution(int n) const
Returns the nth solution.
Definition search.cc:2474
int64_t Value(int n, IntVar *var) const
This is a shortcut to get the Value of 'var' in the nth solution.
Definition search.cc:2512
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.
Definition search.cc:2479
int64_t EndValue(int n, IntervalVar *var) const
This is a shortcut to get the EndValue of 'var' in the nth solution.
Definition search.cc:2524
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].
Definition count_cst.cc:966
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 --—
Definition interval.cc:2249
IntExpr * MakeElement(const std::vector< int64_t > &values, IntVar *index)
values[index]
Definition element.cc:658
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)
Constraint * MakeIsLessOrEqualCt(IntExpr *left, IntExpr *right, IntVar *b)
b == (left <= right)
Definition range_cst.cc:736
Decision * MakeAssignVariablesValuesOrDoNothing(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values)
Definition search.cc:1878
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)
Definition expr_cst.cc:493
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)
Definition range_cst.cc:791
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)
Definition search.cc:5059
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.
Definition expr_cst.cc:1239
void set_fail_intercept(std::function< void()> fail_intercept)
Internal.
Constraint * MakeIsGreaterCt(IntExpr *left, IntExpr *right, IntVar *b)
b == (left > right)
Definition range_cst.cc:806
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Constraint * MakeIsGreaterOrEqualCt(IntExpr *left, IntExpr *right, IntVar *b)
b == (left >= right)
Definition range_cst.cc:796
SearchMonitor * MakeEnterSearchCallback(std::function< void()> callback)
--— Callback-based search monitors --—
Definition search.cc:514
LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)
Constraint * MakeIsEqualCt(IntExpr *v1, IntExpr *v2, IntVar *b)
b == (v1 == v2)
Definition range_cst.cc:628
IntVar * MakeIsMemberVar(IntExpr *expr, const std::vector< int64_t > &values)
Definition expr_cst.cc:1501
Decision * MakeAssignVariableValueOrFail(IntVar *var, int64_t value)
Definition search.cc:1678
Constraint * MakeNonEquality(IntExpr *left, IntExpr *right)
left != right
Definition range_cst.cc:570
IntVar * MakeIsEqualCstVar(IntExpr *var, int64_t value)
status var of (var == value)
Definition expr_cst.cc:468
Constraint * MakeSubCircuit(const std::vector< IntVar * > &nexts)
Decision * MakeVariableLessOrEqualValue(IntVar *var, int64_t value)
Definition search.cc:1766
IntExpr * MakeMax(const std::vector< IntVar * > &vars)
std::max(vars)
SearchMonitor * MakeLubyRestart(int scale_factor)
Definition search.cc:5291
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).
Definition search.cc:3302
IntervalVar * MakeFixedDurationStartSyncedOnEndIntervalVar(IntervalVar *interval_var, int64_t duration, int64_t offset)
Definition interval.cc:2450
LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
IntExpr * MakeDifference(IntExpr *left, IntExpr *right)
left - right
SearchMonitor * MakeConstantRestart(int frequency)
Definition search.cc:5326
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)
Definition search.cc:5178
Constraint * MakeMemberCt(IntExpr *expr, const std::vector< int64_t > &values)
--— Member and related constraints --—
Definition expr_cst.cc:1169
ABSL_MUST_USE_RESULT RegularLimit * MakeSolutionsLimit(int64_t solutions)
Definition search.cc:4694
Constraint * MakeGreaterOrEqual(IntExpr *left, IntExpr *right)
left >= right
Definition range_cst.cc:548
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)
Definition interval.cc:2425
SolutionCollector * MakeBestValueSolutionCollector(const Assignment *assignment, bool maximize)
Definition search.cc:2754
IntVar * MakeIsLessOrEqualCstVar(IntExpr *var, int64_t value)
status var of (var <= value)
Definition expr_cst.cc:785
Constraint * MakeIfThenElseCt(IntVar *condition, IntExpr *then_expr, IntExpr *else_expr, IntVar *target_var)
Special cases with arrays of size two.
Definition element.cc:1607
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.
Definition resource.cc:2620
ABSL_MUST_USE_RESULT SearchLimit * MakeCustomLimit(std::function< bool()> limiter)
Definition search.cc:5016
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)
Definition expr_cst.cc:1489
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)
Definition range_cst.cc:647
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.
Definition interval.cc:2416
ABSL_MUST_USE_RESULT RegularLimit * MakeFailuresLimit(int64_t failures)
Definition search.cc:4687
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)
Definition search.cc:3309
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)
Definition diffn.cc:330
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)
Definition range_cst.cc:802
Decision * MakeVariableGreaterOrEqualValue(IntVar *var, int64_t value)
Definition search.cc:1771
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
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)
Definition range_cst.cc:748
ABSL_MUST_USE_RESULT RegularLimit * MakeTimeLimit(absl::Duration time)
Creates a search limit that constrains the running time.
Definition search.cc:4673
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)
Definition deviation.cc:414
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 -------—
Definition resource.cc:2608
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.
Definition trace.cc:860
Constraint * MakeIsGreaterCstCt(IntExpr *v, int64_t c, IntVar *b)
b == (v > c)
Definition expr_cst.cc:722
DecisionBuilder * Compose(DecisionBuilder *db1, DecisionBuilder *db2)
Definition search.cc:633
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.
Definition search.cc:3661
std::string LocalSearchProfile() const
IntervalVar * MakeFixedDurationEndSyncedOnStartIntervalVar(IntervalVar *interval_var, int64_t duration, int64_t offset)
Definition interval.cc:2457
Constraint * MakeAllDifferentExcept(const std::vector< IntVar * > &vars, int64_t escape_value)
DecisionBuilder * MakePhase(const std::vector< IntVar * > &vars, IntVarStrategy var_str, IntValueStrategy val_str)
Definition search.cc:2140
IntVar * MakeIsGreaterCstVar(IntExpr *var, int64_t value)
status var of (var > value)
Definition expr_cst.cc:702
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)
Definition interval.cc:2299
Decision * MakeAssignVariableValue(IntVar *var, int64_t val)
Decisions.
Definition search.cc:1640
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)
Definition element.cc:869
Decision * MakeAssignVariablesValuesOrFail(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values)
Definition search.cc:1885
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)
Definition expr_cst.cc:822
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)
Definition diffn.cc:300
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)
Definition search.cc:1761
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 -------—
Definition table.cc:1259
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)
Definition interval.cc:2284
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
Definition range_cst.cc:552
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
Definition count_cst.cc:957
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)
Definition search.cc:4902
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).
Definition search.cc:3266
void MakeBoolVarArray(int var_count, const std::string &name, std::vector< IntVar * > *vars)
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.
Definition trace.cc:848
int64_t neighbors() const
The number of neighbors created.
Constraint * MakeIsDifferentCt(IntExpr *v1, IntExpr *v2, IntVar *b)
b == (v1 != v2)
Definition range_cst.cc:692
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
Definition range_cst.cc:566
DisjunctiveConstraint * MakeStrictDisjunctiveConstraint(const std::vector< IntervalVar * > &intervals, const std::string &name)
Definition resource.cc:2613
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)
Definition range_cst.cc:583
IntVar * MakeIsDifferentCstVar(IntExpr *var, int64_t value)
status var of (var != value)
Definition expr_cst.cc:586
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)
Definition search.cc:489
Constraint * MakeCount(const std::vector< IntVar * > &vars, int64_t value, int64_t max_count)
|{i | vars[i] == value}| == max_count
Definition count_cst.cc:33
@ CHOOSE_RANDOM
Randomly select one of the remaining unbound variables.
@ INT_VAR_DEFAULT
The default behavior is CHOOSE_FIRST_UNBOUND.
@ INT_VAR_SIMPLE
The simple selection is CHOOSE_FIRST_UNBOUND.
IntVar * MakeIsBetweenVar(IntExpr *v, int64_t l, int64_t u)
Definition expr_cst.cc:1093
Constraint * MakeElementEquality(const std::vector< int64_t > &vals, IntVar *index, IntVar *target)
Definition element.cc:1679
IntervalVar * MakeFixedInterval(int64_t start, int64_t duration, const std::string &name)
Creates a fixed and performed interval.
Definition interval.cc:2279
Pack * MakePack(const std::vector< IntVar * > &vars, int number_of_bins)
Definition pack.cc:1613
@ 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)
Definition search.cc:781
std::function< int64_t(int64_t, int64_t)> IndexEvaluator2
SolutionCollector * MakeAllSolutionCollector()
Definition search.cc:2964
DecisionBuilder * MakeDefaultPhase(const std::vector< IntVar * > &vars)
SequenceStrategy
Used for scheduling. Not yet implemented.
LocalSearchFilter * MakeRejectFilter()
IntervalVar * RegisterIntervalVar(IntervalVar *var)
Definition trace.cc:869
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)
Definition expr_cst.cc:685
Constraint * MakeMinEquality(const std::vector< IntVar * > &vars, IntVar *min_var)
Decision * MakeDecision(Action apply, Action refute)
Definition search.cc:691
Constraint * MakeIsLessCt(IntExpr *left, IntExpr *right, IntVar *b)
b == (left < right)
Definition range_cst.cc:779
ObjectiveMonitor * MakeLexicographicSimulatedAnnealing(const std::vector< bool > &maximize, std::vector< IntVar * > vars, std::vector< int64_t > steps, std::vector< int64_t > initial_temperatures)
Definition search.cc:3783
SolutionCollector * MakeFirstSolutionCollector()
Definition search.cc:2606
Constraint * MakeIndexOfConstraint(const std::vector< IntVar * > &vars, IntVar *index, int64_t target)
Definition element.cc:1742
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()
Definition search.cc:2658
ModelVisitor * MakeVariableDegreeVisitor(absl::flat_hash_map< const IntVar *, int > *map)
Compute the number of constraints a variable is attached to.
Definition utilities.cc:822
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.
@ kLast
Dummy event whose underlying int is the number of MonitorEvent enums.
std::function< void()> Closure
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)
Definition element.cc:1757
@ 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.
SolutionCollector * MakeBestLexicographicValueSolutionCollector(const Assignment *assignment, std::vector< bool > maximize)
Definition search.cc:2759
SearchMonitor * MakeExitSearchCallback(std::function< void()> callback)
Definition search.cc:539
LocalSearchOperator * MultiArmedBanditConcatenateOperators(const std::vector< LocalSearchOperator * > &ops, double memory_coefficient, double exploration_coefficient, bool maximize)
SearchMonitor * MakeSearchTrace(const std::string &prefix)
Definition search.cc:460
Decision * MakeAssignVariablesValues(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values)
Definition search.cc:1870
SolutionCollector * MakeNBestValueSolutionCollector(const Assignment *assignment, int solution_count, bool maximize)
Definition search.cc:2880
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
Definition range_cst.cc:518
IntervalVar * MakeIntervalRelaxedMax(IntervalVar *interval_var)
Definition interval.cc:2254
IntVar * MakeIsLessOrEqualVar(IntExpr *left, IntExpr *right)
status var of (left <= right)
Definition range_cst.cc:704
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)
Definition search.cc:3671
Assignment * MakeAssignment()
This method creates an empty assignment.
DecisionBuilder * MakeDecisionBuilderFromAssignment(Assignment *assignment, DecisionBuilder *db, const std::vector< IntVar * > &vars)
Definition search.cc:2325
ABSL_MUST_USE_RESULT RegularLimit * MakeBranchesLimit(int64_t branches)
Definition search.cc:4680
@ 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)
Definition search.cc:332
ObjectiveMonitor * MakeSimulatedAnnealing(bool maximize, IntVar *v, int64_t step, int64_t initial_temperature)
Definition search.cc:3776
Constraint * MakeLessOrEqual(IntExpr *left, IntExpr *right)
left <= right
Definition range_cst.cc:532
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)
Definition expr_cst.cc:706
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.
Definition search.cc:3258
void SetSearchContext(Search *search, absl::string_view search_context)
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)
Definition search.cc:4433
IntervalVar * MakeFixedDurationEndSyncedOnEndIntervalVar(IntervalVar *interval_var, int64_t duration, int64_t offset)
Definition interval.cc:2464
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 --—
Definition expr_cst.cc:929
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)
Definition search.cc:4708
OptimizeVar * MakeWeightedMaximize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64_t > &weights, int64_t step)
Creates a maximization weigthed objective.
Definition search.cc:3316
int64_t filtered_neighbors() const
The number of filtered neighbors (neighbors accepted by filters).
Decision * MakeAssignVariableValueOrDoNothing(IntVar *var, int64_t value)
Definition search.cc:1707
SolverState state() const
State of the solver.
SolutionCollector * MakeNBestLexicographicValueSolutionCollector(const Assignment *assignment, int solution_count, std::vector< bool > maximize)
Definition search.cc:2898
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.
Definition utilities.cc:814
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)
Definition search.cc:3680
void ReSeed(int32_t seed)
Reseed the solver random generator.
@ INTERVAL_DEFAULT
The default is INTERVAL_SET_TIMES_FORWARD.
@ 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.
IntervalVar * MakeFixedDurationStartSyncedOnStartIntervalVar(IntervalVar *interval_var, int64_t duration, int64_t offset)
Synced Interval Vars.
Definition interval.cc:2443
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)
Definition search.cc:3271
SearchMonitor * MakeSymmetryManager(const std::vector< SymmetryBreaker * > &visitors)
Symmetry Breaking.
Definition search.cc:5465
IntVar * MakeIsLessCstVar(IntExpr *var, int64_t value)
status var of (var < value)
Definition expr_cst.cc:802
IntervalVar * MakeIntervalRelaxedMin(IntervalVar *interval_var)
Definition interval.cc:2263
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.
Definition search.cc:4723
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)
Definition expr_cst.cc:1057
Constraint * MakeIsLessOrEqualCstCt(IntExpr *var, int64_t value, IntVar *boolvar)
boolvar == (var <= value)
Definition expr_cst.cc:806
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)
Definition table.cc:1272
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)
Definition expr_cst.cc:962
void AddLocalSearchMonitor(LocalSearchMonitor *monitor)
BaseObjectiveMonitor * MakeRoundRobinCompoundObjectiveMonitor(std::vector< BaseObjectiveMonitor * > monitors, int num_max_local_optima_before_metaheuristic_switch)
Definition search.cc:3068
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)
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.
Definition search.cc:3262
Constraint * MakeIsDifferentCstCt(IntExpr *var, int64_t value, IntVar *boolvar)
boolvar == (var != value)
Definition expr_cst.cc:595
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)
Definition search.cc:4893
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
Definition utilities.cc:818
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)
const bool DEBUG_MODE
Definition macros.h:26
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition map_util.h:190
const MapUtilMappedT< Collection > & FindWithDefault(const Collection &collection, const KeyType &key, const MapUtilMappedT< Collection > &value)
Definition map_util.h:36
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 Next()
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 heuristic_num_failures_limit
The failure limit for each heuristic that we run.
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.
static Iterator Begin(IntVarIterator *it)
These are the only way to construct an Iterator.
bool operator<(const SolutionData &other) const
Definition search.cc:2355
Creates a search monitor from logging parameters.
---------------— StateMarker / StateInfo struct --------—
CycleTimer SimpleCycleTimer
Definition timer.h:81
static const int64_t kint64max
Definition types.h:32