OR-Tools  8.2
constraint_solver.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
67 
68 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
69 #define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
70 
71 #include <functional>
72 #include <iosfwd>
73 #include <memory>
74 #include <random>
75 #include <string>
76 #include <utility>
77 #include <vector>
78 
79 #include "absl/base/macros.h"
80 #include "absl/container/flat_hash_map.h"
81 #include "absl/container/flat_hash_set.h"
82 #include "absl/random/distributions.h"
83 #include "absl/random/random.h"
84 #include "absl/strings/str_format.h"
86 #include "ortools/base/hash.h"
88 #include "ortools/base/logging.h"
89 #include "ortools/base/macros.h"
90 #include "ortools/base/map_util.h"
91 #include "ortools/base/sysinfo.h"
92 #include "ortools/base/timer.h"
93 #include "ortools/constraint_solver/routing_parameters.pb.h"
94 #include "ortools/constraint_solver/search_stats.pb.h"
95 #include "ortools/constraint_solver/solver_parameters.pb.h"
98 #include "ortools/util/tuple_set.h"
99 
100 #if !defined(SWIG)
101 ABSL_DECLARE_FLAG(int64, cp_random_seed);
102 #endif // !defined(SWIG)
103 
104 class File;
105 
106 namespace operations_research {
107 
108 class Assignment;
109 class AssignmentProto;
110 class BaseObject;
111 class CpArgument;
112 class CpConstraint;
113 class CpIntegerExpression;
114 class CpIntervalVariable;
115 class CpSequenceVariable;
116 class CastConstraint;
117 class Constraint;
118 class Decision;
119 class DecisionBuilder;
120 class DecisionVisitor;
121 class Demon;
122 class DemonProfiler;
123 class LocalSearchProfiler;
124 class Dimension;
125 class DisjunctiveConstraint;
126 class ExpressionCache;
127 class IntExpr;
128 class IntTupleSet;
129 class IntVar;
130 class IntVarAssignment;
131 class IntVarElement;
132 class IntervalVar;
133 class IntervalVarAssignment;
134 class IntervalVarElement;
135 class IntVarLocalSearchFilter;
136 class LocalSearchFilter;
137 class LocalSearchFilterManager;
138 class LocalSearchOperator;
139 class LocalSearchPhaseParameters;
140 class ModelCache;
141 class ModelVisitor;
142 class OptimizeVar;
143 class Pack;
144 class PropagationBaseObject;
145 class PropagationMonitor;
146 class LocalSearchMonitor;
147 class Queue;
148 class RevBitMatrix;
149 class RevBitSet;
150 class RegularLimit;
151 class RegularLimitParameters;
152 class Search;
153 class ImprovementSearchLimit;
154 class SearchLimit;
155 class SearchMonitor;
156 class SequenceVar;
157 class SequenceVarAssignment;
158 class SolutionCollector;
159 class SolutionPool;
160 class Solver;
161 class ConstraintSolverParameters;
162 class SymmetryBreaker;
163 struct StateInfo;
164 struct Trail;
165 template <class T>
166 class SimpleRevFIFO;
167 
168 inline int64 CpRandomSeed() {
169  return absl::GetFlag(FLAGS_cp_random_seed) == -1
170  ? absl::Uniform<int64>(absl::BitGen(), 0, kint64max)
171  : absl::GetFlag(FLAGS_cp_random_seed);
172 }
173 
178  public:
183  };
184 
188  };
189 
190  enum DisplayLevel { NONE = 0, NORMAL = 1, VERBOSE = 2 };
191 
195 
198 
202 
207 
212 
215 
219 
222 
226 
229 
232 
234 };
235 
253 class Solver {
254  public:
261  : variable(nullptr), expression(nullptr), maintainer(nullptr) {}
262  IntegerCastInfo(IntVar* const v, IntExpr* const e, Constraint* const c)
263  : variable(v), expression(e), maintainer(c) {}
267  };
268 
270  static constexpr int kNumPriorities = 3;
271 
277 
280 
285 
288 
296 
304 
312 
320 
326 
332 
337 
342 
346 
350  };
351  // TODO(user): add HIGHEST_MIN and LOWEST_MAX.
352 
358 
361 
364 
367 
370 
375 
379 
383  };
384 
401 
407  };
408 
415  };
416 
430  };
431 
445 
461 
464 
473 
484 
492 
499 
507 
514 
526 
535 
539 
544 
554 
559 
567  SIMPLELNS
568  };
569 
577  LK,
578 
586 
593  TSPLNS
594  };
595 
602  GE,
604  LE,
607  EQ
608  };
609 
617 
620 
623  };
624 
630 
633 
636 
639 
642 
645 
648 
651 
656  };
657 
663 
666 
669 
672 
675 
678 
683 
687  AVOID_DATE
688  };
689 
699 
704 
709 
713 
717  };
718 
722 
724  enum SolverState {
737  };
738 
741 
743  typedef std::function<int64(int64)> IndexEvaluator1;
744  typedef std::function<int64(int64, int64)> IndexEvaluator2;
745  typedef std::function<int64(int64, int64, int64)> IndexEvaluator3;
746 
747  typedef std::function<bool(int64)> IndexFilter1;
748 
749  typedef std::function<IntVar*(int64)> Int64ToIntVar;
750 
751  typedef std::function<int64(Solver* solver, const std::vector<IntVar*>& vars,
752  int64 first_unbound, int64 last_unbound)>
754 
755  typedef std::function<int64(const IntVar* v, int64 id)> VariableValueSelector;
756  typedef std::function<bool(int64, int64, int64)> VariableValueComparator;
757  typedef std::function<DecisionModification()> BranchSelector;
758  // TODO(user): wrap in swig.
759  typedef std::function<void(Solver*)> Action;
760  typedef std::function<void()> Closure;
761 
763  explicit Solver(const std::string& name);
764  Solver(const std::string& name, const ConstraintSolverParameters& parameters);
765  ~Solver();
766 
768  ConstraintSolverParameters parameters() const { return parameters_; }
770  // TODO(user): Move to constraint_solver_parameters.h.
771  static ConstraintSolverParameters DefaultSolverParameters();
772 
774 
778  template <class T>
779  void SaveValue(T* o) {
780  InternalSaveValue(o);
781  }
782 
795  template <typename T>
796  T* RevAlloc(T* object) {
797  return reinterpret_cast<T*>(SafeRevAlloc(object));
798  }
799 
806  template <typename T>
807  T* RevAllocArray(T* object) {
808  return reinterpret_cast<T*>(SafeRevAllocArray(object));
809  }
810 
844  void AddConstraint(Constraint* const c);
848  void AddCastConstraint(CastConstraint* const constraint,
849  IntVar* const target_var, IntExpr* const expr);
850 
892  bool Solve(DecisionBuilder* const db,
893  const std::vector<SearchMonitor*>& monitors);
894  bool Solve(DecisionBuilder* const db);
895  bool Solve(DecisionBuilder* const db, SearchMonitor* const m1);
896  bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
897  SearchMonitor* const m2);
898  bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
899  SearchMonitor* const m2, SearchMonitor* const m3);
900  bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
901  SearchMonitor* const m2, SearchMonitor* const m3,
902  SearchMonitor* const m4);
904 
913 
914  void NewSearch(DecisionBuilder* const db,
915  const std::vector<SearchMonitor*>& monitors);
916  void NewSearch(DecisionBuilder* const db);
917  void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1);
918  void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
919  SearchMonitor* const m2);
920  void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
921  SearchMonitor* const m2, SearchMonitor* const m3);
922  void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
923  SearchMonitor* const m2, SearchMonitor* const m3,
924  SearchMonitor* const m4);
925 
926  bool NextSolution();
927  void RestartSearch();
928  void EndSearch();
930 
939  bool SolveAndCommit(DecisionBuilder* const db,
940  const std::vector<SearchMonitor*>& monitors);
941  bool SolveAndCommit(DecisionBuilder* const db);
942  bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1);
943  bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1,
944  SearchMonitor* const m2);
945  bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1,
946  SearchMonitor* const m2, SearchMonitor* const m3);
947 
949  bool CheckAssignment(Assignment* const solution);
950 
954  bool CheckConstraint(Constraint* const ct);
955 
957  SolverState state() const { return state_; }
958 
960  void Fail();
961 
962 #if !defined(SWIG)
967  void AddBacktrackAction(Action a, bool fast);
968 #endif
969 
971  std::string DebugString() const;
972 
974  static int64 MemoryUsage();
975 
980  absl::Time Now() const;
981 
984  int64 wall_time() const;
985 
987  int64 branches() const { return branches_; }
988 
990  int64 solutions() const;
991 
993  int64 unchecked_solutions() const;
994 
996  int64 demon_runs(DemonPriority p) const { return demon_runs_[p]; }
997 
999  int64 failures() const { return fails_; }
1000 
1002  int64 neighbors() const { return neighbors_; }
1003 
1005  int64 filtered_neighbors() const { return filtered_neighbors_; }
1006 
1008  int64 accepted_neighbors() const { return accepted_neighbors_; }
1009 
1012  uint64 stamp() const;
1013 
1015  uint64 fail_stamp() const;
1016 
1019  return optimization_direction_;
1020  }
1022  optimization_direction_ = direction;
1023  }
1024 
1025  // All factories (MakeXXX methods) encapsulate creation of objects
1026  // through RevAlloc(). Hence, the Solver used for allocating the
1027  // returned object will retain ownership of the allocated memory.
1028  // Destructors are called upon backtrack, or when the Solver is
1029  // itself destructed.
1030 
1031  // ----- Int Variables and Constants -----
1032 
1034  IntVar* MakeIntVar(int64 min, int64 max, const std::string& name);
1035 
1037  IntVar* MakeIntVar(const std::vector<int64>& values, const std::string& name);
1038 
1040  IntVar* MakeIntVar(const std::vector<int>& values, const std::string& name);
1041 
1044 
1046  IntVar* MakeIntVar(const std::vector<int64>& values);
1047 
1049  IntVar* MakeIntVar(const std::vector<int>& values);
1050 
1052  IntVar* MakeBoolVar(const std::string& name);
1053 
1055  IntVar* MakeBoolVar();
1056 
1058  IntVar* MakeIntConst(int64 val, const std::string& name);
1059 
1061  IntVar* MakeIntConst(int64 val);
1062 
1066  void MakeIntVarArray(int var_count, int64 vmin, int64 vmax,
1067  const std::string& name, std::vector<IntVar*>* vars);
1070  void MakeIntVarArray(int var_count, int64 vmin, int64 vmax,
1071  std::vector<IntVar*>* vars);
1073  IntVar** MakeIntVarArray(int var_count, int64 vmin, int64 vmax,
1074  const std::string& name);
1075 
1079  void MakeBoolVarArray(int var_count, const std::string& name,
1080  std::vector<IntVar*>* vars);
1083  void MakeBoolVarArray(int var_count, std::vector<IntVar*>* vars);
1085  IntVar** MakeBoolVarArray(int var_count, const std::string& name);
1086 
1087  // ----- Integer Expressions -----
1088 
1090  IntExpr* MakeSum(IntExpr* const left, IntExpr* const right);
1092  IntExpr* MakeSum(IntExpr* const expr, int64 value);
1094  IntExpr* MakeSum(const std::vector<IntVar*>& vars);
1095 
1097  IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1098  const std::vector<int64>& coefs);
1100  IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1101  const std::vector<int>& coefs);
1102 
1104  IntExpr* MakeDifference(IntExpr* const left, IntExpr* const right);
1106  IntExpr* MakeDifference(int64 value, IntExpr* const expr);
1108  IntExpr* MakeOpposite(IntExpr* const expr);
1109 
1111  IntExpr* MakeProd(IntExpr* const left, IntExpr* const right);
1113  IntExpr* MakeProd(IntExpr* const expr, int64 value);
1114 
1116  IntExpr* MakeDiv(IntExpr* const expr, int64 value);
1118  IntExpr* MakeDiv(IntExpr* const numerator, IntExpr* const denominator);
1119 
1121  IntExpr* MakeAbs(IntExpr* const expr);
1123  IntExpr* MakeSquare(IntExpr* const expr);
1125  IntExpr* MakePower(IntExpr* const expr, int64 n);
1126 
1128  IntExpr* MakeElement(const std::vector<int64>& values, IntVar* const index);
1130  IntExpr* MakeElement(const std::vector<int>& values, IntVar* const index);
1131 
1135  IntExpr* MakeElement(IndexEvaluator1 values, IntVar* const index);
1142  IntExpr* MakeMonotonicElement(IndexEvaluator1 values, bool increasing,
1143  IntVar* const index);
1145  IntExpr* MakeElement(IndexEvaluator2 values, IntVar* const index1,
1146  IntVar* const index2);
1147 
1149  IntExpr* MakeElement(const std::vector<IntVar*>& vars, IntVar* const index);
1150 
1151 #if !defined(SWIG)
1153  IntExpr* MakeElement(Int64ToIntVar vars, int64 range_start, int64 range_end,
1154  IntVar* argument);
1155 #endif // SWIG
1156 
1159  IntExpr* MakeIndexExpression(const std::vector<IntVar*>& vars, int64 value);
1160 
1162  Constraint* MakeIfThenElseCt(IntVar* const condition,
1163  IntExpr* const then_expr,
1164  IntExpr* const else_expr,
1165  IntVar* const target_var);
1166 
1168  IntExpr* MakeMin(const std::vector<IntVar*>& vars);
1170  IntExpr* MakeMin(IntExpr* const left, IntExpr* const right);
1172  IntExpr* MakeMin(IntExpr* const expr, int64 value);
1174  IntExpr* MakeMin(IntExpr* const expr, int value);
1175 
1177  IntExpr* MakeMax(const std::vector<IntVar*>& vars);
1179  IntExpr* MakeMax(IntExpr* const left, IntExpr* const right);
1181  IntExpr* MakeMax(IntExpr* const expr, int64 value);
1183  IntExpr* MakeMax(IntExpr* const expr, int value);
1184 
1186  IntExpr* MakeConvexPiecewiseExpr(IntExpr* expr, int64 early_cost,
1187  int64 early_date, int64 late_date,
1188  int64 late_cost);
1189 
1192  IntExpr* MakeSemiContinuousExpr(IntExpr* const expr, int64 fixed_charge,
1193  int64 step);
1194 
1197  // TODO(user): Investigate if we can merge all three piecewise linear
1199 #ifndef SWIG
1201  const PiecewiseLinearFunction& f);
1202 #endif
1203 
1205  IntExpr* MakeModulo(IntExpr* const x, int64 mod);
1206 
1208  IntExpr* MakeModulo(IntExpr* const x, IntExpr* const mod);
1209 
1211  IntExpr* MakeConditionalExpression(IntVar* const condition,
1212  IntExpr* const expr,
1213  int64 unperformed_value);
1214 
1219  Constraint* MakeFalseConstraint(const std::string& explanation);
1220 
1223  IntVar* const boolvar);
1227  Constraint* MakeIsEqualCt(IntExpr* const v1, IntExpr* v2, IntVar* const b);
1229  IntVar* MakeIsEqualVar(IntExpr* const v1, IntExpr* v2);
1231  Constraint* MakeEquality(IntExpr* const left, IntExpr* const right);
1233  Constraint* MakeEquality(IntExpr* const expr, int64 value);
1235  Constraint* MakeEquality(IntExpr* const expr, int value);
1236 
1239  IntVar* const boolvar);
1243  IntVar* MakeIsDifferentVar(IntExpr* const v1, IntExpr* const v2);
1245  Constraint* MakeIsDifferentCt(IntExpr* const v1, IntExpr* const v2,
1246  IntVar* const b);
1248  Constraint* MakeNonEquality(IntExpr* const left, IntExpr* const right);
1250  Constraint* MakeNonEquality(IntExpr* const expr, int64 value);
1252  Constraint* MakeNonEquality(IntExpr* const expr, int value);
1253 
1256  IntVar* const boolvar);
1260  IntVar* MakeIsLessOrEqualVar(IntExpr* const left, IntExpr* const right);
1262  Constraint* MakeIsLessOrEqualCt(IntExpr* const left, IntExpr* const right,
1263  IntVar* const b);
1265  Constraint* MakeLessOrEqual(IntExpr* const left, IntExpr* const right);
1267  Constraint* MakeLessOrEqual(IntExpr* const expr, int64 value);
1269  Constraint* MakeLessOrEqual(IntExpr* const expr, int value);
1270 
1273  IntVar* const boolvar);
1277  IntVar* MakeIsGreaterOrEqualVar(IntExpr* const left, IntExpr* const right);
1279  Constraint* MakeIsGreaterOrEqualCt(IntExpr* const left, IntExpr* const right,
1280  IntVar* const b);
1282  Constraint* MakeGreaterOrEqual(IntExpr* const left, IntExpr* const right);
1286  Constraint* MakeGreaterOrEqual(IntExpr* const expr, int value);
1287 
1289  Constraint* MakeIsGreaterCstCt(IntExpr* const v, int64 c, IntVar* const b);
1293  IntVar* MakeIsGreaterVar(IntExpr* const left, IntExpr* const right);
1295  Constraint* MakeIsGreaterCt(IntExpr* const left, IntExpr* const right,
1296  IntVar* const b);
1298  Constraint* MakeGreater(IntExpr* const left, IntExpr* const right);
1300  Constraint* MakeGreater(IntExpr* const expr, int64 value);
1302  Constraint* MakeGreater(IntExpr* const expr, int value);
1303 
1305  Constraint* MakeIsLessCstCt(IntExpr* const v, int64 c, IntVar* const b);
1309  IntVar* MakeIsLessVar(IntExpr* const left, IntExpr* const right);
1311  Constraint* MakeIsLessCt(IntExpr* const left, IntExpr* const right,
1312  IntVar* const b);
1314  Constraint* MakeLess(IntExpr* const left, IntExpr* const right);
1316  Constraint* MakeLess(IntExpr* const expr, int64 value);
1318  Constraint* MakeLess(IntExpr* const expr, int value);
1319 
1321  Constraint* MakeSumLessOrEqual(const std::vector<IntVar*>& vars, int64 cst);
1322  Constraint* MakeSumGreaterOrEqual(const std::vector<IntVar*>& vars,
1323  int64 cst);
1324  Constraint* MakeSumEquality(const std::vector<IntVar*>& vars, int64 cst);
1325  Constraint* MakeSumEquality(const std::vector<IntVar*>& vars,
1326  IntVar* const var);
1327  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1328  const std::vector<int64>& coefficients,
1329  int64 cst);
1330  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1331  const std::vector<int>& coefficients,
1332  int64 cst);
1333  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1334  const std::vector<int64>& coefficients,
1335  IntVar* const target);
1336  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1337  const std::vector<int>& coefficients,
1338  IntVar* const target);
1339  Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1340  const std::vector<int64>& coeffs,
1341  int64 cst);
1342  Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1343  const std::vector<int>& coeffs,
1344  int64 cst);
1345  Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1346  const std::vector<int64>& coefficients,
1347  int64 cst);
1348  Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1349  const std::vector<int>& coefficients,
1350  int64 cst);
1351 
1352  Constraint* MakeMinEquality(const std::vector<IntVar*>& vars,
1353  IntVar* const min_var);
1354  Constraint* MakeMaxEquality(const std::vector<IntVar*>& vars,
1355  IntVar* const max_var);
1356 
1357  Constraint* MakeElementEquality(const std::vector<int64>& vals,
1358  IntVar* const index, IntVar* const target);
1359  Constraint* MakeElementEquality(const std::vector<int>& vals,
1360  IntVar* const index, IntVar* const target);
1361  Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1362  IntVar* const index, IntVar* const target);
1363  Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1364  IntVar* const index, int64 target);
1366  Constraint* MakeAbsEquality(IntVar* const var, IntVar* const abs_var);
1371  Constraint* MakeIndexOfConstraint(const std::vector<IntVar*>& vars,
1372  IntVar* const index, int64 target);
1373 
1381 #if !defined(SWIG)
1383  Demon* MakeActionDemon(Action action);
1384 #endif
1386  Demon* MakeClosureDemon(Closure closure);
1387 
1388  // ----- Between and related constraints -----
1389 
1391  Constraint* MakeBetweenCt(IntExpr* const expr, int64 l, int64 u);
1392 
1397  Constraint* MakeNotBetweenCt(IntExpr* const expr, int64 l, int64 u);
1398 
1400  Constraint* MakeIsBetweenCt(IntExpr* const expr, int64 l, int64 u,
1401  IntVar* const b);
1402  IntVar* MakeIsBetweenVar(IntExpr* const v, int64 l, int64 u);
1403 
1404  // ----- Member and related constraints -----
1405 
1408  Constraint* MakeMemberCt(IntExpr* const expr,
1409  const std::vector<int64>& values);
1410  Constraint* MakeMemberCt(IntExpr* const expr, const std::vector<int>& values);
1411 
1413  Constraint* MakeNotMemberCt(IntExpr* const expr,
1414  const std::vector<int64>& values);
1415  Constraint* MakeNotMemberCt(IntExpr* const expr,
1416  const std::vector<int>& values);
1417 
1419  Constraint* MakeNotMemberCt(IntExpr* const expr, std::vector<int64> starts,
1420  std::vector<int64> ends);
1422  Constraint* MakeNotMemberCt(IntExpr* const expr, std::vector<int> starts,
1423  std::vector<int> ends);
1424 #if !defined(SWIG)
1427  SortedDisjointIntervalList intervals);
1428 #endif // !defined(SWIG)
1429 
1431  Constraint* MakeIsMemberCt(IntExpr* const expr,
1432  const std::vector<int64>& values,
1433  IntVar* const boolvar);
1434  Constraint* MakeIsMemberCt(IntExpr* const expr,
1435  const std::vector<int>& values,
1436  IntVar* const boolvar);
1437  IntVar* MakeIsMemberVar(IntExpr* const expr,
1438  const std::vector<int64>& values);
1439  IntVar* MakeIsMemberVar(IntExpr* const expr, const std::vector<int>& values);
1440 
1442  Constraint* MakeAtMost(std::vector<IntVar*> vars, int64 value,
1443  int64 max_count);
1445  Constraint* MakeCount(const std::vector<IntVar*>& vars, int64 value,
1446  int64 max_count);
1448  Constraint* MakeCount(const std::vector<IntVar*>& vars, int64 value,
1449  IntVar* const max_count);
1450 
1452  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1453  const std::vector<int64>& values,
1454  const std::vector<IntVar*>& cards);
1456  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1457  const std::vector<int>& values,
1458  const std::vector<IntVar*>& cards);
1460  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1461  const std::vector<IntVar*>& cards);
1464  Constraint* MakeDistribute(const std::vector<IntVar*>& vars, int64 card_min,
1465  int64 card_max, int64 card_size);
1469  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1470  const std::vector<int64>& card_min,
1471  const std::vector<int64>& card_max);
1475  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1476  const std::vector<int>& card_min,
1477  const std::vector<int>& card_max);
1481  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1482  const std::vector<int64>& values,
1483  const std::vector<int64>& card_min,
1484  const std::vector<int64>& card_max);
1488  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1489  const std::vector<int>& values,
1490  const std::vector<int>& card_min,
1491  const std::vector<int>& card_max);
1492 
1497  Constraint* MakeDeviation(const std::vector<IntVar*>& vars,
1498  IntVar* const deviation_var, int64 total_sum);
1499 
1502  Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars);
1503 
1507  Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars,
1508  bool stronger_propagation);
1509 
1512  Constraint* MakeAllDifferentExcept(const std::vector<IntVar*>& vars,
1513  int64 escape_value);
1514  // TODO(user): Do we need a version with an array of escape values.
1515 
1531  Constraint* MakeSortingConstraint(const std::vector<IntVar*>& vars,
1532  const std::vector<IntVar*>& sorted);
1533  // TODO(user): Add void MakeSortedArray(
1534  // const std::vector<IntVar*>& vars,
1535  // std::vector<IntVar*>* const sorted);
1536 
1539  Constraint* MakeLexicalLess(const std::vector<IntVar*>& left,
1540  const std::vector<IntVar*>& right);
1541 
1544  Constraint* MakeLexicalLessOrEqual(const std::vector<IntVar*>& left,
1545  const std::vector<IntVar*>& right);
1546 
1552  const std::vector<IntVar*>& left, const std::vector<IntVar*>& right);
1553 
1557  IntVar* index, const std::vector<IntVar*>& vars);
1558 
1562  IntVar* index, const std::vector<IntVar*>& vars);
1563 
1568  Constraint* MakeNullIntersect(const std::vector<IntVar*>& first_vars,
1569  const std::vector<IntVar*>& second_vars);
1570 
1576  Constraint* MakeNullIntersectExcept(const std::vector<IntVar*>& first_vars,
1577  const std::vector<IntVar*>& second_vars,
1578  int64 escape_value);
1579 
1580  // TODO(user): Implement MakeAllNullIntersect taking an array of
1581  // variable vectors.
1582 
1592  Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1593  const std::vector<IntVar*>& active,
1594  IndexFilter1 sink_handler = nullptr);
1595  Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1596  const std::vector<IntVar*>& active,
1597  IndexFilter1 sink_handler, bool assume_paths);
1598 
1600  Constraint* MakeCircuit(const std::vector<IntVar*>& nexts);
1601 
1604  Constraint* MakeSubCircuit(const std::vector<IntVar*>& nexts);
1605 
1610  Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1611  const std::vector<IntVar*>& active,
1612  const std::vector<IntVar*>& cumuls,
1613  const std::vector<IntVar*>& transits);
1616  // TODO(user): Merge with other path-cumuls constraints.
1617  Constraint* MakeDelayedPathCumul(const std::vector<IntVar*>& nexts,
1618  const std::vector<IntVar*>& active,
1619  const std::vector<IntVar*>& cumuls,
1620  const std::vector<IntVar*>& transits);
1627  Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1628  const std::vector<IntVar*>& active,
1629  const std::vector<IntVar*>& cumuls,
1630  IndexEvaluator2 transit_evaluator);
1631 
1638  Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1639  const std::vector<IntVar*>& active,
1640  const std::vector<IntVar*>& cumuls,
1641  const std::vector<IntVar*>& slacks,
1642  IndexEvaluator2 transit_evaluator);
1645  // TODO(user): Only does checking on WhenBound events on next variables.
1647  Constraint* MakePathConnected(std::vector<IntVar*> nexts,
1648  std::vector<int64> sources,
1649  std::vector<int64> sinks,
1650  std::vector<IntVar*> status);
1651 #ifndef SWIG
1654  // TODO(user): This constraint does not make holes in variable domains;
1658  std::vector<IntVar*> nexts,
1659  const std::vector<std::pair<int, int>>& precedences);
1669  std::vector<IntVar*> nexts,
1670  const std::vector<std::pair<int, int>>& precedences,
1671  const std::vector<int>& lifo_path_starts,
1672  const std::vector<int>& fifo_path_starts);
1676  std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1677  const std::vector<std::pair<int, int>>& precedences);
1678 #endif // !SWIG
1682  Constraint* MakeMapDomain(IntVar* const var,
1683  const std::vector<IntVar*>& actives);
1684 
1689  Constraint* MakeAllowedAssignments(const std::vector<IntVar*>& vars,
1690  const IntTupleSet& tuples);
1691 
1699  Constraint* MakeTransitionConstraint(const std::vector<IntVar*>& vars,
1700  const IntTupleSet& transition_table,
1701  int64 initial_state,
1702  const std::vector<int64>& final_states);
1703 
1711  Constraint* MakeTransitionConstraint(const std::vector<IntVar*>& vars,
1712  const IntTupleSet& transition_table,
1713  int64 initial_state,
1714  const std::vector<int>& final_states);
1715 
1716 #if defined(SWIGPYTHON)
1719  const std::vector<IntVar*>& vars,
1720  const std::vector<std::vector<int64> /*keep for swig*/>& raw_tuples) {
1721  IntTupleSet tuples(vars.size());
1722  tuples.InsertAll(raw_tuples);
1723  return MakeAllowedAssignments(vars, tuples);
1724  }
1725 
1727  const std::vector<IntVar*>& vars,
1728  const std::vector<std::vector<int64> /*keep for swig*/>& raw_transitions,
1729  int64 initial_state, const std::vector<int>& final_states) {
1730  IntTupleSet transitions(3);
1731  transitions.InsertAll(raw_transitions);
1732  return MakeTransitionConstraint(vars, transitions, initial_state,
1733  final_states);
1734  }
1735 #endif
1736 
1746  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1747  const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
1749  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1750  const std::vector<int64>& x_size, const std::vector<int64>& y_size);
1752  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1753  const std::vector<int>& x_size, const std::vector<int>& y_size);
1754 
1764  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1765  const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
1767  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1768  const std::vector<int64>& x_size, const std::vector<int64>& y_size);
1770  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1771  const std::vector<int>& x_size, const std::vector<int>& y_size);
1772 
1778  Pack* MakePack(const std::vector<IntVar*>& vars, int number_of_bins);
1779 
1785  int64 duration, bool optional,
1786  const std::string& name);
1787 
1791  int count, int64 start_min, int64 start_max, int64 duration,
1792  bool optional, const std::string& name,
1793  std::vector<IntervalVar*>* const array);
1794 
1797  IntervalVar* MakeFixedDurationIntervalVar(IntVar* const start_variable,
1798  int64 duration,
1799  const std::string& name);
1800 
1803  IntervalVar* MakeFixedDurationIntervalVar(IntVar* const start_variable,
1804  int64 duration,
1805  IntVar* const performed_variable,
1806  const std::string& name);
1807 
1811  const std::vector<IntVar*>& start_variables, int64 duration,
1812  const std::string& name, std::vector<IntervalVar*>* const array);
1813 
1817  const std::vector<IntVar*>& start_variables,
1818  const std::vector<int64>& durations, const std::string& name,
1819  std::vector<IntervalVar*>* const array);
1823  const std::vector<IntVar*>& start_variables,
1824  const std::vector<int>& durations, const std::string& name,
1825  std::vector<IntervalVar*>* const array);
1826 
1830  const std::vector<IntVar*>& start_variables,
1831  const std::vector<int64>& durations,
1832  const std::vector<IntVar*>& performed_variables, const std::string& name,
1833  std::vector<IntervalVar*>* const array);
1834 
1838  const std::vector<IntVar*>& start_variables,
1839  const std::vector<int>& durations,
1840  const std::vector<IntVar*>& performed_variables, const std::string& name,
1841  std::vector<IntervalVar*>* const array);
1842 
1844  IntervalVar* MakeFixedInterval(int64 start, int64 duration,
1845  const std::string& name);
1846 
1850  int64 duration_min, int64 duration_max,
1851  int64 end_min, int64 end_max, bool optional,
1852  const std::string& name);
1853 
1857  int64 duration_min, int64 duration_max,
1858  int64 end_min, int64 end_max, bool optional,
1859  const std::string& name,
1860  std::vector<IntervalVar*>* const array);
1861 
1864  IntervalVar* MakeMirrorInterval(IntervalVar* const interval_var);
1865 
1871  IntervalVar* const interval_var, int64 duration, int64 offset);
1872 
1878  IntervalVar* const interval_var, int64 duration, int64 offset);
1879 
1885  IntervalVar* const interval_var, int64 duration, int64 offset);
1886 
1892  IntervalVar* const interval_var, int64 duration, int64 offset);
1893 
1911  IntervalVar* MakeIntervalRelaxedMin(IntervalVar* const interval_var);
1912 
1930  IntervalVar* MakeIntervalRelaxedMax(IntervalVar* const interval_var);
1931 
1934  Constraint* MakeIntervalVarRelation(IntervalVar* const t,
1936 
1938  Constraint* MakeIntervalVarRelation(IntervalVar* const t1,
1940  IntervalVar* const t2);
1941 
1946  Constraint* MakeIntervalVarRelationWithDelay(IntervalVar* const t1,
1948  IntervalVar* const t2,
1949  int64 delay);
1950 
1954  Constraint* MakeTemporalDisjunction(IntervalVar* const t1,
1955  IntervalVar* const t2, IntVar* const alt);
1956 
1959  Constraint* MakeTemporalDisjunction(IntervalVar* const t1,
1960  IntervalVar* const t2);
1961 
1964  DisjunctiveConstraint* MakeDisjunctiveConstraint(
1965  const std::vector<IntervalVar*>& intervals, const std::string& name);
1966 
1970  DisjunctiveConstraint* MakeStrictDisjunctiveConstraint(
1971  const std::vector<IntervalVar*>& intervals, const std::string& name);
1972 
1982  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
1983  const std::vector<int64>& demands, int64 capacity,
1984  const std::string& name);
1985 
1995  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
1996  const std::vector<int>& demands, int64 capacity,
1997  const std::string& name);
1998 
2008  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2009  const std::vector<int64>& demands,
2010  IntVar* const capacity, const std::string& name);
2011 
2021  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2022  const std::vector<int>& demands,
2023  IntVar* const capacity, const std::string& name);
2024 
2032  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2033  const std::vector<IntVar*>& demands,
2034  int64 capacity, const std::string& name);
2035 
2043  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2044  const std::vector<IntVar*>& demands,
2045  IntVar* const capacity, const std::string& name);
2046 
2052  Constraint* MakeCover(const std::vector<IntervalVar*>& vars,
2053  IntervalVar* const target_var);
2054 
2056  Constraint* MakeEquality(IntervalVar* const var1, IntervalVar* const var2);
2057 
2059  Assignment* MakeAssignment();
2060 
2062  Assignment* MakeAssignment(const Assignment* const a);
2063 
2065  SolutionCollector* MakeFirstSolutionCollector(
2066  const Assignment* const assignment);
2069  SolutionCollector* MakeFirstSolutionCollector();
2070 
2072  SolutionCollector* MakeLastSolutionCollector(
2073  const Assignment* const assignment);
2076  SolutionCollector* MakeLastSolutionCollector();
2077 
2082  SolutionCollector* MakeBestValueSolutionCollector(
2083  const Assignment* const assignment, bool maximize);
2089  SolutionCollector* MakeBestValueSolutionCollector(bool maximize);
2090 
2094  SolutionCollector* MakeNBestValueSolutionCollector(
2095  const Assignment* const assignment, int solution_count, bool maximize);
2096  SolutionCollector* MakeNBestValueSolutionCollector(int solution_count,
2097  bool maximize);
2098 
2100  SolutionCollector* MakeAllSolutionCollector(
2101  const Assignment* const assignment);
2104  SolutionCollector* MakeAllSolutionCollector();
2105 
2107  OptimizeVar* MakeMinimize(IntVar* const v, int64 step);
2108 
2110  OptimizeVar* MakeMaximize(IntVar* const v, int64 step);
2111 
2113  OptimizeVar* MakeOptimize(bool maximize, IntVar* const v, int64 step);
2114 
2117  OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2118  const std::vector<int64>& weights,
2119  int64 step);
2120 
2123  OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2124  const std::vector<int>& weights,
2125  int64 step);
2126 
2128  OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2129  const std::vector<int64>& weights,
2130  int64 step);
2131 
2133  OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2134  const std::vector<int>& weights,
2135  int64 step);
2136 
2138  OptimizeVar* MakeWeightedOptimize(bool maximize,
2139  const std::vector<IntVar*>& sub_objectives,
2140  const std::vector<int64>& weights,
2141  int64 step);
2142 
2144  OptimizeVar* MakeWeightedOptimize(bool maximize,
2145  const std::vector<IntVar*>& sub_objectives,
2146  const std::vector<int>& weights,
2147  int64 step);
2148 
2150 
2166 
2167  SearchMonitor* MakeTabuSearch(bool maximize, IntVar* const v, int64 step,
2168  const std::vector<IntVar*>& vars,
2169  int64 keep_tenure, int64 forbid_tenure,
2170  double tabu_factor);
2171 
2174  SearchMonitor* MakeGenericTabuSearch(bool maximize, IntVar* const v,
2175  int64 step,
2176  const std::vector<IntVar*>& tabu_vars,
2177  int64 forbid_tenure);
2178 
2180  // TODO(user): document behavior
2181  SearchMonitor* MakeSimulatedAnnealing(bool maximize, IntVar* const v,
2182  int64 step, int64 initial_temperature);
2183 
2186  SearchMonitor* MakeGuidedLocalSearch(bool maximize, IntVar* const objective,
2187  IndexEvaluator2 objective_function,
2188  int64 step,
2189  const std::vector<IntVar*>& vars,
2190  double penalty_factor);
2192  bool maximize, IntVar* const objective,
2193  IndexEvaluator3 objective_function, int64 step,
2194  const std::vector<IntVar*>& vars,
2195  const std::vector<IntVar*>& secondary_vars, double penalty_factor);
2196 
2200  SearchMonitor* MakeLubyRestart(int scale_factor);
2201 
2204  SearchMonitor* MakeConstantRestart(int frequency);
2205 
2207  RegularLimit* MakeTimeLimit(absl::Duration time);
2208 #if !defined(SWIG)
2209  ABSL_DEPRECATED("Use the version taking absl::Duration() as argument")
2210 #endif // !defined(SWIG)
2212  return MakeTimeLimit(time_in_ms == kint64max
2213  ? absl::InfiniteDuration()
2214  : absl::Milliseconds(time_in_ms));
2215  }
2216 
2220 
2224 
2228 
2231  // timer by estimating the number of remaining calls, and 'cumulative' means
2232  // that the limit applies cumulatively, instead of search-by-search.
2234  int64 solutions, bool smart_time_check = false,
2235  bool cumulative = false);
2237  RegularLimit* MakeLimit(const RegularLimitParameters& proto);
2238 
2239 #if !defined(SWIG)
2240  ABSL_DEPRECATED("Use other MakeLimit() versions")
2241 #endif // !defined(SWIG)
2243  int64 solutions, bool smart_time_check = false,
2244  bool cumulative = false);
2245 
2247  RegularLimitParameters MakeDefaultRegularLimitParameters() const;
2248 
2252  SearchLimit* MakeLimit(SearchLimit* const limit_1,
2253  SearchLimit* const limit_2);
2254 
2260  IntVar* objective_var, bool maximize, double objective_scaling_factor,
2261  double objective_offset, double improvement_rate_coefficient,
2262  int improvement_rate_solutions_distance);
2263 
2266  SearchLimit* MakeCustomLimit(std::function<bool()> limiter);
2267 
2268  // TODO(user): DEPRECATE API of MakeSearchLog(.., IntVar* var,..).
2269 
2272  SearchMonitor* MakeSearchLog(int branch_period);
2273 
2275  SearchMonitor* MakeSearchLog(int branch_period, IntVar* const var);
2276 
2279  SearchMonitor* MakeSearchLog(int branch_period,
2280  std::function<std::string()> display_callback);
2281 
2284  SearchMonitor* MakeSearchLog(int branch_period, IntVar* var,
2285  std::function<std::string()> display_callback);
2286 
2289  SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* const opt_var);
2290 
2293  SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* const opt_var,
2294  std::function<std::string()> display_callback);
2295 
2300  int branch_period = 1;
2304  IntVar* variable = nullptr;
2308  double scaling_factor = 1.0;
2309  double offset = 0;
2313  std::function<std::string()> display_callback;
2317  };
2319 
2322  SearchMonitor* MakeSearchTrace(const std::string& prefix);
2323 
2325  SearchMonitor* MakeEnterSearchCallback(std::function<void()> callback);
2326  SearchMonitor* MakeExitSearchCallback(std::function<void()> callback);
2327  SearchMonitor* MakeAtSolutionCallback(std::function<void()> callback);
2328 
2333 #if !defined(SWIG)
2336  absl::flat_hash_map<const IntVar*, int>* const map);
2337 #endif // !defined(SWIG)
2338 
2341  const std::vector<SymmetryBreaker*>& visitors);
2344  SymmetryBreaker* const v2);
2346  SymmetryBreaker* const v2,
2347  SymmetryBreaker* const v3);
2349  SymmetryBreaker* const v2,
2350  SymmetryBreaker* const v3,
2351  SymmetryBreaker* const v4);
2352 
2358  bool start_with_lower_half);
2361  Decision* MakeAssignVariablesValues(const std::vector<IntVar*>& vars,
2362  const std::vector<int64>& values);
2364  Decision* MakeDecision(Action apply, Action refute);
2365 
2375  DecisionBuilder* const db2);
2377  DecisionBuilder* const db2,
2378  DecisionBuilder* const db3);
2380  DecisionBuilder* const db2,
2381  DecisionBuilder* const db3,
2382  DecisionBuilder* const db4);
2383  DecisionBuilder* Compose(const std::vector<DecisionBuilder*>& dbs);
2384 
2396  // TODO(user): The search tree can be balanced by using binary
2401  DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2);
2402  DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2,
2403  DecisionBuilder* const db3);
2404  DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2,
2405  DecisionBuilder* const db3, DecisionBuilder* const db4);
2406  DecisionBuilder* Try(const std::vector<DecisionBuilder*>& dbs);
2407 
2409  // TODO(user): name each of them differently, and document them (and do that
2411  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2412  IntVarStrategy var_str, IntValueStrategy val_str);
2413  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2414  IndexEvaluator1 var_evaluator,
2415  IntValueStrategy val_str);
2416 
2417  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2418  IntVarStrategy var_str,
2419  IndexEvaluator2 value_evaluator);
2420 
2423  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2424  IntVarStrategy var_str,
2425  VariableValueComparator var_val1_val2_comparator);
2426 
2427  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2428  IndexEvaluator1 var_evaluator,
2429  IndexEvaluator2 value_evaluator);
2430 
2431  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2432  IntVarStrategy var_str,
2433  IndexEvaluator2 value_evaluator,
2434  IndexEvaluator1 tie_breaker);
2435 
2436  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2437  IndexEvaluator1 var_evaluator,
2438  IndexEvaluator2 value_evaluator,
2439  IndexEvaluator1 tie_breaker);
2440 
2441  DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars);
2442  DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars,
2444 
2446  DecisionBuilder* MakePhase(IntVar* const v0, IntVarStrategy var_str,
2447  IntValueStrategy val_str);
2448  DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2449  IntVarStrategy var_str, IntValueStrategy val_str);
2450  DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2451  IntVar* const v2, IntVarStrategy var_str,
2452  IntValueStrategy val_str);
2453  DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2454  IntVar* const v2, IntVar* const v3,
2455  IntVarStrategy var_str, IntValueStrategy val_str);
2456 
2463  int64* const marker);
2464 
2471  int64* const marker);
2472 
2475  Decision* MakeRankFirstInterval(SequenceVar* const sequence, int index);
2476 
2479  Decision* MakeRankLastInterval(SequenceVar* const sequence, int index);
2480 
2486  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2488 
2496  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2497  IndexEvaluator2 eval, IndexEvaluator1 tie_breaker,
2498  EvaluatorStrategy str);
2499 
2501  DecisionBuilder* MakePhase(const std::vector<IntervalVar*>& intervals,
2502  IntervalStrategy str);
2503 
2504  DecisionBuilder* MakePhase(const std::vector<SequenceVar*>& sequences,
2505  SequenceStrategy str);
2506 
2510  Assignment* const assignment, DecisionBuilder* const db,
2511  const std::vector<IntVar*>& vars);
2512 
2516 
2523  SearchMonitor* const monitor1);
2525  SearchMonitor* const monitor1,
2526  SearchMonitor* const monitor2);
2528  SearchMonitor* const monitor1,
2529  SearchMonitor* const monitor2,
2530  SearchMonitor* const monitor3);
2532  SearchMonitor* const monitor1,
2533  SearchMonitor* const monitor2,
2534  SearchMonitor* const monitor3,
2535  SearchMonitor* const monitor4);
2537  const std::vector<SearchMonitor*>& monitors);
2538 
2547  Assignment* const solution, bool maximize,
2548  int64 step);
2550  Assignment* const solution, bool maximize,
2551  int64 step,
2552  SearchMonitor* const monitor1);
2554  Assignment* const solution, bool maximize,
2555  int64 step, SearchMonitor* const monitor1,
2556  SearchMonitor* const monitor2);
2558  Assignment* const solution, bool maximize,
2559  int64 step, SearchMonitor* const monitor1,
2560  SearchMonitor* const monitor2,
2561  SearchMonitor* const monitor3);
2563  Assignment* const solution, bool maximize,
2564  int64 step, SearchMonitor* const monitor1,
2565  SearchMonitor* const monitor2,
2566  SearchMonitor* const monitor3,
2567  SearchMonitor* const monitor4);
2569  DecisionBuilder* const db, Assignment* const solution, bool maximize,
2570  int64 step, const std::vector<SearchMonitor*>& monitors);
2571 
2575 
2579 
2581  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2583  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2584  const std::vector<IntVar*>& secondary_vars,
2586  // TODO(user): Make the callback an IndexEvaluator2 when there are no
2587  // secondary variables.
2588  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2589  IndexEvaluator3 evaluator,
2591  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2592  const std::vector<IntVar*>& secondary_vars,
2593  IndexEvaluator3 evaluator,
2595 
2603  LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2604  int number_of_variables);
2605  LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2606  int number_of_variables,
2607  int32 seed);
2608 
2615 
2623  const std::vector<IntVar*>& variables,
2624  const std::vector<int64>& target_values);
2625 
2657  const std::vector<LocalSearchOperator*>& ops);
2659  const std::vector<LocalSearchOperator*>& ops, bool restart);
2661  const std::vector<LocalSearchOperator*>& ops,
2662  std::function<int64(int, int)> evaluator);
2666  const std::vector<LocalSearchOperator*>& ops);
2667 
2672  const std::vector<LocalSearchOperator*>& ops, int32 seed);
2673 
2682  const std::vector<LocalSearchOperator*>& ops, double memory_coefficient,
2683  double exploration_coefficient, bool maximize);
2684 
2691  int64 limit);
2692 
2717  // TODO(user): Make a variant which runs a local search after each
2718  // solution found in a DFS.
2719 
2721  Assignment* const assignment,
2724  const std::vector<IntVar*>& vars, DecisionBuilder* const first_solution,
2728  const std::vector<IntVar*>& vars, DecisionBuilder* const first_solution,
2729  DecisionBuilder* const first_solution_sub_decision_builder,
2732  const std::vector<SequenceVar*>& vars,
2733  DecisionBuilder* const first_solution,
2735 
2738 
2741  IntVar* objective, LocalSearchOperator* const ls_operator,
2742  DecisionBuilder* const sub_decision_builder);
2744  IntVar* objective, LocalSearchOperator* const ls_operator,
2745  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit);
2747  IntVar* objective, LocalSearchOperator* const ls_operator,
2748  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
2749  LocalSearchFilterManager* filter_manager);
2750 
2752  IntVar* objective, SolutionPool* const pool,
2753  LocalSearchOperator* const ls_operator,
2754  DecisionBuilder* const sub_decision_builder);
2756  IntVar* objective, SolutionPool* const pool,
2757  LocalSearchOperator* const ls_operator,
2758  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit);
2760  IntVar* objective, SolutionPool* const pool,
2761  LocalSearchOperator* const ls_operator,
2762  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
2763  LocalSearchFilterManager* filter_manager);
2764 
2770  const std::vector<IntVar*>& vars, IndexEvaluator2 values,
2771  Solver::LocalSearchFilterBound filter_enum);
2773  const std::vector<IntVar*>& vars,
2774  const std::vector<IntVar*>& secondary_vars, IndexEvaluator3 values,
2775  Solver::LocalSearchFilterBound filter_enum);
2776 
2779  void TopPeriodicCheck();
2783  int TopProgressPercent();
2784 
2788  void PushState();
2789  void PopState();
2790 
2793  int SearchDepth() const;
2794 
2797  int SearchLeftDepth() const;
2798 
2801  int SolveDepth() const;
2802 
2805 
2808 
2810  template <class T>
2811  void SaveAndSetValue(T* adr, T val) {
2812  if (*adr != val) {
2813  InternalSaveValue(adr);
2814  *adr = val;
2815  }
2816  }
2817 
2819  template <class T>
2820  void SaveAndAdd(T* adr, T val) {
2821  if (val != 0) {
2822  InternalSaveValue(adr);
2823  (*adr) += val;
2824  }
2825  }
2826 
2829  DCHECK_GT(size, 0);
2830  return absl::Uniform<int64>(random_, 0, size);
2831  }
2832 
2835  DCHECK_GT(size, 0);
2836  return absl::Uniform<int32>(random_, 0, size);
2837  }
2838 
2840  void ReSeed(int32 seed) { random_.seed(seed); }
2841 
2845  void ExportProfilingOverview(const std::string& filename);
2846 
2848  // TODO(user): Merge demon and local search profiles.
2849  std::string LocalSearchProfile() const;
2850 
2851 #if !defined(SWIG)
2853  ConstraintSolverStatistics GetConstraintSolverStatistics() const;
2855  LocalSearchStatistics GetLocalSearchStatistics() const;
2856 #endif // !defined(SWIG)
2857 
2861  bool CurrentlyInSolve() const;
2862 
2865  int constraints() const { return constraints_list_.size(); }
2866 
2868  void Accept(ModelVisitor* const visitor) const;
2869 
2870  Decision* balancing_decision() const { return balancing_decision_.get(); }
2871 
2873 #if !defined(SWIG)
2874  void set_fail_intercept(std::function<void()> fail_intercept) {
2875  fail_intercept_ = std::move(fail_intercept);
2876  }
2877 #endif // !defined(SWIG)
2878  void clear_fail_intercept() { fail_intercept_ = nullptr; }
2880  DemonProfiler* demon_profiler() const { return demon_profiler_; }
2881  // TODO(user): Get rid of the following methods once fast local search is
2884  void SetUseFastLocalSearch(bool use_fast_local_search) {
2885  use_fast_local_search_ = use_fast_local_search;
2886  }
2888  bool UseFastLocalSearch() const { return use_fast_local_search_; }
2890  bool HasName(const PropagationBaseObject* object) const;
2892  Demon* RegisterDemon(Demon* const demon);
2894  IntExpr* RegisterIntExpr(IntExpr* const expr);
2896  IntVar* RegisterIntVar(IntVar* const var);
2900 
2902  Search* ActiveSearch() const;
2904  ModelCache* Cache() const;
2906  bool InstrumentsDemons() const;
2908  bool IsProfilingEnabled() const;
2910  bool IsLocalSearchProfilingEnabled() const;
2912  bool InstrumentsVariables() const;
2914  bool NameAllVariables() const;
2916  std::string model_name() const;
2921  void AddPropagationMonitor(PropagationMonitor* const monitor);
2927  void SetSearchContext(Search* search, const std::string& search_context);
2928  std::string SearchContext() const;
2929  std::string SearchContext(const Search* search) const;
2931  // TODO(user): Investigate if this should be moved to Search.
2934  void ClearLocalSearchState() { local_search_state_.reset(nullptr); }
2935 
2940  std::vector<int64> tmp_vector_;
2941 
2942  friend class BaseIntExpr;
2943  friend class Constraint;
2944  friend class DemonProfiler;
2945  friend class FindOneNeighbor;
2946  friend class IntVar;
2948  friend class Queue;
2949  friend class SearchMonitor;
2950  friend class SearchLimit;
2951  friend class RoutingModel;
2952  friend class LocalSearchProfiler;
2953 
2954 #if !defined(SWIG)
2955  friend void InternalSaveBooleanVarValue(Solver* const, IntVar* const);
2956  template <class>
2957  friend class SimpleRevFIFO;
2958  template <class K, class V>
2959  friend class RevImmutableMultiMap;
2960 
2965  bool IsBooleanVar(IntExpr* const expr, IntVar** inner_var,
2966  bool* is_negated) const;
2967 
2972  bool IsProduct(IntExpr* const expr, IntExpr** inner_expr, int64* coefficient);
2973 #endif
2974 
2977  IntExpr* CastExpression(const IntVar* const var) const;
2978 
2980  void FinishCurrentSearch();
2981  void RestartCurrentSearch();
2982 
2985  void ShouldFail() { should_fail_ = true; }
2986  void CheckFail() {
2987  if (!should_fail_) return;
2988  should_fail_ = false;
2989  Fail();
2990  }
2991 
2992  private:
2993  void Init();
2994  void PushState(MarkerType t, const StateInfo& info);
2995  MarkerType PopState(StateInfo* info);
2996  void PushSentinel(int magic_code);
2997  void BacktrackToSentinel(int magic_code);
2998  void ProcessConstraints();
2999  bool BacktrackOneLevel(Decision** fail_decision);
3000  void JumpToSentinelWhenNested();
3001  void JumpToSentinel();
3002  void check_alloc_state();
3003  void FreezeQueue();
3004  void EnqueueVar(Demon* const d);
3005  void EnqueueDelayedDemon(Demon* const d);
3006  void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
3007  void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
3008  void UnfreezeQueue();
3009  void reset_action_on_fail();
3010  void set_action_on_fail(Action a);
3011  void set_variable_to_clean_on_fail(IntVar* v);
3012  void IncrementUncheckedSolutionCounter();
3013  bool IsUncheckedSolutionLimitReached();
3014 
3015  void InternalSaveValue(int* valptr);
3016  void InternalSaveValue(int64* valptr);
3017  void InternalSaveValue(uint64* valptr);
3018  void InternalSaveValue(double* valptr);
3019  void InternalSaveValue(bool* valptr);
3020  void InternalSaveValue(void** valptr);
3021  void InternalSaveValue(int64** valptr) {
3022  InternalSaveValue(reinterpret_cast<void**>(valptr));
3023  }
3024 
3025  BaseObject* SafeRevAlloc(BaseObject* ptr);
3026 
3027  int* SafeRevAllocArray(int* ptr);
3028  int64* SafeRevAllocArray(int64* ptr);
3029  uint64* SafeRevAllocArray(uint64* ptr);
3030  double* SafeRevAllocArray(double* ptr);
3031  BaseObject** SafeRevAllocArray(BaseObject** ptr);
3032  IntVar** SafeRevAllocArray(IntVar** ptr);
3033  IntExpr** SafeRevAllocArray(IntExpr** ptr);
3034  Constraint** SafeRevAllocArray(Constraint** ptr);
3037  void* UnsafeRevAllocAux(void* ptr);
3038  template <class T>
3039  T* UnsafeRevAlloc(T* ptr) {
3040  return reinterpret_cast<T*>(
3041  UnsafeRevAllocAux(reinterpret_cast<void*>(ptr)));
3042  }
3043  void** UnsafeRevAllocArrayAux(void** ptr);
3044  template <class T>
3045  T** UnsafeRevAllocArray(T** ptr) {
3046  return reinterpret_cast<T**>(
3047  UnsafeRevAllocArrayAux(reinterpret_cast<void**>(ptr)));
3048  }
3049 
3050  void InitCachedIntConstants();
3051  void InitCachedConstraint();
3052 
3056  Search* TopLevelSearch() const { return searches_.at(1); }
3060  Search* ParentSearch() const {
3061  const size_t search_size = searches_.size();
3062  DCHECK_GT(search_size, 1);
3063  return searches_[search_size - 2];
3064  }
3065 
3067  std::string GetName(const PropagationBaseObject* object);
3068  void SetName(const PropagationBaseObject* object, const std::string& name);
3069 
3072  int GetNewIntVarIndex() { return num_int_vars_++; }
3073 
3075  bool IsADifference(IntExpr* expr, IntExpr** const left,
3076  IntExpr** const right);
3077 
3078  const std::string name_;
3079  const ConstraintSolverParameters parameters_;
3080  absl::flat_hash_map<const PropagationBaseObject*, std::string>
3081  propagation_object_names_;
3082  absl::flat_hash_map<const PropagationBaseObject*, IntegerCastInfo>
3083  cast_information_;
3084  absl::flat_hash_set<const Constraint*> cast_constraints_;
3085  const std::string empty_name_;
3086  std::unique_ptr<Queue> queue_;
3087  std::unique_ptr<Trail> trail_;
3088  std::vector<Constraint*> constraints_list_;
3089  std::vector<Constraint*> additional_constraints_list_;
3090  std::vector<int> additional_constraints_parent_list_;
3091  SolverState state_;
3092  int64 branches_;
3093  int64 fails_;
3094  int64 decisions_;
3095  int64 demon_runs_[kNumPriorities];
3096  int64 neighbors_;
3097  int64 filtered_neighbors_;
3098  int64 accepted_neighbors_;
3099  OptimizationDirection optimization_direction_;
3100  std::unique_ptr<ClockTimer> timer_;
3101  std::vector<Search*> searches_;
3102  std::mt19937 random_;
3103  uint64 fail_stamp_;
3104  std::unique_ptr<Decision> balancing_decision_;
3106  std::function<void()> fail_intercept_;
3108  DemonProfiler* const demon_profiler_;
3110  bool use_fast_local_search_;
3112  LocalSearchProfiler* const local_search_profiler_;
3114  std::unique_ptr<Assignment> local_search_state_;
3115 
3117  enum { MIN_CACHED_INT_CONST = -8, MAX_CACHED_INT_CONST = 8 };
3118  IntVar* cached_constants_[MAX_CACHED_INT_CONST + 1 - MIN_CACHED_INT_CONST];
3119 
3121  Constraint* true_constraint_;
3122  Constraint* false_constraint_;
3123 
3124  std::unique_ptr<Decision> fail_decision_;
3125  int constraint_index_;
3126  int additional_constraint_index_;
3127  int num_int_vars_;
3128 
3129  std::unique_ptr<ModelCache> model_cache_;
3130  std::unique_ptr<PropagationMonitor> propagation_monitor_;
3131  PropagationMonitor* print_trace_;
3132  std::unique_ptr<LocalSearchMonitor> local_search_monitor_;
3133  int anonymous_variable_index_;
3134  bool should_fail_;
3135 
3137 };
3138 
3139 std::ostream& operator<<(std::ostream& out, const Solver* const s);
3140 
3144 inline int64 Zero() { return 0; }
3145 
3147 inline int64 One() { return 1; }
3148 
3152 class BaseObject {
3153  public:
3155  virtual ~BaseObject() {}
3156  virtual std::string DebugString() const { return "BaseObject"; }
3157 
3158  private:
3159  DISALLOW_COPY_AND_ASSIGN(BaseObject);
3160 };
3161 
3162 std::ostream& operator<<(std::ostream& out, const BaseObject* o);
3163 
3168  public:
3169  explicit PropagationBaseObject(Solver* const s) : solver_(s) {}
3171 
3172  std::string DebugString() const override {
3173  if (name().empty()) {
3174  return "PropagationBaseObject";
3175  } else {
3176  return absl::StrFormat("PropagationBaseObject: %s", name());
3177  }
3178  }
3179  Solver* solver() const { return solver_; }
3180 
3183  void FreezeQueue() { solver_->FreezeQueue(); }
3184 
3187  void UnfreezeQueue() { solver_->UnfreezeQueue(); }
3188 
3192  void EnqueueDelayedDemon(Demon* const d) { solver_->EnqueueDelayedDemon(d); }
3193  void EnqueueVar(Demon* const d) { solver_->EnqueueVar(d); }
3194  void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
3195  void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
3196 
3197 #if !defined(SWIG)
3198  // This method sets a callback that will be called if a failure
3199  // happens during the propagation of the queue.
3201  solver_->set_action_on_fail(std::move(a));
3202  }
3203 #endif // !defined(SWIG)
3204 
3206  void reset_action_on_fail() { solver_->reset_action_on_fail(); }
3207 
3210  solver_->set_variable_to_clean_on_fail(v);
3211  }
3212 
3214  virtual std::string name() const;
3215  void set_name(const std::string& name);
3217  bool HasName() const;
3219  virtual std::string BaseName() const;
3220 
3221  private:
3222  Solver* const solver_;
3223  DISALLOW_COPY_AND_ASSIGN(PropagationBaseObject);
3224 };
3225 
3228 class Decision : public BaseObject {
3229  public:
3231  ~Decision() override {}
3232 
3234  virtual void Apply(Solver* const s) = 0;
3235 
3237  virtual void Refute(Solver* const s) = 0;
3238 
3239  std::string DebugString() const override { return "Decision"; }
3241  virtual void Accept(DecisionVisitor* const visitor) const;
3242 
3243  private:
3244  DISALLOW_COPY_AND_ASSIGN(Decision);
3245 };
3246 
3249 class DecisionVisitor : public BaseObject {
3250  public:
3252  ~DecisionVisitor() override {}
3253  virtual void VisitSetVariableValue(IntVar* const var, int64 value);
3254  virtual void VisitSplitVariableDomain(IntVar* const var, int64 value,
3255  bool start_with_lower_half);
3256  virtual void VisitScheduleOrPostpone(IntervalVar* const var, int64 est);
3257  virtual void VisitScheduleOrExpedite(IntervalVar* const var, int64 est);
3258  virtual void VisitRankFirstInterval(SequenceVar* const sequence, int index);
3259  virtual void VisitRankLastInterval(SequenceVar* const sequence, int index);
3260  virtual void VisitUnknownDecision();
3261 
3262  private:
3263  DISALLOW_COPY_AND_ASSIGN(DecisionVisitor);
3264 };
3265 
3268 class DecisionBuilder : public BaseObject {
3269  public:
3271  ~DecisionBuilder() override {}
3276  virtual Decision* Next(Solver* const s) = 0;
3277  std::string DebugString() const override;
3278 #if !defined(SWIG)
3283  virtual void AppendMonitors(Solver* const solver,
3284  std::vector<SearchMonitor*>* const extras);
3285  virtual void Accept(ModelVisitor* const visitor) const;
3286 #endif
3287 
3288  private:
3289  DISALLOW_COPY_AND_ASSIGN(DecisionBuilder);
3290 };
3291 
3301 class Demon : public BaseObject {
3302  public:
3305  Demon() : stamp_(uint64_t{0}) {}
3306  ~Demon() override {}
3307 
3309  virtual void Run(Solver* const s) = 0;
3310 
3314  virtual Solver::DemonPriority priority() const;
3315 
3316  std::string DebugString() const override;
3317 
3320  void inhibit(Solver* const s);
3321 
3323  void desinhibit(Solver* const s);
3324 
3325  private:
3326  friend class Queue;
3327  void set_stamp(int64 stamp) { stamp_ = stamp; }
3328  uint64 stamp() const { return stamp_; }
3329  uint64 stamp_;
3331 };
3332 
3334 class ModelVisitor : public BaseObject {
3335  public:
3337  static const char kAbs[];
3338  static const char kAbsEqual[];
3339  static const char kAllDifferent[];
3340  static const char kAllowedAssignments[];
3341  static const char kAtMost[];
3342  static const char kIndexOf[];
3343  static const char kBetween[];
3344  static const char kConditionalExpr[];
3345  static const char kCircuit[];
3346  static const char kConvexPiecewise[];
3347  static const char kCountEqual[];
3348  static const char kCover[];
3349  static const char kCumulative[];
3350  static const char kDeviation[];
3351  static const char kDifference[];
3352  static const char kDisjunctive[];
3353  static const char kDistribute[];
3354  static const char kDivide[];
3355  static const char kDurationExpr[];
3356  static const char kElement[];
3357  static const char kElementEqual[];
3358  static const char kEndExpr[];
3359  static const char kEquality[];
3360  static const char kFalseConstraint[];
3361  static const char kGlobalCardinality[];
3362  static const char kGreater[];
3363  static const char kGreaterOrEqual[];
3364  static const char kIntegerVariable[];
3365  static const char kIntervalBinaryRelation[];
3366  static const char kIntervalDisjunction[];
3367  static const char kIntervalUnaryRelation[];
3368  static const char kIntervalVariable[];
3369  static const char kInversePermutation[];
3370  static const char kIsBetween[];
3371  static const char kIsDifferent[];
3372  static const char kIsEqual[];
3373  static const char kIsGreater[];
3374  static const char kIsGreaterOrEqual[];
3375  static const char kIsLess[];
3376  static const char kIsLessOrEqual[];
3377  static const char kIsMember[];
3378  static const char kLess[];
3379  static const char kLessOrEqual[];
3380  static const char kLexLess[];
3381  static const char kLinkExprVar[];
3382  static const char kMapDomain[];
3383  static const char kMax[];
3384  static const char kMaxEqual[];
3385  static const char kMember[];
3386  static const char kMin[];
3387  static const char kMinEqual[];
3388  static const char kModulo[];
3389  static const char kNoCycle[];
3390  static const char kNonEqual[];
3391  static const char kNotBetween[];
3392  static const char kNotMember[];
3393  static const char kNullIntersect[];
3394  static const char kOpposite[];
3395  static const char kPack[];
3396  static const char kPathCumul[];
3397  static const char kDelayedPathCumul[];
3398  static const char kPerformedExpr[];
3399  static const char kPower[];
3400  static const char kProduct[];
3401  static const char kScalProd[];
3402  static const char kScalProdEqual[];
3403  static const char kScalProdGreaterOrEqual[];
3404  static const char kScalProdLessOrEqual[];
3405  static const char kSemiContinuous[];
3406  static const char kSequenceVariable[];
3407  static const char kSortingConstraint[];
3408  static const char kSquare[];
3409  static const char kStartExpr[];
3410  static const char kSum[];
3411  static const char kSumEqual[];
3412  static const char kSumGreaterOrEqual[];
3413  static const char kSumLessOrEqual[];
3414  static const char kTrace[];
3415  static const char kTransition[];
3416  static const char kTrueConstraint[];
3417  static const char kVarBoundWatcher[];
3418  static const char kVarValueWatcher[];
3419 
3421  static const char kCountAssignedItemsExtension[];
3422  static const char kCountUsedBinsExtension[];
3423  static const char kInt64ToBoolExtension[];
3424  static const char kInt64ToInt64Extension[];
3425  static const char kObjectiveExtension[];
3426  static const char kSearchLimitExtension[];
3427  static const char kUsageEqualVariableExtension[];
3428 
3429  static const char kUsageLessConstantExtension[];
3430  static const char kVariableGroupExtension[];
3433 
3435  static const char kActiveArgument[];
3436  static const char kAssumePathsArgument[];
3437  static const char kBranchesLimitArgument[];
3438  static const char kCapacityArgument[];
3439  static const char kCardsArgument[];
3440  static const char kCoefficientsArgument[];
3441  static const char kCountArgument[];
3442  static const char kCumulativeArgument[];
3443  static const char kCumulsArgument[];
3444  static const char kDemandsArgument[];
3445  static const char kDurationMaxArgument[];
3446  static const char kDurationMinArgument[];
3447  static const char kEarlyCostArgument[];
3448  static const char kEarlyDateArgument[];
3449  static const char kEndMaxArgument[];
3450  static const char kEndMinArgument[];
3451  static const char kEndsArgument[];
3452  static const char kExpressionArgument[];
3453  static const char kFailuresLimitArgument[];
3454  static const char kFinalStatesArgument[];
3455  static const char kFixedChargeArgument[];
3456  static const char kIndex2Argument[];
3457  static const char kIndexArgument[];
3458  static const char kInitialState[];
3459  static const char kIntervalArgument[];
3460  static const char kIntervalsArgument[];
3461  static const char kLateCostArgument[];
3462  static const char kLateDateArgument[];
3463  static const char kLeftArgument[];
3464  static const char kMaxArgument[];
3465  static const char kMaximizeArgument[];
3466  static const char kMinArgument[];
3467  static const char kModuloArgument[];
3468  static const char kNextsArgument[];
3469  static const char kOptionalArgument[];
3470  static const char kPartialArgument[];
3471  static const char kPositionXArgument[];
3472  static const char kPositionYArgument[];
3473  static const char kRangeArgument[];
3474  static const char kRelationArgument[];
3475  static const char kRightArgument[];
3476  static const char kSequenceArgument[];
3477  static const char kSequencesArgument[];
3478  static const char kSizeArgument[];
3479  static const char kSizeXArgument[];
3480  static const char kSizeYArgument[];
3481  static const char kSmartTimeCheckArgument[];
3482  static const char kSolutionLimitArgument[];
3483  static const char kStartMaxArgument[];
3484  static const char kStartMinArgument[];
3485  static const char kStartsArgument[];
3486  static const char kStepArgument[];
3487  static const char kTargetArgument[];
3488  static const char kTimeLimitArgument[];
3489  static const char kTransitsArgument[];
3490  static const char kTuplesArgument[];
3491  static const char kValueArgument[];
3492  static const char kValuesArgument[];
3493  static const char kVariableArgument[];
3494  static const char kVarsArgument[];
3495  static const char kEvaluatorArgument[];
3496 
3498  static const char kMirrorOperation[];
3499  static const char kRelaxedMaxOperation[];
3500  static const char kRelaxedMinOperation[];
3501  static const char kSumOperation[];
3502  static const char kDifferenceOperation[];
3503  static const char kProductOperation[];
3504  static const char kStartSyncOnStartOperation[];
3505  static const char kStartSyncOnEndOperation[];
3506  static const char kTraceOperation[];
3507 
3508  ~ModelVisitor() override;
3509 
3511 
3513  virtual void BeginVisitModel(const std::string& type_name);
3514  virtual void EndVisitModel(const std::string& type_name);
3515  virtual void BeginVisitConstraint(const std::string& type_name,
3516  const Constraint* const constraint);
3517  virtual void EndVisitConstraint(const std::string& type_name,
3518  const Constraint* const constraint);
3519  virtual void BeginVisitExtension(const std::string& type);
3520  virtual void EndVisitExtension(const std::string& type);
3521  virtual void BeginVisitIntegerExpression(const std::string& type_name,
3522  const IntExpr* const expr);
3523  virtual void EndVisitIntegerExpression(const std::string& type_name,
3524  const IntExpr* const expr);
3525  virtual void VisitIntegerVariable(const IntVar* const variable,
3526  IntExpr* const delegate);
3527  virtual void VisitIntegerVariable(const IntVar* const variable,
3528  const std::string& operation, int64 value,
3529  IntVar* const delegate);
3530  virtual void VisitIntervalVariable(const IntervalVar* const variable,
3531  const std::string& operation, int64 value,
3532  IntervalVar* const delegate);
3533  virtual void VisitSequenceVariable(const SequenceVar* const variable);
3534 
3536  virtual void VisitIntegerArgument(const std::string& arg_name, int64 value);
3537  virtual void VisitIntegerArrayArgument(const std::string& arg_name,
3538  const std::vector<int64>& values);
3539  virtual void VisitIntegerMatrixArgument(const std::string& arg_name,
3540  const IntTupleSet& tuples);
3541 
3543  virtual void VisitIntegerExpressionArgument(const std::string& arg_name,
3544  IntExpr* const argument);
3545 
3546  virtual void VisitIntegerVariableArrayArgument(
3547  const std::string& arg_name, const std::vector<IntVar*>& arguments);
3548 
3550  virtual void VisitIntervalArgument(const std::string& arg_name,
3551  IntervalVar* const argument);
3552 
3553  virtual void VisitIntervalArrayArgument(
3554  const std::string& arg_name, const std::vector<IntervalVar*>& arguments);
3556  virtual void VisitSequenceArgument(const std::string& arg_name,
3557  SequenceVar* const argument);
3558 
3559  virtual void VisitSequenceArrayArgument(
3560  const std::string& arg_name, const std::vector<SequenceVar*>& arguments);
3561 #if !defined(SWIG)
3564  const std::string& arg_name, const Solver::Int64ToIntVar& arguments);
3565 
3568  void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64 index_min,
3569  int64 index_max);
3571  int64 index_min, int64 index_max);
3574  const std::string& arg_name, int64 index_max);
3575 #endif // #if !defined(SWIG)
3576 };
3577 
3585  public:
3587  ~Constraint() override {}
3588 
3591  virtual void Post() = 0;
3592 
3595  virtual void InitialPropagate() = 0;
3596  std::string DebugString() const override;
3597 
3600  void PostAndPropagate();
3601 
3603  virtual void Accept(ModelVisitor* const visitor) const;
3604 
3606  bool IsCastConstraint() const;
3607 
3611  virtual IntVar* Var();
3612 
3613  private:
3614  DISALLOW_COPY_AND_ASSIGN(Constraint);
3615 };
3616 
3620 class CastConstraint : public Constraint {
3621  public:
3624  CHECK(target_var != nullptr);
3625  }
3626  ~CastConstraint() override {}
3627 
3628  IntVar* target_var() const { return target_var_; }
3629 
3630  protected:
3632 };
3633 
3635 class SearchMonitor : public BaseObject {
3636  public:
3637  static constexpr int kNoProgress = -1;
3638 
3639  explicit SearchMonitor(Solver* const s) : solver_(s) {}
3640  ~SearchMonitor() override {}
3642  virtual void EnterSearch();
3643 
3645  virtual void RestartSearch();
3646 
3648  virtual void ExitSearch();
3649 
3651  virtual void BeginNextDecision(DecisionBuilder* const b);
3652 
3654  virtual void EndNextDecision(DecisionBuilder* const b, Decision* const d);
3655 
3657  virtual void ApplyDecision(Decision* const d);
3658 
3660  virtual void RefuteDecision(Decision* const d);
3661 
3664  virtual void AfterDecision(Decision* const d, bool apply);
3665 
3667  virtual void BeginFail();
3668 
3670  virtual void EndFail();
3671 
3673  virtual void BeginInitialPropagation();
3674 
3676  virtual void EndInitialPropagation();
3677 
3681  virtual bool AcceptSolution();
3682 
3686  virtual bool AtSolution();
3687 
3689  virtual void NoMoreSolutions();
3690 
3693  virtual bool LocalOptimum();
3694 
3696  virtual bool AcceptDelta(Assignment* delta, Assignment* deltadelta);
3697 
3699  virtual void AcceptNeighbor();
3700 
3702  virtual void AcceptUncheckedNeighbor();
3703 
3706  virtual bool IsUncheckedSolutionLimitReached() { return false; }
3707 
3708  Solver* solver() const { return solver_; }
3709 
3711  virtual void PeriodicCheck();
3712 
3715  virtual int ProgressPercent() { return kNoProgress; }
3716 
3718  virtual void Accept(ModelVisitor* const visitor) const;
3719 
3722  virtual void Install();
3723 
3724  private:
3725  Solver* const solver_;
3726  DISALLOW_COPY_AND_ASSIGN(SearchMonitor);
3727 };
3728 
3734 template <class T>
3735 class Rev {
3736  public:
3737  explicit Rev(const T& val) : stamp_(0), value_(val) {}
3738 
3739  const T& Value() const { return value_; }
3740 
3741  void SetValue(Solver* const s, const T& val) {
3742  if (val != value_) {
3743  if (stamp_ < s->stamp()) {
3744  s->SaveValue(&value_);
3745  stamp_ = s->stamp();
3746  }
3747  value_ = val;
3748  }
3749  }
3750 
3751  private:
3752  uint64 stamp_;
3753  T value_;
3754 };
3755 
3757 template <class T>
3758 class NumericalRev : public Rev<T> {
3759  public:
3760  explicit NumericalRev(const T& val) : Rev<T>(val) {}
3761 
3762  void Add(Solver* const s, const T& to_add) {
3763  this->SetValue(s, this->Value() + to_add);
3764  }
3765 
3766  void Incr(Solver* const s) { Add(s, 1); }
3767 
3768  void Decr(Solver* const s) { Add(s, -1); }
3769 };
3770 
3776 template <class T>
3777 class RevArray {
3778  public:
3779  RevArray(int size, const T& val)
3780  : stamps_(new uint64[size]), values_(new T[size]), size_(size) {
3781  for (int i = 0; i < size; ++i) {
3782  stamps_[i] = 0;
3783  values_[i] = val;
3784  }
3785  }
3786 
3788 
3789  int64 size() const { return size_; }
3790 
3791  const T& Value(int index) const { return values_[index]; }
3792 
3793 #if !defined(SWIG)
3794  const T& operator[](int index) const { return values_[index]; }
3795 #endif
3796 
3797  void SetValue(Solver* const s, int index, const T& val) {
3798  DCHECK_LT(index, size_);
3799  if (val != values_[index]) {
3800  if (stamps_[index] < s->stamp()) {
3801  s->SaveValue(&values_[index]);
3802  stamps_[index] = s->stamp();
3803  }
3804  values_[index] = val;
3805  }
3806  }
3807 
3808  private:
3809  std::unique_ptr<uint64[]> stamps_;
3810  std::unique_ptr<T[]> values_;
3811  const int size_;
3812 };
3813 
3815 template <class T>
3816 class NumericalRevArray : public RevArray<T> {
3817  public:
3818  NumericalRevArray(int size, const T& val) : RevArray<T>(size, val) {}
3819 
3820  void Add(Solver* const s, int index, const T& to_add) {
3821  this->SetValue(s, index, this->Value(index) + to_add);
3822  }
3823 
3824  void Incr(Solver* const s, int index) { Add(s, index, 1); }
3825 
3826  void Decr(Solver* const s, int index) { Add(s, index, -1); }
3827 };
3828 
3837  public:
3838  explicit IntExpr(Solver* const s) : PropagationBaseObject(s) {}
3839  ~IntExpr() override {}
3840 
3841  virtual int64 Min() const = 0;
3842  virtual void SetMin(int64 m) = 0;
3843  virtual int64 Max() const = 0;
3844  virtual void SetMax(int64 m) = 0;
3845 
3848  virtual void Range(int64* l, int64* u) {
3849  *l = Min();
3850  *u = Max();
3851  }
3853  virtual void SetRange(int64 l, int64 u) {
3854  SetMin(l);
3855  SetMax(u);
3856  }
3857 
3859  virtual void SetValue(int64 v) { SetRange(v, v); }
3860 
3862  virtual bool Bound() const { return (Min() == Max()); }
3863 
3865  virtual bool IsVar() const { return false; }
3866 
3868  virtual IntVar* Var() = 0;
3869 
3874  IntVar* VarWithName(const std::string& name);
3875 
3877  virtual void WhenRange(Demon* d) = 0;
3879  void WhenRange(Solver::Closure closure) {
3880  WhenRange(solver()->MakeClosureDemon(std::move(closure)));
3881  }
3882 
3883 #if !defined(SWIG)
3885  void WhenRange(Solver::Action action) {
3886  WhenRange(solver()->MakeActionDemon(std::move(action)));
3887  }
3888 #endif // SWIG
3889 
3891  virtual void Accept(ModelVisitor* const visitor) const;
3892 
3893  private:
3894  DISALLOW_COPY_AND_ASSIGN(IntExpr);
3895 };
3896 
3904 
3907 
3913 
3914 class IntVarIterator : public BaseObject {
3915  public:
3916  ~IntVarIterator() override {}
3917 
3919  virtual void Init() = 0;
3920 
3922  virtual bool Ok() const = 0;
3923 
3925  virtual int64 Value() const = 0;
3926 
3928  virtual void Next() = 0;
3929 
3931  std::string DebugString() const override { return "IntVar::Iterator"; }
3932 };
3933 
3934 #ifndef SWIG
3942  public:
3944  : it_(it), begin_was_called_(false) {
3945  it_->Init();
3946  }
3947  struct Iterator;
3949  if (DEBUG_MODE) {
3950  DCHECK(!begin_was_called_);
3951  begin_was_called_ = true;
3952  }
3953  return Iterator::Begin(it_);
3954  }
3955  Iterator end() { return Iterator::End(it_); }
3956 
3957  struct Iterator {
3960  return Iterator(it, /*is_end=*/false);
3961  }
3963  return Iterator(it, /*is_end=*/true);
3964  }
3965 
3966  int64 operator*() const {
3967  DCHECK(it_->Ok());
3968  return it_->Value();
3969  }
3971  DCHECK(it_->Ok());
3972  it_->Next();
3973  return *this;
3974  }
3975  bool operator!=(const Iterator& other) const {
3976  DCHECK(other.it_ == it_);
3977  DCHECK(other.is_end_);
3978  return it_->Ok();
3979  }
3980 
3981  private:
3982  Iterator(IntVarIterator* it, bool is_end) : it_(it), is_end_(is_end) {}
3983 
3984  IntVarIterator* const it_;
3985  const bool is_end_;
3986  };
3987 
3988  private:
3989  IntVarIterator* const it_;
3990  bool begin_was_called_;
3991 };
3992 #endif // SWIG
3993 
3997 class IntVar : public IntExpr {
3998  public:
3999  explicit IntVar(Solver* const s);
4000  IntVar(Solver* const s, const std::string& name);
4001  ~IntVar() override {}
4002 
4003  bool IsVar() const override { return true; }
4004  IntVar* Var() override { return this; }
4005 
4008  virtual int64 Value() const = 0;
4009 
4011  virtual void RemoveValue(int64 v) = 0;
4012 
4015  virtual void RemoveInterval(int64 l, int64 u) = 0;
4016 
4018  virtual void RemoveValues(const std::vector<int64>& values);
4019 
4021  virtual void SetValues(const std::vector<int64>& values);
4022 
4025  virtual void WhenBound(Demon* d) = 0;
4028  void WhenBound(Solver::Closure closure) {
4029  WhenBound(solver()->MakeClosureDemon(std::move(closure)));
4030  }
4031 
4032 #if !defined(SWIG)
4035  void WhenBound(Solver::Action action) {
4036  WhenBound(solver()->MakeActionDemon(std::move(action)));
4037  }
4038 #endif // SWIG
4039 
4042  virtual void WhenDomain(Demon* d) = 0;
4045  void WhenDomain(Solver::Closure closure) {
4046  WhenDomain(solver()->MakeClosureDemon(std::move(closure)));
4047  }
4048 #if !defined(SWIG)
4052  WhenDomain(solver()->MakeActionDemon(std::move(action)));
4053  }
4054 #endif // SWIG
4055 
4057  virtual uint64 Size() const = 0;
4058 
4061  virtual bool Contains(int64 v) const = 0;
4062 
4066  virtual IntVarIterator* MakeHoleIterator(bool reversible) const = 0;
4067 
4071  virtual IntVarIterator* MakeDomainIterator(bool reversible) const = 0;
4072 
4074  virtual int64 OldMin() const = 0;
4075 
4077  virtual int64 OldMax() const = 0;
4078 
4079  virtual int VarType() const;
4080 
4082  void Accept(ModelVisitor* const visitor) const override;
4083 
4085  virtual IntVar* IsEqual(int64 constant) = 0;
4086  virtual IntVar* IsDifferent(int64 constant) = 0;
4087  virtual IntVar* IsGreaterOrEqual(int64 constant) = 0;
4088  virtual IntVar* IsLessOrEqual(int64 constant) = 0;
4089 
4091  int index() const { return index_; }
4092 
4093  private:
4094  const int index_;
4095  DISALLOW_COPY_AND_ASSIGN(IntVar);
4096 };
4097 
4102  public:
4103  SolutionCollector(Solver* const solver, const Assignment* assignment);
4104  explicit SolutionCollector(Solver* const solver);
4105  ~SolutionCollector() override;
4106  std::string DebugString() const override { return "SolutionCollector"; }
4107 
4109  void Add(IntVar* const var);
4110  void Add(const std::vector<IntVar*>& vars);
4111  void Add(IntervalVar* const var);
4112  void Add(const std::vector<IntervalVar*>& vars);
4113  void Add(SequenceVar* const var);
4114  void Add(const std::vector<SequenceVar*>& vars);
4115  void AddObjective(IntVar* const objective);
4116 
4118  void EnterSearch() override;
4119 
4121  int solution_count() const;
4122 
4124  Assignment* solution(int n) const;
4125 
4127  int64 wall_time(int n) const;
4128 
4130  int64 branches(int n) const;
4131 
4134  int64 failures(int n) const;
4135 
4137  int64 objective_value(int n) const;
4138 
4140  int64 Value(int n, IntVar* const var) const;
4141 
4143  int64 StartValue(int n, IntervalVar* const var) const;
4144 
4146  int64 EndValue(int n, IntervalVar* const var) const;
4147 
4149  int64 DurationValue(int n, IntervalVar* const var) const;
4150 
4152  int64 PerformedValue(int n, IntervalVar* const var) const;
4153 
4157  const std::vector<int>& ForwardSequence(int n, SequenceVar* const var) const;
4161  const std::vector<int>& BackwardSequence(int n, SequenceVar* const var) const;
4164  const std::vector<int>& Unperformed(int n, SequenceVar* const var) const;
4165 
4166  protected:
4167  struct SolutionData {
4173  bool operator<(const SolutionData& other) const {
4174  return std::tie(solution, time, branches, failures, objective_value) <
4175  std::tie(other.solution, other.time, other.branches,
4176  other.failures, other.objective_value);
4177  }
4178  };
4179 
4181  void PushSolution();
4182  void Push(const SolutionData& data) { solution_data_.push_back(data); }
4184  void PopSolution();
4185  SolutionData BuildSolutionDataForCurrentState();
4187  void check_index(int n) const;
4188 
4189  std::unique_ptr<Assignment> prototype_;
4190  std::vector<SolutionData> solution_data_;
4191  std::vector<Assignment*> recycle_solutions_;
4192 
4193  private:
4194  DISALLOW_COPY_AND_ASSIGN(SolutionCollector);
4195 };
4196 
4197 // TODO(user): Refactor this into an Objective class:
4198 // - print methods for AtNode and AtSolution.
4199 // - support for weighted objective and lexicographical objective.
4200 
4204 class OptimizeVar : public SearchMonitor {
4205  public:
4206  OptimizeVar(Solver* const s, bool maximize, IntVar* const a, int64 step);
4207  ~OptimizeVar() override;
4208 
4210  int64 best() const { return best_; }
4211 
4213  IntVar* Var() const { return var_; }
4215  bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;
4216  void EnterSearch() override;
4217  void BeginNextDecision(DecisionBuilder* const db) override;
4218  void RefuteDecision(Decision* const d) override;
4219  bool AtSolution() override;
4220  bool AcceptSolution() override;
4221  virtual std::string Print() const;
4222  std::string DebugString() const override;
4223  void Accept(ModelVisitor* const visitor) const override;
4224 
4225  void ApplyBound();
4226 
4227  protected:
4228  IntVar* const var_;
4233 
4234  private:
4235  DISALLOW_COPY_AND_ASSIGN(OptimizeVar);
4236 };
4237 
4239 class SearchLimit : public SearchMonitor {
4240  public:
4241  explicit SearchLimit(Solver* const s) : SearchMonitor(s), crossed_(false) {}
4242  ~SearchLimit() override;
4243 
4245  bool crossed() const { return crossed_; }
4246 
4251  virtual bool Check() = 0;
4252 
4254  virtual void Init() = 0;
4255 
4258  virtual void Copy(const SearchLimit* const limit) = 0;
4259 
4261  virtual SearchLimit* MakeClone() const = 0;
4262 
4264  void EnterSearch() override;
4265  void BeginNextDecision(DecisionBuilder* const b) override;
4266  void PeriodicCheck() override;
4267  void RefuteDecision(Decision* const d) override;
4268  std::string DebugString() const override {
4269  return absl::StrFormat("SearchLimit(crossed = %i)", crossed_);
4270  }
4271 
4272  private:
4273  void TopPeriodicCheck();
4274 
4275  bool crossed_;
4276  DISALLOW_COPY_AND_ASSIGN(SearchLimit);
4277 };
4278 
4281 class RegularLimit : public SearchLimit {
4282  public:
4283  RegularLimit(Solver* const s, absl::Duration time, int64 branches,
4284  int64 failures, int64 solutions, bool smart_time_check,
4285  bool cumulative);
4286  ~RegularLimit() override;
4287  void Copy(const SearchLimit* const limit) override;
4288  SearchLimit* MakeClone() const override;
4290  bool Check() override;
4291  void Init() override;
4292  void ExitSearch() override;
4293  void UpdateLimits(absl::Duration time, int64 branches, int64 failures,
4294  int64 solutions);
4295  absl::Duration duration_limit() const { return duration_limit_; }
4296  int64 wall_time() const {
4297  return duration_limit_ == absl::InfiniteDuration()
4298  ? kint64max
4299  : absl::ToInt64Milliseconds(duration_limit());
4300  }
4301  int64 branches() const { return branches_; }
4302  int64 failures() const { return failures_; }
4303  int64 solutions() const { return solutions_; }
4304  bool IsUncheckedSolutionLimitReached() override;
4305  int ProgressPercent() override;
4306  std::string DebugString() const override;
4307 
4308  absl::Time AbsoluteSolverDeadline() const {
4309  return solver_time_at_limit_start_ + duration_limit_;
4310  }
4311 
4312  void Accept(ModelVisitor* const visitor) const override;
4313 
4314  private:
4315  bool CheckTime();
4316  absl::Duration TimeElapsed();
4317  static int64 GetPercent(int64 value, int64 offset, int64 total) {
4318  return (total > 0 && total < kint64max) ? 100 * (value - offset) / total
4319  : -1;
4320  }
4321 
4322  absl::Duration duration_limit_;
4323  absl::Time solver_time_at_limit_start_;
4324  absl::Duration last_time_elapsed_;
4325  int64 check_count_;
4326  int64 next_check_;
4327  bool smart_time_check_;
4328  int64 branches_;
4329  int64 branches_offset_;
4330  int64 failures_;
4331  int64 failures_offset_;
4332  int64 solutions_;
4333  int64 solutions_offset_;
4341  bool cumulative_;
4342 };
4343 
4344 // Limit based on the improvement rate of 'objective_var'.
4345 // This limit proceeds in two stages:
4346 // 1) During the phase of the search in which the objective_var is strictly
4347 // improving, a threshold value is computed as the minimum improvement rate of
4348 // the objective, based on the 'improvement_rate_coefficient' and
4349 // 'improvement_rate_solutions_distance' parameters.
4350 // 2) Then, if the search continues beyond this phase of strict improvement, the
4351 // limit stops the search when the improvement rate of the objective gets below
4352 // this threshold value.
4354  public:
4355  ImprovementSearchLimit(Solver* const s, IntVar* objective_var, bool maximize,
4356  double objective_scaling_factor,
4357  double objective_offset,
4358  double improvement_rate_coefficient,
4359  int improvement_rate_solutions_distance);
4360  ~ImprovementSearchLimit() override;
4361  void Copy(const SearchLimit* const limit) override;
4362  SearchLimit* MakeClone() const override;
4363  bool Check() override;
4364  bool AtSolution() override;
4365  void Init() override;
4366 
4367  private:
4368  IntVar* objective_var_;
4369  bool maximize_;
4370  double objective_scaling_factor_;
4371  double objective_offset_;
4372  double improvement_rate_coefficient_;
4373  int improvement_rate_solutions_distance_;
4374 
4375  double best_objective_;
4376  // clang-format off
4377  std::deque<std::pair<double, int64> > improvements_;
4378  // clang-format on
4379  double threshold_;
4380  bool objective_updated_;
4381  bool gradient_stage_;
4382 };
4383 
4395  public:
4397  static const int64 kMinValidValue;
4399  static const int64 kMaxValidValue;
4400  IntervalVar(Solver* const solver, const std::string& name)
4402  set_name(name);
4403  }
4404  ~IntervalVar() override {}
4405 
4408  virtual int64 StartMin() const = 0;
4409  virtual int64 StartMax() const = 0;
4410  virtual void SetStartMin(int64 m) = 0;
4411  virtual void SetStartMax(int64 m) = 0;
4412  virtual void SetStartRange(int64 mi, int64 ma) = 0;
4413  virtual int64 OldStartMin() const = 0;
4414  virtual int64 OldStartMax() const = 0;
4415  virtual void WhenStartRange(Demon* const d) = 0;
4417  WhenStartRange(solver()->MakeClosureDemon(std::move(closure)));
4418  }
4419 #if !defined(SWIG)
4421  WhenStartRange(solver()->MakeActionDemon(std::move(action)));
4422  }
4423 #endif // SWIG
4424  virtual void WhenStartBound(Demon* const d) = 0;
4426  WhenStartBound(solver()->MakeClosureDemon(std::move(closure)));
4427  }
4428 #if !defined(SWIG)
4430  WhenStartBound(solver()->MakeActionDemon(std::move(action)));
4431  }
4432 #endif // SWIG
4433 
4435  virtual int64 DurationMin() const = 0;
4436  virtual int64 DurationMax() const = 0;
4437  virtual void SetDurationMin(int64 m) = 0;
4438  virtual void SetDurationMax(int64 m) = 0;
4439  virtual void SetDurationRange(int64 mi, int64 ma) = 0;
4440  virtual int64 OldDurationMin() const = 0;
4441  virtual int64 OldDurationMax() const = 0;
4442  virtual void WhenDurationRange(Demon* const d) = 0;
4444  WhenDurationRange(solver()->MakeClosureDemon(std::move(closure)));
4445  }
4446 #if !defined(SWIG)
4448  WhenDurationRange(solver()->MakeActionDemon(std::move(action)));
4449  }
4450 #endif // SWIG
4451  virtual void WhenDurationBound(Demon* const d) = 0;
4453  WhenDurationBound(solver()->MakeClosureDemon(std::move(closure)));
4454  }
4455 #if !defined(SWIG)
4457  WhenDurationBound(solver()->MakeActionDemon(std::move(action)));
4458  }
4459 #endif // SWIG
4460 
4462  virtual int64 EndMin() const = 0;
4463  virtual int64 EndMax() const = 0;
4464  virtual void SetEndMin(int64 m) = 0;
4465  virtual void SetEndMax(int64 m) = 0;
4466  virtual void SetEndRange(int64 mi, int64 ma) = 0;
4467  virtual int64 OldEndMin() const = 0;
4468  virtual int64 OldEndMax() const = 0;
4469  virtual void WhenEndRange(Demon* const d) = 0;
4471  WhenEndRange(solver()->MakeClosureDemon(std::move(closure)));
4472  }
4473 #if !defined(SWIG)
4475  WhenEndRange(solver()->MakeActionDemon(std::move(action)));
4476  }
4477 #endif // SWIG
4478  virtual void WhenEndBound(Demon* const d) = 0;
4480  WhenEndBound(solver()->MakeClosureDemon(std::move(closure)));
4481  }
4482 #if !defined(SWIG)
4484  WhenEndBound(solver()->MakeActionDemon(std::move(action)));
4485  }
4486 #endif // SWIG
4487 
4490  virtual bool MustBePerformed() const = 0;
4491  virtual bool MayBePerformed() const = 0;
4492  bool CannotBePerformed() const { return !MayBePerformed(); }
4493  bool IsPerformedBound() const {
4494  return MustBePerformed() || !MayBePerformed();
4495  }
4496  virtual void SetPerformed(bool val) = 0;
4497  virtual bool WasPerformedBound() const = 0;
4498  virtual void WhenPerformedBound(Demon* const d) = 0;
4500  WhenPerformedBound(solver()->MakeClosureDemon(std::move(closure)));
4501  }
4502 #if !defined(SWIG)
4504  WhenPerformedBound(solver()->MakeActionDemon(std::move(action)));
4505  }
4506 #endif // SWIG
4507 
4509  void WhenAnything(Demon* const d);
4512  WhenAnything(solver()->MakeClosureDemon(std::move(closure)));
4513  }
4514 #if !defined(SWIG)
4517  WhenAnything(solver()->MakeActionDemon(std::move(action)));
4518  }
4519 #endif // SWIG
4520 
4524  virtual IntExpr* StartExpr() = 0;
4525  virtual IntExpr* DurationExpr() = 0;
4526  virtual IntExpr* EndExpr() = 0;
4527  virtual IntExpr* PerformedExpr() = 0;
4531  virtual IntExpr* SafeStartExpr(int64 unperformed_value) = 0;
4532  virtual IntExpr* SafeDurationExpr(int64 unperformed_value) = 0;
4533  virtual IntExpr* SafeEndExpr(int64 unperformed_value) = 0;
4534 
4536  virtual void Accept(ModelVisitor* const visitor) const = 0;
4537 
4538  private:
4539  DISALLOW_COPY_AND_ASSIGN(IntervalVar);
4540 };
4541 
4549  public:
4550  SequenceVar(Solver* const s, const std::vector<IntervalVar*>& intervals,
4551  const std::vector<IntVar*>& nexts, const std::string& name);
4552 
4553  ~SequenceVar() override;
4554 
4555  std::string DebugString() const override;
4556 
4557 #if !defined(SWIG)
4560  void DurationRange(int64* const dmin, int64* const dmax) const;
4561 
4564  void HorizonRange(int64* const hmin, int64* const hmax) const;
4565 
4568  void ActiveHorizonRange(int64* const hmin, int64* const hmax) const;
4569 
4571  void ComputeStatistics(int* const ranked, int* const not_ranked,
4572  int* const unperformed) const;
4573 #endif // !defined(SWIG)
4574 
4577  void RankFirst(int index);
4578 
4581  void RankNotFirst(int index);
4582 
4585  void RankLast(int index);
4586 
4589  void RankNotLast(int index);
4590 
4593  void ComputePossibleFirstsAndLasts(std::vector<int>* const possible_firsts,
4594  std::vector<int>* const possible_lasts);
4595 
4601  void RankSequence(const std::vector<int>& rank_first,
4602  const std::vector<int>& rank_last,
4603  const std::vector<int>& unperformed);
4604 
4613  void FillSequence(std::vector<int>* const rank_first,
4614  std::vector<int>* const rank_last,
4615  std::vector<int>* const unperformed) const;
4616 
4618  IntervalVar* Interval(int index) const;
4619 
4621  IntVar* Next(int index) const;
4622 
4624  int64 size() const { return intervals_.size(); }
4625 
4627  virtual void Accept(ModelVisitor* const visitor) const;
4628 
4629  private:
4630  int ComputeForwardFrontier();
4631  int ComputeBackwardFrontier();
4632  void UpdatePrevious() const;
4633 
4634  const std::vector<IntervalVar*> intervals_;
4635  const std::vector<IntVar*> nexts_;
4636  mutable std::vector<int> previous_;
4637 };
4638 
4640  public:
4641  AssignmentElement() : activated_(true) {}
4642 
4643  void Activate() { activated_ = true; }
4644  void Deactivate() { activated_ = false; }
4645  bool Activated() const { return activated_; }
4646 
4647  private:
4648  bool activated_;
4649 };
4650 
4652  public:
4653  IntVarElement();
4654  explicit IntVarElement(IntVar* const var);
4655  void Reset(IntVar* const var);
4656  IntVarElement* Clone();
4657  void Copy(const IntVarElement& element);
4658  IntVar* Var() const { return var_; }
4659  void Store() {
4660  min_ = var_->Min();
4661  max_ = var_->Max();
4662  }
4663  void Restore() {
4664  if (var_ != nullptr) {
4665  var_->SetRange(min_, max_);
4666  }
4667  }
4668  void LoadFromProto(const IntVarAssignment& int_var_assignment_proto);
4669  void WriteToProto(IntVarAssignment* int_var_assignment_proto) const;
4670 
4671  int64 Min() const { return min_; }
4672  void SetMin(int64 m) { min_ = m; }
4673  int64 Max() const { return max_; }
4674  void SetMax(int64 m) { max_ = m; }
4675  int64 Value() const {
4676  DCHECK_EQ(min_, max_);
4677  // Get the value from an unbound int var assignment element.
4678  return min_;
4679  }
4680  bool Bound() const { return (max_ == min_); }
4681  void SetRange(int64 l, int64 u) {
4682  min_ = l;
4683  max_ = u;
4684  }
4685  void SetValue(int64 v) {
4686  min_ = v;
4687  max_ = v;
4688  }
4689  std::string DebugString() const;
4690 
4691  bool operator==(const IntVarElement& element) const;
4692  bool operator!=(const IntVarElement& element) const {
4693  return !(*this == element);
4694  }
4695 
4696  private:
4697  IntVar* var_;
4698  int64 min_;
4699  int64 max_;
4700 };
4701 
4703  public:
4705  explicit IntervalVarElement(IntervalVar* const var);
4706  void Reset(IntervalVar* const var);
4708  void Copy(const IntervalVarElement& element);
4709  IntervalVar* Var() const { return var_; }
4710  void Store();
4711  void Restore();
4712  void LoadFromProto(
4713  const IntervalVarAssignment& interval_var_assignment_proto);
4714  void WriteToProto(IntervalVarAssignment* interval_var_assignment_proto) const;
4715 
4716  int64 StartMin() const { return start_min_; }
4717  int64 StartMax() const { return start_max_; }
4718  int64 StartValue() const {
4719  CHECK_EQ(start_max_, start_min_);
4720  return start_max_;
4721  }
4722  int64 DurationMin() const { return duration_min_; }
4723  int64 DurationMax() const { return duration_max_; }
4725  CHECK_EQ(duration_max_, duration_min_);
4726  return duration_max_;
4727  }
4728  int64 EndMin() const { return end_min_; }
4729  int64 EndMax() const { return end_max_; }
4730  int64 EndValue() const {
4731  CHECK_EQ(end_max_, end_min_);
4732  return end_max_;
4733  }
4734  int64 PerformedMin() const { return performed_min_; }
4735  int64 PerformedMax() const { return performed_max_; }
4737  CHECK_EQ(performed_max_, performed_min_);
4738  return performed_max_;
4739  }
4740  void SetStartMin(int64 m) { start_min_ = m; }
4741  void SetStartMax(int64 m) { start_max_ = m; }
4742  void SetStartRange(int64 mi, int64 ma) {
4743  start_min_ = mi;
4744  start_max_ = ma;
4745  }
4747  start_min_ = v;
4748  start_max_ = v;
4749  }
4750  void SetDurationMin(int64 m) { duration_min_ = m; }
4751  void SetDurationMax(int64 m) { duration_max_ = m; }
4753  duration_min_ = mi;
4754  duration_max_ = ma;
4755  }
4757  duration_min_ = v;
4758  duration_max_ = v;
4759  }
4760  void SetEndMin(int64 m) { end_min_ = m; }
4761  void SetEndMax(int64 m) { end_max_ = m; }
4762  void SetEndRange(int64 mi, int64 ma) {
4763  end_min_ = mi;
4764  end_max_ = ma;
4765  }
4766  void SetEndValue(int64 v) {
4767  end_min_ = v;
4768  end_max_ = v;
4769  }
4770  void SetPerformedMin(int64 m) { performed_min_ = m; }
4771  void SetPerformedMax(int64 m) { performed_max_ = m; }
4773  performed_min_ = mi;
4774  performed_max_ = ma;
4775  }
4777  performed_min_ = v;
4778  performed_max_ = v;
4779  }
4780  bool Bound() const {
4781  return (start_min_ == start_max_ && duration_min_ == duration_max_ &&
4782  end_min_ == end_max_ && performed_min_ == performed_max_);
4783  }
4784  std::string DebugString() const;
4785  bool operator==(const IntervalVarElement& element) const;
4786  bool operator!=(const IntervalVarElement& element) const {
4787  return !(*this == element);
4788  }
4789 
4790  private:
4791  int64 start_min_;
4792  int64 start_max_;
4793  int64 duration_min_;
4794  int64 duration_max_;
4795  int64 end_min_;
4796  int64 end_max_;
4797  int64 performed_min_;
4798  int64 performed_max_;
4799  IntervalVar* var_;
4800 };
4801 
4816  public:
4818  explicit SequenceVarElement(SequenceVar* const var);
4819  void Reset(SequenceVar* const var);
4821  void Copy(const SequenceVarElement& element);
4822  SequenceVar* Var() const { return var_; }
4823  void Store();
4824  void Restore();
4825  void LoadFromProto(
4826  const SequenceVarAssignment& sequence_var_assignment_proto);
4827  void WriteToProto(SequenceVarAssignment* sequence_var_assignment_proto) const;
4828 
4829  const std::vector<int>& ForwardSequence() const;
4830  const std::vector<int>& BackwardSequence() const;
4831  const std::vector<int>& Unperformed() const;
4832  void SetSequence(const std::vector<int>& forward_sequence,
4833  const std::vector<int>& backward_sequence,
4834  const std::vector<int>& unperformed);
4835  void SetForwardSequence(const std::vector<int>& forward_sequence);
4836  void SetBackwardSequence(const std::vector<int>& backward_sequence);
4837  void SetUnperformed(const std::vector<int>& unperformed);
4838  bool Bound() const {
4839  return forward_sequence_.size() + unperformed_.size() == var_->size();
4840  }
4841 
4842  std::string DebugString() const;
4843 
4844  bool operator==(const SequenceVarElement& element) const;
4845  bool operator!=(const SequenceVarElement& element) const {
4846  return !(*this == element);
4847  }
4848 
4849  private:
4850  bool CheckClassInvariants();
4851 
4852  SequenceVar* var_;
4853  std::vector<int> forward_sequence_;
4854  std::vector<int> backward_sequence_;
4855  std::vector<int> unperformed_;
4856 };
4857 
4858 template <class V, class E>
4860  public:
4862  E* Add(V* var) {
4863  CHECK(var != nullptr);
4864  int index = -1;
4865  if (!Find(var, &index)) {
4866  return FastAdd(var);
4867  } else {
4868  return &elements_[index];
4869  }
4870  }
4872  E* FastAdd(V* var) {
4873  DCHECK(var != nullptr);
4874  elements_.emplace_back(var);
4875  return &elements_.back();
4876  }
4879  E* AddAtPosition(V* var, int position) {
4880  elements_[position].Reset(var);
4881  return &elements_[position];
4882  }
4883  void Clear() {
4884  elements_.clear();
4885  if (!elements_map_.empty()) {
4886  elements_map_.clear();
4887  }
4888  }
4891  void Resize(size_t size) { elements_.resize(size); }
4892  bool Empty() const { return elements_.empty(); }
4896  for (int i = 0; i < container.elements_.size(); ++i) {
4897  const E& element = container.elements_[i];
4898  const V* const var = element.Var();
4899  int index = -1;
4900  if (i < elements_.size() && elements_[i].Var() == var) {
4901  index = i;
4902  } else if (!Find(var, &index)) {
4903  continue;
4904  }
4905  DCHECK_GE(index, 0);
4906  E* const local_element = &elements_[index];
4907  local_element->Copy(element);
4908  if (element.Activated()) {
4909  local_element->Activate();
4910  } else {
4911  local_element->Deactivate();
4912  }
4913  }
4914  }
4917  void Copy(const AssignmentContainer<V, E>& container) {
4918  Clear();
4919  for (int i = 0; i < container.elements_.size(); ++i) {
4920  const E& element = container.elements_[i];
4921  FastAdd(element.Var())->Copy(element);
4922  }
4923  }
4924  bool Contains(const V* const var) const {
4925  int index;
4926  return Find(var, &index);
4927  }
4928  E* MutableElement(const V* const var) {
4929  E* const element = MutableElementOrNull(var);
4930  DCHECK(element != nullptr)
4931  << "Unknown variable " << var->DebugString() << " in solution";
4932  return element;
4933  }
4934  E* MutableElementOrNull(const V* const var) {
4935  int index = -1;
4936  if (Find(var, &index)) {
4937  return MutableElement(index);
4938  }
4939  return nullptr;
4940  }
4941  const E& Element(const V* const var) const {
4942  const E* const element = ElementPtrOrNull(var);
4943  DCHECK(element != nullptr)
4944  << "Unknown variable " << var->DebugString() << " in solution";
4945  return *element;
4946  }
4947  const E* ElementPtrOrNull(const V* const var) const {
4948  int index = -1;
4949  if (Find(var, &index)) {
4950  return &Element(index);
4951  }
4952  return nullptr;
4953  }
4954  const std::vector<E>& elements() const { return elements_; }
4955  E* MutableElement(int index) { return &elements_[index]; }
4956  const E& Element(int index) const { return elements_[index]; }
4957  int Size() const { return elements_.size(); }
4958  void Store() {
4959  for (E& element : elements_) {
4960  element.Store();
4961  }
4962  }
4963  void Restore() {
4964  for (E& element : elements_) {
4965  if (element.Activated()) {
4966  element.Restore();
4967  }
4968  }
4969  }
4970  bool AreAllElementsBound() const {
4971  for (const E& element : elements_) {
4972  if (!element.Bound()) return false;
4973  }
4974  return true;
4975  }
4976 
4980  bool operator==(const AssignmentContainer<V, E>& container) const {
4982  if (Size() != container.Size()) {
4983  return false;
4984  }
4986  EnsureMapIsUpToDate();
4990  for (const E& element : container.elements_) {
4991  const int position =
4992  gtl::FindWithDefault(elements_map_, element.Var(), -1);
4993  if (position < 0 || elements_[position] != element) {
4994  return false;
4995  }
4996  }
4997  return true;
4998  }
4999  bool operator!=(const AssignmentContainer<V, E>& container) const {
5000  return !(*this == container);
5001  }
5002 
5003  private:
5004  void EnsureMapIsUpToDate() const {
5005  absl::flat_hash_map<const V*, int>* map =
5006  const_cast<absl::flat_hash_map<const V*, int>*>(&elements_map_);
5007  for (int i = map->size(); i < elements_.size(); ++i) {
5008  (*map)[elements_[i].Var()] = i;
5009  }
5010  }
5011  bool Find(const V* const var, int* index) const {
5013  const size_t kMaxSizeForLinearAccess = 11;
5014  if (Size() <= kMaxSizeForLinearAccess) {
5018  for (int i = 0; i < elements_.size(); ++i) {
5019  if (var == elements_[i].Var()) {
5020  *index = i;
5021  return true;
5022  }
5023  }
5024  return false;
5025  } else {
5026  EnsureMapIsUpToDate();
5027  DCHECK_EQ(elements_map_.size(), elements_.size());
5028  return gtl::FindCopy(elements_map_, var, index);
5029  }
5030  }
5031 
5032  std::vector<E> elements_;
5033  absl::flat_hash_map<const V*, int> elements_map_;
5034 };
5035 
5039  public:
5045 
5046  explicit Assignment(Solver* const s);
5047  explicit Assignment(const Assignment* const copy);
5048  ~Assignment() override;
5049 
5050  void Clear();
5051  bool Empty() const {
5052  return int_var_container_.Empty() && interval_var_container_.Empty() &&
5053  sequence_var_container_.Empty();
5054  }
5055  int Size() const {
5056  return NumIntVars() + NumIntervalVars() + NumSequenceVars();
5057  }
5058  int NumIntVars() const { return int_var_container_.Size(); }
5059  int NumIntervalVars() const { return interval_var_container_.Size(); }
5060  int NumSequenceVars() const { return sequence_var_container_.Size(); }
5061  void Store();
5062  void Restore();
5063 
5066  bool Load(const std::string& filename);
5067 #if !defined(SWIG)
5068  bool Load(File* file);
5069 #endif
5070  void Load(const AssignmentProto& assignment_proto);
5072  bool Save(const std::string& filename) const;
5073 #if !defined(SWIG)
5074  bool Save(File* file) const;
5075 #endif // #if !defined(SWIG)
5076  void Save(AssignmentProto* const assignment_proto) const;
5077 
5078  void AddObjective(IntVar* const v);
5079  void ClearObjective() { objective_element_.Reset(nullptr); }
5080  IntVar* Objective() const;
5081  bool HasObjective() const { return (objective_element_.Var() != nullptr); }
5082  int64 ObjectiveMin() const;
5083  int64 ObjectiveMax() const;
5084  int64 ObjectiveValue() const;
5085  bool ObjectiveBound() const;
5086  void SetObjectiveMin(int64 m);
5087  void SetObjectiveMax(int64 m);
5089  void SetObjectiveRange(int64 l, int64 u);
5090 
5091  IntVarElement* Add(IntVar* const var);
5092  void Add(const std::vector<IntVar*>& vars);
5094  IntVarElement* FastAdd(IntVar* const var);
5095  int64 Min(const IntVar* const var) const;
5096  int64 Max(const IntVar* const var) const;
5097  int64 Value(const IntVar* const var) const;
5098  bool Bound(const IntVar* const var) const;
5099  void SetMin(const IntVar* const var, int64 m);
5100  void SetMax(const IntVar* const var, int64 m);
5101  void SetRange(const IntVar* const var, int64 l, int64 u);
5102  void SetValue(const IntVar* const var, int64 value);
5103 
5105  void Add(const std::vector<IntervalVar*>& vars);
5108  int64 StartMin(const IntervalVar* const var) const;
5109  int64 StartMax(const IntervalVar* const var) const;
5110  int64 StartValue(const IntervalVar* const var) const;
5111  int64 DurationMin(const IntervalVar* const var) const;
5112  int64 DurationMax(const IntervalVar* const var) const;
5113  int64 DurationValue(const IntervalVar* const var) const;
5114  int64 EndMin(const IntervalVar* const var) const;
5115  int64 EndMax(const IntervalVar* const var) const;
5116  int64 EndValue(const IntervalVar* const var) const;
5117  int64 PerformedMin(const IntervalVar* const var) const;
5118  int64 PerformedMax(const IntervalVar* const var) const;
5119  int64 PerformedValue(const IntervalVar* const var) const;
5120  void SetStartMin(const IntervalVar* const var, int64 m);
5121  void SetStartMax(const IntervalVar* const var, int64 m);
5122  void SetStartRange(const IntervalVar* const var, int64 mi, int64 ma);
5123  void SetStartValue(const IntervalVar* const var, int64 value);
5124  void SetDurationMin(const IntervalVar* const var, int64 m);
5125  void SetDurationMax(const IntervalVar* const var, int64 m);
5126  void SetDurationRange(const IntervalVar* const var, int64 mi, int64 ma);
5127  void SetDurationValue(const IntervalVar* const var, int64 value);
5128  void SetEndMin(const IntervalVar* const var, int64 m);
5129  void SetEndMax(const IntervalVar* const var, int64 m);
5130  void SetEndRange(const IntervalVar* const var, int64 mi, int64 ma);
5131  void SetEndValue(const IntervalVar* const var, int64 value);
5132  void SetPerformedMin(const IntervalVar* const var, int64 m);
5133  void SetPerformedMax(const IntervalVar* const var, int64 m);
5134  void SetPerformedRange(const IntervalVar* const var, int64 mi, int64 ma);
5135  void SetPerformedValue(const IntervalVar* const var, int64 value);
5136 
5138  void Add(const std::vector<SequenceVar*>& vars);
5141  const std::vector<int>& ForwardSequence(const SequenceVar* const var) const;
5142  const std::vector<int>& BackwardSequence(const SequenceVar* const var) const;
5143  const std::vector<int>& Unperformed(const SequenceVar* const var) const;
5144  void SetSequence(const SequenceVar* const var,
5145  const std::vector<int>& forward_sequence,
5146  const std::vector<int>& backward_sequence,
5147  const std::vector<int>& unperformed);
5148  void SetForwardSequence(const SequenceVar* const var,
5149  const std::vector<int>& forward_sequence);
5150  void SetBackwardSequence(const SequenceVar* const var,
5151  const std::vector<int>& backward_sequence);
5152  void SetUnperformed(const SequenceVar* const var,
5153  const std::vector<int>& unperformed);
5154 
5155  void Activate(const IntVar* const var);
5156  void Deactivate(const IntVar* const var);
5157  bool Activated(const IntVar* const var) const;
5158 
5159  void Activate(const IntervalVar* const var);
5160  void Deactivate(const IntervalVar* const var);
5161  bool Activated(const IntervalVar* const var) const;
5162 
5163  void Activate(const SequenceVar* const var);
5164  void Deactivate(const SequenceVar* const var);
5165  bool Activated(const SequenceVar* const var) const;
5166 
5167  void ActivateObjective();
5168  void DeactivateObjective();
5169  bool ActivatedObjective() const;
5170 
5171  std::string DebugString() const override;
5172 
5173  bool AreAllElementsBound() const {
5174  return int_var_container_.AreAllElementsBound() &&
5175  interval_var_container_.AreAllElementsBound() &&
5176  sequence_var_container_.AreAllElementsBound();
5177  }
5178 
5179  bool Contains(const IntVar* const var) const;
5180  bool Contains(const IntervalVar* const var) const;
5181  bool Contains(const SequenceVar* const var) const;
5183  void CopyIntersection(const Assignment* assignment);
5186  void Copy(const Assignment* assignment);
5187 
5188  // TODO(user): Add element iterators to avoid exposing container class.
5189  const IntContainer& IntVarContainer() const { return int_var_container_; }
5190  IntContainer* MutableIntVarContainer() { return &int_var_container_; }
5192  return interval_var_container_;
5193  }
5195  return &interval_var_container_;
5196  }
5198  return sequence_var_container_;
5199  }
5201  return &sequence_var_container_;
5202  }
5203  bool operator==(const Assignment& assignment) const {
5204  return int_var_container_ == assignment.int_var_container_ &&
5205  interval_var_container_ == assignment.interval_var_container_ &&
5206  sequence_var_container_ == assignment.sequence_var_container_ &&
5207  objective_element_ == assignment.objective_element_;
5208  }
5209  bool operator!=(const Assignment& assignment) const {
5210  return !(*this == assignment);
5211  }
5212 
5213  private:
5214  IntContainer int_var_container_;
5215  IntervalContainer interval_var_container_;
5216  SequenceContainer sequence_var_container_;
5217  IntVarElement objective_element_;
5218  DISALLOW_COPY_AND_ASSIGN(Assignment);
5219 };
5220 
5221 std::ostream& operator<<(std::ostream& out,
5222  const Assignment& assignment);
5223 
5229 void SetAssignmentFromAssignment(Assignment* target_assignment,
5230  const std::vector<IntVar*>& target_vars,
5231  const Assignment* source_assignment,
5232  const std::vector<IntVar*>& source_vars);
5233 
5234 class Pack : public Constraint {
5235  public:
5236  Pack(Solver* const s, const std::vector<IntVar*>& vars, int number_of_bins);
5237 
5238  ~Pack() override;
5239 
5244 
5249  const std::vector<int64>& weights, const std::vector<int64>& bounds);
5250 
5256  Solver::IndexEvaluator1 weights, const std::vector<int64>& bounds);
5257 
5263  Solver::IndexEvaluator2 weights, const std::vector<int64>& bounds);
5264 
5267  void AddWeightedSumEqualVarDimension(const std::vector<int64>& weights,
5268  const std::vector<IntVar*>& loads);
5269 
5274  const std::vector<IntVar*>& loads);
5275 
5286  const std::vector<IntVar*>& usage, const std::vector<int64>& capacity);
5287 
5290  void AddWeightedSumOfAssignedDimension(const std::vector<int64>& weights,
5291  IntVar* const cost_var);
5292 
5295  void AddCountUsedBinDimension(IntVar* const count_var);
5296 
5299  void AddCountAssignedItemsDimension(IntVar* const count_var);
5300 
5301  void Post() override;
5302  void ClearAll();
5303  void PropagateDelayed();
5304  void InitialPropagate() override;
5305  void Propagate();
5306  void OneDomain(int var_index);
5307  std::string DebugString() const override;
5308  bool IsUndecided(int var_index, int bin_index) const;
5309  void SetImpossible(int var_index, int bin_index);
5310  void Assign(int var_index, int bin_index);
5311  bool IsAssignedStatusKnown(int var_index) const;
5312  bool IsPossible(int var_index, int bin_index) const;
5313  IntVar* AssignVar(int var_index, int bin_index) const;
5314  void SetAssigned(int var_index);
5315  void SetUnassigned(int var_index);
5316  void RemoveAllPossibleFromBin(int bin_index);
5317  void AssignAllPossibleToBin(int bin_index);
5318  void AssignFirstPossibleToBin(int bin_index);
5319  void AssignAllRemainingItems();
5321  void Accept(ModelVisitor* const visitor) const override;
5322 
5323  private:
5324  bool IsInProcess() const;
5325  const std::vector<IntVar*> vars_;
5326  const int bins_;
5327  std::vector<Dimension*> dims_;
5328  std::unique_ptr<RevBitMatrix> unprocessed_;
5329  std::vector<std::vector<int>> forced_;
5330  std::vector<std::vector<int>> removed_;
5331  std::vector<IntVarIterator*> holes_;
5332  uint64 stamp_;
5333  Demon* demon_;
5334  std::vector<std::pair<int, int>> to_set_;
5335  std::vector<std::pair<int, int>> to_unset_;
5336  bool in_process_;
5337 };
5338 
5340  public:
5341  DisjunctiveConstraint(Solver* const s,
5342  const std::vector<IntervalVar*>& intervals,
5343  const std::string& name);
5344  ~DisjunctiveConstraint() override;
5345 
5348 
5353  void SetTransitionTime(Solver::IndexEvaluator2 transition_time);
5354 
5355  int64 TransitionTime(int before_index, int after_index) {
5357  return transition_time_(before_index, after_index);
5358  }
5359 
5360 #if !defined(SWIG)
5361  virtual const std::vector<IntVar*>& nexts() const = 0;
5362  virtual const std::vector<IntVar*>& actives() const = 0;
5363  virtual const std::vector<IntVar*>& time_cumuls() const = 0;
5364  virtual const std::vector<IntVar*>& time_slacks() const = 0;
5365 #endif // !defined(SWIG)
5366 
5367  protected:
5368  const std::vector<IntervalVar*> intervals_;
5370 
5371  private:
5372  DISALLOW_COPY_AND_ASSIGN(DisjunctiveConstraint);
5373 };
5374 
5377 class SolutionPool : public BaseObject {
5378  public:
5380  ~SolutionPool() override {}
5381 
5384  virtual void Initialize(Assignment* const assignment) = 0;
5385 
5388  virtual void RegisterNewSolution(Assignment* const assignment) = 0;
5389 
5392  virtual void GetNextSolution(Assignment* const assignment) = 0;
5393 
5396  virtual bool SyncNeeded(Assignment* const local_assignment) = 0;
5397 };
5398 } // namespace operations_research
5399 
5400 #endif // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
Definition: base/file.h:32
bool operator==(const AssignmentContainer< V, E > &container) const
Returns true if this and 'container' both represent the same V* -> E map.
const E * ElementPtrOrNull(const V *const var) const
const std::vector< E > & elements() const
bool Contains(const V *const var) const
E * AddAtPosition(V *var, int position)
Advanced usage: Adds element at a given position; position has to have been allocated with Assignment...
void Copy(const AssignmentContainer< V, E > &container)
Copies all the elements of 'container' to this container, clearing its previous content.
bool operator!=(const AssignmentContainer< V, E > &container) const
const E & Element(const V *const var) const
void CopyIntersection(const AssignmentContainer< V, E > &container)
Copies the elements of 'container' which are already in the calling container.
void Resize(size_t size)
Advanced usage: Resizes the container, potentially adding elements with null variables.
E * FastAdd(V *var)
Adds element without checking its presence in the container.
An Assignment is a variable -> domains mapping, used to report solutions to the user.
const std::vector< int > & Unperformed(const SequenceVar *const var) const
int64 DurationMin(const IntervalVar *const var) const
void SetForwardSequence(const SequenceVar *const var, const std::vector< int > &forward_sequence)
int64 Value(const IntVar *const var) const
void Deactivate(const IntVar *const var)
void SetStartMin(const IntervalVar *const var, int64 m)
void SetBackwardSequence(const SequenceVar *const var, const std::vector< int > &backward_sequence)
const IntContainer & IntVarContainer() const
const std::vector< int > & BackwardSequence(const SequenceVar *const var) const
void SetDurationValue(const IntervalVar *const var, int64 value)
void SetEndMax(const IntervalVar *const var, int64 m)
const SequenceContainer & SequenceVarContainer() const
int64 EndMax(const IntervalVar *const var) const
int64 StartValue(const IntervalVar *const var) const
AssignmentContainer< SequenceVar, SequenceVarElement > SequenceContainer
void SetStartMax(const IntervalVar *const var, int64 m)
void SetPerformedValue(const IntervalVar *const var, int64 value)
int64 PerformedMin(const IntervalVar *const var) const
bool Load(const std::string &filename)
Loads an assignment from a file; does not add variables to the assignment (only the variables contain...
int64 Min(const IntVar *const var) const
bool Contains(const IntVar *const var) const
bool Activated(const IntVar *const var) const
bool Save(const std::string &filename) const
Saves the assignment to a file.
int64 EndMin(const IntervalVar *const var) const
void SetMax(const IntVar *const var, int64 m)
void SetPerformedRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetEndMin(const IntervalVar *const var, int64 m)
const std::vector< int > & ForwardSequence(const SequenceVar *const var) const
int64 StartMin(const IntervalVar *const var) const
void SetPerformedMin(const IntervalVar *const var, int64 m)
void SetMin(const IntVar *const var, int64 m)
SequenceContainer * MutableSequenceVarContainer()
void SetPerformedMax(const IntervalVar *const var, int64 m)
int64 Max(const IntVar *const var) const
IntervalContainer * MutableIntervalVarContainer()
void SetEndValue(const IntervalVar *const var, int64 value)
void SetUnperformed(const SequenceVar *const var, const std::vector< int > &unperformed)
int64 DurationMax(const IntervalVar *const var) const
bool operator==(const Assignment &assignment) const
void SetStartValue(const IntervalVar *const var, int64 value)
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
void SetDurationMax(const IntervalVar *const var, int64 m)
AssignmentContainer< IntervalVar, IntervalVarElement > IntervalContainer
void SetStartRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetValue(const IntVar *const var, int64 value)
void Copy(const Assignment *assignment)
Copies 'assignment' to the current assignment, clearing its previous content.
int64 PerformedMax(const IntervalVar *const var) const
AssignmentContainer< IntVar, IntVarElement > IntContainer
void SetSequence(const SequenceVar *const var, const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
int64 DurationValue(const IntervalVar *const var) const
void SetDurationMin(const IntervalVar *const var, int64 m)
int64 StartMax(const IntervalVar *const var) const
int64 EndValue(const IntervalVar *const var) const
int64 PerformedValue(const IntervalVar *const var) const
IntVarElement * Add(IntVar *const var)
void SetEndRange(const IntervalVar *const var, int64 mi, int64 ma)
void SetDurationRange(const IntervalVar *const var, int64 mi, int64 ma)
const IntervalContainer & IntervalVarContainer() const
bool Bound(const IntVar *const var) const
IntVarElement * FastAdd(IntVar *const var)
Adds without checking if variable has been previously added.
void SetRange(const IntVar *const var, int64 l, int64 u)
bool operator!=(const Assignment &assignment) const
This is the base class for all expressions that are not variables.
A BaseObject is the root of all reversibly allocated objects.
virtual std::string DebugString() const
Cast constraints are special channeling constraints designed to keep a variable in sync with an expre...
CastConstraint(Solver *const solver, IntVar *const target_var)
A constraint is the main modeling object.
void PostAndPropagate()
Calls Post and then Propagate to initialize the constraints.
bool IsCastConstraint() const
Is the constraint created by a cast from expression to integer variable?
virtual void InitialPropagate()=0
This method performs the initial propagation of the constraint.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
virtual IntVar * Var()
Creates a Boolean variable representing the status of the constraint (false = constraint is violated,...
std::string DebugString() const override
virtual void Post()=0
This method is called when the constraint is processed by the solver.
A DecisionBuilder is responsible for creating the search tree.
virtual Decision * Next(Solver *const s)=0
This is the main method of the decision builder class.
virtual void Accept(ModelVisitor *const visitor) const
virtual void AppendMonitors(Solver *const solver, std::vector< SearchMonitor * > *const extras)
This method will be called at the start of the search.
std::string DebugString() const override
A Decision represents a choice point in the search tree.
virtual void Accept(DecisionVisitor *const visitor) const
Accepts the given visitor.
virtual void Apply(Solver *const s)=0
Apply will be called first when the decision is executed.
virtual void Refute(Solver *const s)=0
Refute will be called after a backtrack.
std::string DebugString() const override
A DecisionVisitor is used to inspect a decision.
virtual void VisitSplitVariableDomain(IntVar *const var, int64 value, bool start_with_lower_half)
virtual void VisitRankFirstInterval(SequenceVar *const sequence, int index)
virtual void VisitScheduleOrPostpone(IntervalVar *const var, int64 est)
virtual void VisitScheduleOrExpedite(IntervalVar *const var, int64 est)
virtual void VisitRankLastInterval(SequenceVar *const sequence, int index)
virtual void VisitSetVariableValue(IntVar *const var, int64 value)
A Demon is the base element of a propagation queue.
void inhibit(Solver *const s)
This method inhibits the demon in the search tree below the current position.
Demon()
This indicates the priority of a demon.
void desinhibit(Solver *const s)
This method un-inhibits the demon that was previously inhibited.
virtual Solver::DemonPriority priority() const
This method returns the priority of the demon.
std::string DebugString() const override
virtual void Run(Solver *const s)=0
This is the main callback of the demon.
const std::vector< IntervalVar * > intervals_
virtual const std::vector< IntVar * > & time_cumuls() const =0
virtual const std::vector< IntVar * > & actives() const =0
virtual SequenceVar * MakeSequenceVar()=0
Creates a sequence variable from the constraint.
int64 TransitionTime(int before_index, int after_index)
virtual const std::vector< IntVar * > & nexts() const =0
DisjunctiveConstraint(Solver *const s, const std::vector< IntervalVar * > &intervals, const std::string &name)
Definition: resource.cc:2551
void SetTransitionTime(Solver::IndexEvaluator2 transition_time)
Add a transition time between intervals.
Definition: resource.cc:2563
virtual const std::vector< IntVar * > & time_slacks() const =0
bool Check() override
This method is called to check the status of the limit.
Definition: search.cc:4194
void Init() override
This method is called when the search limit is initialized.
Definition: search.cc:4162
void Copy(const SearchLimit *const limit) override
Copy a limit.
Definition: search.cc:4170
bool AtSolution() override
This method is called when a valid solution is found.
Definition: search.cc:4218
ImprovementSearchLimit(Solver *const s, IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
Definition: search.cc:4144
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Definition: search.cc:4187
Utility class to encapsulate an IntVarIterator and use it in a range-based loop.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual void SetMax(int64 m)=0
virtual IntVar * Var()=0
Creates a variable from the expression.
void WhenRange(Solver::Closure closure)
Attach a demon that will watch the min or the max of the expression.
virtual void SetRange(int64 l, int64 u)
This method sets both the min and the max of the expression.
virtual void SetValue(int64 v)
This method sets the value of the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual void SetMin(int64 m)=0
virtual bool IsVar() const
Returns true if the expression is indeed a variable.
virtual void Range(int64 *l, int64 *u)
By default calls Min() and Max(), but can be redefined when Min and Max code can be factorized.
virtual int64 Max() const =0
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
IntVar * VarWithName(const std::string &name)
Creates a variable from the expression and set the name of the resulting var.
Definition: expressions.cc:49
virtual int64 Min() const =0
virtual void WhenRange(Demon *d)=0
Attach a demon that will watch the min or the max of the expression.
void WhenRange(Solver::Action action)
Attach a demon that will watch the min or the max of the expression.
void Copy(const IntVarElement &element)
bool operator!=(const IntVarElement &element) const
bool operator==(const IntVarElement &element) const
void WriteToProto(IntVarAssignment *int_var_assignment_proto) const
void LoadFromProto(const IntVarAssignment &int_var_assignment_proto)
The class IntVar is a subset of IntExpr.
virtual int64 OldMax() const =0
Returns the previous max.
IntVar * Var() override
Creates a variable from the expression.
void WhenBound(Solver::Closure closure)
This method attaches a closure that will be awakened when the variable is bound.
virtual void RemoveValue(int64 v)=0
This method removes the value 'v' from the domain of the variable.
virtual IntVar * IsDifferent(int64 constant)=0
virtual void SetValues(const std::vector< int64 > &values)
This method intersects the current domain with the values in the array.
IntVar(Solver *const s)
Definition: expressions.cc:57
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
virtual bool Contains(int64 v) const =0
This method returns whether the value 'v' is in the domain of the variable.
void WhenDomain(Solver::Closure closure)
This method attaches a closure that will watch any domain modification of the domain of the variable.
virtual IntVarIterator * MakeHoleIterator(bool reversible) const =0
Creates a hole iterator.
virtual IntVar * IsEqual(int64 constant)=0
IsEqual.
void WhenDomain(Solver::Action action)
This method attaches an action that will watch any domain modification of the domain of the variable.
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
virtual void RemoveValues(const std::vector< int64 > &values)
This method remove the values from the domain of the variable.
virtual IntVarIterator * MakeDomainIterator(bool reversible) const =0
Creates a domain iterator.
virtual IntVar * IsLessOrEqual(int64 constant)=0
virtual void WhenDomain(Demon *d)=0
This method attaches a demon that will watch any domain modification of the domain of the variable.
virtual int64 Value() const =0
This method returns the value of the variable.
virtual void RemoveInterval(int64 l, int64 u)=0
This method removes the interval 'l' .
int index() const
Returns the index of the variable.
virtual uint64 Size() const =0
This method returns the number of values in the domain of the variable.
virtual IntVar * IsGreaterOrEqual(int64 constant)=0
void WhenBound(Solver::Action action)
This method attaches an action that will be awakened when the variable is bound.
bool IsVar() const override
Returns true if the expression is indeed a variable.
virtual int VarType() const
virtual int64 OldMin() const =0
Returns the previous min.
The class Iterator has two direct subclasses.
virtual void Init()=0
This method must be called before each loop.
virtual void Next()=0
This method moves the iterator to the next value.
virtual int64 Value() const =0
This method returns the current value of the iterator.
std::string DebugString() const override
Pretty Print.
virtual bool Ok() const =0
This method indicates if we can call Value() or not.
void LoadFromProto(const IntervalVarAssignment &interval_var_assignment_proto)
bool operator!=(const IntervalVarElement &element) const
bool operator==(const IntervalVarElement &element) const
void Copy(const IntervalVarElement &element)
void WriteToProto(IntervalVarAssignment *interval_var_assignment_proto) const
Interval variables are often used in scheduling.
virtual int64 OldStartMin() const =0
virtual int64 StartMax() const =0
void WhenDurationRange(Solver::Closure closure)
void WhenAnything(Solver::Closure closure)
Attaches a closure awakened when anything about this interval changes.
virtual int64 OldEndMin() const =0
static const int64 kMaxValidValue
The largest acceptable value to be returned by EndMax()
void WhenStartBound(Solver::Closure closure)
virtual void WhenStartBound(Demon *const d)=0
void WhenEndRange(Solver::Closure closure)
virtual IntExpr * SafeDurationExpr(int64 unperformed_value)=0
void WhenAnything(Demon *const d)
Attaches a demon awakened when anything about this interval changes.
Definition: interval.cc:2227
virtual int64 DurationMax() const =0
virtual void SetPerformed(bool val)=0
virtual int64 EndMax() const =0
void WhenEndBound(Solver::Action action)
virtual void SetEndMax(int64 m)=0
virtual void WhenEndRange(Demon *const d)=0
virtual void SetStartMin(int64 m)=0
virtual void SetDurationMin(int64 m)=0
virtual void WhenDurationBound(Demon *const d)=0
virtual int64 OldDurationMin() const =0
virtual void SetEndMin(int64 m)=0
virtual bool WasPerformedBound() const =0
void WhenStartRange(Solver::Action action)
virtual void SetEndRange(int64 mi, int64 ma)=0
virtual void WhenDurationRange(Demon *const d)=0
static const int64 kMinValidValue
The smallest acceptable value to be returned by StartMin()
virtual void WhenEndBound(Demon *const d)=0
virtual void Accept(ModelVisitor *const visitor) const =0
Accepts the given visitor.
void WhenDurationBound(Solver::Action action)
virtual bool MustBePerformed() const =0
These methods query, set, and watch the performed status of the interval var.
IntervalVar(Solver *const solver, const std::string &name)
virtual void WhenPerformedBound(Demon *const d)=0
virtual IntExpr * EndExpr()=0
virtual void SetStartMax(int64 m)=0
virtual int64 OldEndMax() const =0
virtual int64 StartMin() const =0
These methods query, set, and watch the start position of the interval var.
void WhenStartBound(Solver::Action action)
virtual void SetStartRange(int64 mi, int64 ma)=0
void WhenAnything(Solver::Action action)
Attaches an action awakened when anything about this interval changes.
virtual IntExpr * PerformedExpr()=0
virtual int64 OldDurationMax() const =0
virtual IntExpr * DurationExpr()=0
void WhenEndRange(Solver::Action action)
void WhenStartRange(Solver::Closure closure)
virtual int64 EndMin() const =0
These methods query, set, and watch the end position of the interval var.
virtual void WhenStartRange(Demon *const d)=0
virtual IntExpr * StartExpr()=0
These methods create expressions encapsulating the start, end and duration of the interval var.
virtual IntExpr * SafeEndExpr(int64 unperformed_value)=0
virtual IntExpr * SafeStartExpr(int64 unperformed_value)=0
These methods create expressions encapsulating the start, end and duration of the interval var.
virtual int64 DurationMin() const =0
These methods query, set, and watch the duration of the interval var.
virtual void SetDurationRange(int64 mi, int64 ma)=0
virtual void SetDurationMax(int64 m)=0
void WhenPerformedBound(Solver::Action action)
void WhenPerformedBound(Solver::Closure closure)
virtual int64 OldStartMax() const =0
void WhenEndBound(Solver::Closure closure)
virtual bool MayBePerformed() const =0
void WhenDurationRange(Solver::Action action)
void WhenDurationBound(Solver::Closure closure)
Local Search Filters are used for fast neighbor pruning.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
The base class for all local search operators.
Implements a complete cache for model elements: expressions and constraints.
virtual void VisitIntervalVariable(const IntervalVar *const variable, const std::string &operation, int64 value, IntervalVar *const delegate)
static const char kSolutionLimitArgument[]
static const char kCountUsedBinsExtension[]
static const char kMirrorOperation[]
Operations.
static const char kAbs[]
Constraint and Expression types.
virtual void VisitSequenceVariable(const SequenceVar *const variable)
static const char kVariableUsageLessConstantExtension[]
virtual void VisitIntegerVariable(const IntVar *const variable, IntExpr *const delegate)
static const char kActiveArgument[]
argument names:
virtual void VisitIntervalArgument(const std::string &arg_name, IntervalVar *const argument)
Visit interval argument.
static const char kBranchesLimitArgument[]
static const char kIntervalUnaryRelation[]
virtual void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
virtual void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *const expr)
void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64 index_min, int64 index_max)
static const char kWeightedSumOfAssignedEqualVariableExtension[]
virtual void VisitIntegerVariableEvaluatorArgument(const std::string &arg_name, const Solver::Int64ToIntVar &arguments)
Helpers.
static const char kSmartTimeCheckArgument[]
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *const constraint)
virtual void BeginVisitExtension(const std::string &type)
static const char kStartSyncOnStartOperation[]
static const char kUsageLessConstantExtension[]
virtual void EndVisitExtension(const std::string &type)
virtual void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64 > &values)
static const char kUsageEqualVariableExtension[]
virtual void VisitIntegerArgument(const std::string &arg_name, int64 value)
Visit integer arguments.
virtual void EndVisitModel(const std::string &type_name)
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
static const char kVariableGroupExtension[]
static const char kFailuresLimitArgument[]
static const char kScalProdGreaterOrEqual[]
virtual void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments)
static const char kIntervalBinaryRelation[]
virtual void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &tuples)
virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *const argument)
Visit integer expression argument.
virtual void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments)
void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64 index_min, int64 index_max)
Using SWIG on callbacks is troublesome, so we hide these methods during the wrapping.
static const char kInt64ToInt64Extension[]
void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1 &eval, const std::string &arg_name, int64 index_max)
Expands function as array when index min is 0.
static const char kStartSyncOnEndOperation[]
virtual void VisitSequenceArgument(const std::string &arg_name, SequenceVar *const argument)
Visit sequence argument.
virtual void BeginVisitModel(const std::string &type_name)
--— Virtual methods for visitors --—
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *const constraint)
static const char kCountAssignedItemsExtension[]
Extension names:
Subclass of RevArray<T> which adds numerical operations.
void Decr(Solver *const s, int index)
void Add(Solver *const s, int index, const T &to_add)
void Incr(Solver *const s, int index)
Subclass of Rev<T> which adds numerical operations.
void Add(Solver *const s, const T &to_add)
This class encapsulates an objective.
void EnterSearch() override
Beginning of the search.
Definition: search.cc:2738
int64 best() const
Returns the best value found during search.
void BeginNextDecision(DecisionBuilder *const db) override
Before calling DecisionBuilder::Next.
Definition: search.cc:2747
IntVar * Var() const
Returns the variable that is optimized.
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
Definition: search.cc:2840
bool AcceptSolution() override
This method is called when a solution is found.
Definition: search.cc:2765
virtual std::string Print() const
Definition: search.cc:2824
bool AtSolution() override
This method is called when a valid solution is found.
Definition: search.cc:2777
void RefuteDecision(Decision *const d) override
Before refuting the decision.
Definition: search.cc:2763
OptimizeVar(Solver *const s, bool maximize, IntVar *const a, int64 step)
Definition: search.cc:2717
bool AcceptDelta(Assignment *delta, Assignment *deltadelta) override
Internal methods.
Definition: search.cc:2790
std::string DebugString() const override
Definition: search.cc:2828
void AddWeightedSumOfAssignedDimension(const std::vector< int64 > &weights, IntVar *const cost_var)
This dimension enforces that cost_var == sum of weights[i] for all objects 'i' assigned to a bin.
Definition: pack.cc:1578
bool IsAssignedStatusKnown(int var_index) const
Definition: pack.cc:423
void Post() override
This method is called when the constraint is processed by the solver.
Definition: pack.cc:126
void AddCountAssignedItemsDimension(IntVar *const count_var)
This dimension links 'count_var' to the actual number of items assigned to a bin in the pack.
Definition: pack.cc:1604
void InitialPropagate() override
This method performs the initial propagation of the constraint.
Definition: pack.cc:189
Pack(Solver *const s, const std::vector< IntVar * > &vars, int number_of_bins)
Definition: pack.cc:107
void SetImpossible(int var_index, int bin_index)
Definition: pack.cc:407
void SetAssigned(int var_index)
Definition: pack.cc:435
void AddWeightedSumEqualVarDimension(const std::vector< int64 > &weights, const std::vector< IntVar * > &loads)
This dimension imposes that for all bins b, the weighted sum (weights[i]) of all objects i assigned t...
Definition: pack.cc:1558
bool IsUndecided(int var_index, int bin_index) const
Definition: pack.cc:403
bool IsPossible(int var_index, int bin_index) const
Definition: pack.cc:427
void AssignFirstPossibleToBin(int bin_index)
Definition: pack.cc:475
void AddCountUsedBinDimension(IntVar *const count_var)
This dimension links 'count_var' to the actual number of bins used in the pack.
Definition: pack.cc:1597
void OneDomain(int var_index)
Definition: pack.cc:333
void SetUnassigned(int var_index)
Definition: pack.cc:443
void AddSumVariableWeightsLessOrEqualConstantDimension(const std::vector< IntVar * > &usage, const std::vector< int64 > &capacity)
This dimension imposes: forall b in bins, sum (i in items: usage[i] * is_assigned(i,...
Definition: pack.cc:1587
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
Definition: pack.cc:392
void AssignAllPossibleToBin(int bin_index)
Definition: pack.cc:465
void Assign(int var_index, int bin_index)
Definition: pack.cc:415
void UnassignAllRemainingItems()
Definition: pack.cc:492
std::string DebugString() const override
Definition: pack.cc:379
void AssignAllRemainingItems()
Definition: pack.cc:482
void AddWeightedSumLessOrEqualConstantDimension(const std::vector< int64 > &weights, const std::vector< int64 > &bounds)
Dimensions are additional constraints than can restrict what is possible with the pack constraint.
Definition: pack.cc:1528
IntVar * AssignVar(int var_index, int bin_index) const
Definition: pack.cc:431
void RemoveAllPossibleFromBin(int bin_index)
Definition: pack.cc:455
void EnqueueDelayedDemon(Demon *const d)
This method pushes the demon onto the propagation queue.
virtual std::string name() const
Object naming.
void reset_action_on_fail()
This method clears the failure callback.
bool HasName() const
Returns whether the object has been named or not.
void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)
void FreezeQueue()
This method freezes the propagation queue.
void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)
virtual std::string BaseName() const
Returns a base name for automatic naming.
void set_variable_to_clean_on_fail(IntVar *v)
Shortcut for variable cleaner.
void UnfreezeQueue()
This method unfreezes the propagation queue.
Usual limit based on wall_time, number of explored branches and number of failures in the search tree...
bool Check() override
This method is called to check the status of the limit.
Definition: search.cc:3988
absl::Duration duration_limit() const
bool IsUncheckedSolutionLimitReached() override
Returns true if the limit of solutions has been reached including unchecked solutions.
Definition: search.cc:4039
void Init() override
This method is called when the search limit is initialized.
Definition: search.cc:4009
void ExitSearch() override
End of the search.
Definition: search.cc:4020
RegularLimit(Solver *const s, absl::Duration time, int64 branches, int64 failures, int64 solutions, bool smart_time_check, bool cumulative)
Definition: search.cc:3949
int ProgressPercent() override
Returns a percentage representing the propress of the search before reaching limits.
Definition: search.cc:3996
void Accept(ModelVisitor *const visitor) const override
Accepts the given model visitor.
Definition: search.cc:4053
void Copy(const SearchLimit *const limit) override
Copy a limit.
Definition: search.cc:3969
void UpdateLimits(absl::Duration time, int64 branches, int64 failures, int64 solutions)
Definition: search.cc:4031
RegularLimit * MakeIdenticalClone() const
Definition: search.cc:3982
std::string DebugString() const override
Definition: search.cc:4045
SearchLimit * MakeClone() const override
Allocates a clone of the limit.
Definition: search.cc:3980
Reversible array of POD types.
const T & Value(int index) const
RevArray(int size, const T &val)
void SetValue(Solver *const s, int index, const T &val)
const T & operator[](int index) const
This class adds reversibility to a POD type.
void SetValue(Solver *const s, const T &val)
Reversible Immutable MultiMap class.
Base class of all search limits.
void EnterSearch() override
Internal methods.
Definition: search.cc:3919
void PeriodicCheck() override
Periodic call to check limits in long running methods.
Definition: search.cc:3934
virtual void Init()=0
This method is called when the search limit is initialized.
void BeginNextDecision(DecisionBuilder *const b) override
Before calling DecisionBuilder::Next.
Definition: search.cc:3924
virtual void Copy(const SearchLimit *const limit)=0
Copy a limit.
virtual SearchLimit * MakeClone() const =0
Allocates a clone of the limit.
void RefuteDecision(Decision *const d) override
Before refuting the decision.
Definition: search.cc:3929
bool crossed() const
Returns true if the limit has been crossed.
std::string DebugString() const override
virtual bool Check()=0
This method is called to check the status of the limit.
A search monitor is a simple set of callbacks to monitor all search events.
virtual void RefuteDecision(Decision *const d)
Before refuting the decision.
virtual void ApplyDecision(Decision *const d)
Before applying the decision.
virtual void RestartSearch()
Restart the search.
virtual void ExitSearch()
End of the search.
virtual bool IsUncheckedSolutionLimitReached()
Returns true if the limit of solutions has been reached including unchecked solutions.
virtual bool LocalOptimum()
When a local optimum is reached.
virtual int ProgressPercent()
Returns a percentage representing the propress of the search before reaching limits.
virtual void NoMoreSolutions()
When the search tree is finished.
virtual void BeginFail()
Just when the failure occurs.
virtual void AfterDecision(Decision *const d, bool apply)
Just after refuting or applying the decision, apply is true after Apply.
virtual void BeginInitialPropagation()
Before the initial propagation.
virtual void BeginNextDecision(DecisionBuilder *const b)
Before calling DecisionBuilder::Next.
virtual void PeriodicCheck()
Periodic call to check limits in long running methods.
virtual void EnterSearch()
Beginning of the search.
virtual void EndNextDecision(DecisionBuilder *const b, Decision *const d)
After calling DecisionBuilder::Next, along with the returned decision.
virtual void EndFail()
After completing the backtrack.
virtual void EndInitialPropagation()
After the initial propagation.
virtual void AcceptUncheckedNeighbor()
After accepting an unchecked neighbor during local search.
virtual bool AcceptDelta(Assignment *delta, Assignment *deltadelta)
virtual bool AtSolution()
This method is called when a valid solution is found.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
virtual void AcceptNeighbor()
After accepting a neighbor during local search.
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
virtual bool AcceptSolution()
This method is called when a solution is found.
The SequenceVarElement stores a partial representation of ranked interval variables in the underlying...
void SetSequence(const std::vector< int > &forward_sequence, const std::vector< int > &backward_sequence, const std::vector< int > &unperformed)
bool operator==(const SequenceVarElement &element) const
const std::vector< int > & BackwardSequence() const
bool operator!=(const SequenceVarElement &element) const
void SetBackwardSequence(const std::vector< int > &backward_sequence)
const std::vector< int > & Unperformed() const
void SetUnperformed(const std::vector< int > &unperformed)
const std::vector< int > & ForwardSequence() const
void Copy(const SequenceVarElement &element)
void LoadFromProto(const SequenceVarAssignment &sequence_var_assignment_proto)
void WriteToProto(SequenceVarAssignment *sequence_var_assignment_proto) const
void SetForwardSequence(const std::vector< int > &forward_sequence)
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
void ComputePossibleFirstsAndLasts(std::vector< int > *const possible_firsts, std::vector< int > *const possible_lasts)
Computes the set of indices of interval variables that can be ranked first in the set of unranked act...
void FillSequence(std::vector< int > *const rank_first, std::vector< int > *const rank_last, std::vector< int > *const unperformed) const
Clears 'rank_first' and 'rank_last', and fills them with the intervals in the order of the ranks.
void RankSequence(const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)
Applies the following sequence of ranks, ranks first, then rank last.
void ComputeStatistics(int *const ranked, int *const not_ranked, int *const unperformed) const
Compute statistics on the sequence.
void ActiveHorizonRange(int64 *const hmin, int64 *const hmax) const
Returns the minimum start min and the maximum end max of all unranked interval vars in the sequence.
void HorizonRange(int64 *const hmin, int64 *const hmax) const
Returns the minimum start min and the maximum end max of all interval vars in the sequence.
Definition: sched_search.cc:91
int64 size() const
Returns the number of interval vars in the sequence.
IntVar * Next(int index) const
Returns the next of the index_th interval of the sequence.
Definition: sched_search.cc:54
IntervalVar * Interval(int index) const
Returns the index_th interval of the sequence.
Definition: sched_search.cc:50
void RankLast(int index)
Ranks the index_th interval var first of all unranked interval vars.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
Definition: sched_search.cc:71
void DurationRange(int64 *const dmin, int64 *const dmax) const
Returns the minimum and maximum duration of combined interval vars in the sequence.
Definition: sched_search.cc:75
void RankFirst(int index)
Ranks the index_th interval var first of all unranked interval vars.
void RankNotLast(int index)
Indicates that the index_th interval var will not be ranked first of all currently unranked interval ...
void RankNotFirst(int index)
Indicates that the index_th interval var will not be ranked first of all currently unranked interval ...
SequenceVar(Solver *const s, const std::vector< IntervalVar * > &intervals, const std::vector< IntVar * > &nexts, const std::string &name)
Definition: sched_search.cc:37
std::string DebugString() const override
Definition: sched_search.cc:56
This class represent a reversible FIFO structure.
This class is the root class of all solution collectors.
void EnterSearch() override
Beginning of the search.
Definition: search.cc:2263
int64 Value(int n, IntVar *const var) const
This is a shortcut to get the Value of 'var' in the nth solution.
Definition: search.cc:2347
int64 failures(int n) const
Returns the number of failures encountered at the time of the nth solution.
Definition: search.cc:2337
void Push(const SolutionData &data)
void PushSolution()
Push the current state as a new solution.
Definition: search.cc:2272
void AddObjective(IntVar *const objective)
Definition: search.cc:2257
std::vector< Assignment * > recycle_solutions_
std::vector< SolutionData > solution_data_
void Add(IntVar *const var)
Add API.
Definition: search.cc:2221
int solution_count() const
Returns how many solutions were stored during the search.
Definition: search.cc:2325
int64 DurationValue(int n, IntervalVar *const var) const
This is a shortcut to get the DurationValue of 'var' in the nth solution.
Definition: search.cc:2355
int64 PerformedValue(int n, IntervalVar *const var) const
This is a shortcut to get the PerformedValue of 'var' in the nth solution.
Definition: search.cc:2363
const std::vector< int > & Unperformed(int n, SequenceVar *const var) const
This is a shortcut to get the list of unperformed of 'var' in the nth solution.
Definition: search.cc:2377
SolutionData BuildSolutionDataForCurrentState()
Definition: search.cc:2284
Assignment * solution(int n) const
Returns the nth solution.
Definition: search.cc:2320
int64 wall_time(int n) const
Returns the wall time in ms for the nth solution.
Definition: search.cc:2327
int64 EndValue(int n, IntervalVar *const var) const
This is a shortcut to get the EndValue of 'var' in the nth solution.
Definition: search.cc:2359
const std::vector< int > & ForwardSequence(int n, SequenceVar *const var) const
This is a shortcut to get the ForwardSequence of 'var' in the nth solution.
Definition: search.cc:2367
int64 objective_value(int n) const
Returns the objective value of the nth solution.
Definition: search.cc:2342
void FreeSolution(Assignment *solution)
Definition: search.cc:2309
std::unique_ptr< Assignment > prototype_
SolutionCollector(Solver *const solver, const Assignment *assignment)
Definition: search.cc:2205
int64 branches(int n) const
Returns the number of branches when the nth solution was found.
Definition: search.cc:2332
void PopSolution()
Remove and delete the last popped solution.
Definition: search.cc:2276
std::string DebugString() const override
const std::vector< int > & BackwardSequence(int n, SequenceVar *const var) const
This is a shortcut to get the BackwardSequence of 'var' in the nth solution.
Definition: search.cc:2372
int64 StartValue(int n, IntervalVar *const var) const
This is a shortcut to get the StartValue of 'var' in the nth solution.
Definition: search.cc:2351
This class is used to manage a pool of solutions.
virtual bool SyncNeeded(Assignment *const local_assignment)=0
This method checks if the local solution needs to be updated with an external one.
virtual void RegisterNewSolution(Assignment *const assignment)=0
This method is called when a new solution has been accepted by the local search.
virtual void GetNextSolution(Assignment *const assignment)=0
This method is called when the local search starts a new neighborhood to initialize the default assig...
virtual void Initialize(Assignment *const assignment)=0
This method is called to initialize the solution pool with the assignment from the local search.
SolverState state() const
State of the solver.
Decision * MakeDecision(Action apply, Action refute)
Definition: search.cc:610
std::function< bool(int64)> IndexFilter1
IntExpr * MakeElement(const std::vector< int64 > &values, IntVar *const index)
values[index]
Definition: element.cc:647
SearchMonitor * MakeLubyRestart(int scale_factor)
This search monitor will restart the search periodically.
Definition: search.cc:4643
Constraint * MakeMemberCt(IntExpr *const expr, const std::vector< int64 > &values)
expr in set.
Definition: expr_cst.cc:1160
void SaveValue(T *o)
reversibility
SolutionCollector * MakeAllSolutionCollector()
Collect all solutions of the search.
Definition: search.cc:2711
DecisionModification
The Solver is responsible for creating the search tree.
@ NO_CHANGE
Keeps the default behavior, i.e.
@ SWITCH_BRANCHES
Applies right branch first.
@ KEEP_RIGHT
Left branches are ignored.
@ KEEP_LEFT
Right branches are ignored.
@ KILL_BOTH
Backtracks to the previous decisions, i.e.
bool IsBooleanVar(IntExpr *const expr, IntVar **inner_var, bool *is_negated) const
Returns true if expr represents either boolean_var or 1 - boolean_var.
RegularLimit * MakeLimit(absl::Duration time, int64 branches, int64 failures, int64 solutions, bool smart_time_check=false, bool cumulative=false)
Limits the search with the 'time', 'branches', 'failures' and 'solutions' limits.
Definition: search.cc:4117
void MakeBoolVarArray(int var_count, const std::string &name, std::vector< IntVar * > *vars)
This method will append the vector vars with 'var_count' boolean variables having name "name<i>" wher...
LocalSearchFilter * MakeVariableDomainFilter()
Decision * MakeSplitVariableDomain(IntVar *const var, int64 val, bool start_with_lower_half)
Definition: search.cc:1679
bool HasName(const PropagationBaseObject *object) const
Returns whether the object has been named or not.
Constraint * MakeDeviation(const std::vector< IntVar * > &vars, IntVar *const deviation_var, int64 total_sum)
Deviation constraint: sum_i |n * vars[i] - total_sum| <= deviation_var and sum_i vars[i] == total_sum...
Definition: deviation.cc:411
std::vector< int64 > tmp_vector_
Unsafe temporary vector.
void ClearLocalSearchState()
Clears the local search state.
OptimizeVar * MakeWeightedMaximize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a maximization weigthed objective.
Definition: search.cc:2910
DemonProfiler * demon_profiler() const
Access to demon profiler.
SolutionCollector * MakeLastSolutionCollector()
Collect the last solution of the search.
Definition: search.cc:2481
RegularLimit * MakeSolutionsLimit(int64 solutions)
Creates a search limit that constrains the number of solutions found during the search.
Definition: search.cc:4105
Decision * MakeAssignVariableValue(IntVar *const var, int64 val)
Decisions.
Definition: search.cc:1558
SearchMonitor * MakeAtSolutionCallback(std::function< void()> callback)
Definition: search.cc:418
IntExpr * RegisterIntExpr(IntExpr *const expr)
Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
Definition: trace.cc:844
IntVar * MakeIsGreaterOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var >= value)
Definition: expr_cst.cc:677
SearchLimit * MakeCustomLimit(std::function< bool()> limiter)
Callback-based search limit.
Definition: search.cc:4370
Constraint * MakeNullIntersectExcept(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars, int64 escape_value)
Creates a constraint that states that all variables in the first vector are different from all variab...
Definition: alldiff_cst.cc:738
bool SolveAndCommit(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolveAndCommit using a decision builder and up to three search monitors, usually one for the objectiv...
Constraint * MakeLess(IntExpr *const left, IntExpr *const right)
left < right
Definition: range_cst.cc:546
Constraint * MakeIntervalVarRelation(IntervalVar *const t, UnaryIntervalRelation r, int64 d)
This method creates a relation between an interval var and a date.
Definition: timetabling.cc:113
friend void InternalSaveBooleanVarValue(Solver *const, IntVar *const)
LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)
Creates a local search operator that tries to move the assignment of some variables toward a target.
Constraint * MakeSubCircuit(const std::vector< IntVar * > &nexts)
Force the "nexts" variable to create a complete Hamiltonian path for those that do not loop upon them...
IntExpr * MakeAbs(IntExpr *const expr)
|expr|
Constraint * MakeFalseConstraint()
This constraint always fails.
Definition: constraints.cc:520
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
Definition: range_cst.cc:512
Constraint * MakeIsDifferentCt(IntExpr *const v1, IntExpr *const v2, IntVar *const b)
b == (v1 != v2)
Definition: range_cst.cc:686
Constraint * MakeLessOrEqual(IntExpr *const left, IntExpr *const right)
left <= right
Definition: range_cst.cc:526
IntExpr * MakePiecewiseLinearExpr(IntExpr *expr, const PiecewiseLinearFunction &f)
General piecewise-linear function expression, built from f(x) where f is piecewise-linear.
int64 solutions() const
The number of solutions found since the start of the search.
ConstraintSolverStatistics GetConstraintSolverStatistics() const
Returns detailed cp search statistics.
Constraint * MakeNullIntersect(const std::vector< IntVar * > &first_vars, const std::vector< IntVar * > &second_vars)
Creates a constraint that states that all variables in the first vector are different from all variab...
Definition: alldiff_cst.cc:733
DisjunctiveConstraint * MakeStrictDisjunctiveConstraint(const std::vector< IntervalVar * > &intervals, const std::string &name)
This constraint forces all interval vars into an non-overlapping sequence.
Definition: resource.cc:2579
IntVar * MakeIsGreaterVar(IntExpr *const left, IntExpr *const right)
status var of (left > right)
Definition: range_cst.cc:796
LocalSearchStatistics GetLocalSearchStatistics() const
Returns detailed local search statistics.
IntExpr * MakeMin(const std::vector< IntVar * > &vars)
std::min(vars)
Definition: expr_array.cc:3278
Constraint * MakeIsLessCstCt(IntExpr *const v, int64 c, IntVar *const b)
b == (v < c)
Definition: expr_cst.cc:813
static constexpr int kNumPriorities
Number of priorities for demons.
Decision * MakeAssignVariableValueOrFail(IntVar *const var, int64 value)
Definition: search.cc:1596
DemonPriority
This enum represents the three possible priorities for a demon in the Solver queue.
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
@ DELAYED_PRIORITY
DELAYED_PRIORITY is the lowest priority: Demons will be processed after VAR_PRIORITY and NORMAL_PRIOR...
@ NORMAL_PRIORITY
NORMAL_PRIORITY is the highest priority: Demons will be processed first.
OptimizeVar * MakeMaximize(IntVar *const v, int64 step)
Creates a maximization objective.
Definition: search.cc:2853
ConstraintSolverParameters parameters() const
Stored Parameters.
int64 failures() const
The number of failures encountered since the creation of the solver.
Constraint * MakeIndexOfFirstMinValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
Creates a constraint that binds the index variable to the index of the first variable with the minimu...
Definition: constraints.cc:560
SearchMonitor * MakeSymmetryManager(const std::vector< SymmetryBreaker * > &visitors)
Symmetry Breaking.
Definition: search.cc:4815
SolverState
This enum represents the state of the solver w.r.t. the search.
@ AT_SOLUTION
After successful NextSolution and before EndSearch.
@ PROBLEM_INFEASIBLE
After search, the model is infeasible.
@ OUTSIDE_SEARCH
Before search, after search.
@ IN_ROOT_NODE
Executing the root node.
@ NO_MORE_SOLUTIONS
After failed NextSolution and before EndSearch.
@ IN_SEARCH
Executing the search code.
int64 demon_runs(DemonPriority p) const
The number of demons executed during search for a given priority.
Constraint * MakeAbsEquality(IntVar *const var, IntVar *const abs_var)
Creates the constraint abs(var) == abs_var.
std::function< bool(int64, int64, int64)> VariableValueComparator
std::string SearchContext() const
bool CheckAssignment(Assignment *const solution)
Checks whether the given assignment satisfies all relevant constraints.
IntVar * RegisterIntVar(IntVar *const var)
Registers a new IntVar and wraps it inside a TraceIntVar if necessary.
Definition: trace.cc:856
SearchMonitor * MakeGenericTabuSearch(bool maximize, IntVar *const v, int64 step, const std::vector< IntVar * > &tabu_vars, int64 forbid_tenure)
Creates a Tabu Search based on the vars |vars|.
Definition: search.cc:3249
SearchMonitor * MakeSimulatedAnnealing(bool maximize, IntVar *const v, int64 step, int64 initial_temperature)
Creates a Simulated Annealing monitor.
Definition: search.cc:3352
absl::Time Now() const
The 'absolute time' as seen by the solver.
IntVar * MakeIsDifferentVar(IntExpr *const v1, IntExpr *const v2)
status var of (v1 != v2)
Definition: range_cst.cc:641
IntVar * MakeIsEqualVar(IntExpr *const v1, IntExpr *v2)
status var of (v1 == v2)
Definition: range_cst.cc:577
Constraint * MakeNotBetweenCt(IntExpr *const expr, int64 l, int64 u)
(expr < l || expr > u) This constraint is lazy as it will not make holes in the domain of variables.
Definition: expr_cst.cc:953
DecisionBuilder * MakeConstraintAdder(Constraint *const ct)
Returns a decision builder that will add the given constraint to the model.
Constraint * MakeCircuit(const std::vector< IntVar * > &nexts)
Force the "nexts" variable to create a complete Hamiltonian path.
OptimizationDirection
Optimization directions.
IntervalStrategy
This enum describes the straregy used to select the next interval variable and its value to be fixed.
@ INTERVAL_SET_TIMES_FORWARD
Selects the variable with the lowest starting time of all variables, and fixes its starting time to t...
@ INTERVAL_SIMPLE
The simple is INTERVAL_SET_TIMES_FORWARD.
@ INTERVAL_SET_TIMES_BACKWARD
Selects the variable with the highest ending time of all variables, and fixes the ending time to this...
@ INTERVAL_DEFAULT
The default is INTERVAL_SET_TIMES_FORWARD.
Constraint * MakeGreater(IntExpr *const left, IntExpr *const right)
left > right
Definition: range_cst.cc:560
Pack * MakePack(const std::vector< IntVar * > &vars, int number_of_bins)
This constraint packs all variables onto 'number_of_bins' variables.
Definition: pack.cc:1611
Assignment * GetOrCreateLocalSearchState()
Returns (or creates) an assignment representing the state of local search.
Constraint * MakeTransitionConstraint(const std::vector< IntVar * > &vars, const IntTupleSet &transition_table, int64 initial_state, const std::vector< int64 > &final_states)
This constraint create a finite automaton that will check the sequence of variables vars.
bool IsProfilingEnabled() const
Returns whether we are profiling the solver.
Demon * MakeActionDemon(Action action)
Creates a demon from a callback.
Definition: constraints.cc:507
DecisionBuilder * Try(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which will create a search tree where each decision builder is called from...
Definition: search.cc:700
uint64 fail_stamp() const
The fail_stamp() is incremented after each backtrack.
Constraint * MakeLexicalLess(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that left is lexicographically less than right.
Definition: constraints.cc:540
void AddPropagationMonitor(PropagationMonitor *const monitor)
Adds the propagation monitor to the solver.
Constraint * MakeBetweenCt(IntExpr *const expr, int64 l, int64 u)
(l <= expr <= u)
Definition: expr_cst.cc:920
Constraint * MakeIsEqualCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var == value)
Definition: expr_cst.cc:485
RegularLimit * MakeFailuresLimit(int64 failures)
Creates a search limit that constrains the number of failures that can happen when exploring the sear...
Definition: search.cc:4100
SearchMonitor * MakeSearchLog(int branch_period)
The SearchMonitors below will display a periodic search log on LOG(INFO) every branch_period branches...
Definition: search.cc:284
IntValueStrategy
This enum describes the strategy used to select the next variable value to set.
@ INT_VALUE_SIMPLE
The simple selection is ASSIGN_MIN_VALUE.
@ ASSIGN_CENTER_VALUE
Selects the first possible value which is the closest to the center of the domain of the selected var...
@ SPLIT_UPPER_HALF
Split the domain in two around the center, and choose the lower part first.
@ ASSIGN_MIN_VALUE
Selects the min value of the selected variable.
@ ASSIGN_RANDOM_VALUE
Selects randomly one of the possible values of the selected variable.
@ INT_VALUE_DEFAULT
The default behavior is ASSIGN_MIN_VALUE.
@ ASSIGN_MAX_VALUE
Selects the max value of the selected variable.
@ SPLIT_LOWER_HALF
Split the domain in two around the center, and choose the lower part first.
IntExpr * MakePower(IntExpr *const expr, int64 n)
expr ^ n (n > 0)
UnaryIntervalRelation
This enum is used in Solver::MakeIntervalVarRelation to specify the temporal relation between an inte...
@ ENDS_BEFORE
t ends before d, i.e. End(t) <= d.
@ AVOID_DATE
STARTS_AFTER or ENDS_BEFORE, i.e.
@ ENDS_AFTER
t ends after d, i.e. End(t) >= d.
@ STARTS_BEFORE
t starts before d, i.e. Start(t) <= d.
@ STARTS_AT
t starts at d, i.e. Start(t) == d.
@ ENDS_AT
t ends at d, i.e. End(t) == d.
@ STARTS_AFTER
t starts after d, i.e. Start(t) >= d.
@ CROSS_DATE
STARTS_BEFORE and ENDS_AFTER at the same time, i.e.
Constraint * MakeDelayedPathCumul(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, const std::vector< IntVar * > &cumuls, const std::vector< IntVar * > &transits)
Delayed version of the same constraint: propagation on the nexts variables is delayed until all const...
bool CheckConstraint(Constraint *const ct)
Checks whether adding this constraint will lead to an immediate failure.
IntVar * MakeIsDifferentCstVar(IntExpr *const var, int64 value)
status var of (var != value)
Definition: expr_cst.cc:578
Constraint * MakeCover(const std::vector< IntervalVar * > &vars, IntervalVar *const target_var)
This constraint states that the target_var is the convex hull of the intervals.
void SetSearchContext(Search *search, const std::string &search_context)
Constraint * MakeIsGreaterCstCt(IntExpr *const v, int64 c, IntVar *const b)
b == (v > c)
Definition: expr_cst.cc:714
Decision * MakeAssignVariablesValues(const std::vector< IntVar * > &vars, const std::vector< int64 > &values)
Definition: search.cc:1752
Constraint * MakeCumulative(const std::vector< IntervalVar * > &intervals, const std::vector< int64 > &demands, int64 capacity, const std::string &name)
This constraint forces that, for any integer t, the sum of the demands corresponding to an interval c...
Definition: resource.cc:2586
Constraint * MakeNonOverlappingBoxesConstraint(const std::vector< IntVar * > &x_vars, const std::vector< IntVar * > &y_vars, const std::vector< IntVar * > &x_size, const std::vector< IntVar * > &y_size)
This constraint states that all the boxes must not overlap.
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
DecisionBuilder * MakeApplyBranchSelector(BranchSelector bs)
Creates a decision builder that will set the branch selector.
Constraint * MakeAllDifferentExcept(const std::vector< IntVar * > &vars, int64 escape_value)
All variables are pairwise different, unless they are assigned to the escape value.
Definition: alldiff_cst.cc:720
int64 Rand64(int64 size)
Returns a random value between 0 and 'size' - 1;.
void SetUseFastLocalSearch(bool use_fast_local_search)
enabled for metaheuristics.
Decision * MakeAssignVariableValueOrDoNothing(IntVar *const var, int64 value)
Definition: search.cc:1625
IntervalVar * MakeIntervalRelaxedMin(IntervalVar *const interval_var)
Creates and returns an interval variable that wraps around the given one, relaxing the min start and ...
Definition: interval.cc:2218
RegularLimit * MakeTimeLimit(int64 time_in_ms)
IntervalVar * MakeFixedDurationEndSyncedOnEndIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose end is synchronized with the end of another inter...
Definition: interval.cc:2417
Constraint * MakePathConnected(std::vector< IntVar * > nexts, std::vector< int64 > sources, std::vector< int64 > sinks, std::vector< IntVar * > status)
Constraint enforcing that status[i] is true iff there's a path defined on next variables from sources...
Demon * MakeClosureDemon(Closure closure)
!defined(SWIG)
Definition: constraints.cc:511
void AddConstraint(Constraint *const c)
Adds the constraint 'c' to the model.
DecisionBuilder * MakeSolveOnce(DecisionBuilder *const db)
SolveOnce will collapse a search tree described by a decision builder 'db' and a set of monitors and ...
Definition: search.cc:4413
LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Creates a local search operator which concatenates a vector of operators.
IntervalVar * MakeFixedInterval(int64 start, int64 duration, const std::string &name)
Creates a fixed and performed interval.
Definition: interval.cc:2234
LocalSearchFilter * MakeRejectFilter()
LocalSearchFilter * MakeAcceptFilter()
Local Search Filters.
LocalSearchOperator * MakeRandomLnsOperator(const std::vector< IntVar * > &vars, int number_of_variables)
Creates a large neighborhood search operator which creates fragments (set of relaxed variables) with ...
Constraint * MakeIsLessCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left < right)
Definition: range_cst.cc:773
Decision * MakeVariableLessOrEqualValue(IntVar *const var, int64 value)
Definition: search.cc:1684
DisjunctiveConstraint * MakeDisjunctiveConstraint(const std::vector< IntervalVar * > &intervals, const std::string &name)
This constraint forces all interval vars into an non-overlapping sequence.
Definition: resource.cc:2574
void ShouldFail()
These methods are only useful for the SWIG wrappers, which need a way to externally cause the Solver ...
int SearchDepth() const
Gets the search depth of the current active search.
void SaveAndSetValue(T *adr, T val)
All-in-one SaveAndSetValue.
IntVar * MakeIsMemberVar(IntExpr *const expr, const std::vector< int64 > &values)
Definition: expr_cst.cc:1490
void AddLocalSearchMonitor(LocalSearchMonitor *monitor)
Adds the local search monitor to the solver.
LocalSearchOperator * RandomConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)
Randomized version of local search concatenator; calls a random operator at each call to MakeNextNeig...
IntVar * MakeIsEqualCstVar(IntExpr *const var, int64 value)
status var of (var == value)
Definition: expr_cst.cc:460
Constraint * MakeScalProdLessOrEqual(const std::vector< IntVar * > &vars, const std::vector< int64 > &coefficients, int64 cst)
Definition: expr_array.cc:3526
Constraint * MakeNotMemberCt(IntExpr *const expr, const std::vector< int64 > &values)
expr not in set.
Definition: expr_cst.cc:1229
BinaryIntervalRelation
This enum is used in Solver::MakeIntervalVarRelation to specify the temporal relation between the two...
@ ENDS_AFTER_END
t1 ends after t2 end, i.e. End(t1) >= End(t2) + delay.
@ ENDS_AFTER_START
t1 ends after t2 start, i.e. End(t1) >= Start(t2) + delay.
@ STAYS_IN_SYNC
STARTS_AT_START and ENDS_AT_END at the same time.
@ ENDS_AT_END
t1 ends at t2 end, i.e. End(t1) == End(t2) + delay.
@ STARTS_AT_END
t1 starts at t2 end, i.e. Start(t1) == End(t2) + delay.
@ ENDS_AT_START
t1 ends at t2 start, i.e. End(t1) == Start(t2) + delay.
@ STARTS_AFTER_END
t1 starts after t2 end, i.e. Start(t1) >= End(t2) + delay.
@ STARTS_AFTER_START
t1 starts after t2 start, i.e. Start(t1) >= Start(t2) + delay.
@ STARTS_AT_START
t1 starts at t2 start, i.e. Start(t1) == Start(t2) + delay.
Constraint * MakeMaxEquality(const std::vector< IntVar * > &vars, IntVar *const max_var)
Definition: expr_array.cc:3386
LocalSearchOperators
This enum is used in Solver::MakeOperator to specify the neighborhood to create.
@ EXCHANGE
Operator which exchanges the positions of two nodes.
@ MAKEINACTIVE
Operator which makes path nodes inactive.
@ RELOCATE
Relocate neighborhood with length of 1 (see OROPT comment).
@ SWAPACTIVE
Operator which replaces an active node by an inactive one.
@ SIMPLELNS
Operator which defines one neighbor per variable.
@ INCREMENT
Operator which defines one neighbor per variable.
@ MAKECHAININACTIVE
Operator which makes a "chain" of path nodes inactive.
@ TWOOPT
Operator which reverses a sub-chain of a path.
@ FULLPATHLNS
Operator which relaxes one entire path and all inactive nodes, thus defining num_paths neighbors.
@ EXTENDEDSWAPACTIVE
Operator which makes an inactive node active and an active one inactive.
@ OROPT
Relocate: OROPT and RELOCATE.
@ PATHLNS
Operator which relaxes two sub-chains of three consecutive arcs each.
@ UNACTIVELNS
Operator which relaxes all inactive nodes and one sub-chain of six consecutive arcs.
@ MAKEACTIVE
Operator which inserts an inactive node into a path.
@ DECREMENT
Operator which defines a neighborhood to decrement values.
@ CROSS
Operator which cross exchanges the starting chains of 2 paths, including exchanging the whole paths.
Constraint * MakeIsEqualCt(IntExpr *const v1, IntExpr *v2, IntVar *const b)
b == (v1 == v2)
Definition: range_cst.cc:622
LocalSearchPhaseParameters * MakeLocalSearchPhaseParameters(IntVar *objective, LocalSearchOperator *const ls_operator, DecisionBuilder *const sub_decision_builder)
Local Search Phase Parameters.
IntExpr * MakeOpposite(IntExpr *const expr)
-expr
void PushState()
The PushState and PopState methods manipulates the states of the reversible objects.
bool IsLocalSearchProfilingEnabled() const
Returns whether we are profiling local search.
OptimizeVar * MakeWeightedOptimize(bool maximize, const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a weighted objective with a given sense (true = maximization).
Definition: search.cc:2896
IntVarLocalSearchFilter * MakeSumObjectiveFilter(const std::vector< IntVar * > &vars, IndexEvaluator2 values, Solver::LocalSearchFilterBound filter_enum)
LocalSearchOperator * MakeNeighborhoodLimit(LocalSearchOperator *const op, int64 limit)
Creates a local search operator that wraps another local search operator and limits the number of nei...
Constraint * MakeIfThenElseCt(IntVar *const condition, IntExpr *const then_expr, IntExpr *const else_expr, IntVar *const target_var)
Special cases with arrays of size two.
Definition: element.cc:1597
Decision * MakeScheduleOrExpedite(IntervalVar *const var, int64 est, int64 *const marker)
Returns a decision that tries to schedule a task at a given time.
Demon * MakeConstraintInitialPropagateCallback(Constraint *const ct)
This method is a specialized case of the MakeConstraintDemon method to call the InitiatePropagate of ...
Definition: constraints.cc:33
std::string DebugString() const
!defined(SWIG)
Constraint * MakeTrueConstraint()
This constraint always succeeds.
Definition: constraints.cc:515
IntervalVar * MakeFixedDurationEndSyncedOnStartIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose end is synchronized with the start of another int...
Definition: interval.cc:2410
Demon * RegisterDemon(Demon *const demon)
Adds a new demon and wraps it inside a DemonProfiler if necessary.
IntExpr * MakeModulo(IntExpr *const x, int64 mod)
Modulo expression x % mod (with the python convention for modulo).
Search * ActiveSearch() const
Returns the active search, nullptr outside search.
IntExpr * MakeConditionalExpression(IntVar *const condition, IntExpr *const expr, int64 unperformed_value)
Conditional Expr condition ? expr : unperformed_value.
Constraint * MakeIsBetweenCt(IntExpr *const expr, int64 l, int64 u, IntVar *const b)
b == (l <= expr <= u)
Definition: expr_cst.cc:1048
IntervalVar * MakeIntervalRelaxedMax(IntervalVar *const interval_var)
Creates and returns an interval variable that wraps around the given one, relaxing the max start and ...
Definition: interval.cc:2209
int64 wall_time() const
DEPRECATED: Use Now() instead.
Constraint * MakeDistribute(const std::vector< IntVar * > &vars, const std::vector< int64 > &values, const std::vector< IntVar * > &cards)
Aggregated version of count: |{i | v[i] == values[j]}| == cards[j].
Definition: count_cst.cc:964
RegularLimit * MakeBranchesLimit(int64 branches)
Creates a search limit that constrains the number of branches explored in the search tree.
Definition: search.cc:4095
ImprovementSearchLimit * MakeImprovementLimit(IntVar *objective_var, bool maximize, double objective_scaling_factor, double objective_offset, double improvement_rate_coefficient, int improvement_rate_solutions_distance)
Limits the search based on the improvements of 'objective_var'.
Definition: search.cc:4259
Constraint * MakeAtMost(std::vector< IntVar * > vars, int64 value, int64 max_count)
|{i | vars[i] == value}| <= max_count
Definition: count_cst.cc:955
ModelVisitor * MakeVariableDegreeVisitor(absl::flat_hash_map< const IntVar *, int > *const map)
Compute the number of constraints a variable is attached to.
Definition: utilities.cc:815
int64 accepted_neighbors() const
The number of accepted neighbors.
SearchMonitor * MakeConstantRestart(int frequency)
This search monitor will restart the search periodically after 'frequency' failures.
Definition: search.cc:4676
std::function< int64(int64, int64, int64)> IndexEvaluator3
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
int constraints() const
Counts the number of constraints that have been added to the solver before the search.
Constraint * MakeSumEquality(const std::vector< IntVar * > &vars, int64 cst)
Definition: expr_array.cc:3428
Constraint * MakeLexicalLessOrEqual(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that left is lexicographically less than or equal to right.
Definition: constraints.cc:545
void MakeFixedDurationIntervalVarArray(int count, int64 start_min, int64 start_max, int64 duration, bool optional, const std::string &name, std::vector< IntervalVar * > *const array)
This method fills the vector with 'count' interval variables built with the corresponding parameters.
Definition: interval.cc:2253
EvaluatorStrategy
This enum is used by Solver::MakePhase to specify how to select variables and values during the searc...
@ CHOOSE_STATIC_GLOBAL_BEST
Pairs are compared at the first call of the selector, and results are cached.
@ CHOOSE_DYNAMIC_GLOBAL_BEST
Pairs are compared each time a variable is selected.
void set_optimization_direction(OptimizationDirection direction)
int SolveDepth() const
Gets the number of nested searches.
int64 neighbors() const
The number of neighbors created.
PropagationMonitor * GetPropagationMonitor() const
Returns the propagation monitor.
Decision * MakeRankFirstInterval(SequenceVar *const sequence, int index)
Returns a decision that tries to rank first the ith interval var in the sequence variable.
IntExpr * MakeMax(const std::vector< IntVar * > &vars)
std::max(vars)
Definition: expr_array.cc:3321
Constraint * MakeIsLessOrEqualCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left <= right)
Definition: range_cst.cc:730
bool Solve(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolutionPool * MakeDefaultSolutionPool()
Solution Pool.
Constraint * MakeIntervalVarRelationWithDelay(IntervalVar *const t1, BinaryIntervalRelation r, IntervalVar *const t2, int64 delay)
This method creates a relation between two interval vars.
Definition: timetabling.cc:238
Constraint * MakeScalProdGreaterOrEqual(const std::vector< IntVar * > &vars, const std::vector< int64 > &coeffs, int64 cst)
Definition: expr_array.cc:3512
IntExpr * MakeDifference(IntExpr *const left, IntExpr *const right)
left - right
std::string model_name() const
Returns the name of the model.
void MakeIntVarArray(int var_count, int64 vmin, int64 vmax, const std::string &name, std::vector< IntVar * > *vars)
This method will append the vector vars with 'var_count' variables having bounds vmin and vmax and ha...
RegularLimitParameters MakeDefaultRegularLimitParameters() const
Creates a regular limit proto containing default values.
Definition: search.cc:4131
RegularLimit * MakeTimeLimit(absl::Duration time)
Creates a search limit that constrains the running time.
Definition: search.cc:4090
Decision * MakeVariableGreaterOrEqualValue(IntVar *const var, int64 value)
Definition: search.cc:1688
IntVar * MakeBoolVar()
MakeBoolVar will create a variable with a {0, 1} domain.
bool UseFastLocalSearch() const
Returns true if fast local search is enabled.
bool InstrumentsVariables() const
Returns whether we are tracing variables.
Decision * MakeScheduleOrPostpone(IntervalVar *const var, int64 est, int64 *const marker)
Returns a decision that tries to schedule a task at a given time.
SearchMonitor * MakeSearchTrace(const std::string &prefix)
Creates a search monitor that will trace precisely the behavior of the search.
Definition: search.cc:394
IntExpr * MakeDiv(IntExpr *const expr, int64 value)
expr / value (integer division)
SearchMonitor * MakeGuidedLocalSearch(bool maximize, IntVar *const objective, IndexEvaluator2 objective_function, int64 step, const std::vector< IntVar * > &vars, double penalty_factor)
Creates a Guided Local Search monitor.
Definition: search.cc:3894
int64 filtered_neighbors() const
The number of filtered neighbors (neighbors accepted by filters).
std::function< int64(int64)> IndexEvaluator1
Callback typedefs.
Constraint * MakeNonEquality(IntExpr *const left, IntExpr *const right)
left != right
Definition: range_cst.cc:564
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
IntVar * MakeIsLessVar(IntExpr *const left, IntExpr *const right)
status var of (left < right)
Definition: range_cst.cc:742
LocalSearchOperator * MakeOperator(const std::vector< IntVar * > &vars, LocalSearchOperators op)
Local Search Operators.
std::string LocalSearchProfile() const
Returns local search profiling information in a human readable format.
void Accept(ModelVisitor *const visitor) const
Accepts the given model visitor.
int SearchLeftDepth() const
Gets the search left depth of the current active search.
void AddBacktrackAction(Action a, bool fast)
When SaveValue() is not the best way to go, one can create a reversible action that will be called up...
Constraint * MakeTemporalDisjunction(IntervalVar *const t1, IntervalVar *const t2, IntVar *const alt)
This constraint implements a temporal disjunction between two interval vars t1 and t2.
Definition: timetabling.cc:403
void MakeIntervalVarArray(int count, int64 start_min, int64 start_max, int64 duration_min, int64 duration_max, int64 end_min, int64 end_max, bool optional, const std::string &name, std::vector< IntervalVar * > *const array)
This method fills the vector with 'count' interval var built with the corresponding parameters.
Definition: interval.cc:2379
int TopProgressPercent()
Returns a percentage representing the propress of the search before reaching the limits of the top-le...
IntVar * MakeIsBetweenVar(IntExpr *const v, int64 l, int64 u)
Definition: expr_cst.cc:1084
void ReSeed(int32 seed)
Reseed the solver random generator.
bool CurrentlyInSolve() const
Returns true whether the current search has been created using a Solve() call instead of a NewSearch ...
IntervalVar * MakeFixedDurationIntervalVar(int64 start_min, int64 start_max, int64 duration, bool optional, const std::string &name)
Creates an interval var with a fixed duration.
Definition: interval.cc:2239
Constraint * MakeIsMemberCt(IntExpr *const expr, const std::vector< int64 > &values, IntVar *const boolvar)
boolvar == (expr in set)
Definition: expr_cst.cc:1478
T * RevAlloc(T *object)
Registers the given object as being reversible.
IntVarStrategy
This enum describes the strategy used to select the next branching variable at each node during the s...
@ CHOOSE_RANDOM
Randomly select one of the remaining unbound variables.
@ CHOOSE_MIN_SIZE
Among unbound variables, select the variable with the smallest size.
@ CHOOSE_FIRST_UNBOUND
Select the first unbound variable.
@ CHOOSE_PATH
Selects the next unbound variable on a path, the path being defined by the variables: var[i] correspo...
@ CHOOSE_HIGHEST_MAX
Among unbound variables, select the variable with the highest maximal value.
@ CHOOSE_MIN_SIZE_LOWEST_MIN
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ INT_VAR_DEFAULT
The default behavior is CHOOSE_FIRST_UNBOUND.
@ CHOOSE_MIN_SIZE_HIGHEST_MAX
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_MAX_REGRET_ON_MIN
Among unbound variables, select the variable with the largest gap between the first and the second va...
@ CHOOSE_MIN_SIZE_HIGHEST_MIN
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_MAX_SIZE
Among unbound variables, select the variable with the highest size.
@ INT_VAR_SIMPLE
The simple selection is CHOOSE_FIRST_UNBOUND.
@ CHOOSE_MIN_SIZE_LOWEST_MAX
Among unbound variables, select the variable with the smallest size, i.e., the smallest number of pos...
@ CHOOSE_LOWEST_MIN
Among unbound variables, select the variable with the smallest minimal value.
DecisionBuilder * MakePhase(const std::vector< IntVar * > &vars, IntVarStrategy var_str, IntValueStrategy val_str)
Phases on IntVar arrays.
Definition: search.cc:2008
SequenceStrategy
Used for scheduling. Not yet implemented.
Solver(const std::string &name)
Solver API.
std::function< int64(int64, int64)> IndexEvaluator2
Constraint * MakeInversePermutationConstraint(const std::vector< IntVar * > &left, const std::vector< IntVar * > &right)
Creates a constraint that enforces that 'left' and 'right' both represent permutations of [0....
Definition: constraints.cc:550
IntervalVar * MakeFixedDurationStartSyncedOnEndIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose start is synchronized with the end of another int...
Definition: interval.cc:2403
DecisionBuilder * MakeNestedOptimize(DecisionBuilder *const db, Assignment *const solution, bool maximize, int64 step)
NestedOptimize will collapse a search tree described by a decision builder 'db' and a set of monitors...
Definition: search.cc:4532
ModelCache * Cache() const
Returns the cache of the model.
Definition: model_cache.cc:849
Constraint * MakeCount(const std::vector< IntVar * > &vars, int64 value, int64 max_count)
|{i | vars[i] == value}| == max_count
Definition: count_cst.cc:30
Decision * MakeRankLastInterval(SequenceVar *const sequence, int index)
Returns a decision that tries to rank last the ith interval var in the sequence variable.
Constraint * MakeAllDifferent(const std::vector< IntVar * > &vars)
All variables are pairwise different.
Definition: alldiff_cst.cc:690
Constraint * MakeSortingConstraint(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &sorted)
Creates a constraint binding the arrays of variables "vars" and "sorted_vars": sorted_vars[0] must be...
Definition: alldiff_cst.cc:714
DecisionBuilder * MakeLocalSearchPhase(Assignment *const assignment, LocalSearchPhaseParameters *const parameters)
Local Search decision builders factories.
IntExpr * MakeSemiContinuousExpr(IntExpr *const expr, int64 fixed_charge, int64 step)
Semi continuous Expression (x <= 0 -> f(x) = 0; x > 0 -> f(x) = ax + b) a >= 0 and b >= 0.
Demon * MakeDelayedConstraintInitialPropagateCallback(Constraint *const ct)
This method is a specialized case of the MakeConstraintDemon method to call the InitiatePropagate of ...
Definition: constraints.cc:38
IntExpr * MakeScalProd(const std::vector< IntVar * > &vars, const std::vector< int64 > &coefs)
scalar product
Definition: expr_array.cc:3541
Constraint * MakeNonOverlappingNonStrictBoxesConstraint(const std::vector< IntVar * > &x_vars, const std::vector< IntVar * > &y_vars, const std::vector< IntVar * > &x_size, const std::vector< IntVar * > &y_size)
This constraint states that all the boxes must not overlap.
bool NameAllVariables() const
Returns whether all variables should be named.
T * RevAllocArray(T *object)
Like RevAlloc() above, but for an array of objects: the array must have been allocated with the new[]...
Constraint * MakePathTransitPrecedenceConstraint(std::vector< IntVar * > nexts, std::vector< IntVar * > transits, const std::vector< std::pair< int, int >> &precedences)
Same as MakePathPrecedenceConstraint but will force i to be before j if the sum of transits on the pa...
int64 unchecked_solutions() const
The number of unchecked solutions found by local search.
IntExpr * MakeSum(IntExpr *const left, IntExpr *const right)
left + right.
IntExpr * CastExpression(const IntVar *const var) const
!defined(SWIG)
SearchMonitor * MakeEnterSearchCallback(std::function< void()> callback)
--— Callback-based search monitors --—
Definition: search.cc:438
IntExpr * MakeIndexExpression(const std::vector< IntVar * > &vars, int64 value)
Returns the expression expr such that vars[expr] == value.
Definition: element.cc:1745
Constraint * MakeIsDifferentCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var != value)
Definition: expr_cst.cc:587
void SetBranchSelector(BranchSelector bs)
Sets the given branch selector on the current active search.
SearchMonitor * MakeTabuSearch(bool maximize, IntVar *const v, int64 step, const std::vector< IntVar * > &vars, int64 keep_tenure, int64 forbid_tenure, double tabu_factor)
MetaHeuristics which try to get the search out of local optima.
Definition: search.cc:3240
IntExpr * MakeSquare(IntExpr *const expr)
expr * expr
IntervalVar * MakeFixedDurationStartSyncedOnStartIntervalVar(IntervalVar *const interval_var, int64 duration, int64 offset)
Creates an interval var with a fixed duration whose start is synchronized with the start of another i...
Definition: interval.cc:2396
OptimizeVar * MakeWeightedMinimize(const std::vector< IntVar * > &sub_objectives, const std::vector< int64 > &weights, int64 step)
Creates a minimization weighted objective.
Definition: search.cc:2903
int64 branches() const
The number of branches explored since the creation of the solver.
std::function< int64(Solver *solver, const std::vector< IntVar * > &vars, int64 first_unbound, int64 last_unbound)> VariableIndexSelector
IntervalVar * MakeMirrorInterval(IntervalVar *const interval_var)
Creates an interval var that is the mirror image of the given one, that is, the interval var obtained...
Definition: interval.cc:2204
uint64 stamp() const
The stamp indicates how many moves in the search tree we have performed.
LocalSearchOperator * MultiArmedBanditConcatenateOperators(const std::vector< LocalSearchOperator * > &ops, double memory_coefficient, double exploration_coefficient, bool maximize)
Creates a local search operator which concatenates a vector of operators.
Constraint * MakeSumLessOrEqual(const std::vector< IntVar * > &vars, int64 cst)
Variation on arrays.
Definition: expr_array.cc:3408
Constraint * MakeIsGreaterCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left > right)
Definition: range_cst.cc:800
Assignment * MakeAssignment()
This method creates an empty assignment.
ModelVisitor * MakePrintModelVisitor()
Prints the model.
Definition: utilities.cc:807
std::function< void()> Closure
Constraint * MakePathCumul(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, const std::vector< IntVar * > &cumuls, const std::vector< IntVar * > &transits)
Creates a constraint which accumulates values along a path such that: cumuls[next[i]] = cumuls[i] + t...
IntVar * MakeIntVar(int64 min, int64 max, const std::string &name)
MakeIntVar will create the best range based int var for the bounds given.
std::function< void(Solver *)> Action
SolutionCollector * MakeFirstSolutionCollector()
Collect the first solution of the search.
Definition: search.cc:2435
int32 Rand32(int32 size)
Returns a random value between 0 and 'size' - 1;.
Constraint * MakeIndexOfConstraint(const std::vector< IntVar * > &vars, IntVar *const index, int64 target)
This constraint is a special case of the element constraint with an array of integer variables,...
Definition: element.cc:1730
void ExportProfilingOverview(const std::string &filename)
Exports the profiling information in a human readable overview.
DecisionBuilder * Compose(DecisionBuilder *const db1, DecisionBuilder *const db2)
Creates a decision builder which sequentially composes decision builders.
Definition: search.cc:552
std::function< IntVar *(int64)> Int64ToIntVar
Constraint * MakeElementEquality(const std::vector< int64 > &vals, IntVar *const index, IntVar *const target)
Definition: element.cc:1667
Constraint * MakeIndexOfFirstMaxValueConstraint(IntVar *index, const std::vector< IntVar * > &vars)
Creates a constraint that binds the index variable to the index of the first variable with the maximu...
Definition: constraints.cc:555
IntExpr * MakeConvexPiecewiseExpr(IntExpr *expr, int64 early_cost, int64 early_date, int64 late_date, int64 late_cost)
Convex piecewise function.
IntVar * MakeIsLessCstVar(IntExpr *const var, int64 value)
status var of (var < value)
Definition: expr_cst.cc:793
MarkerType
This enum is used internally in private methods Solver::PushState and Solver::PopState to tag states ...
SolutionCollector * MakeBestValueSolutionCollector(const Assignment *const assignment, bool maximize)
Collect the solution corresponding to the optimal value of the objective of 'assignment'; if 'assignm...
Definition: search.cc:2548
IntVar * MakeIsGreaterCstVar(IntExpr *const var, int64 value)
status var of (var > value)
Definition: expr_cst.cc:694
Constraint * MakeMinEquality(const std::vector< IntVar * > &vars, IntVar *const min_var)
Definition: expr_array.cc:3364
void AddCastConstraint(CastConstraint *const constraint, IntVar *const target_var, IntExpr *const expr)
Adds 'constraint' to the solver and marks it as a cast constraint, that is, a constraint created call...
IntervalVar * MakeIntervalVar(int64 start_min, int64 start_max, int64 duration_min, int64 duration_max, int64 end_min, int64 end_max, bool optional, const std::string &name)
Creates an interval var by specifying the bounds on start, duration, and end.
Definition: interval.cc:2370
IntVar * MakeIsLessOrEqualCstVar(IntExpr *const var, int64 value)
status var of (var <= value)
Definition: expr_cst.cc:776
OptimizeVar * MakeMinimize(IntVar *const v, int64 step)
Creates a minimization objective.
Definition: search.cc:2849
DecisionBuilder * MakeStoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which stores an Assignment (calls void Assignment::Store())
Constraint * MakeIsLessOrEqualCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var <= value)
Definition: expr_cst.cc:797
Constraint * MakePathPrecedenceConstraint(std::vector< IntVar * > nexts, const std::vector< std::pair< int, int >> &precedences)
Contraint enforcing, for each pair (i,j) in precedences, i to be before j in paths defined by next va...
std::function< DecisionModification()> BranchSelector
bool InstrumentsDemons() const
Returns whether we are instrumenting demons.
std::function< int64(const IntVar *v, int64 id)> VariableValueSelector
SearchMonitor * MakeExitSearchCallback(std::function< void()> callback)
Definition: search.cc:458
static int64 MemoryUsage()
Current memory usage in bytes.
DecisionBuilder * MakeDefaultPhase(const std::vector< IntVar * > &vars)
IntExpr * MakeProd(IntExpr *const left, IntExpr *const right)
left * right
DecisionBuilder * MakeDecisionBuilderFromAssignment(Assignment *const assignment, DecisionBuilder *const db, const std::vector< IntVar * > &vars)
Returns a decision builder for which the left-most leaf corresponds to assignment,...
Definition: search.cc:2195
void set_fail_intercept(std::function< void()> fail_intercept)
Internal.
DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)
Returns a DecisionBuilder which restores an Assignment (calls void Assignment::Restore())
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
Constraint * MakeGreaterOrEqual(IntExpr *const left, IntExpr *const right)
left >= right
Definition: range_cst.cc:542
OptimizeVar * MakeOptimize(bool maximize, IntVar *const v, int64 step)
Creates a objective with a given sense (true = maximization).
Definition: search.cc:2857
Constraint * MakeIsGreaterOrEqualCstCt(IntExpr *const var, int64 value, IntVar *const boolvar)
boolvar == (var >= value)
Definition: expr_cst.cc:698
IntVar * MakeIsGreaterOrEqualVar(IntExpr *const left, IntExpr *const right)
status var of (left >= right)
Definition: range_cst.cc:785
Constraint * MakeIsGreaterOrEqualCt(IntExpr *const left, IntExpr *const right, IntVar *const b)
b == (left >= right)
Definition: range_cst.cc:790
Constraint * MakeSumGreaterOrEqual(const std::vector< IntVar * > &vars, int64 cst)
Definition: expr_array.cc:3418
Constraint * MakeAllowedAssignments(const std::vector< IntVar * > &vars, const IntTupleSet &tuples)
This method creates a constraint where the graph of the relation between the variables is given in ex...
void FinishCurrentSearch()
Tells the solver to kill or restart the current search.
bool IsProduct(IntExpr *const expr, IntExpr **inner_expr, int64 *coefficient)
Returns true if expr represents a product of a expr and a constant.
void NewSearch(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
IntExpr * MakeMonotonicElement(IndexEvaluator1 values, bool increasing, IntVar *const index)
Function based element.
Definition: element.cc:859
Constraint * MakeNoCycle(const std::vector< IntVar * > &nexts, const std::vector< IntVar * > &active, IndexFilter1 sink_handler=nullptr)
Prevent cycles.
IntVar * MakeIntConst(int64 val, const std::string &name)
IntConst will create a constant expression.
SolutionCollector * MakeNBestValueSolutionCollector(const Assignment *const assignment, int solution_count, bool maximize)
Same as MakeBestValueSolutionCollector but collects the best solution_count solutions.
Definition: search.cc:2652
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
Definition: utilities.cc:811
Decision * balancing_decision() const
IntVar * MakeIsLessOrEqualVar(IntExpr *const left, IntExpr *const right)
status var of (left <= right)
Definition: range_cst.cc:698
IntervalVar * RegisterIntervalVar(IntervalVar *const var)
Registers a new IntervalVar and wraps it inside a TraceIntervalVar if necessary.
Definition: trace.cc:865
EvaluatorLocalSearchOperators
This enum is used in Solver::MakeOperator associated with an evaluator to specify the neighborhood to...
@ TSPOPT
Sliding TSP operator.
@ LK
Lin-Kernighan local search.
LocalSearchFilterBound
This enum is used in Solver::MakeLocalSearchObjectiveFilter.
@ GE
Move is accepted when the current objective value >= objective.Min.
@ LE
Move is accepted when the current objective value <= objective.Max.
@ EQ
Move is accepted when the current objective value is in the interval objective.Min .
Constraint * MakeScalProdEquality(const std::vector< IntVar * > &vars, const std::vector< int64 > &coefficients, int64 cst)
Definition: expr_array.cc:3483
OptimizationDirection optimization_direction() const
The direction of optimization, getter and setter.
void SaveAndAdd(T *adr, T val)
All-in-one SaveAndAdd_value.
This class represents a sorted list of disjoint, closed intervals.
A symmetry breaker is an object that will visit a decision and create the 'symmetrical' decision in r...
ABSL_DECLARE_FLAG(int64, cp_random_seed)
Declaration of the core objects for the constraint solver.
CpModelProto proto
SharedBoundsManager * bounds
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
MPCallback * callback
int int32
static const int64 kint64max
int64_t int64
uint64_t uint64
const bool DEBUG_MODE
Definition: macros.h:24
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
Definition: file.cc:141
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition: map_util.h:155
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:26
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
void SetAssignmentFromAssignment(Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
NOLINT.
int64 One()
This method returns 1.
int index
Definition: pack.cc:508
int64 time
Definition: resource.cc:1683
int64 delta
Definition: resource.cc:1684
int64 capacity
int64 coefficient
std::vector< double > coefficients
Rev< int64 > end_min
Rev< int64 > end_max
Rev< int64 > start_max
Rev< int64 > start_min
const int64 stamp_
Definition: search.cc:3039
This struct holds all parameters for the default search.
int heuristic_num_failures_limit
The failure limit for each heuristic that we run.
int initialization_splits
Maximum number of intervals that the initialization of impacts will scan per variable.
DecisionBuilder * decision_builder
When defined, this overrides the default impact based decision builder.
DisplayLevel display_level
This represents the amount of information displayed by the default search.
ValueSelection value_selection_schema
This parameter describes which value to select for a given var.
VariableSelection var_selection_schema
This parameter describes how the next variable to instantiate will be chosen.
bool persistent_impact
Whether to keep the impact from the first search for other searches, or to recompute the impact for e...
bool use_last_conflict
Should we use last conflict method. The default is false.
int heuristic_period
The distance in nodes between each run of the heuristics.
int random_seed
Seed used to initialize the random part in some heuristics.
bool run_all_heuristics
The default phase will run heuristics periodically.
static Iterator Begin(IntVarIterator *it)
These are the only way to construct an Iterator.
bool operator!=(const Iterator &other) const
static Iterator End(IntVarIterator *it)
bool operator<(const SolutionData &other) const
Holds semantic information stating that the 'expression' has been cast into 'variable' using the Var(...
IntegerCastInfo(IntVar *const v, IntExpr *const e, Constraint *const c)
Creates a search monitor from logging parameters.
int branch_period
SearchMonitors will display a periodic search log every branch_period branches explored.
OptimizeVar * objective
SearchMonitors will display values of objective or variable (both cannot be used together).
std::function< std::string()> display_callback
SearchMonitors will display the result of display_callback at each new solution found and when the se...
double scaling_factor
When displayed, objective or var values will be scaled and offset by the given values in the followin...
bool display_on_new_solutions_only
To be used to protect from cases where display_callback assumes variables are instantiated,...