63 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
64 #define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
74 #include "absl/container/flat_hash_map.h"
75 #include "absl/container/flat_hash_set.h"
76 #include "absl/random/distributions.h"
77 #include "absl/random/random.h"
78 #include "absl/strings/str_format.h"
79 #include "ortools/base/commandlineflags.h"
80 #include "ortools/base/hash.h"
81 #include "ortools/base/integral_types.h"
82 #include "ortools/base/logging.h"
83 #include "ortools/base/macros.h"
84 #include "ortools/base/map_util.h"
85 #include "ortools/base/sysinfo.h"
86 #include "ortools/base/timer.h"
88 #include "ortools/util/piecewise_linear_function.h"
89 #include "ortools/util/sorted_interval_list.h"
90 #include "ortools/util/tuple_set.h"
94 #endif // !defined(SWIG)
101 class AssignmentProto;
105 class CpIntegerExpression;
106 class CpIntervalVariable;
107 class CpSequenceVariable;
108 class CastConstraint;
111 class DecisionBuilder;
112 class DecisionVisitor;
115 class LocalSearchProfiler;
117 class DisjunctiveConstraint;
118 class ExpressionCache;
122 class IntVarAssignment;
125 class IntervalVarAssignment;
126 class IntervalVarElement;
127 class IntVarLocalSearchFilter;
128 class LocalSearchFilter;
129 class LocalSearchOperator;
130 class LocalSearchPhaseParameters;
135 class PropagationBaseObject;
136 class PropagationMonitor;
137 class LocalSearchMonitor;
142 class RegularLimitParameters;
147 class SequenceVarAssignment;
148 class SolutionCollector;
151 class ConstraintSolverParameters;
152 class SymmetryBreaker;
158 inline int64 CpRandomSeed() {
159 return FLAGS_cp_random_seed == -1
160 ? absl::Uniform<int64>(absl::BitGen(), 0, kint64max)
161 : FLAGS_cp_random_seed;
167 struct DefaultPhaseParameters {
169 enum VariableSelection {
170 CHOOSE_MAX_SUM_IMPACT = 0,
171 CHOOSE_MAX_AVERAGE_IMPACT = 1,
172 CHOOSE_MAX_VALUE_IMPACT = 2,
175 enum ValueSelection {
176 SELECT_MIN_IMPACT = 0,
177 SELECT_MAX_IMPACT = 1,
180 enum DisplayLevel { NONE = 0, NORMAL = 1, VERBOSE = 2 };
184 VariableSelection var_selection_schema;
187 ValueSelection value_selection_schema;
191 int initialization_splits;
196 bool run_all_heuristics;
201 int heuristic_period;
204 int heuristic_num_failures_limit;
208 bool persistent_impact;
215 DisplayLevel display_level;
218 bool use_last_conflict;
221 DecisionBuilder* decision_builder;
223 DefaultPhaseParameters();
249 struct IntegerCastInfo {
251 : variable(nullptr), expression(nullptr), maintainer(nullptr) {}
252 IntegerCastInfo(IntVar*
const v, IntExpr*
const e, Constraint*
const c)
253 : variable(v), expression(e), maintainer(c) {}
256 Constraint* maintainer;
260 static const int kNumPriorities = 3;
264 enum IntVarStrategy {
274 CHOOSE_FIRST_UNBOUND,
285 CHOOSE_MIN_SIZE_LOWEST_MIN,
293 CHOOSE_MIN_SIZE_HIGHEST_MIN,
301 CHOOSE_MIN_SIZE_LOWEST_MAX,
309 CHOOSE_MIN_SIZE_HIGHEST_MAX,
335 CHOOSE_MAX_REGRET_ON_MIN,
345 enum IntValueStrategy {
385 enum EvaluatorStrategy {
390 CHOOSE_STATIC_GLOBAL_BEST,
396 CHOOSE_DYNAMIC_GLOBAL_BEST,
400 enum SequenceStrategy {
403 CHOOSE_MIN_SLACK_RANK_FORWARD,
404 CHOOSE_RANDOM_RANK_FORWARD,
409 enum IntervalStrategy {
416 INTERVAL_SET_TIMES_FORWARD,
419 INTERVAL_SET_TIMES_BACKWARD
424 enum LocalSearchOperators {
562 enum EvaluatorLocalSearchOperators {
590 enum LocalSearchFilterBound {
606 DELAYED_PRIORITY = 0,
617 enum BinaryIntervalRelation {
650 enum UnaryIntervalRelation {
685 enum DecisionModification {
711 enum MarkerType { SENTINEL, SIMPLE_MARKER, CHOICE_POINT, REVERSIBLE_ACTION };
730 enum OptimizationDirection { NOT_SET, MAXIMIZATION, MINIMIZATION };
733 typedef std::function<int64(int64)> IndexEvaluator1;
734 typedef std::function<int64(int64, int64)> IndexEvaluator2;
735 typedef std::function<int64(int64, int64, int64)> IndexEvaluator3;
737 typedef std::function<bool(int64)> IndexFilter1;
739 typedef std::function<IntVar*(int64)> Int64ToIntVar;
741 typedef std::function<int64(Solver* solver,
const std::vector<IntVar*>& vars,
742 int64 first_unbound, int64 last_unbound)>
743 VariableIndexSelector;
745 typedef std::function<int64(
const IntVar* v, int64
id)> VariableValueSelector;
746 typedef std::function<bool(int64, int64, int64)> VariableValueComparator;
747 typedef std::function<DecisionModification()> BranchSelector;
749 typedef std::function<void(Solver*)> Action;
750 typedef std::function<void()> Closure;
753 explicit Solver(
const std::string& name);
754 Solver(
const std::string& name,
const ConstraintSolverParameters& parameters);
758 ConstraintSolverParameters parameters()
const {
return parameters_; }
761 static ConstraintSolverParameters DefaultSolverParameters();
769 void SaveValue(T* o) {
770 InternalSaveValue(o);
785 template <
typename T>
786 T* RevAlloc(T*
object) {
787 return reinterpret_cast<T*
>(SafeRevAlloc(
object));
796 template <
typename T>
797 T* RevAllocArray(T*
object) {
798 return reinterpret_cast<T*
>(SafeRevAllocArray(
object));
834 void AddConstraint(Constraint*
const c);
838 void AddCastConstraint(CastConstraint*
const constraint,
839 IntVar*
const target_var, IntExpr*
const expr);
882 bool Solve(DecisionBuilder*
const db,
883 const std::vector<SearchMonitor*>& monitors);
884 bool Solve(DecisionBuilder*
const db);
885 bool Solve(DecisionBuilder*
const db, SearchMonitor*
const m1);
886 bool Solve(DecisionBuilder*
const db, SearchMonitor*
const m1,
887 SearchMonitor*
const m2);
888 bool Solve(DecisionBuilder*
const db, SearchMonitor*
const m1,
889 SearchMonitor*
const m2, SearchMonitor*
const m3);
890 bool Solve(DecisionBuilder*
const db, SearchMonitor*
const m1,
891 SearchMonitor*
const m2, SearchMonitor*
const m3,
892 SearchMonitor*
const m4);
904 void NewSearch(DecisionBuilder*
const db,
905 const std::vector<SearchMonitor*>& monitors);
906 void NewSearch(DecisionBuilder*
const db);
907 void NewSearch(DecisionBuilder*
const db, SearchMonitor*
const m1);
908 void NewSearch(DecisionBuilder*
const db, SearchMonitor*
const m1,
909 SearchMonitor*
const m2);
910 void NewSearch(DecisionBuilder*
const db, SearchMonitor*
const m1,
911 SearchMonitor*
const m2, SearchMonitor*
const m3);
912 void NewSearch(DecisionBuilder*
const db, SearchMonitor*
const m1,
913 SearchMonitor*
const m2, SearchMonitor*
const m3,
914 SearchMonitor*
const m4);
917 void RestartSearch();
929 bool SolveAndCommit(DecisionBuilder*
const db,
930 const std::vector<SearchMonitor*>& monitors);
931 bool SolveAndCommit(DecisionBuilder*
const db);
932 bool SolveAndCommit(DecisionBuilder*
const db, SearchMonitor*
const m1);
933 bool SolveAndCommit(DecisionBuilder*
const db, SearchMonitor*
const m1,
934 SearchMonitor*
const m2);
935 bool SolveAndCommit(DecisionBuilder*
const db, SearchMonitor*
const m1,
936 SearchMonitor*
const m2, SearchMonitor*
const m3);
939 bool CheckAssignment(Assignment*
const solution);
944 bool CheckConstraint(Constraint*
const ct);
947 SolverState state()
const {
return state_; }
953 void AddBacktrackAction(Action a,
bool fast);
960 std::string DebugString()
const;
964 static int64 MemoryUsage();
970 absl::Time Now()
const;
974 int64 wall_time()
const;
977 int64 branches()
const {
return branches_; }
980 int64 solutions()
const;
983 int64 unchecked_solutions()
const;
986 int64 demon_runs(DemonPriority p)
const {
return demon_runs_[p]; }
989 int64 failures()
const {
return fails_; }
992 int64 neighbors()
const {
return neighbors_; }
995 int64 filtered_neighbors()
const {
return filtered_neighbors_; }
998 int64 accepted_neighbors()
const {
return accepted_neighbors_; }
1002 uint64 stamp()
const;
1005 uint64 fail_stamp()
const;
1008 OptimizationDirection optimization_direction()
const {
1009 return optimization_direction_;
1011 void set_optimization_direction(OptimizationDirection direction) {
1012 optimization_direction_ = direction;
1024 IntVar* MakeIntVar(int64 min, int64 max,
const std::string& name);
1027 IntVar* MakeIntVar(
const std::vector<int64>& values,
const std::string& name);
1030 IntVar* MakeIntVar(
const std::vector<int>& values,
const std::string& name);
1033 IntVar* MakeIntVar(int64 min, int64 max);
1036 IntVar* MakeIntVar(
const std::vector<int64>& values);
1039 IntVar* MakeIntVar(
const std::vector<int>& values);
1042 IntVar* MakeBoolVar(
const std::string& name);
1045 IntVar* MakeBoolVar();
1048 IntVar* MakeIntConst(int64 val,
const std::string& name);
1051 IntVar* MakeIntConst(int64 val);
1056 void MakeIntVarArray(
int var_count, int64 vmin, int64 vmax,
1057 const std::string& name, std::vector<IntVar*>* vars);
1060 void MakeIntVarArray(
int var_count, int64 vmin, int64 vmax,
1061 std::vector<IntVar*>* vars);
1063 IntVar** MakeIntVarArray(
int var_count, int64 vmin, int64 vmax,
1064 const std::string& name);
1069 void MakeBoolVarArray(
int var_count,
const std::string& name,
1070 std::vector<IntVar*>* vars);
1073 void MakeBoolVarArray(
int var_count, std::vector<IntVar*>* vars);
1075 IntVar** MakeBoolVarArray(
int var_count,
const std::string& name);
1080 IntExpr* MakeSum(IntExpr*
const left, IntExpr*
const right);
1082 IntExpr* MakeSum(IntExpr*
const expr, int64 value);
1084 IntExpr* MakeSum(
const std::vector<IntVar*>& vars);
1087 IntExpr* MakeScalProd(
const std::vector<IntVar*>& vars,
1088 const std::vector<int64>& coefs);
1090 IntExpr* MakeScalProd(
const std::vector<IntVar*>& vars,
1091 const std::vector<int>& coefs);
1094 IntExpr* MakeDifference(IntExpr*
const left, IntExpr*
const right);
1096 IntExpr* MakeDifference(int64 value, IntExpr*
const expr);
1098 IntExpr* MakeOpposite(IntExpr*
const expr);
1101 IntExpr* MakeProd(IntExpr*
const left, IntExpr*
const right);
1103 IntExpr* MakeProd(IntExpr*
const expr, int64 value);
1106 IntExpr* MakeDiv(IntExpr*
const expr, int64 value);
1108 IntExpr* MakeDiv(IntExpr*
const numerator, IntExpr*
const denominator);
1111 IntExpr* MakeAbs(IntExpr*
const expr);
1113 IntExpr* MakeSquare(IntExpr*
const expr);
1115 IntExpr* MakePower(IntExpr*
const expr, int64 n);
1118 IntExpr* MakeElement(
const std::vector<int64>& values, IntVar*
const index);
1120 IntExpr* MakeElement(
const std::vector<int>& values, IntVar*
const index);
1125 IntExpr* MakeElement(IndexEvaluator1 values, IntVar*
const index);
1132 IntExpr* MakeMonotonicElement(IndexEvaluator1 values,
bool increasing,
1133 IntVar*
const index);
1135 IntExpr* MakeElement(IndexEvaluator2 values, IntVar*
const index1,
1136 IntVar*
const index2);
1139 IntExpr* MakeElement(
const std::vector<IntVar*>& vars, IntVar*
const index);
1142 IntExpr* MakeElement(Int64ToIntVar vars, int64 range_start, int64 range_end,
1149 IntExpr* MakeIndexExpression(
const std::vector<IntVar*>& vars, int64 value);
1152 Constraint* MakeIfThenElseCt(IntVar*
const condition,
1153 IntExpr*
const then_expr,
1154 IntExpr*
const else_expr,
1155 IntVar*
const target_var);
1158 IntExpr* MakeMin(
const std::vector<IntVar*>& vars);
1160 IntExpr* MakeMin(IntExpr*
const left, IntExpr*
const right);
1162 IntExpr* MakeMin(IntExpr*
const expr, int64 value);
1164 IntExpr* MakeMin(IntExpr*
const expr,
int value);
1167 IntExpr* MakeMax(
const std::vector<IntVar*>& vars);
1169 IntExpr* MakeMax(IntExpr*
const left, IntExpr*
const right);
1171 IntExpr* MakeMax(IntExpr*
const expr, int64 value);
1173 IntExpr* MakeMax(IntExpr*
const expr,
int value);
1176 IntExpr* MakeConvexPiecewiseExpr(IntExpr* expr, int64 early_cost,
1177 int64 early_date, int64 late_date,
1182 IntExpr* MakeSemiContinuousExpr(IntExpr*
const expr, int64 fixed_charge,
1190 IntExpr* MakePiecewiseLinearExpr(IntExpr* expr,
1191 const PiecewiseLinearFunction& f);
1195 IntExpr* MakeModulo(IntExpr*
const x, int64 mod);
1198 IntExpr* MakeModulo(IntExpr*
const x, IntExpr*
const mod);
1201 IntExpr* MakeConditionalExpression(IntVar*
const condition,
1202 IntExpr*
const expr,
1203 int64 unperformed_value);
1206 Constraint* MakeTrueConstraint();
1208 Constraint* MakeFalseConstraint();
1209 Constraint* MakeFalseConstraint(
const std::string& explanation);
1212 Constraint* MakeIsEqualCstCt(IntExpr*
const var, int64 value,
1213 IntVar*
const boolvar);
1215 IntVar* MakeIsEqualCstVar(IntExpr*
const var, int64 value);
1217 Constraint* MakeIsEqualCt(IntExpr*
const v1, IntExpr* v2, IntVar*
const b);
1219 IntVar* MakeIsEqualVar(IntExpr*
const v1, IntExpr* v2);
1221 Constraint* MakeEquality(IntExpr*
const left, IntExpr*
const right);
1223 Constraint* MakeEquality(IntExpr*
const expr, int64 value);
1225 Constraint* MakeEquality(IntExpr*
const expr,
int value);
1228 Constraint* MakeIsDifferentCstCt(IntExpr*
const var, int64 value,
1229 IntVar*
const boolvar);
1231 IntVar* MakeIsDifferentCstVar(IntExpr*
const var, int64 value);
1233 IntVar* MakeIsDifferentVar(IntExpr*
const v1, IntExpr*
const v2);
1235 Constraint* MakeIsDifferentCt(IntExpr*
const v1, IntExpr*
const v2,
1238 Constraint* MakeNonEquality(IntExpr*
const left, IntExpr*
const right);
1240 Constraint* MakeNonEquality(IntExpr*
const expr, int64 value);
1242 Constraint* MakeNonEquality(IntExpr*
const expr,
int value);
1245 Constraint* MakeIsLessOrEqualCstCt(IntExpr*
const var, int64 value,
1246 IntVar*
const boolvar);
1248 IntVar* MakeIsLessOrEqualCstVar(IntExpr*
const var, int64 value);
1250 IntVar* MakeIsLessOrEqualVar(IntExpr*
const left, IntExpr*
const right);
1252 Constraint* MakeIsLessOrEqualCt(IntExpr*
const left, IntExpr*
const right,
1255 Constraint* MakeLessOrEqual(IntExpr*
const left, IntExpr*
const right);
1257 Constraint* MakeLessOrEqual(IntExpr*
const expr, int64 value);
1259 Constraint* MakeLessOrEqual(IntExpr*
const expr,
int value);
1262 Constraint* MakeIsGreaterOrEqualCstCt(IntExpr*
const var, int64 value,
1263 IntVar*
const boolvar);
1265 IntVar* MakeIsGreaterOrEqualCstVar(IntExpr*
const var, int64 value);
1267 IntVar* MakeIsGreaterOrEqualVar(IntExpr*
const left, IntExpr*
const right);
1269 Constraint* MakeIsGreaterOrEqualCt(IntExpr*
const left, IntExpr*
const right,
1272 Constraint* MakeGreaterOrEqual(IntExpr*
const left, IntExpr*
const right);
1274 Constraint* MakeGreaterOrEqual(IntExpr*
const expr, int64 value);
1276 Constraint* MakeGreaterOrEqual(IntExpr*
const expr,
int value);
1279 Constraint* MakeIsGreaterCstCt(IntExpr*
const v, int64 c, IntVar*
const b);
1281 IntVar* MakeIsGreaterCstVar(IntExpr*
const var, int64 value);
1283 IntVar* MakeIsGreaterVar(IntExpr*
const left, IntExpr*
const right);
1285 Constraint* MakeIsGreaterCt(IntExpr*
const left, IntExpr*
const right,
1288 Constraint* MakeGreater(IntExpr*
const left, IntExpr*
const right);
1290 Constraint* MakeGreater(IntExpr*
const expr, int64 value);
1292 Constraint* MakeGreater(IntExpr*
const expr,
int value);
1295 Constraint* MakeIsLessCstCt(IntExpr*
const v, int64 c, IntVar*
const b);
1297 IntVar* MakeIsLessCstVar(IntExpr*
const var, int64 value);
1299 IntVar* MakeIsLessVar(IntExpr*
const left, IntExpr*
const right);
1301 Constraint* MakeIsLessCt(IntExpr*
const left, IntExpr*
const right,
1304 Constraint* MakeLess(IntExpr*
const left, IntExpr*
const right);
1306 Constraint* MakeLess(IntExpr*
const expr, int64 value);
1308 Constraint* MakeLess(IntExpr*
const expr,
int value);
1311 Constraint* MakeSumLessOrEqual(
const std::vector<IntVar*>& vars, int64 cst);
1312 Constraint* MakeSumGreaterOrEqual(
const std::vector<IntVar*>& vars,
1314 Constraint* MakeSumEquality(
const std::vector<IntVar*>& vars, int64 cst);
1315 Constraint* MakeSumEquality(
const std::vector<IntVar*>& vars,
1317 Constraint* MakeScalProdEquality(
const std::vector<IntVar*>& vars,
1318 const std::vector<int64>& coefficients,
1320 Constraint* MakeScalProdEquality(
const std::vector<IntVar*>& vars,
1321 const std::vector<int>& coefficients,
1323 Constraint* MakeScalProdEquality(
const std::vector<IntVar*>& vars,
1324 const std::vector<int64>& coefficients,
1325 IntVar*
const target);
1326 Constraint* MakeScalProdEquality(
const std::vector<IntVar*>& vars,
1327 const std::vector<int>& coefficients,
1328 IntVar*
const target);
1329 Constraint* MakeScalProdGreaterOrEqual(
const std::vector<IntVar*>& vars,
1330 const std::vector<int64>& coeffs,
1332 Constraint* MakeScalProdGreaterOrEqual(
const std::vector<IntVar*>& vars,
1333 const std::vector<int>& coeffs,
1335 Constraint* MakeScalProdLessOrEqual(
const std::vector<IntVar*>& vars,
1336 const std::vector<int64>& coefficients,
1338 Constraint* MakeScalProdLessOrEqual(
const std::vector<IntVar*>& vars,
1339 const std::vector<int>& coefficients,
1342 Constraint* MakeMinEquality(
const std::vector<IntVar*>& vars,
1343 IntVar*
const min_var);
1344 Constraint* MakeMaxEquality(
const std::vector<IntVar*>& vars,
1345 IntVar*
const max_var);
1347 Constraint* MakeElementEquality(
const std::vector<int64>& vals,
1348 IntVar*
const index, IntVar*
const target);
1349 Constraint* MakeElementEquality(
const std::vector<int>& vals,
1350 IntVar*
const index, IntVar*
const target);
1351 Constraint* MakeElementEquality(
const std::vector<IntVar*>& vars,
1352 IntVar*
const index, IntVar*
const target);
1353 Constraint* MakeElementEquality(
const std::vector<IntVar*>& vars,
1354 IntVar*
const index, int64 target);
1356 Constraint* MakeAbsEquality(IntVar*
const var, IntVar*
const abs_var);
1361 Constraint* MakeIndexOfConstraint(
const std::vector<IntVar*>& vars,
1362 IntVar*
const index, int64 target);
1366 Demon* MakeConstraintInitialPropagateCallback(Constraint*
const ct);
1370 Demon* MakeDelayedConstraintInitialPropagateCallback(Constraint*
const ct);
1372 Demon* MakeActionDemon(Action action);
1375 Demon* MakeClosureDemon(Closure closure);
1381 Constraint* MakeBetweenCt(IntExpr*
const expr, int64 l, int64 u);
1387 Constraint* MakeNotBetweenCt(IntExpr*
const expr, int64 l, int64 u);
1390 Constraint* MakeIsBetweenCt(IntExpr*
const expr, int64 l, int64 u,
1392 IntVar* MakeIsBetweenVar(IntExpr*
const v, int64 l, int64 u);
1398 Constraint* MakeMemberCt(IntExpr*
const expr,
1399 const std::vector<int64>& values);
1400 Constraint* MakeMemberCt(IntExpr*
const expr,
const std::vector<int>& values);
1403 Constraint* MakeNotMemberCt(IntExpr*
const expr,
1404 const std::vector<int64>& values);
1405 Constraint* MakeNotMemberCt(IntExpr*
const expr,
1406 const std::vector<int>& values);
1409 Constraint* MakeNotMemberCt(IntExpr*
const expr, std::vector<int64> starts,
1410 std::vector<int64> ends);
1412 Constraint* MakeNotMemberCt(IntExpr*
const expr, std::vector<int> starts,
1413 std::vector<int> ends);
1415 Constraint* MakeNotMemberCt(IntExpr* expr,
1417 SortedDisjointIntervalList intervals);
1418 #endif // !defined(SWIG)
1421 Constraint* MakeIsMemberCt(IntExpr*
const expr,
1422 const std::vector<int64>& values,
1423 IntVar*
const boolvar);
1424 Constraint* MakeIsMemberCt(IntExpr*
const expr,
1425 const std::vector<int>& values,
1426 IntVar*
const boolvar);
1427 IntVar* MakeIsMemberVar(IntExpr*
const expr,
1428 const std::vector<int64>& values);
1429 IntVar* MakeIsMemberVar(IntExpr*
const expr,
const std::vector<int>& values);
1432 Constraint* MakeAtMost(std::vector<IntVar*> vars, int64 value,
1435 Constraint* MakeCount(
const std::vector<IntVar*>& vars, int64 value,
1438 Constraint* MakeCount(
const std::vector<IntVar*>& vars, int64 value,
1439 IntVar*
const max_count);
1442 Constraint* MakeDistribute(
const std::vector<IntVar*>& vars,
1443 const std::vector<int64>& values,
1444 const std::vector<IntVar*>& cards);
1446 Constraint* MakeDistribute(
const std::vector<IntVar*>& vars,
1447 const std::vector<int>& values,
1448 const std::vector<IntVar*>& cards);
1450 Constraint* MakeDistribute(
const std::vector<IntVar*>& vars,
1451 const std::vector<IntVar*>& cards);
1454 Constraint* MakeDistribute(
const std::vector<IntVar*>& vars, int64 card_min,
1455 int64 card_max, int64 card_size);
1459 Constraint* MakeDistribute(
const std::vector<IntVar*>& vars,
1460 const std::vector<int64>& card_min,
1461 const std::vector<int64>& card_max);
1465 Constraint* MakeDistribute(
const std::vector<IntVar*>& vars,
1466 const std::vector<int>& card_min,
1467 const std::vector<int>& card_max);
1471 Constraint* MakeDistribute(
const std::vector<IntVar*>& vars,
1472 const std::vector<int64>& values,
1473 const std::vector<int64>& card_min,
1474 const std::vector<int64>& card_max);
1478 Constraint* MakeDistribute(
const std::vector<IntVar*>& vars,
1479 const std::vector<int>& values,
1480 const std::vector<int>& card_min,
1481 const std::vector<int>& card_max);
1487 Constraint* MakeDeviation(
const std::vector<IntVar*>& vars,
1488 IntVar*
const deviation_var, int64 total_sum);
1492 Constraint* MakeAllDifferent(
const std::vector<IntVar*>& vars);
1497 Constraint* MakeAllDifferent(
const std::vector<IntVar*>& vars,
1498 bool stronger_propagation);
1502 Constraint* MakeAllDifferentExcept(
const std::vector<IntVar*>& vars,
1503 int64 escape_value);
1521 Constraint* MakeSortingConstraint(
const std::vector<IntVar*>& vars,
1522 const std::vector<IntVar*>& sorted);
1529 Constraint* MakeLexicalLess(
const std::vector<IntVar*>& left,
1530 const std::vector<IntVar*>& right);
1534 Constraint* MakeLexicalLessOrEqual(
const std::vector<IntVar*>& left,
1535 const std::vector<IntVar*>& right);
1541 Constraint* MakeInversePermutationConstraint(
1542 const std::vector<IntVar*>& left,
const std::vector<IntVar*>& right);
1546 Constraint* MakeIndexOfFirstMaxValueConstraint(
1547 IntVar* index,
const std::vector<IntVar*>& vars);
1551 Constraint* MakeIndexOfFirstMinValueConstraint(
1552 IntVar* index,
const std::vector<IntVar*>& vars);
1558 Constraint* MakeNullIntersect(
const std::vector<IntVar*>& first_vars,
1559 const std::vector<IntVar*>& second_vars);
1566 Constraint* MakeNullIntersectExcept(
const std::vector<IntVar*>& first_vars,
1567 const std::vector<IntVar*>& second_vars,
1568 int64 escape_value);
1582 Constraint* MakeNoCycle(
const std::vector<IntVar*>& nexts,
1583 const std::vector<IntVar*>& active,
1584 IndexFilter1 sink_handler =
nullptr);
1585 Constraint* MakeNoCycle(
const std::vector<IntVar*>& nexts,
1586 const std::vector<IntVar*>& active,
1587 IndexFilter1 sink_handler,
bool assume_paths);
1590 Constraint* MakeCircuit(
const std::vector<IntVar*>& nexts);
1594 Constraint* MakeSubCircuit(
const std::vector<IntVar*>& nexts);
1600 Constraint* MakePathCumul(
const std::vector<IntVar*>& nexts,
1601 const std::vector<IntVar*>& active,
1602 const std::vector<IntVar*>& cumuls,
1603 const std::vector<IntVar*>& transits);
1607 Constraint* MakeDelayedPathCumul(
const std::vector<IntVar*>& nexts,
1608 const std::vector<IntVar*>& active,
1609 const std::vector<IntVar*>& cumuls,
1610 const std::vector<IntVar*>& transits);
1617 Constraint* MakePathCumul(
const std::vector<IntVar*>& nexts,
1618 const std::vector<IntVar*>& active,
1619 const std::vector<IntVar*>& cumuls,
1620 IndexEvaluator2 transit_evaluator);
1628 Constraint* MakePathCumul(
const std::vector<IntVar*>& nexts,
1629 const std::vector<IntVar*>& active,
1630 const std::vector<IntVar*>& cumuls,
1631 const std::vector<IntVar*>& slacks,
1632 IndexEvaluator2 transit_evaluator);
1637 Constraint* MakePathConnected(std::vector<IntVar*> nexts,
1638 std::vector<int64> sources,
1639 std::vector<int64> sinks,
1640 std::vector<IntVar*> status);
1647 Constraint* MakePathPrecedenceConstraint(
1648 std::vector<IntVar*> nexts,
1649 const std::vector<std::pair<int, int>>& precedences);
1658 Constraint* MakePathPrecedenceConstraint(
1659 std::vector<IntVar*> nexts,
1660 const std::vector<std::pair<int, int>>& precedences,
1661 const std::vector<int>& lifo_path_starts,
1662 const std::vector<int>& fifo_path_starts);
1665 Constraint* MakePathTransitPrecedenceConstraint(
1666 std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1667 const std::vector<std::pair<int, int>>& precedences);
1669 Constraint* MakeMapDomain(IntVar*
const var,
1673 const std::vector<IntVar*>& actives);
1679 Constraint* MakeAllowedAssignments(
const std::vector<IntVar*>& vars,
1680 const IntTupleSet& tuples);
1689 Constraint* MakeTransitionConstraint(
const std::vector<IntVar*>& vars,
1690 const IntTupleSet& transition_table,
1691 int64 initial_state,
1692 const std::vector<int64>& final_states);
1701 Constraint* MakeTransitionConstraint(
const std::vector<IntVar*>& vars,
1702 const IntTupleSet& transition_table,
1703 int64 initial_state,
1704 const std::vector<int>& final_states);
1706 #if defined(SWIGPYTHON)
1707 Constraint* MakeAllowedAssignments(
1709 const std::vector<IntVar*>& vars,
1710 const std::vector<std::vector<int64>>& raw_tuples) {
1711 IntTupleSet tuples(vars.size());
1712 tuples.InsertAll(raw_tuples);
1713 return MakeAllowedAssignments(vars, tuples);
1716 Constraint* MakeTransitionConstraint(
1717 const std::vector<IntVar*>& vars,
1718 const std::vector<std::vector<int64>>& raw_transitions,
1719 int64 initial_state,
const std::vector<int>& final_states) {
1720 IntTupleSet transitions(3);
1721 transitions.InsertAll(raw_transitions);
1722 return MakeTransitionConstraint(vars, transitions, initial_state,
1735 Constraint* MakeNonOverlappingBoxesConstraint(
1736 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1737 const std::vector<IntVar*>& x_size,
const std::vector<IntVar*>& y_size);
1738 Constraint* MakeNonOverlappingBoxesConstraint(
1739 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1740 const std::vector<int64>& x_size,
const std::vector<int64>& y_size);
1741 Constraint* MakeNonOverlappingBoxesConstraint(
1742 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1743 const std::vector<int>& x_size,
const std::vector<int>& y_size);
1753 Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
1754 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1755 const std::vector<IntVar*>& x_size,
const std::vector<IntVar*>& y_size);
1756 Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
1757 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1758 const std::vector<int64>& x_size,
const std::vector<int64>& y_size);
1759 Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
1760 const std::vector<IntVar*>& x_vars,
const std::vector<IntVar*>& y_vars,
1761 const std::vector<int>& x_size,
const std::vector<int>& y_size);
1768 Pack* MakePack(
const std::vector<IntVar*>& vars,
int number_of_bins);
1774 IntervalVar* MakeFixedDurationIntervalVar(int64 start_min, int64 start_max,
1775 int64 duration,
bool optional,
1776 const std::string& name);
1780 void MakeFixedDurationIntervalVarArray(
1781 int count, int64 start_min, int64 start_max, int64 duration,
1782 bool optional,
const std::string& name,
1783 std::vector<IntervalVar*>*
const array);
1787 IntervalVar* MakeFixedDurationIntervalVar(IntVar*
const start_variable,
1789 const std::string& name);
1793 IntervalVar* MakeFixedDurationIntervalVar(IntVar*
const start_variable,
1795 IntVar*
const performed_variable,
1796 const std::string& name);
1800 void MakeFixedDurationIntervalVarArray(
1801 const std::vector<IntVar*>& start_variables, int64 duration,
1802 const std::string& name, std::vector<IntervalVar*>*
const array);
1806 void MakeFixedDurationIntervalVarArray(
1807 const std::vector<IntVar*>& start_variables,
1808 const std::vector<int64>& durations,
const std::string& name,
1809 std::vector<IntervalVar*>*
const array);
1812 void MakeFixedDurationIntervalVarArray(
1813 const std::vector<IntVar*>& start_variables,
1814 const std::vector<int>& durations,
const std::string& name,
1815 std::vector<IntervalVar*>*
const array);
1819 void MakeFixedDurationIntervalVarArray(
1820 const std::vector<IntVar*>& start_variables,
1821 const std::vector<int64>& durations,
1822 const std::vector<IntVar*>& performed_variables,
const std::string& name,
1823 std::vector<IntervalVar*>*
const array);
1827 void MakeFixedDurationIntervalVarArray(
1828 const std::vector<IntVar*>& start_variables,
1829 const std::vector<int>& durations,
1830 const std::vector<IntVar*>& performed_variables,
const std::string& name,
1831 std::vector<IntervalVar*>*
const array);
1834 IntervalVar* MakeFixedInterval(int64 start, int64 duration,
1835 const std::string& name);
1839 IntervalVar* MakeIntervalVar(int64 start_min, int64 start_max,
1840 int64 duration_min, int64 duration_max,
1841 int64 end_min, int64 end_max,
bool optional,
1842 const std::string& name);
1846 void MakeIntervalVarArray(
int count, int64 start_min, int64 start_max,
1847 int64 duration_min, int64 duration_max,
1848 int64 end_min, int64 end_max,
bool optional,
1849 const std::string& name,
1850 std::vector<IntervalVar*>*
const array);
1854 IntervalVar* MakeMirrorInterval(IntervalVar*
const interval_var);
1860 IntervalVar* MakeFixedDurationStartSyncedOnStartIntervalVar(
1861 IntervalVar*
const interval_var, int64 duration, int64 offset);
1867 IntervalVar* MakeFixedDurationStartSyncedOnEndIntervalVar(
1868 IntervalVar*
const interval_var, int64 duration, int64 offset);
1874 IntervalVar* MakeFixedDurationEndSyncedOnStartIntervalVar(
1875 IntervalVar*
const interval_var, int64 duration, int64 offset);
1881 IntervalVar* MakeFixedDurationEndSyncedOnEndIntervalVar(
1882 IntervalVar*
const interval_var, int64 duration, int64 offset);
1901 IntervalVar* MakeIntervalRelaxedMin(IntervalVar*
const interval_var);
1920 IntervalVar* MakeIntervalRelaxedMax(IntervalVar*
const interval_var);
1924 Constraint* MakeIntervalVarRelation(IntervalVar*
const t,
1925 UnaryIntervalRelation r, int64 d);
1928 Constraint* MakeIntervalVarRelation(IntervalVar*
const t1,
1929 BinaryIntervalRelation r,
1930 IntervalVar*
const t2);
1936 Constraint* MakeIntervalVarRelationWithDelay(IntervalVar*
const t1,
1937 BinaryIntervalRelation r,
1938 IntervalVar*
const t2,
1944 Constraint* MakeTemporalDisjunction(IntervalVar*
const t1,
1945 IntervalVar*
const t2, IntVar*
const alt);
1949 Constraint* MakeTemporalDisjunction(IntervalVar*
const t1,
1950 IntervalVar*
const t2);
1954 DisjunctiveConstraint* MakeDisjunctiveConstraint(
1955 const std::vector<IntervalVar*>& intervals,
const std::string& name);
1960 DisjunctiveConstraint* MakeStrictDisjunctiveConstraint(
1961 const std::vector<IntervalVar*>& intervals,
const std::string& name);
1972 Constraint* MakeCumulative(
const std::vector<IntervalVar*>& intervals,
1973 const std::vector<int64>& demands, int64 capacity,
1974 const std::string& name);
1985 Constraint* MakeCumulative(
const std::vector<IntervalVar*>& intervals,
1986 const std::vector<int>& demands, int64 capacity,
1987 const std::string& name);
1998 Constraint* MakeCumulative(
const std::vector<IntervalVar*>& intervals,
1999 const std::vector<int64>& demands,
2000 IntVar*
const capacity,
const std::string& name);
2011 Constraint* MakeCumulative(
const std::vector<IntervalVar*>& intervals,
2012 const std::vector<int>& demands,
2013 IntVar*
const capacity,
const std::string& name);
2022 Constraint* MakeCumulative(
const std::vector<IntervalVar*>& intervals,
2023 const std::vector<IntVar*>& demands,
2024 int64 capacity,
const std::string& name);
2033 Constraint* MakeCumulative(
const std::vector<IntervalVar*>& intervals,
2034 const std::vector<IntVar*>& demands,
2035 IntVar*
const capacity,
const std::string& name);
2042 Constraint* MakeCover(
const std::vector<IntervalVar*>& vars,
2043 IntervalVar*
const target_var);
2046 Constraint* MakeEquality(IntervalVar*
const var1, IntervalVar*
const var2);
2049 Assignment* MakeAssignment();
2052 Assignment* MakeAssignment(
const Assignment*
const a);
2055 SolutionCollector* MakeFirstSolutionCollector(
2056 const Assignment*
const assignment);
2059 SolutionCollector* MakeFirstSolutionCollector();
2062 SolutionCollector* MakeLastSolutionCollector(
2063 const Assignment*
const assignment);
2066 SolutionCollector* MakeLastSolutionCollector();
2072 SolutionCollector* MakeBestValueSolutionCollector(
2073 const Assignment*
const assignment,
bool maximize);
2079 SolutionCollector* MakeBestValueSolutionCollector(
bool maximize);
2084 SolutionCollector* MakeNBestValueSolutionCollector(
2085 const Assignment*
const assignment,
int solution_count,
bool maximize);
2086 SolutionCollector* MakeNBestValueSolutionCollector(
int solution_count,
2090 SolutionCollector* MakeAllSolutionCollector(
2091 const Assignment*
const assignment);
2094 SolutionCollector* MakeAllSolutionCollector();
2097 OptimizeVar* MakeMinimize(IntVar*
const v, int64 step);
2100 OptimizeVar* MakeMaximize(IntVar*
const v, int64 step);
2103 OptimizeVar* MakeOptimize(
bool maximize, IntVar*
const v, int64 step);
2107 OptimizeVar* MakeWeightedMinimize(
const std::vector<IntVar*>& sub_objectives,
2108 const std::vector<int64>& weights,
2113 OptimizeVar* MakeWeightedMinimize(
const std::vector<IntVar*>& sub_objectives,
2114 const std::vector<int>& weights,
2118 OptimizeVar* MakeWeightedMaximize(
const std::vector<IntVar*>& sub_objectives,
2119 const std::vector<int64>& weights,
2123 OptimizeVar* MakeWeightedMaximize(
const std::vector<IntVar*>& sub_objectives,
2124 const std::vector<int>& weights,
2128 OptimizeVar* MakeWeightedOptimize(
bool maximize,
2129 const std::vector<IntVar*>& sub_objectives,
2130 const std::vector<int64>& weights,
2134 OptimizeVar* MakeWeightedOptimize(
bool maximize,
2135 const std::vector<IntVar*>& sub_objectives,
2136 const std::vector<int>& weights,
2157 SearchMonitor* MakeTabuSearch(
bool maximize, IntVar*
const v, int64 step,
2158 const std::vector<IntVar*>& vars,
2159 int64 keep_tenure, int64 forbid_tenure,
2160 double tabu_factor);
2164 SearchMonitor* MakeGenericTabuSearch(
bool maximize, IntVar*
const v,
2166 const std::vector<IntVar*>& tabu_vars,
2167 int64 forbid_tenure);
2171 SearchMonitor* MakeSimulatedAnnealing(
bool maximize, IntVar*
const v,
2172 int64 step, int64 initial_temperature);
2176 SearchMonitor* MakeGuidedLocalSearch(
bool maximize, IntVar*
const objective,
2177 IndexEvaluator2 objective_function,
2179 const std::vector<IntVar*>& vars,
2180 double penalty_factor);
2181 SearchMonitor* MakeGuidedLocalSearch(
2182 bool maximize, IntVar*
const objective,
2183 IndexEvaluator3 objective_function, int64 step,
2184 const std::vector<IntVar*>& vars,
2185 const std::vector<IntVar*>& secondary_vars,
double penalty_factor);
2190 SearchMonitor* MakeLubyRestart(
int scale_factor);
2194 SearchMonitor* MakeConstantRestart(
int frequency);
2198 RegularLimit* MakeTimeLimit(int64 time_in_ms);
2202 RegularLimit* MakeBranchesLimit(int64 branches);
2206 RegularLimit* MakeFailuresLimit(int64 failures);
2210 RegularLimit* MakeSolutionsLimit(int64 solutions);
2214 RegularLimit* MakeLimit(int64 time, int64 branches, int64 failures,
2218 RegularLimit* MakeLimit(int64 time, int64 branches, int64 failures,
2219 int64 solutions,
bool smart_time_check);
2222 RegularLimit* MakeLimit(int64 time, int64 branches, int64 failures,
2223 int64 solutions,
bool smart_time_check,
2226 RegularLimit* MakeLimit(
const RegularLimitParameters& proto);
2229 RegularLimitParameters MakeDefaultRegularLimitParameters()
const;
2234 SearchLimit* MakeLimit(SearchLimit*
const limit_1,
2235 SearchLimit*
const limit_2);
2239 SearchLimit* MakeCustomLimit(std::function<
bool()> limiter);
2245 SearchMonitor* MakeSearchLog(
int branch_period);
2248 SearchMonitor* MakeSearchLog(
int branch_period, IntVar*
const var);
2252 SearchMonitor* MakeSearchLog(
int branch_period,
2253 std::function<std::string()> display_callback);
2257 SearchMonitor* MakeSearchLog(
int branch_period, IntVar* var,
2258 std::function<std::string()> display_callback);
2262 SearchMonitor* MakeSearchLog(
int branch_period, OptimizeVar*
const opt_var);
2266 SearchMonitor* MakeSearchLog(
int branch_period, OptimizeVar*
const opt_var,
2267 std::function<std::string()> display_callback);
2270 struct SearchLogParameters {
2273 int branch_period = 1;
2276 OptimizeVar* objective =
nullptr;
2277 IntVar* variable =
nullptr;
2281 double scaling_factor = 1.0;
2285 std::function<std::string()> display_callback;
2287 SearchMonitor* MakeSearchLog(SearchLogParameters parameters);
2291 SearchMonitor* MakeSearchTrace(
const std::string& prefix);
2294 SearchMonitor* MakeEnterSearchCallback(std::function<
void()> callback);
2295 SearchMonitor* MakeExitSearchCallback(std::function<
void()> callback);
2296 SearchMonitor* MakeAtSolutionCallback(std::function<
void()> callback);
2299 ModelVisitor* MakePrintModelVisitor();
2301 ModelVisitor* MakeStatisticsModelVisitor();
2303 ModelVisitor* MakeVariableDegreeVisitor(
2305 absl::flat_hash_map<const IntVar*, int>*
const map);
2306 #endif // !defined(SWIG)
2309 SearchMonitor* MakeSymmetryManager(
2310 const std::vector<SymmetryBreaker*>& visitors);
2311 SearchMonitor* MakeSymmetryManager(SymmetryBreaker*
const v1);
2312 SearchMonitor* MakeSymmetryManager(SymmetryBreaker*
const v1,
2313 SymmetryBreaker*
const v2);
2314 SearchMonitor* MakeSymmetryManager(SymmetryBreaker*
const v1,
2315 SymmetryBreaker*
const v2,
2316 SymmetryBreaker*
const v3);
2317 SearchMonitor* MakeSymmetryManager(SymmetryBreaker*
const v1,
2318 SymmetryBreaker*
const v2,
2319 SymmetryBreaker*
const v3,
2320 SymmetryBreaker*
const v4);
2323 Decision* MakeAssignVariableValue(IntVar*
const var, int64 val);
2324 Decision* MakeVariableLessOrEqualValue(IntVar*
const var, int64 value);
2325 Decision* MakeVariableGreaterOrEqualValue(IntVar*
const var, int64 value);
2326 Decision* MakeSplitVariableDomain(IntVar*
const var, int64 val,
2327 bool start_with_lower_half);
2328 Decision* MakeAssignVariableValueOrFail(IntVar*
const var, int64 value);
2329 Decision* MakeAssignVariableValueOrDoNothing(IntVar*
const var, int64 value);
2330 Decision* MakeAssignVariablesValues(
const std::vector<IntVar*>& vars,
2331 const std::vector<int64>& values);
2332 Decision* MakeFailDecision();
2333 Decision* MakeDecision(Action apply, Action refute);
2343 DecisionBuilder* Compose(DecisionBuilder*
const db1,
2344 DecisionBuilder*
const db2);
2345 DecisionBuilder* Compose(DecisionBuilder*
const db1,
2346 DecisionBuilder*
const db2,
2347 DecisionBuilder*
const db3);
2348 DecisionBuilder* Compose(DecisionBuilder*
const db1,
2349 DecisionBuilder*
const db2,
2350 DecisionBuilder*
const db3,
2351 DecisionBuilder*
const db4);
2352 DecisionBuilder* Compose(
const std::vector<DecisionBuilder*>& dbs);
2370 DecisionBuilder* Try(DecisionBuilder*
const db1, DecisionBuilder*
const db2);
2371 DecisionBuilder* Try(DecisionBuilder*
const db1, DecisionBuilder*
const db2,
2372 DecisionBuilder*
const db3);
2373 DecisionBuilder* Try(DecisionBuilder*
const db1, DecisionBuilder*
const db2,
2374 DecisionBuilder*
const db3, DecisionBuilder*
const db4);
2375 DecisionBuilder* Try(
const std::vector<DecisionBuilder*>& dbs);
2380 DecisionBuilder* MakePhase(
const std::vector<IntVar*>& vars,
2381 IntVarStrategy var_str, IntValueStrategy val_str);
2382 DecisionBuilder* MakePhase(
const std::vector<IntVar*>& vars,
2383 IndexEvaluator1 var_evaluator,
2384 IntValueStrategy val_str);
2386 DecisionBuilder* MakePhase(
const std::vector<IntVar*>& vars,
2387 IntVarStrategy var_str,
2388 IndexEvaluator2 value_evaluator);
2392 DecisionBuilder* MakePhase(
const std::vector<IntVar*>& vars,
2393 IntVarStrategy var_str,
2394 VariableValueComparator var_val1_val2_comparator);
2396 DecisionBuilder* MakePhase(
const std::vector<IntVar*>& vars,
2397 IndexEvaluator1 var_evaluator,
2398 IndexEvaluator2 value_evaluator);
2400 DecisionBuilder* MakePhase(
const std::vector<IntVar*>& vars,
2401 IntVarStrategy var_str,
2402 IndexEvaluator2 value_evaluator,
2403 IndexEvaluator1 tie_breaker);
2405 DecisionBuilder* MakePhase(
const std::vector<IntVar*>& vars,
2406 IndexEvaluator1 var_evaluator,
2407 IndexEvaluator2 value_evaluator,
2408 IndexEvaluator1 tie_breaker);
2410 DecisionBuilder* MakeDefaultPhase(
const std::vector<IntVar*>& vars);
2411 DecisionBuilder* MakeDefaultPhase(
const std::vector<IntVar*>& vars,
2412 const DefaultPhaseParameters& parameters);
2415 DecisionBuilder* MakePhase(IntVar*
const v0, IntVarStrategy var_str,
2416 IntValueStrategy val_str);
2417 DecisionBuilder* MakePhase(IntVar*
const v0, IntVar*
const v1,
2418 IntVarStrategy var_str, IntValueStrategy val_str);
2419 DecisionBuilder* MakePhase(IntVar*
const v0, IntVar*
const v1,
2420 IntVar*
const v2, IntVarStrategy var_str,
2421 IntValueStrategy val_str);
2422 DecisionBuilder* MakePhase(IntVar*
const v0, IntVar*
const v1,
2423 IntVar*
const v2, IntVar*
const v3,
2424 IntVarStrategy var_str, IntValueStrategy val_str);
2431 Decision* MakeScheduleOrPostpone(IntervalVar*
const var, int64 est,
2432 int64*
const marker);
2439 Decision* MakeScheduleOrExpedite(IntervalVar*
const var, int64 est,
2440 int64*
const marker);
2444 Decision* MakeRankFirstInterval(SequenceVar*
const sequence,
int index);
2448 Decision* MakeRankLastInterval(SequenceVar*
const sequence,
int index);
2455 DecisionBuilder* MakePhase(
const std::vector<IntVar*>& vars,
2456 IndexEvaluator2 eval, EvaluatorStrategy str);
2465 DecisionBuilder* MakePhase(
const std::vector<IntVar*>& vars,
2466 IndexEvaluator2 eval, IndexEvaluator1 tie_breaker,
2467 EvaluatorStrategy str);
2470 DecisionBuilder* MakePhase(
const std::vector<IntervalVar*>& intervals,
2471 IntervalStrategy str);
2473 DecisionBuilder* MakePhase(
const std::vector<SequenceVar*>& sequences,
2474 SequenceStrategy str);
2478 DecisionBuilder* MakeDecisionBuilderFromAssignment(
2479 Assignment*
const assignment, DecisionBuilder*
const db,
2480 const std::vector<IntVar*>& vars);
2484 DecisionBuilder* MakeConstraintAdder(Constraint*
const ct);
2490 DecisionBuilder* MakeSolveOnce(DecisionBuilder*
const db);
2491 DecisionBuilder* MakeSolveOnce(DecisionBuilder*
const db,
2492 SearchMonitor*
const monitor1);
2493 DecisionBuilder* MakeSolveOnce(DecisionBuilder*
const db,
2494 SearchMonitor*
const monitor1,
2495 SearchMonitor*
const monitor2);
2496 DecisionBuilder* MakeSolveOnce(DecisionBuilder*
const db,
2497 SearchMonitor*
const monitor1,
2498 SearchMonitor*
const monitor2,
2499 SearchMonitor*
const monitor3);
2500 DecisionBuilder* MakeSolveOnce(DecisionBuilder*
const db,
2501 SearchMonitor*
const monitor1,
2502 SearchMonitor*
const monitor2,
2503 SearchMonitor*
const monitor3,
2504 SearchMonitor*
const monitor4);
2505 DecisionBuilder* MakeSolveOnce(DecisionBuilder*
const db,
2506 const std::vector<SearchMonitor*>& monitors);
2515 DecisionBuilder* MakeNestedOptimize(DecisionBuilder*
const db,
2516 Assignment*
const solution,
bool maximize,
2518 DecisionBuilder* MakeNestedOptimize(DecisionBuilder*
const db,
2519 Assignment*
const solution,
bool maximize,
2521 SearchMonitor*
const monitor1);
2522 DecisionBuilder* MakeNestedOptimize(DecisionBuilder*
const db,
2523 Assignment*
const solution,
bool maximize,
2524 int64 step, SearchMonitor*
const monitor1,
2525 SearchMonitor*
const monitor2);
2526 DecisionBuilder* MakeNestedOptimize(DecisionBuilder*
const db,
2527 Assignment*
const solution,
bool maximize,
2528 int64 step, SearchMonitor*
const monitor1,
2529 SearchMonitor*
const monitor2,
2530 SearchMonitor*
const monitor3);
2531 DecisionBuilder* MakeNestedOptimize(DecisionBuilder*
const db,
2532 Assignment*
const solution,
bool maximize,
2533 int64 step, SearchMonitor*
const monitor1,
2534 SearchMonitor*
const monitor2,
2535 SearchMonitor*
const monitor3,
2536 SearchMonitor*
const monitor4);
2537 DecisionBuilder* MakeNestedOptimize(
2538 DecisionBuilder*
const db, Assignment*
const solution,
bool maximize,
2539 int64 step,
const std::vector<SearchMonitor*>& monitors);
2543 DecisionBuilder* MakeRestoreAssignment(Assignment* assignment);
2547 DecisionBuilder* MakeStoreAssignment(Assignment* assignment);
2550 LocalSearchOperator* MakeOperator(
const std::vector<IntVar*>& vars,
2551 LocalSearchOperators op);
2552 LocalSearchOperator* MakeOperator(
const std::vector<IntVar*>& vars,
2553 const std::vector<IntVar*>& secondary_vars,
2554 LocalSearchOperators op);
2557 LocalSearchOperator* MakeOperator(
const std::vector<IntVar*>& vars,
2558 IndexEvaluator3 evaluator,
2559 EvaluatorLocalSearchOperators op);
2560 LocalSearchOperator* MakeOperator(
const std::vector<IntVar*>& vars,
2561 const std::vector<IntVar*>& secondary_vars,
2562 IndexEvaluator3 evaluator,
2563 EvaluatorLocalSearchOperators op);
2572 LocalSearchOperator* MakeRandomLnsOperator(
const std::vector<IntVar*>& vars,
2573 int number_of_variables);
2574 LocalSearchOperator* MakeRandomLnsOperator(
const std::vector<IntVar*>& vars,
2575 int number_of_variables,
2583 LocalSearchOperator* MakeMoveTowardTargetOperator(
const Assignment& target);
2591 LocalSearchOperator* MakeMoveTowardTargetOperator(
2592 const std::vector<IntVar*>& variables,
2593 const std::vector<int64>& target_values);
2625 LocalSearchOperator* ConcatenateOperators(
2626 const std::vector<LocalSearchOperator*>& ops);
2627 LocalSearchOperator* ConcatenateOperators(
2628 const std::vector<LocalSearchOperator*>& ops,
bool restart);
2629 LocalSearchOperator* ConcatenateOperators(
2630 const std::vector<LocalSearchOperator*>& ops,
2631 std::function<int64(
int,
int)> evaluator);
2634 LocalSearchOperator* RandomConcatenateOperators(
2635 const std::vector<LocalSearchOperator*>& ops);
2640 LocalSearchOperator* RandomConcatenateOperators(
2641 const std::vector<LocalSearchOperator*>& ops, int32 seed);
2648 LocalSearchOperator* MakeNeighborhoodLimit(LocalSearchOperator*
const op,
2678 DecisionBuilder* MakeLocalSearchPhase(
2679 Assignment*
const assignment,
2680 LocalSearchPhaseParameters*
const parameters);
2681 DecisionBuilder* MakeLocalSearchPhase(
2682 const std::vector<IntVar*>& vars, DecisionBuilder*
const first_solution,
2683 LocalSearchPhaseParameters*
const parameters);
2685 DecisionBuilder* MakeLocalSearchPhase(
2686 const std::vector<IntVar*>& vars, DecisionBuilder*
const first_solution,
2687 DecisionBuilder*
const first_solution_sub_decision_builder,
2688 LocalSearchPhaseParameters*
const parameters);
2689 DecisionBuilder* MakeLocalSearchPhase(
2690 const std::vector<SequenceVar*>& vars,
2691 DecisionBuilder*
const first_solution,
2692 LocalSearchPhaseParameters*
const parameters);
2695 SolutionPool* MakeDefaultSolutionPool();
2698 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2699 IntVar* objective, LocalSearchOperator*
const ls_operator,
2700 DecisionBuilder*
const sub_decision_builder);
2701 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2702 IntVar* objective, LocalSearchOperator*
const ls_operator,
2703 DecisionBuilder*
const sub_decision_builder, RegularLimit*
const limit);
2704 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2705 IntVar* objective, LocalSearchOperator*
const ls_operator,
2706 DecisionBuilder*
const sub_decision_builder, RegularLimit*
const limit,
2707 const std::vector<LocalSearchFilter*>& filters);
2709 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2710 IntVar* objective, SolutionPool*
const pool,
2711 LocalSearchOperator*
const ls_operator,
2712 DecisionBuilder*
const sub_decision_builder);
2713 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2714 IntVar* objective, SolutionPool*
const pool,
2715 LocalSearchOperator*
const ls_operator,
2716 DecisionBuilder*
const sub_decision_builder, RegularLimit*
const limit);
2717 LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2718 IntVar* objective, SolutionPool*
const pool,
2719 LocalSearchOperator*
const ls_operator,
2720 DecisionBuilder*
const sub_decision_builder, RegularLimit*
const limit,
2721 const std::vector<LocalSearchFilter*>& filters);
2724 LocalSearchFilter* MakeAcceptFilter();
2725 LocalSearchFilter* MakeRejectFilter();
2726 LocalSearchFilter* MakeVariableDomainFilter();
2727 IntVarLocalSearchFilter* MakeSumObjectiveFilter(
2728 const std::vector<IntVar*>& vars, IndexEvaluator2 values,
2729 Solver::LocalSearchFilterBound filter_enum);
2730 IntVarLocalSearchFilter* MakeSumObjectiveFilter(
2731 const std::vector<IntVar*>& vars,
2732 const std::vector<IntVar*>& secondary_vars, IndexEvaluator3 values,
2733 Solver::LocalSearchFilterBound filter_enum);
2737 void TopPeriodicCheck();
2741 int TopProgressPercent();
2751 int SearchDepth()
const;
2755 int SearchLeftDepth()
const;
2759 int SolveDepth()
const;
2762 void SetBranchSelector(BranchSelector bs);
2765 DecisionBuilder* MakeApplyBranchSelector(BranchSelector bs);
2769 void SaveAndSetValue(T* adr, T val) {
2771 InternalSaveValue(adr);
2778 void SaveAndAdd(T* adr, T val) {
2780 InternalSaveValue(adr);
2786 int64 Rand64(int64 size) {
2788 return absl::Uniform<int64>(random_, 0, size);
2792 int32 Rand32(int32 size) {
2794 return absl::Uniform<int32>(random_, 0, size);
2798 void ReSeed(int32 seed) { random_.seed(seed); }
2803 void ExportProfilingOverview(
const std::string& filename);
2808 std::string LocalSearchProfile()
const;
2813 bool CurrentlyInSolve()
const;
2817 int constraints()
const {
return constraints_list_.size(); }
2820 void Accept(ModelVisitor*
const visitor)
const;
2822 Decision* balancing_decision()
const {
return balancing_decision_.get(); }
2826 void set_fail_intercept(std::function<
void()> fail_intercept) {
2827 fail_intercept_ = std::move(fail_intercept);
2829 #endif // !defined(SWIG)
2830 void clear_fail_intercept() { fail_intercept_ =
nullptr; }
2832 DemonProfiler* demon_profiler()
const {
return demon_profiler_; }
2836 void SetUseFastLocalSearch(
bool use_fast_local_search) {
2837 use_fast_local_search_ = use_fast_local_search;
2840 bool UseFastLocalSearch()
const {
return use_fast_local_search_; }
2842 bool HasName(
const PropagationBaseObject*
object)
const;
2844 Demon* RegisterDemon(Demon*
const demon);
2846 IntExpr* RegisterIntExpr(IntExpr*
const expr);
2848 IntVar* RegisterIntVar(IntVar*
const var);
2851 IntervalVar* RegisterIntervalVar(IntervalVar*
const var);
2854 Search* ActiveSearch()
const;
2856 ModelCache* Cache()
const;
2858 bool InstrumentsDemons()
const;
2860 bool IsProfilingEnabled()
const;
2862 bool IsLocalSearchProfilingEnabled()
const;
2864 bool InstrumentsVariables()
const;
2866 bool NameAllVariables()
const;
2868 std::string model_name()
const;
2870 PropagationMonitor* GetPropagationMonitor()
const;
2873 void AddPropagationMonitor(PropagationMonitor*
const monitor);
2875 LocalSearchMonitor* GetLocalSearchMonitor()
const;
2878 void AddLocalSearchMonitor(LocalSearchMonitor* monitor);
2879 void SetSearchContext(Search* search,
const std::string& search_context);
2880 std::string SearchContext()
const;
2881 std::string SearchContext(
const Search* search)
const;
2884 Assignment* GetOrCreateLocalSearchState();
2886 void ClearLocalSearchState() { local_search_state_.reset(
nullptr); }
2892 std::vector<int64> tmp_vector_;
2894 friend class BaseIntExpr;
2895 friend class Constraint;
2896 friend class DemonProfiler;
2897 friend class FindOneNeighbor;
2898 friend class IntVar;
2899 friend class PropagationBaseObject;
2901 friend class SearchMonitor;
2902 friend class SearchLimit;
2903 friend class RoutingModel;
2904 friend class LocalSearchProfiler;
2907 friend void InternalSaveBooleanVarValue(Solver*
const, IntVar*
const);
2909 friend class SimpleRevFIFO;
2910 template <
class K,
class V>
2911 friend class RevImmutableMultiMap;
2917 bool IsBooleanVar(IntExpr*
const expr, IntVar** inner_var,
2918 bool* is_negated)
const;
2924 bool IsProduct(IntExpr*
const expr, IntExpr** inner_expr, int64* coefficient);
2927 IntExpr* CastExpression(
const IntVar*
const var)
const;
2932 void FinishCurrentSearch();
2933 void RestartCurrentSearch();
2937 void ShouldFail() { should_fail_ =
true; }
2939 if (!should_fail_)
return;
2940 should_fail_ =
false;
2946 void PushState(MarkerType t,
const StateInfo& info);
2947 MarkerType PopState(StateInfo* info);
2948 void PushSentinel(
int magic_code);
2949 void BacktrackToSentinel(
int magic_code);
2950 void ProcessConstraints();
2951 bool BacktrackOneLevel(Decision** fail_decision);
2952 void JumpToSentinelWhenNested();
2953 void JumpToSentinel();
2954 void check_alloc_state();
2956 void EnqueueVar(Demon*
const d);
2957 void EnqueueDelayedDemon(Demon*
const d);
2958 void ExecuteAll(
const SimpleRevFIFO<Demon*>& demons);
2959 void EnqueueAll(
const SimpleRevFIFO<Demon*>& demons);
2960 void UnfreezeQueue();
2961 void reset_action_on_fail();
2962 void set_action_on_fail(Action a);
2963 void set_variable_to_clean_on_fail(IntVar* v);
2964 void IncrementUncheckedSolutionCounter();
2965 bool IsUncheckedSolutionLimitReached();
2967 void InternalSaveValue(
int* valptr);
2968 void InternalSaveValue(int64* valptr);
2969 void InternalSaveValue(uint64* valptr);
2970 void InternalSaveValue(
double* valptr);
2971 void InternalSaveValue(
bool* valptr);
2972 void InternalSaveValue(
void** valptr);
2973 void InternalSaveValue(int64** valptr) {
2974 InternalSaveValue(
reinterpret_cast<void**
>(valptr));
2977 BaseObject* SafeRevAlloc(BaseObject* ptr);
2979 int* SafeRevAllocArray(
int* ptr);
2980 int64* SafeRevAllocArray(int64* ptr);
2981 uint64* SafeRevAllocArray(uint64* ptr);
2982 double* SafeRevAllocArray(
double* ptr);
2983 BaseObject** SafeRevAllocArray(BaseObject** ptr);
2984 IntVar** SafeRevAllocArray(IntVar** ptr);
2985 IntExpr** SafeRevAllocArray(IntExpr** ptr);
2986 Constraint** SafeRevAllocArray(Constraint** ptr);
2989 void* UnsafeRevAllocAux(
void* ptr);
2991 T* UnsafeRevAlloc(T* ptr) {
2992 return reinterpret_cast<T*
>(
2993 UnsafeRevAllocAux(
reinterpret_cast<void*
>(ptr)));
2995 void** UnsafeRevAllocArrayAux(
void** ptr);
2997 T** UnsafeRevAllocArray(T** ptr) {
2998 return reinterpret_cast<T**
>(
2999 UnsafeRevAllocArrayAux(
reinterpret_cast<void**
>(ptr)));
3002 void InitCachedIntConstants();
3003 void InitCachedConstraint();
3008 Search* TopLevelSearch()
const {
return searches_.at(1); }
3012 Search* ParentSearch()
const {
3013 const size_t search_size = searches_.size();
3014 DCHECK_GT(search_size, 1);
3015 return searches_[search_size - 2];
3019 std::string GetName(
const PropagationBaseObject*
object);
3020 void SetName(
const PropagationBaseObject*
object,
const std::string& name);
3024 int GetNewIntVarIndex() {
return num_int_vars_++; }
3027 bool IsADifference(IntExpr* expr, IntExpr**
const left,
3028 IntExpr**
const right);
3030 const std::string name_;
3031 const ConstraintSolverParameters parameters_;
3032 absl::flat_hash_map<const PropagationBaseObject*, std::string>
3033 propagation_object_names_;
3034 absl::flat_hash_map<const PropagationBaseObject*, IntegerCastInfo>
3036 absl::flat_hash_set<const Constraint*> cast_constraints_;
3037 const std::string empty_name_;
3038 std::unique_ptr<Queue> queue_;
3039 std::unique_ptr<Trail> trail_;
3040 std::vector<Constraint*> constraints_list_;
3041 std::vector<Constraint*> additional_constraints_list_;
3042 std::vector<int> additional_constraints_parent_list_;
3047 int64 demon_runs_[kNumPriorities];
3049 int64 filtered_neighbors_;
3050 int64 accepted_neighbors_;
3051 OptimizationDirection optimization_direction_;
3052 std::unique_ptr<ClockTimer> timer_;
3053 std::vector<Search*> searches_;
3054 std::mt19937 random_;
3056 std::unique_ptr<Decision> balancing_decision_;
3058 std::function<void()> fail_intercept_;
3060 DemonProfiler*
const demon_profiler_;
3062 bool use_fast_local_search_;
3064 LocalSearchProfiler*
const local_search_profiler_;
3066 std::unique_ptr<Assignment> local_search_state_;
3069 enum { MIN_CACHED_INT_CONST = -8, MAX_CACHED_INT_CONST = 8 };
3070 IntVar* cached_constants_[MAX_CACHED_INT_CONST + 1 - MIN_CACHED_INT_CONST];
3073 Constraint* true_constraint_;
3074 Constraint* false_constraint_;
3076 std::unique_ptr<Decision> fail_decision_;
3077 int constraint_index_;
3078 int additional_constraint_index_;
3081 std::unique_ptr<ModelCache> model_cache_;
3082 std::unique_ptr<PropagationMonitor> propagation_monitor_;
3083 PropagationMonitor* print_trace_;
3084 std::unique_ptr<LocalSearchMonitor> local_search_monitor_;
3085 int anonymous_variable_index_;
3088 DISALLOW_COPY_AND_ASSIGN(Solver);
3091 std::ostream& operator<<(std::ostream& out,
const Solver*
const s);
3096 inline int64 Zero() {
return 0; }
3099 inline int64 One() {
return 1; }
3107 virtual ~BaseObject() {}
3108 virtual std::string DebugString()
const {
return "BaseObject"; }
3111 DISALLOW_COPY_AND_ASSIGN(BaseObject);
3114 std::ostream& operator<<(std::ostream& out,
const BaseObject* o);
3119 class PropagationBaseObject :
public BaseObject {
3121 explicit PropagationBaseObject(Solver*
const s) : solver_(s) {}
3122 ~PropagationBaseObject()
override {}
3124 std::string DebugString()
const override {
3125 if (name().empty()) {
3126 return "PropagationBaseObject";
3128 return absl::StrFormat(
"PropagationBaseObject: %s", name());
3131 Solver* solver()
const {
return solver_; }
3135 void FreezeQueue() { solver_->FreezeQueue(); }
3139 void UnfreezeQueue() { solver_->UnfreezeQueue(); }
3144 void EnqueueDelayedDemon(Demon*
const d) { solver_->EnqueueDelayedDemon(d); }
3145 void EnqueueVar(Demon*
const d) { solver_->EnqueueVar(d); }
3146 void ExecuteAll(
const SimpleRevFIFO<Demon*>& demons);
3147 void EnqueueAll(
const SimpleRevFIFO<Demon*>& demons);
3152 void set_action_on_fail(Solver::Action a) {
3153 solver_->set_action_on_fail(std::move(a));
3155 #endif // !defined(SWIG)
3158 void reset_action_on_fail() { solver_->reset_action_on_fail(); }
3161 void set_variable_to_clean_on_fail(IntVar* v) {
3162 solver_->set_variable_to_clean_on_fail(v);
3166 virtual std::string name()
const;
3167 void set_name(
const std::string& name);
3169 bool HasName()
const;
3171 virtual std::string BaseName()
const;
3174 Solver*
const solver_;
3175 DISALLOW_COPY_AND_ASSIGN(PropagationBaseObject);
3180 class Decision :
public BaseObject {
3183 ~Decision()
override {}
3186 virtual void Apply(Solver*
const s) = 0;
3189 virtual void Refute(Solver*
const s) = 0;
3191 std::string DebugString()
const override {
return "Decision"; }
3193 virtual void Accept(DecisionVisitor*
const visitor)
const;
3196 DISALLOW_COPY_AND_ASSIGN(Decision);
3201 class DecisionVisitor :
public BaseObject {
3203 DecisionVisitor() {}
3204 ~DecisionVisitor()
override {}
3205 virtual void VisitSetVariableValue(IntVar*
const var, int64 value);
3206 virtual void VisitSplitVariableDomain(IntVar*
const var, int64 value,
3207 bool start_with_lower_half);
3208 virtual void VisitScheduleOrPostpone(IntervalVar*
const var, int64 est);
3209 virtual void VisitScheduleOrExpedite(IntervalVar*
const var, int64 est);
3210 virtual void VisitRankFirstInterval(SequenceVar*
const sequence,
int index);
3211 virtual void VisitRankLastInterval(SequenceVar*
const sequence,
int index);
3212 virtual void VisitUnknownDecision();
3215 DISALLOW_COPY_AND_ASSIGN(DecisionVisitor);
3220 class DecisionBuilder :
public BaseObject {
3222 DecisionBuilder() {}
3223 ~DecisionBuilder()
override {}
3228 virtual Decision* Next(Solver*
const s) = 0;
3229 std::string DebugString()
const override;
3231 virtual void AppendMonitors(Solver*
const solver,
3236 std::vector<SearchMonitor*>*
const extras);
3237 virtual void Accept(ModelVisitor*
const visitor)
const;
3241 DISALLOW_COPY_AND_ASSIGN(DecisionBuilder);
3253 class Demon :
public BaseObject {
3257 Demon() : stamp_(GG_ULONGLONG(0)) {}
3258 ~Demon()
override {}
3261 virtual void Run(Solver*
const s) = 0;
3266 virtual Solver::DemonPriority priority()
const;
3268 std::string DebugString()
const override;
3272 void inhibit(Solver*
const s);
3275 void desinhibit(Solver*
const s);
3279 void set_stamp(int64 stamp) { stamp_ = stamp; }
3280 uint64 stamp()
const {
return stamp_; }
3282 DISALLOW_COPY_AND_ASSIGN(Demon);
3286 class ModelVisitor :
public BaseObject {
3289 static const char kAbs[];
3290 static const char kAbsEqual[];
3291 static const char kAllDifferent[];
3292 static const char kAllowedAssignments[];
3293 static const char kAtMost[];
3294 static const char kIndexOf[];
3295 static const char kBetween[];
3296 static const char kConditionalExpr[];
3297 static const char kCircuit[];
3298 static const char kConvexPiecewise[];
3299 static const char kCountEqual[];
3300 static const char kCover[];
3301 static const char kCumulative[];
3302 static const char kDeviation[];
3303 static const char kDifference[];
3304 static const char kDisjunctive[];
3305 static const char kDistribute[];
3306 static const char kDivide[];
3307 static const char kDurationExpr[];
3308 static const char kElement[];
3309 static const char kElementEqual[];
3310 static const char kEndExpr[];
3311 static const char kEquality[];
3312 static const char kFalseConstraint[];
3313 static const char kGlobalCardinality[];
3314 static const char kGreater[];
3315 static const char kGreaterOrEqual[];
3316 static const char kIntegerVariable[];
3317 static const char kIntervalBinaryRelation[];
3318 static const char kIntervalDisjunction[];
3319 static const char kIntervalUnaryRelation[];
3320 static const char kIntervalVariable[];
3321 static const char kInversePermutation[];
3322 static const char kIsBetween[];
3323 static const char kIsDifferent[];
3324 static const char kIsEqual[];
3325 static const char kIsGreater[];
3326 static const char kIsGreaterOrEqual[];
3327 static const char kIsLess[];
3328 static const char kIsLessOrEqual[];
3329 static const char kIsMember[];
3330 static const char kLess[];
3331 static const char kLessOrEqual[];
3332 static const char kLexLess[];
3333 static const char kLinkExprVar[];
3334 static const char kMapDomain[];
3335 static const char kMax[];
3336 static const char kMaxEqual[];
3337 static const char kMember[];
3338 static const char kMin[];
3339 static const char kMinEqual[];
3340 static const char kModulo[];
3341 static const char kNoCycle[];
3342 static const char kNonEqual[];
3343 static const char kNotBetween[];
3344 static const char kNotMember[];
3345 static const char kNullIntersect[];
3346 static const char kOpposite[];
3347 static const char kPack[];
3348 static const char kPathCumul[];
3349 static const char kDelayedPathCumul[];
3350 static const char kPerformedExpr[];
3351 static const char kPower[];
3352 static const char kProduct[];
3353 static const char kScalProd[];
3354 static const char kScalProdEqual[];
3355 static const char kScalProdGreaterOrEqual[];
3356 static const char kScalProdLessOrEqual[];
3357 static const char kSemiContinuous[];
3358 static const char kSequenceVariable[];
3359 static const char kSortingConstraint[];
3360 static const char kSquare[];
3361 static const char kStartExpr[];
3362 static const char kSum[];
3363 static const char kSumEqual[];
3364 static const char kSumGreaterOrEqual[];
3365 static const char kSumLessOrEqual[];
3366 static const char kTrace[];
3367 static const char kTransition[];
3368 static const char kTrueConstraint[];
3369 static const char kVarBoundWatcher[];
3370 static const char kVarValueWatcher[];
3373 static const char kCountAssignedItemsExtension[];
3374 static const char kCountUsedBinsExtension[];
3375 static const char kInt64ToBoolExtension[];
3376 static const char kInt64ToInt64Extension[];
3377 static const char kObjectiveExtension[];
3378 static const char kSearchLimitExtension[];
3379 static const char kUsageEqualVariableExtension[];
3381 static const char kUsageLessConstantExtension[];
3382 static const char kVariableGroupExtension[];
3383 static const char kVariableUsageLessConstantExtension[];
3384 static const char kWeightedSumOfAssignedEqualVariableExtension[];
3387 static const char kActiveArgument[];
3388 static const char kAssumePathsArgument[];
3389 static const char kBranchesLimitArgument[];
3390 static const char kCapacityArgument[];
3391 static const char kCardsArgument[];
3392 static const char kCoefficientsArgument[];
3393 static const char kCountArgument[];
3394 static const char kCumulativeArgument[];
3395 static const char kCumulsArgument[];
3396 static const char kDemandsArgument[];
3397 static const char kDurationMaxArgument[];
3398 static const char kDurationMinArgument[];
3399 static const char kEarlyCostArgument[];
3400 static const char kEarlyDateArgument[];
3401 static const char kEndMaxArgument[];
3402 static const char kEndMinArgument[];
3403 static const char kEndsArgument[];
3404 static const char kExpressionArgument[];
3405 static const char kFailuresLimitArgument[];
3406 static const char kFinalStatesArgument[];
3407 static const char kFixedChargeArgument[];
3408 static const char kIndex2Argument[];
3409 static const char kIndexArgument[];
3410 static const char kInitialState[];
3411 static const char kIntervalArgument[];
3412 static const char kIntervalsArgument[];
3413 static const char kLateCostArgument[];
3414 static const char kLateDateArgument[];
3415 static const char kLeftArgument[];
3416 static const char kMaxArgument[];
3417 static const char kMaximizeArgument[];
3418 static const char kMinArgument[];
3419 static const char kModuloArgument[];
3420 static const char kNextsArgument[];
3421 static const char kOptionalArgument[];
3422 static const char kPartialArgument[];
3423 static const char kPositionXArgument[];
3424 static const char kPositionYArgument[];
3425 static const char kRangeArgument[];
3426 static const char kRelationArgument[];
3427 static const char kRightArgument[];
3428 static const char kSequenceArgument[];
3429 static const char kSequencesArgument[];
3430 static const char kSizeArgument[];
3431 static const char kSizeXArgument[];
3432 static const char kSizeYArgument[];
3433 static const char kSmartTimeCheckArgument[];
3434 static const char kSolutionLimitArgument[];
3435 static const char kStartMaxArgument[];
3436 static const char kStartMinArgument[];
3437 static const char kStartsArgument[];
3438 static const char kStepArgument[];
3439 static const char kTargetArgument[];
3440 static const char kTimeLimitArgument[];
3441 static const char kTransitsArgument[];
3442 static const char kTuplesArgument[];
3443 static const char kValueArgument[];
3444 static const char kValuesArgument[];
3445 static const char kVariableArgument[];
3446 static const char kVarsArgument[];
3447 static const char kEvaluatorArgument[];
3450 static const char kMirrorOperation[];
3451 static const char kRelaxedMaxOperation[];
3452 static const char kRelaxedMinOperation[];
3453 static const char kSumOperation[];
3454 static const char kDifferenceOperation[];
3455 static const char kProductOperation[];
3456 static const char kStartSyncOnStartOperation[];
3457 static const char kStartSyncOnEndOperation[];
3458 static const char kTraceOperation[];
3460 ~ModelVisitor()
override;
3465 virtual void BeginVisitModel(
const std::string& type_name);
3466 virtual void EndVisitModel(
const std::string& type_name);
3467 virtual void BeginVisitConstraint(
const std::string& type_name,
3468 const Constraint*
const constraint);
3469 virtual void EndVisitConstraint(
const std::string& type_name,
3470 const Constraint*
const constraint);
3471 virtual void BeginVisitExtension(
const std::string& type);
3472 virtual void EndVisitExtension(
const std::string& type);
3473 virtual void BeginVisitIntegerExpression(
const std::string& type_name,
3474 const IntExpr*
const expr);
3475 virtual void EndVisitIntegerExpression(
const std::string& type_name,
3476 const IntExpr*
const expr);
3477 virtual void VisitIntegerVariable(
const IntVar*
const variable,
3478 IntExpr*
const delegate);
3479 virtual void VisitIntegerVariable(
const IntVar*
const variable,
3480 const std::string& operation, int64 value,
3481 IntVar*
const delegate);
3482 virtual void VisitIntervalVariable(
const IntervalVar*
const variable,
3483 const std::string& operation, int64 value,
3484 IntervalVar*
const delegate);
3485 virtual void VisitSequenceVariable(
const SequenceVar*
const variable);
3488 virtual void VisitIntegerArgument(
const std::string& arg_name, int64 value);
3489 virtual void VisitIntegerArrayArgument(
const std::string& arg_name,
3490 const std::vector<int64>& values);
3491 virtual void VisitIntegerMatrixArgument(
const std::string& arg_name,
3492 const IntTupleSet& tuples);
3495 virtual void VisitIntegerExpressionArgument(
const std::string& arg_name,
3496 IntExpr*
const argument);
3498 virtual void VisitIntegerVariableArrayArgument(
3499 const std::string& arg_name,
const std::vector<IntVar*>& arguments);
3502 virtual void VisitIntervalArgument(
const std::string& arg_name,
3503 IntervalVar*
const argument);
3505 virtual void VisitIntervalArrayArgument(
3506 const std::string& arg_name,
const std::vector<IntervalVar*>& arguments);
3508 virtual void VisitSequenceArgument(
const std::string& arg_name,
3509 SequenceVar*
const argument);
3511 virtual void VisitSequenceArrayArgument(
3512 const std::string& arg_name,
const std::vector<SequenceVar*>& arguments);
3514 virtual void VisitIntegerVariableEvaluatorArgument(
3516 const std::string& arg_name,
const Solver::Int64ToIntVar& arguments);
3520 void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64 index_min,
3522 void VisitInt64ToInt64Extension(
const Solver::IndexEvaluator1& eval,
3523 int64 index_min, int64 index_max);
3525 void VisitInt64ToInt64AsArray(
const Solver::IndexEvaluator1& eval,
3526 const std::string& arg_name, int64 index_max);
3527 #endif // #if !defined(SWIG)
3536 class Constraint :
public PropagationBaseObject {
3538 explicit Constraint(Solver*
const solver) : PropagationBaseObject(solver) {}
3539 ~Constraint()
override {}
3543 virtual void Post() = 0;
3547 virtual void InitialPropagate() = 0;
3548 std::string DebugString()
const override;
3552 void PostAndPropagate();
3555 virtual void Accept(ModelVisitor*
const visitor)
const;
3558 bool IsCastConstraint()
const;
3563 virtual IntVar* Var();
3566 DISALLOW_COPY_AND_ASSIGN(Constraint);
3572 class CastConstraint :
public Constraint {
3574 CastConstraint(Solver*
const solver, IntVar*
const target_var)
3575 : Constraint(solver), target_var_(target_var) {
3576 CHECK(target_var !=
nullptr);
3578 ~CastConstraint()
override {}
3580 IntVar* target_var()
const {
return target_var_; }
3583 IntVar*
const target_var_;
3587 class SearchMonitor :
public BaseObject {
3589 static const int kNoProgress = -1;
3591 explicit SearchMonitor(Solver*
const s) : solver_(s) {}
3592 ~SearchMonitor()
override {}
3594 virtual void EnterSearch();
3597 virtual void RestartSearch();
3600 virtual void ExitSearch();
3603 virtual void BeginNextDecision(DecisionBuilder*
const b);
3606 virtual void EndNextDecision(DecisionBuilder*
const b, Decision*
const d);
3609 virtual void ApplyDecision(Decision*
const d);
3612 virtual void RefuteDecision(Decision*
const d);
3616 virtual void AfterDecision(Decision*
const d,
bool apply);
3619 virtual void BeginFail();
3622 virtual void EndFail();
3625 virtual void BeginInitialPropagation();
3628 virtual void EndInitialPropagation();
3633 virtual bool AcceptSolution();
3638 virtual bool AtSolution();
3641 virtual void NoMoreSolutions();
3645 virtual bool LocalOptimum();
3648 virtual bool AcceptDelta(Assignment* delta, Assignment* deltadelta);
3651 virtual void AcceptNeighbor();
3654 virtual void AcceptUncheckedNeighbor();
3658 virtual bool IsUncheckedSolutionLimitReached() {
return false; }
3660 Solver* solver()
const {
return solver_; }
3663 virtual void PeriodicCheck();
3667 virtual int ProgressPercent() {
return kNoProgress; }
3670 virtual void Accept(ModelVisitor*
const visitor)
const;
3674 virtual void Install();
3677 Solver*
const solver_;
3678 DISALLOW_COPY_AND_ASSIGN(SearchMonitor);
3689 explicit Rev(
const T& val) : stamp_(0), value_(val) {}
3691 const T& Value()
const {
return value_; }
3693 void SetValue(Solver*
const s,
const T& val) {
3694 if (val != value_) {
3695 if (stamp_ < s->stamp()) {
3696 s->SaveValue(&value_);
3697 stamp_ = s->stamp();
3710 class NumericalRev :
public Rev<T> {
3712 explicit NumericalRev(
const T& val) : Rev<T>(val) {}
3714 void Add(Solver*
const s,
const T& to_add) {
3715 this->SetValue(s, this->Value() + to_add);
3718 void Incr(Solver*
const s) { Add(s, 1); }
3720 void Decr(Solver*
const s) { Add(s, -1); }
3731 RevArray(
int size,
const T& val)
3732 : stamps_(new uint64[size]), values_(new T[size]), size_(size) {
3733 for (
int i = 0; i < size; ++i) {
3741 int64 size()
const {
return size_; }
3743 const T& Value(
int index)
const {
return values_[index]; }
3746 const T& operator[](
int index)
const {
return values_[index]; }
3749 void SetValue(Solver*
const s,
int index,
const T& val) {
3750 DCHECK_LT(index, size_);
3751 if (val != values_[index]) {
3752 if (stamps_[index] < s->stamp()) {
3753 s->SaveValue(&values_[index]);
3754 stamps_[index] = s->stamp();
3756 values_[index] = val;
3761 std::unique_ptr<uint64[]> stamps_;
3762 std::unique_ptr<T[]> values_;
3768 class NumericalRevArray :
public RevArray<T> {
3770 NumericalRevArray(
int size,
const T& val) : RevArray<T>(size, val) {}
3772 void Add(Solver*
const s,
int index,
const T& to_add) {
3773 this->SetValue(s, index, this->Value(index) + to_add);
3776 void Incr(Solver*
const s,
int index) { Add(s, index, 1); }
3778 void Decr(Solver*
const s,
int index) { Add(s, index, -1); }
3788 class IntExpr :
public PropagationBaseObject {
3790 explicit IntExpr(Solver*
const s) : PropagationBaseObject(s) {}
3791 ~IntExpr()
override {}
3793 virtual int64 Min()
const = 0;
3794 virtual void SetMin(int64 m) = 0;
3795 virtual int64 Max()
const = 0;
3796 virtual void SetMax(int64 m) = 0;
3800 virtual void Range(int64* l, int64* u) {
3805 virtual void SetRange(int64 l, int64 u) {
3811 virtual void SetValue(int64 v) { SetRange(v, v); }
3814 virtual bool Bound()
const {
return (Min() == Max()); }
3817 virtual bool IsVar()
const {
return false; }
3820 virtual IntVar* Var() = 0;
3826 IntVar* VarWithName(
const std::string& name);
3829 virtual void WhenRange(Demon* d) = 0;
3831 void WhenRange(Solver::Closure closure) {
3832 WhenRange(solver()->MakeClosureDemon(std::move(closure)));
3836 void WhenRange(Solver::Action action) {
3838 WhenRange(solver()->MakeActionDemon(std::move(action)));
3843 virtual void Accept(ModelVisitor*
const visitor)
const;
3846 DISALLOW_COPY_AND_ASSIGN(IntExpr);
3866 class IntVarIterator :
public BaseObject {
3868 ~IntVarIterator()
override {}
3871 virtual void Init() = 0;
3874 virtual bool Ok()
const = 0;
3877 virtual int64 Value()
const = 0;
3880 virtual void Next() = 0;
3883 std::string DebugString()
const override {
return "IntVar::Iterator"; }
3887 class InitAndGetValues {
3895 explicit InitAndGetValues(IntVarIterator* it)
3896 : it_(it), begin_was_called_(false) {
3902 DCHECK(!begin_was_called_);
3903 begin_was_called_ =
true;
3905 return Iterator::Begin(it_);
3907 Iterator end() {
return Iterator::End(it_); }
3911 static Iterator Begin(IntVarIterator* it) {
3912 return Iterator(it,
false);
3914 static Iterator End(IntVarIterator* it) {
3915 return Iterator(it,
true);
3918 int64 operator*()
const {
3920 return it_->Value();
3922 Iterator& operator++() {
3927 bool operator!=(
const Iterator& other)
const {
3928 DCHECK(other.it_ == it_);
3929 DCHECK(other.is_end_);
3934 Iterator(IntVarIterator* it,
bool is_end) : it_(it), is_end_(is_end) {}
3936 IntVarIterator*
const it_;
3941 IntVarIterator*
const it_;
3942 bool begin_was_called_;
3949 class IntVar :
public IntExpr {
3951 explicit IntVar(Solver*
const s);
3952 IntVar(Solver*
const s,
const std::string& name);
3953 ~IntVar()
override {}
3955 bool IsVar()
const override {
return true; }
3956 IntVar* Var()
override {
return this; }
3960 virtual int64 Value()
const = 0;
3963 virtual void RemoveValue(int64 v) = 0;
3967 virtual void RemoveInterval(int64 l, int64 u) = 0;
3970 virtual void RemoveValues(
const std::vector<int64>& values);
3973 virtual void SetValues(
const std::vector<int64>& values);
3977 virtual void WhenBound(Demon* d) = 0;
3980 void WhenBound(Solver::Closure closure) {
3981 WhenBound(solver()->MakeClosureDemon(std::move(closure)));
3985 void WhenBound(Solver::Action action) {
3988 WhenBound(solver()->MakeActionDemon(std::move(action)));
3994 virtual void WhenDomain(Demon* d) = 0;
3997 void WhenDomain(Solver::Closure closure) {
3998 WhenDomain(solver()->MakeClosureDemon(std::move(closure)));
4001 void WhenDomain(Solver::Action action) {
4004 WhenDomain(solver()->MakeActionDemon(std::move(action)));
4009 virtual uint64 Size()
const = 0;
4013 virtual bool Contains(int64 v)
const = 0;
4018 virtual IntVarIterator* MakeHoleIterator(
bool reversible)
const = 0;
4023 virtual IntVarIterator* MakeDomainIterator(
bool reversible)
const = 0;
4026 virtual int64 OldMin()
const = 0;
4029 virtual int64 OldMax()
const = 0;
4031 virtual int VarType()
const;
4034 void Accept(ModelVisitor*
const visitor)
const override;
4037 virtual IntVar* IsEqual(int64 constant) = 0;
4038 virtual IntVar* IsDifferent(int64 constant) = 0;
4039 virtual IntVar* IsGreaterOrEqual(int64 constant) = 0;
4040 virtual IntVar* IsLessOrEqual(int64 constant) = 0;
4043 int index()
const {
return index_; }
4047 DISALLOW_COPY_AND_ASSIGN(IntVar);
4053 class SolutionCollector :
public SearchMonitor {
4055 SolutionCollector(Solver*
const solver,
const Assignment* assignment);
4056 explicit SolutionCollector(Solver*
const solver);
4057 ~SolutionCollector()
override;
4058 std::string DebugString()
const override {
return "SolutionCollector"; }
4061 void Add(IntVar*
const var);
4062 void Add(
const std::vector<IntVar*>& vars);
4063 void Add(IntervalVar*
const var);
4064 void Add(
const std::vector<IntervalVar*>& vars);
4065 void Add(SequenceVar*
const var);
4066 void Add(
const std::vector<SequenceVar*>& vars);
4067 void AddObjective(IntVar*
const objective);
4070 void EnterSearch()
override;
4073 int solution_count()
const;
4076 Assignment* solution(
int n)
const;
4079 int64 wall_time(
int n)
const;
4082 int64 branches(
int n)
const;
4086 int64 failures(
int n)
const;
4089 int64 objective_value(
int n)
const;
4092 int64 Value(
int n, IntVar*
const var)
const;
4095 int64 StartValue(
int n, IntervalVar*
const var)
const;
4098 int64 EndValue(
int n, IntervalVar*
const var)
const;
4101 int64 DurationValue(
int n, IntervalVar*
const var)
const;
4104 int64 PerformedValue(
int n, IntervalVar*
const var)
const;
4109 const std::vector<int>& ForwardSequence(
int n, SequenceVar*
const var)
const;
4113 const std::vector<int>& BackwardSequence(
int n, SequenceVar*
const var)
const;
4116 const std::vector<int>& Unperformed(
int n, SequenceVar*
const var)
const;
4119 struct SolutionData {
4120 Assignment* solution;
4124 int64 objective_value;
4125 bool operator<(
const SolutionData& other)
const {
4126 return std::tie(solution, time, branches, failures, objective_value) <
4127 std::tie(other.solution, other.time, other.branches,
4128 other.failures, other.objective_value);
4133 void PushSolution();
4134 void Push(
const SolutionData& data) { solution_data_.push_back(data); }
4137 SolutionData BuildSolutionDataForCurrentState();
4138 void FreeSolution(Assignment* solution);
4139 void check_index(
int n)
const;
4141 std::unique_ptr<Assignment> prototype_;
4142 std::vector<SolutionData> solution_data_;
4143 std::vector<Assignment*> recycle_solutions_;
4146 DISALLOW_COPY_AND_ASSIGN(SolutionCollector);
4156 class OptimizeVar :
public SearchMonitor {
4158 OptimizeVar(Solver*
const s,
bool maximize, IntVar*
const a, int64 step);
4159 ~OptimizeVar()
override;
4162 int64 best()
const {
return best_; }
4165 IntVar* Var()
const {
return var_; }
4167 bool AcceptDelta(Assignment* delta, Assignment* deltadelta)
override;
4168 void EnterSearch()
override;
4169 void BeginNextDecision(DecisionBuilder*
const db)
override;
4170 void RefuteDecision(Decision*
const d)
override;
4171 bool AtSolution()
override;
4172 bool AcceptSolution()
override;
4173 virtual std::string Print()
const;
4174 std::string DebugString()
const override;
4175 void Accept(ModelVisitor*
const visitor)
const override;
4184 bool found_initial_solution_;
4187 DISALLOW_COPY_AND_ASSIGN(OptimizeVar);
4191 class SearchLimit :
public SearchMonitor {
4193 explicit SearchLimit(Solver*
const s) : SearchMonitor(s), crossed_(false) {}
4194 ~SearchLimit()
override;
4197 bool crossed()
const {
return crossed_; }
4203 virtual bool Check() = 0;
4206 virtual void Init() = 0;
4210 virtual void Copy(
const SearchLimit*
const limit) = 0;
4213 virtual SearchLimit* MakeClone()
const = 0;
4216 void EnterSearch()
override;
4217 void BeginNextDecision(DecisionBuilder*
const b)
override;
4218 void PeriodicCheck()
override;
4219 void RefuteDecision(Decision*
const d)
override;
4220 std::string DebugString()
const override {
4221 return absl::StrFormat(
"SearchLimit(crossed = %i)", crossed_);
4225 void TopPeriodicCheck();
4228 DISALLOW_COPY_AND_ASSIGN(SearchLimit);
4233 class RegularLimit :
public SearchLimit {
4235 RegularLimit(Solver*
const s, absl::Duration time, int64 branches,
4236 int64 failures, int64 solutions,
bool smart_time_check,
4238 ~RegularLimit()
override;
4239 void Copy(
const SearchLimit*
const limit)
override;
4240 SearchLimit* MakeClone()
const override;
4241 RegularLimit* MakeIdenticalClone()
const;
4242 bool Check()
override;
4243 void Init()
override;
4244 void ExitSearch()
override;
4245 void UpdateLimits(int64 time, int64 branches, int64 failures,
4247 absl::Duration duration_limit()
const {
return duration_limit_; }
4248 int64 wall_time()
const {
4249 return duration_limit_ == absl::InfiniteDuration()
4251 : absl::ToInt64Milliseconds(duration_limit());
4253 int64 branches()
const {
return branches_; }
4254 int64 failures()
const {
return failures_; }
4255 int64 solutions()
const {
return solutions_; }
4256 bool IsUncheckedSolutionLimitReached()
override;
4257 int ProgressPercent()
override;
4258 std::string DebugString()
const override;
4260 absl::Time AbsoluteSolverDeadline()
const {
4261 return solver_time_at_limit_start_ + duration_limit_;
4264 void Accept(ModelVisitor*
const visitor)
const override;
4268 absl::Duration TimeElapsed();
4269 static int64 GetPercent(int64 value, int64 offset, int64 total) {
4270 return (total > 0 && total < kint64max) ? 100 * (value - offset) / total
4274 absl::Duration duration_limit_;
4275 absl::Time solver_time_at_limit_start_;
4276 absl::Duration last_time_elapsed_;
4279 bool smart_time_check_;
4281 int64 branches_offset_;
4283 int64 failures_offset_;
4285 int64 solutions_offset_;
4306 class IntervalVar :
public PropagationBaseObject {
4309 static const int64 kMinValidValue;
4311 static const int64 kMaxValidValue;
4312 IntervalVar(Solver*
const solver,
const std::string& name)
4313 : PropagationBaseObject(solver) {
4316 ~IntervalVar()
override {}
4320 virtual int64 StartMin()
const = 0;
4321 virtual int64 StartMax()
const = 0;
4322 virtual void SetStartMin(int64 m) = 0;
4323 virtual void SetStartMax(int64 m) = 0;
4324 virtual void SetStartRange(int64 mi, int64 ma) = 0;
4325 virtual int64 OldStartMin()
const = 0;
4326 virtual int64 OldStartMax()
const = 0;
4327 virtual void WhenStartRange(Demon*
const d) = 0;
4328 void WhenStartRange(Solver::Closure closure) {
4329 WhenStartRange(solver()->MakeClosureDemon(std::move(closure)));
4332 void WhenStartRange(Solver::Action action) {
4333 WhenStartRange(solver()->MakeActionDemon(std::move(action)));
4336 virtual void WhenStartBound(Demon*
const d) = 0;
4337 void WhenStartBound(Solver::Closure closure) {
4338 WhenStartBound(solver()->MakeClosureDemon(std::move(closure)));
4341 void WhenStartBound(Solver::Action action) {
4342 WhenStartBound(solver()->MakeActionDemon(std::move(action)));
4347 virtual int64 DurationMin()
const = 0;
4348 virtual int64 DurationMax()
const = 0;
4349 virtual void SetDurationMin(int64 m) = 0;
4350 virtual void SetDurationMax(int64 m) = 0;
4351 virtual void SetDurationRange(int64 mi, int64 ma) = 0;
4352 virtual int64 OldDurationMin()
const = 0;
4353 virtual int64 OldDurationMax()
const = 0;
4354 virtual void WhenDurationRange(Demon*
const d) = 0;
4355 void WhenDurationRange(Solver::Closure closure) {
4356 WhenDurationRange(solver()->MakeClosureDemon(std::move(closure)));
4359 void WhenDurationRange(Solver::Action action) {
4360 WhenDurationRange(solver()->MakeActionDemon(std::move(action)));
4363 virtual void WhenDurationBound(Demon*
const d) = 0;
4364 void WhenDurationBound(Solver::Closure closure) {
4365 WhenDurationBound(solver()->MakeClosureDemon(std::move(closure)));
4368 void WhenDurationBound(Solver::Action action) {
4369 WhenDurationBound(solver()->MakeActionDemon(std::move(action)));
4374 virtual int64 EndMin()
const = 0;
4375 virtual int64 EndMax()
const = 0;
4376 virtual void SetEndMin(int64 m) = 0;
4377 virtual void SetEndMax(int64 m) = 0;
4378 virtual void SetEndRange(int64 mi, int64 ma) = 0;
4379 virtual int64 OldEndMin()
const = 0;
4380 virtual int64 OldEndMax()
const = 0;
4381 virtual void WhenEndRange(Demon*
const d) = 0;
4382 void WhenEndRange(Solver::Closure closure) {
4383 WhenEndRange(solver()->MakeClosureDemon(std::move(closure)));
4386 void WhenEndRange(Solver::Action action) {
4387 WhenEndRange(solver()->MakeActionDemon(std::move(action)));
4390 virtual void WhenEndBound(Demon*
const d) = 0;
4391 void WhenEndBound(Solver::Closure closure) {
4392 WhenEndBound(solver()->MakeClosureDemon(std::move(closure)));
4395 void WhenEndBound(Solver::Action action) {
4396 WhenEndBound(solver()->MakeActionDemon(std::move(action)));
4402 virtual bool MustBePerformed()
const = 0;
4403 virtual bool MayBePerformed()
const = 0;
4404 bool CannotBePerformed()
const {
return !MayBePerformed(); }
4405 bool IsPerformedBound()
const {
4406 return MustBePerformed() || !MayBePerformed();
4408 virtual void SetPerformed(
bool val) = 0;
4409 virtual bool WasPerformedBound()
const = 0;
4410 virtual void WhenPerformedBound(Demon*
const d) = 0;
4411 void WhenPerformedBound(Solver::Closure closure) {
4412 WhenPerformedBound(solver()->MakeClosureDemon(std::move(closure)));
4415 void WhenPerformedBound(Solver::Action action) {
4416 WhenPerformedBound(solver()->MakeActionDemon(std::move(action)));
4421 void WhenAnything(Demon*
const d);
4423 void WhenAnything(Solver::Closure closure) {
4424 WhenAnything(solver()->MakeClosureDemon(std::move(closure)));
4427 void WhenAnything(Solver::Action action) {
4429 WhenAnything(solver()->MakeActionDemon(std::move(action)));
4436 virtual IntExpr* StartExpr() = 0;
4437 virtual IntExpr* DurationExpr() = 0;
4438 virtual IntExpr* EndExpr() = 0;
4439 virtual IntExpr* PerformedExpr() = 0;
4443 virtual IntExpr* SafeStartExpr(int64 unperformed_value) = 0;
4444 virtual IntExpr* SafeDurationExpr(int64 unperformed_value) = 0;
4445 virtual IntExpr* SafeEndExpr(int64 unperformed_value) = 0;
4448 virtual void Accept(ModelVisitor*
const visitor)
const = 0;
4451 DISALLOW_COPY_AND_ASSIGN(IntervalVar);
4460 class SequenceVar :
public PropagationBaseObject {
4462 SequenceVar(Solver*
const s,
const std::vector<IntervalVar*>& intervals,
4463 const std::vector<IntVar*>& nexts,
const std::string& name);
4465 ~SequenceVar()
override;
4467 std::string DebugString()
const override;
4470 void DurationRange(int64*
const dmin, int64*
const dmax)
const;
4476 void HorizonRange(int64*
const hmin, int64*
const hmax)
const;
4480 void ActiveHorizonRange(int64*
const hmin, int64*
const hmax)
const;
4483 void ComputeStatistics(
int*
const ranked,
int*
const not_ranked,
4484 int*
const unperformed)
const;
4485 #endif // !defined(SWIG)
4489 void RankFirst(
int index);
4493 void RankNotFirst(
int index);
4497 void RankLast(
int index);
4501 void RankNotLast(
int index);
4505 void ComputePossibleFirstsAndLasts(std::vector<int>*
const possible_firsts,
4506 std::vector<int>*
const possible_lasts);
4513 void RankSequence(
const std::vector<int>& rank_first,
4514 const std::vector<int>& rank_last,
4515 const std::vector<int>& unperformed);
4525 void FillSequence(std::vector<int>*
const rank_first,
4526 std::vector<int>*
const rank_last,
4527 std::vector<int>*
const unperformed)
const;
4530 IntervalVar* Interval(
int index)
const;
4533 IntVar* Next(
int index)
const;
4536 int64 size()
const {
return intervals_.size(); }
4539 virtual void Accept(ModelVisitor*
const visitor)
const;
4542 int ComputeForwardFrontier();
4543 int ComputeBackwardFrontier();
4544 void UpdatePrevious()
const;
4546 const std::vector<IntervalVar*> intervals_;
4547 const std::vector<IntVar*> nexts_;
4548 mutable std::vector<int> previous_;
4551 class AssignmentElement {
4553 AssignmentElement() : activated_(true) {}
4555 void Activate() { activated_ =
true; }
4556 void Deactivate() { activated_ =
false; }
4557 bool Activated()
const {
return activated_; }
4563 class IntVarElement :
public AssignmentElement {
4566 explicit IntVarElement(IntVar*
const var);
4567 void Reset(IntVar*
const var);
4568 IntVarElement* Clone();
4569 void Copy(
const IntVarElement& element);
4570 IntVar* Var()
const {
return var_; }
4576 if (var_ !=
nullptr) {
4577 var_->SetRange(min_, max_);
4580 void LoadFromProto(
const IntVarAssignment& int_var_assignment_proto);
4581 void WriteToProto(IntVarAssignment* int_var_assignment_proto)
const;
4583 int64 Min()
const {
return min_; }
4584 void SetMin(int64 m) { min_ = m; }
4585 int64 Max()
const {
return max_; }
4586 void SetMax(int64 m) { max_ = m; }
4587 int64 Value()
const {
4588 DCHECK_EQ(min_, max_);
4592 bool Bound()
const {
return (max_ == min_); }
4593 void SetRange(int64 l, int64 u) {
4597 void SetValue(int64 v) {
4601 std::string DebugString()
const;
4603 bool operator==(
const IntVarElement& element)
const;
4604 bool operator!=(
const IntVarElement& element)
const {
4605 return !(*
this == element);
4614 class IntervalVarElement :
public AssignmentElement {
4616 IntervalVarElement();
4617 explicit IntervalVarElement(IntervalVar*
const var);
4618 void Reset(IntervalVar*
const var);
4619 IntervalVarElement* Clone();
4620 void Copy(
const IntervalVarElement& element);
4621 IntervalVar* Var()
const {
return var_; }
4625 const IntervalVarAssignment& interval_var_assignment_proto);
4626 void WriteToProto(IntervalVarAssignment* interval_var_assignment_proto)
const;
4628 int64 StartMin()
const {
return start_min_; }
4629 int64 StartMax()
const {
return start_max_; }
4630 int64 StartValue()
const {
4631 CHECK_EQ(start_max_, start_min_);
4634 int64 DurationMin()
const {
return duration_min_; }
4635 int64 DurationMax()
const {
return duration_max_; }
4636 int64 DurationValue()
const {
4637 CHECK_EQ(duration_max_, duration_min_);
4638 return duration_max_;
4640 int64 EndMin()
const {
return end_min_; }
4641 int64 EndMax()
const {
return end_max_; }
4642 int64 EndValue()
const {
4643 CHECK_EQ(end_max_, end_min_);
4646 int64 PerformedMin()
const {
return performed_min_; }
4647 int64 PerformedMax()
const {
return performed_max_; }
4648 int64 PerformedValue()
const {
4649 CHECK_EQ(performed_max_, performed_min_);
4650 return performed_max_;
4652 void SetStartMin(int64 m) { start_min_ = m; }
4653 void SetStartMax(int64 m) { start_max_ = m; }
4654 void SetStartRange(int64 mi, int64 ma) {
4658 void SetStartValue(int64 v) {
4662 void SetDurationMin(int64 m) { duration_min_ = m; }
4663 void SetDurationMax(int64 m) { duration_max_ = m; }
4664 void SetDurationRange(int64 mi, int64 ma) {
4668 void SetDurationValue(int64 v) {
4672 void SetEndMin(int64 m) { end_min_ = m; }
4673 void SetEndMax(int64 m) { end_max_ = m; }
4674 void SetEndRange(int64 mi, int64 ma) {
4678 void SetEndValue(int64 v) {
4682 void SetPerformedMin(int64 m) { performed_min_ = m; }
4683 void SetPerformedMax(int64 m) { performed_max_ = m; }
4684 void SetPerformedRange(int64 mi, int64 ma) {
4685 performed_min_ = mi;
4686 performed_max_ = ma;
4688 void SetPerformedValue(int64 v) {
4692 bool Bound()
const {
4693 return (start_min_ == start_max_ && duration_min_ == duration_max_ &&
4694 end_min_ == end_max_ && performed_min_ == performed_max_);
4696 std::string DebugString()
const;
4697 bool operator==(
const IntervalVarElement& element)
const;
4698 bool operator!=(
const IntervalVarElement& element)
const {
4699 return !(*
this == element);
4705 int64 duration_min_;
4706 int64 duration_max_;
4709 int64 performed_min_;
4710 int64 performed_max_;
4727 class SequenceVarElement :
public AssignmentElement {
4729 SequenceVarElement();
4730 explicit SequenceVarElement(SequenceVar*
const var);
4731 void Reset(SequenceVar*
const var);
4732 SequenceVarElement* Clone();
4733 void Copy(
const SequenceVarElement& element);
4734 SequenceVar* Var()
const {
return var_; }
4738 const SequenceVarAssignment& sequence_var_assignment_proto);
4739 void WriteToProto(SequenceVarAssignment* sequence_var_assignment_proto)
const;
4741 const std::vector<int>& ForwardSequence()
const;
4742 const std::vector<int>& BackwardSequence()
const;
4743 const std::vector<int>& Unperformed()
const;
4744 void SetSequence(
const std::vector<int>& forward_sequence,
4745 const std::vector<int>& backward_sequence,
4746 const std::vector<int>& unperformed);
4747 void SetForwardSequence(
const std::vector<int>& forward_sequence);
4748 void SetBackwardSequence(
const std::vector<int>& backward_sequence);
4749 void SetUnperformed(
const std::vector<int>& unperformed);
4750 bool Bound()
const {
4751 return forward_sequence_.size() + unperformed_.size() == var_->size();
4754 std::string DebugString()
const;
4756 bool operator==(
const SequenceVarElement& element)
const;
4757 bool operator!=(
const SequenceVarElement& element)
const {
4758 return !(*
this == element);
4762 bool CheckClassInvariants();
4765 std::vector<int> forward_sequence_;
4766 std::vector<int> backward_sequence_;
4767 std::vector<int> unperformed_;
4770 template <
class V,
class E>
4771 class AssignmentContainer {
4773 AssignmentContainer() {}
4775 CHECK(var !=
nullptr);
4777 if (!Find(var, &index)) {
4778 return FastAdd(var);
4780 return &elements_[index];
4784 E* FastAdd(V* var) {
4785 DCHECK(var !=
nullptr);
4786 elements_.emplace_back(var);
4787 return &elements_.back();
4791 E* AddAtPosition(V* var,
int position) {
4792 elements_[position].Reset(var);
4793 return &elements_[position];
4797 if (!elements_map_.empty()) {
4798 elements_map_.clear();
4803 void Resize(
size_t size) { elements_.resize(size); }
4804 bool Empty()
const {
return elements_.empty(); }
4807 void CopyIntersection(
const AssignmentContainer<V, E>& container) {
4808 for (
int i = 0; i < container.elements_.size(); ++i) {
4809 const E& element = container.elements_[i];
4810 const V*
const var = element.Var();
4812 if (i < elements_.size() && elements_[i].Var() == var) {
4814 }
else if (!Find(var, &index)) {
4817 DCHECK_GE(index, 0);
4818 E*
const local_element = &elements_[index];
4819 local_element->Copy(element);
4820 if (element.Activated()) {
4821 local_element->Activate();
4823 local_element->Deactivate();
4829 void Copy(
const AssignmentContainer<V, E>& container) {
4831 for (
int i = 0; i < container.elements_.size(); ++i) {
4832 const E& element = container.elements_[i];
4833 FastAdd(element.Var())->Copy(element);
4836 bool Contains(
const V*
const var)
const {
4838 return Find(var, &index);
4840 E* MutableElement(
const V*
const var) {
4841 E*
const element = MutableElementOrNull(var);
4842 DCHECK(element !=
nullptr)
4843 <<
"Unknown variable " << var->DebugString() <<
" in solution";
4846 E* MutableElementOrNull(
const V*
const var) {
4848 if (Find(var, &index)) {
4849 return MutableElement(index);
4853 const E& Element(
const V*
const var)
const {
4854 const E*
const element = ElementPtrOrNull(var);
4855 DCHECK(element !=
nullptr)
4856 <<
"Unknown variable " << var->DebugString() <<
" in solution";
4859 const E* ElementPtrOrNull(
const V*
const var)
const {
4861 if (Find(var, &index)) {
4862 return &Element(index);
4866 const std::vector<E>& elements()
const {
return elements_; }
4867 E* MutableElement(
int index) {
return &elements_[index]; }
4868 const E& Element(
int index)
const {
return elements_[index]; }
4869 int Size()
const {
return elements_.size(); }
4871 for (E& element : elements_) {
4876 for (E& element : elements_) {
4877 if (element.Activated()) {
4882 bool AreAllElementsBound()
const {
4883 for (
const E& element : elements_) {
4884 if (!element.Bound())
return false;
4892 bool operator==(
const AssignmentContainer<V, E>& container)
const {
4894 if (Size() != container.Size()) {
4898 EnsureMapIsUpToDate();
4902 for (
const E& element : container.elements_) {
4903 const int position =
4904 gtl::FindWithDefault(elements_map_, element.Var(), -1);
4905 if (position < 0 || elements_[position] != element) {
4911 bool operator!=(
const AssignmentContainer<V, E>& container)
const {
4912 return !(*
this == container);
4916 void EnsureMapIsUpToDate()
const {
4917 absl::flat_hash_map<const V*, int>* map =
4918 const_cast<absl::flat_hash_map<const V*, int>*
>(&elements_map_);
4919 for (
int i = map->size(); i < elements_.size(); ++i) {
4920 (*map)[elements_[i].Var()] = i;
4923 bool Find(
const V*
const var,
int* index)
const {
4925 const size_t kMaxSizeForLinearAccess = 11;
4926 if (Size() <= kMaxSizeForLinearAccess) {
4930 for (
int i = 0; i < elements_.size(); ++i) {
4931 if (var == elements_[i].Var()) {
4938 EnsureMapIsUpToDate();
4939 DCHECK_EQ(elements_map_.size(), elements_.size());
4940 return gtl::FindCopy(elements_map_, var, index);
4944 std::vector<E> elements_;
4945 absl::flat_hash_map<const V*, int> elements_map_;
4950 class Assignment :
public PropagationBaseObject {
4952 typedef AssignmentContainer<IntVar, IntVarElement> IntContainer;
4953 typedef AssignmentContainer<IntervalVar, IntervalVarElement>
4955 typedef AssignmentContainer<SequenceVar, SequenceVarElement>
4958 explicit Assignment(Solver*
const s);
4959 explicit Assignment(
const Assignment*
const copy);
4960 ~Assignment()
override;
4963 bool Empty()
const {
4964 return int_var_container_.Empty() && interval_var_container_.Empty() &&
4965 sequence_var_container_.Empty();
4968 return NumIntVars() + NumIntervalVars() + NumSequenceVars();
4970 int NumIntVars()
const {
return int_var_container_.Size(); }
4971 int NumIntervalVars()
const {
return interval_var_container_.Size(); }
4972 int NumSequenceVars()
const {
return sequence_var_container_.Size(); }
4978 bool Load(
const std::string& filename);
4980 bool Load(File* file);
4982 void Load(const AssignmentProto& assignment_proto);
4983 bool Save(
const std::string& filename)
const;
4986 bool Save(File* file)
const;
4987 #endif // #if !defined(SWIG)
4988 void Save(AssignmentProto*
const assignment_proto)
const;
4990 void AddObjective(IntVar*
const v);
4991 void ClearObjective() { objective_element_.Reset(
nullptr); }
4992 IntVar* Objective()
const;
4993 bool HasObjective()
const {
return (objective_element_.Var() !=
nullptr); }
4994 int64 ObjectiveMin()
const;
4995 int64 ObjectiveMax()
const;
4996 int64 ObjectiveValue()
const;
4997 bool ObjectiveBound()
const;
4998 void SetObjectiveMin(int64 m);
4999 void SetObjectiveMax(int64 m);
5000 void SetObjectiveValue(int64 value);
5001 void SetObjectiveRange(int64 l, int64 u);
5003 IntVarElement* Add(IntVar*
const var);
5004 void Add(
const std::vector<IntVar*>& vars);
5006 IntVarElement* FastAdd(IntVar*
const var);
5007 int64 Min(
const IntVar*
const var)
const;
5008 int64 Max(
const IntVar*
const var)
const;
5009 int64 Value(
const IntVar*
const var)
const;
5010 bool Bound(
const IntVar*
const var)
const;
5011 void SetMin(
const IntVar*
const var, int64 m);
5012 void SetMax(
const IntVar*
const var, int64 m);
5013 void SetRange(
const IntVar*
const var, int64 l, int64 u);
5014 void SetValue(
const IntVar*
const var, int64 value);
5016 IntervalVarElement* Add(IntervalVar*
const var);
5017 void Add(
const std::vector<IntervalVar*>& vars);
5019 IntervalVarElement* FastAdd(IntervalVar*
const var);
5020 int64 StartMin(
const IntervalVar*
const var)
const;
5021 int64 StartMax(
const IntervalVar*
const var)
const;
5022 int64 StartValue(
const IntervalVar*
const var)
const;
5023 int64 DurationMin(
const IntervalVar*
const var)
const;
5024 int64 DurationMax(
const IntervalVar*
const var)
const;
5025 int64 DurationValue(
const IntervalVar*
const var)
const;
5026 int64 EndMin(
const IntervalVar*
const var)
const;
5027 int64 EndMax(
const IntervalVar*
const var)
const;
5028 int64 EndValue(
const IntervalVar*
const var)
const;
5029 int64 PerformedMin(
const IntervalVar*
const var)
const;
5030 int64 PerformedMax(
const IntervalVar*
const var)
const;
5031 int64 PerformedValue(
const IntervalVar*
const var)
const;
5032 void SetStartMin(
const IntervalVar*
const var, int64 m);
5033 void SetStartMax(
const IntervalVar*
const var, int64 m);
5034 void SetStartRange(
const IntervalVar*
const var, int64 mi, int64 ma);
5035 void SetStartValue(
const IntervalVar*
const var, int64 value);
5036 void SetDurationMin(
const IntervalVar*
const var, int64 m);
5037 void SetDurationMax(
const IntervalVar*
const var, int64 m);
5038 void SetDurationRange(
const IntervalVar*
const var, int64 mi, int64 ma);
5039 void SetDurationValue(
const IntervalVar*
const var, int64 value);
5040 void SetEndMin(
const IntervalVar*
const var, int64 m);
5041 void SetEndMax(
const IntervalVar*
const var, int64 m);
5042 void SetEndRange(
const IntervalVar*
const var, int64 mi, int64 ma);
5043 void SetEndValue(
const IntervalVar*
const var, int64 value);
5044 void SetPerformedMin(
const IntervalVar*
const var, int64 m);
5045 void SetPerformedMax(
const IntervalVar*
const var, int64 m);
5046 void SetPerformedRange(
const IntervalVar*
const var, int64 mi, int64 ma);
5047 void SetPerformedValue(
const IntervalVar*
const var, int64 value);
5049 SequenceVarElement* Add(SequenceVar*
const var);
5050 void Add(
const std::vector<SequenceVar*>& vars);
5052 SequenceVarElement* FastAdd(SequenceVar*
const var);
5053 const std::vector<int>& ForwardSequence(
const SequenceVar*
const var)
const;
5054 const std::vector<int>& BackwardSequence(
const SequenceVar*
const var)
const;
5055 const std::vector<int>& Unperformed(
const SequenceVar*
const var)
const;
5056 void SetSequence(
const SequenceVar*
const var,
5057 const std::vector<int>& forward_sequence,
5058 const std::vector<int>& backward_sequence,
5059 const std::vector<int>& unperformed);
5060 void SetForwardSequence(
const SequenceVar*
const var,
5061 const std::vector<int>& forward_sequence);
5062 void SetBackwardSequence(
const SequenceVar*
const var,
5063 const std::vector<int>& backward_sequence);
5064 void SetUnperformed(
const SequenceVar*
const var,
5065 const std::vector<int>& unperformed);
5067 void Activate(
const IntVar*
const var);
5068 void Deactivate(
const IntVar*
const var);
5069 bool Activated(
const IntVar*
const var)
const;
5071 void Activate(
const IntervalVar*
const var);
5072 void Deactivate(
const IntervalVar*
const var);
5073 bool Activated(
const IntervalVar*
const var)
const;
5075 void Activate(
const SequenceVar*
const var);
5076 void Deactivate(
const SequenceVar*
const var);
5077 bool Activated(
const SequenceVar*
const var)
const;
5079 void ActivateObjective();
5080 void DeactivateObjective();
5081 bool ActivatedObjective()
const;
5083 std::string DebugString()
const override;
5085 bool AreAllElementsBound()
const {
5086 return int_var_container_.AreAllElementsBound() &&
5087 interval_var_container_.AreAllElementsBound() &&
5088 sequence_var_container_.AreAllElementsBound();
5091 bool Contains(
const IntVar*
const var)
const;
5092 bool Contains(
const IntervalVar*
const var)
const;
5093 bool Contains(
const SequenceVar*
const var)
const;
5095 void CopyIntersection(
const Assignment* assignment);
5098 void Copy(
const Assignment* assignment);
5101 const IntContainer& IntVarContainer()
const {
return int_var_container_; }
5102 IntContainer* MutableIntVarContainer() {
return &int_var_container_; }
5103 const IntervalContainer& IntervalVarContainer()
const {
5104 return interval_var_container_;
5106 IntervalContainer* MutableIntervalVarContainer() {
5107 return &interval_var_container_;
5109 const SequenceContainer& SequenceVarContainer()
const {
5110 return sequence_var_container_;
5112 SequenceContainer* MutableSequenceVarContainer() {
5113 return &sequence_var_container_;
5115 bool operator==(
const Assignment& assignment)
const {
5116 return int_var_container_ == assignment.int_var_container_ &&
5117 interval_var_container_ == assignment.interval_var_container_ &&
5118 sequence_var_container_ == assignment.sequence_var_container_ &&
5119 objective_element_ == assignment.objective_element_;
5121 bool operator!=(
const Assignment& assignment)
const {
5122 return !(*
this == assignment);
5126 IntContainer int_var_container_;
5127 IntervalContainer interval_var_container_;
5128 SequenceContainer sequence_var_container_;
5129 IntVarElement objective_element_;
5130 DISALLOW_COPY_AND_ASSIGN(Assignment);
5133 std::ostream& operator<<(std::ostream& out,
5134 const Assignment& assignment);
5141 void SetAssignmentFromAssignment(Assignment* target_assignment,
5142 const std::vector<IntVar*>& target_vars,
5143 const Assignment* source_assignment,
5144 const std::vector<IntVar*>& source_vars);
5146 class Pack :
public Constraint {
5148 Pack(Solver*
const s,
const std::vector<IntVar*>& vars,
int number_of_bins);
5160 void AddWeightedSumLessOrEqualConstantDimension(
5161 const std::vector<int64>& weights,
const std::vector<int64>& bounds);
5167 void AddWeightedSumLessOrEqualConstantDimension(
5168 Solver::IndexEvaluator1 weights,
const std::vector<int64>& bounds);
5174 void AddWeightedSumLessOrEqualConstantDimension(
5175 Solver::IndexEvaluator2 weights,
const std::vector<int64>& bounds);
5179 void AddWeightedSumEqualVarDimension(
const std::vector<int64>& weights,
5180 const std::vector<IntVar*>& loads);
5185 void AddWeightedSumEqualVarDimension(Solver::IndexEvaluator2 weights,
5186 const std::vector<IntVar*>& loads);
5197 void AddSumVariableWeightsLessOrEqualConstantDimension(
5198 const std::vector<IntVar*>& usage,
const std::vector<int64>& capacity);
5202 void AddWeightedSumOfAssignedDimension(
const std::vector<int64>& weights,
5203 IntVar*
const cost_var);
5207 void AddCountUsedBinDimension(IntVar*
const count_var);
5211 void AddCountAssignedItemsDimension(IntVar*
const count_var);
5213 void Post()
override;
5215 void PropagateDelayed();
5216 void InitialPropagate()
override;
5218 void OneDomain(
int var_index);
5219 std::string DebugString()
const override;
5220 bool IsUndecided(
int var_index,
int bin_index)
const;
5221 void SetImpossible(
int var_index,
int bin_index);
5222 void Assign(
int var_index,
int bin_index);
5223 bool IsAssignedStatusKnown(
int var_index)
const;
5224 bool IsPossible(
int var_index,
int bin_index)
const;
5225 IntVar* AssignVar(
int var_index,
int bin_index)
const;
5226 void SetAssigned(
int var_index);
5227 void SetUnassigned(
int var_index);
5228 void RemoveAllPossibleFromBin(
int bin_index);
5229 void AssignAllPossibleToBin(
int bin_index);
5230 void AssignFirstPossibleToBin(
int bin_index);
5231 void AssignAllRemainingItems();
5232 void UnassignAllRemainingItems();
5233 void Accept(ModelVisitor*
const visitor)
const override;
5236 bool IsInProcess()
const;
5237 const std::vector<IntVar*> vars_;
5239 std::vector<Dimension*> dims_;
5240 std::unique_ptr<RevBitMatrix> unprocessed_;
5241 std::vector<std::vector<int>> forced_;
5242 std::vector<std::vector<int>> removed_;
5243 std::vector<IntVarIterator*> holes_;
5246 std::vector<std::pair<int, int>> to_set_;
5247 std::vector<std::pair<int, int>> to_unset_;
5251 class DisjunctiveConstraint :
public Constraint {
5253 DisjunctiveConstraint(Solver*
const s,
5254 const std::vector<IntervalVar*>& intervals,
5255 const std::string& name);
5256 ~DisjunctiveConstraint()
override;
5259 virtual SequenceVar* MakeSequenceVar() = 0;
5265 void SetTransitionTime(Solver::IndexEvaluator2 transition_time);
5267 int64 TransitionTime(
int before_index,
int after_index) {
5268 DCHECK(transition_time_);
5269 return transition_time_(before_index, after_index);
5273 virtual const std::vector<IntVar*>& nexts()
const = 0;
5274 virtual const std::vector<IntVar*>& actives()
const = 0;
5275 virtual const std::vector<IntVar*>& time_cumuls()
const = 0;
5276 virtual const std::vector<IntVar*>& time_slacks()
const = 0;
5277 #endif // !defined(SWIG)
5280 const std::vector<IntervalVar*> intervals_;
5281 Solver::IndexEvaluator2 transition_time_;
5284 DISALLOW_COPY_AND_ASSIGN(DisjunctiveConstraint);
5289 class SolutionPool :
public BaseObject {
5292 ~SolutionPool()
override {}
5296 virtual void Initialize(Assignment*
const assignment) = 0;
5300 virtual void RegisterNewSolution(Assignment*
const assignment) = 0;
5304 virtual void GetNextSolution(Assignment*
const assignment) = 0;
5308 virtual bool SyncNeeded(Assignment*
const local_assignment) = 0;
5312 #endif // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_