C++ Reference

C++ Reference: Routing

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 
62 
63 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
64 #define OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
65 
66 #include <functional>
67 #include <iosfwd>
68 #include <memory>
69 #include <random>
70 #include <string>
71 #include <utility>
72 #include <vector>
73 
74 #include "absl/container/flat_hash_map.h"
75 #include "absl/container/flat_hash_set.h"
76 #include "absl/random/distributions.h"
77 #include "absl/random/random.h"
78 #include "absl/strings/str_format.h"
79 #include "ortools/base/commandlineflags.h"
80 #include "ortools/base/hash.h"
81 #include "ortools/base/integral_types.h"
82 #include "ortools/base/logging.h"
83 #include "ortools/base/macros.h"
84 #include "ortools/base/map_util.h"
85 #include "ortools/base/sysinfo.h"
86 #include "ortools/base/timer.h"
88 #include "ortools/util/piecewise_linear_function.h"
89 #include "ortools/util/sorted_interval_list.h"
90 #include "ortools/util/tuple_set.h"
91 
92 #if !defined(SWIG)
93 DECLARE_int64(cp_random_seed);
94 #endif // !defined(SWIG)
95 
96 class File;
97 
98 namespace operations_research {
99 
100 class Assignment;
101 class AssignmentProto;
102 class BaseObject;
103 class CpArgument;
104 class CpConstraint;
105 class CpIntegerExpression;
106 class CpIntervalVariable;
107 class CpSequenceVariable;
108 class CastConstraint;
109 class Constraint;
110 class Decision;
111 class DecisionBuilder;
112 class DecisionVisitor;
113 class Demon;
114 class DemonProfiler;
115 class LocalSearchProfiler;
116 class Dimension;
117 class DisjunctiveConstraint;
118 class ExpressionCache;
119 class IntExpr;
120 class IntTupleSet;
121 class IntVar;
122 class IntVarAssignment;
123 class IntVarElement;
124 class IntervalVar;
125 class IntervalVarAssignment;
126 class IntervalVarElement;
127 class IntVarLocalSearchFilter;
128 class LocalSearchFilter;
129 class LocalSearchOperator;
130 class LocalSearchPhaseParameters;
131 class ModelCache;
132 class ModelVisitor;
133 class OptimizeVar;
134 class Pack;
135 class PropagationBaseObject;
136 class PropagationMonitor;
137 class LocalSearchMonitor;
138 class Queue;
139 class RevBitMatrix;
140 class RevBitSet;
141 class RegularLimit;
142 class RegularLimitParameters;
143 class Search;
144 class SearchLimit;
145 class SearchMonitor;
146 class SequenceVar;
147 class SequenceVarAssignment;
148 class SolutionCollector;
149 class SolutionPool;
150 class Solver;
151 class ConstraintSolverParameters;
152 class SymmetryBreaker;
153 struct StateInfo;
154 struct Trail;
155 template <class T>
156 class SimpleRevFIFO;
157 
158 inline int64 CpRandomSeed() {
159  return FLAGS_cp_random_seed == -1
160  ? absl::Uniform<int64>(absl::BitGen(), 0, kint64max)
161  : FLAGS_cp_random_seed;
162 }
163 
167 struct DefaultPhaseParameters {
168  public:
169  enum VariableSelection {
170  CHOOSE_MAX_SUM_IMPACT = 0,
171  CHOOSE_MAX_AVERAGE_IMPACT = 1,
172  CHOOSE_MAX_VALUE_IMPACT = 2,
173  };
174 
175  enum ValueSelection {
176  SELECT_MIN_IMPACT = 0,
177  SELECT_MAX_IMPACT = 1,
178  };
179 
180  enum DisplayLevel { NONE = 0, NORMAL = 1, VERBOSE = 2 };
181 
184  VariableSelection var_selection_schema;
185 
187  ValueSelection value_selection_schema;
188 
191  int initialization_splits;
192 
196  bool run_all_heuristics;
197 
201  int heuristic_period;
202 
204  int heuristic_num_failures_limit;
205 
208  bool persistent_impact;
209 
211  int random_seed;
212 
215  DisplayLevel display_level;
216 
218  bool use_last_conflict;
219 
221  DecisionBuilder* decision_builder;
222 
223  DefaultPhaseParameters();
224 };
225 
243 class Solver {
244  public:
249  struct IntegerCastInfo {
250  IntegerCastInfo()
251  : variable(nullptr), expression(nullptr), maintainer(nullptr) {}
252  IntegerCastInfo(IntVar* const v, IntExpr* const e, Constraint* const c)
253  : variable(v), expression(e), maintainer(c) {}
254  IntVar* variable;
255  IntExpr* expression;
256  Constraint* maintainer;
257  };
258 
260  static const int kNumPriorities = 3;
261 
264  enum IntVarStrategy {
266  INT_VAR_DEFAULT,
267 
269  INT_VAR_SIMPLE,
270 
274  CHOOSE_FIRST_UNBOUND,
275 
277  CHOOSE_RANDOM,
278 
285  CHOOSE_MIN_SIZE_LOWEST_MIN,
286 
293  CHOOSE_MIN_SIZE_HIGHEST_MIN,
294 
301  CHOOSE_MIN_SIZE_LOWEST_MAX,
302 
309  CHOOSE_MIN_SIZE_HIGHEST_MAX,
310 
315  CHOOSE_LOWEST_MIN,
316 
321  CHOOSE_HIGHEST_MAX,
322 
326  CHOOSE_MIN_SIZE,
327 
331  CHOOSE_MAX_SIZE,
332 
335  CHOOSE_MAX_REGRET_ON_MIN,
336 
339  CHOOSE_PATH,
340  };
341  // TODO(user): add HIGHEST_MIN and LOWEST_MAX.
342 
345  enum IntValueStrategy {
347  INT_VALUE_DEFAULT,
348 
350  INT_VALUE_SIMPLE,
351 
353  ASSIGN_MIN_VALUE,
354 
356  ASSIGN_MAX_VALUE,
357 
359  ASSIGN_RANDOM_VALUE,
360 
364  ASSIGN_CENTER_VALUE,
365 
368  SPLIT_LOWER_HALF,
369 
372  SPLIT_UPPER_HALF,
373  };
374 
385  enum EvaluatorStrategy {
390  CHOOSE_STATIC_GLOBAL_BEST,
391 
396  CHOOSE_DYNAMIC_GLOBAL_BEST,
397  };
398 
400  enum SequenceStrategy {
401  SEQUENCE_DEFAULT,
402  SEQUENCE_SIMPLE,
403  CHOOSE_MIN_SLACK_RANK_FORWARD,
404  CHOOSE_RANDOM_RANK_FORWARD,
405  };
406 
409  enum IntervalStrategy {
411  INTERVAL_DEFAULT,
413  INTERVAL_SIMPLE,
416  INTERVAL_SET_TIMES_FORWARD,
419  INTERVAL_SET_TIMES_BACKWARD
420  };
421 
424  enum LocalSearchOperators {
434  TWOOPT,
435 
450  OROPT,
451 
453  RELOCATE,
454 
462  EXCHANGE,
463 
473  CROSS,
474 
481  MAKEACTIVE,
482 
488  MAKEINACTIVE,
489 
496  MAKECHAININACTIVE,
497 
503  SWAPACTIVE,
504 
515  EXTENDEDSWAPACTIVE,
516 
524  PATHLNS,
525 
528  FULLPATHLNS,
529 
533  UNACTIVELNS,
534 
543  INCREMENT,
544 
548  DECREMENT,
549 
557  SIMPLELNS
558  };
559 
562  enum EvaluatorLocalSearchOperators {
567  LK,
568 
575  TSPOPT,
576 
583  TSPLNS
584  };
585 
590  enum LocalSearchFilterBound {
592  GE,
594  LE,
597  EQ
598  };
599 
603  enum DemonPriority {
606  DELAYED_PRIORITY = 0,
607 
609  VAR_PRIORITY = 1,
610 
612  NORMAL_PRIORITY = 2,
613  };
614 
617  enum BinaryIntervalRelation {
619  ENDS_AFTER_END,
620 
622  ENDS_AFTER_START,
623 
625  ENDS_AT_END,
626 
628  ENDS_AT_START,
629 
631  STARTS_AFTER_END,
632 
634  STARTS_AFTER_START,
635 
637  STARTS_AT_END,
638 
640  STARTS_AT_START,
641 
645  STAYS_IN_SYNC
646  };
647 
650  enum UnaryIntervalRelation {
652  ENDS_AFTER,
653 
655  ENDS_AT,
656 
658  ENDS_BEFORE,
659 
661  STARTS_AFTER,
662 
664  STARTS_AT,
665 
667  STARTS_BEFORE,
668 
672  CROSS_DATE,
673 
677  AVOID_DATE
678  };
679 
685  enum DecisionModification {
688  NO_CHANGE,
689 
693  KEEP_LEFT,
694 
698  KEEP_RIGHT,
699 
702  KILL_BOTH,
703 
706  SWITCH_BRANCHES
707  };
708 
711  enum MarkerType { SENTINEL, SIMPLE_MARKER, CHOICE_POINT, REVERSIBLE_ACTION };
712 
714  enum SolverState {
716  OUTSIDE_SEARCH,
718  IN_ROOT_NODE,
720  IN_SEARCH,
722  AT_SOLUTION,
724  NO_MORE_SOLUTIONS,
726  PROBLEM_INFEASIBLE
727  };
728 
730  enum OptimizationDirection { NOT_SET, MAXIMIZATION, MINIMIZATION };
731 
733  typedef std::function<int64(int64)> IndexEvaluator1;
734  typedef std::function<int64(int64, int64)> IndexEvaluator2;
735  typedef std::function<int64(int64, int64, int64)> IndexEvaluator3;
736 
737  typedef std::function<bool(int64)> IndexFilter1;
738 
739  typedef std::function<IntVar*(int64)> Int64ToIntVar;
740 
741  typedef std::function<int64(Solver* solver, const std::vector<IntVar*>& vars,
742  int64 first_unbound, int64 last_unbound)>
743  VariableIndexSelector;
744 
745  typedef std::function<int64(const IntVar* v, int64 id)> VariableValueSelector;
746  typedef std::function<bool(int64, int64, int64)> VariableValueComparator;
747  typedef std::function<DecisionModification()> BranchSelector;
748  // TODO(user): wrap in swig.
749  typedef std::function<void(Solver*)> Action;
750  typedef std::function<void()> Closure;
751 
753  explicit Solver(const std::string& name);
754  Solver(const std::string& name, const ConstraintSolverParameters& parameters);
755  ~Solver();
756 
758  ConstraintSolverParameters parameters() const { return parameters_; }
760  // TODO(user): Move to constraint_solver_parameters.h.
761  static ConstraintSolverParameters DefaultSolverParameters();
762 
764 
768  template <class T>
769  void SaveValue(T* o) {
770  InternalSaveValue(o);
771  }
772 
785  template <typename T>
786  T* RevAlloc(T* object) {
787  return reinterpret_cast<T*>(SafeRevAlloc(object));
788  }
789 
796  template <typename T>
797  T* RevAllocArray(T* object) {
798  return reinterpret_cast<T*>(SafeRevAllocArray(object));
799  }
800 
834  void AddConstraint(Constraint* const c);
838  void AddCastConstraint(CastConstraint* const constraint,
839  IntVar* const target_var, IntExpr* const expr);
840 
882  bool Solve(DecisionBuilder* const db,
883  const std::vector<SearchMonitor*>& monitors);
884  bool Solve(DecisionBuilder* const db);
885  bool Solve(DecisionBuilder* const db, SearchMonitor* const m1);
886  bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
887  SearchMonitor* const m2);
888  bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
889  SearchMonitor* const m2, SearchMonitor* const m3);
890  bool Solve(DecisionBuilder* const db, SearchMonitor* const m1,
891  SearchMonitor* const m2, SearchMonitor* const m3,
892  SearchMonitor* const m4);
894 
903 
904  void NewSearch(DecisionBuilder* const db,
905  const std::vector<SearchMonitor*>& monitors);
906  void NewSearch(DecisionBuilder* const db);
907  void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1);
908  void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
909  SearchMonitor* const m2);
910  void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
911  SearchMonitor* const m2, SearchMonitor* const m3);
912  void NewSearch(DecisionBuilder* const db, SearchMonitor* const m1,
913  SearchMonitor* const m2, SearchMonitor* const m3,
914  SearchMonitor* const m4);
915 
916  bool NextSolution();
917  void RestartSearch();
918  void EndSearch();
920 
929  bool SolveAndCommit(DecisionBuilder* const db,
930  const std::vector<SearchMonitor*>& monitors);
931  bool SolveAndCommit(DecisionBuilder* const db);
932  bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1);
933  bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1,
934  SearchMonitor* const m2);
935  bool SolveAndCommit(DecisionBuilder* const db, SearchMonitor* const m1,
936  SearchMonitor* const m2, SearchMonitor* const m3);
937 
939  bool CheckAssignment(Assignment* const solution);
940 
944  bool CheckConstraint(Constraint* const ct);
945 
947  SolverState state() const { return state_; }
948 
950  void Fail();
951 
952 #if !defined(SWIG)
953  void AddBacktrackAction(Action a, bool fast);
958 #endif
959 
960  std::string DebugString() const;
962 
964  static int64 MemoryUsage();
965 
970  absl::Time Now() const;
971 
974  int64 wall_time() const;
975 
977  int64 branches() const { return branches_; }
978 
980  int64 solutions() const;
981 
983  int64 unchecked_solutions() const;
984 
986  int64 demon_runs(DemonPriority p) const { return demon_runs_[p]; }
987 
989  int64 failures() const { return fails_; }
990 
992  int64 neighbors() const { return neighbors_; }
993 
995  int64 filtered_neighbors() const { return filtered_neighbors_; }
996 
998  int64 accepted_neighbors() const { return accepted_neighbors_; }
999 
1002  uint64 stamp() const;
1003 
1005  uint64 fail_stamp() const;
1006 
1008  OptimizationDirection optimization_direction() const {
1009  return optimization_direction_;
1010  }
1011  void set_optimization_direction(OptimizationDirection direction) {
1012  optimization_direction_ = direction;
1013  }
1014 
1015  // All factories (MakeXXX methods) encapsulate creation of objects
1016  // through RevAlloc(). Hence, the Solver used for allocating the
1017  // returned object will retain ownership of the allocated memory.
1018  // Destructors are called upon backtrack, or when the Solver is
1019  // itself destructed.
1020 
1021  // ----- Int Variables and Constants -----
1022 
1024  IntVar* MakeIntVar(int64 min, int64 max, const std::string& name);
1025 
1027  IntVar* MakeIntVar(const std::vector<int64>& values, const std::string& name);
1028 
1030  IntVar* MakeIntVar(const std::vector<int>& values, const std::string& name);
1031 
1033  IntVar* MakeIntVar(int64 min, int64 max);
1034 
1036  IntVar* MakeIntVar(const std::vector<int64>& values);
1037 
1039  IntVar* MakeIntVar(const std::vector<int>& values);
1040 
1042  IntVar* MakeBoolVar(const std::string& name);
1043 
1045  IntVar* MakeBoolVar();
1046 
1048  IntVar* MakeIntConst(int64 val, const std::string& name);
1049 
1051  IntVar* MakeIntConst(int64 val);
1052 
1056  void MakeIntVarArray(int var_count, int64 vmin, int64 vmax,
1057  const std::string& name, std::vector<IntVar*>* vars);
1060  void MakeIntVarArray(int var_count, int64 vmin, int64 vmax,
1061  std::vector<IntVar*>* vars);
1063  IntVar** MakeIntVarArray(int var_count, int64 vmin, int64 vmax,
1064  const std::string& name);
1065 
1069  void MakeBoolVarArray(int var_count, const std::string& name,
1070  std::vector<IntVar*>* vars);
1073  void MakeBoolVarArray(int var_count, std::vector<IntVar*>* vars);
1075  IntVar** MakeBoolVarArray(int var_count, const std::string& name);
1076 
1077  // ----- Integer Expressions -----
1078 
1080  IntExpr* MakeSum(IntExpr* const left, IntExpr* const right);
1082  IntExpr* MakeSum(IntExpr* const expr, int64 value);
1084  IntExpr* MakeSum(const std::vector<IntVar*>& vars);
1085 
1087  IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1088  const std::vector<int64>& coefs);
1090  IntExpr* MakeScalProd(const std::vector<IntVar*>& vars,
1091  const std::vector<int>& coefs);
1092 
1094  IntExpr* MakeDifference(IntExpr* const left, IntExpr* const right);
1096  IntExpr* MakeDifference(int64 value, IntExpr* const expr);
1098  IntExpr* MakeOpposite(IntExpr* const expr);
1099 
1101  IntExpr* MakeProd(IntExpr* const left, IntExpr* const right);
1103  IntExpr* MakeProd(IntExpr* const expr, int64 value);
1104 
1106  IntExpr* MakeDiv(IntExpr* const expr, int64 value);
1108  IntExpr* MakeDiv(IntExpr* const numerator, IntExpr* const denominator);
1109 
1111  IntExpr* MakeAbs(IntExpr* const expr);
1113  IntExpr* MakeSquare(IntExpr* const expr);
1115  IntExpr* MakePower(IntExpr* const expr, int64 n);
1116 
1118  IntExpr* MakeElement(const std::vector<int64>& values, IntVar* const index);
1120  IntExpr* MakeElement(const std::vector<int>& values, IntVar* const index);
1121 
1125  IntExpr* MakeElement(IndexEvaluator1 values, IntVar* const index);
1132  IntExpr* MakeMonotonicElement(IndexEvaluator1 values, bool increasing,
1133  IntVar* const index);
1135  IntExpr* MakeElement(IndexEvaluator2 values, IntVar* const index1,
1136  IntVar* const index2);
1137 
1139  IntExpr* MakeElement(const std::vector<IntVar*>& vars, IntVar* const index);
1140 
1141 #if !defined(SWIG)
1142  IntExpr* MakeElement(Int64ToIntVar vars, int64 range_start, int64 range_end,
1144  IntVar* argument);
1145 #endif // SWIG
1146 
1149  IntExpr* MakeIndexExpression(const std::vector<IntVar*>& vars, int64 value);
1150 
1152  Constraint* MakeIfThenElseCt(IntVar* const condition,
1153  IntExpr* const then_expr,
1154  IntExpr* const else_expr,
1155  IntVar* const target_var);
1156 
1158  IntExpr* MakeMin(const std::vector<IntVar*>& vars);
1160  IntExpr* MakeMin(IntExpr* const left, IntExpr* const right);
1162  IntExpr* MakeMin(IntExpr* const expr, int64 value);
1164  IntExpr* MakeMin(IntExpr* const expr, int value);
1165 
1167  IntExpr* MakeMax(const std::vector<IntVar*>& vars);
1169  IntExpr* MakeMax(IntExpr* const left, IntExpr* const right);
1171  IntExpr* MakeMax(IntExpr* const expr, int64 value);
1173  IntExpr* MakeMax(IntExpr* const expr, int value);
1174 
1176  IntExpr* MakeConvexPiecewiseExpr(IntExpr* expr, int64 early_cost,
1177  int64 early_date, int64 late_date,
1178  int64 late_cost);
1179 
1182  IntExpr* MakeSemiContinuousExpr(IntExpr* const expr, int64 fixed_charge,
1183  int64 step);
1184 
1187  // TODO(user): Investigate if we can merge all three piecewise linear
1189 #ifndef SWIG
1190  IntExpr* MakePiecewiseLinearExpr(IntExpr* expr,
1191  const PiecewiseLinearFunction& f);
1192 #endif
1193 
1195  IntExpr* MakeModulo(IntExpr* const x, int64 mod);
1196 
1198  IntExpr* MakeModulo(IntExpr* const x, IntExpr* const mod);
1199 
1201  IntExpr* MakeConditionalExpression(IntVar* const condition,
1202  IntExpr* const expr,
1203  int64 unperformed_value);
1204 
1206  Constraint* MakeTrueConstraint();
1208  Constraint* MakeFalseConstraint();
1209  Constraint* MakeFalseConstraint(const std::string& explanation);
1210 
1212  Constraint* MakeIsEqualCstCt(IntExpr* const var, int64 value,
1213  IntVar* const boolvar);
1215  IntVar* MakeIsEqualCstVar(IntExpr* const var, int64 value);
1217  Constraint* MakeIsEqualCt(IntExpr* const v1, IntExpr* v2, IntVar* const b);
1219  IntVar* MakeIsEqualVar(IntExpr* const v1, IntExpr* v2);
1221  Constraint* MakeEquality(IntExpr* const left, IntExpr* const right);
1223  Constraint* MakeEquality(IntExpr* const expr, int64 value);
1225  Constraint* MakeEquality(IntExpr* const expr, int value);
1226 
1228  Constraint* MakeIsDifferentCstCt(IntExpr* const var, int64 value,
1229  IntVar* const boolvar);
1231  IntVar* MakeIsDifferentCstVar(IntExpr* const var, int64 value);
1233  IntVar* MakeIsDifferentVar(IntExpr* const v1, IntExpr* const v2);
1235  Constraint* MakeIsDifferentCt(IntExpr* const v1, IntExpr* const v2,
1236  IntVar* const b);
1238  Constraint* MakeNonEquality(IntExpr* const left, IntExpr* const right);
1240  Constraint* MakeNonEquality(IntExpr* const expr, int64 value);
1242  Constraint* MakeNonEquality(IntExpr* const expr, int value);
1243 
1245  Constraint* MakeIsLessOrEqualCstCt(IntExpr* const var, int64 value,
1246  IntVar* const boolvar);
1248  IntVar* MakeIsLessOrEqualCstVar(IntExpr* const var, int64 value);
1250  IntVar* MakeIsLessOrEqualVar(IntExpr* const left, IntExpr* const right);
1252  Constraint* MakeIsLessOrEqualCt(IntExpr* const left, IntExpr* const right,
1253  IntVar* const b);
1255  Constraint* MakeLessOrEqual(IntExpr* const left, IntExpr* const right);
1257  Constraint* MakeLessOrEqual(IntExpr* const expr, int64 value);
1259  Constraint* MakeLessOrEqual(IntExpr* const expr, int value);
1260 
1262  Constraint* MakeIsGreaterOrEqualCstCt(IntExpr* const var, int64 value,
1263  IntVar* const boolvar);
1265  IntVar* MakeIsGreaterOrEqualCstVar(IntExpr* const var, int64 value);
1267  IntVar* MakeIsGreaterOrEqualVar(IntExpr* const left, IntExpr* const right);
1269  Constraint* MakeIsGreaterOrEqualCt(IntExpr* const left, IntExpr* const right,
1270  IntVar* const b);
1272  Constraint* MakeGreaterOrEqual(IntExpr* const left, IntExpr* const right);
1274  Constraint* MakeGreaterOrEqual(IntExpr* const expr, int64 value);
1276  Constraint* MakeGreaterOrEqual(IntExpr* const expr, int value);
1277 
1279  Constraint* MakeIsGreaterCstCt(IntExpr* const v, int64 c, IntVar* const b);
1281  IntVar* MakeIsGreaterCstVar(IntExpr* const var, int64 value);
1283  IntVar* MakeIsGreaterVar(IntExpr* const left, IntExpr* const right);
1285  Constraint* MakeIsGreaterCt(IntExpr* const left, IntExpr* const right,
1286  IntVar* const b);
1288  Constraint* MakeGreater(IntExpr* const left, IntExpr* const right);
1290  Constraint* MakeGreater(IntExpr* const expr, int64 value);
1292  Constraint* MakeGreater(IntExpr* const expr, int value);
1293 
1295  Constraint* MakeIsLessCstCt(IntExpr* const v, int64 c, IntVar* const b);
1297  IntVar* MakeIsLessCstVar(IntExpr* const var, int64 value);
1299  IntVar* MakeIsLessVar(IntExpr* const left, IntExpr* const right);
1301  Constraint* MakeIsLessCt(IntExpr* const left, IntExpr* const right,
1302  IntVar* const b);
1304  Constraint* MakeLess(IntExpr* const left, IntExpr* const right);
1306  Constraint* MakeLess(IntExpr* const expr, int64 value);
1308  Constraint* MakeLess(IntExpr* const expr, int value);
1309 
1311  Constraint* MakeSumLessOrEqual(const std::vector<IntVar*>& vars, int64 cst);
1312  Constraint* MakeSumGreaterOrEqual(const std::vector<IntVar*>& vars,
1313  int64 cst);
1314  Constraint* MakeSumEquality(const std::vector<IntVar*>& vars, int64 cst);
1315  Constraint* MakeSumEquality(const std::vector<IntVar*>& vars,
1316  IntVar* const var);
1317  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1318  const std::vector<int64>& coefficients,
1319  int64 cst);
1320  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1321  const std::vector<int>& coefficients,
1322  int64 cst);
1323  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1324  const std::vector<int64>& coefficients,
1325  IntVar* const target);
1326  Constraint* MakeScalProdEquality(const std::vector<IntVar*>& vars,
1327  const std::vector<int>& coefficients,
1328  IntVar* const target);
1329  Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1330  const std::vector<int64>& coeffs,
1331  int64 cst);
1332  Constraint* MakeScalProdGreaterOrEqual(const std::vector<IntVar*>& vars,
1333  const std::vector<int>& coeffs,
1334  int64 cst);
1335  Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1336  const std::vector<int64>& coefficients,
1337  int64 cst);
1338  Constraint* MakeScalProdLessOrEqual(const std::vector<IntVar*>& vars,
1339  const std::vector<int>& coefficients,
1340  int64 cst);
1341 
1342  Constraint* MakeMinEquality(const std::vector<IntVar*>& vars,
1343  IntVar* const min_var);
1344  Constraint* MakeMaxEquality(const std::vector<IntVar*>& vars,
1345  IntVar* const max_var);
1346 
1347  Constraint* MakeElementEquality(const std::vector<int64>& vals,
1348  IntVar* const index, IntVar* const target);
1349  Constraint* MakeElementEquality(const std::vector<int>& vals,
1350  IntVar* const index, IntVar* const target);
1351  Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1352  IntVar* const index, IntVar* const target);
1353  Constraint* MakeElementEquality(const std::vector<IntVar*>& vars,
1354  IntVar* const index, int64 target);
1356  Constraint* MakeAbsEquality(IntVar* const var, IntVar* const abs_var);
1361  Constraint* MakeIndexOfConstraint(const std::vector<IntVar*>& vars,
1362  IntVar* const index, int64 target);
1363 
1366  Demon* MakeConstraintInitialPropagateCallback(Constraint* const ct);
1370  Demon* MakeDelayedConstraintInitialPropagateCallback(Constraint* const ct);
1371 #if !defined(SWIG)
1372  Demon* MakeActionDemon(Action action);
1374 #endif
1375  Demon* MakeClosureDemon(Closure closure);
1377 
1378  // ----- Between and related constraints -----
1379 
1381  Constraint* MakeBetweenCt(IntExpr* const expr, int64 l, int64 u);
1382 
1387  Constraint* MakeNotBetweenCt(IntExpr* const expr, int64 l, int64 u);
1388 
1390  Constraint* MakeIsBetweenCt(IntExpr* const expr, int64 l, int64 u,
1391  IntVar* const b);
1392  IntVar* MakeIsBetweenVar(IntExpr* const v, int64 l, int64 u);
1393 
1394  // ----- Member and related constraints -----
1395 
1398  Constraint* MakeMemberCt(IntExpr* const expr,
1399  const std::vector<int64>& values);
1400  Constraint* MakeMemberCt(IntExpr* const expr, const std::vector<int>& values);
1401 
1403  Constraint* MakeNotMemberCt(IntExpr* const expr,
1404  const std::vector<int64>& values);
1405  Constraint* MakeNotMemberCt(IntExpr* const expr,
1406  const std::vector<int>& values);
1407 
1409  Constraint* MakeNotMemberCt(IntExpr* const expr, std::vector<int64> starts,
1410  std::vector<int64> ends);
1412  Constraint* MakeNotMemberCt(IntExpr* const expr, std::vector<int> starts,
1413  std::vector<int> ends);
1414 #if !defined(SWIG)
1415  Constraint* MakeNotMemberCt(IntExpr* expr,
1417  SortedDisjointIntervalList intervals);
1418 #endif // !defined(SWIG)
1419 
1421  Constraint* MakeIsMemberCt(IntExpr* const expr,
1422  const std::vector<int64>& values,
1423  IntVar* const boolvar);
1424  Constraint* MakeIsMemberCt(IntExpr* const expr,
1425  const std::vector<int>& values,
1426  IntVar* const boolvar);
1427  IntVar* MakeIsMemberVar(IntExpr* const expr,
1428  const std::vector<int64>& values);
1429  IntVar* MakeIsMemberVar(IntExpr* const expr, const std::vector<int>& values);
1430 
1432  Constraint* MakeAtMost(std::vector<IntVar*> vars, int64 value,
1433  int64 max_count);
1435  Constraint* MakeCount(const std::vector<IntVar*>& vars, int64 value,
1436  int64 max_count);
1438  Constraint* MakeCount(const std::vector<IntVar*>& vars, int64 value,
1439  IntVar* const max_count);
1440 
1442  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1443  const std::vector<int64>& values,
1444  const std::vector<IntVar*>& cards);
1446  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1447  const std::vector<int>& values,
1448  const std::vector<IntVar*>& cards);
1450  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1451  const std::vector<IntVar*>& cards);
1454  Constraint* MakeDistribute(const std::vector<IntVar*>& vars, int64 card_min,
1455  int64 card_max, int64 card_size);
1459  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1460  const std::vector<int64>& card_min,
1461  const std::vector<int64>& card_max);
1465  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1466  const std::vector<int>& card_min,
1467  const std::vector<int>& card_max);
1471  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1472  const std::vector<int64>& values,
1473  const std::vector<int64>& card_min,
1474  const std::vector<int64>& card_max);
1478  Constraint* MakeDistribute(const std::vector<IntVar*>& vars,
1479  const std::vector<int>& values,
1480  const std::vector<int>& card_min,
1481  const std::vector<int>& card_max);
1482 
1487  Constraint* MakeDeviation(const std::vector<IntVar*>& vars,
1488  IntVar* const deviation_var, int64 total_sum);
1489 
1492  Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars);
1493 
1497  Constraint* MakeAllDifferent(const std::vector<IntVar*>& vars,
1498  bool stronger_propagation);
1499 
1502  Constraint* MakeAllDifferentExcept(const std::vector<IntVar*>& vars,
1503  int64 escape_value);
1504  // TODO(user): Do we need a version with an array of escape values.
1505 
1521  Constraint* MakeSortingConstraint(const std::vector<IntVar*>& vars,
1522  const std::vector<IntVar*>& sorted);
1523  // TODO(user): Add void MakeSortedArray(
1524  // const std::vector<IntVar*>& vars,
1525  // std::vector<IntVar*>* const sorted);
1526 
1529  Constraint* MakeLexicalLess(const std::vector<IntVar*>& left,
1530  const std::vector<IntVar*>& right);
1531 
1534  Constraint* MakeLexicalLessOrEqual(const std::vector<IntVar*>& left,
1535  const std::vector<IntVar*>& right);
1536 
1541  Constraint* MakeInversePermutationConstraint(
1542  const std::vector<IntVar*>& left, const std::vector<IntVar*>& right);
1543 
1546  Constraint* MakeIndexOfFirstMaxValueConstraint(
1547  IntVar* index, const std::vector<IntVar*>& vars);
1548 
1551  Constraint* MakeIndexOfFirstMinValueConstraint(
1552  IntVar* index, const std::vector<IntVar*>& vars);
1553 
1558  Constraint* MakeNullIntersect(const std::vector<IntVar*>& first_vars,
1559  const std::vector<IntVar*>& second_vars);
1560 
1566  Constraint* MakeNullIntersectExcept(const std::vector<IntVar*>& first_vars,
1567  const std::vector<IntVar*>& second_vars,
1568  int64 escape_value);
1569 
1570  // TODO(user): Implement MakeAllNullIntersect taking an array of
1571  // variable vectors.
1572 
1582  Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1583  const std::vector<IntVar*>& active,
1584  IndexFilter1 sink_handler = nullptr);
1585  Constraint* MakeNoCycle(const std::vector<IntVar*>& nexts,
1586  const std::vector<IntVar*>& active,
1587  IndexFilter1 sink_handler, bool assume_paths);
1588 
1590  Constraint* MakeCircuit(const std::vector<IntVar*>& nexts);
1591 
1594  Constraint* MakeSubCircuit(const std::vector<IntVar*>& nexts);
1595 
1600  Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1601  const std::vector<IntVar*>& active,
1602  const std::vector<IntVar*>& cumuls,
1603  const std::vector<IntVar*>& transits);
1606  // TODO(user): Merge with other path-cumuls constraints.
1607  Constraint* MakeDelayedPathCumul(const std::vector<IntVar*>& nexts,
1608  const std::vector<IntVar*>& active,
1609  const std::vector<IntVar*>& cumuls,
1610  const std::vector<IntVar*>& transits);
1617  Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1618  const std::vector<IntVar*>& active,
1619  const std::vector<IntVar*>& cumuls,
1620  IndexEvaluator2 transit_evaluator);
1621 
1628  Constraint* MakePathCumul(const std::vector<IntVar*>& nexts,
1629  const std::vector<IntVar*>& active,
1630  const std::vector<IntVar*>& cumuls,
1631  const std::vector<IntVar*>& slacks,
1632  IndexEvaluator2 transit_evaluator);
1635  // TODO(user): Only does checking on WhenBound events on next variables.
1637  Constraint* MakePathConnected(std::vector<IntVar*> nexts,
1638  std::vector<int64> sources,
1639  std::vector<int64> sinks,
1640  std::vector<IntVar*> status);
1641 #ifndef SWIG
1642  // TODO(user): This constraint does not make holes in variable domains;
1647  Constraint* MakePathPrecedenceConstraint(
1648  std::vector<IntVar*> nexts,
1649  const std::vector<std::pair<int, int>>& precedences);
1658  Constraint* MakePathPrecedenceConstraint(
1659  std::vector<IntVar*> nexts,
1660  const std::vector<std::pair<int, int>>& precedences,
1661  const std::vector<int>& lifo_path_starts,
1662  const std::vector<int>& fifo_path_starts);
1665  Constraint* MakePathTransitPrecedenceConstraint(
1666  std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1667  const std::vector<std::pair<int, int>>& precedences);
1668 #endif
1669  Constraint* MakeMapDomain(IntVar* const var,
1673  const std::vector<IntVar*>& actives);
1674 
1679  Constraint* MakeAllowedAssignments(const std::vector<IntVar*>& vars,
1680  const IntTupleSet& tuples);
1681 
1689  Constraint* MakeTransitionConstraint(const std::vector<IntVar*>& vars,
1690  const IntTupleSet& transition_table,
1691  int64 initial_state,
1692  const std::vector<int64>& final_states);
1693 
1701  Constraint* MakeTransitionConstraint(const std::vector<IntVar*>& vars,
1702  const IntTupleSet& transition_table,
1703  int64 initial_state,
1704  const std::vector<int>& final_states);
1705 
1706 #if defined(SWIGPYTHON)
1707  Constraint* MakeAllowedAssignments(
1709  const std::vector<IntVar*>& vars,
1710  const std::vector<std::vector<int64>>& raw_tuples) {
1711  IntTupleSet tuples(vars.size());
1712  tuples.InsertAll(raw_tuples);
1713  return MakeAllowedAssignments(vars, tuples);
1714  }
1715 
1716  Constraint* MakeTransitionConstraint(
1717  const std::vector<IntVar*>& vars,
1718  const std::vector<std::vector<int64>>& raw_transitions,
1719  int64 initial_state, const std::vector<int>& final_states) {
1720  IntTupleSet transitions(3);
1721  transitions.InsertAll(raw_transitions);
1722  return MakeTransitionConstraint(vars, transitions, initial_state,
1723  final_states);
1724  }
1725 #endif
1726 
1735  Constraint* MakeNonOverlappingBoxesConstraint(
1736  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1737  const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
1738  Constraint* MakeNonOverlappingBoxesConstraint(
1739  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1740  const std::vector<int64>& x_size, const std::vector<int64>& y_size);
1741  Constraint* MakeNonOverlappingBoxesConstraint(
1742  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1743  const std::vector<int>& x_size, const std::vector<int>& y_size);
1744 
1753  Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
1754  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1755  const std::vector<IntVar*>& x_size, const std::vector<IntVar*>& y_size);
1756  Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
1757  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1758  const std::vector<int64>& x_size, const std::vector<int64>& y_size);
1759  Constraint* MakeNonOverlappingNonStrictBoxesConstraint(
1760  const std::vector<IntVar*>& x_vars, const std::vector<IntVar*>& y_vars,
1761  const std::vector<int>& x_size, const std::vector<int>& y_size);
1762 
1768  Pack* MakePack(const std::vector<IntVar*>& vars, int number_of_bins);
1769 
1774  IntervalVar* MakeFixedDurationIntervalVar(int64 start_min, int64 start_max,
1775  int64 duration, bool optional,
1776  const std::string& name);
1777 
1780  void MakeFixedDurationIntervalVarArray(
1781  int count, int64 start_min, int64 start_max, int64 duration,
1782  bool optional, const std::string& name,
1783  std::vector<IntervalVar*>* const array);
1784 
1787  IntervalVar* MakeFixedDurationIntervalVar(IntVar* const start_variable,
1788  int64 duration,
1789  const std::string& name);
1790 
1793  IntervalVar* MakeFixedDurationIntervalVar(IntVar* const start_variable,
1794  int64 duration,
1795  IntVar* const performed_variable,
1796  const std::string& name);
1797 
1800  void MakeFixedDurationIntervalVarArray(
1801  const std::vector<IntVar*>& start_variables, int64 duration,
1802  const std::string& name, std::vector<IntervalVar*>* const array);
1803 
1806  void MakeFixedDurationIntervalVarArray(
1807  const std::vector<IntVar*>& start_variables,
1808  const std::vector<int64>& durations, const std::string& name,
1809  std::vector<IntervalVar*>* const array);
1812  void MakeFixedDurationIntervalVarArray(
1813  const std::vector<IntVar*>& start_variables,
1814  const std::vector<int>& durations, const std::string& name,
1815  std::vector<IntervalVar*>* const array);
1816 
1819  void MakeFixedDurationIntervalVarArray(
1820  const std::vector<IntVar*>& start_variables,
1821  const std::vector<int64>& durations,
1822  const std::vector<IntVar*>& performed_variables, const std::string& name,
1823  std::vector<IntervalVar*>* const array);
1824 
1827  void MakeFixedDurationIntervalVarArray(
1828  const std::vector<IntVar*>& start_variables,
1829  const std::vector<int>& durations,
1830  const std::vector<IntVar*>& performed_variables, const std::string& name,
1831  std::vector<IntervalVar*>* const array);
1832 
1834  IntervalVar* MakeFixedInterval(int64 start, int64 duration,
1835  const std::string& name);
1836 
1839  IntervalVar* MakeIntervalVar(int64 start_min, int64 start_max,
1840  int64 duration_min, int64 duration_max,
1841  int64 end_min, int64 end_max, bool optional,
1842  const std::string& name);
1843 
1846  void MakeIntervalVarArray(int count, int64 start_min, int64 start_max,
1847  int64 duration_min, int64 duration_max,
1848  int64 end_min, int64 end_max, bool optional,
1849  const std::string& name,
1850  std::vector<IntervalVar*>* const array);
1851 
1854  IntervalVar* MakeMirrorInterval(IntervalVar* const interval_var);
1855 
1860  IntervalVar* MakeFixedDurationStartSyncedOnStartIntervalVar(
1861  IntervalVar* const interval_var, int64 duration, int64 offset);
1862 
1867  IntervalVar* MakeFixedDurationStartSyncedOnEndIntervalVar(
1868  IntervalVar* const interval_var, int64 duration, int64 offset);
1869 
1874  IntervalVar* MakeFixedDurationEndSyncedOnStartIntervalVar(
1875  IntervalVar* const interval_var, int64 duration, int64 offset);
1876 
1881  IntervalVar* MakeFixedDurationEndSyncedOnEndIntervalVar(
1882  IntervalVar* const interval_var, int64 duration, int64 offset);
1883 
1901  IntervalVar* MakeIntervalRelaxedMin(IntervalVar* const interval_var);
1902 
1920  IntervalVar* MakeIntervalRelaxedMax(IntervalVar* const interval_var);
1921 
1924  Constraint* MakeIntervalVarRelation(IntervalVar* const t,
1925  UnaryIntervalRelation r, int64 d);
1926 
1928  Constraint* MakeIntervalVarRelation(IntervalVar* const t1,
1929  BinaryIntervalRelation r,
1930  IntervalVar* const t2);
1931 
1936  Constraint* MakeIntervalVarRelationWithDelay(IntervalVar* const t1,
1937  BinaryIntervalRelation r,
1938  IntervalVar* const t2,
1939  int64 delay);
1940 
1944  Constraint* MakeTemporalDisjunction(IntervalVar* const t1,
1945  IntervalVar* const t2, IntVar* const alt);
1946 
1949  Constraint* MakeTemporalDisjunction(IntervalVar* const t1,
1950  IntervalVar* const t2);
1951 
1954  DisjunctiveConstraint* MakeDisjunctiveConstraint(
1955  const std::vector<IntervalVar*>& intervals, const std::string& name);
1956 
1960  DisjunctiveConstraint* MakeStrictDisjunctiveConstraint(
1961  const std::vector<IntervalVar*>& intervals, const std::string& name);
1962 
1972  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
1973  const std::vector<int64>& demands, int64 capacity,
1974  const std::string& name);
1975 
1985  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
1986  const std::vector<int>& demands, int64 capacity,
1987  const std::string& name);
1988 
1998  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
1999  const std::vector<int64>& demands,
2000  IntVar* const capacity, const std::string& name);
2001 
2011  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2012  const std::vector<int>& demands,
2013  IntVar* const capacity, const std::string& name);
2014 
2022  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2023  const std::vector<IntVar*>& demands,
2024  int64 capacity, const std::string& name);
2025 
2033  Constraint* MakeCumulative(const std::vector<IntervalVar*>& intervals,
2034  const std::vector<IntVar*>& demands,
2035  IntVar* const capacity, const std::string& name);
2036 
2042  Constraint* MakeCover(const std::vector<IntervalVar*>& vars,
2043  IntervalVar* const target_var);
2044 
2046  Constraint* MakeEquality(IntervalVar* const var1, IntervalVar* const var2);
2047 
2049  Assignment* MakeAssignment();
2050 
2052  Assignment* MakeAssignment(const Assignment* const a);
2053 
2055  SolutionCollector* MakeFirstSolutionCollector(
2056  const Assignment* const assignment);
2059  SolutionCollector* MakeFirstSolutionCollector();
2060 
2062  SolutionCollector* MakeLastSolutionCollector(
2063  const Assignment* const assignment);
2066  SolutionCollector* MakeLastSolutionCollector();
2067 
2072  SolutionCollector* MakeBestValueSolutionCollector(
2073  const Assignment* const assignment, bool maximize);
2079  SolutionCollector* MakeBestValueSolutionCollector(bool maximize);
2080 
2084  SolutionCollector* MakeNBestValueSolutionCollector(
2085  const Assignment* const assignment, int solution_count, bool maximize);
2086  SolutionCollector* MakeNBestValueSolutionCollector(int solution_count,
2087  bool maximize);
2088 
2090  SolutionCollector* MakeAllSolutionCollector(
2091  const Assignment* const assignment);
2094  SolutionCollector* MakeAllSolutionCollector();
2095 
2097  OptimizeVar* MakeMinimize(IntVar* const v, int64 step);
2098 
2100  OptimizeVar* MakeMaximize(IntVar* const v, int64 step);
2101 
2103  OptimizeVar* MakeOptimize(bool maximize, IntVar* const v, int64 step);
2104 
2107  OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2108  const std::vector<int64>& weights,
2109  int64 step);
2110 
2113  OptimizeVar* MakeWeightedMinimize(const std::vector<IntVar*>& sub_objectives,
2114  const std::vector<int>& weights,
2115  int64 step);
2116 
2118  OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2119  const std::vector<int64>& weights,
2120  int64 step);
2121 
2123  OptimizeVar* MakeWeightedMaximize(const std::vector<IntVar*>& sub_objectives,
2124  const std::vector<int>& weights,
2125  int64 step);
2126 
2128  OptimizeVar* MakeWeightedOptimize(bool maximize,
2129  const std::vector<IntVar*>& sub_objectives,
2130  const std::vector<int64>& weights,
2131  int64 step);
2132 
2134  OptimizeVar* MakeWeightedOptimize(bool maximize,
2135  const std::vector<IntVar*>& sub_objectives,
2136  const std::vector<int>& weights,
2137  int64 step);
2138 
2140 
2156 
2157  SearchMonitor* MakeTabuSearch(bool maximize, IntVar* const v, int64 step,
2158  const std::vector<IntVar*>& vars,
2159  int64 keep_tenure, int64 forbid_tenure,
2160  double tabu_factor);
2161 
2164  SearchMonitor* MakeGenericTabuSearch(bool maximize, IntVar* const v,
2165  int64 step,
2166  const std::vector<IntVar*>& tabu_vars,
2167  int64 forbid_tenure);
2168 
2170  // TODO(user): document behavior
2171  SearchMonitor* MakeSimulatedAnnealing(bool maximize, IntVar* const v,
2172  int64 step, int64 initial_temperature);
2173 
2176  SearchMonitor* MakeGuidedLocalSearch(bool maximize, IntVar* const objective,
2177  IndexEvaluator2 objective_function,
2178  int64 step,
2179  const std::vector<IntVar*>& vars,
2180  double penalty_factor);
2181  SearchMonitor* MakeGuidedLocalSearch(
2182  bool maximize, IntVar* const objective,
2183  IndexEvaluator3 objective_function, int64 step,
2184  const std::vector<IntVar*>& vars,
2185  const std::vector<IntVar*>& secondary_vars, double penalty_factor);
2186 
2190  SearchMonitor* MakeLubyRestart(int scale_factor);
2191 
2194  SearchMonitor* MakeConstantRestart(int frequency);
2195 
2198  RegularLimit* MakeTimeLimit(int64 time_in_ms);
2199 
2202  RegularLimit* MakeBranchesLimit(int64 branches);
2203 
2206  RegularLimit* MakeFailuresLimit(int64 failures);
2207 
2210  RegularLimit* MakeSolutionsLimit(int64 solutions);
2211 
2214  RegularLimit* MakeLimit(int64 time, int64 branches, int64 failures,
2215  int64 solutions);
2218  RegularLimit* MakeLimit(int64 time, int64 branches, int64 failures,
2219  int64 solutions, bool smart_time_check);
2222  RegularLimit* MakeLimit(int64 time, int64 branches, int64 failures,
2223  int64 solutions, bool smart_time_check,
2224  bool cumulative);
2226  RegularLimit* MakeLimit(const RegularLimitParameters& proto);
2227 
2229  RegularLimitParameters MakeDefaultRegularLimitParameters() const;
2230 
2234  SearchLimit* MakeLimit(SearchLimit* const limit_1,
2235  SearchLimit* const limit_2);
2236 
2239  SearchLimit* MakeCustomLimit(std::function<bool()> limiter);
2240 
2241  // TODO(user): DEPRECATE API of MakeSearchLog(.., IntVar* var,..).
2242 
2245  SearchMonitor* MakeSearchLog(int branch_period);
2246 
2248  SearchMonitor* MakeSearchLog(int branch_period, IntVar* const var);
2249 
2252  SearchMonitor* MakeSearchLog(int branch_period,
2253  std::function<std::string()> display_callback);
2254 
2257  SearchMonitor* MakeSearchLog(int branch_period, IntVar* var,
2258  std::function<std::string()> display_callback);
2259 
2262  SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* const opt_var);
2263 
2266  SearchMonitor* MakeSearchLog(int branch_period, OptimizeVar* const opt_var,
2267  std::function<std::string()> display_callback);
2268 
2270  struct SearchLogParameters {
2273  int branch_period = 1;
2276  OptimizeVar* objective = nullptr;
2277  IntVar* variable = nullptr;
2281  double scaling_factor = 1.0;
2282  double offset = 0;
2285  std::function<std::string()> display_callback;
2286  };
2287  SearchMonitor* MakeSearchLog(SearchLogParameters parameters);
2288 
2291  SearchMonitor* MakeSearchTrace(const std::string& prefix);
2292 
2294  SearchMonitor* MakeEnterSearchCallback(std::function<void()> callback);
2295  SearchMonitor* MakeExitSearchCallback(std::function<void()> callback);
2296  SearchMonitor* MakeAtSolutionCallback(std::function<void()> callback);
2297 
2299  ModelVisitor* MakePrintModelVisitor();
2301  ModelVisitor* MakeStatisticsModelVisitor();
2302 #if !defined(SWIG)
2303  ModelVisitor* MakeVariableDegreeVisitor(
2305  absl::flat_hash_map<const IntVar*, int>* const map);
2306 #endif // !defined(SWIG)
2307 
2309  SearchMonitor* MakeSymmetryManager(
2310  const std::vector<SymmetryBreaker*>& visitors);
2311  SearchMonitor* MakeSymmetryManager(SymmetryBreaker* const v1);
2312  SearchMonitor* MakeSymmetryManager(SymmetryBreaker* const v1,
2313  SymmetryBreaker* const v2);
2314  SearchMonitor* MakeSymmetryManager(SymmetryBreaker* const v1,
2315  SymmetryBreaker* const v2,
2316  SymmetryBreaker* const v3);
2317  SearchMonitor* MakeSymmetryManager(SymmetryBreaker* const v1,
2318  SymmetryBreaker* const v2,
2319  SymmetryBreaker* const v3,
2320  SymmetryBreaker* const v4);
2321 
2323  Decision* MakeAssignVariableValue(IntVar* const var, int64 val);
2324  Decision* MakeVariableLessOrEqualValue(IntVar* const var, int64 value);
2325  Decision* MakeVariableGreaterOrEqualValue(IntVar* const var, int64 value);
2326  Decision* MakeSplitVariableDomain(IntVar* const var, int64 val,
2327  bool start_with_lower_half);
2328  Decision* MakeAssignVariableValueOrFail(IntVar* const var, int64 value);
2329  Decision* MakeAssignVariableValueOrDoNothing(IntVar* const var, int64 value);
2330  Decision* MakeAssignVariablesValues(const std::vector<IntVar*>& vars,
2331  const std::vector<int64>& values);
2332  Decision* MakeFailDecision();
2333  Decision* MakeDecision(Action apply, Action refute);
2334 
2343  DecisionBuilder* Compose(DecisionBuilder* const db1,
2344  DecisionBuilder* const db2);
2345  DecisionBuilder* Compose(DecisionBuilder* const db1,
2346  DecisionBuilder* const db2,
2347  DecisionBuilder* const db3);
2348  DecisionBuilder* Compose(DecisionBuilder* const db1,
2349  DecisionBuilder* const db2,
2350  DecisionBuilder* const db3,
2351  DecisionBuilder* const db4);
2352  DecisionBuilder* Compose(const std::vector<DecisionBuilder*>& dbs);
2353 
2365  // TODO(user): The search tree can be balanced by using binary
2370  DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2);
2371  DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2,
2372  DecisionBuilder* const db3);
2373  DecisionBuilder* Try(DecisionBuilder* const db1, DecisionBuilder* const db2,
2374  DecisionBuilder* const db3, DecisionBuilder* const db4);
2375  DecisionBuilder* Try(const std::vector<DecisionBuilder*>& dbs);
2376 
2378  // TODO(user): name each of them differently, and document them (and do that
2380  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2381  IntVarStrategy var_str, IntValueStrategy val_str);
2382  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2383  IndexEvaluator1 var_evaluator,
2384  IntValueStrategy val_str);
2385 
2386  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2387  IntVarStrategy var_str,
2388  IndexEvaluator2 value_evaluator);
2389 
2392  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2393  IntVarStrategy var_str,
2394  VariableValueComparator var_val1_val2_comparator);
2395 
2396  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2397  IndexEvaluator1 var_evaluator,
2398  IndexEvaluator2 value_evaluator);
2399 
2400  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2401  IntVarStrategy var_str,
2402  IndexEvaluator2 value_evaluator,
2403  IndexEvaluator1 tie_breaker);
2404 
2405  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2406  IndexEvaluator1 var_evaluator,
2407  IndexEvaluator2 value_evaluator,
2408  IndexEvaluator1 tie_breaker);
2409 
2410  DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars);
2411  DecisionBuilder* MakeDefaultPhase(const std::vector<IntVar*>& vars,
2412  const DefaultPhaseParameters& parameters);
2413 
2415  DecisionBuilder* MakePhase(IntVar* const v0, IntVarStrategy var_str,
2416  IntValueStrategy val_str);
2417  DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2418  IntVarStrategy var_str, IntValueStrategy val_str);
2419  DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2420  IntVar* const v2, IntVarStrategy var_str,
2421  IntValueStrategy val_str);
2422  DecisionBuilder* MakePhase(IntVar* const v0, IntVar* const v1,
2423  IntVar* const v2, IntVar* const v3,
2424  IntVarStrategy var_str, IntValueStrategy val_str);
2425 
2431  Decision* MakeScheduleOrPostpone(IntervalVar* const var, int64 est,
2432  int64* const marker);
2433 
2439  Decision* MakeScheduleOrExpedite(IntervalVar* const var, int64 est,
2440  int64* const marker);
2441 
2444  Decision* MakeRankFirstInterval(SequenceVar* const sequence, int index);
2445 
2448  Decision* MakeRankLastInterval(SequenceVar* const sequence, int index);
2449 
2455  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2456  IndexEvaluator2 eval, EvaluatorStrategy str);
2457 
2465  DecisionBuilder* MakePhase(const std::vector<IntVar*>& vars,
2466  IndexEvaluator2 eval, IndexEvaluator1 tie_breaker,
2467  EvaluatorStrategy str);
2468 
2470  DecisionBuilder* MakePhase(const std::vector<IntervalVar*>& intervals,
2471  IntervalStrategy str);
2472 
2473  DecisionBuilder* MakePhase(const std::vector<SequenceVar*>& sequences,
2474  SequenceStrategy str);
2475 
2478  DecisionBuilder* MakeDecisionBuilderFromAssignment(
2479  Assignment* const assignment, DecisionBuilder* const db,
2480  const std::vector<IntVar*>& vars);
2481 
2484  DecisionBuilder* MakeConstraintAdder(Constraint* const ct);
2485 
2490  DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db);
2491  DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2492  SearchMonitor* const monitor1);
2493  DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2494  SearchMonitor* const monitor1,
2495  SearchMonitor* const monitor2);
2496  DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2497  SearchMonitor* const monitor1,
2498  SearchMonitor* const monitor2,
2499  SearchMonitor* const monitor3);
2500  DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2501  SearchMonitor* const monitor1,
2502  SearchMonitor* const monitor2,
2503  SearchMonitor* const monitor3,
2504  SearchMonitor* const monitor4);
2505  DecisionBuilder* MakeSolveOnce(DecisionBuilder* const db,
2506  const std::vector<SearchMonitor*>& monitors);
2507 
2515  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2516  Assignment* const solution, bool maximize,
2517  int64 step);
2518  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2519  Assignment* const solution, bool maximize,
2520  int64 step,
2521  SearchMonitor* const monitor1);
2522  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2523  Assignment* const solution, bool maximize,
2524  int64 step, SearchMonitor* const monitor1,
2525  SearchMonitor* const monitor2);
2526  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2527  Assignment* const solution, bool maximize,
2528  int64 step, SearchMonitor* const monitor1,
2529  SearchMonitor* const monitor2,
2530  SearchMonitor* const monitor3);
2531  DecisionBuilder* MakeNestedOptimize(DecisionBuilder* const db,
2532  Assignment* const solution, bool maximize,
2533  int64 step, SearchMonitor* const monitor1,
2534  SearchMonitor* const monitor2,
2535  SearchMonitor* const monitor3,
2536  SearchMonitor* const monitor4);
2537  DecisionBuilder* MakeNestedOptimize(
2538  DecisionBuilder* const db, Assignment* const solution, bool maximize,
2539  int64 step, const std::vector<SearchMonitor*>& monitors);
2540 
2543  DecisionBuilder* MakeRestoreAssignment(Assignment* assignment);
2544 
2547  DecisionBuilder* MakeStoreAssignment(Assignment* assignment);
2548 
2550  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2551  LocalSearchOperators op);
2552  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2553  const std::vector<IntVar*>& secondary_vars,
2554  LocalSearchOperators op);
2555  // TODO(user): Make the callback an IndexEvaluator2 when there are no
2556  // secondary variables.
2557  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2558  IndexEvaluator3 evaluator,
2559  EvaluatorLocalSearchOperators op);
2560  LocalSearchOperator* MakeOperator(const std::vector<IntVar*>& vars,
2561  const std::vector<IntVar*>& secondary_vars,
2562  IndexEvaluator3 evaluator,
2563  EvaluatorLocalSearchOperators op);
2564 
2572  LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2573  int number_of_variables);
2574  LocalSearchOperator* MakeRandomLnsOperator(const std::vector<IntVar*>& vars,
2575  int number_of_variables,
2576  int32 seed);
2577 
2583  LocalSearchOperator* MakeMoveTowardTargetOperator(const Assignment& target);
2584 
2591  LocalSearchOperator* MakeMoveTowardTargetOperator(
2592  const std::vector<IntVar*>& variables,
2593  const std::vector<int64>& target_values);
2594 
2625  LocalSearchOperator* ConcatenateOperators(
2626  const std::vector<LocalSearchOperator*>& ops);
2627  LocalSearchOperator* ConcatenateOperators(
2628  const std::vector<LocalSearchOperator*>& ops, bool restart);
2629  LocalSearchOperator* ConcatenateOperators(
2630  const std::vector<LocalSearchOperator*>& ops,
2631  std::function<int64(int, int)> evaluator);
2634  LocalSearchOperator* RandomConcatenateOperators(
2635  const std::vector<LocalSearchOperator*>& ops);
2636 
2640  LocalSearchOperator* RandomConcatenateOperators(
2641  const std::vector<LocalSearchOperator*>& ops, int32 seed);
2642 
2648  LocalSearchOperator* MakeNeighborhoodLimit(LocalSearchOperator* const op,
2649  int64 limit);
2650 
2675  // TODO(user): Make a variant which runs a local search after each
2676  // solution found in a DFS.
2677 
2678  DecisionBuilder* MakeLocalSearchPhase(
2679  Assignment* const assignment,
2680  LocalSearchPhaseParameters* const parameters);
2681  DecisionBuilder* MakeLocalSearchPhase(
2682  const std::vector<IntVar*>& vars, DecisionBuilder* const first_solution,
2683  LocalSearchPhaseParameters* const parameters);
2685  DecisionBuilder* MakeLocalSearchPhase(
2686  const std::vector<IntVar*>& vars, DecisionBuilder* const first_solution,
2687  DecisionBuilder* const first_solution_sub_decision_builder,
2688  LocalSearchPhaseParameters* const parameters);
2689  DecisionBuilder* MakeLocalSearchPhase(
2690  const std::vector<SequenceVar*>& vars,
2691  DecisionBuilder* const first_solution,
2692  LocalSearchPhaseParameters* const parameters);
2693 
2695  SolutionPool* MakeDefaultSolutionPool();
2696 
2698  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2699  IntVar* objective, LocalSearchOperator* const ls_operator,
2700  DecisionBuilder* const sub_decision_builder);
2701  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2702  IntVar* objective, LocalSearchOperator* const ls_operator,
2703  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit);
2704  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2705  IntVar* objective, LocalSearchOperator* const ls_operator,
2706  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
2707  const std::vector<LocalSearchFilter*>& filters);
2708 
2709  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2710  IntVar* objective, SolutionPool* const pool,
2711  LocalSearchOperator* const ls_operator,
2712  DecisionBuilder* const sub_decision_builder);
2713  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2714  IntVar* objective, SolutionPool* const pool,
2715  LocalSearchOperator* const ls_operator,
2716  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit);
2717  LocalSearchPhaseParameters* MakeLocalSearchPhaseParameters(
2718  IntVar* objective, SolutionPool* const pool,
2719  LocalSearchOperator* const ls_operator,
2720  DecisionBuilder* const sub_decision_builder, RegularLimit* const limit,
2721  const std::vector<LocalSearchFilter*>& filters);
2722 
2724  LocalSearchFilter* MakeAcceptFilter();
2725  LocalSearchFilter* MakeRejectFilter();
2726  LocalSearchFilter* MakeVariableDomainFilter();
2727  IntVarLocalSearchFilter* MakeSumObjectiveFilter(
2728  const std::vector<IntVar*>& vars, IndexEvaluator2 values,
2729  Solver::LocalSearchFilterBound filter_enum);
2730  IntVarLocalSearchFilter* MakeSumObjectiveFilter(
2731  const std::vector<IntVar*>& vars,
2732  const std::vector<IntVar*>& secondary_vars, IndexEvaluator3 values,
2733  Solver::LocalSearchFilterBound filter_enum);
2734 
2737  void TopPeriodicCheck();
2741  int TopProgressPercent();
2742 
2746  void PushState();
2747  void PopState();
2748 
2751  int SearchDepth() const;
2752 
2755  int SearchLeftDepth() const;
2756 
2759  int SolveDepth() const;
2760 
2762  void SetBranchSelector(BranchSelector bs);
2763 
2765  DecisionBuilder* MakeApplyBranchSelector(BranchSelector bs);
2766 
2768  template <class T>
2769  void SaveAndSetValue(T* adr, T val) {
2770  if (*adr != val) {
2771  InternalSaveValue(adr);
2772  *adr = val;
2773  }
2774  }
2775 
2777  template <class T>
2778  void SaveAndAdd(T* adr, T val) {
2779  if (val != 0) {
2780  InternalSaveValue(adr);
2781  (*adr) += val;
2782  }
2783  }
2784 
2786  int64 Rand64(int64 size) {
2787  DCHECK_GT(size, 0);
2788  return absl::Uniform<int64>(random_, 0, size);
2789  }
2790 
2792  int32 Rand32(int32 size) {
2793  DCHECK_GT(size, 0);
2794  return absl::Uniform<int32>(random_, 0, size);
2795  }
2796 
2798  void ReSeed(int32 seed) { random_.seed(seed); }
2799 
2803  void ExportProfilingOverview(const std::string& filename);
2804 
2806  // TODO(user): Add a profiling protocol buffer and merge demon and local
2808  std::string LocalSearchProfile() const;
2809 
2813  bool CurrentlyInSolve() const;
2814 
2817  int constraints() const { return constraints_list_.size(); }
2818 
2820  void Accept(ModelVisitor* const visitor) const;
2821 
2822  Decision* balancing_decision() const { return balancing_decision_.get(); }
2823 
2825 #if !defined(SWIG)
2826  void set_fail_intercept(std::function<void()> fail_intercept) {
2827  fail_intercept_ = std::move(fail_intercept);
2828  }
2829 #endif // !defined(SWIG)
2830  void clear_fail_intercept() { fail_intercept_ = nullptr; }
2832  DemonProfiler* demon_profiler() const { return demon_profiler_; }
2833  // TODO(user): Get rid of the following methods once fast local search is
2836  void SetUseFastLocalSearch(bool use_fast_local_search) {
2837  use_fast_local_search_ = use_fast_local_search;
2838  }
2840  bool UseFastLocalSearch() const { return use_fast_local_search_; }
2842  bool HasName(const PropagationBaseObject* object) const;
2844  Demon* RegisterDemon(Demon* const demon);
2846  IntExpr* RegisterIntExpr(IntExpr* const expr);
2848  IntVar* RegisterIntVar(IntVar* const var);
2851  IntervalVar* RegisterIntervalVar(IntervalVar* const var);
2852 
2854  Search* ActiveSearch() const;
2856  ModelCache* Cache() const;
2858  bool InstrumentsDemons() const;
2860  bool IsProfilingEnabled() const;
2862  bool IsLocalSearchProfilingEnabled() const;
2864  bool InstrumentsVariables() const;
2866  bool NameAllVariables() const;
2868  std::string model_name() const;
2870  PropagationMonitor* GetPropagationMonitor() const;
2873  void AddPropagationMonitor(PropagationMonitor* const monitor);
2875  LocalSearchMonitor* GetLocalSearchMonitor() const;
2878  void AddLocalSearchMonitor(LocalSearchMonitor* monitor);
2879  void SetSearchContext(Search* search, const std::string& search_context);
2880  std::string SearchContext() const;
2881  std::string SearchContext(const Search* search) const;
2883  // TODO(user): Investigate if this should be moved to Search.
2884  Assignment* GetOrCreateLocalSearchState();
2886  void ClearLocalSearchState() { local_search_state_.reset(nullptr); }
2887 
2892  std::vector<int64> tmp_vector_;
2893 
2894  friend class BaseIntExpr;
2895  friend class Constraint;
2896  friend class DemonProfiler;
2897  friend class FindOneNeighbor;
2898  friend class IntVar;
2899  friend class PropagationBaseObject;
2900  friend class Queue;
2901  friend class SearchMonitor;
2902  friend class SearchLimit;
2903  friend class RoutingModel;
2904  friend class LocalSearchProfiler;
2905 
2906 #if !defined(SWIG)
2907  friend void InternalSaveBooleanVarValue(Solver* const, IntVar* const);
2908  template <class>
2909  friend class SimpleRevFIFO;
2910  template <class K, class V>
2911  friend class RevImmutableMultiMap;
2912 
2917  bool IsBooleanVar(IntExpr* const expr, IntVar** inner_var,
2918  bool* is_negated) const;
2919 
2924  bool IsProduct(IntExpr* const expr, IntExpr** inner_expr, int64* coefficient);
2925 #endif
2926 
2927  IntExpr* CastExpression(const IntVar* const var) const;
2930 
2932  void FinishCurrentSearch();
2933  void RestartCurrentSearch();
2934 
2937  void ShouldFail() { should_fail_ = true; }
2938  void CheckFail() {
2939  if (!should_fail_) return;
2940  should_fail_ = false;
2941  Fail();
2942  }
2943 
2944  private:
2945  void Init();
2946  void PushState(MarkerType t, const StateInfo& info);
2947  MarkerType PopState(StateInfo* info);
2948  void PushSentinel(int magic_code);
2949  void BacktrackToSentinel(int magic_code);
2950  void ProcessConstraints();
2951  bool BacktrackOneLevel(Decision** fail_decision);
2952  void JumpToSentinelWhenNested();
2953  void JumpToSentinel();
2954  void check_alloc_state();
2955  void FreezeQueue();
2956  void EnqueueVar(Demon* const d);
2957  void EnqueueDelayedDemon(Demon* const d);
2958  void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
2959  void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
2960  void UnfreezeQueue();
2961  void reset_action_on_fail();
2962  void set_action_on_fail(Action a);
2963  void set_variable_to_clean_on_fail(IntVar* v);
2964  void IncrementUncheckedSolutionCounter();
2965  bool IsUncheckedSolutionLimitReached();
2966 
2967  void InternalSaveValue(int* valptr);
2968  void InternalSaveValue(int64* valptr);
2969  void InternalSaveValue(uint64* valptr);
2970  void InternalSaveValue(double* valptr);
2971  void InternalSaveValue(bool* valptr);
2972  void InternalSaveValue(void** valptr);
2973  void InternalSaveValue(int64** valptr) {
2974  InternalSaveValue(reinterpret_cast<void**>(valptr));
2975  }
2976 
2977  BaseObject* SafeRevAlloc(BaseObject* ptr);
2978 
2979  int* SafeRevAllocArray(int* ptr);
2980  int64* SafeRevAllocArray(int64* ptr);
2981  uint64* SafeRevAllocArray(uint64* ptr);
2982  double* SafeRevAllocArray(double* ptr);
2983  BaseObject** SafeRevAllocArray(BaseObject** ptr);
2984  IntVar** SafeRevAllocArray(IntVar** ptr);
2985  IntExpr** SafeRevAllocArray(IntExpr** ptr);
2986  Constraint** SafeRevAllocArray(Constraint** ptr);
2989  void* UnsafeRevAllocAux(void* ptr);
2990  template <class T>
2991  T* UnsafeRevAlloc(T* ptr) {
2992  return reinterpret_cast<T*>(
2993  UnsafeRevAllocAux(reinterpret_cast<void*>(ptr)));
2994  }
2995  void** UnsafeRevAllocArrayAux(void** ptr);
2996  template <class T>
2997  T** UnsafeRevAllocArray(T** ptr) {
2998  return reinterpret_cast<T**>(
2999  UnsafeRevAllocArrayAux(reinterpret_cast<void**>(ptr)));
3000  }
3001 
3002  void InitCachedIntConstants();
3003  void InitCachedConstraint();
3004 
3008  Search* TopLevelSearch() const { return searches_.at(1); }
3012  Search* ParentSearch() const {
3013  const size_t search_size = searches_.size();
3014  DCHECK_GT(search_size, 1);
3015  return searches_[search_size - 2];
3016  }
3017 
3019  std::string GetName(const PropagationBaseObject* object);
3020  void SetName(const PropagationBaseObject* object, const std::string& name);
3021 
3024  int GetNewIntVarIndex() { return num_int_vars_++; }
3025 
3027  bool IsADifference(IntExpr* expr, IntExpr** const left,
3028  IntExpr** const right);
3029 
3030  const std::string name_;
3031  const ConstraintSolverParameters parameters_;
3032  absl::flat_hash_map<const PropagationBaseObject*, std::string>
3033  propagation_object_names_;
3034  absl::flat_hash_map<const PropagationBaseObject*, IntegerCastInfo>
3035  cast_information_;
3036  absl::flat_hash_set<const Constraint*> cast_constraints_;
3037  const std::string empty_name_;
3038  std::unique_ptr<Queue> queue_;
3039  std::unique_ptr<Trail> trail_;
3040  std::vector<Constraint*> constraints_list_;
3041  std::vector<Constraint*> additional_constraints_list_;
3042  std::vector<int> additional_constraints_parent_list_;
3043  SolverState state_;
3044  int64 branches_;
3045  int64 fails_;
3046  int64 decisions_;
3047  int64 demon_runs_[kNumPriorities];
3048  int64 neighbors_;
3049  int64 filtered_neighbors_;
3050  int64 accepted_neighbors_;
3051  OptimizationDirection optimization_direction_;
3052  std::unique_ptr<ClockTimer> timer_;
3053  std::vector<Search*> searches_;
3054  std::mt19937 random_;
3055  uint64 fail_stamp_;
3056  std::unique_ptr<Decision> balancing_decision_;
3058  std::function<void()> fail_intercept_;
3060  DemonProfiler* const demon_profiler_;
3062  bool use_fast_local_search_;
3064  LocalSearchProfiler* const local_search_profiler_;
3066  std::unique_ptr<Assignment> local_search_state_;
3067 
3069  enum { MIN_CACHED_INT_CONST = -8, MAX_CACHED_INT_CONST = 8 };
3070  IntVar* cached_constants_[MAX_CACHED_INT_CONST + 1 - MIN_CACHED_INT_CONST];
3071 
3073  Constraint* true_constraint_;
3074  Constraint* false_constraint_;
3075 
3076  std::unique_ptr<Decision> fail_decision_;
3077  int constraint_index_;
3078  int additional_constraint_index_;
3079  int num_int_vars_;
3080 
3081  std::unique_ptr<ModelCache> model_cache_;
3082  std::unique_ptr<PropagationMonitor> propagation_monitor_;
3083  PropagationMonitor* print_trace_;
3084  std::unique_ptr<LocalSearchMonitor> local_search_monitor_;
3085  int anonymous_variable_index_;
3086  bool should_fail_;
3087 
3088  DISALLOW_COPY_AND_ASSIGN(Solver);
3089 };
3090 
3091 std::ostream& operator<<(std::ostream& out, const Solver* const s);
3092 
3096 inline int64 Zero() { return 0; }
3097 
3099 inline int64 One() { return 1; }
3100 
3104 class BaseObject {
3105  public:
3106  BaseObject() {}
3107  virtual ~BaseObject() {}
3108  virtual std::string DebugString() const { return "BaseObject"; }
3109 
3110  private:
3111  DISALLOW_COPY_AND_ASSIGN(BaseObject);
3112 };
3113 
3114 std::ostream& operator<<(std::ostream& out, const BaseObject* o);
3115 
3119 class PropagationBaseObject : public BaseObject {
3120  public:
3121  explicit PropagationBaseObject(Solver* const s) : solver_(s) {}
3122  ~PropagationBaseObject() override {}
3123 
3124  std::string DebugString() const override {
3125  if (name().empty()) {
3126  return "PropagationBaseObject";
3127  } else {
3128  return absl::StrFormat("PropagationBaseObject: %s", name());
3129  }
3130  }
3131  Solver* solver() const { return solver_; }
3132 
3135  void FreezeQueue() { solver_->FreezeQueue(); }
3136 
3139  void UnfreezeQueue() { solver_->UnfreezeQueue(); }
3140 
3144  void EnqueueDelayedDemon(Demon* const d) { solver_->EnqueueDelayedDemon(d); }
3145  void EnqueueVar(Demon* const d) { solver_->EnqueueVar(d); }
3146  void ExecuteAll(const SimpleRevFIFO<Demon*>& demons);
3147  void EnqueueAll(const SimpleRevFIFO<Demon*>& demons);
3148 
3149 #if !defined(SWIG)
3150  // This method sets a callback that will be called if a failure
3151  // happens during the propagation of the queue.
3152  void set_action_on_fail(Solver::Action a) {
3153  solver_->set_action_on_fail(std::move(a));
3154  }
3155 #endif // !defined(SWIG)
3156 
3158  void reset_action_on_fail() { solver_->reset_action_on_fail(); }
3159 
3161  void set_variable_to_clean_on_fail(IntVar* v) {
3162  solver_->set_variable_to_clean_on_fail(v);
3163  }
3164 
3166  virtual std::string name() const;
3167  void set_name(const std::string& name);
3169  bool HasName() const;
3171  virtual std::string BaseName() const;
3172 
3173  private:
3174  Solver* const solver_;
3175  DISALLOW_COPY_AND_ASSIGN(PropagationBaseObject);
3176 };
3177 
3180 class Decision : public BaseObject {
3181  public:
3182  Decision() {}
3183  ~Decision() override {}
3184 
3186  virtual void Apply(Solver* const s) = 0;
3187 
3189  virtual void Refute(Solver* const s) = 0;
3190 
3191  std::string DebugString() const override { return "Decision"; }
3193  virtual void Accept(DecisionVisitor* const visitor) const;
3194 
3195  private:
3196  DISALLOW_COPY_AND_ASSIGN(Decision);
3197 };
3198 
3201 class DecisionVisitor : public BaseObject {
3202  public:
3203  DecisionVisitor() {}
3204  ~DecisionVisitor() override {}
3205  virtual void VisitSetVariableValue(IntVar* const var, int64 value);
3206  virtual void VisitSplitVariableDomain(IntVar* const var, int64 value,
3207  bool start_with_lower_half);
3208  virtual void VisitScheduleOrPostpone(IntervalVar* const var, int64 est);
3209  virtual void VisitScheduleOrExpedite(IntervalVar* const var, int64 est);
3210  virtual void VisitRankFirstInterval(SequenceVar* const sequence, int index);
3211  virtual void VisitRankLastInterval(SequenceVar* const sequence, int index);
3212  virtual void VisitUnknownDecision();
3213 
3214  private:
3215  DISALLOW_COPY_AND_ASSIGN(DecisionVisitor);
3216 };
3217 
3220 class DecisionBuilder : public BaseObject {
3221  public:
3222  DecisionBuilder() {}
3223  ~DecisionBuilder() override {}
3228  virtual Decision* Next(Solver* const s) = 0;
3229  std::string DebugString() const override;
3230 #if !defined(SWIG)
3231  virtual void AppendMonitors(Solver* const solver,
3236  std::vector<SearchMonitor*>* const extras);
3237  virtual void Accept(ModelVisitor* const visitor) const;
3238 #endif
3239 
3240  private:
3241  DISALLOW_COPY_AND_ASSIGN(DecisionBuilder);
3242 };
3243 
3253 class Demon : public BaseObject {
3254  public:
3257  Demon() : stamp_(GG_ULONGLONG(0)) {}
3258  ~Demon() override {}
3259 
3261  virtual void Run(Solver* const s) = 0;
3262 
3266  virtual Solver::DemonPriority priority() const;
3267 
3268  std::string DebugString() const override;
3269 
3272  void inhibit(Solver* const s);
3273 
3275  void desinhibit(Solver* const s);
3276 
3277  private:
3278  friend class Queue;
3279  void set_stamp(int64 stamp) { stamp_ = stamp; }
3280  uint64 stamp() const { return stamp_; }
3281  uint64 stamp_;
3282  DISALLOW_COPY_AND_ASSIGN(Demon);
3283 };
3284 
3286 class ModelVisitor : public BaseObject {
3287  public:
3289  static const char kAbs[];
3290  static const char kAbsEqual[];
3291  static const char kAllDifferent[];
3292  static const char kAllowedAssignments[];
3293  static const char kAtMost[];
3294  static const char kIndexOf[];
3295  static const char kBetween[];
3296  static const char kConditionalExpr[];
3297  static const char kCircuit[];
3298  static const char kConvexPiecewise[];
3299  static const char kCountEqual[];
3300  static const char kCover[];
3301  static const char kCumulative[];
3302  static const char kDeviation[];
3303  static const char kDifference[];
3304  static const char kDisjunctive[];
3305  static const char kDistribute[];
3306  static const char kDivide[];
3307  static const char kDurationExpr[];
3308  static const char kElement[];
3309  static const char kElementEqual[];
3310  static const char kEndExpr[];
3311  static const char kEquality[];
3312  static const char kFalseConstraint[];
3313  static const char kGlobalCardinality[];
3314  static const char kGreater[];
3315  static const char kGreaterOrEqual[];
3316  static const char kIntegerVariable[];
3317  static const char kIntervalBinaryRelation[];
3318  static const char kIntervalDisjunction[];
3319  static const char kIntervalUnaryRelation[];
3320  static const char kIntervalVariable[];
3321  static const char kInversePermutation[];
3322  static const char kIsBetween[];
3323  static const char kIsDifferent[];
3324  static const char kIsEqual[];
3325  static const char kIsGreater[];
3326  static const char kIsGreaterOrEqual[];
3327  static const char kIsLess[];
3328  static const char kIsLessOrEqual[];
3329  static const char kIsMember[];
3330  static const char kLess[];
3331  static const char kLessOrEqual[];
3332  static const char kLexLess[];
3333  static const char kLinkExprVar[];
3334  static const char kMapDomain[];
3335  static const char kMax[];
3336  static const char kMaxEqual[];
3337  static const char kMember[];
3338  static const char kMin[];
3339  static const char kMinEqual[];
3340  static const char kModulo[];
3341  static const char kNoCycle[];
3342  static const char kNonEqual[];
3343  static const char kNotBetween[];
3344  static const char kNotMember[];
3345  static const char kNullIntersect[];
3346  static const char kOpposite[];
3347  static const char kPack[];
3348  static const char kPathCumul[];
3349  static const char kDelayedPathCumul[];
3350  static const char kPerformedExpr[];
3351  static const char kPower[];
3352  static const char kProduct[];
3353  static const char kScalProd[];
3354  static const char kScalProdEqual[];
3355  static const char kScalProdGreaterOrEqual[];
3356  static const char kScalProdLessOrEqual[];
3357  static const char kSemiContinuous[];
3358  static const char kSequenceVariable[];
3359  static const char kSortingConstraint[];
3360  static const char kSquare[];
3361  static const char kStartExpr[];
3362  static const char kSum[];
3363  static const char kSumEqual[];
3364  static const char kSumGreaterOrEqual[];
3365  static const char kSumLessOrEqual[];
3366  static const char kTrace[];
3367  static const char kTransition[];
3368  static const char kTrueConstraint[];
3369  static const char kVarBoundWatcher[];
3370  static const char kVarValueWatcher[];
3371 
3373  static const char kCountAssignedItemsExtension[];
3374  static const char kCountUsedBinsExtension[];
3375  static const char kInt64ToBoolExtension[];
3376  static const char kInt64ToInt64Extension[];
3377  static const char kObjectiveExtension[];
3378  static const char kSearchLimitExtension[];
3379  static const char kUsageEqualVariableExtension[];
3380 
3381  static const char kUsageLessConstantExtension[];
3382  static const char kVariableGroupExtension[];
3383  static const char kVariableUsageLessConstantExtension[];
3384  static const char kWeightedSumOfAssignedEqualVariableExtension[];
3385 
3387  static const char kActiveArgument[];
3388  static const char kAssumePathsArgument[];
3389  static const char kBranchesLimitArgument[];
3390  static const char kCapacityArgument[];
3391  static const char kCardsArgument[];
3392  static const char kCoefficientsArgument[];
3393  static const char kCountArgument[];
3394  static const char kCumulativeArgument[];
3395  static const char kCumulsArgument[];
3396  static const char kDemandsArgument[];
3397  static const char kDurationMaxArgument[];
3398  static const char kDurationMinArgument[];
3399  static const char kEarlyCostArgument[];
3400  static const char kEarlyDateArgument[];
3401  static const char kEndMaxArgument[];
3402  static const char kEndMinArgument[];
3403  static const char kEndsArgument[];
3404  static const char kExpressionArgument[];
3405  static const char kFailuresLimitArgument[];
3406  static const char kFinalStatesArgument[];
3407  static const char kFixedChargeArgument[];
3408  static const char kIndex2Argument[];
3409  static const char kIndexArgument[];
3410  static const char kInitialState[];
3411  static const char kIntervalArgument[];
3412  static const char kIntervalsArgument[];
3413  static const char kLateCostArgument[];
3414  static const char kLateDateArgument[];
3415  static const char kLeftArgument[];
3416  static const char kMaxArgument[];
3417  static const char kMaximizeArgument[];
3418  static const char kMinArgument[];
3419  static const char kModuloArgument[];
3420  static const char kNextsArgument[];
3421  static const char kOptionalArgument[];
3422  static const char kPartialArgument[];
3423  static const char kPositionXArgument[];
3424  static const char kPositionYArgument[];
3425  static const char kRangeArgument[];
3426  static const char kRelationArgument[];
3427  static const char kRightArgument[];
3428  static const char kSequenceArgument[];
3429  static const char kSequencesArgument[];
3430  static const char kSizeArgument[];
3431  static const char kSizeXArgument[];
3432  static const char kSizeYArgument[];
3433  static const char kSmartTimeCheckArgument[];
3434  static const char kSolutionLimitArgument[];
3435  static const char kStartMaxArgument[];
3436  static const char kStartMinArgument[];
3437  static const char kStartsArgument[];
3438  static const char kStepArgument[];
3439  static const char kTargetArgument[];
3440  static const char kTimeLimitArgument[];
3441  static const char kTransitsArgument[];
3442  static const char kTuplesArgument[];
3443  static const char kValueArgument[];
3444  static const char kValuesArgument[];
3445  static const char kVariableArgument[];
3446  static const char kVarsArgument[];
3447  static const char kEvaluatorArgument[];
3448 
3450  static const char kMirrorOperation[];
3451  static const char kRelaxedMaxOperation[];
3452  static const char kRelaxedMinOperation[];
3453  static const char kSumOperation[];
3454  static const char kDifferenceOperation[];
3455  static const char kProductOperation[];
3456  static const char kStartSyncOnStartOperation[];
3457  static const char kStartSyncOnEndOperation[];
3458  static const char kTraceOperation[];
3459 
3460  ~ModelVisitor() override;
3461 
3463 
3465  virtual void BeginVisitModel(const std::string& type_name);
3466  virtual void EndVisitModel(const std::string& type_name);
3467  virtual void BeginVisitConstraint(const std::string& type_name,
3468  const Constraint* const constraint);
3469  virtual void EndVisitConstraint(const std::string& type_name,
3470  const Constraint* const constraint);
3471  virtual void BeginVisitExtension(const std::string& type);
3472  virtual void EndVisitExtension(const std::string& type);
3473  virtual void BeginVisitIntegerExpression(const std::string& type_name,
3474  const IntExpr* const expr);
3475  virtual void EndVisitIntegerExpression(const std::string& type_name,
3476  const IntExpr* const expr);
3477  virtual void VisitIntegerVariable(const IntVar* const variable,
3478  IntExpr* const delegate);
3479  virtual void VisitIntegerVariable(const IntVar* const variable,
3480  const std::string& operation, int64 value,
3481  IntVar* const delegate);
3482  virtual void VisitIntervalVariable(const IntervalVar* const variable,
3483  const std::string& operation, int64 value,
3484  IntervalVar* const delegate);
3485  virtual void VisitSequenceVariable(const SequenceVar* const variable);
3486 
3488  virtual void VisitIntegerArgument(const std::string& arg_name, int64 value);
3489  virtual void VisitIntegerArrayArgument(const std::string& arg_name,
3490  const std::vector<int64>& values);
3491  virtual void VisitIntegerMatrixArgument(const std::string& arg_name,
3492  const IntTupleSet& tuples);
3493 
3495  virtual void VisitIntegerExpressionArgument(const std::string& arg_name,
3496  IntExpr* const argument);
3497 
3498  virtual void VisitIntegerVariableArrayArgument(
3499  const std::string& arg_name, const std::vector<IntVar*>& arguments);
3500 
3502  virtual void VisitIntervalArgument(const std::string& arg_name,
3503  IntervalVar* const argument);
3504 
3505  virtual void VisitIntervalArrayArgument(
3506  const std::string& arg_name, const std::vector<IntervalVar*>& arguments);
3508  virtual void VisitSequenceArgument(const std::string& arg_name,
3509  SequenceVar* const argument);
3510 
3511  virtual void VisitSequenceArrayArgument(
3512  const std::string& arg_name, const std::vector<SequenceVar*>& arguments);
3513 #if !defined(SWIG)
3514  virtual void VisitIntegerVariableEvaluatorArgument(
3516  const std::string& arg_name, const Solver::Int64ToIntVar& arguments);
3517 
3520  void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64 index_min,
3521  int64 index_max);
3522  void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1& eval,
3523  int64 index_min, int64 index_max);
3525  void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1& eval,
3526  const std::string& arg_name, int64 index_max);
3527 #endif // #if !defined(SWIG)
3528 };
3529 
3536 class Constraint : public PropagationBaseObject {
3537  public:
3538  explicit Constraint(Solver* const solver) : PropagationBaseObject(solver) {}
3539  ~Constraint() override {}
3540 
3543  virtual void Post() = 0;
3544 
3547  virtual void InitialPropagate() = 0;
3548  std::string DebugString() const override;
3549 
3552  void PostAndPropagate();
3553 
3555  virtual void Accept(ModelVisitor* const visitor) const;
3556 
3558  bool IsCastConstraint() const;
3559 
3563  virtual IntVar* Var();
3564 
3565  private:
3566  DISALLOW_COPY_AND_ASSIGN(Constraint);
3567 };
3568 
3572 class CastConstraint : public Constraint {
3573  public:
3574  CastConstraint(Solver* const solver, IntVar* const target_var)
3575  : Constraint(solver), target_var_(target_var) {
3576  CHECK(target_var != nullptr);
3577  }
3578  ~CastConstraint() override {}
3579 
3580  IntVar* target_var() const { return target_var_; }
3581 
3582  protected:
3583  IntVar* const target_var_;
3584 };
3585 
3587 class SearchMonitor : public BaseObject {
3588  public:
3589  static const int kNoProgress = -1;
3590 
3591  explicit SearchMonitor(Solver* const s) : solver_(s) {}
3592  ~SearchMonitor() override {}
3594  virtual void EnterSearch();
3595 
3597  virtual void RestartSearch();
3598 
3600  virtual void ExitSearch();
3601 
3603  virtual void BeginNextDecision(DecisionBuilder* const b);
3604 
3606  virtual void EndNextDecision(DecisionBuilder* const b, Decision* const d);
3607 
3609  virtual void ApplyDecision(Decision* const d);
3610 
3612  virtual void RefuteDecision(Decision* const d);
3613 
3616  virtual void AfterDecision(Decision* const d, bool apply);
3617 
3619  virtual void BeginFail();
3620 
3622  virtual void EndFail();
3623 
3625  virtual void BeginInitialPropagation();
3626 
3628  virtual void EndInitialPropagation();
3629 
3633  virtual bool AcceptSolution();
3634 
3638  virtual bool AtSolution();
3639 
3641  virtual void NoMoreSolutions();
3642 
3645  virtual bool LocalOptimum();
3646 
3648  virtual bool AcceptDelta(Assignment* delta, Assignment* deltadelta);
3649 
3651  virtual void AcceptNeighbor();
3652 
3654  virtual void AcceptUncheckedNeighbor();
3655 
3658  virtual bool IsUncheckedSolutionLimitReached() { return false; }
3659 
3660  Solver* solver() const { return solver_; }
3661 
3663  virtual void PeriodicCheck();
3664 
3667  virtual int ProgressPercent() { return kNoProgress; }
3668 
3670  virtual void Accept(ModelVisitor* const visitor) const;
3671 
3674  virtual void Install();
3675 
3676  private:
3677  Solver* const solver_;
3678  DISALLOW_COPY_AND_ASSIGN(SearchMonitor);
3679 };
3680 
3686 template <class T>
3687 class Rev {
3688  public:
3689  explicit Rev(const T& val) : stamp_(0), value_(val) {}
3690 
3691  const T& Value() const { return value_; }
3692 
3693  void SetValue(Solver* const s, const T& val) {
3694  if (val != value_) {
3695  if (stamp_ < s->stamp()) {
3696  s->SaveValue(&value_);
3697  stamp_ = s->stamp();
3698  }
3699  value_ = val;
3700  }
3701  }
3702 
3703  private:
3704  uint64 stamp_;
3705  T value_;
3706 };
3707 
3709 template <class T>
3710 class NumericalRev : public Rev<T> {
3711  public:
3712  explicit NumericalRev(const T& val) : Rev<T>(val) {}
3713 
3714  void Add(Solver* const s, const T& to_add) {
3715  this->SetValue(s, this->Value() + to_add);
3716  }
3717 
3718  void Incr(Solver* const s) { Add(s, 1); }
3719 
3720  void Decr(Solver* const s) { Add(s, -1); }
3721 };
3722 
3728 template <class T>
3729 class RevArray {
3730  public:
3731  RevArray(int size, const T& val)
3732  : stamps_(new uint64[size]), values_(new T[size]), size_(size) {
3733  for (int i = 0; i < size; ++i) {
3734  stamps_[i] = 0;
3735  values_[i] = val;
3736  }
3737  }
3738 
3739  ~RevArray() {}
3740 
3741  int64 size() const { return size_; }
3742 
3743  const T& Value(int index) const { return values_[index]; }
3744 
3745 #if !defined(SWIG)
3746  const T& operator[](int index) const { return values_[index]; }
3747 #endif
3748 
3749  void SetValue(Solver* const s, int index, const T& val) {
3750  DCHECK_LT(index, size_);
3751  if (val != values_[index]) {
3752  if (stamps_[index] < s->stamp()) {
3753  s->SaveValue(&values_[index]);
3754  stamps_[index] = s->stamp();
3755  }
3756  values_[index] = val;
3757  }
3758  }
3759 
3760  private:
3761  std::unique_ptr<uint64[]> stamps_;
3762  std::unique_ptr<T[]> values_;
3763  const int size_;
3764 };
3765 
3767 template <class T>
3768 class NumericalRevArray : public RevArray<T> {
3769  public:
3770  NumericalRevArray(int size, const T& val) : RevArray<T>(size, val) {}
3771 
3772  void Add(Solver* const s, int index, const T& to_add) {
3773  this->SetValue(s, index, this->Value(index) + to_add);
3774  }
3775 
3776  void Incr(Solver* const s, int index) { Add(s, index, 1); }
3777 
3778  void Decr(Solver* const s, int index) { Add(s, index, -1); }
3779 };
3780 
3788 class IntExpr : public PropagationBaseObject {
3789  public:
3790  explicit IntExpr(Solver* const s) : PropagationBaseObject(s) {}
3791  ~IntExpr() override {}
3792 
3793  virtual int64 Min() const = 0;
3794  virtual void SetMin(int64 m) = 0;
3795  virtual int64 Max() const = 0;
3796  virtual void SetMax(int64 m) = 0;
3797 
3800  virtual void Range(int64* l, int64* u) {
3801  *l = Min();
3802  *u = Max();
3803  }
3805  virtual void SetRange(int64 l, int64 u) {
3806  SetMin(l);
3807  SetMax(u);
3808  }
3809 
3811  virtual void SetValue(int64 v) { SetRange(v, v); }
3812 
3814  virtual bool Bound() const { return (Min() == Max()); }
3815 
3817  virtual bool IsVar() const { return false; }
3818 
3820  virtual IntVar* Var() = 0;
3821 
3826  IntVar* VarWithName(const std::string& name);
3827 
3829  virtual void WhenRange(Demon* d) = 0;
3831  void WhenRange(Solver::Closure closure) {
3832  WhenRange(solver()->MakeClosureDemon(std::move(closure)));
3833  }
3834 
3835 #if !defined(SWIG)
3836  void WhenRange(Solver::Action action) {
3838  WhenRange(solver()->MakeActionDemon(std::move(action)));
3839  }
3840 #endif // SWIG
3841 
3843  virtual void Accept(ModelVisitor* const visitor) const;
3844 
3845  private:
3846  DISALLOW_COPY_AND_ASSIGN(IntExpr);
3847 };
3848 
3856 
3859 
3865 
3866 class IntVarIterator : public BaseObject {
3867  public:
3868  ~IntVarIterator() override {}
3869 
3871  virtual void Init() = 0;
3872 
3874  virtual bool Ok() const = 0;
3875 
3877  virtual int64 Value() const = 0;
3878 
3880  virtual void Next() = 0;
3881 
3883  std::string DebugString() const override { return "IntVar::Iterator"; }
3884 };
3885 
3886 #ifndef SWIG
3887 class InitAndGetValues {
3894  public:
3895  explicit InitAndGetValues(IntVarIterator* it)
3896  : it_(it), begin_was_called_(false) {
3897  it_->Init();
3898  }
3899  struct Iterator;
3900  Iterator begin() {
3901  if (DEBUG_MODE) {
3902  DCHECK(!begin_was_called_);
3903  begin_was_called_ = true;
3904  }
3905  return Iterator::Begin(it_);
3906  }
3907  Iterator end() { return Iterator::End(it_); }
3908 
3909  struct Iterator {
3911  static Iterator Begin(IntVarIterator* it) {
3912  return Iterator(it, /*is_end=*/false);
3913  }
3914  static Iterator End(IntVarIterator* it) {
3915  return Iterator(it, /*is_end=*/true);
3916  }
3917 
3918  int64 operator*() const {
3919  DCHECK(it_->Ok());
3920  return it_->Value();
3921  }
3922  Iterator& operator++() {
3923  DCHECK(it_->Ok());
3924  it_->Next();
3925  return *this;
3926  }
3927  bool operator!=(const Iterator& other) const {
3928  DCHECK(other.it_ == it_);
3929  DCHECK(other.is_end_);
3930  return it_->Ok();
3931  }
3932 
3933  private:
3934  Iterator(IntVarIterator* it, bool is_end) : it_(it), is_end_(is_end) {}
3935 
3936  IntVarIterator* const it_;
3937  const bool is_end_;
3938  };
3939 
3940  private:
3941  IntVarIterator* const it_;
3942  bool begin_was_called_;
3943 };
3944 #endif // SWIG
3945 
3949 class IntVar : public IntExpr {
3950  public:
3951  explicit IntVar(Solver* const s);
3952  IntVar(Solver* const s, const std::string& name);
3953  ~IntVar() override {}
3954 
3955  bool IsVar() const override { return true; }
3956  IntVar* Var() override { return this; }
3957 
3960  virtual int64 Value() const = 0;
3961 
3963  virtual void RemoveValue(int64 v) = 0;
3964 
3967  virtual void RemoveInterval(int64 l, int64 u) = 0;
3968 
3970  virtual void RemoveValues(const std::vector<int64>& values);
3971 
3973  virtual void SetValues(const std::vector<int64>& values);
3974 
3977  virtual void WhenBound(Demon* d) = 0;
3980  void WhenBound(Solver::Closure closure) {
3981  WhenBound(solver()->MakeClosureDemon(std::move(closure)));
3982  }
3983 
3984 #if !defined(SWIG)
3985  void WhenBound(Solver::Action action) {
3988  WhenBound(solver()->MakeActionDemon(std::move(action)));
3989  }
3990 #endif // SWIG
3991 
3994  virtual void WhenDomain(Demon* d) = 0;
3997  void WhenDomain(Solver::Closure closure) {
3998  WhenDomain(solver()->MakeClosureDemon(std::move(closure)));
3999  }
4000 #if !defined(SWIG)
4001  void WhenDomain(Solver::Action action) {
4004  WhenDomain(solver()->MakeActionDemon(std::move(action)));
4005  }
4006 #endif // SWIG
4007 
4009  virtual uint64 Size() const = 0;
4010 
4013  virtual bool Contains(int64 v) const = 0;
4014 
4018  virtual IntVarIterator* MakeHoleIterator(bool reversible) const = 0;
4019 
4023  virtual IntVarIterator* MakeDomainIterator(bool reversible) const = 0;
4024 
4026  virtual int64 OldMin() const = 0;
4027 
4029  virtual int64 OldMax() const = 0;
4030 
4031  virtual int VarType() const;
4032 
4034  void Accept(ModelVisitor* const visitor) const override;
4035 
4037  virtual IntVar* IsEqual(int64 constant) = 0;
4038  virtual IntVar* IsDifferent(int64 constant) = 0;
4039  virtual IntVar* IsGreaterOrEqual(int64 constant) = 0;
4040  virtual IntVar* IsLessOrEqual(int64 constant) = 0;
4041 
4043  int index() const { return index_; }
4044 
4045  private:
4046  const int index_;
4047  DISALLOW_COPY_AND_ASSIGN(IntVar);
4048 };
4049 
4053 class SolutionCollector : public SearchMonitor {
4054  public:
4055  SolutionCollector(Solver* const solver, const Assignment* assignment);
4056  explicit SolutionCollector(Solver* const solver);
4057  ~SolutionCollector() override;
4058  std::string DebugString() const override { return "SolutionCollector"; }
4059 
4061  void Add(IntVar* const var);
4062  void Add(const std::vector<IntVar*>& vars);
4063  void Add(IntervalVar* const var);
4064  void Add(const std::vector<IntervalVar*>& vars);
4065  void Add(SequenceVar* const var);
4066  void Add(const std::vector<SequenceVar*>& vars);
4067  void AddObjective(IntVar* const objective);
4068 
4070  void EnterSearch() override;
4071 
4073  int solution_count() const;
4074 
4076  Assignment* solution(int n) const;
4077 
4079  int64 wall_time(int n) const;
4080 
4082  int64 branches(int n) const;
4083 
4086  int64 failures(int n) const;
4087 
4089  int64 objective_value(int n) const;
4090 
4092  int64 Value(int n, IntVar* const var) const;
4093 
4095  int64 StartValue(int n, IntervalVar* const var) const;
4096 
4098  int64 EndValue(int n, IntervalVar* const var) const;
4099 
4101  int64 DurationValue(int n, IntervalVar* const var) const;
4102 
4104  int64 PerformedValue(int n, IntervalVar* const var) const;
4105 
4109  const std::vector<int>& ForwardSequence(int n, SequenceVar* const var) const;
4113  const std::vector<int>& BackwardSequence(int n, SequenceVar* const var) const;
4116  const std::vector<int>& Unperformed(int n, SequenceVar* const var) const;
4117 
4118  protected:
4119  struct SolutionData {
4120  Assignment* solution;
4121  int64 time;
4122  int64 branches;
4123  int64 failures;
4124  int64 objective_value;
4125  bool operator<(const SolutionData& other) const {
4126  return std::tie(solution, time, branches, failures, objective_value) <
4127  std::tie(other.solution, other.time, other.branches,
4128  other.failures, other.objective_value);
4129  }
4130  };
4131 
4133  void PushSolution();
4134  void Push(const SolutionData& data) { solution_data_.push_back(data); }
4136  void PopSolution();
4137  SolutionData BuildSolutionDataForCurrentState();
4138  void FreeSolution(Assignment* solution);
4139  void check_index(int n) const;
4140 
4141  std::unique_ptr<Assignment> prototype_;
4142  std::vector<SolutionData> solution_data_;
4143  std::vector<Assignment*> recycle_solutions_;
4144 
4145  private:
4146  DISALLOW_COPY_AND_ASSIGN(SolutionCollector);
4147 };
4148 
4149 // TODO(user): Refactor this into an Objective class:
4150 // - print methods for AtNode and AtSolution.
4151 // - support for weighted objective and lexicographical objective.
4152 
4156 class OptimizeVar : public SearchMonitor {
4157  public:
4158  OptimizeVar(Solver* const s, bool maximize, IntVar* const a, int64 step);
4159  ~OptimizeVar() override;
4160 
4162  int64 best() const { return best_; }
4163 
4165  IntVar* Var() const { return var_; }
4167  bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;
4168  void EnterSearch() override;
4169  void BeginNextDecision(DecisionBuilder* const db) override;
4170  void RefuteDecision(Decision* const d) override;
4171  bool AtSolution() override;
4172  bool AcceptSolution() override;
4173  virtual std::string Print() const;
4174  std::string DebugString() const override;
4175  void Accept(ModelVisitor* const visitor) const override;
4176 
4177  void ApplyBound();
4178 
4179  protected:
4180  IntVar* const var_;
4181  int64 step_;
4182  int64 best_;
4183  bool maximize_;
4184  bool found_initial_solution_;
4185 
4186  private:
4187  DISALLOW_COPY_AND_ASSIGN(OptimizeVar);
4188 };
4189 
4191 class SearchLimit : public SearchMonitor {
4192  public:
4193  explicit SearchLimit(Solver* const s) : SearchMonitor(s), crossed_(false) {}
4194  ~SearchLimit() override;
4195 
4197  bool crossed() const { return crossed_; }
4198 
4203  virtual bool Check() = 0;
4204 
4206  virtual void Init() = 0;
4207 
4210  virtual void Copy(const SearchLimit* const limit) = 0;
4211 
4213  virtual SearchLimit* MakeClone() const = 0;
4214 
4216  void EnterSearch() override;
4217  void BeginNextDecision(DecisionBuilder* const b) override;
4218  void PeriodicCheck() override;
4219  void RefuteDecision(Decision* const d) override;
4220  std::string DebugString() const override {
4221  return absl::StrFormat("SearchLimit(crossed = %i)", crossed_);
4222  }
4223 
4224  private:
4225  void TopPeriodicCheck();
4226 
4227  bool crossed_;
4228  DISALLOW_COPY_AND_ASSIGN(SearchLimit);
4229 };
4230 
4233 class RegularLimit : public SearchLimit {
4234  public:
4235  RegularLimit(Solver* const s, absl::Duration time, int64 branches,
4236  int64 failures, int64 solutions, bool smart_time_check,
4237  bool cumulative);
4238  ~RegularLimit() override;
4239  void Copy(const SearchLimit* const limit) override;
4240  SearchLimit* MakeClone() const override;
4241  RegularLimit* MakeIdenticalClone() const;
4242  bool Check() override;
4243  void Init() override;
4244  void ExitSearch() override;
4245  void UpdateLimits(int64 time, int64 branches, int64 failures,
4246  int64 solutions);
4247  absl::Duration duration_limit() const { return duration_limit_; }
4248  int64 wall_time() const {
4249  return duration_limit_ == absl::InfiniteDuration()
4250  ? kint64max
4251  : absl::ToInt64Milliseconds(duration_limit());
4252  }
4253  int64 branches() const { return branches_; }
4254  int64 failures() const { return failures_; }
4255  int64 solutions() const { return solutions_; }
4256  bool IsUncheckedSolutionLimitReached() override;
4257  int ProgressPercent() override;
4258  std::string DebugString() const override;
4259 
4260  absl::Time AbsoluteSolverDeadline() const {
4261  return solver_time_at_limit_start_ + duration_limit_;
4262  }
4263 
4264  void Accept(ModelVisitor* const visitor) const override;
4265 
4266  private:
4267  bool CheckTime();
4268  absl::Duration TimeElapsed();
4269  static int64 GetPercent(int64 value, int64 offset, int64 total) {
4270  return (total > 0 && total < kint64max) ? 100 * (value - offset) / total
4271  : -1;
4272  }
4273 
4274  absl::Duration duration_limit_;
4275  absl::Time solver_time_at_limit_start_;
4276  absl::Duration last_time_elapsed_;
4277  int64 check_count_;
4278  int64 next_check_;
4279  bool smart_time_check_;
4280  int64 branches_;
4281  int64 branches_offset_;
4282  int64 failures_;
4283  int64 failures_offset_;
4284  int64 solutions_;
4285  int64 solutions_offset_;
4293  bool cumulative_;
4294 };
4295 
4306 class IntervalVar : public PropagationBaseObject {
4307  public:
4309  static const int64 kMinValidValue;
4311  static const int64 kMaxValidValue;
4312  IntervalVar(Solver* const solver, const std::string& name)
4313  : PropagationBaseObject(solver) {
4314  set_name(name);
4315  }
4316  ~IntervalVar() override {}
4317 
4320  virtual int64 StartMin() const = 0;
4321  virtual int64 StartMax() const = 0;
4322  virtual void SetStartMin(int64 m) = 0;
4323  virtual void SetStartMax(int64 m) = 0;
4324  virtual void SetStartRange(int64 mi, int64 ma) = 0;
4325  virtual int64 OldStartMin() const = 0;
4326  virtual int64 OldStartMax() const = 0;
4327  virtual void WhenStartRange(Demon* const d) = 0;
4328  void WhenStartRange(Solver::Closure closure) {
4329  WhenStartRange(solver()->MakeClosureDemon(std::move(closure)));
4330  }
4331 #if !defined(SWIG)
4332  void WhenStartRange(Solver::Action action) {
4333  WhenStartRange(solver()->MakeActionDemon(std::move(action)));
4334  }
4335 #endif // SWIG
4336  virtual void WhenStartBound(Demon* const d) = 0;
4337  void WhenStartBound(Solver::Closure closure) {
4338  WhenStartBound(solver()->MakeClosureDemon(std::move(closure)));
4339  }
4340 #if !defined(SWIG)
4341  void WhenStartBound(Solver::Action action) {
4342  WhenStartBound(solver()->MakeActionDemon(std::move(action)));
4343  }
4344 #endif // SWIG
4345 
4347  virtual int64 DurationMin() const = 0;
4348  virtual int64 DurationMax() const = 0;
4349  virtual void SetDurationMin(int64 m) = 0;
4350  virtual void SetDurationMax(int64 m) = 0;
4351  virtual void SetDurationRange(int64 mi, int64 ma) = 0;
4352  virtual int64 OldDurationMin() const = 0;
4353  virtual int64 OldDurationMax() const = 0;
4354  virtual void WhenDurationRange(Demon* const d) = 0;
4355  void WhenDurationRange(Solver::Closure closure) {
4356  WhenDurationRange(solver()->MakeClosureDemon(std::move(closure)));
4357  }
4358 #if !defined(SWIG)
4359  void WhenDurationRange(Solver::Action action) {
4360  WhenDurationRange(solver()->MakeActionDemon(std::move(action)));
4361  }
4362 #endif // SWIG
4363  virtual void WhenDurationBound(Demon* const d) = 0;
4364  void WhenDurationBound(Solver::Closure closure) {
4365  WhenDurationBound(solver()->MakeClosureDemon(std::move(closure)));
4366  }
4367 #if !defined(SWIG)
4368  void WhenDurationBound(Solver::Action action) {
4369  WhenDurationBound(solver()->MakeActionDemon(std::move(action)));
4370  }
4371 #endif // SWIG
4372 
4374  virtual int64 EndMin() const = 0;
4375  virtual int64 EndMax() const = 0;
4376  virtual void SetEndMin(int64 m) = 0;
4377  virtual void SetEndMax(int64 m) = 0;
4378  virtual void SetEndRange(int64 mi, int64 ma) = 0;
4379  virtual int64 OldEndMin() const = 0;
4380  virtual int64 OldEndMax() const = 0;
4381  virtual void WhenEndRange(Demon* const d) = 0;
4382  void WhenEndRange(Solver::Closure closure) {
4383  WhenEndRange(solver()->MakeClosureDemon(std::move(closure)));
4384  }
4385 #if !defined(SWIG)
4386  void WhenEndRange(Solver::Action action) {
4387  WhenEndRange(solver()->MakeActionDemon(std::move(action)));
4388  }
4389 #endif // SWIG
4390  virtual void WhenEndBound(Demon* const d) = 0;
4391  void WhenEndBound(Solver::Closure closure) {
4392  WhenEndBound(solver()->MakeClosureDemon(std::move(closure)));
4393  }
4394 #if !defined(SWIG)
4395  void WhenEndBound(Solver::Action action) {
4396  WhenEndBound(solver()->MakeActionDemon(std::move(action)));
4397  }
4398 #endif // SWIG
4399 
4402  virtual bool MustBePerformed() const = 0;
4403  virtual bool MayBePerformed() const = 0;
4404  bool CannotBePerformed() const { return !MayBePerformed(); }
4405  bool IsPerformedBound() const {
4406  return MustBePerformed() || !MayBePerformed();
4407  }
4408  virtual void SetPerformed(bool val) = 0;
4409  virtual bool WasPerformedBound() const = 0;
4410  virtual void WhenPerformedBound(Demon* const d) = 0;
4411  void WhenPerformedBound(Solver::Closure closure) {
4412  WhenPerformedBound(solver()->MakeClosureDemon(std::move(closure)));
4413  }
4414 #if !defined(SWIG)
4415  void WhenPerformedBound(Solver::Action action) {
4416  WhenPerformedBound(solver()->MakeActionDemon(std::move(action)));
4417  }
4418 #endif // SWIG
4419 
4421  void WhenAnything(Demon* const d);
4423  void WhenAnything(Solver::Closure closure) {
4424  WhenAnything(solver()->MakeClosureDemon(std::move(closure)));
4425  }
4426 #if !defined(SWIG)
4427  void WhenAnything(Solver::Action action) {
4429  WhenAnything(solver()->MakeActionDemon(std::move(action)));
4430  }
4431 #endif // SWIG
4432 
4436  virtual IntExpr* StartExpr() = 0;
4437  virtual IntExpr* DurationExpr() = 0;
4438  virtual IntExpr* EndExpr() = 0;
4439  virtual IntExpr* PerformedExpr() = 0;
4443  virtual IntExpr* SafeStartExpr(int64 unperformed_value) = 0;
4444  virtual IntExpr* SafeDurationExpr(int64 unperformed_value) = 0;
4445  virtual IntExpr* SafeEndExpr(int64 unperformed_value) = 0;
4446 
4448  virtual void Accept(ModelVisitor* const visitor) const = 0;
4449 
4450  private:
4451  DISALLOW_COPY_AND_ASSIGN(IntervalVar);
4452 };
4453 
4460 class SequenceVar : public PropagationBaseObject {
4461  public:
4462  SequenceVar(Solver* const s, const std::vector<IntervalVar*>& intervals,
4463  const std::vector<IntVar*>& nexts, const std::string& name);
4464 
4465  ~SequenceVar() override;
4466 
4467  std::string DebugString() const override;
4468 
4469 #if !defined(SWIG)
4470  void DurationRange(int64* const dmin, int64* const dmax) const;
4473 
4476  void HorizonRange(int64* const hmin, int64* const hmax) const;
4477 
4480  void ActiveHorizonRange(int64* const hmin, int64* const hmax) const;
4481 
4483  void ComputeStatistics(int* const ranked, int* const not_ranked,
4484  int* const unperformed) const;
4485 #endif // !defined(SWIG)
4486 
4489  void RankFirst(int index);
4490 
4493  void RankNotFirst(int index);
4494 
4497  void RankLast(int index);
4498 
4501  void RankNotLast(int index);
4502 
4505  void ComputePossibleFirstsAndLasts(std::vector<int>* const possible_firsts,
4506  std::vector<int>* const possible_lasts);
4507 
4513  void RankSequence(const std::vector<int>& rank_first,
4514  const std::vector<int>& rank_last,
4515  const std::vector<int>& unperformed);
4516 
4525  void FillSequence(std::vector<int>* const rank_first,
4526  std::vector<int>* const rank_last,
4527  std::vector<int>* const unperformed) const;
4528 
4530  IntervalVar* Interval(int index) const;
4531 
4533  IntVar* Next(int index) const;
4534 
4536  int64 size() const { return intervals_.size(); }
4537 
4539  virtual void Accept(ModelVisitor* const visitor) const;
4540 
4541  private:
4542  int ComputeForwardFrontier();
4543  int ComputeBackwardFrontier();
4544  void UpdatePrevious() const;
4545 
4546  const std::vector<IntervalVar*> intervals_;
4547  const std::vector<IntVar*> nexts_;
4548  mutable std::vector<int> previous_;
4549 };
4550 
4551 class AssignmentElement {
4552  public:
4553  AssignmentElement() : activated_(true) {}
4554 
4555  void Activate() { activated_ = true; }
4556  void Deactivate() { activated_ = false; }
4557  bool Activated() const { return activated_; }
4558 
4559  private:
4560  bool activated_;
4561 };
4562 
4563 class IntVarElement : public AssignmentElement {
4564  public:
4565  IntVarElement();
4566  explicit IntVarElement(IntVar* const var);
4567  void Reset(IntVar* const var);
4568  IntVarElement* Clone();
4569  void Copy(const IntVarElement& element);
4570  IntVar* Var() const { return var_; }
4571  void Store() {
4572  min_ = var_->Min();
4573  max_ = var_->Max();
4574  }
4575  void Restore() {
4576  if (var_ != nullptr) {
4577  var_->SetRange(min_, max_);
4578  }
4579  }
4580  void LoadFromProto(const IntVarAssignment& int_var_assignment_proto);
4581  void WriteToProto(IntVarAssignment* int_var_assignment_proto) const;
4582 
4583  int64 Min() const { return min_; }
4584  void SetMin(int64 m) { min_ = m; }
4585  int64 Max() const { return max_; }
4586  void SetMax(int64 m) { max_ = m; }
4587  int64 Value() const {
4588  DCHECK_EQ(min_, max_);
4589  // Get the value from an unbound int var assignment element.
4590  return min_;
4591  }
4592  bool Bound() const { return (max_ == min_); }
4593  void SetRange(int64 l, int64 u) {
4594  min_ = l;
4595  max_ = u;
4596  }
4597  void SetValue(int64 v) {
4598  min_ = v;
4599  max_ = v;
4600  }
4601  std::string DebugString() const;
4602 
4603  bool operator==(const IntVarElement& element) const;
4604  bool operator!=(const IntVarElement& element) const {
4605  return !(*this == element);
4606  }
4607 
4608  private:
4609  IntVar* var_;
4610  int64 min_;
4611  int64 max_;
4612 };
4613 
4614 class IntervalVarElement : public AssignmentElement {
4615  public:
4616  IntervalVarElement();
4617  explicit IntervalVarElement(IntervalVar* const var);
4618  void Reset(IntervalVar* const var);
4619  IntervalVarElement* Clone();
4620  void Copy(const IntervalVarElement& element);
4621  IntervalVar* Var() const { return var_; }
4622  void Store();
4623  void Restore();
4624  void LoadFromProto(
4625  const IntervalVarAssignment& interval_var_assignment_proto);
4626  void WriteToProto(IntervalVarAssignment* interval_var_assignment_proto) const;
4627 
4628  int64 StartMin() const { return start_min_; }
4629  int64 StartMax() const { return start_max_; }
4630  int64 StartValue() const {
4631  CHECK_EQ(start_max_, start_min_);
4632  return start_max_;
4633  }
4634  int64 DurationMin() const { return duration_min_; }
4635  int64 DurationMax() const { return duration_max_; }
4636  int64 DurationValue() const {
4637  CHECK_EQ(duration_max_, duration_min_);
4638  return duration_max_;
4639  }
4640  int64 EndMin() const { return end_min_; }
4641  int64 EndMax() const { return end_max_; }
4642  int64 EndValue() const {
4643  CHECK_EQ(end_max_, end_min_);
4644  return end_max_;
4645  }
4646  int64 PerformedMin() const { return performed_min_; }
4647  int64 PerformedMax() const { return performed_max_; }
4648  int64 PerformedValue() const {
4649  CHECK_EQ(performed_max_, performed_min_);
4650  return performed_max_;
4651  }
4652  void SetStartMin(int64 m) { start_min_ = m; }
4653  void SetStartMax(int64 m) { start_max_ = m; }
4654  void SetStartRange(int64 mi, int64 ma) {
4655  start_min_ = mi;
4656  start_max_ = ma;
4657  }
4658  void SetStartValue(int64 v) {
4659  start_min_ = v;
4660  start_max_ = v;
4661  }
4662  void SetDurationMin(int64 m) { duration_min_ = m; }
4663  void SetDurationMax(int64 m) { duration_max_ = m; }
4664  void SetDurationRange(int64 mi, int64 ma) {
4665  duration_min_ = mi;
4666  duration_max_ = ma;
4667  }
4668  void SetDurationValue(int64 v) {
4669  duration_min_ = v;
4670  duration_max_ = v;
4671  }
4672  void SetEndMin(int64 m) { end_min_ = m; }
4673  void SetEndMax(int64 m) { end_max_ = m; }
4674  void SetEndRange(int64 mi, int64 ma) {
4675  end_min_ = mi;
4676  end_max_ = ma;
4677  }
4678  void SetEndValue(int64 v) {
4679  end_min_ = v;
4680  end_max_ = v;
4681  }
4682  void SetPerformedMin(int64 m) { performed_min_ = m; }
4683  void SetPerformedMax(int64 m) { performed_max_ = m; }
4684  void SetPerformedRange(int64 mi, int64 ma) {
4685  performed_min_ = mi;
4686  performed_max_ = ma;
4687  }
4688  void SetPerformedValue(int64 v) {
4689  performed_min_ = v;
4690  performed_max_ = v;
4691  }
4692  bool Bound() const {
4693  return (start_min_ == start_max_ && duration_min_ == duration_max_ &&
4694  end_min_ == end_max_ && performed_min_ == performed_max_);
4695  }
4696  std::string DebugString() const;
4697  bool operator==(const IntervalVarElement& element) const;
4698  bool operator!=(const IntervalVarElement& element) const {
4699  return !(*this == element);
4700  }
4701 
4702  private:
4703  int64 start_min_;
4704  int64 start_max_;
4705  int64 duration_min_;
4706  int64 duration_max_;
4707  int64 end_min_;
4708  int64 end_max_;
4709  int64 performed_min_;
4710  int64 performed_max_;
4711  IntervalVar* var_;
4712 };
4713 
4727 class SequenceVarElement : public AssignmentElement {
4728  public:
4729  SequenceVarElement();
4730  explicit SequenceVarElement(SequenceVar* const var);
4731  void Reset(SequenceVar* const var);
4732  SequenceVarElement* Clone();
4733  void Copy(const SequenceVarElement& element);
4734  SequenceVar* Var() const { return var_; }
4735  void Store();
4736  void Restore();
4737  void LoadFromProto(
4738  const SequenceVarAssignment& sequence_var_assignment_proto);
4739  void WriteToProto(SequenceVarAssignment* sequence_var_assignment_proto) const;
4740 
4741  const std::vector<int>& ForwardSequence() const;
4742  const std::vector<int>& BackwardSequence() const;
4743  const std::vector<int>& Unperformed() const;
4744  void SetSequence(const std::vector<int>& forward_sequence,
4745  const std::vector<int>& backward_sequence,
4746  const std::vector<int>& unperformed);
4747  void SetForwardSequence(const std::vector<int>& forward_sequence);
4748  void SetBackwardSequence(const std::vector<int>& backward_sequence);
4749  void SetUnperformed(const std::vector<int>& unperformed);
4750  bool Bound() const {
4751  return forward_sequence_.size() + unperformed_.size() == var_->size();
4752  }
4753 
4754  std::string DebugString() const;
4755 
4756  bool operator==(const SequenceVarElement& element) const;
4757  bool operator!=(const SequenceVarElement& element) const {
4758  return !(*this == element);
4759  }
4760 
4761  private:
4762  bool CheckClassInvariants();
4763 
4764  SequenceVar* var_;
4765  std::vector<int> forward_sequence_;
4766  std::vector<int> backward_sequence_;
4767  std::vector<int> unperformed_;
4768 };
4769 
4770 template <class V, class E>
4771 class AssignmentContainer {
4772  public:
4773  AssignmentContainer() {}
4774  E* Add(V* var) {
4775  CHECK(var != nullptr);
4776  int index = -1;
4777  if (!Find(var, &index)) {
4778  return FastAdd(var);
4779  } else {
4780  return &elements_[index];
4781  }
4782  }
4784  E* FastAdd(V* var) {
4785  DCHECK(var != nullptr);
4786  elements_.emplace_back(var);
4787  return &elements_.back();
4788  }
4791  E* AddAtPosition(V* var, int position) {
4792  elements_[position].Reset(var);
4793  return &elements_[position];
4794  }
4795  void Clear() {
4796  elements_.clear();
4797  if (!elements_map_.empty()) {
4798  elements_map_.clear();
4799  }
4800  }
4803  void Resize(size_t size) { elements_.resize(size); }
4804  bool Empty() const { return elements_.empty(); }
4807  void CopyIntersection(const AssignmentContainer<V, E>& container) {
4808  for (int i = 0; i < container.elements_.size(); ++i) {
4809  const E& element = container.elements_[i];
4810  const V* const var = element.Var();
4811  int index = -1;
4812  if (i < elements_.size() && elements_[i].Var() == var) {
4813  index = i;
4814  } else if (!Find(var, &index)) {
4815  continue;
4816  }
4817  DCHECK_GE(index, 0);
4818  E* const local_element = &elements_[index];
4819  local_element->Copy(element);
4820  if (element.Activated()) {
4821  local_element->Activate();
4822  } else {
4823  local_element->Deactivate();
4824  }
4825  }
4826  }
4829  void Copy(const AssignmentContainer<V, E>& container) {
4830  Clear();
4831  for (int i = 0; i < container.elements_.size(); ++i) {
4832  const E& element = container.elements_[i];
4833  FastAdd(element.Var())->Copy(element);
4834  }
4835  }
4836  bool Contains(const V* const var) const {
4837  int index;
4838  return Find(var, &index);
4839  }
4840  E* MutableElement(const V* const var) {
4841  E* const element = MutableElementOrNull(var);
4842  DCHECK(element != nullptr)
4843  << "Unknown variable " << var->DebugString() << " in solution";
4844  return element;
4845  }
4846  E* MutableElementOrNull(const V* const var) {
4847  int index = -1;
4848  if (Find(var, &index)) {
4849  return MutableElement(index);
4850  }
4851  return nullptr;
4852  }
4853  const E& Element(const V* const var) const {
4854  const E* const element = ElementPtrOrNull(var);
4855  DCHECK(element != nullptr)
4856  << "Unknown variable " << var->DebugString() << " in solution";
4857  return *element;
4858  }
4859  const E* ElementPtrOrNull(const V* const var) const {
4860  int index = -1;
4861  if (Find(var, &index)) {
4862  return &Element(index);
4863  }
4864  return nullptr;
4865  }
4866  const std::vector<E>& elements() const { return elements_; }
4867  E* MutableElement(int index) { return &elements_[index]; }
4868  const E& Element(int index) const { return elements_[index]; }
4869  int Size() const { return elements_.size(); }
4870  void Store() {
4871  for (E& element : elements_) {
4872  element.Store();
4873  }
4874  }
4875  void Restore() {
4876  for (E& element : elements_) {
4877  if (element.Activated()) {
4878  element.Restore();
4879  }
4880  }
4881  }
4882  bool AreAllElementsBound() const {
4883  for (const E& element : elements_) {
4884  if (!element.Bound()) return false;
4885  }
4886  return true;
4887  }
4888 
4892  bool operator==(const AssignmentContainer<V, E>& container) const {
4894  if (Size() != container.Size()) {
4895  return false;
4896  }
4898  EnsureMapIsUpToDate();
4902  for (const E& element : container.elements_) {
4903  const int position =
4904  gtl::FindWithDefault(elements_map_, element.Var(), -1);
4905  if (position < 0 || elements_[position] != element) {
4906  return false;
4907  }
4908  }
4909  return true;
4910  }
4911  bool operator!=(const AssignmentContainer<V, E>& container) const {
4912  return !(*this == container);
4913  }
4914 
4915  private:
4916  void EnsureMapIsUpToDate() const {
4917  absl::flat_hash_map<const V*, int>* map =
4918  const_cast<absl::flat_hash_map<const V*, int>*>(&elements_map_);
4919  for (int i = map->size(); i < elements_.size(); ++i) {
4920  (*map)[elements_[i].Var()] = i;
4921  }
4922  }
4923  bool Find(const V* const var, int* index) const {
4925  const size_t kMaxSizeForLinearAccess = 11;
4926  if (Size() <= kMaxSizeForLinearAccess) {
4930  for (int i = 0; i < elements_.size(); ++i) {
4931  if (var == elements_[i].Var()) {
4932  *index = i;
4933  return true;
4934  }
4935  }
4936  return false;
4937  } else {
4938  EnsureMapIsUpToDate();
4939  DCHECK_EQ(elements_map_.size(), elements_.size());
4940  return gtl::FindCopy(elements_map_, var, index);
4941  }
4942  }
4943 
4944  std::vector<E> elements_;
4945  absl::flat_hash_map<const V*, int> elements_map_;
4946 };
4947 
4950 class Assignment : public PropagationBaseObject {
4951  public:
4952  typedef AssignmentContainer<IntVar, IntVarElement> IntContainer;
4953  typedef AssignmentContainer<IntervalVar, IntervalVarElement>
4954  IntervalContainer;
4955  typedef AssignmentContainer<SequenceVar, SequenceVarElement>
4956  SequenceContainer;
4957 
4958  explicit Assignment(Solver* const s);
4959  explicit Assignment(const Assignment* const copy);
4960  ~Assignment() override;
4961 
4962  void Clear();
4963  bool Empty() const {
4964  return int_var_container_.Empty() && interval_var_container_.Empty() &&
4965  sequence_var_container_.Empty();
4966  }
4967  int Size() const {
4968  return NumIntVars() + NumIntervalVars() + NumSequenceVars();
4969  }
4970  int NumIntVars() const { return int_var_container_.Size(); }
4971  int NumIntervalVars() const { return interval_var_container_.Size(); }
4972  int NumSequenceVars() const { return sequence_var_container_.Size(); }
4973  void Store();
4974  void Restore();
4975 
4978  bool Load(const std::string& filename);
4979 #if !defined(SWIG)
4980  bool Load(File* file);
4981 #endif
4982  void Load(const AssignmentProto& assignment_proto);
4983  bool Save(const std::string& filename) const;
4985 #if !defined(SWIG)
4986  bool Save(File* file) const;
4987 #endif // #if !defined(SWIG)
4988  void Save(AssignmentProto* const assignment_proto) const;
4989 
4990  void AddObjective(IntVar* const v);
4991  void ClearObjective() { objective_element_.Reset(nullptr); }
4992  IntVar* Objective() const;
4993  bool HasObjective() const { return (objective_element_.Var() != nullptr); }
4994  int64 ObjectiveMin() const;
4995  int64 ObjectiveMax() const;
4996  int64 ObjectiveValue() const;
4997  bool ObjectiveBound() const;
4998  void SetObjectiveMin(int64 m);
4999  void SetObjectiveMax(int64 m);
5000  void SetObjectiveValue(int64 value);
5001  void SetObjectiveRange(int64 l, int64 u);
5002 
5003  IntVarElement* Add(IntVar* const var);
5004  void Add(const std::vector<IntVar*>& vars);
5006  IntVarElement* FastAdd(IntVar* const var);
5007  int64 Min(const IntVar* const var) const;
5008  int64 Max(const IntVar* const var) const;
5009  int64 Value(const IntVar* const var) const;
5010  bool Bound(const IntVar* const var) const;
5011  void SetMin(const IntVar* const var, int64 m);
5012  void SetMax(const IntVar* const var, int64 m);
5013  void SetRange(const IntVar* const var, int64 l, int64 u);
5014  void SetValue(const IntVar* const var, int64 value);
5015 
5016  IntervalVarElement* Add(IntervalVar* const var);
5017  void Add(const std::vector<IntervalVar*>& vars);
5019  IntervalVarElement* FastAdd(IntervalVar* const var);
5020  int64 StartMin(const IntervalVar* const var) const;
5021  int64 StartMax(const IntervalVar* const var) const;
5022  int64 StartValue(const IntervalVar* const var) const;
5023  int64 DurationMin(const IntervalVar* const var) const;
5024  int64 DurationMax(const IntervalVar* const var) const;
5025  int64 DurationValue(const IntervalVar* const var) const;
5026  int64 EndMin(const IntervalVar* const var) const;
5027  int64 EndMax(const IntervalVar* const var) const;
5028  int64 EndValue(const IntervalVar* const var) const;
5029  int64 PerformedMin(const IntervalVar* const var) const;
5030  int64 PerformedMax(const IntervalVar* const var) const;
5031  int64 PerformedValue(const IntervalVar* const var) const;
5032  void SetStartMin(const IntervalVar* const var, int64 m);
5033  void SetStartMax(const IntervalVar* const var, int64 m);
5034  void SetStartRange(const IntervalVar* const var, int64 mi, int64 ma);
5035  void SetStartValue(const IntervalVar* const var, int64 value);
5036  void SetDurationMin(const IntervalVar* const var, int64 m);
5037  void SetDurationMax(const IntervalVar* const var, int64 m);
5038  void SetDurationRange(const IntervalVar* const var, int64 mi, int64 ma);
5039  void SetDurationValue(const IntervalVar* const var, int64 value);
5040  void SetEndMin(const IntervalVar* const var, int64 m);
5041  void SetEndMax(const IntervalVar* const var, int64 m);
5042  void SetEndRange(const IntervalVar* const var, int64 mi, int64 ma);
5043  void SetEndValue(const IntervalVar* const var, int64 value);
5044  void SetPerformedMin(const IntervalVar* const var, int64 m);
5045  void SetPerformedMax(const IntervalVar* const var, int64 m);
5046  void SetPerformedRange(const IntervalVar* const var, int64 mi, int64 ma);
5047  void SetPerformedValue(const IntervalVar* const var, int64 value);
5048 
5049  SequenceVarElement* Add(SequenceVar* const var);
5050  void Add(const std::vector<SequenceVar*>& vars);
5052  SequenceVarElement* FastAdd(SequenceVar* const var);
5053  const std::vector<int>& ForwardSequence(const SequenceVar* const var) const;
5054  const std::vector<int>& BackwardSequence(const SequenceVar* const var) const;
5055  const std::vector<int>& Unperformed(const SequenceVar* const var) const;
5056  void SetSequence(const SequenceVar* const var,
5057  const std::vector<int>& forward_sequence,
5058  const std::vector<int>& backward_sequence,
5059  const std::vector<int>& unperformed);
5060  void SetForwardSequence(const SequenceVar* const var,
5061  const std::vector<int>& forward_sequence);
5062  void SetBackwardSequence(const SequenceVar* const var,
5063  const std::vector<int>& backward_sequence);
5064  void SetUnperformed(const SequenceVar* const var,
5065  const std::vector<int>& unperformed);
5066 
5067  void Activate(const IntVar* const var);
5068  void Deactivate(const IntVar* const var);
5069  bool Activated(const IntVar* const var) const;
5070 
5071  void Activate(const IntervalVar* const var);
5072  void Deactivate(const IntervalVar* const var);
5073  bool Activated(const IntervalVar* const var) const;
5074 
5075  void Activate(const SequenceVar* const var);
5076  void Deactivate(const SequenceVar* const var);
5077  bool Activated(const SequenceVar* const var) const;
5078 
5079  void ActivateObjective();
5080  void DeactivateObjective();
5081  bool ActivatedObjective() const;
5082 
5083  std::string DebugString() const override;
5084 
5085  bool AreAllElementsBound() const {
5086  return int_var_container_.AreAllElementsBound() &&
5087  interval_var_container_.AreAllElementsBound() &&
5088  sequence_var_container_.AreAllElementsBound();
5089  }
5090 
5091  bool Contains(const IntVar* const var) const;
5092  bool Contains(const IntervalVar* const var) const;
5093  bool Contains(const SequenceVar* const var) const;
5095  void CopyIntersection(const Assignment* assignment);
5098  void Copy(const Assignment* assignment);
5099 
5100  // TODO(user): Add element iterators to avoid exposing container class.
5101  const IntContainer& IntVarContainer() const { return int_var_container_; }
5102  IntContainer* MutableIntVarContainer() { return &int_var_container_; }
5103  const IntervalContainer& IntervalVarContainer() const {
5104  return interval_var_container_;
5105  }
5106  IntervalContainer* MutableIntervalVarContainer() {
5107  return &interval_var_container_;
5108  }
5109  const SequenceContainer& SequenceVarContainer() const {
5110  return sequence_var_container_;
5111  }
5112  SequenceContainer* MutableSequenceVarContainer() {
5113  return &sequence_var_container_;
5114  }
5115  bool operator==(const Assignment& assignment) const {
5116  return int_var_container_ == assignment.int_var_container_ &&
5117  interval_var_container_ == assignment.interval_var_container_ &&
5118  sequence_var_container_ == assignment.sequence_var_container_ &&
5119  objective_element_ == assignment.objective_element_;
5120  }
5121  bool operator!=(const Assignment& assignment) const {
5122  return !(*this == assignment);
5123  }
5124 
5125  private:
5126  IntContainer int_var_container_;
5127  IntervalContainer interval_var_container_;
5128  SequenceContainer sequence_var_container_;
5129  IntVarElement objective_element_;
5130  DISALLOW_COPY_AND_ASSIGN(Assignment);
5131 };
5132 
5133 std::ostream& operator<<(std::ostream& out,
5134  const Assignment& assignment);
5135 
5141 void SetAssignmentFromAssignment(Assignment* target_assignment,
5142  const std::vector<IntVar*>& target_vars,
5143  const Assignment* source_assignment,
5144  const std::vector<IntVar*>& source_vars);
5145 
5146 class Pack : public Constraint {
5147  public:
5148  Pack(Solver* const s, const std::vector<IntVar*>& vars, int number_of_bins);
5149 
5150  ~Pack() override;
5151 
5156 
5160  void AddWeightedSumLessOrEqualConstantDimension(
5161  const std::vector<int64>& weights, const std::vector<int64>& bounds);
5162 
5167  void AddWeightedSumLessOrEqualConstantDimension(
5168  Solver::IndexEvaluator1 weights, const std::vector<int64>& bounds);
5169 
5174  void AddWeightedSumLessOrEqualConstantDimension(
5175  Solver::IndexEvaluator2 weights, const std::vector<int64>& bounds);
5176 
5179  void AddWeightedSumEqualVarDimension(const std::vector<int64>& weights,
5180  const std::vector<IntVar*>& loads);
5181 
5185  void AddWeightedSumEqualVarDimension(Solver::IndexEvaluator2 weights,
5186  const std::vector<IntVar*>& loads);
5187 
5197  void AddSumVariableWeightsLessOrEqualConstantDimension(
5198  const std::vector<IntVar*>& usage, const std::vector<int64>& capacity);
5199 
5202  void AddWeightedSumOfAssignedDimension(const std::vector<int64>& weights,
5203  IntVar* const cost_var);
5204 
5207  void AddCountUsedBinDimension(IntVar* const count_var);
5208 
5211  void AddCountAssignedItemsDimension(IntVar* const count_var);
5212 
5213  void Post() override;
5214  void ClearAll();
5215  void PropagateDelayed();
5216  void InitialPropagate() override;
5217  void Propagate();
5218  void OneDomain(int var_index);
5219  std::string DebugString() const override;
5220  bool IsUndecided(int var_index, int bin_index) const;
5221  void SetImpossible(int var_index, int bin_index);
5222  void Assign(int var_index, int bin_index);
5223  bool IsAssignedStatusKnown(int var_index) const;
5224  bool IsPossible(int var_index, int bin_index) const;
5225  IntVar* AssignVar(int var_index, int bin_index) const;
5226  void SetAssigned(int var_index);
5227  void SetUnassigned(int var_index);
5228  void RemoveAllPossibleFromBin(int bin_index);
5229  void AssignAllPossibleToBin(int bin_index);
5230  void AssignFirstPossibleToBin(int bin_index);
5231  void AssignAllRemainingItems();
5232  void UnassignAllRemainingItems();
5233  void Accept(ModelVisitor* const visitor) const override;
5234 
5235  private:
5236  bool IsInProcess() const;
5237  const std::vector<IntVar*> vars_;
5238  const int bins_;
5239  std::vector<Dimension*> dims_;
5240  std::unique_ptr<RevBitMatrix> unprocessed_;
5241  std::vector<std::vector<int>> forced_;
5242  std::vector<std::vector<int>> removed_;
5243  std::vector<IntVarIterator*> holes_;
5244  uint64 stamp_;
5245  Demon* demon_;
5246  std::vector<std::pair<int, int>> to_set_;
5247  std::vector<std::pair<int, int>> to_unset_;
5248  bool in_process_;
5249 };
5250 
5251 class DisjunctiveConstraint : public Constraint {
5252  public:
5253  DisjunctiveConstraint(Solver* const s,
5254  const std::vector<IntervalVar*>& intervals,
5255  const std::string& name);
5256  ~DisjunctiveConstraint() override;
5257 
5259  virtual SequenceVar* MakeSequenceVar() = 0;
5260 
5265  void SetTransitionTime(Solver::IndexEvaluator2 transition_time);
5266 
5267  int64 TransitionTime(int before_index, int after_index) {
5268  DCHECK(transition_time_);
5269  return transition_time_(before_index, after_index);
5270  }
5271 
5272 #if !defined(SWIG)
5273  virtual const std::vector<IntVar*>& nexts() const = 0;
5274  virtual const std::vector<IntVar*>& actives() const = 0;
5275  virtual const std::vector<IntVar*>& time_cumuls() const = 0;
5276  virtual const std::vector<IntVar*>& time_slacks() const = 0;
5277 #endif // !defined(SWIG)
5278 
5279  protected:
5280  const std::vector<IntervalVar*> intervals_;
5281  Solver::IndexEvaluator2 transition_time_;
5282 
5283  private:
5284  DISALLOW_COPY_AND_ASSIGN(DisjunctiveConstraint);
5285 };
5286 
5289 class SolutionPool : public BaseObject {
5290  public:
5291  SolutionPool() {}
5292  ~SolutionPool() override {}
5293 
5296  virtual void Initialize(Assignment* const assignment) = 0;
5297 
5300  virtual void RegisterNewSolution(Assignment* const assignment) = 0;
5301 
5304  virtual void GetNextSolution(Assignment* const assignment) = 0;
5305 
5308  virtual bool SyncNeeded(Assignment* const local_assignment) = 0;
5309 };
5310 } // namespace operations_research
5311 
5312 #endif // OR_TOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVER_H_
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
DECLARE_int64(cp_random_seed)
Declaration of the core objects for the constraint solver.